题目链接

题意:给出n个字符串,长度均为len;

有m次操作,每次将两个字符交换;

求每个字符串在任何时点上,与相同的它最多的字符串个数;

数据范围:$2<=n<=1000,1<=l<=100,1<=m<=100000$

题解:

注意到数据范围中l不是很大,那么我们可以在每次修改后暴力重构hash值,那么在这里修改会影响的个数就只是修改后的两个值,然后用multiset暴力维护就行了

code:

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull base=131;
#define maxn 1005
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    } 
    return x*f;
}
ull hsh[maxn],val;
int n,l,m,ans[maxn],x,y,xx,yy;
char s[maxn][105];
multiset<ull>ss;
multiset<ull>::iterator it;
void init(){
    n=read();l=read();m=read();
    for(int i=1;i<=n;i++){
        scanf("%s",s[i]+1);
        val=0;
        for(int j=1;j<=l;j++){
            val=val*base+s[i][j]-'0';
        }
        hsh[i]=val;
        ss.insert(hsh[i]);
    }
    for(int i=1;i<=n;i++) {
    int t=ss.count(hsh[i]);
    ans[i]=max(ans[i],t);   
    }
    for(int i=1;i<=m;i++){
        x=read();y=read();xx=read();yy=read();
        if(s[x][y]==s[xx][yy]) continue;
        swap(s[x][y],s[xx][yy]);
        if(x==xx){
            it=ss.find(hsh[x]);
            ss.erase(it);
            val=0;
            for(int j=1;j<=l;j++) val=val*base+s[x][j]-'0';
            hsh[x]=val;
            ss.insert(hsh[x]);
            int t1=ss.count(hsh[x]);
            for(int j=1;j<=n;j++){
            if(hsh[j]==hsh[x]) ans[j]=max(ans[j],t1);
            }
            continue;
        }
        it=ss.find(hsh[x]);
        ss.erase(it);
        it=ss.find(hsh[xx]);
        ss.erase(it);
        val=0;
        for(int j=1;j<=l;j++) val=val*base+s[x][j]-'0';
        hsh[x]=val;
        val=0;
        for(int j=1;j<=l;j++) val=val*base+s[xx][j]-'0';
        hsh[xx]=val;
        ss.insert(hsh[x]);ss.insert(hsh[xx]);
        int t1=ss.count(hsh[x]),t2=ss.count(hsh[xx]);
        for(int j=1;j<=n;j++){
            if(hsh[j]==hsh[x]) ans[j]=max(ans[j],t1);
            if(hsh[j]==hsh[xx]) ans[j]=max(ans[j],t2);
        }
    } 
    for(int i=1;i<=n;i++) printf("%d\n",ans[i]);

}
int main(){
    init();

    return 0;
}
Last modification:March 30th, 2019 at 04:01 pm