CF1091

反悔贪心。

A - New Year and the Christmas Ornament

题面

给定 $y,b,r$，你需要求 $y^\prime,b^\prime,r^\prime$ 使得 $y^\prime\le y,b^\prime\le b,r^\prime\le r$，且 $y^\prime+1=b^\prime=r^\prime-1$，求 $y^\prime+b^\prime+r^\prime$ 最大值

$1\le y\le100,2\le b\le100,3\le r\le100$

题解

必定有一个 $x^\prime$ 满足 $x^\prime=x$，枚举一下是哪个然后取最小值一定能得到最大的满足条件的

B - New Year and the Treasure Geolocation

题面

有 $n$ 个点以及 $n$ 个向量，你需要给每个点搭配一个向量，使得点 + 向量均指向同一个点，保证有解

$1\le n\le1000$

题解

$y$ 最小，且 $y$ 最小的前提下 $x$ 最小的点，一定搭配 $y$ 最大，且 $y$ 最大的前提下 $x$ 最大的点，由于必定有解，所以输出这个点即可

C - New Year and the Sphere Transmission

题面

$n$ 个人围成一圈，顺时针 $1\sim n$ 编号，你需要选择一个 $k$，第 $1$ 个人有一个球，接下来每一时刻，手里有球的人会传给它顺时针方向的第 $k$ 个人，球最后回到第 $1$ 个人手中时结束，这个过程中，定义所有有过球的人的编号和为 $f(k)$

将 $f(k)$ 从小到大去重排序输出

$2\le n\le10^9$

题解

与 $n$ 的 $\gcd$ 相等的 $k$ 的 $f$ 值一定也相等

因此答案为 $\sum_{d|n}\frac nd+d\times\frac{(n/d)(n/d-1)}2$，复杂度 $O(\sqrt n)$

D - New Year and the Permutation Concatenation

题面

给定 $n$，定义 $a$ 为 $1\sim n$ 的所有排列按字典序排序后依次拼接得到的数组，求这个数组有多少长为 $n$ 的连续子段的和为 $\frac12n(n+1)$

$1\le n\le10^6$，对 $998244353$ 取模

题解

考虑求解字典序中下一个排列的方式，我们找到最后一个满足 $p_k<p_{k+1}$ 的 $k$，然后将 $p_k$ 替换为 $p_{k+1}\sim p_n$ 中最小的大于 $p_k$ 的，并将这个后缀剩下的数从小到大排序

只有递降后缀不会贡献答案，因此我们枚举长度为 $k$ 的递降后缀个数，那么答案就为：

$$n!\times n-\sum_{k=1}^{n-1}\frac{n!}{k!}$$

复杂度 $O(n)$

E - New Year and the Acquaintance Estimation

题面

有一个 $n+1$ 个点的无重边无自环的无向图，给定其中 $n$ 个点的度数，问剩下一个点的度数的所有可能值

$1\le n\le5\times10^5$

题解

存在一个结论：如果我们将一个图所有的点度数从大到小排序 $d_1,d_2,\cdots,d_n$，那么存在这样的图当且仅当 $\sum_{i=1}^n d_i$ 是偶数且对于所有 $k$，$\sum_{i=1}^k d_i\le k(k-1)+\sum_{i=k+1}^n\min(d_i,k)$ 均成立

证明咕了

那么我们将已知度数从大到小排序，一个 $k$ 不管插入新点的度数在前或在后，都会对新点度数有一个上/下界限制，而这个限制是可以预处理出的，所以我们直接枚举度数，然后二分找出在哪两个已知度数之间，调用预处理的限制判断即可

复杂度 $O(n\log n)$

F - New Year and the Mallard Expedition

题面

有 $n$ 个首尾相接的线段，每个线段有一个长度 $a_i$ 和一个 WGL 中的属性，你要在这些线段上运动（你可以随时改变方向，不一定要在整数坐标），你在 G 上走 $1$ 的距离需要 $5$ 的时间，在 W 上走 $1$ 的距离需要 $3$ 的时间，在 L 上不能走，但是你可以在任何一种线段上飞，且飞 $1$ 的距离永远需要 $1$ 的时间

你有一个属性叫做能量，你需要保持其非负，初始为 $0$，飞行 $1$ 的距离会消耗 $1$ 的能量，在 G 或 W 上走 $1$ 单位距离都会增加 $1$ 的能量，问从第一个线段的开头走到最后一个线段的结尾的最小时间，保证有解（即第一个线段属性不为 L）

$1\le n\le10^5$

题解

反悔贪心。

我们如果不需要攒能量的话在 G 上最快运动速度是 $3$，在 W 上最快运动速度是 $2$，称这种状态为跑

那么我们初始假设所有线段都是跑过的，但是这样能量显然不够，因此如果遇到 L/G（不难发现飞过 W 没有意义），会有一系列反悔措施能使答案变得更优

我们开一个桶 $cnt_i$，表示当前有多少距离可以增加 $1$ 的能量需要增加 $i$ 的时间

1. 遇到 W，我们假设跑过，那么 $cnt_1$ 会加 $1$，代表我们可以将其又跑改为走
2. 遇到 G，我们假设跑过，如果 $cnt_1>0$，那么一定是使用这个距离兑换能量再飞过当前的 G 更优，因为 $3\rightarrow1$ 节省了 $2$ 的时间，而兑换能量只会增加 $1$ 的时间，因此我们优先使用 $cnt_1$ 兑换能量，那么我们每按照这种方式走 $1$ 的距离，就会有两次耗费 $2$ 时间兑换 $1$ 能量的机会（$1\rightarrow3\rightarrow5$），其余的距离只有一次机会（$3\rightarrow5$）
3. 遇到 L，我们一定是飞过，那么我们从小到大依次贪心兑换能量，直到攒够了能量能够飞过去，如果总和仍然不够，那么我们一定是在之前的某个格子里来回踱步，如果之前出现过 W ，那么我们就可以耗费 $3$ 时间获得 $1$ 能量，否则我们只能在 G 上踱步，耗费 $5$ 时间获得 $1$ 能量，这样直至将能量集够

复杂度 $O(n)$