我們考慮一個字符串 \(s_i\) 與另外 \(n-1\) 個字符串均有 \(k\) 個字符不同，但一個一個字符串枚舉比較的時間復雜度顯然是 \(O(n^2m)\) 的。所以考慮更優的實現方法，我們發現 \(s_i\) 與其它字符串應該一共有 \((n-1)k\) 個字符不同，我們只需要用桶記錄每個位置 \(4\) 種字符的個數，即可計算 \(s_i\) 與其它字符串不同字符的總數，時間復雜度是 \(O(nm)\) 的，但顯然會有多個字符串滿足上述約束，所以我們需要多次計算來獲得唯一解，顯然對于正確字符串 \(s_i\)，從原來 \(n\) 個字符串中任意取 \(x\) 個不是 \(s_i\) 的字符串，\(s_i\) 依然滿足與另外 \(x-1\) 個字符串均有 \(k\) 個字符不同，也就是與其它字符串應該一共有 \((x-1)k\) 個字符不同。于是我們考慮每次篩選出所有滿足與其它字符串一共有 \((n-1)k\) 個字符不同的字符串，然后從桶中刪去部分不可能成為答案的字符串對其的貢獻，再不斷地重復上述過程直到找到唯一解，時間復雜度是 \(O(\alpha nm)\) 的，為了保證答案正確與時間不超時，我們發現在 \(n\) 比較小時刪去部分字符串會使計算次數少使其正確性無保證，所以在 \(n\le100\) 時我們跑 \(O(n^2m)\) 的算法，在\(n<1800\) 時每次僅刪去 \(1\) 到 \(2\) 個字符串，在 \(n\geq 1800\) 時刪去 \(\frac{n}{50}\) 之類個數的字符串，這樣既可以保證正確性，也可以保證 \(\alpha\) 的大小不大。

#include<bits/stdc++.h>
using namespace std;
string s[4205];
int n,m,k,cnt,book[4205],id,sum;
vector<string> q; 
struct node{
    int a,b,c,d;
}se[4205];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>k;
    cnt=sum=n;
    for(int i=0;i<n;i++) {cin>>s[i];for(int j=0;j<m;j++)if(s[i][j]=='A')se[j].a++;else if(s[i][j]=='T')se[j].b++;else if(s[i][j]=='G')se[j].c++;else se[j].d++;}
    if(n<=100){
        for(int i=0;i<n;i++){
            int ccc=0,flag=true;
            for(int j=0;j<n&&flag;j++){
                if(i==j)continue;
                ccc=0;
                for(int o=0;o<m;o++)if(s[i][o]!=s[j][o]) ccc++;
                if(ccc!=k) flag=false;
            }
            if(flag) {cout<<i+1;return 0;}    
        }
    }
    while(cnt!=1){
        int cou=0;
        for(int i=0;i<n;i++){
            if(book[i]) continue;
            int num=0;
            for(int j=0;j<m;j++){
                if(s[i][j]=='A') num+=se[j].b+se[j].c+se[j].d;
                else if(s[i][j]=='T') num+=se[j].a+se[j].c+se[j].d;
                else if(s[i][j]=='G') num+=se[j].b+se[j].a+se[j].d;
                else num+=se[j].b+se[j].c+se[j].a;
            }
            if(num!=(sum-1)*k) {book[i]=1;q.push_back(s[i]);cou++;}
        }
        cnt-=cou;
        if(cnt!=1){
            int k;
            if(n<1700) k=2;
            else if(n<1800) k=1;
            else k=n/100;
            for(int i=0;i<k&&id<q.size();i++){
                for(int j=0;j<m;j++){
                    if(q[id][j]=='A') se[j].a--;
                    else if(q[id][j]=='T') se[j].b--;
                    else if(q[id][j]=='G') se[j].c--;
                    else se[j].d--;
                }
                id++;
                sum--;
            }
        }
    }
    for(int i=0;i<n;i++)if(!book[i]){cout<<i+1;return 0;} 
    return 0;
}