用户工具

站点工具


2020-2021:teams:legal_string:jxm2001:contest:cf_706_div._1

这是本文档旧的修订版!


Codeforces Round #706 (Div. 1)

C. Garden of the Sun

题意

给定一些黑格和一些白格,要求将一些白格转化为黑格,使得所有黑格连通但不出现环路。

题目保证以起始时以每个黑格为中心的 $3\times 3$ 范围内没有其他黑格。

题解

当 $n\equiv 1\bmod 3$ 时,考虑将第 $1,4,7\cdots$ 行染成黑色,然后对第 $3k+2,3k+3$ 行的每列,最多只有一个黑格。

如果第 $3k+2,3k+3$ 行间存在黑格,直接将两行的任意一个黑格所在列全染黑,否则将两行的第一列染黑。易知这样即可完成构造。

当 $n\not\equiv 1\bmod 3$ 时,将 $1,4,7\cdots$ 行换成第 $2,5,8\cdots$ 行处理即可。

查看代码

查看代码

const int MAXN=505;
char buf[MAXN][MAXN];
int main()
{
	int T=read_int();
	while(T--){
		int n=read_int(),m=read_int();
		_for(i,0,n)scanf("%s",buf[i]);
		int s1,s2;
		if(n%3==1){
			s1=0;
			s2=2;
		}
		else{
			s1=1;
			s2=3;
		}
		for(int i=s1;i<n;i+=3)_for(j,0,m)buf[i][j]='X';
		for(int i=s2;i<n;i+=3){
			bool flag=false;
			_for(j,0,m){
				if(buf[i-1][j]=='X'||buf[i][j]=='X'){
					buf[i-1][j]=buf[i][j]='X';
					flag=true;
					break;
				}
			}
			if(!flag)
			buf[i-1][0]=buf[i][0]='X';
		}
		_for(i,0,n)puts(buf[i]);
	}
	return 0;
}
2020-2021/teams/legal_string/jxm2001/contest/cf_706_div._1.1616592181.txt.gz · 最后更改: 2021/03/24 21:23 由 jxm2001