补题进度：5/6(11)
输出忘记加Case(演？
$x,y$变量反了(假？
躺尸两个半小时
A
题解
- 推公式发现是$n-1$，没加$Case$罚时$+1$
B
留坑
C
题解
- 简单的博弈游戏，推一推很简单
D
留坑
E
题解
- 签到，简单的模拟
F
莫比乌斯反演，留坑？
G
题意
给$m$个区间，区间范围为$[1,n]$，求选 $k$ 个区间能覆盖的最多点的数量
$(n,m,k\le 2·10^4)$
题解
- 赛时想的按照经典的按照左端点排序，定义$dp[i][j]$：前 $i$ 条线段选 $j$ 条的最大值且第$i$必选的最大值，这样的转移时 $O(n^3)$，因为每次要考虑前 $i-1$ 条的情况，没有想到怎么优化$gg$
- 正解：考虑$n$的范围只有 $2000$，我们可以从点入手，定义 $dp[i][j]$：前 $i$ 个点用了 $j$ 个区间的最大值
- 转移：考虑$dp[i][j]$由谁转移而来，不是很好转移，因为第 $i$ 个点可能所处很多区间，不如考虑$dp[i][j]$能转移的状态，显然$dp[i][j]$转移到 $i$点所能延伸的最右端是最优的，故预处理每个点可以延伸到的最右端，转移即可
- 时间复杂度 $O(n^2)$
H
留坑
I
题意
给你一个基环树，树上的边有各种颜色，每次操作有两种：
- 修改一条边的颜色
- 询问这个图有多少色块（相同颜色的边公用一个点，则为一块）
题解
待补
J
- 队友构造的
K
题解
- 差分打表看出规律，推出多项式方程
- $n$高达$10^9$，需要高精度