2024“钉耙编程”中国大学生算法设计超级联赛（2）
我的代码都扔 Code Repo 里面了
| Problems | AC |
|---|---|
| 1001. 鸡爪 | ○ |
| 1002. 梦中的地牢战斗 | 待补 |
| 1003. 绝对不模拟的简单魔方 | ⊕ |
| 1004. a*b problem | |
| 1005. 小塔的养成游戏之梦 | |
| 1006. 传奇勇士小凯 | ○ |
| 1007. URL划分 | ○ |
| 1008. 成长，生命，幸福 | ⊕ |
| 1009. 强攻计策 | |
| 1010. 女神的睿智 | ○ |
| 1011. 在 A 里面找有 C 的 B | ○ |
| 1012. 图计算 | ⊕ |
1001 鸡爪
队友写了
1003 魔方
小T最近有些疲惫，想找一些能够放松自己的事情去做，正好想起上次被队友用三阶魔方暴杀的经历，就想苦练一下魔方技术，好在下次的对战中击败他的队友。
于是他在网上下单了一个魔方，让小C帮他去取快递。
可是小C有些调皮，私自拆开了快递，随意的扭了这个魔方不超过三次（扭的是侧面，不是中间层，且扭的角度固定为90度），还弄掉了同一个角上的两片贴纸。
小C的记性不太好，不太记得两片贴纸正确的位置了，所以随意的将两片贴纸贴了回去，并将这件事告诉了小T。
但小T作为一个还在学习如何还原底层十字的小萌新，面对被小C打乱过的魔方很是束手无策。
所以他向你寻求帮助，希望你告诉他小C有没有将两片贴纸正确的贴回去，如果没有的话，是哪一个角的贴纸贴错了呢。
逆天题，不超过三次的条件是为了骗你去爆搜，实际上直接看每个角的情况就行了。
1006 传奇勇士小凯 树形 DP
分数类 + 树形 DP。
丁真题，直接转移。
1007 URL 划分 模拟
逆天题，题面写不清楚。要定义了变量（带等号）的才输出。
1008 成长，生命，幸福 树的直径
德鲁伊题。
最后几十分钟会了，没写出来。
首先一个性质是，成长一次后每个点度数有三种情况：1/2/3
- 对于度数为 2 的，下一次会分裂出 2 个 度数 2 的。
- 对于度数为 3 的，下一次会分裂出 2 个 度数 2 的 和 1 个 度数 3 的。
- 对于度数为 d 的，下一次会分裂出 2 个 度数 2 的 和 d - 2 个 度数 3 的。
那么对于一开始度数为 d 的点，(2, d - 2) -> ((d - 2) * 2 + 2 * 2, d - 2) -> ((d - 2) * 4 + (d - 2) * 2 + 2 * 2 * 2, d - 2)……
归纳一下就是 $2 ^ m + (d - 2) * (2 ^ m - 1) = (d - 1) * 2 ^ m - d + 2$
直接对这个权值求树的直径就是答案。但是，求直径的时候不是要两个点取 max 吗，直接算是会爆 long long 的，也不能取模。发现 2 ^ m 这一项是非常大的，也就说是你 2 ^ m 比 - d + 2 大出一个数量级的时候 比较 $(d_i - 1, -d_i + 2)$ 和 $(d_j - 1, -d_j + 2)$ 可以变为比较两个关键字的大小。
1010 女神的睿智 模拟
签到题
1011 在 A 里面找有 C 的 B
AC 自动机 + KMP
板子双拼的签到题。。。。。
1012 图计算
逆天原题 洛谷 P8026 [ONTAK2015] Bajtocja
给定 $d$ 张 $n$ 个点的图和 $m$ 次加边操作 (每次只在某个图上加边), 求每次操作后在 $d$ 张图上都连通的点对个数, $d \leq 200, n \leq 5 \times 10^3, m \leq 10^6$ 。
首先你知道一张图的情况是很简单的并查集对吧。如果两个点在并查集的上的父亲都相同的话，那么他们就是相互连通的。
你拓展到 $d$ 个并查集的情况，那么把一个点在 $d$ 个并查集上的祖先 hash 下来。如果一个 hash 值出现了 $k$ 次的话，就对答案有 $k^2$ 的贡献。
2024“钉耙编程”中国大学生算法设计超级联赛（2）