XSY 1903 - Circle of Stones & XSY 1606 - 大包子的绕口令

题目精选 KMP FFT

题意

  桌子上有 $n$ 个石头围成一个环。每个石头都有一种颜色。每种颜色可以由小写英文字母表示，所以总共有 $26$ 种颜色。不同的石头可能有相同的颜色。

  如果每一对的石头都是不同颜色的，则称这 $n$ 个石头构成的环是美丽的。两个石头是相邻的充要条件是这两个石头中间没有其它石头。例如：$1$ 号和 $2$ 号是相邻的，$2$ 号和 $3$ 号是相邻的，……，$n$ 号和 $1$ 号是相邻的。

  现在，你可以从这 $n$ 个石头中拿走一段连续的石头（可以为空），且你只能拿一次。

  你的任务是对于每个 $k(0≤k≤n−1)$ ，判断是否存在一种取石头的方案，使得在拿走 $k$ 个连续的石头后，剩下的 $n−k$ 个石头构成的环是美丽的。

   $n\le 10^6$

分析

  现在的问题是是否能删去连续的 $k$ 个， $0\le k\le n-1$ ，使得剩下的 $n-k$ 个两两不同。那么，问题等价于能否保留连续的 $k$ 个， $1\le k\le n$ ，它们两两不同。

  首先将数组 $a$ 进行倍长。

  我们考虑到，若在原数组中 $a$ 中，存在一个位置 $i$ ， $a_i=a_{i+1}$ ，则我们保留的区间一定不同时覆盖 $i$ 与 $i+1$ 。按照 $a_i\ne a_{i+1}$ ，将原数组分段。那么，考虑每个段内可以保留的情况，然后并起来即可。对于一个段，长度为 $len$ ，那么段内保留的长度上限一定是 $O(len)$ 的，所以总共的保留是 $O(n)$ 的。

  对于一个段，它的任意两个相邻元素不同。我们考虑能否保留连续的 $k$ 个。直接想能否保留不好想，我们考虑怎样才不能保留连续的 $k$ 个。那么要求 $a_i=a_{i+k-1}$ ，所以 $a_{1..k-1}$ 是原串的一个覆盖串。我们只要找到所有的覆盖串，就能确定所有不能覆盖的了，反之就是能覆盖的。

分析2

  我们记 $b_i=[a_i=a_{i-1}],s_k=\sum_{i\le k} b_i$ 。
  考虑一个区间 $[l,r]$ 什么时候合法。合法，当且仅当 $a_l\ne a_r$ ，且 $s_r-s_l=0$ ，它可以贡献到 $n-(r-l+1)$ 。
  发现 $s$ 是单调递增的，所以只需要对连续的一段，对所有 $a_l\ne a_r$ ，贡献到 $n-(r-l+1)$ 。
  我们构造式子 $c_k=\sum_{i-j=k}(a_i-a_j)^2\times a_i\times b_j$ ，那么，一个位置 $k$ 有解，当且仅当 $c_k>0$ 。
  如何快速求 $c_k$ ？我们考虑将一个 $a$ 进行翻转，然后用 FFT 解决。

  为什么分析2能更巧妙的化为分析1？
  首先，发现 $s$ 单调递增，这相当于进行分段。
  然后，我们 FFT 做法的本质是用优化暴力，但实际上有着更多的特性：循环节。从而有了分析1。

  这种做法在 xsy1903 一题25分 ， xsy1606 一题50分。

实现

KMP：
将 int 写成了 char ，调了好久。

#include <cstdio>
#include <cstring>
#define F(i,a,b) for (int i=(a);i<=(b);i++)
const int N=2097152;
const int INF=0x7fffffff;
int n,n2;
char s[N];
int v[N];
int len;
int nx[N];
char ans[N];
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        freopen("sdchr.out","w",stdout);
    #endif
    F(c,1,INF) {
        memset(s,0,sizeof s);
        if (scanf("%s",s+1)==EOF) break;
        n=strlen(s+1);
        n2=n+n;
        F(i,n+1,n2) s[i]=s[i-n];
        memset(v,0,sizeof v);
        F(x,1,n2) {
            int d=x-1;
            int y=x; while (y+1<=n2&&s[y]!=s[y+1]) y++;
            len=y-x+1;
            int j=nx[1]=0;
            F(i,2,len) {
                while (j>0&&s[d+j+1]!=s[d+i]) j=nx[j];
                if (s[d+j+1]==s[d+i]) j++;
                nx[i]=j;
            }
            F(i,1,len) v[i]++;
            for (int i=len;nx[i]>0;i=nx[i])
                v[(len-nx[i])+1]--;
            x=y;
            memset(nx,0,sizeof(nx[0])*len);
            len=0;
        }
        memset(ans,0,sizeof ans);
        F(i,0,n-1)
            if (v[n-i]>0)
                ans[i]='1';
            else ans[i]='0';
        ans[n]='\n';
        printf("Case %d: %s",c,ans);
    }
    return 0;
}

FFT：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
#define F(i,a,b) for (int i=(a);i<=(b);i++)
const int N=4194304;
const int INF=0x7fffffff;
const double PI=acos(-1);
int n;
int a[N];
int n2;
int b[N],s[N];
int bit,len,rev[N];
struct CP {
    double x,y;
    inline CP(double _x=0,double _y=0):x(_x),y(_y){}
    friend inline CP operator + (CP a,CP b) {
        return CP(a.x+b.x,a.y+b.y);
    }
    friend inline CP operator - (CP a,CP b) {
        return CP(a.x-b.x,a.y-b.y);
    }
    friend inline CP operator * (CP a,CP b) {
        return CP(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
    }
}A[N],A2[N],A3[N],B[N],B2[N],B3[N],R[N];
char ans[N];
inline int Read(int &n,int *a) {
    static char s[N]; if (scanf("%s",s+1)==EOF) return 0;
    n=strlen(s+1); F(i,1,n) a[i]=s[i]-'a'+1; return 1;
}
void FFT(CP *a,int bit,int n,int kd) {
    F(i,0,n-1) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int i=2;i<=n;i<<=1) {
        CP wn(cos(2*PI/i),kd*sin(2*PI/i));
        for (int j=0;j<n;j+=i) {
            CP w(1,0);
            F(k,0,i/2-1) {
                CP x=a[j+k],y=w*a[j+k+i/2];
                a[j+k]=x+y,a[j+k+i/2]=x-y;
                w=w*wn;
            }
        }
    }
    if (kd==-1) F(i,0,n-1) a[i].x=round(a[i].x/n),a[i].y=0;
}
int main(void) {
    #ifndef ONLINE_JUDGE
        freopen("sdchr.in","r",stdin);
        freopen("sdchr.out","w",stdout);
    #endif
    F(c,1,INF) {
        if (!Read(n,a)) break;
        n2=n+n; F(i,n+1,n2) a[i]=a[i-n];
        F(i,2,n2) b[i]=(a[i]==a[i-1]),s[i]=s[i-1]+b[i];
        fill(ans,ans+(n-2)+1,'0'); ans[n-1]='1',ans[n]='\n';
        F(x,2,n2) {
            int y=x; while (y+1<=n2&&s[y+1]==s[x]) y++;
            int length=y-x+1;
            for (bit=0,len=1;len<=(length-1)+(length-1);bit++,len<<=1);
            F(i,0,len-1) rev[i]=rev[i>>1]>>1|(i&1)<<(bit-1);
            F(i,x,y) {
                int loc=i-x;
                A[loc]=B[loc]=CP(a[i]);
                A2[loc]=B2[loc]=CP(a[i]*a[i]);
                A3[loc]=B3[loc]=CP(a[i]*a[i]*a[i]);
            }
            reverse(B,B+length);
            reverse(B2,B2+length);
            reverse(B3,B3+length);
            FFT(A,bit,len,1);
            FFT(A2,bit,len,1);
            FFT(A3,bit,len,1);
            FFT(B,bit,len,1);
            FFT(B2,bit,len,1);
            FFT(B3,bit,len,1);
            F(i,0,len-1)
                R[i]=A3[i]*B[i]+CP(-2)*A2[i]*B2[i]+A[i]*B3[i];
            FFT(R,bit,len,-1);
            F(i,0,len-1) if (R[i].x>0) {
                int loc=n-(i-(length-1)+1);
                if (0<=loc&&loc<=n-2)
                    ans[loc]='1';
            }
            memset(A,0,sizeof(A[0])*len);
            memset(A2,0,sizeof(A2[0])*len);
            memset(A3,0,sizeof(A2[0])*len);
            memset(B,0,sizeof(B[0])*len);
            memset(B2,0,sizeof(B2[0])*len);
            memset(B3,0,sizeof(A2[0])*len);
            memset(R,0,sizeof(R[0])*len);
            x=y;
        }
        printf("Case %d: ",c);
        fwrite(ans,1,n+1,stdout);
        memset(a+1,0,sizeof(a[0])*n2);
        memset(b+1,0,sizeof(b[0])*n2);
        memset(s+1,0,sizeof(s[0])*n2);
    }
    return 0;
}