题解

T1 模拟题，暴力的统计一下 \text{jz} , \text{zc} , \text{d} 出现的次数。注意不要访问越界。

T2 • 本体需要从图的 度方面考虑，可以把构造抽象成 C 需要四个 度，O 需要两个 度 ，H 需要 一个 度 。 • 就 C 来说，本题限制了 C 链接其他 C 的数量不大于 2，并且 x\ge 3，所以 C 相链接的形态有且仅有 一条链 和 一个环 两种，那么链条形态的 C 剩余度数是 2\times (x+1)，环形的 C 剩余度数是 2\times x • H 在连接其他点后不能再连接别的点，所以我们可以把 H 的数量考虑成图中需要剩余的度数，比如图中还剩六个度，也就是剩下六个可连接的空间，那么就一定可以插入六个 H • O 可以连接两个点，那么他就可以当作‘管道’使用，只要不两头都接在 C 上，就不影响图中剩余的度数，并且可以无限放。否则他就要接在两个 C 上，这种操作会使图的剩余度数稳点减 2。 • 据此可以分析出，H 的数量必须是偶数，因为图的剩余度数无论怎样变化，都不会是奇数。再次分 析，C 的形态为一条链的形态，即是图中剩余度数的最大值。C 为一个环的形态，并且当图中剩余度不为零时，所有 O 都去占用图中剩余的度，就能让图中剩余的度最少，这就是最小值。 • 所以图中剩余度上限为 2\times (x+1) , 图中剩余度的下限为 max(0,2\times(x-y)) 。 • 因此，H 的数量为偶数，且处于 [2\times (x-y) ,2\times (x+1)] 之间，就是 YES，否则 NO。

T3 10% pts ：n^2 暴力对于区间修改即可

30% pts ：对于每个区间修改差分，最后统计个数和最大值。O(n)

100% pts：对于每个区间离散化，统计个数的时候不能直接对答案+1 ，因为离散化之后区间长度不是原来的区间长度，所以要用原先的右端点减左端点贡献答案。但是要考虑到存在长度为 1 的区间，如果直接把 l,r+1 离散化你会发现样例是过不了的。因为长度为 1 的区间会影响到离散化后区间的连续性，所以再多塞几个 [l,r] 中间的数。

T4 20%pts ：如果地图为一条链，那么这就是一个经典的线性dp问题。设 dp_{i,j} 表示走到第 i 个点，花费了 j 步获得的最大价值。然后按照顺序转移即可。转移方程：dp_{v,j}=max(dp_{u,j-w}+val[v]) 。 100% pts：注意到，这张图是一个DAG，而且还用了动态规划。根据动态规划的无后效性可以想到这题可以在拓扑序上进行转移。而且题目要求从 1 号节点为起点，那么先用dfs求出以 1 号节点为起点的入度，再在拓扑排序上进行状态转移。 最后注意统计答案的时候只能取地上节点的最大值。