The 16th Zhejiang Provincial Collegiate Programming Contest Sponsored by TuSimple

Problem A Vertices in the Pocket

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5989

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4100

Problem B Element Swapping

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5990

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4101

题意：数组a通过交换一对数字,得到了b数组,给出x=和y=和b数组,问有多少对l,r(l<=r)能满足条件

C++版本一

题解：规律+数学

1、；

2、

3、，则；

4、，则不合法数据；

5、，，则不合法数据；

6、，，对于某一个位置i，可以推出应该交换的位置，其中，不一定在范围内，不一定在范围内；

7、对于每个再完成上述操作后，放进vector；

8、可以查询vector是否操作 ,当然直接询问;

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=200000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r;
ll x,y;
ll ans,cnt,flag,temp,X,Y;
ll b[N];
vector<int>v[M];
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d%lld%lld",&n,&x,&y);
        X=Y=0;
        for(int i=1;i<=100000;i++)
            v[i].clear();
        for(int i=1;i<=n;i++){
            scanf("%lld",&b[i]);
            X+=i*b[i];
            Y+=i*b[i]*b[i];
        }
        //cout<<X<<" "<<Y<<endl;
        ll needx=x-X,needy=y-Y;
        ans=0;
        if(needx==0&&needy==0){//needx==0&&needy==0时，任意两个相同的元素都可以交换
            for(int i=1;i<=n;i++){
                ans+=v[b[i]].size();
                v[b[i]].push_back(i);
            }
        }else if(needx==0){
            ans=0;
        }else if(needy%needx==0){//needx和needy必须倍数关系
            //cout<<needx<<" "<<needy<<endl;
            ll need=needy/needx;
            //cout<<need<<endl;
            for(int i=1;i<=n;i++){
                if(need-2*b[i]&&1<=need-b[i]&&need-b[i]<=100000){
                    int j=i-needx/(need-2*b[i]);
                    vector<int>::iterator it=lower_bound(v[need-b[i]].begin(),v[need-b[i]].end(),j);
                    //cout<<need-b[i]<<" "<<i-needx/(need-2*b[i])<<endl;
                    if(it!=v[need-b[i]].end()&&*it==j){//it不能是end(),不然会段错误
                        ans++;
                    }
                }
                v[b[i]].push_back(i);
            }
        }
        cout<<ans<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

题解：

原博客 

#include<bits/stdc++.h>
#define ll long long 
#define Map map<ll,ll>::iterator
#define MAXN 100005
#define se second
using namespace std;
map<ll,ll>cnt;
ll X1,Y1,X2,Y2,a[MAXN];
int T,n;
int main(){
    cin>>T;
    while(T--){
        cnt.clear();
        scanf("%d%lld%lld",&n,&X1,&Y1);
        X2=Y2=0;
        for(ll i=1;i<=n;i++){
            scanf("%lld",&a[i]);
            cnt[a[i]]++;
            X2+=a[i]*i;Y2+=a[i]*a[i]*i;
        }
        ll dx=X2-X1,dy=Y2-Y1;
        if(dx==0){
            if(dy!=0){
                puts("0");continue;
            }
            ll ans=0;
            for(Map it=cnt.begin();it!=cnt.end();it++){
                ans+=((it->se)-1)*(it->se)/2;
            }
            printf("%lld\n",ans);
            continue;
        }
        if(dy%dx){
            puts("0");continue;
        }
        //cout<<dx<<" "<<dy<<endl;
        ll dt=dy/dx,ans=0;
        //cout<<dt<<endl;
        for(ll i=1;i<=n;i++){
            ll Aj=dt-a[i];
            if((Aj-a[i])==0)continue;
            ll j=(dx+(Aj-a[i])*i)/(Aj-a[i]);
            if(j<=i||j>n)continue;
            if(a[j]==Aj)ans++;
        }
        printf("%lld\n",ans);
    }
}

Problem C Array in the Pocket

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5991

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4102

Problem D Traveler

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5992

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4103

Problem E Sequence in the Pocket

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5993

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4104

题解：排序，查找有多少是不需要操作的

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N],b[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%d",&a[i]);
            b[i]=a[i];
        }
        sort(b+1,b+n+1);
        int pos=n;
        for(int i=n;i>=1;i--){
            if(a[i]==b[pos])
                pos--;
        }
        cout<<pos<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem F Abbreviation

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5994

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4105

题意：删去除第一个字符以外，所有的元音字母

题解：模拟 

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str[N];
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
    //scanf("%d",&n);
        cin>>str;
        string ans="";
        ans+=str[0];
        for(int i=1;str[i]!='\0';i++){
            if(str[i]=='a'||str[i]=='e'||str[i]=='i'||str[i]=='o'||str[i]=='u'||str[i]=='y')
                continue;
            ans+=str[i];
        }
        cout<<ans<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem G Lucky 7 in the Pocket

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5995

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4106

 题意：求大于等于n的最小可以被7整除不能被4整除的数

题解：预处理+二分

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    for(int i=1;i<1000;i++){
        if(i%7==0&&i%4!=0){
            a[++cnt]=i;
        }
    }
    //cout<<cnt<<endl;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        cout<<a[lower_bound(a+1,a+cnt+1,n)-a]<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem H Singing Everywhere

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5996

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4107

题意：至多删除一个点，使得破音数量最少

题解：前缀+后缀+枚举 

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
int a[N],pre[N],suf[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        memset(pre,0,sizeof(pre));
        memset(suf,0,sizeof(suf));
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        if(n<=2){
            cout<<0<<endl;
            continue;
        }
        for(int i=2;i<n;i++){
            pre[i]=pre[i-1]+(a[i-1]<a[i]&&a[i+1]<a[i]);
        }
        for(int i=n-1;i>1;i--){
            suf[i]=suf[i+1]+(a[i-1]<a[i]&&a[i+1]<a[i]);
        }

        ans=min(suf[2]-(a[1]<a[2]&&a[3]<a[2]),pre[n-1]-(a[n-2]<a[n-1]&&a[n]<a[n-1]));
        ans=min(ans,min(pre[n-3]+(a[n-3]<a[n-2]&&a[n]<a[n-2]),suf[4]+(a[1]<a[3]&&a[4]<a[3])));
        for(int i=3;i<=n-2;i++){
            //cout<<pre[i]<<" "<<suf[i]<<" "<<pre[i-2]+suf[i+2]+(a[i-2]<a[i-1]&&a[i+1]<a[i-1])+(a[i-1]<a[i+1]&&a[i+2]<a[i+1])<<endl;
            ans=min(ans,pre[i-2]+suf[i+2]+(a[i-2]<a[i-1]&&a[i+1]<a[i-1])+(a[i-1]<a[i+1]&&a[i+2]<a[i+1]));
        }
        cout<<min(ans,pre[n-1])<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem I Fibonacci in the Pocket

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5997

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4108

题意：求斐波那契数列区间[l，r]之和的奇偶性

题解： 规律

1、斐波那契数列奇偶性为 1 1 0 1 1 0 1 1 0 ......；

2、在区间，如果时为奇数，时为偶数；

3、询问一个数的余数=各位数字之和；

4、奇数-奇数=奇数，偶数-偶数=偶数，奇数-偶数=奇数，偶数-奇数=奇数；

5、询问和的奇偶性，不相同则1，相同则0；

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=100000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans,cnt,flag,temp,sum;
char a[N],b[N];
char str;
struct node{};
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        //scanf("%d",&n);
        cin>>a>>b;
        sum=0;
        ans=0;
        for(int i=0;a[i]!='\0';i++){
            sum+=a[i]-'0';
        }
        for(int i=0;b[i]!='\0';i++){
            ans+=b[i]-'0';
        }
        sum%=3;
        sum=(sum+2)%3;
        ans%=3;
        sum=sum==1;
        ans=ans==1;
        cout<<(ans!=sum)<<endl;
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem J Welcome Party

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=6000

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4109

题意：n个人参加会议，如果当参与者进入大厅时，如果他或她发现他或她的朋友都不在大厅中，那么即使他或她的朋友稍后将进入大厅，该参与者也会感到不快乐。求最小化不满意参与者数量，并给出一个入场顺序，如果存在多个答案，输出字典序最小的顺序

题解：并查集+优先队列

不要用memset，TLE警告

C++版本一

链式向前星边存

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans[N],cnt,flag,temp,sum;
int vis[N],pre[N],head[N];
char str;
struct node{};
struct Edge {
    int to;
    int next;
} edge[N * 2];
int cnt_edge = 0;
void add_edge(int from, int to)
{
    edge[cnt_edge].to = to;
    edge[cnt_edge].next = head[from];
    head[from] = cnt_edge++;
}
int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);}
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            vis[i]=0;
            head[i]=-1;
            pre[i]=i;//G[i].clear();
        }
        cnt=0;sum=0;
        while(!q.empty()){
            q.pop();
        }
        //memset(vis,0,sizeof(vis));
        //memset(head, -1, sizeof(head));
        cnt_edge = 0;
        //memset(pre,0,sizeof(pre));
        while(m--){
            scanf("%d%d",&u,&v);
            //G[u].push_back(v);
            //G[v].push_back(u);
            add_edge(u,v);
            add_edge(v,u);
            int tu=find(u);
            int tv=find(v);
            if(tu!=tv){
                if(tu<tv)
                    pre[tv]=tu;
                else
                    pre[tu]=tv;
            }
        }
        for(int i=1;i<=n;i++){
            if(pre[i]==i){
                sum++;
                q.push(i);
                vis[i]=1;
            }
        }



        while(!q.empty()){
            int u=q.top();
            q.pop();
            ans[++cnt]=u;
            for(int i=head[u];~i;i=edge[i].next){
                int v=edge[i].to;
                if(vis[v]==0){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
        cout<<sum<<endl;
        for(int i=1;i<=n;i++)
            printf("%d%c",ans[i]," \n"[i==n]);
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

 C++版本二

vector边存

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=1000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
int ans[N],cnt,flag,temp,sum;
int vis[N],pre[N];
char str;
struct node{};
vector<int>G[N];
int find(int x){return pre[x]==x?x:pre[x]=find(pre[x]);}
priority_queue<int,vector<int>,greater<int> >q;
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    //cout.tie(0);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;i++){
            vis[i]=0;
            pre[i]=i;
            G[i].clear();
        }
        cnt=0;sum=0;
        while(!q.empty()){
            q.pop();
        }
        while(m--){
            scanf("%d%d",&u,&v);
            G[u].push_back(v);
            G[v].push_back(u);
            int tu=find(u);
            int tv=find(v);
            if(tu!=tv){
                if(tu<tv)
                    pre[tv]=tu;
                else
                    pre[tu]=tv;
            }
        }
        for(int i=1;i<=n;i++){
            if(pre[i]==i){
                sum++;
                q.push(i);
                vis[i]=1;
            }
        }
        while(!q.empty()){
            int u=q.top();
            q.pop();
            ans[++cnt]=u;
            for(int i=0,j=G[u].size();i<j;i++){
                int v=G[u][i];
                if(vis[v]==0){
                    vis[v]=1;
                    q.push(v);
                }
            }
        }
        cout<<sum<<endl;
        for(int i=1;i<=n;i++)
            printf("%d%c",ans[i]," \n"[i==n]);
    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

Problem K Strings in the Pocket

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5998

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4110

题意：反转某一个区间的子字符串，使得两个字符串相同

题解：

1、判断两个字符串是否完全相同；

2、完全相同则Manacher's Algorithm求回文字符串数量；

3、不完全相同则分别从头从尾至不相同得到区间[l，r],反转这个区间判断是否和另一个字符串相同；

4、3中不相同则ans==0；

5、3中相同则同时向两边扩张，条件是同时加1，并且相同

C++版本一

/*
*@Author:   STZG
*@Language: C++
*/
#include <bits/stdc++.h>
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<string>
#include<vector>
#include<bitset>
#include<queue>
#include<deque>
#include<stack>
#include<cmath>
#include<list>
#include<map>
#include<set>
//#define DEBUG
#define RI register int
#define endl "\n"
using namespace std;
typedef long long ll;
//typedef __int128 lll;
const int N=2000000+10;
const int M=100000+10;
const int MOD=1e9+7;
const double PI = acos(-1.0);
const double EXP = 1E-8;
const int INF = 0x3f3f3f3f;
int t,n,m,k,p,l,r,u,v;
ll ans,cnt,flag,temp,sum;
char a[N],b[N];
int P[N<<1];
char str;
struct node{};
ll Manacher(string s)
{
    /*改造字符串*/
    string res="$#";
    for(int i=0;i<s.size();++i){
        res+=s[i];
        res+="#";
    }
    /*数组*/
    ll ans=0;
    int mi=0,right=0;   //mi为最大回文串对应的中心点，right为该回文串能达到的最右端的值
    for(int i=1;i<res.size();++i){
        P[i]=right>i ?min(P[2*mi-i],right-i):1;     //关键句，文中对这句以详细讲解
        while(res[i+P[i]]==res[i-P[i]])
            ++P[i];
        if(right<i+P[i]){    //超过之前的最右端，则改变中心点和对应的最右端
            right=i+P[i];
            mi=i;
        }
        ans+=P[i]/2;
    }
    return ans;
}
int main()
{
#ifdef DEBUG
	freopen("input.in", "r", stdin);
	//freopen("output.out", "w", stdout);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    //cout.tie(0);
    //scanf("%d",&t);
    cin>>t;
    while(t--){
        //scanf("%s%s",a,b);
        cin>>a>>b;
        int len=strlen(a);
        for(l=0;l<len&&a[l]==b[l];l++);
        for(r=len-1;r>=0&&a[r]==b[r];r--);
        if(l>r){
            cout<<Manacher(a)<<endl;
        }else{
            flag=1;
            for(int i=l;i<=r;i++){
                if(a[i]!=b[r-i+l]){
                    flag=0;
                    break;
                }
            }
            if(flag){
                ans=1;
                while(l-1>=0&&r+1<=len-1&&a[l-1]==a[r+1])ans++,l--,r++;
                cout<<ans<<endl;
            }else{
                cout<<0<<endl;
            }
        }

    }

#ifdef DEBUG
	printf("Time cost : %lf s\n",(double)clock()/CLOCKS_PER_SEC);
#endif
    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

原博客

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
using namespace std;
const int N=2e6+50;
char s1[N],s2[N],s[N*2];
int len[N*2];
int mi(int a,int b){
    if(a<b) return a;
    return b;
}
int main(){
    int t,i,n,k,p,ma;
    scanf("%d",&t);
    while(t--){
        scanf("%s%s",s1+1,s2+1);
        n=strlen(s1+1);
        k=1;
        for(i=1;i<=n;i++) if(s1[i]!=s2[i]) k=0;
        if(k){
            for(i=1;i<=n+1;i++){
                s[i*2]=s1[i];
                s[i*2-1]='*';
            }
            s[0]='#';
            p=ma=0;
            long long ans=0;
            for(i=1;i<=2*n;i++){
                if(ma>i) len[i]=mi(ma-i,len[2*p-i]);
                else len[i]=1;
                while(s[i+len[i]]==s[i-len[i]]) len[i]++;
                if(ma<len[i]+i){
                    ma=len[i]+i;
                    p=i;
                }
                ans+=len[i]/2;
            }
            printf("%lld\n",ans);
        }
        else{
            int l=1,r=n,ans=1;
            while(s1[l]==s2[l]) l++;
            while(s1[r]==s2[r]) r--;
            for(i=l;i<=r;i++) if(s1[i]!=s2[r-(i-l)]) ans=0;
            if(ans==0) printf("0\n");
            else{
                ma=1;
                while(l-ma>=1&&r+ma<=n&&s1[l-ma]==s1[r+ma]) ma++;
                printf("%d\n",ma);
            }
        }
    }
    return 0;
}
 
 

Problem L Square on the Plane

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=5999

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4111

Problem M Trees in the Pocket

比赛地址：http://acm.zju.edu.cn/onlinejudge/showContestProblem.do?problemId=6001

补题地址： http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=4112