danihao123's Blog

Hash第一题……

这个题直接枚举串长Hash判断即可。不过，注意读题。

感觉Hash挺简单的。还有就是我用了wyy的生日做Hash种子辣！

代码：

/**************************************************************
    Problem: 2081
    User: danihao123
    Language: C++
    Result: Accepted
    Time:5636 ms
    Memory:10904 kb
****************************************************************/
 
#include <cstdio>
#include <set>
#include <vector>
using namespace std;
typedef unsigned long long ull;
const int maxn=200005;
const ull x=200261;
ull s[maxn];
ull sufHash[maxn],preHash[maxn],x_pow[maxn];
int n;
inline void InitHash(){
    register int i;
    for(i=n;i>=1;i--){
        sufHash[i]=s[i]+sufHash[i+1]*x;
    }
    for(i=1;i<=n;i++){
        preHash[i]=s[i]+preHash[i-1]*x;
    }
    x_pow[0]=1;
    for(i=1;i<=n;i++){
        x_pow[i]=x*x_pow[i-1];
    }
}
inline ull Hash(int i,int L){
    return sufHash[i]-x_pow[L]*sufHash[i+L];
}
inline ull FilpHash(int i,int L){
    return preHash[i+L-1]-x_pow[L]*preHash[i-1];
}
 
set<ull> S;
vector<int> AnsList;
int tot=0;
inline void Check(int k){
    register int i,ans=0;
    register ull h;
    S.clear();
    for(i=1;(i+k-1)<=n;i+=k){
        h=Hash(i,k)*FilpHash(i,k);
        if(!S.count(h)){
            S.insert(h);
            ans++;
        }
    }
    if(ans>tot){
        tot=ans;
        AnsList.clear();
        AnsList.push_back(k);
    }else{
        if(ans==tot)
            AnsList.push_back(k);
    }
}
 
int main(){
    register int i,ans=0,maxv=0,cnt,temp;
    bool flag;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        scanf("%llu",&s[i]);
    InitHash();
    for(i=1;i<=n;i++){
        Check(i);
    }
    printf("%d %d\n",tot,AnsList.size());
    flag=false;
    for(i=0;i<AnsList.size();i++){
        if(flag)
            putchar(' ');
        flag=true;
        printf("%d",AnsList[i]);
    }
    putchar('\n');
    return 0;
}

秒，秒啊……

很容易想到线段树，但是在[tex]N=10^6,M=10^7[/tex]的情况下，线段树肯定会TLE。

考虑修改，我们可以发现真正影响一个馒头颜色的只是作用于此馒头上的最后一个操作。可以考虑倒序枚举操作，然后暴力修改。但是如此暴力修改的话可能覆盖了实际时间线较晚的操作……

考虑并查集！每个节点修改完后将其父亲改为下一个点，这样的话被修改的地方就可以轻松跳过了。

注意一个细节，第[tex]N[/tex]个馒头被染色后，其父亲会被修改为[tex]N+1[/tex]，所以说并查集实际上要开[tex]N+1[/tex]！

代码：

/**************************************************************
    Problem: 2054
    User: danihao123
    Language: C++
    Result: Accepted
    Time:2476 ms
    Memory:39796 kb
****************************************************************/
 
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1000005;
int Color[maxn];
int P[maxn];
int n;
int find_set(int x){
    if(P[x]==x)
        return x;
    else
        return P[x]=find_set(P[x]);
}
inline void init_set(){
    register int i;
    for(i=1;i<=(n+1);i++)
        P[i]=i;
}
int buf[20];
inline void PutInt(int x){
    register int i,p=0;
    if(x==0){
        buf[p++]=0;
    }else{
        while(x){
            buf[p++]=x%10;
            x/=10;
        }
    }
    for(i=p-1;i>=0;i--)
        putchar(buf[i]+'0');
    putchar('\n');
}
int main(){
    int m,p,q;
    register int i,j,l,r,k=0;
    bool OK=false;
    scanf("%d%d%d%d",&n,&m,&p,&q);
    init_set();
    for(i=m;i>=1;i--){
        l=(((i%n)*(p%n))%n+q%n)%n+1;
        r=(((i%n)*(q%n))%n+p%n)%n+1;
        if(l>r)
            swap(l,r);
        for(j=find_set(l);j<=r;j=find_set(j)){
            Color[j]=i;
            P[j]=j+1;
            k++;
            if(k==n){
                OK=true;
                break;
            }
        }
        if(OK)
            break;
    }
    for(i=1;i<=n;i++)
        PutInt(Color[i]);
    return 0;
}