P9744 「KDOI-06-S」消除序列
题目 link 题解 考虑dp 设f[i]表示使序列由全是1到满足集合PPP条件所需的最少代价 然后想一想，f[i]怎么推 首先，我们可以把p[i]之前的全部推平，都变成000，然后一个一个变成1 其次，我们也可以把f[i - 1]搞出来，然后把p[i - 1] + 1到p[i] - 1之间都弄成000。 这里就只能进行若干次第二次操作了，可以用前缀和来优化 但是“首先”一条的复杂度这么做肯定
P1712 [NOI2016] 区间
题目 link 题解 首先，看到数据范围这么大，答案还与值域有关，考虑离散化 按照长度（离散前）排序以后肯定一段一段取 所以，考虑双指针，维护两个指针l,r,意义是从l到r恰好是有m个区间包裹一个点 每次r++，如果包含同一个点的数量大于m了，就l++，知道不大于m 当然，一开始要给区间按大小排个序。 （为啥要排序，有没有大佬解释一下） 我们看到要求的是最大区间长度减去最小的区间长度。从
P2047
题目 link 题解 看题目范围，n≤100n\leq100n≤100，又要求最短路，因此考虑floyd 先预处理出i到j的最短路，顺便还可以求出i 到j的最短路的条数。具体看代码 统计答案的时候枚举每个点k，然后枚举s，t，如果k点在s到t的最短路上的话，这个点的答案加上cnt[s][k] * cnt[k][t] * 1.0 / cnt[s][t] 不开long long见祖宗 代码 12
P1894
题目 link 题解 由于每头奶牛只会和牛栏起关系，而让我们求最多能分配到多少牛栏，所以我们可以建立二分图 代码 //二分图最大匹配...
[CERC2014] Outer space invaders
题目 来自外太空的外星人（最终）入侵了地球。保卫自己，或者解体，被他们同化，或者成为食物。迄今为止，我们无法确定。 外星人遵循已知的攻击模式。有 N 个外星人进攻，第 i 个进攻的外星人会在时间 a_i 出现，距离你的距离为 d_i，它必须在时间 b_i 前被消灭，否则被消灭的会是你。 你的武器是一个区域冲击波器，可以设置任何给定的功率。如果被设置了功率 R，它会瞬间摧毁与你的距离在 R 以内的所
P7960 [NOIP2021] 报数
题目 link 题解 简单的一个筛法 一个数不能取到，那么它的倍数一定不能取到 看一个数能不能取到，暴力求解就行 不过，要对于每个数预处理出答案 具体看代码 ...
P3373 【模板】线段树 2
题目 link 题解 线段树 考虑两个tag，mul与add 表示[l, mid] [mid + 1, r]这两个区间分别需要* mul + tag 下传标记的时候[l, mid] [mid + 1, r]这两个子区间的tag，mul tag直接*mul[u]，add tag要* mul[u] + tag[u] 锅 1.change最后返回前要pushup一下 2.下传的时候u要穿ls，
P4281
题目 link 题解 弱化题目条件 如果是两个人的话，集合点肯定在这两个点的lca上 而这里是三个人，怎么办？ 猜测发现一定在其中两个人的lca上 分别求出两两的lca，3种情况分别比较大小即可 代码 ...
[JOI 2022 Final] 铁路旅行 2 (Railway Trip 2)
题目 IOI 铁路公司在一条铁轨上运营线路。铁轨为一条直线，该铁轨上有 NNN 个车站，编号为 1∼N1 \sim N1∼N。车站 iii 与车站 i+1i + 1i+1 之间由一条铁轨直接连接。 IOI 铁路公司正在运营 MMM 条线路，编号为 1∼M1 \sim M1∼M。线路 jjj 的起点为 AjA_jAj，终点为 BjB_jBj，列车在每一站均会停靠，即如果 Aj<BjA_j
染色
题目 给定一棵 nnn 个点的以 111 为根的有根树，现在有 mmm 种颜色，你需要对每个节点染色 求本质不同的染色数，对 998244353998244353998244353 取模 两棵树本质相同，当且仅当忽略节点编号后(根不变)，两棵树同构(颜色＋形态) 满足 n≤500n≤500n≤500 题解 首先，这是个计数问题，不擅长 计数方面的问题等学会了再来补充 然后看一下这个题目另一个关