【题组】XCPC 2024 思维题训练

题目来源

题单：思维 - Virtual Judge problemPdfAll

来源：

Problem A

简单贪心题，难度全在模拟上。

首先选择之后可以充电的电池，并且先充电的先用，正确性显然。

但是 $O(n)$ 的模拟十分复杂，换成堆来存储最近的位置显然就方便许多了。

Code: Submission #290312414 - Codeforces

Problem B

同样的贪心 + 分讨。

第一种情况是去掉上界，最为简单，将剩余的全给利润最大的即可。（但我一开始漏掉了）

第二种较为复杂，枚举去掉下界的作物的下标 $i$ ，此时剩余的时间 $rest \gets m - \sum{l} + l_i$ ，去掉之后的总利润 $cur \gets \sum {l \times w} - l_i \times w_i$ 。

根据贪心不难想出剩余的优先给大的，因此从大到小排序，定义数组 $precnt$ 表示前 $i$ 个可以添加剩余的个数， $presum$ 表示装满前 $i$ 个剩余个数所增加的利润值。有：

$precnt_i = precnt_{i - 1} + r_i - l_i\\ presum_i = presum_{i - 1} + (r_i - l_i) \times w_i$

显然单调，二分找到最后一个小于 $rest$ 的 $precnt$ 的下标 $idx$ ，答案即为：

$cur + presum_{idx} + (rest - precnt_{idx}) \times w_i$

枚举这个下标求最大值即可。

Code: Submission #290315716 - Codeforces

Problem C

~~真正意义上的第一道思维题。~~

将一个序列从第 $i$ 处断开，那么这个 $gcd$ 的值为 $\gcd(pre_i, suf_{i + 1})$ ，其中 $pre$ 和 $suf$ 分别是序列的前缀和后缀 $\gcd$ 值， $pre_0 = suf_{n + 1} = 0$ 。

扩展到本题上仍然适用，答案 $ans$ 为：

$\max_{1 \le l \le r \le n} \left(\gcd \left(\gcd(pre_{l - 1}, suf_{r + 1}), \gcd_{l \le i \le r} a_i + k \right) \right )$

区间枚举的时间复杂度难以承受，但是考虑一种贪心，枚举左端点 $L$ ，找到最右的端点 $R$ 使得 $pre_{L - 1} = \gcd_{L \le i \le R} a_i + k$ ，如果此时的 $suf_{R + 1} = pre_{L - 1}$ ，那么说明此时的答案成立。看似最坏的时间复杂度没有变化，其实已经可以通过了。

这是因为选择的左端点 $L$ 只在它即将变化时才遍历，由于 $\gcd$ 的性质，前缀最大公约数中不同的值最多只会有 $\log W$ 个（每一个 $pre_i$ 都是 $pre_{i - 1}$ 的因数），因此枚举的时间复杂度仅为 $O(\log W)$ 次，总的时间复杂度为 $O(n \times \log W)$ ，可以通过。

Code: Submission #290318036 - Codeforces

Problem D

没有完全想出来。

一开始想的是按边所属的公司分类，定义一组 set， $set_i$ 存储所属公司是 $i$ 的边的下标，将边加进去当且仅当这条边的一个起点刚刚被达到，而另一个起点没有达到，删去这条边当两个点都被到达过了，按照边的权值从小到大进行排序。

这样写的复杂度可能会超标，因为每当确立一个节点，就要遍历它相邻的所有节点，时间复杂度可以达到 $O(km)$ ，同时不能很好的处理同时走过两条边以上的情况。

正解的做法其实十分接近，将 set 换成堆来做，对于每一对 $a_i$ 和 $b_i$ ，我们都将 heap[a[i]] 中边权小于 $b_i$ 的加入到一个堆中，这个堆用来跑 Dijkstra。比较之下我想出的做法更像暴力 BFS。

图论最短路模型没想到有 Dijkstra，简直唐完了。

Code: Submission #290322711 - Codeforces

显然第 $0$ 行不受到任何制约， $\sum_{y = 0}^q f(0, y) = \sum_{y = 0}^q y = \frac{y(y + 1)}{2}$ ，对于第 $i$ 行，每一个都相当于向上走一行，每一列上都加 $1$ ，如果第 $i - 1$ 行存在一个点，那么就在这个点可以到达的第 $i$ 行上面的所有点减去 $1$ 步。一开始我采取了一种刷表的形式，然后 TLE 了，因为这道题恶心的一点就是 $p,q$ 不受到制约，然后通过缩点加速的方法，然后就 WA 了，原因很简单，因为我的这种做法会导致 $(x1, y1)$ 和 $(x2, y2)$ 对于同一点发生两次贡献，其中 $x1 \lt x2,y1 \gt y2$ ，然后就 WA 了（结果样例没有这种情况，害得我调了两个小时）。

正解出奇的简单，先求出不存在任何点的总数 $ans$ ，通过在线的更新，将纵坐标从小到大排序，横坐标从大到小排序（第二关键字），每次减去从 $(x + 1, y + 1)$ 到 $(p, q)$ 中的所有点个数，这样可以保证不会有重复解问题。

写完了才发现这道题转化后十分简单，可惜没有完全转化。

Wrong Answer: Submission #290346331 - Codeforces

Code: Submission #290349113 - Codeforces

Problem H

代码好写，但是第一步就没想出来。

策略：一直随机到直到小于等于某个值 $c$ 后一直减。

题解的策略是这样的，但我死活也想不出来。

设这个值为 $c$ ，值域为 $T$ ，那么每一次随机成立的概率 $p = \frac{c}{T}$ ，那么操作次数 $cnt$ 有：

$\begin{align} cnt &= \frac{c - 1}{2} + 1 + (1 - p)^1 + (1 - p)^2 + (1 - p)^ 3 + \dots \\ &= \frac{c - 1}{2} + \frac{1}{p} \end{align}$

至于为什么成立，将 $\sum_{i = 1}^{\infty} (1 - p) ^ i$ 换元即可证明。

由于 $cnt$ 满足

$cnt \ge 2 \sqrt{ \frac{c - 1}{2} \times \frac{1}{p} }$

因此 $c$ 的取值介于 $\left \lfloor \sqrt{2T} \right \rfloor$ 和 $\left \lceil \sqrt{2T} \right \rceil$ 之间，分数运算即可。

Code: Submission #290373852 - Codeforces

Problem J

一开始看错题导致的，本以为筹码会从输的人给赢的人，这样子总的非平局次数必然不超过 $O(\log n)$ 次，直接深搜即可。

但是写完之后才发现筹码会不断减少，这就意味这一旦有一个人筹码很小并且一直赢，这样的状态树会退化成一条链（严谨来说是一条毛毛虫或者想一条链的二叉树）。

因为是一种链形的结构，自然可以区间加速，但是没有找到很巧妙的做法。

看了题解，题解说的是直接辗转相减变成辗转相除，和我想得差不多，其实在原来的代码上面改一下即可，例如当且递归的 $x,y$ 有 $x \gt y$ ，直接加速到 $x \le y$ ，并直接用快速幂算出中间的概率，最后递归的时候返回即可，对于 $x \lt y$ 同理。需要注意的是当 $x \gt y$ 时的加速过程中，除了一直输，赢一次就算做贡献，直接容斥即可，具体操作代码有。