2020-2021:teams:farmer_john:2020牛客暑期多校第三场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第三场 [2020/07/24 15:42] jjleo [题解] |
2020-2021:teams:farmer_john:2020牛客暑期多校第三场 [2020/07/24 17:06] (当前版本) bazoka13 [题解] |
||
|---|---|---|---|
| 行 53: | 行 53: | ||
| **upsolved by Bazoka13** | **upsolved by Bazoka13** | ||
| ====题意==== | ====题意==== | ||
| + | 每次替换一个位置的字符，将所有到达的字符串排序 | ||
| ====题解==== | ====题解==== | ||
| + | 因为给了$2e6$的数据，硬排会$T$掉,考虑到一种分治的思路，每次取当前区间会改变字符的最小值，那么区间被分成的两部分就可以确定大小，而最小值可以用笛卡尔树找到，二者结合即可 | ||
| =====I.===== | =====I.===== | ||
| **upsolved by ** | **upsolved by ** | ||
| 行 77: | 行 77: | ||
| 可以发现A永远走最后一步，因此我们不妨考虑一个状态是A必胜还是A必败。设此时有$x$个奇数位的问号和$y$个偶数位的问号，奇数位之和减去偶数位之和模$11$为$z$，那么状态$(x,y,z)$是A必胜态等价于$10(y-x) \equiv z \pmod {11}$，证明如下：考虑如果$(x,y,z)$是A必胜态，那么$(x-1,y,z-10),(x+1,y,z+10),(x,y-1,z+10),(x,y+1,z-10)$都是必败态，而当前者是必败态时后者都是必胜态；我们以前者是必胜态为例分析该结论，每次操作最多只能$\pm 9$，不可能实现$\pm 10$，如果自己的回合无法到达必胜态，那么对手就可以通过操作达到必败态（因为$\pm 20$在模$11$下等价于$\pm 9$，一先一后两次操作后，后手一定可以达到这个值）；而最终A胜利状态为$(0,0,0)$，即可推导出结论中的公式。 | 可以发现A永远走最后一步，因此我们不妨考虑一个状态是A必胜还是A必败。设此时有$x$个奇数位的问号和$y$个偶数位的问号，奇数位之和减去偶数位之和模$11$为$z$，那么状态$(x,y,z)$是A必胜态等价于$10(y-x) \equiv z \pmod {11}$，证明如下：考虑如果$(x,y,z)$是A必胜态，那么$(x-1,y,z-10),(x+1,y,z+10),(x,y-1,z+10),(x,y+1,z-10)$都是必败态，而当前者是必败态时后者都是必胜态；我们以前者是必胜态为例分析该结论，每次操作最多只能$\pm 9$，不可能实现$\pm 10$，如果自己的回合无法到达必胜态，那么对手就可以通过操作达到必败态（因为$\pm 20$在模$11$下等价于$\pm 9$，一先一后两次操作后，后手一定可以达到这个值）；而最终A胜利状态为$(0,0,0)$，即可推导出结论中的公式。 | ||
| - | 输赢确定后，考虑双方会如何进行最优操作。初始状态确定，必赢的一方要保证每一步操作后都是对手的必败态的前提下使得最终数字的绝对值更大，而必输的一方只用考虑使得最终数字的绝对值更小。如果必胜一方先手，那它第一步有两种选择，在奇数位填或在偶数位填进入对手的必败态，可以直接将两种情况都算一遍最后取绝对值更大的即可，此时填的数字可以通过上述结论算出来，如果是非$0$数，那么要填在奇数位或偶数位的最高位，否则要填在奇数位或偶数位的最低位，这样做显然是最优的。接下来，进入必败方-必胜方-必败方-必胜方的循环，必败方显然要让更高的位填$0$才能使绝对值更小。通过对上述结论可以得到如果必败方在奇数位填$0$，那么必胜方只能在奇数位填$9$或在偶数位填$0$，如果必败方在奇数位填$9$，那么必胜方只能在奇数位填$0$或在偶数位填$9$，奇偶反转过来也是同样成立的。因此通过一大波博弈思考，得出以下结论： | + | 输赢确定后，考虑双方会如何进行最优操作。必赢的一方要保证每一步操作后都是对手的必败态的前提下使得最终数字的绝对值更大，而必输的一方只用考虑使得最终数字的绝对值更小。如果必胜一方先手，那它第一步有两种选择，在奇数位填或在偶数位填进入对手的必败态，可以直接将两种情况都算一遍最后取绝对值更大的即可，此时填的数字可以通过上述结论算出来，如果是非$0$数，那么要填在奇数位或偶数位的最高位，否则要填在奇数位或偶数位的最低位，这样做显然是最优的。接下来，进入必败方-必胜方-必败方-必胜方的循环，必败方显然要让更高的位填$0$才能使绝对值更小。通过对上述结论可以得到如果必败方在奇数位填$0$，那么必胜方只能在奇数位填$9$或在偶数位填$0$，如果必败方在奇数位填$9$，那么必胜方只能在奇数位填$0$或在偶数位填$9$，奇偶反转过来也是同样成立的。因此通过亿阵博弈思考，得出以下结论：设奇数位置上有$x$个问号，偶数位置上有$y$个问号，那么如果$xy$奇偶性相同，最终双方的策略都是按顺序填$09090909 \cdots$；否则可以在其中一个填$009090909 \cdots$，另一个还是按顺序填$09090909 \cdots$，哪个先填两个$0$可以由必败方决定，因此讨论对应位置的前后即可得到大小关系，选择更小的那一个即可。 |
| + | |||
| + | 值得一提的是，必败方并不是只会一直填$0$，上述先填两个$0$的方案就是通过必败方从后往前填$9$逼迫必胜方填$0$从而达成的。 | ||
| =====L.===== | =====L.===== | ||
| **solved by JJLeo** | **solved by JJLeo** | ||
| 行 105: | 行 107: | ||
| * CSK强制下机，很痛苦，CSK$H$题写了傻逼线段树，很痛苦 | * CSK强制下机，很痛苦，CSK$H$题写了傻逼线段树，很痛苦 | ||
| * MJX写代码常有小 bug ，下场尤为突出 | * MJX写代码常有小 bug ，下场尤为突出 | ||
| + | * ZYF在懵逼时要及时交给队友接盘，避免浪费时间。 | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第三场.1595576532.txt.gz · 最后更改: 2020/07/24 15:42 由 jjleo
