$\mathcal O\left(n^3\right)$ 暴力做法
$\mathcal O\left(n^2\right)$ 枚举两个字符串，$\mathcal O(n)$ 计算差异个数。
$\mathcal O\left(\frac{n^3}{w}\right)$ 做法
$w$ 为计算机字长，一般为 $64$ 或 $32$。
（如果不会 bitset 或 shuffle 可以参考此处）
bitset 统计
考虑到 $3\leq N,M\leq 4100$，$\mathcal O\left(n^3\right)$ 是肯定不行的。
然而我们使用计算器可以发现：$4100^3=6.8921\times 10^{10}$。
计算机每秒能够处理的数据的规模为 $4\times 10^8$ 量级，实际运算次数至少是 $1\times 10^9$。
这之间的差异约是 $69$ 倍。
因此我们考虑优化。
我们开一个桶 $p_{i,j}\in{0,1}$ 表示第 $i$ 个字符串是否包含第 $j$ 个字符（第一个字符为 A，第二个为 T，第三个为 G，第四个为 C）。
同时我们可以进行状态压缩。
相比于每次都需要把 $p_{i,j}$ 拿出来比较，如果我们将其压缩为一个数后进行 & 运算来统计显然会快很多。
因此我们可以使用 bitset 来处理。
那么对于字符串 $i$ 和字符串 $j$，其相同位数就是 $\sum\limits_{x=0}^4(p_{i,x}\ \&\ p_{j,x}).count()$。
不同位数即用 $m$ 去减这个东西，然后判断是否等于 $k$ 即可。
随机化
这样很明显是有可能被卡超时的。
因此我们可以随机打乱顺序，来防止被“模式串在最后”的数据卡掉。
可以使用 shuffle。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
//#include<cstring>
//#include<iomanip>
//#include<cstdio>
//#include<string>
//#include<vector>
//#include<cmath>
#include<ctime>
//#include<deque>
//#include<queue>
//#include<stack>
//#include<list>
#include<bitset>
#include<random>
using namespace std;
typedef long long ll;
mt19937 Rand(time(0));
const int N=4100,M=4100;
int n,m,k,order[N+1];
char a[N+1][M+1];
bitset<N+1>p[N+1][4];
inline int g(char x){
switch(x){
case 'A':return 0;
case 'T':return 1;
case 'G':return 2;
case 'C':return 3;
}
}
inline char gc(){
static int p1,p2;
static char buf[1<<20];
if(p1==p2){
p2=fread(buf,1,1<<20,stdin);
p1=0;
}if(p1==p2)return EOF;
return buf[p1++];
}
template<typename T>
inline void Read(T &x){
x=0;
T f=1;
char ch=gc();
for(;ch<'0'||'9'<ch;ch=gc())if(ch=='-')f=-1;
for(;'0'<=ch&&ch<='9';ch=gc())x=(x<<3)+(x<<1)+(ch^48);
x*=f;
}
inline void Read_str(char s[]){
for(int i=0;i<m;i++)while(s[i]<'A'||'Z'<s[i])s[i]=gc();
}
#define putchar putchar_unlocked
template<typename T>
inline void Write(T x){
static char s[101];
int top=0;
do{
s[++top]=x%10+'0';
x/=10;
}while(x);
while(top)putchar(s[top--]);
putchar(10);
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
Read(n);Read(m);Read(k);
for(int i=1;i<=n;i++){
Read_str(a[i]);
order[i]=i;
}
shuffle(order+1,order+n+1,Rand);
for(int i=1;i<=n;i++){
int &ii=order[i];
for(int j=0;j<m;j++){
p[ii][g(a[ii][j])].set(j);
}
}
for(int i=1;i<=n;i++){
bool flag=true;
int &ii=order[i];
for(int j=1;j<=n;j++){
int &jj=order[j];
if(ii==jj)continue;
int pl=0;
for(int x=0;x<4;x++){
pl+=(p[ii][x]&p[jj][x]).count();
}
if(m-pl!=k){
flag=false;
break;
}
}if(flag){
Write(ii);
return 0;
}
}
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
