B.Up the Strip
题目链接
简要题解
我们可以自然地设出状态\(F[i]\)，表示有多少种方案能移动到\(i\)。
假设我们现在已经得到了\(F[i]\)的值，考虑从\(i\)处继续往下走。
对于第一种操作，实际上是将\(F[1]\)~\(F[i-1]\)全部加上\(F[i]\)，我们可以用一个维护差分的树状数组来实现。
对于第二种操作，对于每一个\(i\)，大约可以转移给\(\sqrt{i}\)个数，显然是不能暴力转移的。
我们倒过来想，对于一个\(i\)，有哪些数可以通过第二种操作转移到它，那么我们枚举\(j\)，满足\(\lfloor\frac{x}{j}\rfloor=i\)的\(x\)一定是一段连续区间。
我们枚举\(j\)，算出对应区间的贡献和，这也可以用树状数组实现。
不难发现，枚举\(j\)的复杂度是\(O(n*logn)\)的，因此总复杂度为\(O(n*log^2n)\)
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=4e6+10;
int n,Mod,F1[MAXN],F2[MAXN];
int Read()
{ int a=0,c=1; char b=getchar();
while(b!=‘-‘&&(b<‘0‘||b>‘9‘)) b=getchar();
if(b==‘-‘) c=-1,b=getchar();
while(b>=‘0‘&&b<=‘9‘) a=a*10+b-48,b=getchar();
return a*c;
}
int Min(int A,int B){ return A<B?A:B; }
int Lowbit(int K){ return K&(-K); }
int Add(int A,int B){ return A+=B,A>=Mod?A-Mod:A; }
void Modify(int *F,int Np,int Num){ while(Np<=n) F[Np]=Add(F[Np],Num),Np+=Lowbit(Np); }
int Query(int *F,int Np)
{ int Ret=0;
while(Np>=1) Ret=Add(Ret,F[Np]),Np-=Lowbit(Np);
return Ret;
}
int main()
{ scanf("%d%d",&n,&Mod),F1[n]=1;
for(int i=n,Nv=0;i>=1;i--)
{ for(int j=2,Le,Ri;i*j<=n;j++)
Le=i*j,Ri=Min(n,Le+j-1),Nv=Add(Nv,Add(Query(F2,Ri),Mod-Query(F2,Le-1)));
Nv=Add(Nv,Query(F1,i)),Modify(F1,1,Nv),Modify(F1,i,Mod-Nv),Modify(F2,i,Nv),Nv=0;
}
printf("%d\n",F2[1]);
}
C.Bottom-Tier Reversals
题目链接
简要题解
我们需要把整个序列排序，由于每次只能翻转前缀，因此一定是把元素从后往前依次归位。
由于只能翻转奇数长度的前缀，所以奇数位上的数不能移到偶数位上，反之亦然。
那么若奇数位上存在偶数，或者偶数位上存在奇数，就一定无法还原序列。
接下来讨论从后往前还原序列，假设当前需要还原第\(i\)位和第\(i-1\)位，其中\(i\)是奇数。
我们设当前第\(i\)个位置上的数为\(b_i\)，那么有以下几种情况：
\(Case 1:i,i-1,...,b_i,i+1,i+2,...,n\)
????我们只需要将前\(i\)个位置翻转即可还原\(i\)和\(i-1\)，总共\(1\)步还原。
\(Case 2:b_1,b_2,...,i-1,i,...,b_i,i+1,i+2,...,n\)
????我们只需要将以\(i\)为结尾的前缀翻转即可变成\(Case1\)的情况，总共\(2\)步还原。
\(Case 3:b_1,b_2,...,i,i-1,...,b_i,i+1,i+2,...,n\)
????我们只需要将任意一个包含\(i\)和\(i-1\)的前缀翻转即可变成\(Case2\)的情况，总共\(3\)步还原。
\(Case 4:i,b_2,...,i-1,...,b_i,i+1,i+2,...,n\)
????我们只需要将\(i-1\)前面的位置翻转即可变成\(Case3\)的情况，总共\(4\)步还原。
\(Case 5:b_1,b_2,...,i-1,...,i,...,b_i,i+1,i+2,...,n\)
????我们只需要将以\(i\)为结尾的前缀翻转即可变成\(Case4\)的情况，总共\(5\)步还原。
\(Case 6:b_1,b_2,...,i,...,i-1,...,b_i,i+1,i+2,...,n\)
????我们只需要将以\(i\)为结尾的前缀翻转即可变成\(Case4\)的情况，总共\(5\)步还原。
可以发现，我们至多花五步就可以还原两个位置，因此在\(\frac{5}{2}\)步内一定可以还原整个序列。
可以直接暴力翻转，时间复杂度\(O(n^2)\)
代码如下：
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int MAXN=2050;
int T,n,Flag,A[MAXN];
vector<int>Ans;
void Solve(int Lp,int Rp,int Aim)
{ if(Rp==Aim&&Lp==Aim-1) return ;
if(Rp==1&&Lp==2) return reverse(A+1,A+Aim+1),Ans.pb(Aim);
if(Rp==Lp+1) return reverse(A+1,A+Rp+1),Ans.pb(Rp),Solve(2,1,Aim);
if(Lp==Rp+1)
{ int Nt=Lp+1;
for(int i=Nt;i<=Aim;i+=2)
if(A[i+1]==A[1]-1) Nt=i;
return reverse(A+1,A+Nt+1),Ans.pb(Nt),Solve(Nt-Lp+1,Nt-Rp+1,Aim);
}
if(Rp==1) return reverse(A+1,A+Lp),Ans.pb(Lp-1),Solve(Lp,Lp-1,Aim);
if(Rp>Lp) reverse(A+1,A+Rp+1),Ans.pb(Rp),Solve(Rp-Lp+1,1,Aim);
if(Rp<Lp) reverse(A+1,A+Rp+1),Ans.pb(Rp),Solve(Lp,1,Aim);
}
int main()
{ for(scanf("%d",&T);T;T--)
{ scanf("%d",&n),Flag=0,Ans.clear();
for(int i=1;i<=n;i++) scanf("%d",&A[i]),Flag|=(A[i]^i)&1;
if(Flag){ puts("-1"); continue ; }
for(int i=n,Lp,Rp;i>=2&&!Flag;i-=2)
{ for(int j=1;j<=i;j++) A[j]==i-1?Lp=j:0,A[j]==i?Rp=j:0;
Solve(Lp,Rp,i);
}
if(Flag||Ans.size()>5*n/2){ puts("-1"); continue ; }
printf("%d\n",Ans.size());
for(int v:Ans) printf("%d ",v);
if(Ans.size()) puts("");
}
}