题解：P9951 [USACO20FEB] Swapity Swap B

· · 题解

题解：P9951 [USACO20FEB] Swapity Swap B

找规律题。

题目分析：

给你一个序列，再给你两对起点和终点，把这两段先后反转，重复 a 次。

如此，我们可以很快写出如下代码：

while(k--) {//重复k次
    for(int i=a1,j=a2; i<=j; i++,j--) {
        swap(a[i],a[j]);//反转第一段
    }
    for(int i=b1,j=b2; i<=j; i++,j--) {
        swap(a[i],a[j]);//反转第二段
    }
}

然后你会发现超时了……

优化

多输出几个结果，观察一下。

可以清楚的发现，样例在循环四次后又回到原点，这就说明有大量无意义的循环导致程序时间超限。

知道问题就好解决了，找到数据的循环节，找到循环回到原点的次数，用 k \bmod ok 即可。

    while(f!=1) {//f用来判断是否相等，相等就结束
        f=1;
        for(int i=a1,j=a2; i<=j; i++,j--) {
            swap(a[i],a[j]);
        }
        for(int i=b1,j=b2; i<=j; i++,j--) {
            swap(a[i],a[j]);
        }
        for(int i=1; i<=n; i++) {
            if(a[i]!=b[i])f=0;
                //这里其实还有一个方法，判断每个元素出现次数，然后求最小公倍数。
                //不过比较麻烦，不做赘述
        }
        ok++;
    }
    k%=ok;//确保每步循环都是有意义的
    //代码可放心食用

然后你就 AC 啦！

后记：这是我第一篇题解，有问题请大家指出，谢谢！

完结撒花！