时间戳

首页 > 技术文章 > [整理]U S A C O 代 码 小 合 集

[整理]U S A C O 代 码 小 合 集

juruoajh 2020-09-25 18:20 原文

前言

都是些水题，仅用于练习基础算法。

P1360 Gold Balanced Lineup G

做一个前缀和就会发现一个有趣的性质：
1 1 1
2 2 1
3 3 2
3 4 2
3 4 3
4 4 3
4 5 3
标粗的两行内相对差值相同，说明提升了相等的次数。
这时我们减一下，再用map存下来即可。

#define N 100010
int n,m,ans;
map<vector<int>,int>mp;
int main(){
	Read(n),Read(m);
	vector<int>now(m);
	mp[now]=0;
	for(rg int i=1;i<=n;i++){
		int u;Read(u);
		for(rg int j=0;j<m;j++)if(u&(1<<j))now[j]++;
		if(u&1)for(rg int j=0;j<m;j++)now[j]--;
		if(mp.count(now))ans=max(ans,i-mp[now]);
		else mp[now]=i;
	}
	cout<<ans<<endl;
	return 0;
}

P1468 Party Lamps

此题直接枚举即可，性质比较简单不再多讲。

int n,c,li[110],now[110],cnt;
string ans[110];
inline bool Check(int cur[]){
	for(rg int i=1;i<=n;i++){
		if(li[i]==-1)continue;
		if(li[i]!=cur[i])return 0;
	}
	return 1;
}
inline void Save(){
	ans[++cnt]="";
	for(rg int i=1;i<=n;i++)ans[cnt]+=(char)(now[i]+'0');
}
int main(){
	Read(n),Read(c);
	int light;memset(li,-1,sizeof(li));
	while(cin>>light&&light!=-1)li[light]=1;
	while(cin>>light&&light!=-1)li[light]=0;
	for(rg int i=0;i<2;i++){
		for(rg int j=0;j<2;j++){
			for(rg int k=0;k<2;k++){
				for(rg int l=0;l<2;l++){
					if(i+j+k+l>c)continue;
					if((c&1)&&((i+j)&1)==((k+l)&1))continue;
					if(!(c&1)&&((i+j)&1)!=((k+l)&1))continue;
					for(rg int a=1;a<=n;a++)now[a]=1;
					if(i)for(rg int a=1;a<=n;a+=1)now[a]^=1;
					if(j)for(rg int a=1;a<=n;a+=2)now[a]^=1;
					if(k)for(rg int a=2;a<=n;a+=2)now[a]^=1;
					if(l)for(rg int a=1;a<=n;a+=3)now[a]^=1;
					if(Check(now))Save();
				}
			}
		}
	}
	sort(ans+1,ans+1+cnt);
	if(!cnt)puts("IMPOSSIBLE");
	else {
		for(rg int i=1;i<=cnt;i++)cout<<ans[i]<<endl;
	}
	return 0;
}

P1457 The Castle

首先常规操作求出连通块，再枚举敲的墙即可。
注意存储方式。

int n,m,mp[60][60][4];//WNES:0123
int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int col[60][60],siz[2510],tot,mx;
int ans,ansx,ansy,ansd;
const string DIST="WNES";
inline void BFS(int x,int y){
	queue<pii >q;
	col[x][y]=++tot,q.push(mkp(x,y)),siz[tot]++;
	while(!q.empty()){
		pii u=q.front();q.pop();
		for(rg int i=0;i<4;i++){
			int xx=u.first+dx[i],yy=u.second+dy[i];
			if(xx>0&&yy>0&&xx<=n&&yy<=m&&!col[xx][yy]&&!mp[u.first][u.second][i]){
				col[xx][yy]=tot,q.push(mkp(xx,yy)),siz[tot]++;
			}
		}
	}
	mx=max(mx,siz[tot]);
}
int main(){
	Read(m),Read(n);
	for(rg int i=1;i<=n;i++){
		for(rg int j=1;j<=m;j++){
			int x;Read(x);
			for(rg int k=0;k<4;k++){
				if(x&(1<<k))mp[i][j][k]=1;
			}
		}
	}
	for(rg int i=1;i<=n;i++){
		for(rg int j=1;j<=m;j++){
			if(!col[i][j])BFS(i,j);
		}
	}
	cout<<tot<<endl<<mx<<endl;
	for(rg int j=1;j<=m;j++){
		for(rg int i=n;i;i--){
			for(rg int k=1;k<=2;k++){
				if(mp[i][j][k]){
					int x=i+dx[k],y=j+dy[k],newsiz=siz[col[i][j]]+siz[col[x][y]];
					if(col[i][j]!=col[x][y]&&newsiz>ans){
						ans=newsiz,ansx=i,ansy=j,ansd=DIST[k];
					}
				}
			}
		}
	}
	cout<<ans<<endl<<ansx<<" "<<ansy<<" "<<(char)ansd<<endl;
	return 0;
}

P1849 Tractor S

利用双端队列\(BFS\)，无草放队头，有草放队尾，同时记录答案。
注意搜索的边界，可以走到\(0\)和\(1001\)。

#define N 1010
int n,mp[N][N],sx,sy,vis[N][N],ans[N][N];
int dx[4]={1,0,-1,0},dy[4]={0,1,0,-1};
inline void BFS(){
	deque<pii >q;
	q.push_back(mkp(sx,sy)),vis[sx][sy]=1,ans[sx][sy]=0;
	while(!q.empty()){
		pii u=q.front();q.pop_front();
		int x=u.first,y=u.second;
		if(x==0&&y==0){
			cout<<ans[0][0]<<endl;
			exit(0);
		}
		for(rg int i=0;i<4;i++){
			int xx=x+dx[i],yy=y+dy[i];
			if(xx>=0&&yy>=0&&xx<=1001&&yy<=1001&&!vis[xx][yy]){
				if(mp[xx][yy])q.push_back(mkp(xx,yy));
				else q.push_front(mkp(xx,yy));
				vis[xx][yy]=1,ans[xx][yy]=ans[x][y]+mp[xx][yy];
			}
		}
	}
}
int main(){
	Read(n),Read(sx),Read(sy);
	for(rg int i=1;i<=n;i++){
		int xi,yi;Read(xi),Read(yi);
		mp[xi][yi]=1;
	}
	memset(ans,0x3f,sizeof(ans));
	BFS();
	return 0;
}

推荐阅读