自动搬运

查看原文

来自洛谷，原作者为

	Shunpower 我笨笨的，菜菜的，累累的 >_< | 在役

搬运于2025-08-24 23:14:28，当前版本为作者最后更新于2025-04-24 19:50:13，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

whk 晚自习的时候搓的题。做了差不多十分钟以为自己搓出了最优解实际上 corner case 一筐筐……

很有意思的一道题。很像小时候玩过的一款桌游但记不得名字了。写篇题解记录一下。

---

我们首先证明，$c$ 和 $s$ 必须是偶数才有解。

$s$ 是偶数的证明比较简单。考虑我们从某一个弯曲轨道的弯曲位置之前出发，那么每经过一次弯曲轨道，都一定会将方向进行一次水平与竖直的旋转，所以我们必然需要经过偶数次弯曲轨道，才能使得最终方向与初始方向有可能相同，才能构成环。

$c$ 是偶数的证明，可以考虑把弯曲轨道看成没有圆弧，由两条 $0.5$ 单位长度线段拼接在一起，那么整个轨道是一个每条边的边长都是整数的曼哈顿多边形。容易证明，它的周长一定由若干个长方形作为基得到（人话就是若干个长方形的周长能把它的周长异或出来），所以一定是是偶数。由于每个弯曲轨道贡献 $1$ 的长度，并且弯曲轨道有偶数个，所以直轨道也一定有偶数个。

因此我们只需解决 $c,s$ 均为偶数的情况。奇数没用，必须减去 $1$ 规约到偶数。

接下来我们就可以开始构造了！

考虑我们把直轨道放进一个环应该是比较简单的，选择一个地方竖着或者横着劈开平行地塞进去就可以了。所以我们尝试构造没有直轨道并尽可能使用弯曲轨道的方案。

进一步地，我们发现只由弯曲轨道构成的纯环的长度必然是 $4$ 的倍数。换句话说，必然只有 $4$ 的倍数个弯曲轨道才能构成纯环。

证明可以考虑每条轨道都一定会变换方向，而四种变法的总数必然是相等的（显然，水平变竖直和竖直变水平的次数肯定相等，而每种内部的两个变法因为方向相斥所以也一定相等才能抵消），所以一定是 $4$ 的倍数个弯曲轨道。

手画一下几个比较容易得到的构造可以发现：

$c\equiv 0\pmod 4$ 处的方案

考虑 $c=4$ 的时候显然就是一个圈圈。

我们尝试把环做大一点，那么容易想到把 $c=4$ 的环四面朝外打开，然后再绕回来，得到了 $c=12$ 处的方案：

我们应该会尝试把这个结构往右边复制：

可以发现每次相当于往中间插了 $8$ 个弯曲轨道。由此，我们获得了 $c\equiv 4\pmod 8$ 处的最优解，然而这并不能解决 $c\equiv 0\pmod 8$。

一个简单的想法是，我们直接把 $c\equiv 4\pmod 8$ 处的最优解抹掉最右边那个环，但至少要使用两条直轨道。

可以发现过不了。因为实际上我们确实存在一个不需要直轨道的纯环方案。

考虑延续刚刚那个结构，可以发现我们除了能横着拼，还能向斜下方嵌进去：

可以发现这等价于我们每次往中间插入 $4$ 条轨道。因此这个解决办法可以完整地完成这个部分……吗？

Corner Case

注意到我们一开始设计的结构有 $12$ 条弯曲轨道，所以我们其实根本没有解决 $8$ 条弯曲轨道的方案。

很遗憾，$c=8$ 时根本没有不使用直轨道的方案。这可以通过暴力证明。

而如果允许使用两条直轨道，我们有一个显然的方案：将一个 $c=4$ 的环展开，取代其中的两条直轨道，就像这样：

完善 $c=8$ 之后，这个部分算是彻底解决了。

$c\equiv 2\pmod 4$

此时我们不得不至少使用两条直轨道才能用上所有的弯曲轨道了。所以对于直轨道为 $0$ 条的情况，我们必须舍去两条弯曲轨道后采用上面 $c\equiv 0\pmod 4$ 的办法。

考虑 $c=6$，容易得到下面这个结构：

我们仍然考虑扩展这个结构。显然应该往右下方扩展：

可以发现，这样我们每次塞进去 $4$ 个弯曲轨道，可以解决整个 $c\equiv 2\pmod 4$。

---

于是做完了。

int s,c;
string ans;
void make40(int s,int c){
	if(c==4){
		cout<<"RR";
		fr1(i,1,s/2) cout<<"S";
		cout<<"RR";
		fr1(i,1,s/2) cout<<"S";
		return;
	}
	cout<<"R";
	fr1(i,1,s/2) cout<<"S";
	cout<<"RLR";
	fr1(i,1,c/4-2) cout<<"RL";
	cout<<"R";
	fr1(i,1,s/2) cout<<"S";
	cout<<"RLR";
	fr1(i,1,c/4-2) cout<<"RL";
}
void make42(int s,int c){
	c/=4;
	cout<<"RR";
	fr1(i,1,c) cout<<"LR";
	fr1(i,1,s/2-1) cout<<"S";
	cout<<"RSR";
	fr1(i,1,s/2-1) cout<<"S";
	fr1(i,1,c-1) cout<<"LR";
	cout<<"S";	
}
int main(){
#ifdef Shun
	freopen(".in","r",stdin);
	freopen(".out","w",stdout);
#endif
	cin>>s>>c;
	if(s&1) s--;
	if(c&1) c--;
	if(c%4==0){
		if(c==8){
			if(s==0) make40(s,4);
			else{
				cout<<"RLRRL";
				fr1(i,1,s/2-1) cout<<"S";
				cout<<"RR";
				fr1(i,1,s/2+1) cout<<"S";
				cout<<"R";
			}
		}
		else make40(s,c);
	}
	else{
		if(s==0){
			if(c==10) make40(s,4); 
			else make40(s,c-2);
		}
		else make42(s,c);
	}
	ET;
}
//ALL FOR Zhang Junhao.