一句话题解(2020-04)

看起来很牛逼,实际上是因为懒得写详细题解所以摸了,只写一句话题解。

02

CF1303F

注意到填充颜色递增,对每个颜色而言就是此颜色正序加入,非此颜色倒序加入,并查集正反两遍维护,链接

10

CF1303G

点分治,经过重心的路径分成上下两段,对于一个上段,权值关于下段的长度是一个一次函数,用李超树维护上段的函数,链接

CF1301E

预处理出以每个位置为中心的最大图标大小,询问时二分答案查询一个矩形区域中的最大值是否不小于答案,二维 RMQ,链接

CF1301F

BFS 预处理每个颜色到所有点的距离,要么不传送(曼哈顿距离)要么传送(枚举使用了传送的颜色,到起点 + 到终点),链接

11

「JSOI2019」精准预测

离散化,2-SAT 建图,建出来发现是天然的 DAG,传递闭包直接 bitset 整上,为了防止 MLE 需要分块做 bitset,链接

17

「JOI 2020 Final」集邮比赛 3

按照第一次经过每一张邮票的顺序做区间 DP,第三维状态是可收集邮票数,DP 值为最少需要花费的时间,链接

「JOI 2020 Final」奥运公交

注意到是往返,对正反图以 (1, n) 为起点建立 (4) 棵最短路树,Dijkstra 算法使用 (mathcal O (N^2 + M)) 的实现。
一条边 (u o v) 反向后的 (1)(n) 的最短路就是「(1)(n) 不经过这条边的最短路」与「『(1) 不经过这条边到 (v) 的最短路』+ 边权 +『(u) 不经过这条边到 (n) 的最短路』」的较小值,如果这条边在最短路树上则需要重新求最短路,(n)(1) 的最短路类似,链接

27

「HNOI2019」多边形

这题比较难,本应写正式题解的,但是不想写,仅仅是记录一下,链接

28

「JOI 2019 Final」有趣的家庭菜园 3

考虑 (mathrm{dp}[r][g][y][3]) 表示最终序列中前 (r + g + y) 个的颜色分布以及最后一个颜色时的最小逆序对数,转移显然,链接

「JOI 2019 Final」硬币收藏

普及组贪心或者模拟费用流,反正我确实不会,链接

「JOI 2019 Final」独特的城市

对于某点的独特的城市都分布在它到离它较远的直径端点的路径上,对两个直径端点分别考虑。
以端点为根做长链剖分,维护一个栈,在进入某点后栈内元素从浅到深表示忽略该点子树后的独特的城市(强制在到根的链上)。
要先把距离该点不超过次长子树距离的点退栈,然后才能往长儿子方向递归,然后把距离该点不超过最长子树距离的点退栈,然后统计该点自己的答案,再递归其它儿子,链接

29

「JOI 2018 Final」月票购买

求出所有可能成为 (S)(T) 的最短路上的边,把它们按照 (S o T) 方向定向,建立分层图,第一层和第三层就是原图,第二层是定向后的那些边((0) 权),每个点向下一层的同一个点连边,这样可以保证如果经过变成 (0) 权的那些边,一定是只会经过一条有向链,然后求 (U o V) 的最短路,注意还需要按照 (T o S) 方向定向一次,因为 (U o V) 经过的那些边可能是与 (S o T) 反向的,链接

「JOI 2018 Final」毒蛇越狱

如果 ( exttt{?}) 的数量比较少就暴力,如果 ( exttt{1}) 的数量比较少,考虑容斥,需要预处理高维前缀和后的数组,如果 ( exttt{0}) 的数量比较少同理,三者结合可以得到 (mathcal O (L cdot 2^L + Q cdot 2^{L / 3})) 的时间复杂度和 (mathcal O (2^L)) 的空间复杂度,链接

原文地址:https://www.cnblogs.com/PinkRabbit/p/SentenceSolution2020-04.html