The 2021 CCPC Guilin Onsite (Grand Prix of EDG)¶
| 排名 | 当场过题数 | 至今过题数 | 总题数 |
|---|---|---|---|
| 46/546 | 8 | 8 | 12 |
B¶
solved by 2sozx JJLeo
题意¶
两行十进制 \(n\) 位数，第三行永远等于这两行相加后低 \(n\) 位的值，每次修改两行中的某一行的某一位，问修改后第三行对应这一位是多少，以及三行总体相比之前修改了多少位。
题解¶
先算出来第三行每一位是多少，之后对每个修改分类讨论：
- 如果改的位置的数没变，则不会有变化。
- 如果第三行的数直接加上偏移量还是 \([0,9]\) 的范围，说明不会进位，直接改即可。
- 否则，如果 \(>9\) 说明会进位，找到左边最长连续 \(9\)，全变成 \(0\)，再右边一个 \(+1\)；如果 \(<0\) 说明会退位，找到左边最长连续 \(0\)，全变成 \(9\)，再右边一个 \(-1\)。 s 上述操作都可以在线段树上二分完成，每个节点记录区间内是否全部变成了 \(0/9\) 以及 \(0/9\) 的个数即可，需要注意单点修改也要把标记传下去再清楚，每次查询单点也要把标记传下去看看有没有。
复杂度为 \(O(q\log{n})\)
C¶
upsolved by
题意¶
题解¶
D¶
upsolved by
题意¶
题解¶
E¶
solved by JJLeo Bazoka13
题意¶
给定一个有向图，每条边有费用，在不超过给定的最大费用的情况下，可以选择一些边构成新的有向图。对于新的有向图，每次可以删除一个DAG，最大化新生成的有向图删除次数。
题解¶
可以证明一切如果有向图非DAG两次即可将整张图删掉。
即求最小环的大小。
对于每个点作为起点跑一次最短路，然后对于连接到起点的边我们新开一个点作为终点，起点到终点的最短距离即为这个最小环，复杂度 \(O(nm\log{m})\)。
\(n\le 2000, m\le 5000\)
F¶
upsolved by
题意¶
题解¶
H¶
upsolved by
题意¶
题解¶
J¶
solved by JJLeo
题意¶
把一个长度为 \(n\) 的字符串所有本质不同字串拿出来按长度为第一关键字，字典序为第二关键字进行排序，\(q\) 次询问第 \(k\) 个第一次出现位置是什么。
题解¶
建出后缀树，每个节点代表一段长度连续的子串，可以用差分算出来每种长度有多少个串。
离线所有询问，lowerbound 算出来询问的是为长度是多少的串的字典序第几个。
按字典序 dfs 后缀树，每个点记录一个 dfn 序，从小到大遍历长度，设每个节点对应串长度是 \([l,r]\)，则在 \(l\) 时将其 dfn 加入树状数组，在 \(r+1\) 时从树状数组删掉，对于每个询问就是树状数组求第 \(k\) 大。
卡空间，需要把 \(26\) 换成 map，再把几个 vector 换成链式前向星。
复杂度 \(O((n + q)\log{n})\)
K¶
solved by 2sozx
题意¶
\(n\) 个点，\(m\) 条边，边长度为 \(1\)，每条边属于一个公司，每个公司有一个权值 \(w_i\)。一个人从 \(1\) 出发，到其余 \(n-1\) 个点，首先他要走最短路，其次他要这条路径花费最小。一条边的花费为 \(w_i\times app_i\) ，其中 \(i\) 是这条边的所属公司，\(app_i\) 是这个公司在这条边之前的出现次数，对 \(2\sim n - 1\) 输出最小花费。\(n\le 50, m \le \dfrac{n(n - 1)}{2}\)
题解¶
首先跑一个最短路，之后 \(dfs\) 暴力跑即可，最短路最多仅有 \(3^{n/3}\) 条，可以接受。
L¶
upsolved by
题意¶
题解¶
记录¶
0h：打桂林！MJX看A太长不看，换题，2min发现过穿了，MJX瞅了瞅 Input 和 Output，输出 \(2x-1\) 即可。看I有人过了，也是个签到，ZYF直接冲了过了。看G直接PTSD了，和广州C几乎一样。ZYF写完样例没过，MJX发现有点小不同，先把B的解法喂给ZYF。CSK瞅D YY了个结论，MJX准备写。MJX YY了个大概对的贪心，ZYF开冲，过了。MJX写D，CSK ZYF讨论E。
1h：MJX写完了，交上去WA了。ZYF开始写E，MJX发现有个地方考虑的不对，抢机器改了过了。ZYF 5min速冲AC，ZYF CSK 开始交替冲B F。MJX觉得K可以暴力嗯跑，复杂度很对，不过状态好像存不下。30min后MJX发现自己是个nt，不用存状态，直接跑就行，写写过了，帮ZYF瞅瞅B的代码。
2h：ZYF写完了WA了，发现状态改完没在线段树上modify，改了后又冲了一次，寄了，开始写对拍。CSK继续写F。
3h：拍了半天大概找到错误了，改了过了，开始交替冲J，但是时间空间都不咋够。
4h：MJX和CSK继续爆搞F，感觉很对，但是完全不对，感觉该改的地方不该改，怪。改了一堆样例倒是过了，交上去WA3了，开始de。ZYF发现写线段树分治是nt，改成树状数组时空都对了，交上去MLE11，把SAM改成了map存边变成了MLE13，改成了前向星过了。MJX觉得F应该是凸包共线的问题，然而改了样例也过不去，乱改一同交了两发WA了，寄了。