这周比赛十分弱鸡，题目难度比较高，所以分数比较绝望
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;
}
