牛客IOI周赛28-普及组 ABC题解

A. String Game

Solution

签到题，做 次，将 的第一个字符放在 的后面，并将第一个字符删除。
注意 ，但是每做 次后字符串会变成初始的样子，所以对字符串长度取模随后用双端队列模拟即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48673298&returnHomeType=1&uid=105308122

B. Sequence Game

Solution

注意到数据范围，显然是个平方级别复杂度的 ，注意到值域很小，可以从值域入手
令 表示到了第 行的时候，结尾数字为 的最长上升子序列长度
只需要维护一个前缀最大值即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48678257&returnHomeType=1&uid=105308122

C. Simple Game

Solution

观察数据特征，由于出现环，同一个环中所有元素能到达的最小城市都是一样的。于是先做一次 缩点，剩下的就是有向无环图。此时注意到如果存在一条边 ，那么如果 ， 的答案可以被 所覆盖，所以考虑建反向边，此时变成 ，如果 ，就更新 的答案，直接在新图上拓扑排序并 即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48674145&returnHomeType=1&uid=105308122