Solution

新奇解法 .

给一个很直观的方法 : 对于每一个串 , 计算和它同位置不同的情况一共有多少种 , 记为 $x$ . 若 $x = k \times (n-1)$ 那么成立 .

显然这可以被 hack 掉 . 因为很有可能这不同的情况并不是每个串分 $k$ 个 . What should I do ?

随机 ! 给每个串随机赋一个权值 . 把所有东西加权就可以 .

看代码实现 :

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=4100+10;
int n,m,k,tot,w[MAXN],sum[MAXN][4];
map<char,int> mp={{'A',0},{'T',1},{'G',2},{'C',3}};
int Rand(void) {
	return rand()*1ll*rand();
}
string S[MAXN];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k;
	ffor(i,1,n) w[i]=Rand(),tot+=w[i];
	ffor(i,1,n) {
		cin>>S[i];S[i]='$'+S[i];
		ffor(j,1,m) ffor(k,0,3) if(mp[S[i][j]]!=k) sum[j][k]+=w[i];
	}
	ffor(i,1,n) {
		int ans=0;
		ffor(j,1,m) ans+=sum[j][mp[S[i][j]]];
		if(ans==(tot-w[i])*k) {cout<<i;break;}
	}
	return 0;
}

由于用了 STL , 开 O2 才能过 .

上面的这个 sum[i][j] 表示第 $i$ 列 , 字符不是 $j$ 的权值和 .

如果这份代码挂了 ( 毕竟是随机 ) 怎么办 ?

你可以 :

• 跑 N 遍 . 显然这样还出错的概率几乎为 0 .

• 泰然处之 . 不就几个点吗 ! 有这运气让你家长买彩票中个大奖 , 你也不用学 OI 了 ( 不必为这个情况纠结 .