切了 D 但不会 C，使我的大脑旋转。
A
进行一个分类讨论。
- 如果序列是有序的，答案自然为 \(0\)。
- 如果存在 \(i\) 使得 \(p_i = i\) 且 \(i\) 之前的数全小于 \(i\)，那么答案为 \(1\)，否则答案显然大于 \(1\)。
- 如果 \(p_1 \ne n\)，那么答案等于 \(2\)，先后对 \(1\) 和 \(n\) 操作即可，\(p_n \ne 1\) 时同理。
- 如果 \(p_1 = n\) 且 \(p_n = 1\) 那么答案等于 \(3\)，显然可以在中间任意处操作使得其变为上面一种情况，并且不可能变为答案为 \(1\) 的情况，因为一次操作后 \(1\) 必然还在 \(n\) 右边。
代码
#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
const int N=2e5+5;
int T,n,cnt;
int p[N],vis[N];
signed main(){
rd(T);
while(T--){
rd(n);cnt=0;
int now=1,ans=0;
for(int i=1;i<=n;i++)rd(p[i]),vis[i]=0;
if(is_sorted(p+1,p+n+1)){
printf("0\n");
continue;
}
for(int i=1;i<=n;i++){
if(now==i&&i==p[i]){
ans=1;
break;
}
vis[p[i]]=1;
while(vis[now])++now;
}
if(ans){
printf("1\n");
continue;
}
if(p[1]==n&&p[n]==1)printf("3\n");
else printf("2\n");
}
return 0;
}
B
又是分讨。
注意到答案只和 01 串中 \(0\) 和 \(1\) 的数量有关，和其排列顺序无关。
设四个数量分别为 \(x_0,y_0,x_1,y_1\)。
- 若 \(x_0 = y_0\) 显然正确，\(T\) 取空串即可。
- 否则，若 \(x_1 = y_1\) 显然错误。
- 若 \((x_0,x_1),(y_0,y_1)\) 构成偏序关系，显然错误，因为 \(len\) 一定不相等。
- 以上情况都不符合时，会形成一个 “\(a\) 个 \(S\) 等于 \(b\) 个 \(T\)”的关系，使用 KMP 或 Hash 求出 \(S\) 的最小周期，看看是否整除即可。
代码
#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
const int N=5e5+5;
int T,nxt[N];
char s[N],x[N],y[N];
signed main(){
rd(T);
while(T--){
scanf("%s",s+1);
scanf("%s",x+1);
scanf("%s",y+1);
int xN=strlen(x+1),yN=strlen(y+1);
int cntx0=0,cntx1=0,cnty0=0,cnty1=0,yS,yT;
for(int i=1;i<=xN;i++){
if(x[i]=='0')cntx0++;
else cntx1++;
}
for(int i=1;i<=yN;i++){
if(y[i]=='0')cnty0++;
else cnty1++;
}
yS=abs(cntx0-cnty0);
yT=abs(cntx1-cnty1);
if(!yT&&yS)printf("No\n");
else if(!yT&&!yS)printf("Yes\n");
else if(yT&&!yS)printf("Yes\n");
else{
if(cntx0>cnty0&&cntx1>cnty1)printf("No\n");
else if(cntx0<cnty0&&cntx1<cnty1)printf("No\n");
else{
int sN=strlen(s+1),p=0;int r=sN;
for(int i=2;i<=sN;i++){
while(p&&s[p+1]!=s[i])p=nxt[p];
if(s[p+1]==s[i])++p;
nxt[i]=p;
}
if(sN%(sN-nxt[sN])==0)r=sN-nxt[sN];
if(1ll*yS*(sN/r)%yT==0)printf("Yes\n");
else printf("No\n");
}
}
}
return 0;
}
C
神必构造题。
结论：设 \(rkp_i\) 和 \(rkq_i\) 代表 \(i\) 位置的排名。那么给 \(rkp_i + rkq_j > n\) 的 \((i,j)\) 位置赋 \(1\) 即可。
结论我没想出来，但证明还是很简单的。读者自证不难。
代码
#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
int n,x,p[505],q[505];
signed main(){
rd(n);
for(int i=1;i<=n;i++)rd(x),p[x]=i;
for(int i=1;i<=n;i++)rd(x),q[x]=i;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)
printf("%d",(p[i]+q[j]>n));
printf("\n");
}
return 0;
}
D
题目大意：一个排列，每次对一个前缀进行一次冒泡排序，并询问一次全局逆序对数量。
设 \(r_i\) 为数字 \(i\) 前面比它大的数字数量，显然总逆序对数为 \(\sum{r_i}\)。
每对一个前缀进行一次冒泡排序，对于 \(r_{p_i} = 0\) 的位置，它前面的数字都比它小，不会交换到前面，而它本身也不会和后面比她大的数字交换，因此 \(r_{p_i}\) 还是为 \(0\)。
对于 \(r_{p_i} > 0\) 的位置， 只会有前面最大的和她交换，因此 \(r_{p_i}\) 减 \(1\)。
用树状数组直接维护即可。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
const int N=2e5+5;
int n,m,a[N],p[N],v[N];
namespace BIT1{
int t[N];
inline void Add(int x,int v){while(x<=n)t[x]+=v,x+=x&-x;}
inline int Query(int x){int ans=0;while(x)ans+=t[x],x-=x&-x;return ans;}
}
namespace BIT2{
int t[N<<1];
inline void Add(int x,int v){while(x<=n+m)t[x]+=v,x+=x&-x;}
inline int Query(int x){int ans=0;while(x)ans+=t[x],x-=x&-x;return ans;}
}
signed main(){
rd(n);for(int i=1;i<=n;i++)rd(p[i]);
rd(m);for(int i=1;i<=m;i++)rd(a[i]);
int ans=0;
for(int i=1;i<=n;i++){
BIT1::Add(p[i],1);
v[i]=i-BIT1::Query(p[i]);
ans+=v[i];
}
int now=0,tag=0;
for(int i=1;i<=m;i++){
while(now<a[i]){
++now;
if(v[now]+tag==0)continue;
BIT2::Add(v[now]+tag,1);
}
++tag;
ans-=BIT2::Query(n+m)-BIT2::Query(tag-1);
printf("%lld\n",ans);
}
return 0;
}