UVa 11825

【Topic Link】

Hackers’ Crackdown

【题意】

有N台机器,每台机器上有N个服务

你可以对每台机器选择关闭他以及和他相邻的机器的一种服务

当所有机器不能运行一个服务时,就是摧毁了一种服务

问你最多能摧毁多少个服务

【题解】

就是把n台电脑看成n个集合,每个集合的成员就是这台电脑,以及和这台电脑相邻的电脑;
我们就是要求把这些集合合并成尽量多的大集合,使每个集合都等于全集;也就是因为最开始的小集合,我们可以让它里面全部电脑的某一项服务全部失误,那如果合并成一个大集合,则这个大集合的某一项服务可以全部失效;所以能合并成几个等于全集的大集合,就可以让几项服务失效;

【Tip】

状态压缩,异或操作是相同得0,不同得1.LRJ这道题的位运算用的好…

【Source Code】

github: Uva 11825.cpp


#include<bits/stdc++.h>
using namespace std;
int N,T,P[1<<17],f[1<<17],cover[1<<17],ca=1;
int main(){
    while(~scanf("%d",&N),N){
        ///初始化第i台计算机的相邻集合
        for(int i=0;i<N;++i){
            int n,m;
            scanf("%d",&n);
            P[i]=1<<i;
            for(int j=0;j<n;++j){
                scanf("%d",&m);
                P[i] |= 1<<m;
            }
        }
        ///S是N个计算机的所有组合的集合,二进制表示,cover[S]是集合的并
        for(int S=0;S<(1<<N);++S){
            cover[S]=0;
            for(int i=0;i<N;++i){
                if(S & (1<<i)) cover[S] |= P[i];///第i台机器选/不选
            }
        }
        f[0]=0;
        int ALL=(1<<N)-1;///全集二进制表示
        for(int S=1;S<(1<<N);++S){
            f[S]=0;
            ///筛出S的子集进行动态规划
            for(int S0=S;S0;S0=(S0-1)&S){
                if(cover[S0]==ALL)///如果子集S的子集的并是全集
                    f[S]=max(f[S],f[S^S0]+1);
            }
        }
        printf("Case %d: %d\n",ca++,f[ALL]);
    }
    return 0;
}

第14届浙江省赛By Tusimple

【网赛链接】

第14届浙江省赛By Tusimple

【A】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int N,a1,T;
int Kobayashi[4]={1,0,1,-1},Kscore;
int Tohru[4]={0,1,1,-1},Tscore;
int main(){
    while(~SI(N)){
        while(N–){
            SI(T);
            Kscore=0;
            Tscore=0;
            rep(i,T){
                SI(a1);
                Kscore+=Kobayashi[a1-1];
                Tscore+=Tohru[a1-1];
            }
            if(Kscore>Tscore)
                puts(“Kobayashi”);
            else if(Tscore>Kscore)
                puts(“Tohru”);
            else
                puts(“Draw”);
        }
    }
    return 0;
}

【B】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
const int maxn=20000+10;
int T,N,fk,Orz,flag,cnt;
int score[maxn],scomp[maxn];
int main(){
    while(~SI(T)){
        while(T–){
            fill(score,score+4000,0);
            Orz=flag=0;
            SI(N);
            if(N>13 || N<10){
                rep(i,N){
                    SI(fk);
                }
                puts(“No”);continue;
            }
            rep(i,N){
                SI(fk);
                if(fk<=0){
                    flag=1;
                }else{
                    score[fk]++;
                }
                scomp[i]=fk;
            }
            if(flag){
                puts(“No”);
            }else{
                if(score[1]<2){
                    puts(“No”);
                    continue;
                }else{
                    sort(scomp,scomp+N);
                    rez(i,1,N-2){
                        if(scomp[i]-scomp[i-1]>2){
                            puts(“No”);
                            flag=1;
                            break;
                        }
                    }
                    if(!flag) puts(“Yes”);
                }
            }
        }
    }
    return 0;
}

【C】

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;
int T,n,q,c;
map<string,int> mp;
map<string,int>::iterator ite;
map<int,vector<string> > res;
string st;

inline int readt(int N){
    int ans=0,tit;
    rep(i,N){
        SI(tit);
        ans+=(1<<N-i-1) & (tit<<N-i-1);
    }
    return ans;
}

int main(){
    SI(T);
    while(T–){
        //测试数据可能出现重复的名字和情况,所以要初始化
        mp.clear();
        res.clear();
        SII(n,q);
        SI(c);
        rep(i,c){
            cin>>st;
            mp[st]=0;
        }
        rep(i,q){
            int nu;
            SI(nu);
            rep(j,nu){
                cin>>st;
                mp[st]+=(1<<q-i-1);
            }
        }
        for(ite=mp.begin();ite!=mp.end();ite++){
            res[ite->second].push_back(ite->first);
        }
        rep(i,n){
            int index=readt(q);
            if(res.find(index)==res.end()){
                puts(“Let’s go to the library!!”);
            }else{
                vector<string>& t=res[index];
                if(t.size()>1){
                    puts(“Let’s go to the library!!”);
                }else{
                    cout<<t[0]<<“\n”;
                }
            }
        }
    }
    return 0;
}

【D】

因为样例用的是m=3…所以我就一直卡在z>=3……然后比赛结束以后发现了…好亏啊

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF = 0x3f3f3f3f;
#define cle(a,val) memset(a,(val),sizeof(a))
#define SI(N) scanf(“%d”,&(N))
#define SII(N,M) scanf(“%d %d”,&(N),&(M))
#define SIII(N,M,K) scanf(“%d %d %d”,&(N),&(M),&(K))
#define rep(i,b) for(int i=0;i<(b);i++)
#define rez(i,a,b) for(int i=(a);i<=(b);i++)
#define red(i,a,b) for(int i=(a);i>=(b);i–)
const ll LINF = 0x3f3f3f3f3f3f3f3f;
#define PU(x) puts(#x);
#define PI(A) cout<<(A)<<endl;
#define DG(x) cout<<#x<<“=”<<(x)<<endl;
#define DGG(x,y) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<endl;
#define DGGG(x,y,z) cout<<#x<<“=”<<(x)<<” “<<#y<<“=”<<(y)<<” “<<#z<<“=”<<(z)<<endl;
#define PIar(a,n) rep(i,n)cout<<a[i]<<” “;cout<<endl;
#define PIarr(a,n,m) rep(aa,n){rep(bb, m)cout<<a[aa][bb]<<” “;cout<<endl;}
const double EPS = 1e-9 ;

struct Star{
    int left,right;
    bool operator<(const Star MM) const{
        return left<MM.left;
    }
}A[500],B[500];
int n,m,x,y,T,s,e;

int main(){
    SI(T);
    while(T–){
        SII(n,m);SII(x,y);
        rep(i,x){
            SII(s,e);
            A[i].left=s;
            A[i].right=e;
        }
        rep(i,y){
            SII(s,e);
            B[i].left=s;
            B[i].right=e;
        }
        sort(A,A+x);
        sort(B,B+y);
        int ans=0;
        rep(i,x){
            s=A[i].left;
            e=A[i].right;
            int z=0;
            rep(j,y){
                if(B[j].left>A[i].right) break;
                z+=(min(B[j].right,A[i].right)-max(A[i].left,B[j].left)+1);
                    if(z>=m){
                        ans+=z-m+1;
                        z=0;
                    }else{
                        z=0;
                    }
            }
        }
        printf(“%d\n”,ans);
    }
    return 0;
}

UVa 11464

【生词】

gird 网格,格子

so taht 以便

The parity 奇偶校验

even 有偶数意

transformation 转化

achieve 取得,获得,实现,成功

requirement 要求

indicates 表明

character 性格,品质

separated 分开,隔开

instead 代替,反而,相反

【题解】

蓝书 P16

【Code】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=20;
int A[maxn][maxn],B[maxn][maxn],n,T,ca=1;

int check(int s){
    memset(B,0,sizeof(B));
    //先初始化第一行
    for(int i=0;i<n;++i){
        if(s & (1<<i)) B[0][i]=1;//这句意思是判断每一位上是否是1
        //即(1<<n)只有第n位是1,其他位都是0 为真即为1
        else if(A[0][i]==1) return INF;//1不能变成0
    }
    for(int i=1;i<n;++i){
        for(int j=0;j<n;++j){
            int sum=0;//元素B[i-1][0]的上,左,右元素之和
            if(i>1)sum+=B[i-2][j];
            if(j>0)sum+=B[i-1][j-1];
            if(j<n-1)sum+=B[i-1][j+1];
            B[i][j]=sum%2;//sum是偶数,=0,奇数,=1
            if(A[i][j]==1 && B[i][j]==0) return INF;
            //不存在1->0的操作.
        }
    }
    int cnt=0;
    for(int i=0;i<n;++i){
        for(int j=0;j<n;++j){
            if(A[i][j]!=B[i][j])
            cnt++;
        }
    }
    return cnt;
}

int main(){
    scanf(“%d”,&T);
    while(T–){
        printf(“Case %d: “,ca++);
        scanf(“%d”,&n);
        for(int i=0;i<n;++i)
            for(int j=0;j<n;++j)
                scanf(“%d”,&A[i][j]);
        int ans=INF;
        for(int i=0;i<(1<<n);++i)
            ans=min(ans,check(i));
        if(ans==INF) ans=-1;
        printf(“%d\n”,ans);
    }
    return 0;
}