开坑 主要是cf和atcoder 记录一下非水题 =====CF1404B===== ====题意==== 博弈论，两人轮流在树上跑，每次分别可以移动不超过 $da$ 和 $db$ 的距离，问先手能不能追到后手。 ====题解==== 三种情况必胜： * 两者距离不超过 $da$。 * $2 \times da \ge db$，以 $a$ 为根往下逼近即可。 * $2 \times da \ge \text{diameter}$，卡中点即可。 证明我吐了，有时间再来补。 =====CF1404C===== ====题意==== 给定一个序列 $a_i$，如果 $a_i = i$，那么你可以将它删掉，多次询问如果强制前 $x$ 个数和后 $y$ 个数都不能删，最多能删几个数。 ====题解==== 发现问题的**可二分性**，[[https://www.cnblogs.com/dysyn1314/p/13625607.html|巨佬题解]]。 设 $\text{lim}_i$ 表示如果禁止删除的长度 $\le \text{lim}_i$，那么该位置可以被删，否则不能被删。 考虑二分求解，对于我们正在二分的 $\text{mid}$，等价于求前面满足 $\text{lim}_j \ge \text{mid}$ 的有多少个，这个过程可以使用主席树优化到 $O(n \log n)$。 对于询问，直接询问 $[1,n-y]$ 中 $\text{lim}_i \ge x$ 的个数即可，主席树上查询即可。 =====CF1404D===== ====题意==== 交互题，给定 $1$ 到 $2n$ 共 $2n$ 个数，你可以选择当 A 或 B。 * A 要将 $2n$ 个数两两一组分为 $n$ 个。 * B 要在上述 $n$ 组中每组选一个使得选择数之和是 $2n$ 的倍数。 你需要选择一个角色扮演并获胜。 ====题解==== * $n$ 为偶数，根据奇偶分析可以得到 $$\frac{n(n+1)}{2} \equiv \frac{n}{2} \pmod n$$ 只要按照 $(i, i + n)$ 的方式分，就可以保证结果在模 $n$ 意义下不为 $0$，那么在模 $2n$ 意义下更不可能为 $0$，因此选 A 必胜。 * $n$ 为奇数，对于 A 给出的一种方案，我们将每组之间的两点连红边，在 $(i, i + n)$ 之间连蓝边，如下图所示，那么我们黑白染色后选黑点，可以发现选的所有点在模 $n$ 意义下两两不同，根据奇偶分析，有 $$\frac{n(n+1)}{2} \equiv 0 \pmod n$$ 因此选 A 必胜。{{:2020-2021:teams:farmer_john:jjleo:cf1404d.png?600|}} =====CF1404E===== ====题意==== 给定一个 $n \times m$ 的方格图，分黑白格，要求用 $1 \times x$ 和 $x \times 1$ 的砖块铺满所有黑格，白格不能放砖，且所有砖不能重叠，问最少需要多少砖。 ====题解==== 考虑一开始一个黑格放一个砖块，然后进行合并，砖块不能拐弯合并等价于求如下二分图的最大独立集。{{:2020-2021:teams:farmer_john:jjleo:cf1404e.png?400|}} =====CF1406D===== ====题意==== 给定一个序列 $a_i$，将其拆分成两个序列 $b_i$ 和 $c_i$，要求满足 $a_i=b_i+c_i$，且 $b_i$ 递增，$c_i$ 递减。求 $\max(b_i,c_i)$ 的最小值。多组询问，每次对 $a_i$ 进行区间加。 ====题解==== $\max(b_i,c_i)$ 等价于 $\max(b_n,c_1)$，在 $b_1$ 和 $c_1$ 固定时，$b_i$ 的增量越少越好，所以如果 $a_i > a_{i-1}$，那么将多的部分加到$b_i$ 上面，否则将多的部分减到 $c_i$ 上面。因此答案为 $$\max(b_n,c_1)=\max(x+\sum_{i=2}^n\max(0,a_i-a_{i-1}),a_1-x)$$ 设 $y=\sum_{i=2}^n\max(0,a_i-a_{i-1})$，则答案为 $\max(x+y, a_1-x)$，直接取 $x=\lfloor \frac{a_1+y}{2} \rfloor$ 即可。 修改时，区间加只会改变两个点的差分值，因此可以 $O(1)$ 维护。 =====CF1418E===== ====题意==== 有 $n$ 个怪，每个怪物有一个攻击力 $d$。有 $m$ 个武器。每个武器有两个属性，耐久度 $a$ 和 防御值 $b$。对于一个打怪顺序，按顺序处理每一个怪： * 如果当前耐久度为 $0$，那么会受到 $d$ 点伤害。 * 如果当前耐久度不为 $0$，如果 $d \ge b$，那么令 $a$ 减少一，否则无事发生。 对于每个武器，所有 $n!$ 种打怪顺序出现概率相等，求期望收到的伤害。 ====题解==== 考虑先把所有怪按攻击力排序，那么对于一个武器，设 $d \ge b$ 的怪物有 $x$ 个。那么对于这 $x$ 个怪物，他能造成伤害当且仅当他前面至少有 $b$ 个怪物属于这 $x$ 个怪物，概率为 $\frac{x-b}{x}$；对于剩下 $n - x$ 个怪物，他和上述 $x$ 个怪物的相对顺序相当于插空，他能造成伤害当且仅当上述 $x$ 个怪物至少有 $b$ 个在它前面，概率为 $\frac{x+1-b}{x+1}$。 期望还需要乘以怪物他们自己的攻击力，上述 $x$ 个怪物和 $n-x$ 个怪物分别是一个后缀和前缀，因此求个前缀和乘上即可。 =====CF1418F===== ====题意==== ====题解==== =====CF1418G===== ====题意==== 给定一个序列，问有多少个连续的子序列其中每个数字都恰好出现了三次。 ====题解==== 那么从左往右扫一遍利用线段树维护以当前位置为右端点有多少合法的左端点，对于每个数，将对于他来说不能选的区间覆盖，能选的区间消除覆盖，这样所有覆盖次数为 $0$ 的下标即看成为合法左端点。处理出每个位置往左第 $i(1 \le i \le 3)$ 次出现的位置 $p_i$，那么 $[1,p_3]$ 无法选，覆盖一次；$[p_1, i]$ 是新产生的不能选的区间，覆盖一次；$[p_3 + 1, p_2]$ 可以选，取消覆盖一次。 使用标记永久化（不下传）即可完成。 =====CF1419F===== ====题意==== 二维平面上 $n$ 个点，如果两个点的横坐标或纵坐标相同，那么可以在它们之间连边，边的长度为两者距离之差。现在可以额外添加一个点，问能否使图联通，如果可以，所有边最大值的最小值是多少。 ====题解==== 二分答案 $\text{mid}$，那么所有横坐标相同或纵坐标相同且距离不超过 $\text{mid}$ 的点之间可以连边。我们对连通块的数量分类讨论： * 1 个连通块，当前情况直接合法。 * 2 个连通块，直接枚举两个点，如果两个点属于两个连通块且它们距离不超过 $2\text{mid}$ 则合法。 * 3 个连通块，新加的点一定与两点共线，这条线与它和第三点连线垂直，且这三个点属于各自的连通块。枚举所有相邻的两点共线的点以及其它单个点，看是否交点满足到三个点距离都不超过 $\text{mid}$。注意上述三个点要属于三个连通块，且前者只需要枚举相邻的即可，因为如果不相邻两者距离肯定已经超过 $2\text{mid}$。 * 4 个连通块，类似 3 个连通块，只不过变成了四个点所连成的两条线段相交，二重枚举垂直和水平的相邻连线判断即可，注意这四个点要属于不同的连通块。 * 连通块数量如果超过 4，无解，因为加一个点最多能连四条边。 时间复杂度 $O(n^2)$。 =====CF1420E===== ====题意==== 给定一个 $\texttt{01}$ 串，每次操作可以交换相邻的两个 $\texttt{0}$ 和 $\texttt{1}$，问至多操作 $0$ 到 $\frac{n(n-1)}{2}$ 次，两者中间至少有一个 $\texttt{1}$ 的 $\texttt{0}$ 的对数最大值。 ====题解==== 答案等于任意选 $\texttt{0}$ 的对数减去在连续 $\texttt{0}$ 段选的对数。 设 $pos_i$ 为第 $i$ 个 $\texttt{1}$ 的位置，一共有 $cnt$ 个 $\texttt{1}$，$f_{i,j,k}$ 表示第 $i$ 个 $\texttt{1}$，已经到第 $j$ 位，操作了 $k$ 次需要减去的对数的最小值，有如下转移方程：$$f_{i,j,k}=\min_{t=0}^{j-1}(f_{i - 1,t,k - |pos[i] - j|} + \frac{(j - t - 1) * (j - t - 2)}{2})$$ 对于每一个状态，最后还要减掉最后的一段 $\texttt{0}$，即为 $$ans_i=\frac{(n - cnt)(n - cnt - 1)}{2} - \min_{j=1}^{n}(f_{cnt,j,i}+\frac{(n - j)(n - j - 1)}{2})$$ 时间复杂度为 $O(n^4)$。 =====CF1416D===== ====题意==== 给出一张无向图，一开始第 $i$ 个点上面写着数字 $i$，有如下两种操作： * 输出点 $x$ 所在连通块里面写着数字最大的点上面的数字，并将其改为 $0$。 * 删除一条边。 ====题解==== 考虑逆向过程，将删边改为加边，建出 Kruskal 重构树，非叶节点的权值代表子树中是第 $i$ 次删边操作前可以到达的连通块，之后倍增找祖先再套一个线段树维护 dfs 序，维护最小值和修改最小值即可。 =====CF1408E===== ====题意==== $m$ 个集合，里面放 $1$ 到 $n$ 的正整数。对于集合 $i$，如果里面有元素 $j$ 和 $k$，则在它们之间连一条颜色为 $i$ 的边。删除集合 $i$ 里面的数 $j$ 需要耗费 $a_i + b_j$ 的金钱，问使图不存在所有边颜色均不相同的环最少需要耗费多少钱。 ====题解==== 新建 $m$ 个点代表每个集合，将集合里每个元素像对于集合代表的点连边，可以发现这样构造后原图有彩虹环等价于新图有环，直接求最大生成树即可，然后用总权值减去生成树上的边权之和。 =====CF1408G===== ====题意==== ====题解==== =====CF1408H===== ====题意==== ====题解==== =====CF1408I===== ====题意==== ====题解==== =====CF1422D===== ====题意==== ====题解==== =====CF1422F===== ====题意==== ====题解==== =====CF1430F===== ====题意==== ====题解==== =====CF1430G===== ====题意==== ====题解==== =====ABC178F===== ====题意==== ====题解==== =====ABC179D===== ====题意==== ====题解==== =====ACL1B===== ====题意==== ====题解==== =====ACL1A===== ====题意==== ====题解==== =====ACL1D===== ====题意==== ====题解==== =====ACL1E===== ====题意==== ====题解==== =====ABLF===== ====题意==== ====题解==== =====ARC104D===== ====题意==== ====题解==== =====ARC104E===== ====题意==== ====题解==== =====ARC104F===== ====题意==== ====题解==== =====HHKB2020D===== ====题意==== ====题解==== =====HHKB2020F===== ====题意==== ====题解==== =====ARC105D===== ====题意==== ====题解==== =====ARC105E===== ====题意==== ====题解==== =====ARC105F===== ====题意==== ====题解====