P2502
用时:30min
枚举最小边,对于给定边集,两点之间的最大边权最小是最小生成树伤的边,直接 \(O(m^2\log n)\) 去做即可。
P6569
发现 \(f_{i,k}\) 就是点 \(i\) 走 \(k\) 步能到达的点的异或和。
于是对于点 \(1\) 求出走 \(a_i\) 步到每个点的方案数,如果是奇数就计入答案。
显然可以矩阵乘法,\(qn^3\log V\),过不了。
发现我们只关心方案数奇偶用 bitset 压一下,\(q\frac{n^3}{64}\log V\) 可以过了。
P2707
这个代价一是个二次函数,发现可以按增长量去贪心就做完了,用一个 pq。
CF1598F
考虑用前缀和判断括号序列。
设计 \(f_S\) 表示前面已经选了 \(S\) 的括号串,发现新加进来的括号串与前面怎么排的没关系,于是对于每个串记录每个前缀和出现多少次,和前缀前缀和最小值即可。