简单题记录

sevenki · 2024-09-25 21:51:05 · 个人记录

P9619 生成树

zek户厕时搬的题。赛时尝试推式子结果越推越像多项式但其实非常简单
考虑有标号无根树有 n^{n-2} 种，每种有 n-1 条边，而总共可供选的边数有 \frac{n(n-1)}2 种，我们平均一下，就可以得到每条边对于答案的贡献次数是 2n^{n-3} 的。
然后你可以 O(n^2) 枚举着做了，然后异或的话，拆拆位加速成 O(n\log w) 就做完了。

ABC215E Chain Contestant

题目相当于：相同字母都得挨一块。

挺好的一道状压。虽然一眼就知道是状压，但是实际上方程还是有点思维的，如果像我一样绕晕一样。

设 dp_{i,S,j} 表示截止下标为 i，目前已经出现过的字符集合为 S，上一个字符为 j 的方案数量。

首先，不选上这个字符，那么有 dp_{i,S,j}\gets_+ dp_{i-1,S,j}。
然后选上这个字符，有 dp_{i,S,j}\gets_+ dp_{i-1,S,j}~\textsf{if }s_i=j~\&~j\in S。

当然以上是“从以前那里接上的”，还有自己新开一个段的。有 dp_{i,S,j}\gets_+ dp_{i-1,S \backslash s_i,j}~\textsf{if }s_i=j~\&~j\notin S。

最后还有从这里从头开始的。dp_{i,\{s_i\},s_i}\gets_+ 1。

CSP-S 2021 回文

首先如果确定前 n 次操作的话，那么剩下操作的顺序是唯一确定的。

然后我们考虑第一次究竟是在做什么：

选定左边/右边最开头的数。然后对应的，这个数的另一个出现位置将会是最后一个出去的。

然后第二个数，容易得知第二个数对应的另一个位置会是倒数第二个出去的，肯定挨在倒数第一个旁边。如此类推。

然后你会发现我们其实就是维护了外面两个指针，里面两个指针，外面的指针扩充的前提是里面的指针也有相应的数。那么我们只需要对第一个选左边/右边分类讨论一下，再对每种情况在可行性下贪心即可。

CSP-S2019 江西 网格图

实际上就是要你把最小生成树的过程在这个特殊图上优化一下。然后模拟最小生成树就行了。

当然为了保证连通性，我们要先保证行/列分别的最小值都被选上。

省选联考 2020 B 卷 幸运数字

挺魔怔的一道题。可以转化为区间异或，然后求序列最大。由于我不会边界情况，所以无脑上个动态开点线段树，最后再dfs统计一下答案就完了。比离散化扫描线好些不少。

JOI 2024 Final 建设工程 2

两遍 dij，然后枚举中介点，二分查找一下即可。

赛时脑瘫做法：

枚举中介边，然后找满足 xxx或xxx 的点（此处省略条件）可以容斥一下。然后就会发现 xxx与xxx 这个条件等价于三维偏序，所以无脑上cdq分治。。

NOI Online 2022 入门组 数学游戏

脑电波可还行。

设 d=\gcd(x,y),da=x,db=y，那么有 \gcd(a,b)=1。
然后 z=dadbd=d^3ab,\dfrac z x=d^2b。

然后 \gcd(\dfrac z x,x^2)=\gcd(d^2b,d^2a^2)=d^2。