这周比赛十分弱鸡，题目难度比较高，所以分数比较绝望

T2:

发现两个字符串的本质是相同的

于是可以把他们都用“最小表示法”来表示出来

然后判断是否相同即可

code:

#include<bits/stdc++.h>
using namespace std;
char a[1000010],b[1000010];
int solve(char s[]){
    int len=strlen(s+1);
    for(int i=1;i<=len;i++) s[len+i]=s[i];
    int i=1,j=2,k=0;
    while(i<=len&&j<=len){
        for(k=0;k<=len&&s[i+k]==s[j+k];k++);
        if(k==len) break;
        if(s[i+k]>s[j+k]){
            i+=k+1;
            if(i==j) i++;
        }
        else{
            j+=k+1;
            if(i==j) j++;
        }
    }
    return min(i,j);
}
int main(){
    scanf("%s%s",a+1,b+1);
    int la=strlen(a+1),lb=strlen(b+1);
    int x=solve(a),y=solve(b);
    a[la+x]=b[lb+y]=0;
    if(la==lb&&!strcmp(a+x,b+y)){
        puts("Yes");
        printf("%s",a+x);
    }
    else puts("No");
    return 0;
}

T3:

我们发现2^k步之后，每个硬币的状态之和离他2^k远的硬币有关

于是用一种二进制拆解的方法，把T拆开，然后做，复杂度O(nlog(T))

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int f[2][1000010];
int x=1,y,n,flag;
ll T;
ll get(ll mx){
    ll ans=2;
    while(ans<=mx) ans<<=1;
    ans>>=1;
    return ans;
}
int main(){
    scanf("%d%lld",&n,&T);
    for(int i=0;i<n;i++)scanf("%d",&f[0][i]);
    flag=T%2;
    T>>=1;
    while(T){
        ll t=get(T);
        T-=t;
        for(int i=0;i<n;i++)f[x][i]=(f[y][(i+n-t%n)%n]!=f[y][(i+t)%n])+1;
        swap(x,y);
    }
    if(flag){
        f[y][n]=f[y][0];
        for(int i=0;i<n;i++) printf("0 %d ",(f[y][i]!=f[y][i+1])+1);
    }
    else for(int i=0;i<n;i++) printf("%d 0 ",f[y][i]);
    return 0;
}

T4：

玄学做法

code:

#include<bits/stdc++.h>
using namespace std;
int n,b;
int a[100010];
int ans,pos,cnt;
int l[200010],r[200010];
int main(){
    scanf("%d%d",&n,&b);
    l[n]=r[n]=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]==b) pos=i,a[i]=0;
        if(a[i]<b) a[i]=-1;
        if(a[i]>b) a[i]=1; 
    }
    cnt=n;
    for(int i=pos-1;i>=1;i--) cnt+=a[i],l[cnt]++;
    cnt=n;
    for(int i=pos+1;i<=n;i++) cnt+=a[i],r[cnt]++;
    for(int i=0;i<=2*n;i++) ans+=l[i]*r[2*n-i];
    printf("%d",ans);         
    return 0;
}

T5:

我们可以利用DP的思想，设l[i]表示i左边第一个比h[i]高的下标

r[i]表示i右边第一个比h[i]高的下标

如果两个点可以看到，那么其中必定有一个矮的（或者同高）

于是我们枚举一个i，然后发现l[i]-r[i]这段区间中i只能够和l[i]与r[i]连接，并且不能连接到l[i]-r[i]以外

注意要判断l[i]是否和r[i]相等

code:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,a[1000010];
int pos,b[1000010];
int same[1000010],maxn=-1;
int r[1000010],l[1000010];
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&a[i]);
        if(a[i]>maxn){
            maxn=a[i];
            pos=i;
        }
    }
    for(int i=0;i<n;i++) b[i]=a[(pos+i)%n];
    b[n]=a[pos];
//    for(int i=0;i<n;i++) printf("%d ",b[i]);
    for(int i=n-1;i>=0;i--){
        r[i]=i+1;
        while(r[i]<n&&b[i]>b[r[i]]) r[i]=r[r[i]];
        while(r[i]<n&&b[i]==b[r[i]]){
            same[i]=same[r[i]]+1;
            r[i]=r[r[i]];
        }
    }
    for(int i=0;i<n;i++){
        l[i]=i-1;
        while(l[i]>0&&b[i]>=b[l[i]]) l[i]=l[l[i]];
    }
    ll ans=0;
    for(int i=0;i<n;i++){
        ans+=same[i];
        if(b[i]<b[0]){
            if(l[i]==0&&r[i]==n) ans++;
            else ans+=2;
        }
    }
    printf("%lld",ans);
    return 0;
}