题解：P9939 [USACO21OPEN] Acowdemia III B

贪心解决。

为什么？

当两头与同一个草地相邻的牛交朋友的时候，对答案的贡献是

1

，而这个草地有两种情况：连接着不同的牛和只连接了这两头牛，这两种情况对答案的多出贡献分别是

1

和

0

，由此可见，按照贪心的思想（找到所有与相邻的未使用草地，连接的两头牛交朋友），是可以找到正确答案的。

去除重复

对于草地，我们很容易就可以判断使用与否，用一个二维数组标记一下就可以了。

但是对于牛，不可能开一个四维数组来记录是否交友。

那怎么办？

其实可以不用管。只要按照行和列的顺序依次找每头牛的位置，比如在第

i

行第

j

列的位置有一头牛，这头牛在之前的所有第

x

行第

y

列（

x<i,y<j

）没有被找到过，也就没有和任何牛交过朋友，那么这头牛交的朋友就不会重复算。

不会算重

对于第

i

行第

j

列的牛，我们先只计算他与第

x

行第

y

列（

x<i,y<j

）的牛交朋友的交友数量，没有被找到的牛就不会受到影响。

不会漏算

不妨假设第

i

行第

j

列的牛可以和第

r

行第

c

列（

r>i,c>j

）的牛交朋友。

显而易见，第

r

行第

c

列的牛也一定能与它交朋友，这两头牛之间的交友贡献虽然在遍历到第

i

行第

j

列的牛时不会计算，但是在第

r

行第

c

列时就会计入总量了。

总结

所以，对于一头牛，我们需要找如下的草坪与牛是否能与其交友。

图片解释：已经被找到的牛（黄色），草坪（绿色），当前的牛（红色）。

code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=3e3+5;
int n,m,k;
int T;
char c[M][M];
int vis[M][M];
signed main(){
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			cin>>c[i][j];
		}
	}
	int ans=0;
	for(int x=1;x<=n;x++){
		for(int y=1;y<=m;y++){
			if(c[x][y]=='C'){
				int vvs[10]={};
				if(x-1>=1&&c[x-1][y]=='G'&&!vis[x-1][y]){//上边的草地 
					if(x-2>=1&&c[x-2][y]=='C')ans++,vis[x-1][y]=1;
					else if(y-1>=1&&c[x-1][y-1]=='C')ans++,vis[x-1][y]=1,vvs[2]=1;
					else if(y+1<=m&&c[x-1][y+1]=='C')ans++,vis[x-1][y]=1,vvs[3]=1;
				}
				if(y-1>=1&&c[x][y-1]=='G'&&!vis[x][y-1]){//左边的草地 
					if(x-1>=1&&c[x-1][y-1]=='C'&&!vvs[2])ans++,vvs[2]=1,vis[x][y-1]=1;
					else if(y-2>=1&&c[x][y-2]=='C')ans++,vis[x][y-1]=1;
				}
				if(y+1<=m&&c[x][y+1]=='G'&&!vis[x][y+1]){//右边的草地 
					if(x-1>=1&&c[x-1][y+1]=='C'&&!vvs[3])ans++,vis[x][y+1]=1,vvs[3]=1;
				}
			}
		}
	}
	cout<<ans;
}

题解：P9939 [USACO21OPEN] Acowdemia III B

文章操作

贪心解决。

去除重复

总结

code

相关推荐

评论

题解：P9939 [USACO21OPEN] Acowdemia III B