题解：P12308 [ICPC 2022 WF] 玩具火车轨道

· · 题解

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

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

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

$c$ 是偶数的证明，可以考虑把弯曲轨道看成没有圆弧，由两条 $0.5$ 单位长度线段拼接在一起，那么整个轨道是一个每条边的边长都是整数的曼哈顿多边形。容易证明，它的周长一定由若干个长方形作为基得到（人话就是若干个长方形的周长能把它的周长异或出来），所以一定是是偶数。由于每个弯曲轨道贡献 $1$ 的长度，并且弯曲轨道有偶数个，所以直轨道也一定有偶数个。 因此我们只需解决 $c,s$ 均为偶数的情况。奇数没用，必须减去 $1$ 规约到偶数。 接下来我们就可以开始构造了！ 考虑我们把直轨道放进一个环应该是比较简单的，选择一个地方竖着或者横着劈开平行地塞进去就可以了。所以我们尝试构造没有直轨道并尽可能使用弯曲轨道的方案。 进一步地，我们发现只由弯曲轨道构成的纯环的长度必然是 $4$ 的倍数。换句话说，必然只有 $4$ 的倍数个弯曲轨道才能构成纯环。 证明可以考虑每条轨道都一定会变换方向，而四种变法的总数必然是相等的（显然，水平变竖直和竖直变水平的次数肯定相等，而每种内部的两个变法因为方向相斥所以也一定相等才能抵消），所以一定是 $4$ 的倍数个弯曲轨道。 手画一下几个比较容易得到的构造可以发现： ### $c\equiv 0\pmod 4$ 处的方案 考虑 $c=4$ 的时候显然就是一个圈圈。 我们尝试把环做大一点，那么容易想到把 $c=4$ 的环四面朝外打开，然后再绕回来，得到了 $c=12$ 处的方案： ![](https://cdn.luogu.com.cn/upload/image_hosting/pp87imru.png) 我们应该会尝试把这个结构往右边复制： ![](https://cdn.luogu.com.cn/upload/image_hosting/etkdvidp.png) 可以发现每次相当于往中间插了 $8$ 个弯曲轨道。由此，我们获得了 $c\equiv 4\pmod 8$ 处的最优解，然而这并不能解决 $c\equiv 0\pmod 8$。 一个简单的想法是，我们直接把 $c\equiv 4\pmod 8$ 处的最优解抹掉最右边那个环，但至少要使用两条直轨道。 可以发现过不了。因为实际上我们确实存在一个不需要直轨道的纯环方案。 考虑延续刚刚那个结构，可以发现我们除了能横着拼，还能向斜下方嵌进去： ![](https://cdn.luogu.com.cn/upload/image_hosting/7s4rkv3b.png) 可以发现这等价于我们每次往中间插入 $4$ 条轨道。因此这个解决办法可以完整地完成这个部分……吗？ ### Corner Case 注意到我们一开始设计的结构有 $12$ 条弯曲轨道，所以我们其实根本没有解决 $8$ 条弯曲轨道的方案。 很遗憾，$c=8$ 时根本没有不使用直轨道的方案。这可以通过暴力证明。 而如果允许使用两条直轨道，我们有一个显然的方案：将一个 $c=4$ 的环展开，取代其中的两条直轨道，就像这样： ![](https://cdn.luogu.com.cn/upload/image_hosting/u0tjhnbr.png) 完善 $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.