[usaco] Chapter2-Bigger Challenges(Section 2.1)

 

/*
    ID:123ldss2
    PROG: castle
    LANG: C++
*/
#include<cstring>
#include<fstream>
#include<cstdio>
using namespace std;
const int nMax=100005;
int father[nMax],rank[nMax],N,M,num[nMax],sum;   //rank近似树的高度。

ifstream fin("castle.in");
ofstream fout("castle.out");
int find(int x){ // 寻找父节点
    if(x!=father[x])
        return father[x]=find(father[x]);
    return x;
}

void unite(int a,int b){
 //   cout<<a<<" unio "<<b<<endl;
    int x=find(a);
    int y=find(b);
    if(x==y)
        return ;
    else{
        if(rank[x]>rank[y]){
            father[y]=x;
            num[x]+=num[y];
        }
        else if(rank[x]<rank[y]){
            father[x]=y;
            num[y]+=num[x];
        }
        else{
            father[x]=y;
            num[y]+=num[x];
            rank[y]++;
        }
    }
}

void set(){    // 初始化
    int i;
    for(i=0; i<nMax-1; i++){
        father[i]=i;
        rank[i]=0;
        num[i]=1;
    }
    //n=0;
}

int map[100][100];
bool vis[nMax];

int main(){
    int n,m,i,j,ans1,a,b;
//    freopen ( "castle.in", "r", stdin );
//    freopen ( "castle.out", "w", stdout );
    while(fin>>m>>n){//scanf("%d%d",&m,&n)!=EOF
        set();
        sum=0;
        memset(vis,0,sizeof(vis));
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                //scanf("%d",&map[i][j]);
                fin>>map[i][j];
                if((map[i][j]&1)==0){
                    unite((i-1)*m+j,(i-1)*m+j-1);
                }
                if((map[i][j]&2)==0){
                    unite((i-1)*m+j,(i-2)*m+j);
                }
                if((map[i][j]&4)==0){
                    unite((i-1)*m+j,(i-1)*m+j+1);
                }
                if((map[i][j]&8)==0){
                    unite((i-1)*m+j,(i)*m+j);
                }
            }
        }
        ans1=0;
        for(i=1;i<=n*m;i++){
            j=find(i);
           // cout<<"num"<<num[find(i)]<<endl;
            ans1=max(ans1,num[find(i)]);
            if(vis[j]==0){
                vis[j]=1;
                sum++;
            }
        }
        fout<<sum<<endl;
        fout<<ans1<<endl;
        int xxx,yyy;
        ans1=0;
        char cha;
        for(j=1;j<=m;j++)
        {
            for(i=n;i>=1;i--)
            {
                a=(i-1)*m+j;
                a=find(a);
                if(i!=1)
                {
                    b=(i-2)*m+j;
                    b=find(b);
                    if(a!=b&&ans1<num[a]+num[b])
                    {
                        ans1=num[a]+num[b];
                        xxx=j;
                        yyy=i;
                        cha='N';
                    }
                }
                if(j!=m)
                {
                    b=(i-1)*m+j+1;
                    b=find(b);
                    if(a!=b&&ans1<num[a]+num[b])
                    {
                        ans1=num[a]+num[b];
                        xxx=j;
                        yyy=i;
                        cha='E';
                    }
                }
            }
        }
        fout<<ans1<<endl;
        fout<<yyy<<" "<<xxx<<" "<<cha<<endl;
    }
    return 0;
}

  /*

    ID: bbezxcy1
    PROG: frac1
    LANG: C++
*/
#include<iostream>
#include<cstring>
#include<fstream>
#include<algorithm>
#include<cstdio>
using namespace std;

ifstream fin("frac1.in");
ofstream fout("frac1.out");
int  play(int a, int b){
    int c,d,e;
    d=a;e=b;
    do{c=a%b;a=b;b=c;}while(c!=0);
    return a;
}

class fuck
{
    public:
    int a,b;
}sum[1000000];

bool cmp(fuck x,fuck y)
{
    if(x.a*y.b>x.b*y.a)
    {
        return 0;
    }
    return 1;
}
int cnt;
int main()
{
    int n,m,i,k,j,a,b,c;
    while(fin>>n)
    {
        for(i=2;i<=n;i++)
        {
            for(j=1;j<i;j++)
            {
              //  cout<<j<<" "<<i<<" "<<play(i,j)<<endl;
                if(play(i,j)==1)
                {
                    sum[cnt].a=j;
                    sum[cnt++].b=i;
                }
            }
        }
        sort(sum,sum+cnt,cmp);
        fout<<"0/1\n";
        for(i=0;i<cnt;i++)
        {
            fout<<sum[i].a<<"/"<<sum[i].b<<endl;
        }
        fout<<"1/1\n";
    }
    return 0;
}

  /*

    ID:123ldss2
    PROG: sort3
    LANG: C++
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<fstream>
#include<cmath>
using namespace std;
const int nMax=2000;
const int mMax=300000;
const int inf=1<<30;
ifstream fin("sort3.in");
ofstream fout("sort3.out");
int num[1003],check[1003],aaa[4],bbb[4],map[10][10];
int main(){
    int n,i,j,k,a,b,c;
    while(fin>>n)
    {
        memset(aaa,0,sizeof(aaa));
        memset(bbb,0,sizeof(bbb));
        memset(map,0,sizeof(map));
        for(i=1;i<=n;i++)
        {
            fin>>num[i];
            aaa[num[i]]++;
        }
        k=1;
        for(j=1;j<=3;j++)
        {
            for(i=1;i<=aaa[j];i++)
            {
                check[k++]=j;
            }
        }
        for(i=1;i<=n;i++)
        {
            if(num[i]!=check[i])
            {
                map[num[i]][check[i]]++;
            //    map[check[i]][num[i]]++;
                bbb[num[i]]++;
            }
        }
        int ans=0;
        b=0;

//        for(i=1;i<=3;i++)
//        {
//            for(j=1;j<=3;j++)
//            {
//                cout<<map[i][j]<<" ";
//            }cout<<endl;
//        }
        for(i=1;i<=3;i++)
        {
            for(j=1;j<=3;j++)
            {
                if(i==j)continue;
                if(map[i][j]&&map[j][i])
                {

                    a=min(map[i][j],map[j][i]);
                    ans+=a;
                    map[i][j]-=a;
                    map[j][i]-=a;
                }
                b+=map[i][j];
               // cout<<map[i][j]<<" ";
            }//cout<<endl;
        }
        ans+=(b/3*2);
        fout<<ans<<endl;
    }
    return 0;
}

  /*

ID: bbezxcy1
PROG: holstein
LANG: C++
*/
#include<iostream>
#include<cstring>
#include<fstream>
#include<cstdio>
using namespace std;
int need[2000],n,m,res[30],ans;
int madc[30][2000];
int have[1000];
int vis[30];
ifstream fin("holstein.in");
ofstream fout("holstein.out");
bool check(){
	for(int i=0;i<n;i++){
        if(have[i]<need[i]){
			return 0;
		}
	}
	return 1;
}
void dfs(int pos,int dep){
    int i,j;
	if(dep>=ans||pos>m){
		return;
	}
	if(check()){
	    if(dep<ans){
	    //    cout<<"dwad "<<dep;
			ans=dep;
			for(i=0;i<=m;i++){
			//    cout<<" "<<vis[i];
				res[i]=vis[i];
			}
		}
	}
    for(i=pos+1;i<=m;i++){
		vis[i]=1;
		for(j=0;j<n;j++){
			have[j]+=madc[i][j];
		}
	    dfs(i,dep+1);
		for(j=0;j<n;j++){
			have[j]-=madc[i][j];
		}
		vis[i]=0;
	}
}
int main(){
	int i,j;
   // freopen("namenum.in","r",stdin );
	while(fin>>n){
		ans=1<<30;
		for(i=0;i<n;i++){
			fin>>need[i];
		}
		fin>>m;
		for(i=1;i<=m;i++){
			for(j=0;j<n;j++){
				fin>>madc[i][j];
			}
		}
		memset(vis,0,sizeof(vis));
		memset(res,0,sizeof(res));
		memset(have,0,sizeof(have));
		dfs(0,0);
		fout<<ans;
		int b=0;
		for(i=0;i<=m;i++)
		{
		    if(res[i])
		    {
		        fout<<" "<<i;
//		        if(b)cout<<" ";
//		        cout<<i;
//		        b=1;
		    }
		}fout<<endl;
	}
	return 0;
}

  /*

    ID:bbezxcy1
    PROG: hamming
    LANG: C++
*/
#include<iostream>
#include<fstream>
#include<cstring>
#include<cstdio>
using namespace std;
int n,b,d;
int ans1[100];
int getdis(int a,int bs){
	int aaa[50],bbb[50];
	memset(aaa,0,sizeof(aaa));
	memset(bbb,0,sizeof(bbb));
	int ccc=0,ddd=0;
	while(a){
		aaa[ccc]=a%2;
		a/=2;
		ccc++;
	}
	while(bs){
		bbb[ddd]=bs%2;
		bs/=2;
		ddd++;
	}
	ddd=0;
	for(int i=0;i<b;i++){
		if(aaa[i]!=bbb[i]){
			ddd++;
		}
	}
	return ddd;
}
bool flag;
void dfs(int dep,int pre){
    int i;
    if(dep>=2){
		for(i=1;i<dep;i++){
			if(getdis(ans1[i],ans1[dep])<d){
				return;
			}
		}
	}
	if(dep==n){
		flag=0;
	}
	for(i=pre+1;i<1<<b;i++){
		ans1[dep+1]=i;
		dfs(dep+1,i);
		if(!flag){
			return;
		}
	}
}
ifstream fin("hamming.in");
ofstream fout("hamming.out");
int main(){
	int i,j,k,a,c;
//	while(cin>>a>>c>>b)
//	{
//	    cout<<getdis(a,c)<<endl;
//	}
	while(fin>>n>>b>>d){
		flag=1;
		dfs(0,-1);
		k=1;
		for(i=1;i<=n;i++){
		    k++;
		    if(k>10)
		    {
                fout<<ans1[i]<<endl;
                k=1;
		    }
		    else
		    {
		        if(i==n)
		        {
		            fout<<ans1[i]<<endl;
		        }
		        else{
		            fout<<ans1[i]<<" ";
		        }
		    }
		}
	}
	return 0;
}