目录
- D1T1 P9166 [省选联考 2023] 火车站
- D1T2 P9167 [省选联考 2023] 城市建造
- D1T3 P9168 [省选联考 2023] 人员调度
- D2T1 P9169 [省选联考 2023] 过河卒
- D2T2 P9170 [省选联考 2023] 填数游戏
- D2T3 P9171 [省选联考 2023] 染色数组
D1T1 P9166 [省选联考 2023] 火车站
性质很好找。关键在所有的区间排序时候的情况分讨。统计答案的时候也很有意思。可以将最远的节点进行标记，而小于最远节点的起始节点都是可到达的，然后以此不断更新最远节点的位置。代码
D1T2 P9167 [省选联考 2023] 城市建造
D1T3 P9168 [省选联考 2023] 人员调度
D2T1 P9169 [省选联考 2023] 过河卒
经典的博弈DP。首先将三个棋子的移动方向分别建图，然后规定胜、负、平的条件，最后针对状态进行先后手转移。注意这里的转移比较有操作，可以使用先后队列的方式转移状态，同时统计步数。代码
D2T2 P9170 [省选联考 2023] 填数游戏
这题确实很思维。首先转化题面，\(T_{i,1}\) \(T_{i,2}\) 进行连边，如果只有一个就连自环。这道题就抽象成Bob有能力将每个连通块中删去一个点，最小化代价，而Alice的任务是最大化最小代价。看到特殊性质A，也就是和Alice的操作没有任何关系，即是判断0还是-1。根据图的性质，如果我们希望选择不相同的 \(n\) 个点，那么我们必须要有 \(n-1\) 条边的树的形态和 \(n\) 条边的基环树形态。考虑使用这条性质判断是否有解。特殊性质A代码。然后考虑特殊性质B，也就是说Bob的操作只有两种可能，且分别构成两条环。而Alice的每次操作产生的贡献分为三种，对1 \(\sim\) n序列产生贡献，对2 \(\sim\) n 和 1 产生贡献，和对两者都能产生贡献（不产生贡献不考虑），最后使得分别产生贡献的最小值最大即可。特殊性质B代码。此时发现其实针对所有情况我们都可以归为三种情况，首先是既不是基环树森林也不是树森林，那么输出-1；而基环树上环的情况的最大的最小值是已知的，就是特殊性质B的答案。那么我们只需要知道树的情况，然后将环的情况加入到树中就可以了。考虑单独的树在未确定边方向时产生的贡献是入点的子树大小，那么将边的方向反转，会产生一个差值。而我们最后就要这个连通块内不选哪个节点的最小代价最大。暴力枚举过不去，需要用线段树差分做到 \(\log\) 。代码