求条ARC B

diqiuyi @ 2024-08-04 22:03:27

#include <bits/stdc++.h>
#define ll long long
#define int long long 
using namespace std;
int t,n,m,cntx,cnty,lx,ly,nxt[500005];
string s,x,y;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    cin>>t;
    while(t--){
        cin>>s>>x>>y,n=s.size(),lx=x.size(),ly=y.size(),s='@'+s,cntx=cnty=0;
        for(int i=0;i<x.size();i++) cntx+=(x[i]=='0');
        for(int i=0;i<y.size();i++) cnty+=(y[i]=='0');
        if(cntx==cnty){
            cout<<"Yes\n";
            continue;
        }
        if(lx-ly-cntx+cnty==0){
            cout<<"No\n";
            continue; 
        }
        ll res=1ll*(cnty-cntx)*n/(lx-ly-cntx+cnty);
        if(res*(lx-ly-cntx+cnty)!=1ll*(cnty-cntx)*n||res<0){
            cout<<"No\n";
            continue;
        }
        for(int i=2;i<=n;i++){
            nxt[i]=nxt[i-1];
            while(nxt[i]&&s[i]!=s[nxt[i]+1]) nxt[i]=nxt[nxt[i]];
            if(s[i]==s[nxt[i]+1]) nxt[i]++;
        }
        int len;
        if(nxt[n]*2<n) len=n;
        else len=n-nxt[n];
        if(!(res%len)) cout<<"Yes\n";
        else cout<<"No\n";
    }
    return 0;
} 

by Btls @ 2024-08-04 22:29:57

帮你改了，下面的KMP是错的。

#include <bits/stdc++.h>
#define ll long long
#define int long long 
using namespace std;
int t,n,m,cntx,cnty,lx,ly,nxt[500005];
string s,x,y;
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); 
    cin>>t;
    while(t--){
        cin>>s>>x>>y,n=s.size(),lx=x.size(),ly=y.size(),s='@'+s,cntx=cnty=0;
        for(int i=0;i<x.size();i++) cntx+=(x[i]=='0');
        for(int i=0;i<y.size();i++) cnty+=(y[i]=='0');
        if(cntx==cnty){
            cout<<"Yes\n";
            continue;
        }
        if(lx-ly-cntx+cnty==0){
            cout<<"No\n";
            continue; 
        }
        ll res=1ll*(cnty-cntx)*n/(lx-ly-cntx+cnty);
        if(res*(lx-ly-cntx+cnty)!=1ll*(cnty-cntx)*n||res<0){
            cout<<"No\n";
            continue;
        }
        res=__gcd(n,res);
        bool f=0;
        for(int i=1;i<=n-res;++i)if(s[i]!=s[i+res])
        {
            f=1;
            break;
        }
        if(f)cout<<"No\n";
        else cout<<"Yes\n";
    }
    return 0;
} 

by SlayedDrawer @ 2024-08-04 22:30:04

一致讨论得出：你的 KMP 有问题。而且你没有取 gcd。

负负得正。 @diqiuyi

by SlayedDrawer @ 2024-08-04 22:33:03

kmp 结论本身有问题。其实你要加上关于最小整周期的判断。你原来的判断是错的。

by SlayedDrawer @ 2024-08-04 22:34:55

你求的应该是最小周期。

by SlayedDrawer @ 2024-08-04 22:35:41

拜谢 @PrinceX @2020wjn

by PrinceX @ 2024-08-04 22:37:17

在35行加一个判断即可：

        if(n%len) len=n;

by diqiuyi @ 2024-08-05 12:44:07

@PrinceX @Aleph_Drawer @2020wjn 已经过了，感谢各位

by diqiuyi @ 2024-08-05 12:51:21

@Aleph_Drawer 我求的甚至不是最小周期。