七月算法竞赛选题（三）

[[ slider_text ]]

[[ item.c ]]

七月算法竞赛选题（三）

发布时间 2025-08-13 作者：zhangminchen 来源：算法小站

扫描线 状态压缩dp 哈希 博弈论

## 牛客暑期多校训练营4
### G
**[Ghost in the Parentheses](https://ac.nowcoder.com/acm/contest/108301/G)**
**问题描述**
有一个有效括号序列，但是，每个字符有$$1/2$$的机会被替换成`?`，问得到的序列，能够构造出**唯一**括号序列的方案数

**算法分析**
> 假设有一个有效括号序列，你可以挖掉若干个位置，什么情况下不唯一呢？

有序括号序列前缀和为`0`，并且有`n`个`+1`和`n`个`-1`，那么你很显然可以把`(`或者`)`都挖掉，换成`?`
方案数是唯一的，那么你挖掉$$n$$个`(`之后，再多挖掉一个`)`，方案数还唯一吗？

除非序列长度是`2`，否则答案一定不唯一，因为多挖掉的`)`，能够和之前的**任意`(`**匹配在一起
`()`的子段和是`0`，这样构成的序列一定是合法的，是不唯一的

> 什么时候唯一呢？假设说你有若干个括号被换成`?`，你手上有`l`个`(`和`r`个`)`，怎么构造方案数唯一呢？

合法括号序列的方案数一定是前缀和非负，那么贪心地，前缀和要尽量大，需要在尽量靠前的位置把`(`都放好
之后再放`)`，这样就可以保证前缀和尽可能大了，也就是**最优解**
那么考虑**次优解**，我们在保证前缀和尽量大的基础上，交换**需要还原的（即原来是`?`的位置）**
得到我们填的最后一个`(`和第一个`)`，交换之后，如果`) (`非法，那么不存在次优解，其他位置也就更不可能了

> 那么我们预处理好所有前缀和恰好为`0`的子段，分成左右两半$$L, R$$

根据之前的分析，子段的`(`可以全部挖掉，但是你不能再多挖一个`)`了，$$L$$的`(`可以全部都挖掉
那么$$R$$的呢？

你要方案数唯一，**等价于序列中有多少个位置，`+1 变 -1，-1 变 +1`，交换后会导致序列不合法**
那么很显然$$L$$中`)`的位置是确定的，而所有`(`都变成了`?`了，它要想换成`-1`，括号从哪里来？
只能从后半段$$R$$中来，而$$L$$的前缀和恰好为`0`，换任何一个`-1`过来，都会导致前缀和`< 0`

也就是说，$$R$$中的`)`是换不过来的，那么这些位置替换成`?`无所谓

综上所述，枚举每个前缀和为`0`的位置，$$L$$中有多少个`+1`，$$R$$中有多少个`-1`

那么分子，**作为方案数**是$$\displaystyle \sum 2^{pre(i)} \cdot 2^{suf(i+1)}$$，分母是$$2^n$$
概率即可求得

> 注意，计数的时候怎么不重不漏？

首先所有的`(`或者`)`都可以被挖掉，一开始统计`)`全部挖掉，然后遍历完之后，统计`(`全挖掉的情况
接下来枚举哪些区间的`[l...r]`不挖

> 题中给出，爱丽丝的有效括号序列是`s = ( ( ) ( ) )`，他收不到字符序列`? ? ( ( ) )`

之前我们讨论过，右边的`)`可以不挖，那么我们就枚举不挖的位置$$i$$

也就是说，对于枚举对于不挖的右括号位置`s[i] = )`，那么它能作为**分界线的充要条件**是什么呢？
是它的左边能找到第一个前缀和为`+1`的位置`j`，根据题中描述，此时`i`这个位置的前缀和恰好为`0`
如果能找到这样的位置`j`，`j`之前的前缀和必须为`+1`，不能减小了，而把所有的`(`替换成`)`都会导致前缀和变小
所以$$L$$的方案数是$$2^{pre(j)}$$，$$R$$的方案数就是$$2^{suf(i+1)}$$

> 总结

如果不挖掉`s[i] = )`，那么要想括号序列唯一，那么一定要使得`s[1....i]`的前缀和恰为`0`
换句话说，在`i`之前，一定要找到一个位置`j`，使得前缀和`s[1...j]`恰为`1`
特别注意，`)`之前前缀和恰为`1`的位置，有一种特殊情况

形如 `(... 完全配对的段 ...) + ( ( ( ... ( )`，那么对于`( ( ( ... )`而言，这个子段恰好为`1`的位置在子段开头
形如这样的子段，`(`只能挖掉**第一个**，再多挖一个都不行，否则的话`( (`，第二个`(`可以替换成后半段的`)`
方案不唯一

综上所述，如果枚举`)`不改，需要考虑`)`作为前缀和为`0`的子段的右端点，此时需要结算
否则的话，`)`是中途的点，那么就要考虑`( ( ... ( )`的情况，此时只能改第一个`(`

## 2025钉耙编程中国大学生算法设计暑期联赛
### 1007性质不同的数字
**[性质不同的数字](https://acm.hdu.edu.cn/contest/problem?cid=1174&pid=1007)**
在一个无限长的数轴上，有$$n$$个集合，每个集合用`[l, r]`表示，我们称$$x, y$$性质不同
当且仅当存在至少一个$$S$$，使得$$x \in S$$但是$$y \notin S$$

**算法分析**
可以**哈希**，注意到，如果按线段左端点排序，对于某条线段$$[l, r]$$，都可以选$$l$$
另外，如果你选了$$l$$，中间的某一点$$x$$**在线段上**，却没有另外的线段来覆盖它，那么这个点是不能选的
因此，一条线段只有在端点处是有用的，如果$$x \in [l, r]$$被另一条线段$$[l_1, r_1]$$覆盖
我们让$$x$$这个点在$$l_1$$处结算，因此可以离散化

问题就转化成，你要选若干个点，每个点都属于不同的线段
**可以给每条线段一个哈希值**，$$[l, r]$$中所有的点都拥有哈希值，可以用**异或哈希+差分**
令 $$l \oplus sha, (r+1) \oplus sha$$，最后求出$$[1, 2n]$$每个点的哈希值$$sha$$
然后统计一下有几个不同的数即可

**坑点**
**离散化 + 差分**的时候，对于$$[l, r]$$，我们的有效点不是$$l, r$$，而是$$l, r+1$$
应该让$$r+1$$插入数组中去离散化

### 1004三带一
**[三带一](https://acm.hdu.edu.cn/contest/problem?cid=1174&pid=1004)**
扑克牌有`13`种花色，问最多能打出多少张三带一，三带一必须是`AAAB`类型的牌，使用过的牌不能重复使用

**算法分析**
不难想到二分答案，那么二分答案的范围很显然是$$[0, \dfrac{tot}{4}]$$，`tot`是牌的数量的总和

> 那么还有什么限制呢？

首先，当二分了答案$$x$$之后，考虑花色$$i$$，能够用来**搭配，带出来**的牌，总数是确定的
一定是$$sumr = tot - 3x$$

那么考虑花色$$i$$，划分成两个集合，一个是$$|C|$$集合，表示三张牌，一个是$$|R|$$集合，表示带出来的牌
最好的情况，那当然是$$C_i = \lfloor num(i) / 3 \rfloor$$，剩下的$$r_i = num(i) \bmod 3$$

现在问题转化成，$$C_i$$有没有足够的，其他花色的牌跟他配，如果不够，$$C_i$$就要减少
这里有一个**贪心**，能够使用的其他花色的牌，总数是$$sumr$$，最多能够用的实际上就是$$sum - r_i$$了
为什么呢？假设说$$C_i$$减少了，你丢掉若干张`3 * ?`的牌，这些牌都**不能用于匹配**
能够用于匹配的牌的总数，并不会因此而增加，$$can = sumr - r_i$$，`can`要尽量大，那么$$r_i$$尽量小
所以$$r_i$$就取$$num(i) \bmod 3$$即可

> 那么限制，假设说对于花色$$i$$，有$$C_i$$组

那么首先$$C_i \leqslant \lfloor \dfrac{a_i}{3}\rfloor$$，另外，$$3C_i + r_i = a_i$$
其次，$$C_i$$还受到其他花色牌的限制，受到$$sumr - r_i$$的限制

如果$$C_i > sumr - r_i$$，那么$$C_i$$要对应地减小，不满足
如果$$C_i = sumr - r_i$$，那么刚刚好分成$$C_i$$组
如果$$C_i < sumr - r_i$$，那么一定可以匹配完$$C_i$$组
从而$$C_i \leqslant sumr - r_i$$

综上，$$C_i \leqslant tot - 3x - (a_i - 3C_i)$$，$$C_i \geqslant \lceil \dfrac{3x + a_i - tot}{2} \rceil$$
同时$$C_i \leqslant \lfloor \dfrac{a_i}{3} \rfloor$$

检查每个花色的上下界，累加，然后判断$$x$$是否在$$[L, R]$$之间

## 2025牛客暑期多校训练营5
### A
**[Entangled Coins](https://ac.nowcoder.com/acm/contest/108302/A)**
给定`n`枚硬币，有`s`枚正面朝上，其余朝下，你可以操作任意次，每一次选恰好`k`个进行翻转
目标是朝上的硬币数量从$$s \to t$$，输出最少操作次数，或者报告无解

**算法分析**
形式化地看，实际上就给定了一个$$x \in [0, n]$$，它可以变成$$x-a+b$$
其中$$a+b = k, a \in [0, s], b\in [0, n - s]$$
换句话说，$$x \to x-(a-b) = x-(a+b-2b) = x-(k - 2b)$$，不管怎么翻转
**一次翻转中，$$x$$的奇偶性总是和$$x - k$$相同**

那既然如此，因为$$a+b = k$$，可以构造出$$x$$能够到达的范围的**上下界**
最坏情况，$$(x, n - x)$$，`k`张翻转全部从$$x$$中拿，变成了$$|x - k|$$
最好情况，`k`张翻转全部从$$n - x$$中拿，$$x$$还剩下$$n - |(n - x - k)|$$
所以$$x \to [|x-k|, n-|(n-x-k)|]$$，我们先看简单的$$[x-k, x+k]$$的情况

> 如果$$s, t$$奇偶性相同，那么考虑$$k$$的奇偶性，这时候分类讨论就有点复杂了
 如果$$k$$是奇数，那么$$s, t$$同奇偶，要**偶数次修改**，$$s, t$$不同奇偶，那**只能奇数次**修改
 如果$$k$$是偶数，$$+k$$并不会改变$$s$$的奇偶性，如果$$s, t$$同奇偶，那么**可以奇数次，也可以偶数次**
如果$$s, t$$不同奇偶呢，那么无解

综上，我们发现，不管$$k$$的奇偶性，**偶数次修改**，只有在$$s, t$$同奇偶的情况下才会发生
于是我们先讨论$$s, t$$同奇偶，并且偶数次修改的情况

偶数次修改，**每两个为一组**，每一组，我们要翻转$$2k$$次
我们先看$$2k \leqslant n$$，即$$k \leqslant \lfloor \dfrac{n}{2} \rfloor$$，即两次翻转不会超过$$n$$
确保想翻的都能翻到，不存在两次翻转重合，导致**有翻等于没翻的情况**

根据上面的讨论，两次翻转中，$$x \to x'\in [\max(x-2k, 0), \min(n, x+2k)]$$
这个区间的数都可以取得到，因为$$a+b = k$$，翻转的时候可以根据需要来取$$a, b$$的值
假设翻转有$$c$$组，那么$$s - 2k \cdot c \leqslant t \leqslant s + 2k \cdot c$$

从而我们有限制$$c \geqslant \lceil \dfrac{|s- t|}{2k} \rceil$$

那么$$k > \lfloor \dfrac{n}{2} \rfloor$$的情况呢？自然想到转化成$$k \leqslant \lfloor \dfrac{n}{2} \rfloor$$
根据之前**有翻等于没翻**的角度来看，这个时候**一次翻转**可以看作$$n - k$$张先翻一遍
然后所有的再翻一遍，然后会发现，做两次这个过程，相当于$$n - k$$张翻两遍
然后所有的再翻两遍，所有牌翻两遍就等于没翻，发现这种翻转可以和$$k^{\prime} = n - k$$**等价**
所以对偶数次翻转的讨论，转化成$$k = \min(k, n - k)$$的讨论即可

> 接着来看奇数次

奇数次，我们很自然想到，先算出一次能翻转的上下界，然后就是偶数次翻转了
把上下界依次带入`calc(lo), calc(hi)`，然后取一个`max`，就可以转化成偶数次翻转来解决
根据之前的讨论，上下界是$$[\max(0, |s-k|), \min(n, n - |(n - s) - k|)]$$

值得注意的是，`lo, hi`不一定就是左右区间，还必须满足`lo（一般情况 lo, hi 同奇偶）`的奇偶性和`s + k`相同
`hi`的奇偶性也要和`s + k`相同，这一点在`0, n`的时候特别要注意
不管怎样都特判一下，奇偶性不满足就`lo++ or hi--`

然后，最后的区间范围是$$lo - 2k\cdot c \leqslant t \leqslant hi + 2k\cdot c$$，用$$2c + 1$$来更新答案

注意，这里相当于以`lo`作为新的起点，经过偶数次的更改，$$c \geqslant \lceil \dfrac{lo - t}{2} \rceil, c \geqslant \lceil \dfrac{t - hi}{2} \rceil$$
应该要**同时满足**，所以是取`max`

同时偶数次更改，还必须满足**起点的值和`t`同奇偶**，这里的起点是$$lo$$要和$$t$$同奇偶，$$hi$$不一定
经过上面的分析，$$[lo, hi]$$所有和$$lo$$同奇偶的时候，都可以取到，`hi`在正常情况下，比如$$hi = x + k$$的时候
是可以满足和`lo`同奇偶的，但是$$hi$$可能受到$$n$$的限制，`hi = n`的时候可能并不和`t`同奇偶
我们只要在`[lo, hi]`中能找到一个和$$t$$同奇偶的即可，$$lo = |s - k|$$，是经过了一次翻转的
如果是奇数次翻转的情况，此时$$lo, t$$必须要同奇偶，所以检查这个条件是否满足
同时上界`hi`是用来保证取值范围的，如果`hi`也能满足取值范围
那么就表示$$[lo, hi]$$中存在一个同奇偶的**起点**，有一个合法的解

## 2025“钉耙编程”
### 1001矩形框选
**[矩形框选](https://acm.hdu.edu.cn/contest/problem?cid=1178&pid=1001)**
给定平面上的$$n$$个点，第$$i$$个点位于$$(x_i + 0.5, y_i + 0.5)$$，价值是$$v_i$$，现在要求你选`4`个整数
使得$$(a, c), (b, c), (a, d), (b, d)$$所围成的矩形中，里面的点的权值和最大，还必须满足矩形的面积$$\leqslant K$$

**算法分析**
实际上，矩形的面积$$\leqslant K$$，也就意味着，矩形的边长是$$O(\sqrt{K})$$级别，那么可以枚举边长

当边长确定了，比如水平方向的$$y$$，边长是$$ylen$$，可以从$$[l, r] = [1, ylen]$$开始，**滑动窗口**来求解
那么垂直方向呢？垂直方向长度也是确定的，一定是$$xlen = K / ylen$$
这样的滑动窗口的复杂度是$$O(n\sqrt{K})$$的

只考虑垂直方向，一种直接的想法是，将$$(xi, vi)$$封装成事件，挂载到每一个$$line(yi)$$上，这样就可以滑动窗口了
滑动窗口的时候，只需要暴力添加$$line(r+1)$$上的点，再暴力删除$$line(l)$$上的点，`l += 1, r += 1`即可维护

> 现在的问题是，怎么加点，才方便求？这里有一个限制，那就是需要一个$$x$$方向的，垂直的，长度为$$xlen$$的一段
并且要使得和最大

这个用**线段树区间加**即可满足，对于$$line(yi)$$上挂载的每个点$$(xi, vi)$$
对应区间$$[l, r] = [\max(xi-xlen+1), xi]$$，线段树维护**最大和**，区间修改`modify(l, r, +vi)`即可
删除就是`modify(l, r, -vi)`

> 实际上，这个问题转化为，在垂直方向上，每一个点$$(x_i, v_i)$$，我们在线段树上插入一整个线段
即$$[x_i - len + 1, x_i]$$（等价于区间加`vi`），这样线段树维护这些**线段和的最大值**，在根节点查询即可

**注意**，这里我们贪心地，对于每个点，希望它能够覆盖（影响）到尽可能远的区域，所以将其放在端点上
即$$[x_i - xlen + 1, x_i]$$或者$$[x_i, x_i + xlen - 1]$$，这样你要选$$x_i$$，就可以同时把$$[x_i - xlen + 1, x_i]$$内的点全部选上
这样可以贪心地选到更多的点

这样每个$$x_i$$，实际上都代表一条$$[x_i - xlen+1, x_i]$$的线段，对$$line[yl \cdots yr]$$区间内
插入这样一条一条的线段，最后求**这些线段**的最大值，即线段树根节点的最大值即可

## AtCoder Beginner Contest 418
### D
**[XNOR Operation](https://atcoder.jp/contests/abc418/tasks/abc418_d)**
定义一个字符串是好的，当且仅当它可以通过以下变换，变成`1`
```bash
如果 s[i] = 0, s[i+1] = 0, 删除 s[i], s[i+1]，用 x = 1 替换它们
s[i] = 0, s[i+1] = 1, then x = 0
s[i] = 1, s[i+1] = 0, then x = 0
s[i] = 1, s[i+1] = 1, then x = 1
```
现在给你一个串$$T$$，问有多少个好的子串，子串必须连续

**算法分析**
倒着思考，`1`最终只能从`1 1`或者是`0 0`演变出来
```bash
要么形如
1 1 1 1 ..... 1 1 1 1 1
其中任意一个 1 可以用 0 0 来替换

要么形如
0 0 ... 0 0
这个要求有点苛刻，0 的个数必须是偶数
其中，任意一个位置可以插入任意个 1
```
那么合法的方案数就很明显了，区间$$[l, r]$$之间，`0`的个数必须是偶数，`1`的个数不做要求
直接统计即可

## 2025“钉耙编程”算法设计暑期联赛（8）
### 1006
**[最甜的小情侣](https://acm.hdu.edu.cn/contest/problem?cid=1179&pid=1006)**
环形项链，有`n`个宝珠，最大化选的宝珠价值之和，不能选择连续的$$> 3$$个的宝珠，项链是环形的
首尾也要满足要求，现在有若干修改操作，`x v`，表示$$a_x \to v$$，对于每个询问都要回答最大宝珠的价值

**算法分析**
如果没有修改操作，那么对于上一个位置，可能有$$0, 1, 2, 3$$这几种状态
```bash
假设 val = a[i]
dp(i-1, 0) + a[i] --> dp(i, 1)
dp(i-1, 1) + a[i] --> dp(i, 2)
dp(i-1, 2) + a[i] --> dp(i, 3)
```

那么可以用状态机，每一个位置实际上代表$$(sta, sta+1)$$的状态转移

**线段树维护状态矩阵转移**
对于每一个位置（叶子结点），线段树不是维护具体的值，而是维护**这个位置所有状态转移情况**
```bash
leaf i, i 这个叶子结点，实际上值是一个转移矩阵
leaf[i] = mat

mat: 
for sta = 0 to 2:		mat[sta][sta+1] = a[i]
```
这样状态转移，可以通过`mat`的`max-plus`矩阵乘法来实现，具体来说
```math
\displaystyle
mat(i, j) = \max_{k} (mat(i, k) + mat(k, j))
```
因为是环形的，所以第一个位置（根节点），对应的状态应该要相同，答案是$$\max_i tr[1].mat(i, i)$$
即对应的，选中的第一个宝珠的状态，都应该是$$i$$

### 1005
**[最自律的松鼠](https://acm.hdu.edu.cn/contest/problem?cid=1179&pid=1005)**
最开始有一个主干道，主干道有一个权值，每次给三种操作
```bash
1 w，主干道拓宽，在主干道末尾新开一个点与原来的末端连接，边权是 w
2 x w，连接在某个节点 x 上，边权为 w，称为一个叶子结点

因为保证主干道一定是树上最长路径之一，所以 2 x w，这个 x 不会是主干道末端节点

3 查询，表示有一个小松鼠总是沿着直径走，但不一定是主干道，问在哪些边一定能遇见松鼠？
输出边权和
```

**算法分析**
实际上就是树的直径，**必经边一定在树的直径上**
那么问题就转化成，左右两边，伸下去（非直径边的最远距离）最长的叶子，最长距离会不会和直径相等？

这个实际上比较容易实现，可以用并查集，把所有的非主干道的点，维护它到**主干道**的深度，主干道上的点的`dep`是`0`
非主干道上的点，`dep[x] = dep[fa] + 1`，然后用并查集，把这些点往主干道的点$$u$$（主干道上距离最近的点）合并
同时维护并查集的根，$$mx(u)$$表示$$u$$往下走非直径边，最远能走到哪里

1）`(u 到左端点距离) + (左边伸下去的 mx[u])`这部分，可能会构成新的直径，但因为扩展是往右扩展的，所以这部分是不会变的
可以用线段树，对于操作`2`，找到新添加节点对应的`dsu.fa`，单点修改`change(fa, sum[u] + dsu.mx[u])`
其中`sum[u]`是主干道距离左端点的距离，这样可以很方便地知道**前缀最大值**，二分找到第一个**[1...p] 最大值 = diam**的点$$p$$
那么$$R = p$$，再往右走就一定不可以了

2）另一半呢？注意，另一半`(u 到右端点的距离)`是会不断增加的，也就是说线段树要懒标记，但是主干道上的点又是离散的
懒标记增加，不在主干道上的点，不能加懒标记，所以单纯的线段树是不好维护的

> 实在要维护也可以，把主干道的点离散化成`1, 2, ...`，根据离散化后的下标建线段树
单点修改不是`change(fa, dsu.mx)`，而是找到`fa`在主干道上的位置`j  -->  change(j, dsu.mx[fa])`
另外，主干道拓宽，需要前缀修改，`modify([1...tot.back()-1], w)`，其中`tot`保存主干道上所有的点
单点修改`change`之前，需要先`query`一下，把标记都压下去，然后再修改

注意到题中保证**主干道一定是直径之一**，这也就意味着，如果一个叶子在某个时间戳成为了直径，之后它就一直会是直径
因为首先它不能再接叶子了，其次扩展主干道，相当于说对`这些已经是直径的链长 += w`，原来就已经和直径相等，都`+ w`之后自然还是相等
所以当一个叶子成为右边的直径之后，它就一直是直径了

这样我们就可以用`0/1`标记主干道上的点，会不会是直径？同样用线段树维护，只不过这里用线段树标记`0/1`，是否是直径
如果`dsu.mx[u] + sum[last] - sum[fa] = diam`，那么`u`是右直径，单点修改`change(fa, 1)`
这样，找到右直径的分叉点，只需要**二分最右边的后缀，满足后缀和 > 0**，即最右边的**sum[1...p] > 0**的点`p`即可
此时$$L = p$$，再往左都不可以

综上所述，$$[L, R]$$就是主干道上合法的等待边

## 2025牛客暑期多校训练营9
### L
**[Ping Pong](https://ac.nowcoder.com/acm/contest/108306/L)**
有$$n$$个同学打乒乓球，每个人有一个能力值$$a_i$$，能力值互不相同
每一轮比赛由队首两个人进行，胜者留在场上，败者回到队尾，但是有一个特殊规则
如果一个人连续打了$$n-1$$场比赛，那么他下一场就会输，会插入队尾
现在比赛打了$$k$$轮，求每个同学分别打了多少场比赛
**注意**，如果一个人因为连续打了`n-1`场比赛而被换下去，他只是下去休息了，休息完了还可以继续连着打`n-1`场

**算法分析**
因为$$n$$个同学能力值互不相同，所以能够连着打`n-1`场比赛的，只有能力值最强的同学，不妨记为$$X$$

首先，不难发现，如果轮到$$X$$上场了，一直到$$X$$比赛结束，剩下的$$n-1$$个人相对位置不会变化
```bash
X |  A,B,C,D,E
A B C D E  <--X
```
那么考虑在场上的不是`X`，会是什么情况，考虑**能力值排第二的人**$$Y$$
![](/media/content_img/nowcoderCamp9.png)

> 不难发现，有周期性，周期恰为$$2n - 2$$
当然，实际比赛的时候不一定能分析出来，可以先手动模拟$$O(4n)$$轮，然后尝试找周期

找周期可以用**哈希**，对队列哈希（可以用字符串哈希的方法），`hash(que)`
当且仅当`seen( hash(que) ) = true`的时候，找到了一个周期
从$$X$$上场的时候开始找，此时`hash( start = que )`并标记为`true`，当且仅当`seen[ hash ] = true`的时候
对应走的轮数`prod`就是**周期**

> 注意，最后计算的时候，`hashv`要用**滚动哈希**
记录一下上一次的队首元素`fst`，以及当前的`que.back()`
```bash
hashv -= a[fst] * PW[ que.size()-1 ]
hashv *= P
hashv += a[ que.back() ]
```

## Codeforces Round 1043 (Div. 3)
### C2. The Cunning Seller (hard version)
**[C2. The Cunning Seller (hard version)](https://codeforces.com/contest/2132/problem/C2)**
一次操作，你可以花费$$3^{x+1} + x\cdot 3^{x-1}$$买到$$3^x$$个西瓜，现在你需要**恰好**买到$$n$$个西瓜
同时你的操作次数不能超过$$k$$，问你最少需要多少钱

**算法分析**
最少次数，对应将$$n$$写成`3`进制，操作次数相当于$$n$$的各个`digit`的和
如果求出这个最少次数$$mn$$，已经$$> K$$了，那么无解

否则，你还可以有$$k = K - mn$$次操作，做拆分，每次拆分高位肯定最优

考虑拆分，每一次拆分高位，相当于$$3 \cdot 3^{x-1}$$，本来买`1`个$$3^x$$的
现在要买$$3$$个，多出来了$$2$$次操作，这`2`次操作从$$k$$中扣

假设第$$x$$位上的数是$$a_x$$，能拆的数$$c \in [0, a_x]$$，同时还要满足$$2 \cdot c \leqslant k$$
即$$c \leqslant \min(a_x, k / 2)$$，拆位之后
```bash
从高位到低位
a[x] -= c
a[x - 1] += c * 3
k -= 2 * c
```
这样做完以后，考虑每一位，$$\sum a_i \cdot cost_i$$即可

上一篇：七月算法竞赛选题（二）下一篇：八月算法竞赛选题（一）

看完文章有啥想法