题解：P6456 [COCI 2006/2007 #5] DVAPUT

Clare613 · 2025-07-20 21:38:04 · 题解

思路：

这是打 OI 比赛时场切的，写篇题解纪念一下。\ 第一步，审题。看到这样的题面，判断是哈希。然后看数据范围：1\le L\le 2\times 10^5，判断是哈希 + 二分。\ 很快把哈希板子打出来，然后写 \operatorname{check} 函数。不难发现，unordered_map<int,bool> 叠加 O2 优化后不会超时。于是就可以利用 unordered_map<int,bool> 秒了这道题。\ ⚠⚠⚠注意事项：不同的位置不代表不重叠，请注意。

code：

#include<bits/stdc++.h>
#define int unsigned long long
using namespace std;
int ha[200005],pw[200005];
unordered_map<int,bool> f;
int n;
string x;
int hashh(int l,int r){
    return ha[r]-ha[l-1]*pw[r-l+1];
}
bool check(int x){
    f.clear();
    for(int i=x;i<=n;i++){
        if(f[hashh(i-x+1,i)]==1){
            return 1;
        }
        f[hashh(i-x+1,i)]=1;
    }
    return 0;
}
signed main(){
    cin>>n;
    cin>>x;
    x=" "+x;
    pw[0]=1;
    for(int i=1;i<=n;i++){
        ha[i]=ha[i-1]*13331+x[i];
        pw[i]=pw[i-1]*13331;
    }
    int l=0,r=n;
    while(l<r){
//      cout<<l<<" "<<r<<"\n";
        int mid=(l+r+1)/2;
        if(check(mid)) l=mid;
        else r=mid-1; 
    }
    cout<<l;
    return 0;
}