526互联

[LGR-152-Div2] 全场题解

发布时间 2023-09-08 10:49:18作者: NBest

2023-08-22 16:15:06

前言

现在的比赛怎么都开始向 CF Div.2 的遍地结论题看齐了，感觉打下来 3 题都是结论题？

A

这么秒的题我一开始猜结论居然猜错了啊啊啊。

看了题目以后，毫无头绪，准备从部分分入手。

\(p=2\)？奇奇偶偶互配即可，找不出什么性质。

\(p=3\)？发现 \(\%3=1\) 的和 \(\%3=2\) 的配最好，然后就想到是不是只需要按顺序配余数互补？调了20分钟才发现有很多反例，于是不出意料的挂了。这时想到如果把相同的余数放到一起，它们会组和组之间又产生贡献，于是这题就做完了，把每个余数相同的配在一起输出，然后把余数和自己配对的和没有余数的单独输出即可，注意 \(p\le10^8\)，我们要特判当 \(p\ge 2n\) 时直接随意输出一个序列即可，因为不可能产生任何贡献。

\(Code\)

int T,n,p;
int main(){
    T=read();
    while(T--){
        n=read(),p=read();
        if(p<=2||p>=2*n){
            for(int i=1;i<=n;i+=2)printf("%d ",i);
            for(int i=2;i<=n;i+=2)printf("%d ",i);
            puts("");
            continue;
        }
        for(int k=1;k<=(p-1>>1);k++){
            for(int i=k;i<=n;i+=p){
                int j=i+p-k*2;
                if(j<=n)printf("%d %d ",i,j);
                else printf("%d ",i);
            }
        }
        if(p+1&1)for(int i=p/2;i<=n;i+=p)printf("%d ",i);
        for(int i=p;i<=n;i+=p)printf("%d ",i);
        puts("");
    }
}

B

一开始想到只要出现 BTTB 就转换，因为两个 B 把 T 给挡住了，所以放出来肯定比挡住要优，果不其然又猜错了，因为 BTBTTB 转换之后前面还能转换，所以还得回去继续转换，所以就又根据这个乱打了一个，发现还是不行，因为 BTBTTBTTBTTTTTT 如果把前面转换了后面就换不了，还是不够优，机智的我倒着做了一遍，骗了 55，还是会 WA 一个点。

讨论来讨论去太麻烦了，重新思考正解，观察到我们只需要求最大值，而对于每一个 T 序列，通过转换最多加 2 的长度，所以我们只需要对于 T 串向左右搜即可，这样会 TLE，还得加一些诸如记忆化和剪枝的优化，然后就过了？真是正解比歪门邪道好想。

\(Code\)

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> PII;
int T,n,f[100050];
int f1[100005],f2[100005];
string l;
priority_queue<PII>Q;
bool check1(int x){
    if(x<1||x>n)return 0;
    if(~f1[x])return f1[x];
    if(l[x]=='B'&&l[x+1]=='T'&&l[x+2]=='T'&&l[x+3]=='B')return f1[x]=f2[x+3]=1;
    if(l[x]!='B'||l[x+1]!='T')return f1[x]=0;
    return f1[x]=check1(x+2);
}
bool check2(int x){
    if(x<1||x>n)return 0;
    if(~f2[x])return f2[x];
    if(l[x]=='B'&&l[x-1]=='T'&&l[x-2]=='T'&&l[x-3]=='B')return f1[x-3]=f2[x]=1;
    if(l[x]!='B'||l[x-1]!='T')return f2[x]=0;
    return f2[x]=check2(x-2);
}
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);std::cout.tie(0);
    for(cin>>T;T--;){
        cin>>n>>l;
        string s=l;
        while(!Q.empty())Q.pop();
        l=" "+l+"         ";
        int ans=0;
        for(int i=1;i<=n;i++)
            ans=max(ans,(f[i]=(l[i]=='T'?1+f[i-1]:0))),f1[i]=f2[i]=-1;
        bool flag=0;
        for(int i=n;i;--i){
            if(!flag&&f[i])Q.push({f[i],i}),flag=1;
            if(!f[i])flag=0;
        }
        while(!Q.empty()){
            int r=Q.top().second,l=r-Q.top().first+1;
            Q.pop();
            int res=r-l+1;
            if(res<=ans-2)break;
            if(check1(r+1))res++;
            if(check2(l-1))res++;
            ans=max(ans,res);
        }
        cout<<ans<<endl;
    }
}

C

这题说实话我一开始想的就已经很接近正解了，可是邪恶的 IOI 赛制和奇葩的数据，导致我一度舍弃了我的正解。

第一眼还是一点头绪都没有，所以再看一眼部分分，思考 \(n\) 偶数的时候，我们只需要让全部 \(\gcd\) 为 \(1\) 然后对半分即可，\(a_i\) 全是奇数的时候，一开始我是先直接输出 \(-1\) 发现这一档数据全过了，再考虑到奇数的 \(\gcd\) 也是奇数，在 \(n\) 也为奇数的情况下是不可能分成相等的两部分的（奇数个奇数相加也是奇数，无法对半分）。

这时我考虑到这题是不是也有什么结论，比如只需要考虑奇偶什么的，想到假如有偶数，并且偶数个数为奇数，这时令 \(x\) 为 \(2\)，然后去掉一个偶数对半分，让其中的一个 \(1\) 跑到另外一组去再把这个 \(2\) 放到这组即可，对于偶数个偶数，抵消后是会剩下奇数个 \(1\) 然后凑不出来的输出 \(-1\)。交上去发现一个点都没过？卑微的我就开始怀疑我解法的正确性了。同时我又交了一个如果全是偶数就输出 \(-1\) 的特判，发现之前输出 \(-1\) 能过的点又都过了？？？我。。。（赛后：这什么数据啊）我就理所当然的认为全是偶数和全是奇数都是不行的，最后结束了也没想到正解。

后来经过题解的一点点指点，瞬间知道为什么错了——大部分数据都是全偶的，只需要把全偶的除上若干个 \(2\) 看成之前的情况做就行了。相信自己啊，再思考周全一点就过了！！！

\(Code\)

int n,a[100005],k=1000000,ou;
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        k=min(k,((a[i]=read())&-a[i]));
    for(int i=1;i<=n;i++)
        ou+=(a[i]/=k)+1&1;
    if(n+1&1){
        puts("1");
        for(int i=1;i<=n/2;i++)printf("01");
        return 0;
    }
    if(ou+1&1)return puts("-1"),0;
    printf("%d\n",k<<1);
    //从赛时代码直接搬来的
    int o2=ou/2,o1=(n-ou)/2+1;
    for(int i=1;i<=n;i++){
        if(a[i]&1){
            if(o1)o1--,putchar(49);
            else putchar(48);
        }else{
            if(o2)o2--,putchar(49);
            else putchar(48);
        }
    }
}

D

题意就是给定一个字符串，删除一个非空区间后拼起来后找目标子串的方案数。

显然有两种答案，一个是本来就有的，一个是删除一段区间拼起来以后产生的。

对于本来就有的，先记录哈希，然后扫一遍，再用乘法原理计算一下总贡献即可。

对于拼起来的，我们对每一个 \(i\le n\) 记录前缀匹配数和后缀匹配数，对于第 \(i\) 位，假设它的后缀匹配数为 \(l_i\)，那么前 \(i-|t|\) 个前缀 \(r_j\) 中满足 \(1\le r_j\le |t|-l_i\) 的都可以记录答案。这个用一个树状数组或者线段树的区间操作即可实现 \(O(\log m)\) 查询和修改。

前缀和后缀匹配数用二分答案统计即可。(写了一个 \(l=0,r=|t|,while(l<=r)\) 的二分打挂了，以后得抽时间研究一下二分的区别和运用了)

long long 一定要开全，我调了一下午发现写了很久的 int query()。

\(Code\)

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;
#define mid (l+r>>1)
const ll p=1331;
ll s[400005],t[200005],P[400005];
//prehash(s),prehash(t),premul(p)
string S,T;
int n,m;
long long ans,d[400005],id[400005];
inline bool check(int l,int r,int L,int R){
    if(l<1||r>n||L<1||R>m||r<l||R<L||r-l+1!=R-L+1)return 0;
    return (s[r]-s[l-1]*P[r-l+1]==t[R]-t[L-1]*P[R-L+1]);
}
int L[400005],R[400005];//向左最大匹配，向右最大匹配 
inline int lb(int x){return (x&-x);}
void add(int x,int v){
    for(int i=x;x<=m;x+=lb(x))
        d[x]+=v,id[x]+=1ll*i*v;
}
long long query(int x){
    long long res=0;
    for(int i=x+1;x;x-=lb(x))
        res+=d[x]*i-id[x];
    return res;
}
inline void add(int l,int r,int v){
    if(l>r)return;
    add(l,v),add(r+1,-v);
}
inline long long query(int l,int r){
    if(l>r)return 0;
    return query(r)-query(l-1);
}
int main(){
    cin>>S>>T;
    n=S.length(),m=T.length();
    S=" "+S,T=" "+T;
    P[0]=1;
    for(int i=1;i<=n;i++){
        P[i]=P[i-1]*p;
        s[i]=s[i-1]*p+(S[i]-'a');
    }
    for(int i=1;i<=m;i++){
        t[i]=t[i-1]*p+(T[i]-'a');
    }
    for(int i=1;i<=n;i++){
        int l=1,r=m+1,o=0;//o 记录最后一个满足的答案
        while(l<=r){
            if(check(i,i+mid-1,1,mid))o=mid,l=mid+1;
            else r=mid-1;
        }
        R[i]=o;
        l=1,r=m+1,o=0;
        while(l<=r){
            if(check(i-mid+1,i,m-mid+1,m))o=mid,l=mid+1;
            else r=mid-1;
        }
        L[i]=o;
        if(R[i]==m){
            ans+=1ll*(i-1)*i/2;
            if(i<=n-m)ans+=1ll*(n-(i+m-1))*(n-(i+m-1)+1)/2;
        }
    }
    for(int i=1;i<=n;i++){
        if(i-m>=1)add(1,min(R[i-m],m-1),1);
        ans+=query(max(1,m-L[i]),m-1);
    }
    cout<<ans;
    return 0;
}