发布时间：2024-08-07

牛客第7场

D Interval Selection

题意：

• 求有多少个子区间满足所有数出现恰好k次
• 异或哈希板子题

mt19937_64 rng(time(0));
void solve(){
    int n,k;
    cin>>n>>k;
    vector<int> a(n+1),nums,freq(n+1);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        nums.push_back(a[i]);
    }
    sort(nums.begin(),nums.end());
    nums.erase(unique(nums.begin(),nums.end()),nums.end());
    for(int i=1;i<=n;i++)a[i]=lower_bound(nums.begin(),nums.end(),a[i])-nums.begin()+1;
    vector<ULL> h(n+1),rdm(n+1);
    for(int i=0;i<=n;i++)rdm[i]=rng();
    vector<int> fre(n+1);
    for(int i=1;i<=n;i++){
        h[i]=h[i-1];
        h[i]-=fre[a[i]]*rdm[a[i]];
        (fre[a[i]]+=1)%=k;
        h[i]+=fre[a[i]]*rdm[a[i]];
    }
    fre.assign(n+1,0);
    unordered_map<ULL,int> cnt;
    cnt[0]=1;
    int ans=0;
    for(int i=1,j=0;i<=n;i++){
        fre[a[i]]++;
        while(fre[a[i]]>k){
            fre[a[j]]--;
            cnt[h[j-1]]--;
            j++;
        }
        ans+=cnt[h[i]]++;
    }
    cout<<ans<<"\n";
}

K Strings, Subsequences, Reversed Subsequences, Prefixes

题意：
给定两个字符串s,t,算出s中有多少个子序列满足t即是它的前缀也是它的后缀
思路：

• 算出最短前缀位置和后缀位置，如果这两部分不相交，那么就变成询问中间的字符串，一个(动态规划：本质不同子序列数问题，这里包含空串)
  • 如果之前没出现过 $s_i$ ,那么 $dp_i=dp_{i-1}*2$,上一个所有的序列+上一个所有序列加上当前字符
  • 否则， $dp_i=dp_{i-1}*2-dp_{lst-1}$,去重
• 这会漏掉前后缀相交的解，那么用manacher算出有多少个后缀回文，如果回文中心相同，那么只会对答案贡献加1，判断能不能组成这个回文串即可

int p[N*2],l[N],r[N],dp[N];
char ma[N*2];
void manacher(string tmp){
    string s="";
    s+="$#";
    for(auto c:tmp)s+=c,s+="#";
    s+="^";
    int n=s.size();
    int mr=0,mid;
    for(int i=0;i<n;i++){
        if(i<mr)p[i]=min(p[2*mid-i],mr-i);
        else p[i]=1;
        while(s[i-p[i]]==s[i+p[i]])p[i]++;
        if(i+p[i]>mr){
            mr=i+p[i];
            mid=i;
        }
    }
}
string s,t;
int n,m;
void init(){
    for(int i=1;i<=m;i++)l[i]=r[i]=-1;
    for(int i=1,j=1;i<=n;i++){
        if(j<=m&&s[i]==t[j]){
            l[j]=i;
            j++;
        }
    }
    r[0]=n+1;
    for(int i=n,j=1;i>=1;i--){
        if(j<=m&&s[i]==t[j]){
            r[j]=i;
            j++;
        }
    }
}
void solve(){
    cin>>n>>m>>s>>t;
    manacher(t);
    s=" "+s;
    t=" "+t;
    init();
    int ans=0;
    if(l[m]==-1||r[m]==-1){
        cout<<"0\n";
        return;
    }
    for(int i=0;i<2*m+2;i++){
        if(i+p[i]==2*m+2&&p[i]-1)ans+=(l[m]<r[m-p[i]+1]);
    }
    if(l[m]<r[m]){
        vector<int> lst(26);
        dp[l[m]]=1;
        for(int i=l[m]+1;i<r[m];i++){
            if(lst[s[i]-'a'])dp[i]=((dp[i-1]*2-dp[lst[s[i]-'a']-1])%mod+mod)%mod;
            else dp[i]=dp[i-1]*2%mod;
            lst[s[i]-'a']=i;
        }
        (ans+=dp[r[m]-1])%=mod;
    }
    cout<<ans<<"\n";
}