2020-2021:teams:farmer_john:2020牛客暑期多校第三场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:farmer_john:2020牛客暑期多校第三场 [2020/07/24 14:51] jjleo [题解] |
2020-2021:teams:farmer_john:2020牛客暑期多校第三场 [2020/07/24 17:06] (当前版本) bazoka13 [题解] |
||
|---|---|---|---|
| 行 48: | 行 48: | ||
| 给定一个$n$个点$m$条边的无向连通图，一开始$i$点的颜色就是$i$。每次操作选择一个颜色$c$，如果已经不存在这个颜色则无事发生；否则如果某个点的颜色为$c$，另一个颜色为$d$的点与该点相邻，则所有颜色为$d$的点全部变为颜色$c$。问全部操作完成后所有点的颜色。$(n,m \le 8 \times 10^5)$ | 给定一个$n$个点$m$条边的无向连通图，一开始$i$点的颜色就是$i$。每次操作选择一个颜色$c$，如果已经不存在这个颜色则无事发生；否则如果某个点的颜色为$c$，另一个颜色为$d$的点与该点相邻，则所有颜色为$d$的点全部变为颜色$c$。问全部操作完成后所有点的颜色。$(n,m \le 8 \times 10^5)$ | ||
| ====题解==== | ====题解==== | ||
| - | 显然每次操作后每种颜色组成的点是一个联通块。因此每种颜色的点在扩张一次后就不会再产生作用，可以将其称作某种颜色的内侧点，而每次新加入的点则称作外侧点，可以考虑开一个vector放每种颜色的外侧点。扩张某种颜色时遍历上述vector中的全部外侧点，合并所有相连的其它颜色对应的vector，并将扩张过的点弹出vector，每个点仅进出vector一次，合并时采用启发式合并，时间复杂度$O(\log n)$。 | + | 显然每次操作后每种颜色组成的点是一个联通块。因此每种颜色的点在扩张一次后就不会再产生作用，可以将其称作某种颜色的内侧点，而每次新加入的点则称作外侧点，可以考虑开一个vector放每种颜色的外侧点。扩张某种颜色时遍历上述vector中的全部外侧点，合并所有相连的其它颜色对应的vector，并将扩张过的点弹出vector，除合并外每个点仅进出vector一次，合并时采用启发式合并，时间复杂度$O(\log n)$。 |
| =====H.===== | =====H.===== | ||
| **upsolved by Bazoka13** | **upsolved by Bazoka13** | ||
| ====题意==== | ====题意==== | ||
| + | 每次替换一个位置的字符，将所有到达的字符串排序 | ||
| ====题解==== | ====题解==== | ||
| + | 因为给了$2e6$的数据，硬排会$T$掉,考虑到一种分治的思路，每次取当前区间会改变字符的最小值，那么区间被分成的两部分就可以确定大小，而最小值可以用笛卡尔树找到，二者结合即可 | ||
| =====I.===== | =====I.===== | ||
| **upsolved by ** | **upsolved by ** | ||
| 行 69: | 行 69: | ||
| =====K.===== | =====K.===== | ||
| - | **upsolved by ** | + | **upsolved by JJLeo** |
| ====题意==== | ====题意==== | ||
| + | 两人玩游戏。给定一个由数字和至少一个问号组成的序列，每人轮流将一个问号改为一个数字。如果问号数量为奇数则A先手，否则B先手。最终所有问号的被填完后，如果所得数字是$11$的倍数，则本轮游戏得分为该数字，否则得分为该数字的相反数。A希望数字越大越好，B希望数字越小越好，如果他们会按照最优策略进行操作，求最终游戏结果。 | ||
| ====题解==== | ====题解==== | ||
| + | 前置芝士：一个数是$11$的倍数等价于奇数位之和减去偶数位之和是$11$的倍数。 | ||
| + | |||
| + | 可以发现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$，奇偶反转过来也是同样成立的。因此通过亿阵博弈思考，得出以下结论：设奇数位置上有$x$个问号，偶数位置上有$y$个问号，那么如果$xy$奇偶性相同，最终双方的策略都是按顺序填$09090909 \cdots$；否则可以在其中一个填$009090909 \cdots$，另一个还是按顺序填$09090909 \cdots$，哪个先填两个$0$可以由必败方决定，因此讨论对应位置的前后即可得到大小关系，选择更小的那一个即可。 | ||
| + | |||
| + | 值得一提的是，必败方并不是只会一直填$0$，上述先填两个$0$的方案就是通过必败方从后往前填$9$逼迫必胜方填$0$从而达成的。 | ||
| =====L.===== | =====L.===== | ||
| - | **solved by ** | + | **solved by JJLeo** |
| ====题意==== | ====题意==== | ||
| + | 签到。 | ||
| ====题解==== | ====题解==== | ||
| + | 比手速。 | ||
| =====记录===== | =====记录===== | ||
| 行 97: | 行 107: | ||
| * CSK强制下机，很痛苦，CSK$H$题写了傻逼线段树，很痛苦 | * CSK强制下机，很痛苦，CSK$H$题写了傻逼线段树，很痛苦 | ||
| * MJX写代码常有小 bug ，下场尤为突出 | * MJX写代码常有小 bug ，下场尤为突出 | ||
| + | * ZYF在懵逼时要及时交给队友接盘，避免浪费时间。 | ||
2020-2021/teams/farmer_john/2020牛客暑期多校第三场.1595573516.txt.gz · 最后更改: 2020/07/24 14:51 由 jjleo
