P9951 [USACO20FEB] Swapity Swap B 题解

ymyctsz · 2024-01-13 21:20:47 · 题解

题目

模拟题。

暴力 58，试过了。

概要题意：

其实就是将长度为 N 且 N_i=i 的序列上的两段序列分别翻转，并重复 K 次，输出翻转后的序列。

Part 1

思路：

假设 A_1 ...A_2 与 B_1 ...B_2 的中点分别为 mid_1 与 mid_2 ，则有以下情况：

• 设 A_1 ...A_2 与 B_1 ...B_2 范围为集合 A 与 B ，若 A\cap B=\varnothing 或 A\subseteq B 或 B\subseteq A 则每 2 次翻转序列恢复（为没有公共部分或者一个为另一个的子序列）。

  比较容易想，就不放图了。

由于翻转可视为每个数与该序列到中点长度相同数进行交换，的我们则可以将他们分成 5 部分，即 x1,x2,x3,x4,x5 （ x1,x3,x5 等长，为 A_1...A_2 与 B_1 ...B_2 的重叠部分长度 x2,x4 为独立部分只受自身翻转影响）令其“位置”为 1,2,3,4,5 。

如题意模拟：

经过 6 次序列恢复。将各个部分拆分（图中 k1 为题意中第一次翻转， k2 为题意中第二次翻转后的位置以及头尾顺序结果）：

发现其每个部分经过一定次数必能回到原来“位置”。那么这个“结论”是否适用于其他情况？

如题意模拟：

经过 12 次序列恢复。各部分 2 或 3 或 4 次回到原来“位置”（ x4 两次， x1,x3,x5 三次， x2,x6 四次）。

可总结：

    if(B1>=mid_1&&A2<=mid_2) k%=6;//具有对称性，与 A1...A2，B1...B2 前后无关。
    else if((B1<=mid_1&&A2<=mid_2)||(A2>=mid_2&&B1>=mid_1)) k%=12;//重复的不用执行了。

• 但当 B_1<mid_1 且 mid_2<A_1 则有如图：

如果按照上面的思路，会发现序列会产生很多的部分，这就导致结论没有普遍性（假了）。

但是凭借如此可以拿 79。

Part 2

但是！我们可以知道上面的序列恢复的次数，这个次数刚刚好是 A_1 ...A_2 与 B_1 ...B_2 中所有数回到原位置的最小次数的最小公倍数。

所以我们可以先每个数回到原位置的最小次数及最小公倍数算出来，再将 K 取模，减少重复次数，最后如题模拟，并输出。

提交记录

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,r,l,z,y,k=1,tot,t=0,f[101],b[101];
void s(int x,int y) {for(int j=x,k=y;j<k;j++,k--) swap(f[j],f[k]);}//翻转操作。
void d() {for(int i=1;i<=n;i++) f[i]=i;}//初始化与还原序列。
int main() 
{
    scanf("%d%d%d%d%d%d",&n,&m,&l,&r,&z,&y);
    tot=r-l+y-z+2-max(0,r-z+1);d();
    if((z<=l&&y>=r)||(l<=z&&r>=y)) tot=max(r,y)-min(l,z)+1;//tot求的是A_1 ...A_2，B_1 ...B_2中有多少个数。
    for(int i=1;;i++)
    {
        s(l,r),s(z,y);
        for(int j=1;j<=n;j++) if(((j>=l&&j<=r)||(j>=z&&j<=y))&&f[j]==j&&b[j]==0)b[j]=i,tot--;//判断是否在 A_1 ...A_2，B_1 ...B_2 中，是否第一次翻转到原来位置。
        if(tot==0) break;//所有数回到原位置的最小次数都求出来了，退出。
    }
    for(int i=1;i<=n;i++) if(b[i]!=0) k=k*b[i]/__gcd(k,b[i]);//恢复序列的最小次数。
    m%=k;d();
    for(int i=1;i<=m;i++) s(l,r),s(z,y);
    for(int i=1;i<=n;i++) printf("%d\n",f[i]);
    return 0;
}

感谢管理员的付出！

有错请指出！ 蒟蒻第一篇题解，求通过！