ICPC2023合肥站：D. Balanced Array

这道题我也没有想到正解，用了一个奇技淫巧过了。

显然，对于每个k，它所满足要求的i肯定是一个区间。

我们不难发现，满足条件的$k$基本都很大（相对于(n-1)/2)，因此我们维护最大的20个满足条件的k即可。

#include
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){
    x=0;int f=0;char s=getchar();
    while(!isdigit(s))f|=s=='-',s=getchar();
    while(isdigit(s))x=x*10+s-48,s=getchar();
    x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){
    if(x<0)putchar('-'),x=-x;
    do{buf[++cc]=int(x%10);x/=10;}while(x);
    while(cc)putchar(buf[cc--]+'0');
}
const int N=2e6+10;
int n,a[N];char s[30];
int tp,sta[30];
bool check(int i,int j){
    return 2*a[i-j]==a[i]+a[i-2*j];
}
void push(int x){
    if(tp==20){
        rep(i,1,tp-1)sta[i]=sta[i+1];
        sta[tp]=x;
    }
    else{
        sta[++tp]=x;
    }
}
void update(int now){
    rep(i,1,tp)if(!check(now,sta[i]))sta[i]=0;
    int last=tp;tp=0;
    rep(i,1,last){
        if(sta[i])sta[++tp]=sta[i];
    }
}
void solve(){
    qr(n);
    rep(i,1,n){
        scanf("%s",s+1);int len=strlen(s+1);
        rep(j,1,len){
            int w;
            if('0'<=s[j]&&s[j]<='9')w=s[j]-'0';
            else if('a'<=s[j]&&s[j]<='z')w=s[j]-'a'+10;
            else w=s[j]-'A'+36;
            a[i]=a[i]*62+w;
        }
    }
    rep(i,1,n){
        if(i>=3&&i%2==1){
            int num=i/2;
            if(check(i,num))push(num);
        }
        update(i);
        putchar(tp?'1':'0');
    }
}
int main(){
    int tt;tt=1;
    while(tt--)solve();
    return 0;
}

后面看到题解居然能够用哈希进行快速的判断。
考虑一段数，我们把它复制成三份，第一份不变，第二份往左边移动k个位置，第三份往右边移动k个位置，那很明显就是上下的和等于中间的两倍。

#include
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
#define ull unsigned long long
using namespace std;
template<typename T>inline void qr(T &x){
    x=0;int f=0;char s=getchar();
    while(!isdigit(s))f|=s=='-',s=getchar();
    while(isdigit(s))x=x*10+s-48,s=getchar();
    x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){
    if(x<0)putchar('-'),x=-x;
    do{buf[++cc]=int(x%10);x/=10;}while(x);
    while(cc)putchar(buf[cc--]+'0');
}
const int N=2e6+10;
int n,a[N],c[N];
ull hsh[N],val[N];
ull hsh2[N],val2[N];
ull calc(int l,int r){
    if(l>r)return 0;
    return hsh[r]-hsh[l-1]*val[r-l+1];
}
ull calc2(int l,int r){
    if(l>r)return 0;
    return hsh2[r]-hsh2[l-1]*val2[r-l+1];
}
bool check(int i,int k){
    return calc(1,i-2*k)+calc(2*k+1,i)==calc(k+1,i-k)*2ull
    &&calc2(1,i-2*k)+calc2(2*k+1,i)==calc2(k+1,i-k)*2ull;
}
void solve(){
    qr(n);
    if(n<=2){
        rep(i,1,n)putchar('0');
        return;
    }
    char s[20];
    val[0]=1;
    val2[0]=1;
    rep(i,1,n){
        scanf("%s",s+1);
        int len=strlen(s+1);
        rep(j,1,len){
            if('0'<=s[j]&&s[j]<='9')a[i]=a[i]*62+(s[j]-'0');
            else if('a'<=s[j]&&s[j]<='z')a[i]=a[i]*62+(s[j]-'a'+10);
            else a[i]=a[i]*62+(s[j]-'A'+36);
        }
        val[i]=val[i-1]*998244353;
        hsh[i]=hsh[i-1]*998244353+a[i];
        val2[i]=val2[i-1]*200000009;
        hsh2[i]=hsh2[i-1]*200000009+a[i];
    }
    int now=1;
    putchar('0');putchar('0');
    rep(i,3,n){
        while(now+1<=(i-1)/2&&!check(i,now))now++;
        if(check(i,now))putchar('1');
        else putchar('0');
    }
}
int main(){
    int tt;tt=1;
    while(tt--)solve();
    return 0;
}