贪心

发现自己贪心跟没学一样, 完全不会.

贪心 做题笔记

题库里筛选greedy, 2600, 通过人数降序.

1400E Clear the Multiset

给定 $1\ldots n$ 每个数的个数 $a$ , 每次给一个区间个数减1或对一个数减去任意, 求清空次数. $n\le 5000, a_i\le 10^9$

“能大力dp的谁贪心啊” –qyc

好像给人感觉很经典.

很能dp, $f_{i, j}$ 表示前 $i$ 个数, 有 $j$ 个区间操作延伸到 $i$ 清空的最小代价. 复杂度 $n^2$ .

好吧, 贪心就是, 每次大力给全局减掉全局最小值, 然后全局裂开成若干区间, 再递归下去做, 如果这么算出来的答案大于区间长度直接变成区间长度(全用单点)

1537E2. Erase and Extend (Hard Version)

给定一个字符串, 可以任意多次删掉末尾字符或者把当前字符串复制一份接在后面, 求能得到的字典序最小的, 长度恰好为 $k$ 的字符串.
$n, k\le 5\times 10^5$

切不动2200了? !

结论是最优解一定先用删再用复制. 考虑我们一定是先删后复制不劣于先复制后删, 也就是一个前缀反复复制, 做完了.

1333F. Kate and imperfection

对所有 $k\in [1\ldots n]$ 求出 ${1\ldots n}$ 的大小为 $k$ 的子集中最小的值, 一个子集的值为这个子集的任选两个不同的数 $a, b$ 的 $\gcd$ 的最大值.
$n\le 5\times 10^5$

$1\ldots n$ 选出互质的 $k$ 个数的做法是什么? 选所有质数.

那现在允许 $\gcd \le c$ 怎么办? 猜测一定是在之前的基础上加. $c=2$ , 发现可以再插入4, $c=3$ 则可以插入6, 9, $c=4$ 可以插入8, $c=5$ 可以插入10, 15, 25, $c=6$ 可以插入

发现一个数会在 $c$ 为自己除以自己最小质因子的时候被插入. 于是结束了.

证明是, 考虑当前集合中若有 $a\bmod b=0, a>b$ , 我们一定删 $a$ 而不是 $b$ . 由此得到一个数在集合的时候自己的所有因数一定在集合里. 于是就是这个结论了.

1474D Cleaning

你有一个长度为 $n$ 的数组 $a$ .
现在要进行一些操作将数组的所有元素清除:

选定两个下标连续的数, 若两个数均不为 $0$ , 则将两个数均减 $1$ .
在此之前, 你可以使用一次超能力(可以不使用): 任选两个下标连续的数并交换.

编写程序, 判断是否可以清空 $a$ 数组.
多组询问
$T\le 10^4$ , $\sum n\le 2\times 10^5$

如果不交换是简单的, 从第一个开始考虑容易的出限制是 $a_i\ge c_i= \sum a_k\times {(-1)}^{i-k+1}$ , 当 $i=n$ 时需要是相等.

考虑交换两个数 $a_i, a_j, i<j$ 后, 实际上是对所有 $n>j$ 交换了这两个数的符号, 对 $i$ 来说 $c_i$ 符号取反加上 $a_j$ , $a_j$ 减去 $a_i$ 再取反.

所以我们统计出 $c_i$ , 然后考虑再每个位置交换即可. 如果我来拍上去一棵线段树就是区间加, 单点改, 区间最小值.

哦你发现不对劲, 后面不是区间加, 因为是给一些位置加上他俩的差, 另一些位置减去.

如果我不拍线段树, 是不是就是统计一下后缀min之类的结束了啊.

所以为什么是贪心标签呢?

CF1092D Great Vova Wall

合并了

(Version 1)

给定序列 $a$ , 你可以给相邻相等的两个数加1或给任意位置加2, 求是否可以若干次操作后让所有位置相同.
$n\le 2\times 10^5, a_i\le 10^9$

看着很想JOI的俄罗斯方块题? 但这个不能悬空.

$f_{i, 0/1, 0/1}$ 表示前 $i-1$ 个为膜 $2$ 余 $0/1$ , 其中最后一个膜 $2$ 余 $0/1$ 是否可以. 转移是是否在最后一个位置放一个.

这个做法成功给做Version2给出负效果. . .

我们已经发现是膜2意义下的, 那么就成了给定01串, 可以翻转相邻两个, 问最后能否弄成一样的.

这种套路其实是括号序, 我们可以翻转任意偶数长度的段, 那么从左往右扫去匹配高度相等的即可.

(Version 2)

版本1的基础上没有给任意位置加2操作.

向上次一样设状态现在会爆炸了.

好吧别dp了, 还是看看可爱的贪心吧.

模仿刚才的栈的做法的话其实只是相当于出栈时这一次的要不低于上一次的. . . 并且要特判 $n$ 为奇数的情况最后一个是否能行.

哦, 另一个更无脑的做法是从下往上扫描线, 每次碰到一个连续段如果长度为奇数就寄, 否则就加一继续扫. 用set维护连续段是 $n\log n$ .

CF1428E Carrots for Rabbits

给 $n$ 个胡萝卜, 再 $n-k$ 次选出一个胡萝卜切一刀成俩, 最小化最后所有胡萝卜平方和.

猜测最后所有胡萝卜大小一定是相邻的两个数, 不对. 因为可能让你切不到相邻的两个数.

但同一段萝卜肯定是切到相邻的两个数吧? 所以我们现在问题是不知道给那些萝卜切几段.

你随便写写式子, 给一个长 $n$ 萝卜切 $k$ 段连续情况代价是 $\dfrac{n^2}{k}$ 是凸且单减的, 然后发现离散也对, 所以开个堆每次取最大的给他多切一刀再塞回去即可.

CF1406D Three Sequences

给一个长 $n$ 序列 $a$ , 区间加, 每次操作后询问, 把 $a$ 拆成 $a_i=b_i+c_i$ , 且 $b$ 不增, $c$ 不降, 求最小的 $\max(b_i, c_i)$ .

考虑直接差分, 就是给定序列 $a$ , 构造 $b$ 和 $c$ 使得 $a_i=c_i-b_{i+1}$ 且 $b_{i+1}>0, c_i>0$ , 最小化 $\max(\sum b_{i+1}, \sum c_i)$

你发现如果 $a_i>0$ , 那么一定让 $c_i=a_i$ , 否则 $b_i=-a_i$ , 否则会同时增加 $b_i$ 和 $c_i$ .

转化回来其实就是若 $a_{i+1}<a_i$ , 则 $b_{i+1}=b_i+(a_{i+1}-a_i)$ , 否则 $c_{i+1}=c_i+(a_{i+1}-a_i)$

那么问题就是 $b_1$ 和 $c_1$ 了, 由于加起来是一定的所以直接越近越好. 做完了.

CF1599J Bob’s Beautiful Array

你有一个长度为 $n$ 的数组 $a$ , 你需要构造一个长度为 $n$ 的数组 $b$ , 使得 $a$ 中每一个元素都能由 $b$ 中两个位置不同的元素相加得到.
$n\le 10^5, a_i\le 10^9$

好神奇

特判 $n=2, n=3$

如果有一个偶数一定可以: 考虑我们只要构造出 $3$ 个数可以得到 $a$ 中3个数, 剩下的就可以随便弄了, 这是个三元一次方程, 发现我们选的 $a$ 中三个数只要满足都是偶数或一个偶数两个奇数都是有整数解的, 所以就成功了.

于是考虑全是奇数的情况: 我们考虑如果最终答案 $b_1\ldots b_n$ , 若 $b_i+b_j$ 是 $a$ 中的数就连一条边, 显然它至少得有 $n$ 条边, 那么就有一个环, 环的大小必须是偶数(因为 $a$ 中数都是奇数), 并且这个环的边黑白染色后和相等. 所以猜测有解条件是 $A$ 中能选出两个集合 $S, T$ 和相等. 然后再正着去构造证明: 如果有这样两个集合, 我们把它交错的插开推推式子发现一定没问题, 于是剩下的随便弄即可了.

所以现在要判断是否有两个这样的东西了, 众所周知subset sum指数, 要点在于当 $n\ge 28$ 时, $\binom {28}{14}>14\times 10^6$ , 根据鸽子原理一定有解. 所以只取28个, 折半爆搜即可.

太脑洞了构造题.

CF175E Power Defence

一个塔防游戏: 给定一个无限长的数轴, 一个无限血的敌人要从正无穷走到负无穷. 你的任务是放置三种塔, 包含两种攻击塔和一种寒冰塔, 使得敌人受到的伤害最大.

其中, 每种塔的攻击半径可能不同, 每种攻击塔的攻击力也可能不同. 而寒冰塔没有攻击力, 它的作用是使范围内敌人的速度减速, 即一段区间若有 $k$ 个寒冰塔覆盖, 敌人速度变为 $\frac{1}{k+1}$ . 同一个位置只能放两个塔.

敌人初始速度为1格每秒, 攻击塔的伤害值也是以秒计算的.

三种塔数量总和不超过20.

首先体会一下如果没有一个位置只能放俩的性质, 最好的方案是全部堆到一个点上. 由这个大概可以想到, 最终局面是堆在一起的一排, 长度最大为 $\lceil\dfrac{n}{2}\rceil+1$ (就是中间摆满, 然后两边各伸出一个位置).

然后发现安排位置好困难, 根本不会, 看题解, 啥? 塔只有20个? /qd

直接枚举冰塔的方案(每个位置放0/1/2个), 方案是 $3^{\dfrac{n}{2}}$

现在有一些空位, 可以求出每个位置放每种塔的伤害.

此时还不能直接从高往低放. . . 暴力dp它, $f_{i, j, k}$ 表示前 $i$ 个, 放了 $j$ 个第一种攻击塔, $k$ 个第二种攻击塔的伤害, 复杂度是 $3^11\times 20^3$ 有点大.

我们的问题在于 $j+k\ne i$ 是吧, 想想怎么能让他放满一点, 如果给每个位置按照放第一种攻击塔的收益排序, 前面一段是放满的, 后面一段是不算前面放的情况下的前 $k$ 大.

那么这样dp, 省掉一维, 然后再枚举前面最长的一段放了多少即可. 用set从后往前扫一遍即可.

看一眼另一篇题解, 猜完连续的结论后直接模拟退火

CF935F Fafa and Array

给定一个长 $n$ 序列 $f(A)=\sum_{i=1}^{n-1} \vert a_{i+1}-a_{i} \vert$ .
区间加, 或者给定一个区间和 $x$ , 询问给定区间中给一个数加上 $x$ 后 $f(a)$ 最大是多少. 询问独立.
$n, q\le 10^5, a_i\le 10^9$

数据结构题混到greedy.

差分. 数组叫 $c$

按贡献算, 若 $c_i>0, c_{i+1}<0$ , 贡献显然为 $2x$
若 $c_i, c_{i+1}$ 同号, $y$ 为 $\max(-c_i, c_{i+1})$ , 贡献为 $\max(0, x-y)$
若 $c_i<0, c_{i+1}>0$ , 贡献是写着很麻烦, 但也是分段一次函数.

于是你准备离线后按 $x$ 排序, 拍上去一个 $KTT$ .

然后你冷静一下想一想, 斜率只有 $-2, -1, 0, 1, 2$ 5种. 开线段树分别维护区间最大截距即可. 支持单点修改和区间查询.

一个不这么野蛮DS的方法是, 考虑其实第一种贡献直接出, 第二种贡献只要求最小的 $y$ , 第三种贡献才不会做. 那么一个区间内最多有一个第三种情况, 否则必然有一个第一种情况况. 于是单独维护所有这样下凹的位置即可.

CF30D King’s Problem?

给定 $x$ 轴上 $n$ 个点和轴外一个点, 求从点 $k$ 出发把他们全部走一遍(可以重复走)的最短路径长度. $n\le 10^5$

考虑如果从轴外那个点出发要么从最左走到最右要么从最右走到最左.

于是只要考虑在轴内的情况下了. 此时我们的问题是什么时候走那个外面的点不知道. 于是直接枚举什么时候过去的然后 $O(1)$ 算一些距离即可.

CF758E Broken Tree

给定一棵有根树树, 每个边有一个重量和一个硬度, 如果一棵树的一条边下面的儿子中的边的重量和大于它的硬度树就寄了, 你可以把一条边的硬度和重量减去一个相同的值, 但必须保证重量为正整数硬度为整数, 求让树不会寄的最大的重量.
$n\le 2\times 10^5$

性质是一棵子树的重量是一个区间, 考虑我们求出最重的那种然后从深度大的开始减是没问题的. 主要在于重量最小的一定是从下往上把所有能减的都减掉得到的重量.

考虑dp出所有子树的区间, 最小的很显然, 最大的大概是考虑在所有子树都最小的基础上还能增加多少重量.

这样求的是最后的最大值. 输出方案很烦人, dp时记一下最大/最小的时候这条边减去多少以及当前状态比所有子树都最小的基础上增加了多少. 因为一个点的儿子最后的情况一定是若干最小的若干最大的和一个不满的, 这个用来算那个不满的.

考虑一条边的限制实际上是限制自己的子树重量不超过什么, 那么从深度大的开始调整一定不劣, 每次会让若干点满足限制, todo

CF1651E Sum of Matchings

给定一个每个点度数都是2的二分图, 左右两侧点分别标号 $[1, n]$ , $[n+1, 2n]$ , 求对于所有 $1\le l\le r\le n<n+1\le L\le R\le 2n$ , $l, r, L, R$ 四元组, 求 $[l, r], [L, R]$ 中的点的导出子图的匹配之和.
$n\le 10^5$

突破点在度数是2上. 所以每个点都恰好在一个环中, 即环互不相交. 每个环互不影响. 此时一个环贡献的匹配数是环长除以2.

而现在两边各截取出一段, 可能有一些环变成了若干个链, 但发现链也是互不相交的. 分别考虑发现每条链的贡献是长度除以2下取整.

于是这样一个导出子图都答案是 $(点数-奇数长度链的个数)/2$ .

那么因为 $n$ 很小, 可以直接遍历图的每一个环的每一个区间, $O(1)$ 计算它会被多少区间包含即可.

CF1661F Teleporters

给定数轴上 $n$ 个点和 $m$ , 要再建立若干点, 使得存在一条路径 $a_1\ldots a_n$ 的 $\sum {(a_i-a_{i-1})}^2\le m$ . 求最少再建几个点.
$n\le 2\times 10^5, a_i\le 10^9$

显然可以每一段单独考虑, 在这一段里再建 $k$ 个显然让它平均分布, 因为这个平方让你想着是不是凸的然后发现是的所以一个堆每次把收益最大的拿出来加一就好了. 你以为做完了. 发现可能答案会很大就寄了.

考虑二分每一段收益减到多少我们就不干了, 就是说我们给一段不断加点知道它再加的收益小于我们二分的常数 $x$ 就不加了, 这样就可以直接根据 $x$ 在每一段再二分加了多少次, 得到一段的解, 然后就做完了. 最后需要处理一些边界条件.

CF37E Trial for Chief

给一个 $n\times m$ 黑白两色的网格图, 要全染白, 每次把一个连续颜色块反色, 求最少次数. $n, m\le 50$

idea是不是借鉴于拿着油漆桶在画图上一直点的那种感觉.

考虑如果你摁着一个点一直点, 这样一层一层下去, 到最后一层就完成了.

这个东西等价于把相邻两个点同色连边权为0, 不同连1, 然后以这个点跑最短路. 得到的最远的黑点.

但有没有可能我们不摁着一个点涂色呢? 考虑交换所有操作的顺序使得每个涂色都是在涂色点和第一次点的点连通后再做, 就和一直按着一个做一样了. 一定是可以这么调整的原因在于做这个的时候必然不连通, 会相互影响的讨论一下一定是一样的. 所以我们一定可以摁着一个点涂色.

于是直接对每个点跑一遍dij或01bfs就结束了.

CF1599A Weights

给定序列 $a_{1\ldots n}$ 和由 $\texttt{LR}$ 组成的长 $n$ 字符串 $S$ , 两个集合 $L, R$ 初始为空, 要求给一个方案使得我们第 $i$ 次选择一个数添加进去后集合 $S_i$ 更大.
$n\le 2\times 10^5, a_i\le 10^9$

我们首先考虑一个比较显然的事情, 如果 $a$ 从小到大排序后轮流往两个集合里放, 那么显然每次都是刚放完的那个集合更大.

于是考虑在这个基础上, 如果我们删掉最大的一个一定会切换, 而删掉最小的那个不会切换, 且始终保持交错的性质, 于是直接倒着做, 不断删最大或最小的即可.

[think] 保持性质构造方案; 倒序

CF1257G Divisor Set

给定一个 $n$ 个元素多重集, 求最大的子集族使得族内任意两子集没有包含关系. $n\le 2\times 10^5$

孤陋寡闻, 学到了Sperner定理.

在不是多重集的情况下, 就是Sperner定理, 内容就是对于 $n$ 个元素集合从中选出最大的彼此无包含关系的子集族中子集的数量为 $\binom{n}{\lfloor \dfrac{n}{2} \rfloor}$ . 构造解只需选出所有大小为 $\lfloor \dfrac{n}{2} \rfloor$ 的子集.

那么在是多重集的情况下显然会出问题. 考虑其中两个集合 $S\subseteq T$ , 那么因为 $\vert S \vert = \vert T \vert$ 所以 $S=T$ , 也就是说除了两集合相同的情况否则不会出现包含.

结论是去掉所有重复的之后就是正确答案, 还是要锻炼猜结论的能力啊.

如果不知道Sperner定理, 应该通过大小相同的不同集合不会互相包含得出选大小相同的构造, 然后去猜大小为 $\dfrac{n}{2}$ 的最多吧, 这一步可以打个表.

然后要统计所有大小为 $n$ 且本质不同的子集数, 单选多重集中一个元素的式子是 $1+x^2+x^3\ldots$ , 然后把它们都卷起来就好了. 复杂度 $n\log^2 n$

贪心只能过样例

qyc搬的题
有两只队伍滚榜, 已知他们封榜前的过题数和罚时, 也知道封榜之后的过的 $n$ 个题和对应罚时, 要求一个滚榜顺序使得第一名变化次数最多.
$n\le 10^5, v\le 10^9$ , $v$ 表示除了 $n$ 的其他所有数字.

贪心, 结论是把两只队伍的罚时一个从小到大一个从大到小排序, 然后模拟

怎么回事呢? 可以考虑这个结论在一开始没有过题和罚时的情况下一次一换的.

数学上来先打表

有 $n$ 个数列 $a$ , 求数列 $b$ , 使得 $\sum a_ib_i-\max a_ib_i$ 最大. 多测, $n\le 20$ , $\sum n\le 10000$

看一眼样例, 第一个样例是直接给最大和次大的 $a_i$ 分配 $b_i$ 使得他们 $a_ib_i$ 相等, 后面的没算出来.

于是直接猜这个, 过了前两个第三个寄了.

又想一想这个东西是线性规划, 不会写单纯形, 于是一个假单纯形上去TLE30.

原来是贪心, 如果我们分配的时候最大值 $a_ib_i$ 只有一个, 把它调小一定更好. 于是一定有若干个相同的最大值 $a_ib_i$ .

然后你发现, 在不止一个最大的 $a_ib_i$ 的情况下, 如果一个 $a_ib_i<a_jb_j$ , 那么把 $b$ 分配到更大的 $a_i$ 一定可以让它更好.

所以我们最后的样子是有若干个相同的数. 且对应的 $a$ 一定是前若干大.

那么只要枚举选前几大再解个小方程即可.

CF1592F Alice and Recoloring

合并了

给定一个 $n\times m$ 01网格, 你可以进行4个操作, 将其变全0:

  1. 翻转一个包含 $(1, 1)$ 的矩形
  2. 翻转一个包含 $(n, 1)$ 的矩形
  3. 翻转一个包含 $(1, m)$ 的矩形
  4. 翻转一个包含 $(n, m)$ 的矩形
    求最小代价.
    $n, m\le 500$ .

F1

四个操作代价分别为 $1, 2, 4, 3$ .

可以证明2, 3操作绝对不会用, 因为可以被替代为两次1操作.

对于4操作是4次1操作, 所以有可能用到4, 但3次1操作的效果是4的效果再翻转全局, 所以可以认为4操作只会用一次, 如果用两次就可以都替换成3次1操作.

因为矩形操作比较复杂, 考虑差分. 若原网格为 $a$ , 设 $s_{i, j}=a_{i, j} \mathrm{xor} a_{i+1, j}\mathrm{xor}a_{i, j+1}\mathrm{xor}a_{i+1, j+1}$ , 目标状态显然仍是全0, 这样可以使得1操作变成单点修改.

而对于4操作, 变成4次单点修改, 那么只要枚举4操作操作在哪, 剩下全用1操作即可. 复杂度 $nm$

F2

四个操作代价分别为 $1, 3, 4, 2$ .

2, 3操作仍然是来充数的.

但现在4操作可能被用多次了, 需要再分析:

1. 设4操作翻转 $x, y, n, m$ , $P(x, y)$ , 则不会对同一行或同一列的 $P$ 都用4操作.

因为这样4个单点修改中有两个被翻转两次抵消了, 所以实际上只修改了两个, 可以用1操作代替.

2. 仅当4操作的单点修改中除了点 $(n, m)$ 外3个都是1时会操作

如果有2个, 翻完还要再搭一次操作1, 那么反而比直接1更糟糕.

在此基础上我们希望4操作尽可能多, 那么我们算整张网络最多进行多少次, 发现是一个二分图匹配: 每一行列建点, 对于满足要求2的4操作 $P$ 由行向列连边跑网络流即可.

剩下的每一个用一个1操作即可. 复杂度 $n^2\sqrt n$

CF1158D Winding polygonal line

给定平面上 $n$ 个点和 $\texttt{LR}$ 构成的长 $n-2$ 的字符串, 求一条不自交路径经过每一个点一次, 且第 $i+1$ 个点是在 $i-1$ 到 $i$ 的基础上忘 $s_i$ (左或右)的方向拐的.
$n\le 2000$

好厉害构造题.

任选一个凸包上的点, 如果下一次是 $\texttt{L}$ 那就选当前向右转最后碰到的点, 否则是向左转最后碰到的点, 就对了.

原因是, 考虑一开始在凸包上, 那么若下一次是在左边, 我们向右转到的点无论到哪个剩下的点都是往左转的且不会自交, 因为当前点到下一个点的连线一定在剩下所有点的一侧.

CF1380G Circular Dungeon

简单题

在游戏中, 有 $n$ 个排列在环上的房间, 第 $i$ 个房间只能到达第 $i+1$ 个房间(特别地, 第 $n$ 个房间只能到达第 $1$ 个房间).

同时有 $n$ 个宝箱, 第 $i$ 个宝箱的价值是 $c_i$ , 其中恰好有 $k$ 个宝箱是假宝箱, 其余均为真宝箱, 每个房间有且仅放置一个宝箱.

玩家等概率地从 $n$ 个房间中选取一个房间开始移动, 如果当前房间有真宝箱, 他将获得此宝箱的价值, 否则立刻结束游戏. 最后获得的总收益等于之前收集的宝箱的总价值.

对于每一个 $k\in[1, n]$ , 你可以决定宝箱的排列顺序和宝箱的真假, 使玩家收益的期望值最小, 请求出最小的期望值 $\pmod {998244353}$ .
$n\le 3\times 10^5$

首先把最大的 $k$ 个变成假的, 显然.

然后假的把真的分成若干段, 对于每一段显然是递减的.

然后再考虑一下会发现平均分配好过不平均分配.

然后再考虑一下发现不仅每一段递减, 实际上递减顺序是, 每一段第一个>每一段第二个. . . , 于是直接顺着放即可.

CF725E Too Much Money

给定常数 $c$ 和 $n$ 个整数, 每个数只能用一次, 求加到 $c$ 的一个方案. 求法是每次选择不超过 $c$ 的最大的加进去, 那么现在让你再添加任意多个数hack它, 或者判断hack不掉, 最小化添加的数的和.
$n, c\le 2\times 10^5$

首先, 实际上只会添加一个数

考虑如果添加两个数 $a, b$ , 那么直接添加 $a+b$ 是不劣的.

然后可以暴力判断每一个, 判断方法是暴力查出能加的下一个, 复杂度上对的就直接考虑和为 $c$ 的数有 $\sqrt c$ 种.

CF1500C Matrix Sorting

给定两个 $n\times m$ 的矩阵 $A$ , $B$ , 每次可以选则一列作为关键字把所有行稳定排序, 问是否能通过至多5000次操作把 $A$ 变成 $B$ .
$n, m\le 1500$

排序过程实际是指定了第一关键字第二关键字. . . 这样的.

添加值为 $A$ 矩阵编号的一行可以让初始矩阵转化成一次排序操作.

显然如果末状态相邻两行关系是对的则整个数组是对的, 考虑一次操作对末状态的相邻两行的大小关系的影响, 可能是变成对的, 变成错的, 或者没有影响(对应位置相等). 从后往前考虑操作序列, 如果一个位置之后出现过变成对的, 那前面啥都可以, 否则不能出现变成错的.

于是考虑一个拓扑排序过程, 每个操作建点, 每个相邻两行建点, 若操作可以把两行变成对的就操作连向点, 变成错的点连向操作, 那么一个操作可以选就当且仅当所有入边都被消了, 就是对的了.

复杂度 $nm$

CF1700F Puzzle

给定两个 $2\times n$ 01矩阵 $a$ , $b$ , 每次交换 $a$ 中相邻两个数, 问让 $a$ 变到 $b$ 的最少步数.
$n\le 2\times 10^5$

先考虑只有一行的情况, 发现我们可以对每一个相邻对的交换次数分别计算, 设 $sa_i$ 为 $a$ 前缀和, $sb$ 同理, 则 $i, i+1$ 两个数会交换 $\vert sa_i-sb_i\vert$ 次.

那么现在有了第二行前缀和加上一维0/1表示行, 考虑如果对于一个位置, $s_{a, 0}>s_{b, 0}, s_{a, 1}<s_{b, 1}$ , 那么显然我们应该换到下面去一个1来省一次, 往上换的同理, 就做完了.

重点在于这样一种运行到后面我们再考虑一开始是不是换一下这种思想?

CF1685C Bring Balance

给定一个括号序列, 每次可以翻转一个区间, 求最少的操作次数使得括号串合法. 保证左右括号数量相等.
$n\le 2\times 10^5$

考虑画出折线图, 那么一次翻转是把一个区间的折线中心对称. 要让折线对称后全在x轴上方, 则设最高点值为 $a_p$ , 左右端点为 $a_l, a_r$ , 翻转后显然要求 $a_p\le a_l+a_r$

于是用经典套路是只会进行一两次, 发现如果整个序列有一个非常非常高的你可能一次干不掉, 但以这个为端点左右两次一定都没问题所以最多只会进行两次.

此时怎么构造也显然了.

CF1373G Pawns

$n\times n$ 的棋盘, 第 $k$ 行是特殊行, $(i, j)$ 位置可以走到 $(i-1, j+1), (i, j+1), (i+1, j+1)$ 棋子不能重叠, 要所有棋子都移动到第 $k$ 行, 问最少要再右侧添加多少列.
多次询问, 每次切换棋盘上一个位置是否有棋子.
$n, q\le 10^5$

首先你想一想发现棋子 $(i, j)$ 走到第 $k$ 行位置就是 $(k, j+\vert i-k\vert)$ , 于是就成了一个数轴上的问题了.

不想动脑子, 于是直接 $f_i$ 表示还有几个棋子最后要停到 $i$ 右边去, $f_i=f_{i-1}+a_i-1$ , 直接另 $a_i$ 减1, 变成一个模板ddp.

然后动动脑子, 发现自己是智障这其实是最大后缀和/kx

CF1348F Phoenix and Memory

问是否存在唯一一个 $1 \ldots n$ 的排列 $c$ , 满足 $a_i \leq c_i \leq b_i$
$n\le 2\times 10^5$

简单题?

考虑从最小的往大考虑, 显然你会选左端点最小的并且此时右端点最小的一定不劣, 然后再往上加一, 反正每次选能选的里面右端点最小的, 就是一个合法方案.

那么如何判断方案是否唯一呢?

如果有两个区间一致, 显然有第二小的, 于是考虑互不相同的.

那么如果方案不唯一, 至少有两个方案, 那么就是说我们过程中有一次, 不选右端点最小的也成, 比如选第二小的, 那么以后最优策略仍然是选最小的, 那么我们下一个数一定选刚才没选的那个, 接下来情况相同, 所以我们交换了两个数, 所以若方案不唯一, 我们最终一定可以交换值域上两个数得到第二个构造.

于是对于每一个元素, 考虑若交换的会怎样, 就是统计序列中有多少个满足另一个元素在当前这个区间并且当前这个区间包含另一个元素的, 这是个静态三维数点, 2log.

然后你想一想, 其实可能没必要这么多限制, 假设我们枚举的是大的那个数, 那么另一个数只要满足小于大的并且另一个数的限制右端点不小于当前数, 就只有两维了. 1log.

CF1584F Strange LCS

给定 $n$ 个英文字母(大写小写)字符串, 每个字符在每个字符串最多出现2次, 求最长公共子序列. $n\le 10$ .
多组询问, $t\le 5$

考虑每个字符最多出现一次的情况, 此时字符与位置一一对应, $f_i$ 表示字符 $i$ 结尾的答案, 则有 $f_i=\max f_j+1$ , 在所有字符串中 $j$ 均出现在 $i$ 前.

现在每个字符可以出现两次, 当我们仍想这么干的时候不知道 $i$ 哪些在前面哪些在后面, 那就再加一维直接记每个 $i$ 是第一个或第二个. 转移仍是枚举所有出现位置都在字符 $i$ 前的. 这样复杂度是 $4^n\times 52^2$ 之类的.

你发现, 对于每一个 $s$ , 如果字符 $c$ 两次出现都在 $i$ 前面, 从第二次出现转移一定不劣, 这样我们就只用枚举上一个字符是谁了, 复杂度大概是 $2^n\times 52^2n$ 之类的.

CF586C New Language

字符集被分成集合 $V$ 和 $C$ , 给定 $m$ 个限制和一个给定的字符串, 求满足限制, 长度为 $n$ , 字典序大于给定字符串的最小字符串, 每个限制是如果第 $i$ 个位置属于 $A$ , 则第 $j$ 个位置属于 $B$ .
$\vert \sigma\vert \le 26, n \le 200, m \le 4n(n-1)$ .

还能比这个限制更2sat提示的吗, 认准为2sat. 要考虑如何解这东西了, 基本上就是贪心, 从前往后每一位选择可能都最小的. 此时在满足2sat的基础上仍然可能有一种情况是, 如果这个位置选了一个啥, 后面虽然有解但可能不满足字典序要求. 但200的话, 是不是暴力验证就好了啊.

CF1539F Strange Array

给定长 $n$ 的数组 $a$ , 对每一个 $a_i$ , 可以选择一个包含它的区间并将区间排序, 设它排序后的位置是 $x$ , 与区间 $[l, r]$ 的中心 $\lceil \dfrac{l+r}{2}\rceil$ 为 $y$ , 则它的奇异值是最大的 $\vert x-y\vert$ .
对每个数求出它的奇异值.
$n\le 2\times 10^5$

比较简单?

先去掉绝对值分正负分别考虑, 现在考虑 $x-y>0$ 的情况:

排完序后它是第几个取决于小于它的数的个数 $cnt$ , 所以奇异值可以看成 $l+cnt-\lceil \dfrac{l+r}{2}\rceil=cnt-\lceil \dfrac{r-l}{2} \rceil$ . 我们要最大化 $cnt$ 减去区间长度.

于是考虑把小于当前数的设为1, 其他的都设为0, 由于再减去一半的区间长度所以每一个都再减去 $\dfrac{1}{2}$ , 那么变成了 $\dfrac{1}{2}, -\dfrac{1}{2}$ 的序列, 可以都乘2变成正负1的序列.

于是就是求包含当前节点的最长子段和, 线段树维护一下即可.

然后因为每个都要求一遍所以要排序后加 $a_i$ , 另外求最大值最小值的时候处理一下等于 $a_i$ 的设成1还是-1即可.

考虑对一个 $a_i$ , 区间往左一位会让值减 $\dfrac{1}{2}$ ,

CF1091F New Year and the Mallard Expedition

你要走过 $n$ 块的地, 每一块可以是水, 岩浆, 或土地, 并且长 $l_i$ 个单位长度, 你可以在水上游泳或飞, 在岩浆上飞, 在土地上走或飞, 走一个单位长度用5s, 游泳3s, 飞用1s, 初始时你有0个体力, 走一个或游一个单位长度会加1, 飞一个会减1, 体力显然不能为负, 求走过这 $n$ 段路的最小时间.
$n\le 10^5$

首先在水上游在土地上走在岩浆上飞, 得到一个答案, 此时可能到了一个地方飞不过去要往回走, 我们看如果前面有过水就游着攒(总可以在第一个水攒够再走), 否则就走着攒.

然后会剩下不少能量, 先让这些能量代替走的, 再代替飞的即可. 但有情况使得有土地但你不能把能量加上去如 $GLWW$ , 若当前能量小于前面的土地长度, 则能加的土地应该是当前能量.

一些类似费用提前延后计算的技巧吧.

CF1699E Three Days Grace

给定 $n$ 个元素的可重集 $A$ , 元素在 $[1, m]$ 间, 每次可以把 $x$ 删掉添加 $p, q$ 满足 $pq=x$ . 求任意操作后集合的极差的最小值.
$n\le 10\times 10^6$
$\sum n\le 10^6, \sum m\le 5\times 10^6$

可以枚举掉一个端点, 比如我们现在求固定最小值的最大值最小.

那么我们要把所有大于最小值的都拆成不小于最小值的值.

设 $f_{i, j}$ 表示 $i$ 拆成不小于 $j$ 的最大因子大小, 发现 $f_{i, j}\ne f_{i, j+1}$ 一定说明最小的因子是 $j$ , 由此则 $f_i$ 是只在所有因数上变化, 总变化次数是调和级数的.

那么如何求得变化后变成啥了呢? 正着转移有点困难考虑从 $j$ 到 $j-1$ , 那么它可以选若干个 $j$ , 所以它的新值就是 $\min f_{i, j}, f_{i/j, j}, f_{i/j/j, j}\ldots$

就结束了.

CF1469F Power Sockets

给出 $n$ 个链分别长为 $l_1\ldots l_n$ , 和一个只有一个节点的树, 每次可以添加一条边把一个链接到树上并且这条边的两个顶点变黑, 可以进行任意次操作, 最小化操作完后第 $k$ 近的白点到根的距离. 不一定要把所有链都接上.
$n\le 2\times 10^5, l_i\le 2\times 10^5, k\le 10^9$

考虑每次挂链显然一定挑重心挂.

另外我们一定从长往短挂, 考虑如果先放了短的再放长的, 则最大深度是长链长度一半加一, 但先放短的就只是长链一半, 所以排完序之后依次加入.

那么如何维护往上挂的这个操作呢? 考虑我们并不关心树的结构, 那么直接开个线段树维护每个深度点的个数支持区间加单点加即可.

同时因为我们挂点一定是从深度小往深度大的挂, 所以可以用差分实现, 因为我们一定是按顺序的, 所以可以一边累加一边做.

CF1430F Realistic Gameplay

有 $n$ 波怪物, 你有一把枪, 枪的弹夹量为 $k$ , 第 $i$ 波怪物数量为 $a_i$ , 在第 $l_i$ 到 $r_i$ 时间出现( $r_i<=l_{i+1}$ ), 你可以在任意时刻打出一发子弹击杀一只怪物且不耗费时间, 你必须在 $[l_i, r_i]$ 时间内消灭 $a_i$ 只怪物, 你每次换弹都需要将弹夹(包括里面的子弹)扔掉, 并花费 1 单位的时间, 在尽量保证通关的情况下, 需要的最少的子弹数为多少.
$n\le 2000, k\le 10^9$

看起来似乎很简单啊, 这个 $n\le 2000$ .

直接dp, $f_{i, j}$ 表示干完前 $i$ 段, 还有 $j$ 个子弹的最小子弹数, 好的 $k\le 10^9$ .

你体会一下发现 $j$ 可能的取值很少, 因为只根最后一次换弹时间有关, 你也可以直接 $f_{i, j}$ 表示走完前 $i$ 段, 最后一次 $j$ 换弹的最小子弹数之类的.

然后看一眼题解, 发现这题可以线性, 说的是, 考虑我们一定是再不换弹就死了都时候才换弹. $f_i$ 表示能走完后面的最小子弹数去转移, 最后扫一遍即可.

CF1572C Paint

给定长度为 $n$ 的颜色序列 $a_i$ , 每次可以选择任意一个颜色全部相等的区间染成另一种颜色, 求全都染成一种的最小代价.
$\sum n\le 3000$

这个题和前面那个黑白格子二维染色的有点像, 但颜色多了, 没有一直在一个地方做的性质了.

注意到一个区间一定可以染色成其右端点的颜色.

于是区间dp它, $f_{i, j}$ 表示把 $[i, j]$ 染色成 $a_j$ 的最少次数, 那么考虑转移:

  • $f_{i, j}=\min f_{i+1, j}, f_{i, j-1} + 1$ , 显然的.
  • $f_{i, j}=\min f_{i, k}+f_{k+1, j}, \ s. t. \ a_k=a_j$

CF1601D Difficult Mountain

$n$ 个人相约去爬山.
山的初始攀登难度为 $d$ .
每位登山者有两个属性: 技巧 $s$ 和整洁度 $a$ .

技巧为 $s$ 的登山者能登上攀登难度为 $p$ 的山当且仅当 $p\le s$ .
在一位整洁度为 $a$ 的登山者登上攀登难度为 $p$ 的山后, 山的攀登难度会变为 $\max(p, a)$ .

请给这些登山者指定一个爬山的先后顺序, 最大化登上山的人数.
如果轮到一位登山者时他能登上山, 则他一定会选择登山.
$n\le 5\times 10^5, d, s_i, a_i\le 10^9$

正确做法是直接贪心, 按照 $\max a_i, s_i$ 第一关键字, $s$ 为第二关键字排序就是答案.

证明它, 当前山高度为 $h$ :

  • 如果 $\max a_i, s_i=s_i$ ,
    • 首先一定有 $h\le s_i$ , 因为前面所有人的 $a$ 都不大于 $s_i$ .
    • 那么我们让这个人上山, 考虑后面一个不能上山的人 $j, s_j< s_i$
      • 如果我们强行让那个人上山, 这个人一定上不了, 并且之后山的高度一定大于当前状况(它排在后面且 $s_j<s_i$ 只能是 $a_j>\max s_i, a_i$ ), 所以一定不优
  • 如果 $\max a_i, s_i=a_i$
    • 能上山就上山, 如果硬上就是上面那种情况.

思路似乎很不自然啊, 邻项交换?

考虑相邻两项 $(a_1, s_1), (a_2, s_2)$

如果 $a_1>a_2$ 且 $a_1>s_2$ , 肯定让2先上.

如果 $a_1>a_2$ , $a_1<s_2$ , 也一定让2先上.

如果 $s_1>a_2$ 且 $s_1>s_2$ , 肯定让2先上.

. . .

然后就得到结论了/kx

CF1344D Résumé Review

好像是咱们上面那个 Teleporters 啊. 凸的-二分就做完了.

CF1641D Two Arrays

给定 $n$ 个长 $m$ 的序列 $a_i$ , 每个序列有权值 $w$ , 求最小的 $w_i+w_j$ 满足 $a_i, a_j$ 的交集为空.
$n\le 10^5, m\le 5$

这个有点神仙?

首先可以双指针: 把 $w$ 递增排序, 枚举 $i$ 要找到最小的 $j$ , 发现当 $i$ 右移的时候 $j$ 如果右移一定不如刚才那个, 所以 $j$ 是单调左移的.

那么现在都问题是我们啥时候应该左移, 那就是如果区间 $[1, j]$ 中有一个集合和当前 $a_i$ 无交. 这也是这个题最妙的地方, 计算

$$
\sum_{t\subseteq T} [t\subseteq S]\cdot (-1)^{ \vert t \vert }
$$

如果等于1则没有重复元素, 否则有. 还挺显然, 考虑 $\sum_i \binom{n}{i}(-1)^i=[n=0]$

这个方法的关键之处在于我们可以判断一个集合与一堆集合是否都有交, 因为我们只要枚举这一个集合的子集, 判断出现次数即可.

另外一种办法是用bitset莽

CF356D Bags and Coins

给定长 $n$ 的数组 $a$ 和一个数 $s$ , 构造一个森林, 每个点 $i$ 有非负点权 $c_i$ , 要求点 $i$ 的子树中点权之和恰好为 $a_i$ , 并且所有点权的和为 $s$ .

输出答案时, 对于每个 $i$ , 先输出 $c_i$ , 再输出 $k_i$ 表示 $i$ 的儿子数量, 然后依次输出 $i$ 的儿子们. 无解输出-1.
$n, s\le 70000$

首先你一眼看出森林的每一棵树应该都是一条链, 就直接构造完了.

于是现在问题是哪些节点当根, 因为它们的 $a$ 和要等于 $s$ .

于是要找到若干个数和 $s$ , bitset背包即可.

CF1292D Chaotic V.

一棵树, $i$ 的父亲是 $i$ 最大的非自身的因数, 给定 $n$ 个 $k_i!$ , 求树上一点到这 $n$ 个点的距离和最小值.
$k_i\le 5000, n\le 10^6$ .

其实只有5000个点做带权重心(重心经典结论), 重点是求出这些点的虚树. 于是要知道:

  • dfs序排序
    • 我们dfs肯定用先进最小的点的办法. 那么考虑比较两个点的dfs序大小: 一个点从祖先到自己的路上质因子是递增的, 体会一下发现直接按 $k_i$ 排序即可.
  • lca
    • 质因子是从大往小乘的, 所以找到两个点最大的共同质因子, 次数取min, 即它们的lca

于是求虚树就好了.

CF1672H Zigu Zagu

给定一个长 $n$ 01串, $q$ 次询问对于一个区间, 若你每次可以删除这个区间的一个01相间子区间(没有00或11), 那么最少要删多少次.
$n, q\le 2\times 10^5$

考虑区间内的00和11个数:

对于00101010101011这样的, 我们要么一次操作删掉一个11一个00(0010101011->01), 要么一次删掉一个11或00(00101010100->00)并且只要同时有00和11, 一定可以选择同时删掉0011(交界处)于是就统计区间00, 11个数, 取个max即可.

CF578D LCS Again

给定一个字符串 $S$ , 求有多少个与 $S$ 等长字符串 $T$ , 满足 $\mathrm{LCS}(S, T)= \vert S \vert -1$ , 其中 $S, T$ 只包含前 $m$ 个小写字母.
$n\le 10^5, m\le 26$

首先明显转化为 $s$ 删掉一个再增加一个转化成的不同的串个数.

那么先考虑删掉字符后串相同的情况, 发现两个串相同当且仅当删掉的两个字符及它们中间的字符全部相同.

那么考虑此时再插入一个字符的方案, 基础情况是除了原位都能插入. 但对于一个相同段, 向其中插入等于这个相同段的东西, 所以贡献是 $m(n-1)-\text{相同元素个数}$

但发现删掉 $s_i$ 和 $s_{i+1}$ 的时候有一种情况会重复, 会得到 $s_{[1\ldots i-1]}+s_{i+1}+s_{i}+s_{[i+2\ldots n]}$ 这样的. 于是再减1. 就结束了.

另一个做法是dpofdp, 直接记录求LCS的一行的状态显然是爆炸的. 考虑对于一个状态 $(i, j)$ , 其 $(i, j)\le \min i, j$ , 所以其能对 $(n, n)$ 有贡献需要 $\min i, j+\min n-i, n-j\ge n-1$ . 化简得到 $\vert i-j \vert \le 1$ , 于是现在 $i$ 行只有 $i, i-1, i+1$ 三个格子有意义.

那么我们设 $f_{i, j, k, l}$ 表示当前填写到第 $i$ 行, 其中lcsdp数组的 $(i, i-1), (i, i), (i, i+1)$ 分别是几的状态. 状态数 $n^4$

再考虑, 因为 $(n, n)=n-1$ , 所以对于状态 $(i, j)$ 有 $\min {i, j}\ -1\le (i, j)\le \min i, j$ . 否则后面 $\min n-i, n-j$ 没法把它加到 $n-1$ .

于是每一位只可能是 $i$ 或 $i-1$ , 用 $0/1$ 记录. 时间 $nm$

题目很好, 可为啥是贪心呢?

CF1422E Minlexes

给定一个字符串, 每一个后缀, 求可以删去若干个相邻两相同字符的情况下这个后缀最小的字典序. aabb可以到空, 但abba不行, 就是可以一次选若干个不想交的相邻两个删.
$\vert S \vert \le 10^5$

$f_i$ 表示 $i$ 开头的后缀, $f_i=\min {s_i+s_i+f_{i+1}}$ 记录开头前几个字符即可.

CF1658F Juju and Binary String

给定一个长 $n$ 01串, 要从中选取若干个不相交子串, 使得:

  • 所有子串长度加起来为 $m$
  • 所有子串拼起来后1的个数占总长的比与原字符串相等.
    最小化你选的子串个数. 输出方案.

精妙的.

第一步, 设原串有 $a$ 个0, $b$ 个1, 则给一个1赋权 $a$ , 0赋权 $b$ , 要求就是选的子串权值和为0.

结论是, 把串头尾相接, 一定有一个长度为 $m$ 的子串权值为0. 考虑若所有 $m$ 的子串权值都大于0, 那么总权值不能等于0. 于是至少有一个长 $m$ 子串权值小于0. 于是这个负的区间不断移动到一个正的区间这个过程中一定会碰到一个恰好等于0的.

于是就做完了.

CF578E Walking!

给定长度为 $n$ 的01串 $s$ , 构造一个排列使得 $s_{p_i}\ne s_{p_{i+1}}$ , 最小化排列的逆序对个数, 输出方案. $n\le 10^5$

相当于选择尽可能少的若干个01交替的子序列.

于是从左往右扫, 维护当前已有的所有子序列, 看新来的这个是否能添加到其中一个或要新开一个.

然后有可能添加完之后无法拼到一起, 比如两个分别是 $\texttt{LR}$ , $\texttt{RL}$ 这样的, 我们发现若一个字符串 $\texttt{L}$ 开头 $\texttt{R}$ 结尾叫 $LR$ , 那么最后若有一个 $LR$ , 一个 $RL$ , 那么一定可以把一个的头或尾放到另一个上变成 $LL$ 和 $RR$ , 就可以随便拼了.

PNR2 Div1 B

降智题

给一个序列, 你有一个栈, 你要从 $1\ldots n$ 扫这个序列, 如果大于栈顶或栈为空就入栈, 否则可以选择什么都不做或者删掉一个把它加进去, 前提是加进去后栈从底到顶依然是单增的. 求处理完之后栈最多剩下多少数.
$n\le 5\times 10^5$

选择的时候一定能加进去就加进去. 因为加进去让栈顶变小并且不改变栈内数的个数.

CF235E Number Challenge

给定 $a, b, c$ , 求 $\sum_{i=1}^a \sum_{i=1}^b \sum_{i=1}^c d(ijk) \pmod {2^{30}}$
$a, b, c\le 2000$

这不莫反题吗咋混进来的.
就用
$$
d(ij)=\sum_{a \vert i} \sum_{b \vert j} [gcd(a, b)=1]
$$
拓展之后是
$$
d(ijk)=\sum_{a \vert i} \sum_{b \vert j} \sum_{c \vert k} [gcd(a, b, c)=1]
$$

然后做就行了.

Tomik poezji

给定一个集合 $S$ 和整数 $s$, 其得分规则是不断从前往后, 若当前 $sum=-1\pmod s$, 则把和清空并把得分加一, 最后一次不算, 求排列使得得分最小.
$n\le 5\times 10^5$

考虑如果数不重, 那么若当前还剩下至少两个数, 你一定可以选一个让它不是 $s-1$, 所以得分一定是0.

当有重复的时候, 结论是每次选择当前出现次数最大的数, 如果不对就随便选另一个.

证明是考虑, 最后剩下的一定是出现次数最大的一个数, 那么设这个数为 $a$, 若其不于 $s$ 互质, 则 $ka$ 始终不等于 $s-1$, 不会出现不对的情况, 否则现在它与 $s$ 互质, 可以把序列中的所有数都乘 $a^{-1}$, 另 $t=s\cdot a^{-1}$, 此时原来的 $a$ 变成了 $1$, 而其它的数可以认为全都在 $-(s-2)\ldots -1$ 之间, 那么假设从 $0$ 开始, 按照上面的流程一定是先走 $1$ 走到 $t-1$, 然后往回走一个, 不断重复, 最后等前面的都用完了就只能走 $1$ 跨过若干个 $kt$, 发现因为那些负数的总和一定, 所以最后这个 $kt$ 也是固定且最少的, 因此策略是最优的.

AT_cf17_final_d Zabuton

有 $N$ 个人, 他们按一定顺序排成一队, 依次向砖堆中加砖.
对于第 $i$ 个人, 如果此时砖堆中有 $\leq H_i$ 块砖, 他就会往砖堆中加入 $P_i$ 块砖, 否则他会什么也不做.
一开始砖堆中有 $0$ 块砖, 即没有.
你可以任意安排这些选手加砖的顺序, 求出最多能够让多少人往砖堆中加入砖.

$n\le 5000$

考虑钦点一个无后效性的顺序, 按照 $H_i+P_i$ 排序, 因为这代表着这个人最多能把大小提升到这个值, 如果 $H_i+P_i<H_j+P_j$, 那么如果 $i$ 在 $j$ 后必扔一个, 只有 $i$ 在 $j$ 前可能两个人都能上.

然后dp. 因为 $V$ 很大, $f_{i, j}$ 表示前 $i$ 个人, 用 $j$ 个人的最小砖数, 复杂度 $n^2$

AT_agc027_b Garbage Collector

第一眼以为每次扔的应该是一个区间, 但实际不是的. 考虑假设一次扔的垃圾位置序列为 $t_k$, 那么代价是 $t_k+\sum_i^k (2k-2i+1)t_i$, 那么因为越往后系数越小, 把最大的几个垃圾分多次扔才好. 但这个式子也表示了如果我们知道一共扔几次, 只需要从后往前从大到小安排系数即可, 那么就只要枚举扔几次, 设扔的次数为 $m$ 时, 则可以用前缀和处理出 $t_i$ 的区间和, 每次把一段加到贡献里, 单次就成 $O(n/m)$ 了, 总复杂度 $n\ln n$

CF1891E Brukhovich and Exams

给定序列 $a_n$, 可以把 $k$ 个数变成 $0$, 最小化 $\sum_i [\gcd(a_i, a_{i-1})=1]$.

$n\le 10^5$

直接贪, 找出原序列连续1段和gcd序列的连续1段, 先删gcd连续1段中原序列不是1段的段, 再按原序列1段大小从小到大删, 再删刚才剩下的奇数位置和原序列与1或n相连的段.

[ARC164F] Subtree Reversi

给出了一个 $N$  个点的树, 以 $1$  为根.

  • Alice 是先手持白棋, Bob 是后手持黑棋.
  • 若 $u$ 无棋子且其儿子都有棋子, 则可以放.
  • 在 $u$ 放棋子时, 子树内棋子颜色反转($u$ 不变).

Alice 希望白棋最多, Bob 希望黑棋最多, 双方都采取最优策略, 问白棋数量.

考虑对于一个点其翻转次数固定, 因此可以有一些正点和一些反点, 正点贡献到放棋子的一放, 反点贡献到对方, 而每次放一个点要求它是叶子, 放了之后删掉这个点.

于是考虑对于当前状态, 能放正叶子肯定不放反的, 于是先把正叶子贡献, 于是现在只有反叶子, 考虑若删掉反叶子后会获得正叶子, 则对手连加两分, 而先后手不变, 因此尽量先选删掉反叶子不会获得正叶子的点.

于是可以把整棵树划分成若干区域, 每个区域是一个由一个以一个父亲度数大于 $1$ 的反点为根, 有若干红蓝交替的链构成的连通块, 问题变成了选择一个这样的区域把它删掉, 发现直接每次选收益最大的区域就是对的, 而你可以自底向上的划分区域, 于是就做完了, 复杂度单log.