Codeforces Round 530
题目HERE
求一个n x m <= 300 000的二维字符数组
满足任何2x2的字符都包含A T G C
并且和给你的 数组不同的字符尽量少
我的思路
我有发现如果已经有
1 | AG |
那么右侧一列,一定是AT,顺序不定
下面两个一定是AG顺序不定,
又发现如果对于任意2*3
1 | XYZ |
如果XYZ出现了3个字母
那么???下方的一定是XYZ且顺序不变
因为如果Y不在中间,那么会变成
1 | XYZ |
第3行填X 或 Z都是不行的
又发现2x3如果XYZ 3个字母不同,具有性质,
1 | XYZ |
下面的??? 是确定的,因为X列和Z列是相等的,所以一定是,其中O表示第4个字母
1 | XYZ |
然后我就现在想如何构造 去找,因为找到3个不同,那么整列都确定了
然后就自闭了
其实可以把上面的事实展开
1 | XYZ |
有结论,如果 某行中出现连续3个不同字符,那么这3个字符对应的列,每列包含且仅包含两个字符,且任意行 包含连续这3个不同字符
交换行列有,如果 某列中出现连续3个不同字符,那么这3个字符对应的行,每行包含且仅包含两个字符,且任意列 包含连续这3个不同字符
注意到上面两条是事实,但是是互斥的
那么 目前有3种情况
- 所有行列,的每一个行列,仅仅包含两个字符[且两两交替.废话]
- 存在一列 包含3个不同字符,那么所有列都包含这3个不同字符,所有行的每一行仅仅包含两个字符,
- 和2把 行列换一下
综上↓
以下是一句话题解
如果你发现了事实:
要么每一行 只有两种字母
或
要么每一列 只有两种字母
没了 然后暴力枚举就完了 这个题评分果然有2300,感觉这种题又是需要多枚举几个比如能枚举到5*5的能看出规律就好了