比赛链接 https://ac.nowcoder.com/acm/contest/88527
A
很显然的一个思路是 直接爆搜 具体实现我们可以用一个map 先标记终点日期为0 然后从起始日期开始枚举所有可能后继状态搜索,存在必胜点的即为必败点 全为必败点的为必胜点 为了节约时间我们加一个记忆化即可 实测跑得飞快
B
目标是把≥R的数减小到R 把≤L的数增加到L 根据我们的操作贪心的想肯定是同时进行最好
于是答案是两种情况下操作数量取大的结果 注意到数组的和不变 需要特判不可能的情况
C
首先我们发现 当答案确定时 两两回忆能不能划分在一起也就被确定了 我们只需要判定可行性即可 所以我们首先二分答案 然后判定可行性可以跑2-sat
D
线段树裸题 直接写就行
E
欧拉筛筛出质数 枚举其中两个即可
F
翻译一下题意就是跑到每个点再回来 跑到每个点的距离最小就是最短路板子 直接跑dijkstra 至于回来的路程最小 我们不难想到可以建反图 重新跑一次以1为起点的dijkstra
G
显然有转移式子
dp[i]=dp[i-1]+dp[i-2]+dp[i-3]
H
静态RMQ 线段树会T ST表可以跑过 如果题目时限更紧 可以考虑压位ST表
I
同样是一个经典问题 即找一个点到给定点集的距离总和最小 答案是点集的中位数
J
直接输出即可
K
最小瓶颈路板子题 虽然只有一次询问 我们直接建出kruskal重构树 查询 s,t的lca的点权即可