[BZOJ 1433]假期的宿舍

这几乎是个二分图匹配的裸题了……

不过有很多细节问题,比如说题面里提到的那些。还有多组数据的话注意清理数组。

代码:

/**************************************************************
    Problem: 1433
    User: danihao123
    Language: C++
    Result: Accepted
    Time:68 ms
    Memory:824 kb
****************************************************************/
 
#include <cstdio>
#include <cstring>
const int maxn=55;
bool G[maxn][maxn];
int n,m;
int Pei[maxn];
bool vis[maxn];
bool DFS(int x){
    int i;
    for(i=1;i<=m;i++)
        if(G[x][i] && !vis[i]){
            vis[i]=true;
            if(!Pei[i] || DFS(Pei[i])){
                Pei[i]=x;
                return true;
            }
        }
    return false;
}
int Hungray(){
    register int i,ans=0;
    memset(Pei,0,sizeof(Pei));
    for(i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(DFS(i))
            ans++;
    }
    return ans;
}
 
int Per[maxn],Bed[maxn];
bool isStudent[maxn],Back[maxn];
int main(){
    int T,N,u,v;
    register int i,j;
    scanf("%d",&T);
    while(T--){
        n=m=0;
        scanf("%d",&N);
        memset(G,0,sizeof(G));
        memset(Per,0,sizeof(Per));
        memset(Bed,0,sizeof(Bed));
        memset(isStudent,0,sizeof(isStudent));
        memset(Back,0,sizeof(Back));
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            isStudent[i]=u;
        }
        for(i=1;i<=N;i++){
            scanf("%d",&u);
            if(isStudent[i]){
                Back[i]=u;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                Bed[i]=++m;
                if(!Back[i]){
                    Per[i]=++n;
                }
            }else{
                Per[i]=++n;
            }
        }
        for(i=1;i<=N;i++){
            if(isStudent[i]){
                G[Per[i]][Bed[i]]=true;
            }
            for(j=1;j<=N;j++){
                scanf("%d",&v);
                if(v && isStudent[j]){
                    G[Per[i]][Bed[j]]=true;
                }
            }
        }
        if(Hungray()==n)
            puts("^_^");
        else
            puts("T_T");
    }
    return 0;
}

[BZOJ 1034]泡泡堂

这题其实就是一个田忌赛马类问题。贪心即可。

如果你不知道田忌赛马怎么贪,可以看《骗分导论》相关介绍(然而那个贪心不是骗分算法哦)。

代码:

/**************************************************************
    Problem: 1034
    User: danihao123
    Language: C++
    Result: Accepted
    Time:256 ms
    Memory:1604 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
#include <algorithm>
using namespace std;
const int maxn=100001;
int a[maxn],b[maxn];
int n;
inline int solve(int *A,int *B){
    register int L1=1,R1=n,L2=1,R2=n,ans=0;
    while(L1<=R1 && L2<=R2){
        if(A[L1]>B[L2]){
            ans+=2;
            L1++;
            L2++;
        }else{
            if(A[R1]>B[R2]){
                ans+=2;
                R1--;
                R2--;
            }else{
                if(A[L1]==B[R2])
                    ans++;
                L1++;
                R2--;
            }
        }
    }
    return ans;
}
int main(){
    register int i,ans;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(i=1;i<=n;i++)
        scanf("%d",&b[i]);
    sort(a+1,a+1+n);
    sort(b+1,b+1+n);
    printf("%d %d\n",solve(a,b),2*n-solve(b,a));
    return 0;
}

[BZOJ 1036]树的统计

终于A了这题了!

树剖大水题~

然而zzs这种蒟蒻还是要交很多次才过:

继续阅读