自动搬运

查看原文

来自洛谷，原作者为

	Distorted_Fate_ 我看到了【生生不息】的激荡！

搬运于2025-08-24 22:53:19，当前版本为作者最后更新于2024-06-11 20:56:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题解：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$ 啦！

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

完结撒花！