6.21 冲刺国赛模拟 22
T1 跳跃
不妨看作两只青蛙从相同起点出发且跳跃次数相同，设 \(f_{i,j,k}\) 为两只青蛙分别在 \(i,j\) 位置，且相差步数 \(k\)。由于需要记录相邻位置对答案贡献，我们在要求必须严格按照升序对处理状态，也就是必须保证当前跳跃的一只青蛙落点在另一只青蛙更前面，且靠后的青蛙可以也可以一步跳到或跳过靠前的一只，也就是 \(0\le i-j\le B\)。
考虑优化，设 \(i=a_i\times A+b_i\times B+C,j=a_j\times A+B_j\times B+C\)，如果已知 \(i,a_i,a_j\)，再结合 \(0\le i-j=(a_i-a_j)\times A+(b_i-b_j)\times B\le B\) 的特殊性质，就能计算出 \(i,j\)，不放修改状态为 \(f_{i,j,k}\) 表示靠前的青蛙在 \(i\) 位置，其中两只青蛙分别跳 \(A\) \(j\) 或 \(k\) 次的最大答案。同时发现直接模 \(B\) 就是 \(i-j\)，而对于 \(i-j=B\) 的情况，发现这个时候 \(j\) 由 \(i-B\) 到 \(i\) 是去到了两个去过的地方且 \(j,k\) 的值也没改变，所以不用考虑。
再优化，注意到 \(j,k\) 的用处实际是作为 \(j-k\) 整体，所以把状态改成 \(f_{i,j}\) 后者表示 \(a_i\) 与 \(a_j\) 的差，这样转移即可。
同时存在 \(i\) 不变，\(j\) 先跳到 \(i\) 然后再跳到后面的位置，因此第二维不能完全按下标顺序转移，需要把 \(i=j\) 的情况放最后。
点击查看代码
int n,A,B;
int c[maxn];
int f[maxn][maxw<<1];
vector<int> V;
int main(){
freopen("jump.in","r",stdin);
freopen("jump.out","w",stdout);
n=read(),A=read(),B=read();
for(int i=1;i<=n;++i) c[i]=read();
memset(f,~0x3f,sizeof(f));
for(int i=1;i<=B;++i) f[i][maxw]=0;
for(int i=1;i<=A;++i) f[i-A+B][-1+maxw]=((i-A+B)-i)*(c[i-A+B]^c[i]);
for(int i=1,j;i<=n;++i){
V.clear();
for(int k=-i/A-1;k<=i/A+1;++k){
//i-j=(ai-aj)A+(bi-bj)B<=B
j=i-(k*A%B+B)%B;
if(i==j){
V.push_back(k);
continue;
}
if(i+A<=n&&j+B>=i+A){
f[i+A][k+1+maxw]=max(f[i+A][k+1+maxw],f[i][k+maxw]+(i+A-i)*(c[i+A]^c[i]));
}
if(j+A<=n&&j+A>=i){
f[j+A][-k+1+maxw]=max(f[j+A][-k+1+maxw],f[i][k+maxw]+(j+A-i)*(c[j+A]^c[i]));
}
if(j+B<=n&&j+B>=i){
f[j+B][-k+maxw]=max(f[j+B][-k+maxw],f[i][k+maxw]+(j+B-i)*(c[j+B]^c[i]));
}
}
for(int k:V){
if(i+A<=n){
f[i+A][k+1+maxw]=max(f[i+A][k+1+maxw],f[i][k+maxw]+(i+A-i)*(c[i+A]^c[i]));
f[i+A][-k+1+maxw]=max(f[i+A][-k+1+maxw],f[i][k+maxw]+(i+A-i)*(c[i+A]^c[i]));
}
if(i+B<=n){
f[i+B][k+maxw]=max(f[i+B][k+maxw],f[i][k+maxw]+(i+B-i)*(c[i+B]^c[i]));
f[i+B][-k+maxw]=max(f[i+B][-k+maxw],f[i][k+maxw]+(i+B-i)*(c[i+B]^c[i]));
}
}
}
printf("%d\n",f[n][maxw]);
return 0;
}
6.22 冲刺国赛模拟 23
T1 無言
容易发现编号相对应的去填是不劣的，于是一个球以其到对应位置的距离为半径，两侧的所有坑都要先被填满，相当于是一个区间对单点连边，进行拓扑排序。优化使用线段树优化建图。
点击查看代码
int n;
int a[maxn],b[maxn];
struct edge{
int to,nxt;
}e[maxm];
int head[maxn*5],cnt;
int deg[maxn*5];
inline void add_edge(int u,int v){
e[++cnt].to=v,e[cnt].nxt=head[u],head[u]=cnt;
++deg[v];
}
queue<int> q;
ll ans;
int tot;
int pos[maxn];
map<int,int> mp;
struct SegmentTree{
#define mid ((l+r)>>1)
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
void build(int rt,int l,int r){
tot=max(tot,rt);
if(l==r){
pos[l]=rt;
mp[rt]=l;
return;
}
add_edge(rt<<1,rt),add_edge(rt<<1|1,rt);
build(lson),build(rson);
}
void update(int rt,int l,int r,int pl,int pr,int p){
if(pl<=l&&r<=pr){
add_edge(rt,p);
return;
}
if(pl<=mid) update(lson,pl,pr,p);
if(pr>mid) update(rson,pl,pr,p);
}
#undef mid
#undef lson
#undef rson
}S;
int main(){
freopen("nameless.in","r",stdin);
freopen("nameless.out","w",stdout);
n=read();
for(int i=1;i<=n;++i) a[i]=read();
for(int i=1;i<=n;++i) b[i]=read();
S.build(1,1,n);
for(int i=1;i<=n;++i){
int dis=abs(a[i]-b[i]);
ans+=dis;
if(a[i]<b[i]){
//to left
int l=i+1,r=lower_bound(a+1,a+n+1,2*b[i]-a[i])-a-1;
if(r==i) continue;
S.update(1,1,n,l,r,pos[i]);
}
else{
//to right
int l=lower_bound(a+1,a+n+1,2*b[i]-a[i])-a,r=i-1;
if(l==i) continue;
S.update(1,1,n,l,r,pos[i]);
}
}
printf("%lld\n",ans);
for(int i=1;i<=tot;++i){
if(!deg[i]) q.push(i);
}
while(!q.empty()){
int u=q.front();
q.pop();
if(mp.count(u)) printf("%d ",mp[u]);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
--deg[v];
if(!deg[v]) q.push(v);
}
}
printf("\n");
return 0;
}
T2 排列
\(k\) 有一个 \(\log\) 的限制，所以考虑倍增之类的做法，设 \(f_{i,j}\) 表示第 \(i\) 个排列中 \(j\) 置换到的数，那么可以以 \(f_{i,j}=j+2^{i-1}\) 为定义，如果是 \(f\) 的逆，那就是减去 \(2^{i-1}\)，所以我们进行 \(k\) 次操作得到的应该是 \(\sum_{i=1}^k a_i2^{i-1}\)，其中 \(a_i=\pm 1\)，这样是可以取到所有 \((-2^k,2^k)\) 的奇数的，由于答案对 \(n\) 取模，且 \(2^k\ge n\)，那么当 \(n\) 为奇数时，取模后可以取遍所有的数。
在此基础上考虑 \(n\) 是偶数，实际上从 \(x\) 到 \(y\) 在模意义下理论上最多只要增加或减少 \(\dfrac{n}{2}\) 就可以了，那么我们可以舍弃前两次置换来让 \(n\) 是偶数时成立。
注意到 \(n=2\) 是一定不行的，如果我们把 \(4\) 个相邻划为一组，那么需要奇偶性两个改变两个不变，同时需要其本身发生相对位置变化，从而求逆时变成另两个改变，这个时候 \((0,1,2,3)\) 变为 \((2,3,1,0)\) 即可，此时 \(0,1\) 奇偶性改变，且位置改变，这样求逆就是 \(2,3\) 奇偶性改变了，这就是 \(n\) 是 \(4\) 的倍数的情况。最后一种把最后 \(6\) 个划为一组，第一个排列对前 \(4\) 个做，第二个对后 \(4\) 个做就行了。
点击查看代码
int n,k;
int main(){
freopen("permutation.in","r",stdin);
freopen("permutation.out","w",stdout);
n=read();
if(n==1) return printf("1\n0\n"),0;
else if(n==2) return printf("-1\n"),0;
k=__lg(n-1)+2;
printf("%d\n",k);
if(n&1){
for(int i=1;i<=k;++i){
for(int j=0;j<n;++j){
printf("%d ",(j+(1<<i-1))%n);
}
printf("\n");
}
}
else if(n%4==0){
for(int j=0;j<n;++j){
if(j%4<=1) printf("%d ",j+2);
else if(j%4==2) printf("%d ",j-1);
else printf("%d ",j-3);
}
printf("\n");
for(int i=1;i<k;++i){
for(int j=0;j<n;++j){
printf("%d ",(j+(1<<i-1))%n);
}
printf("\n");
}
}
else{
for(int j=0;j<n-2;++j){
if(j%4<=1) printf("%d ",j+2);
else if(j%4==2) printf("%d ",j-1);
else printf("%d ",j-3);
}
printf("%d %d\n",n-2,n-1);
for(int j=0;j<n-4;++j) printf("%d ",j);
printf("%d %d %d %d\n",n-2,n-1,n-3,n-4);
for(int i=1;i<k-1;++i){
for(int j=0;j<n;++j){
printf("%d ",(j+(1<<i-1))%n);
}
printf("\n");
}
}
return 0;
}