十二月算法竞赛选题（三）

[[ slider_text ]]

[[ item.c ]]

十二月算法竞赛选题（三）

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

莫队

## Codeforces Round 948 (Div. 2)
### D
**[D. XORificator](https://codeforces.com/problemset/problem/1977/D)**
给定一个$$n \times m$$的`01`矩阵，你有一个异或器，可以选定某一行进行翻转
如果某一列恰好包含一个`1`，那么称为特殊列，现在要找到，最多能让多少列称为特殊列

**算法分析**
直接做显然是没法做的，考虑每个位置$$(i, j)$$能不能成为**特殊的**，即第`j`列能否称为特殊列
但怎么算最多呢？考虑**哈希**

因为你钦定了哪些列能成为特殊列，那么行翻转与否的状态随之确定
假设第`j`列是`1`的集合为$$S\_j= \\{i\_1, i\_2, \cdots, i\_m\\}$$
你可以枚举这一列哪个位置（即哪个`i`是`1`），然后得到需要翻转的行
但要得到翻转的行，不能再`for`了，怎么办呢？**考虑哈希，每一行（即每个`i`）给一个哈希值**

这样$$S_j = sha(i_1) \oplus sha(i_2) \oplus \cdots \oplus sha(i_m)$$
枚举并钦定$$i$$为这个特殊位置，即`(i, j) = 1`，那么
如果$$i \notin S_j$$，答案是$$S_j \cup i$$，也就是$$S_j \oplus sha(i)$$
否则的话，要$$S_j - \\{i\\}$$，答案也是$$S_j \oplus sha(i)$$

综上所述，$$(i, j) = 1$$需要翻转的行的集合是$$st = S_j \oplus sha(i)$$

怎么求最大呢？实际上，枚举$$(i, j)$$的时候，可以让`cnt[st]++`，哪个集合`S`**出现次数最多**
我们就选这个集合，记为$$tar$$

> 怎么输出方案

仍然是枚举$$(i, j) = 1$$，如果$$S(j) \oplus sha(i) = tar$$，那么`sha(i)`就是我们钦定要翻转的行的集合
既然已经得到钦定的为`1`的位置$$(i, j)$$
那么就看原来的矩阵，如果原来的`i`位置是`0`，那么要翻转第`i`行，否则不翻转
其他不等于`i`的行，都必须是`0`，如果不是`0`就需要翻转

> 总结

枚举每个点，然后考虑这个点**被哪些集合所包含**（或者是这个点被哪些线段所包含）
往往可以考虑**异或哈希**，给每个**线段（或集合）**一个哈希值

## Codeforces Round 953 (Div. 2)
### D
**[D. Elections](https://codeforces.com/problemset/problem/1978/D)**
有`n`个人参加选举，其中第`i`个候选人的支持者有$$a_i$$个，另外还有`C`名未决定者
未决定者会把票投给**编号最小**的候选人
现在你可以踢掉若干候选人，被踢掉的人，他的支持者$$a_j$$全部变成未决定者，并且会投票给**编号最小**的人
回答对$$i = 1 \to n$$，最少要排除多少候选人，才能让编号为`i`的人赢得选举

**算法分析**
如果按支持者从大到小排序，相同支持者按编号从小到大排序
如果$$i$$就在`rank 1`，不需要踢人，`res[i] = 0`
否则，就一定要踢人

但是，踢掉一个人，就相当于把**最大值转移给当前还“活着的”，编号最小的人**
1）如果`a[i] = maxv`，那么此时$$a_0 = a_0 + maxv$$
如果$$a_0 > 0$$，那么获胜的就是$$a_0$$了，不会轮到$$i$$，所以编号$$[0, i-1]$$都要踢掉
如果$$a_0 = 0$$，只要$$i > 0$$，即`i`不是第一个，那么也轮不到`i`，也要踢掉$$[0, i-1]$$

2）如果`a[i] < maxv`，那么只要$$a_i$$不是第一个，这个`maxv`的值就会转移给`a[0]`
也轮不到$$i$$

综上所述，$$[0, i-1]$$所有数都应该踢掉，并且他们的得票应该要算到`i`身上
另外，由于$$j \in [0, i-1]$$被踢出之后，它的支持者会转移到$$j+1$$身上
所以可以一开始令`a[0] += C`不影响，反正后续`C`会继续转移到`j = 2, 3, ...., i`上

既然前缀都踢掉了，`i`能获得的**额外支持者**的票数，可以很容易用前缀和求出来
可以用一个**多重集合**$$S$$来维护**还活着的人的票数**
```bash
S.erase( {a[i],  i} )
S.insert( {a[i]+extra,  i} )
```
如果此时`(S 的最大值的下标) = i`的话，那么答案就是`i - 1`
否则呢？`a[i] = a[i] + extra`
1）如果`Smaxv > a[i]`，那么此时再删掉一个`Smaxv`即可，把它加到`i`上，`i`就是最大的了
答案对应是`i`
2）如果`Smaxv = a[i]`，这种情况是不会发生的，因为`[0, i-1]`都踢掉了，还活着的值`= a[i]`的最小下标就是`i`
不会是其他数

如果`S 的最大值的下标`$$\neq i$$，答案是$$i$$

计算完的时候，记得把`i`这个位置的数从`S`中删掉

## Codeforces Global Round 31
### C
**[C. XOR-factorization](https://codeforces.com/contest/2180/problem/C)**
给定`n, k`，构造$$a_1 \oplus a_2 \oplus \cdots \oplus a_k = n$$
必须最大化$$a_1 + a_2 + \cdots + a_k$$，其中还必须$$0 \leqslant a_i \leqslant n$$

**算法分析**
如果$$k$$是奇数，很简单，$$\forall a_i = n$$，就可以了
考虑$$k$$是偶数的情况，有一种错误的贪心如下
放`k - 2`个`n`，然后找两个`x, y`，使得$$x \oplus y = n$$，最大化$$x + y$$
```math
\displaystyle
x + y = (x \oplus y) + 2(x \textbf{ and } y)
```
考虑`x and y`，实际上就是最大化这个值
此时对于`n >> j & 1 = 1`的位`j`，`x, y`在这个位上只能是`(1, 0)`，`x and y`这一位的贡献是确定的，只能是`0`
可以调整的，只能是`n = 0 的位`，此时`x, y`在这个位上都放`1`，显然可以最大化`x and y`

所以如果`n`是`2 的幂`，那么只能是`(x, y) = (n, 0)`这样组合下去
否则的话，找到`n 最高为 1 的位 j1 和 次高为 1 的位 j2`
```bash
x 在 j1 位放 1，j2 位放 0
y 在 j1 位放 0，j2 位放 1
```
至于`j2-1....0`的低位，如果是`1`，那么只把这个`1`分配给`x`
如果是`0`，则`x, y`这个位都放上`1`
**注意**，因为我们在高位`j1, j2`上拆掉了`1`，你在更低的位上放`1`，是不会超过`n`这个上界的

> 但是这样做不对

因为按位加法的推广如下
对每一位$$k$$，记一下有多少个数在该位是$$1$$，不妨设为$$t_k$$

```math
\displaystyle
\sum_{i = 1}^{n} a_i = \left( \bigoplus_{i = 1}^{n}a_i \right) + 2 \sum_{k \geqslant 0} \left( \lfloor \dfrac{t_k}{2} \rfloor \cdot 2^k\right)
```
补上的这一项很简单，就是异或操作，对于$$t_k$$个`1`，如果两两配对的话
有$$\lfloor t_k / 2 \rfloor$$组，这些组本来$$\sum$$起来应该有值的
贡献是$$2 (\lfloor t_k / 2 \rfloor \cdot 2^{k})$$，但是异或操作把这部分的贡献变成`0`
要补上

除此之外，还有容斥形式
```math
\displaystyle
\sum_{i = 1}^{n} a_i = \left( \bigoplus_{i = 1}^{n}a_i \right) + \sum_{m = 2}^{n}(-1)^{m} 2^{m-1} \sum_{1 \leqslant i_1, i_2, \cdots i_m \leqslant n}(a_{i_1} \textbf{ and } a_{i_2} \textbf{ and } \cdots \textbf{ and } a_{i_m})
```
也就是，枚举所有大小为$$m$$的子集，取$$\textbf{and}$$操作，然后乘以容斥系数$$(-1)^{m}2^{m-1}$$
累加上去

比如$$n = 2$$，只有$$m = 2$$这一项，容斥系数是$$(-1)^2 2^1 = 2$$
就是$$x + y = x \oplus y + 2(x \textbf{ and } y)$$

那么$$n = 3$$呢
```math
\displaystyle
a + b + c = (a \oplus b \oplus c) + 2( (a \textbf{ and } b) + (a \textbf{ and } c) + (b \textbf{ and } c) ) - 4(a \textbf{ and } b \textbf{ and } c)
```

> 根据之前的分析，已经知道了拆成`K - 2`个$$n$$和$$(x \oplus y = n)$$不一定是最优的

但可以采用类似的贪心策略，先放`K`个$$n$$
从高位到低位，如果能找到两个数在高位都拆过`1`了，那么之后往低位走
出现`0`的位，这两个数都可以在这一位放上`1`
**（否则的话，放`1`就炸了，一定会超过`n`）**

从高位到低位，如果`(n >> j & 1) = 1`，说明对于这一位，需要将`a[1...K]`其中一个数
这一位置为`0`，因为要最大化和，只置一个数为`0`即可，我们称这一操作为**`拆 1`**

另外，对于高位的`1`，我们要尽可能将**不同的数**拆掉`1`
这样对于之后的`0`，才有更多的数可以用（被拆掉高位的`1`的数，才能在这一位放上`1`）

之后遇到`0`了，我们从候选集合（被拆过高位`1`的数的集合）中，**两两配对**，在这一位放上`1`

```bash
auto hi = topbit(n);
vector<i64> res(K, n);

int ptr = 0;
// j = [0, ptr) 表示当前被拆过 1 的数有哪些
for (int i = hi; i >= 0; i--) {
	auto bit = n >> i & 1;

if (bit == 1) {
		// ptr >= K，所有数都被拆过，此时选一个 res[0] 继续拆即可
		// 否则，ptr++，每一次都拆不同的数
		if (ptr >= K) res[0] ^= (1LL << i);
		else res[ptr++] ^= (1LL << i);
	}
	else {
		// 当前第 i 位是 0，对于 [0, ptr) 这些拆过高位 1 的数
		// 可以两两配对，都放上 1
		for (int j = 0; j + 1 < min(ptr, K); j += 2) {
			res[j] |= (1LL << i);
			res[j+1] |= (1LL << i);
		}
	}
}
```

## Codeforces Round 953 (Div. 2)
### E
**[E. Computing Machine](https://codeforces.com/problemset/problem/1978/E)**
给定两个串`s, t`，只有`0 和 1`，再给定`q`次询问，每个询问给出`[l, r]`
记`s, t`在`[l, r]`上的子串分别是`a, b`，可以进行任意次如下操作
1）若**存在一个**$$i, i+2 \in [l, r]$$，`a[i] = a[i+2] = 0`，那么可以使得`b[i+1]`变成`1`
2）若**存在一个**$$i, i+2 \in [l, r]$$，`b[i] = b[i+2] = 1`，那么可以使得`a[i+1]`变成`1`

每个询问单独回答，最多可以使得`a`有多少个`1`

**算法分析**
要让`a`中的`1`尽可能的多，就要让原来是`0`的也尽量变成`1`
那么就要使得`0`被两个`b 中的 1`夹住，也就是说，`b`中的`1`变得尽可能多，答案一定不会劣
不难发现，`b 中的 1 和 a 中的 0`构成类似`zig-zag`路径

**这么多询问，又不带修改**，可以考虑**莫队**
最优操作一定是先把`操作 1`给做完，构造出`b 中尽可能多的 1`，然后再`操作 2`
莫队需要注意的是，区间的增减变化，会导致原来已经变成`1`的`b`回退到`0`

![](/media/content_img/cf953E.png)

```bash
void solve(){
    int B = sqrt(n);
    sort(qry.begin(), qry.end(), [&](const arr &a, const arr &b) {
        int bl = a[0] / B;
        if (bl != b[0] / B) return bl < b[0] / B;

if (bl % 2) return a[1] < b[1];
        else return a[1] > b[1];
    });

auto nb = b;

int l = 1, r = 0, res = 0;
    auto fixb = [&](int p, int d) -> void {
        assert(nb[p] == 1);

if (p+2 <= min(r, n) and nb[p+2] == 1) {
            if (a[p+1] == 0) res += d;
        }

if (p-2 >= max(1, l) and nb[p-2] == 1) {
            if (a[p-1] == 0) res += d;
        }

};

auto add = [&](int p) -> void {
        if (p <= 0 or p > n) return;

if (a[p] == 1) res++;
        else {
            if (p+2 <= min(r, n) and a[p+2] == 0 and b[p+1] == 0) nb[p+1] = 1, fixb(p+1, 1);
            if (p-2 >= max(1, l) and a[p-2] == 0 and b[p-1] == 0) nb[p-1] = 1, fixb(p-1, 1);
        }

if (nb[p]) fixb(p, 1);
    };

auto del = [&](int p) -> void {
        if (p <= 0 or p > n) return;

if (a[p] == 1) res--;
        else {
            if (p+2 <= min(r, n) and a[p+2] == 0 and b[p+1] == 0) fixb(p+1, -1), nb[p+1] = 0;
            if (p-2 >= max(1, l) and a[p-2] == 0 and b[p-1] == 0) fixb(p-1, -1), nb[p-1] = 0;
        }

if (nb[p]) fixb(p, -1);
    };
}
```
### F
**[F. Large Graph](https://codeforces.com/problemset/problem/1978/F)**
给定一个数组`a[1...n]`，构造一个$$n \times n$$的矩阵`b`
第一行就是`a`，从第$$i = 2 \cdots n$$行开始，`b[i] = a 数组向右循环移位 i-1 次`
构造一个图，包含$$n^2$$个顶点，$$(i, j)$$表示$$b(i, j)$$
如果满足$$|i_1 - i_2| + |j_1 - j_2| \leqslant k$$，$$k$$也是给定的

并且$$\text{gcd}(b\_{i\_1, j\_1}, b\_{i\_2, j\_2}) > 1$$，在$$(i_1, j_1), (i_2, j_2)$$之间连边
求所得到的图中连通分量的数量

**算法分析**
题中保证$$k \geqslant 2$$，也就是说，如果`a`中不含有`1`，同一条主对角线上的元素
一定在同一个连通分量中

那么思路基本上是有了，$$\log$$复杂度枚举每个素因子$$p$$
然后将含有素因子$$p$$的$$a_i, a_j$$所在的并查集合并即可
难点是，怎么保证$$|i_1 - i_2| + |j_1 - j_2| \leqslant k$$这个条件成立？

> 观察如下

![](/media/content_img/cf953F.png)

另外可以发现，两个位置$$(i, j)$$的数要想合并
对应到对角线编号上$$id_1, id_2$$，发现$$|i - j| = |id_1 - id_2|$$

这就可以用并查集 + 枚举素因子来实现

上一篇：十二月算法竞赛选题（二）下一篇：2026.1月算法竞赛选题（一）

看完文章有啥想法