2024牛客多校第七场

K

贪心地先凑出前后端后，中间的部分是本质不同的子序列个数

然后枚举可以重叠的部分，如果可以重叠肯定是回文后缀

有不少细节，比如空串，重叠部分要求后面的能取到

#include<cstdio>
#include<iostream>
#define int long long 
#define ULL unsigned long long
using namespace std;
const int P=1e9+7;
const int N=1e6+505;
const int K=97;
int n,m,res;
int dp[N],last[N];
ULL pre[N],suf[N],pow[N];
string s,t; 
int check(int x){
    return pre[x]==suf[x];
}
signed main(){
    cin >> n >> m;
    cin >> s >> t;
    s=' '+s+' ';
    t=' '+t+' ';
    int l=1,r=n;
    pow[0]=1;
    for (int i=1;i<=m;i++)
        pow[i]=pow[i-1]*K;
    for (int i=m;i>=1;i--){
        pre[i]=pre[i+1]*K+(t[i]-'a');
        suf[i]=suf[i+1]+pow[m-i]*(t[i]-'a');
    }
        
    for (int i=1;i<=m;i++){
        while(l<=n&&s[l]!=t[i]) l++;
        //if (l>n) break;
        l++;        
    }
    for (int i=1;i<=m;i++){
        if (l<=r+1) res+=check(i);
        while(r>0&&s[r]!=t[i]) r--;
        //if (r<=0) break;
        r--;
    }
    if (l<=r){
        dp[l-1]=1;
        for (int i=l;i<=r;i++){
            if (last[s[i]]) dp[i]=(dp[i-1]*2-dp[last[s[i]]-1]+P)%P;
                else dp[i]=dp[i-1]*2%P;
            last[s[i]]=i;        
        }

        res=(res+dp[r])%P;    
    }
    if (r==l-1) res=(res+1)%P;
    cout << res << endl;
    return 0;
}

J

考虑极限的情况，最极限就是两端能否扫到

没想到极限的话就可能要算不等式

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
void Kafka()
{
    int l=read(),x=read(),y=read();
    if(1LL*x*x+1LL*y*y<=1LL*l*l) printf("Yes\n0\n");
    else if(1LL*(l-x)*(l-x)+1LL*y*y<=1LL*l*l) printf("Yes\n%d\n",l);
    else puts("No");    
}
signed main()
{
    for(int T=read();T--;) Kafka();
    return 0;
}

I

首先可以二分枚举，初始机器n越多，最后能造成的伤害越多

肯定是先造新的机器，直到不能再造，然后全都拿去打击怪物

造新的机器这个问题就转化成：

给定n，每次用m个换新的k个，最后能换出多少个。

可以写出递推式子f(n)=f(n-m+k)+m，可以把-m+k写成-c

等价为f(n)=f(n-c)+m=f(n-2c)+2m=...

但是不能直接把n减到小于c，因为要满足先够-m然后再+k，这里就特判一下

#include<bits/stdc++.h>
using namespace std;

inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
#define int long long
int m,k,h;
int check(int n,int h){
    if(n<m){
        if(n<h) return 0;
        else return 1;
    }
    int c=m-k;
    int sum=((n-m)/c+1)*m;
    sum+=(n-m)%c+k;
    if(sum>=h) return 1;
    else return 0;
}
void solve(){
    cin>>m>>k>>h;
    if(h==0) {
        cout<<0<<"\n";
        return;
    }
    if(k==m){
        if(m-1>=h) {
            cout<<h<<"\n";
        }
        else cout<<m<<"\n";
    }
    else {
        int l=0,r=h,ans=-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(check(mid,h)){
                ans=mid;
                r=mid-1;
            }
            else l=mid+1;
        }
        cout<<ans<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

D

队友用一种神奇的哈希过了

把所有数出现的次数哈希

原本哈希字符串是abcdeaa，给它哈希成一个值

同理用cnt[x]表示x出现的次数，cnt[1]cnt[2]cnt[3]..cnt[n]，给它哈希成一个值

则在i这个位置时，能匹配得上的一定是之前位置哈希值也一样的数

但是有一个问题！！

能匹配得上的位置也可能是k的倍数，所以再用一个双指针维护一下

#include<bits/stdc++.h>
#define int long long
using namespace std;
const __int128 P=1000000000000000003;
const int N=2e5+505;
inline int read()
{
    int x=0;bool f=1;char ch=getchar();
    for(;ch<'0'||ch>'9';ch=getchar())f^=(ch=='-');
    for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    return f?x:-x;
}
int n,k,m;
int a[N],h[N],dp[N];
__int128 hs[N];
map<int,int> f,g;
struct lst{
    vector<int> c,d;
    int n,t,i=1;
    int sum=0;
    void init(int _n,int _t){
        n=_n;
        t=_t;
        c.resize(n+5);
        d.resize(n+5);
    }
    void next(){
        int p=a[i];
        c[p]++;
        d[p]++;
        if (t==-1) g[sum]+=t;
        sum=(sum+hs[p])%P;
        //printf("p=%lld\n",p);
        if (d[p]==k){
            d[p]=0;
            sum=(sum-hs[p]*k%P+P)%P;
        }
        if (t==1) g[sum]+=t;
        i++;
    }
};
void test(){
    for (int i=0;i<=n;i++)
        printf("a[%lld]=%lld\n",i,a[i]);
    for (int i=1;i<=n;i++)
        cout << (long long)hs[i] << endl;
}
void test_map(){
    for (auto i=g.begin();i!=g.end();i++){
        printf("%lld %lld\n",i->first,i->second);
    }
}
void work(){
    n=read(); k=read();
    for (int i=1;i<=n;i++)
        a[i]=read();
    f.clear(); g.clear(); 
    
    for (int i=1;i<=n;i++)
        f[a[i]]=0;
    m=0;
    for (auto i=f.begin();i!=f.end();i++)
        i->second=++m;
    
    for (int i=1;i<=n;i++)
        a[i]=f[a[i]];
    lst p,q;
    p.init(n,1);
    q.init(n,-1);
    int res=0;
    //test();
    g[0]=1;
    for (int i=1;i<=n;i++){
        int pos=a[i];
        p.next();
        while(p.c[pos]-q.c[pos]>k){
            q.next();
            //printf("%lld %lld q.i=%lld\n",p.c[pos],q.c[pos],q.i);
        }
        
        res+=g[p.sum]-1;
        //printf("add %lld:%lld %lld\n",i,g[p.sum]-1,p.sum);
        //test_map();
        //printf("p.i=%lld q.i=%lld\n",p.i,q.i);
    }
    
    
    cout << res << endl;
}
signed main()
{
    hs[0]=0;
    hs[1]=1;
    for (int i=2;i<N;i++){
        hs[i]=hs[i-1]*N%P;
    }
    int T;
    T=read();
    while(T--) work();
    return 0;
}