10.15 晚上考试总结

· · 个人记录

题目编号 分数
T1 0
T2 100
T3 100
T4 10

So we only need to write the summary for T1

T1 P13867

考场写得都差不多了，但是在哈希维护的时候脑子抽了，怎么想都想不通，考完试听完后又会了，主要思路就是二分答案

正解代码

#include <bits/stdc++.h>
#define int unsigned long long
using namespace std;
const int N=1e6+5;
const int p=13331;
int pw[N],hs[N];
int lens;
int get_hash(int l,int r)
{
    return hs[r]-hs[l-1]*pw[r-l+1];
}
map<int,int> v;
bool check(int x)
{
    v.clear();
    for(int i=1;i<=lens-x+1;i++)v[get_hash(i,i+x-1)]++;
    for(int i=1;i<=lens-x+1;i++)
    {
        if(v[get_hash(i,i+x-1)]==1)return 1;//就是这里
    }
    return 0;
}
signed main()
{
    string s;
    cin>>s;
    lens=s.size();
    s='#'+s;
    pw[0]=1;
    for(int i=1;i<=lens;i++)
    {
        hs[i]=hs[i-1]*p+(s[i]-'0');
        pw[i]=pw[i-1]*p;
    }
    int l=1,r=lens;
    while(l<r)
    {
        int mid=(l+r)/2;
        if(check(mid))r=mid;
        else l=mid+1;
    }
    v.clear();
    for(int i=1;i<=lens-l+1;i++)v[get_hash(i,i+l-1)]++;
    for(int i=1;i<=lens-l+1;i++)
    {
        if(v[get_hash(i,i+l-1)]==1)
        {
            cout<<s.substr(i,l);
            return 0;
        }
    }
    return 0;
}