7.22 学习笔记

其只是内容已经在其他的博客中整理过，这里不再赘述。下面开始例题讲解。

1 例题

1.1 P3454 [POI2007]OSI-Axes of Symmetry

多边形的对称轴数量。我们直接用边长的平方和邻边作为字符，断环为链（复制一段），然后跑 Manacher，判断是否有符合长度的回文串即可。代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define int long long 
#define uint unsigned int
#define ull unsigned long long
#define N 1000100
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> inline T Max(T a,T b){
    return a<b?b:a;
}

template<typename T> inline T Min(T a,T b){
    return a<b?a:b;
}

int t,n;
struct point{
    ll x,y;
    inline point(){}
    inline point(ll x,ll y) : x(x),y(y) {}
    inline ll operator ^ (const point &b) const{
        return x*b.y-y*b.x;
    }
    inline point operator - (const point &b) const{
        return point(x-b.x,y-b.y);
    }
};
point a[N];
ll b[N],tail;
ll c[N],L;

inline int dis(point a,point b){
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}

inline void ManacherPre(){
    for(int i=1;i<=tail;i++){
        c[i*2]=b[i];c[i*2-1]=INF;
    }
    c[2*tail+1]=INF;L=2*tail+1;
}

int len[N<<2];

inline void Manacher(){
    ManacherPre();
    int maxright=0,mid=0;
    for(int i=1;i<=L;i++){
        if(i<maxright) len[i]=Min(len[(mid<<1)-i],len[mid]+mid-i);
        else len[i]=1;
        while(i+len[i]<=L&&i-len[i]>=1&&c[i+len[i]]==c[i-len[i]]) len[i]++;
        if(maxright<i+len[i]){mid=i;maxright=i+len[i];}
    }
}

inline void Clear(){
    for(int i=1;i<=L;i++) len[i]=c[i]=0;
    tail=0;L=0;
}

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y;
        b[++tail]=((a[n]-a[1])^(a[2]-a[1]));
        if(b[tail]>0) b[tail]*=-1;
        for(int i=2;i<=n-1;i++){
            b[++tail]=dis(a[i-1],a[i]);
            b[++tail]=((a[i-1]-a[i])^(a[i+1]-a[i]));
            if(b[tail]>0) b[tail]*=-1;
        }
        b[++tail]=dis(a[n],a[n-1]);
        b[++tail]=((a[n-1]-a[n])^(a[1]-a[n]));
        if(b[tail]>0) b[tail]*=-1;
        b[++tail]=dis(a[1],a[n]);
        // for(int i=1;i<=tail;i++) printf("i:%d b:%d
",i,b[i]);putchar('
');
        for(int i=1;i<=tail;i++) b[i+tail]=b[i];
        tail*=2;
        // printf("tail:%d
",tail);
        // for(int i=1;i<=tail;i++) printf("i:%d b:%d
",i,b[i]);putchar('
');
        Manacher();int ans=0;
        // for(int i=1;i<=L;i++) printf("i:%d c:%d
",i,c[i]);putchar('
');
        for(int i=1;i<=L;i++){
            int nowlen=len[i]/2;
            int now=2*nowlen-1;
            if(now>=tail/2){
                ans++;
                // printf("i:%d
",i);
            }
        }
        cout<<ans/2<<"
";
        Clear();
    }
    return 0;
}
/*
update 1 101-106,108 处理循环，计算答案有问题。
*/

1.2 P2375 [NOI2014] 动物园

这个题其实就是 KMP 的 next 数组，但是要求两段不能重叠。一开始我考虑直接在求 next 数组的时候让他们不重叠。但这样是不行的，这是因为你前面求的 next 会影响你求后面的 next 。所以我们直接求出所有的 next，然后统计答案的时候我们相当于是在上次 next 的基础上再求一遍 next，不能一个一个暴力去做，否则会超时。

上面这段话总结一下就是我们先求 next 数组，再求需要满足不重叠的数组。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define int long long
#define uint unsigned int
#define ull unsigned long long
#define N 1000010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;
const ll mod=1e9+7;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

int n,nxt[N],num[N],ans=1;
char s[N];

signed main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    read(n);
    while(n--){
        ans=1;
        scanf("%s",s+1);
        int len=strlen(s+1);
        nxt[1]=0;num[1]=1;
        for(int i=2,j=0;i<=len;i++){
            while(j>0&&s[j+1]!=s[i]) j=nxt[j];
            if(s[j+1]==s[i]) j++;
            nxt[i]=j;num[i]=num[j]+1;
        }
        // for(int i=1;i<=len;i++){
        //     int cha=nxt[i]*2-i;
        //     if(cha>0){nxt[i]-=cha/2;}
        // }
        for(int i=2,j=0;i<=len;i++){
            while(j>0&&s[j+1]!=s[i]) j=nxt[j];
            if(s[j+1]==s[i]) j++;
            // if(j!=nxt[i]) while(1);
            while((j<<1)>i) j=nxt[j];
            ans*=(num[j]+1);ans%=mod;
        }
        // for(int i=1;i<=len;i++){
        //     if(nxt[i]==0) continue;
        //     num[i]=(num[nxt[i]]+1)%mod;
        // };
        // for(int i=1;i<=len;i++) printf("%d ",nxt[i]);putchar('
');
        // for(int i=1;i<=len;i++) printf("%d ",num[i]);putchar('
');
        // for(int i=1;i<=len;i++){
        //     ans*=(num[i]+1);ans%=mod;
        //     // printf("nowans:%lld
",ans);
        // }
        printf("%lld
",ans);
        for(int i=1;i<=len;i++) num[i]=nxt[i]=0;
    }
}

1.3 P3435 [POI2006]OKR-Periods of Words

不难发现如何做这个题，这个也是 KMP 的简单应用，通过在纸上手玩几个数据可以知道，我们相当于不断跳 next 数组，往小了跳，直到不能跳了位置，然后把 (i-j) 加上即可。

我们可以用记忆化的方式优化时间复杂度。

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<bits/stdc++.h>
#include<cstring>
#define dd double
#define ld long double
#define int long long
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 1000010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

char s[N];
int nxt[N],ans,n;

signed main(){
    read(n);
    scanf("%s",s+1);int len=strlen(s+1);
    nxt[1]=0;
    for(int i=2,j=0;i<=len;i++){
        while(j>0&&s[j+1]!=s[i]) j=nxt[j];
        if(s[j+1]==s[i]) j++;
        nxt[i]=j;
    }
    int j=0;
    for(int i=2;i<=len;i++){
        j=i;
        while(nxt[j]>0) j=nxt[j];
        if(nxt[i]!=0) nxt[i]=j;
        ans+=i-j;
    }
    printf("%lld",ans);
    return 0;
}

1.4 UVA10298 Power Strings

我们仍然还是先跑一遍 KMP 求出 next 数组来。然后我们考虑 next 数组的最后一位：(next_{len}) ，我们发现用总长度减去这个东西，如果有重复的话，这个长度应该是那个重复的字符串的长度，至于是不是我们只需要判断这个长度是否能整除总长度即可。

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 1000010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

char s[N];
int nxt[N],ans;

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    int tot=0;
    while(1){
        tot++;
        // printf("here
");
        cin>>(s+1);
        int len=strlen(s+1);
        if(len==1&&s[1]=='.') break;
        nxt[1]=0;
        for(int i=2,j=0;i<=len;i++){
            while(j>0&&s[j+1]!=s[i]){
                j=nxt[j];
            }
            if(s[j+1]==s[i]) j++;
            nxt[i]=j;
        }
        int ans;
        // printf("len:%d
",len);
        // printf("nxt:%d
",nxt[len]);
        if(len%(len-nxt[len])==0) ans=len/(len-nxt[len]);
        else ans=len;
        printf("%d
",ans);
    }
    return 0;
}

1.5 P2603 [ZJOI2008]无序运动

我们先不考虑翻转，先考虑其余的一些变换。不难发现，其余的变换都是相似的，也就是说，对应角相等，对应边成比例。我们考虑如何描述边与角。如果我们直接除的话会有精度，所以每相邻 (3) 个点我们用四个整数来表示，前两个整数用来表示边长平方的最简比是多少，后两个整数用来表示点积与叉积的最简比，带符号。然后我们用 AC 自动机跑匹配即可。

为了加快匹配速度，我们可以记一个 (last_k) 表示 (k) 这个节点一直跳 (fail) 跳到的第一个为结尾节点的点是哪一个。

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 200010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

inline int gcd(int a,int b){return b==0?a:gcd(b,a%b);}

struct node{
    int a,b,c,d;
    inline void Print(){printf("%d %d %d %d ",a,b,c,d);}
    inline node(){}
    inline node(int a,int b,int c,int d) : a(a),b(b),c(c),d(d) {}
    inline bool operator < (const node &q) const{
        if(a!=q.a) return a<q.a;
        else if(b!=q.b) return b<q.b;
        else if(c!=q.c) return c<q.c;
        else return d<q.d;
    }
};

struct Point{
    int x,y;
    inline Point(){}
    inline Point(int x,int y) : x(x),y(y) {}
    inline Point operator - (const Point &b) const{return Point(x-b.x,y-b.y);}
    inline void Intt(){read(x);read(y);}
};

inline int Dis(Point a,Point b){return (b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y);}

struct Vector{
    int x,y;
    inline Vector(){}
    inline Vector(int x,int y) : x(x),y(y) {}
    inline Vector(Point a) : x(a.x),y(a.y) {}
    inline int operator ^ (const Vector &b) const{return x*b.y-y*b.x;}
    inline int operator * (const Vector &b) const{return x*b.x+y*b.y;}
};

Point a[N];
node c[N<<2];
int n,m,ans[N],tail;
bool vis[N];

typedef map<node,int>::iterator it;
struct AC_automata{
    map<node,int> ch[N];
    int tot,fail[N],last[N],cnt[N];
    vector<int> end[N];
    inline AC_automata(){tot=0;}
    //Insert c
    inline void Insert(int n,int id){
        int p=0;
        for(int i=1;i<=n;i++){
            if(ch[p].find(c[i])==ch[p].end()) ch[p][c[i]]=++tot;
            p=ch[p][c[i]];
        }
        end[p].push_back(id);
    }
    inline void BuildFail(){
        queue<int> q;while(q.size()) q.pop();
        for(it i=ch[0].begin();i!=ch[0].end();i++) q.push(i->second);
        while(q.size()){
            int top=q.front();q.pop();
            for(it i=ch[top].begin();i!=ch[top].end();i++){
                int p=top,now=i->second;
                node c=i->first;
                p=fail[p];
                while(p&&ch[p].find(c)==ch[p].end()) p=fail[p];
                if(ch[p].find(c)!=ch[p].end()) p=ch[p][c];
                fail[now]=p;q.push(now);
                last[now]=end[p].empty()?last[p]:p;
            }
        }
    }
    inline void GetAns(int n){
        int now=0;
        for(int i=1;i<=n;i++){
            // printf("now:%d
",now);
            int p=now;
            while(p&&ch[p].find(c[i])==ch[p].end()) p=fail[p];
            // printf("p0:%d
",p);
            // c[i].Print();puts("");
            if(ch[p].find(c[i])!=ch[p].end()) p=ch[p][c[i]];
            // printf("now1:%d
",now);printf("p1:%d
",p);
            now=p;
            for(;p;p=last[p]) cnt[p]++;
            // printf("p:%d
",p);
        }
    }
    inline void FinaGetAns(){
        for(int i=1;i<=tot;i++){
            for(int j=0;j<end[i].size();j++){
                ans[end[i][j]]+=cnt[i];
                if(vis[end[i][j]]) ans[end[i][j]]/=2;
            }
        }
    }
    inline void Print(){
        printf("tot:%d
",tot);
        for(int i=1;i<=tot;i++){
            printf("i:%d fail:%d
",i,fail[i]);
        }
        for(int i=0;i<=tot;i++){
            printf("i:%d cnt:%d
",i,cnt[i]);
        }
    }
};
AC_automata ac;

inline void Print(){
    for(int i=1;i<=tail;i++) c[i].Print();puts("");
}

//change a[1,k] into an order c
inline void GetNewOrder(int k,int id){
    tail=0;vis[id]=1;
    for(int i=1;i<=k-2;i++){
        int len1=Dis(a[i],a[i+1]);
        int len2=Dis(a[i+1],a[i+2]);
        int g=gcd(len1,len2);len1/=g;len2/=g;
        int DotProduct=(Vector(a[i+2]-a[i+1])*Vector(a[i]-a[i+1]));
        int CrossProduct(Vector(a[i+2]-a[i+1])^Vector(a[i]-a[i+1]));
        g=gcd(abs(DotProduct),abs(CrossProduct));
        DotProduct/=g;CrossProduct/=g;
        c[++tail]=node(len1,len2,DotProduct,CrossProduct);
        if(CrossProduct) vis[id]=0;
    }
}

inline void intt(){
    read(n);read(m);
    for(int i=1;i<=m;i++){
        int k;read(k);
        for(int j=1;j<=k;j++) a[j].Intt();
        if(k<=2){
            if(k==1) ans[i]=n;else ans[i]=n-1;
            continue;
        }
        GetNewOrder(k,i);ac.Insert(tail,i);
    }
    ac.BuildFail();
    // ac.Print();
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    intt();
    // Print();
    for(int i=1;i<=n;i++) a[i].Intt();
    GetNewOrder(n,0);ac.GetAns(tail);
    // Print();ac.Print();
    for(int i=1;i<=n;i++) a[i].y*=-1;
    GetNewOrder(n,0);ac.GetAns(tail);
    // Print();ac.Print();
    ac.FinaGetAns();
    for(int i=1;i<=m;i++) printf("%d
",ans[i]);
    return 0;
}

1.6 Simpsons’ Hidden Talents

EXKMP 裸题。我们直接跑就可以。

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 50010
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> T Max(T a,T b){
    return a<b?b:a;
}

template<typename T> T Min(T a,T b){
    return a<b?a:b;
}

int nxt[N],extend[N],len1,len2;
char s1[N],s2[N];

inline void GetNext(){
    nxt[0]=len1;int now=0;
    while(s1[now]==s1[1+now]&&now+1<len1) now++;
    nxt[1]=now;
    int p0=1;
    for(int i=2;i<len1;i++){
        if(i+nxt[i-p0]<nxt[p0]+p0) nxt[i]=nxt[i-p0];
        else{
            int now=nxt[p0]+p0-i;
            now=Max(now,0);
            while(s1[now]==s1[i+now]&&now+i<len1) now++;
            nxt[i]=now;p0=i;
        }
    }
}

inline void GetZ(){
    GetNext();int now=0;
    while(s1[now]==s2[now]&&now<Min(len2,len1)) now++;
    extend[0]=now;
    int p0=0;
    for(int i=1;i<len2;i++){
        if(i+nxt[i-p0]<extend[p0]+p0) extend[i]=nxt[i-p0];
        else{
            int now=extend[p0]+p0-i;
            now=Max(now,0);
            while(s1[now]==s2[i+now]&&now<len1&&now+i<len2) now++;
            extend[i]=now;p0=i;
        }
    }   
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    ios::sync_with_stdio(false);cin.tie(0);
    while(cin>>s1>>s2){
        len1=strlen(s1);len2=strlen(s2);
        GetZ();
        // for(int i=0;i<len2;i++) printf("%d
",extend[i]);
        bool op=0;int ans;
        for(int i=0;i<len2;i++){
            if(extend[i]==len2-i){
                printf("%s %d
",s2+i,len2-i);
                op=1;break;
            }
        }
        if(!op) printf("0
");
        memset(nxt,0,sizeof(nxt));
        memset(extend,0,sizeof(extend));
    }
}

1.7 Problem M. Mediocre String Problem

链接

我们考虑这个串首先是基于 (s) 串中的一个回文串，然后我们把 (s) 翻转，跑一遍 EXKMP，拿到 extend 数组。然后我们枚举回文中心，统计 extend 的前缀和就可以。

代码：

#include<bits/stdc++.h>
#define dd double
#define ld long double
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define N 1000050
#define M number
using namespace std;

const int INF=0x3f3f3f3f;

template<typename T> inline void read(T &x) {
    x=0; int f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c == '-') f=-f;
    for(;isdigit(c);c=getchar()) x=x*10+c-'0';
    x*=f;
}

template<typename T> inline T Min(T a,T b){
    return a<b?a:b;
}

template<typename T> inline T Max(T a,T b){return a<b?b:a;}

char s[N],t[N];
int lens,lent,nxt[N],extend[N];
ll ans,sum[N];

inline void GetNext(){
    nxt[0]=lent;int len=0;int p0=1;
    while(len+1<lent&&t[len+1]==t[len]) len++;nxt[1]=len;
    for(int i=2;i<=lent-1;i++){
        if(i+nxt[i-p0]<p0+nxt[p0]) nxt[i]=nxt[i-p0];
        else{
            int now=p0+nxt[p0]-i;now=Max(now,0);
            while(now+i<lent&&t[now]==t[i+now]) now++;
            nxt[i]=now;p0=i;
        }
    }
}

inline void ExKmp(){
    int len=0;int p0=0;
    while(len<lens&&len<lent&&t[len]==s[len]) len++;extend[0]=len;
    for(int i=1;i<lens;i++){
        if(i+nxt[i-p0]<p0+extend[p0]) extend[i]=nxt[i-p0];
        else{
            int now=p0+extend[p0]-i;now=Max(now,0);
            while(now<lent&&now+i<lens&&t[now]==s[i+now]) now++;
            extend[i]=now;p0=i;
        }
    }
}

char Ma[N<<1];
int len[N<<1],Len;

inline void PreManacher(){
    for(int i=0;i<=(lens-1);i++){
        Ma[i<<1]='#';
        Ma[i<<1|1]=s[i];
    }
    Ma[lens<<1]='#';Len=lens<<1;
    // puts(Ma);
}

inline void Manacher(){
    PreManacher();
    int mid=0,maxright=0;
    for(int i=0;i<=Len;i++){
        if(i<maxright) len[i]=Min(len[(mid<<1)-i],len[mid]+mid-i);
        while(i-len[i]>=0&&Ma[i-len[i]]==Ma[i+len[i]]) len[i]++;
        if(maxright<len[i]+i){maxright=len[i]+i;mid=i;}
    }
}

inline int Ref(int x){
    if((x&1)==0) x--;return (x-1)/2;
}

inline ll GetSum(int l,int r){
    if(r<l) return 0;if(l<=0) return sum[r];return sum[r]-sum[l-1];
}

int main(){
    // freopen("my.in","r",stdin);
    // freopen("my.out","w",stdout);
    scanf("%s%s",s,t);lens=strlen(s);lent=strlen(t);
    reverse(s,s+lens);GetNext();ExKmp();Manacher();
    sum[0]=extend[0];for(int i=1;i<lens;i++) sum[i]=sum[i-1]+extend[i];
    // for(int i=0;i<lens;i++) printf("%d ",sum[i]);puts("");
    // for(int i=0;i<lens;i++) printf("%d ",extend[i]);puts("");
    // for(int i=0;i<=Len;i++) printf("%d ",len[i]);puts("");
    for(int i=0;i<=Len;i++){
        int l=-1,r=-1;
        if(Ma[i]=='#'){
            l=i+3,r=i+len[i];
            // if(i<=2) continue;
            r=Min(r,i<<1|1);r=Min(r,Len-1);
            l=Ref(l);r=Ref(r);
            ans=ans+GetSum(l,r);
        }
        else{
            l=i+2,r=i+len[i];
            // if(i<=1) continue;
            r=Min(r,i<<1|1);r=Min(r,Len-1);
            l=Ref(l);r=Ref(r);
            ans=ans+GetSum(l,r);
        }
        // printf("l:%d r:%d
",l,r);printf("%d
",GetSum(l,r));
        // printf("i:%d ans:%d
",i,ans);
    }
    printf("%lld
",ans);
    return 0;
}