A

算法标签: 模拟

问题陈述

给你一个长度为 $N$ 的整数序列：$A=(A_1,A_2,\dots ,A_N)$。
请判断在 $A$ 中是否有相同元素连续出现三次或三次以上的位置。
更正式地说，请判断是否存在一个整数 $i$ 与 $1\le i\le N-2$ 中的 $A_i=A_{i+1}=A_{i+2}$。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 110;

int n, w[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> w[i];

    int i = 0, j = 2;
    while (j < n) {
        if (w[i] == w[j] && w[i] == w[i + 1]) {
            cout << "Yes" << "\n";
            return 0;
        }
        i++, j++;
    }
    cout << "No" << "\n";

    return 0;
}

---

B

算法标签: 栈, 模拟

问题陈述

有一叠 $100$ 纸牌，每张都标有整数 $0$ 。

处理 $Q$ 个查询。每个查询都属于以下情况之一：

• 输入 $1$ ：将一张标有整数 $x$ 的卡片放在堆栈顶部。
• 类型 $2$ ：取出堆栈顶端的卡片，并输出写在该卡片上的整数。在此问题的限制条件下，牌堆中总是至少有一张牌。

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 210;

int n;
int stack[N], top;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    top = 99;
    cin >> n;
    while (n--) {
        int op, val;
        cin >> op;
        if (op == 1) {
            cin >> val;
            stack[++top] = val;
        }
        else cout << stack[top--] << "\n";
    }

    return 0;
}

---

C

算法标签: 前缀和, 贪心

问题陈述

有 $N$ 个黑球和 $M$ 个白球。
每个球都有一个值。第 $i$ 个黑球( $1\le i\le N$ )的值是 $B_i$ ，第 $j$ 个白球( $1\le j\le M$ )的值是 $W_j$ 。

选择零个或更多的球，使得所选黑球的数量至少等于所选白球的数量。在所有这样的选择中，求所选球的数值之和的最大值。

思路

很容易想到时间复杂度$O(n^2)$的做法, 但是球的数量$10^5$级别, 会超时, 因此需要优化到$O(n^2)$以下

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int n, m;
int b[N], w[N], gre;
LL s1[N], s2[N];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> b[i];
	for (int i = 1; i <= m; ++i) cin >> w[i];

	sort(b + 1, b + n + 1);
	reverse(b + 1, b + n + 1);
	sort(w + 1, w + m + 1);
	reverse(w + 1, w + m + 1);

	for (int i = 1; i <= n; ++i) {
		if (b[i] > 0) gre = i;
		s1[i] = (LL) s1[i - 1] + b[i];
	}
	for (int i = 1; i <= m; ++i) s2[i] = (LL) s2[i - 1] + w[i];

	LL res = 0;
	// 枚举选择白球的数量
	for (int k = 0; k <= min(n, m); ++k) {
		int cnt = max(k, gre);
		res = max(res, s2[k] + s1[cnt]);
	}

	cout << res << "\n";
	return 0;
}

---

D

算法标签: $dfs$

问题陈述

给你一个简单相连的无向图，图中有 $N$ 个顶点，编号为 $1$ 到 $N$，有 $M$ 条边，编号为 $1$ 到 $M$。边 $i$ 连接顶点 $u_i$ 和 $v_i$，其标签为 $w_i$。

在从顶点 $1$ 到顶点 $N$ 的所有简单路径（不经过同一顶点多次的路径）中，求路径上边的标签的最小 XOR。

关于 XOR 的说明

对于非负整数 $A$ 和 $B$，它们的 XOR $A\oplus B$ 定义如下：

• 在 $A\oplus B$ 的二进制表示中，当且仅当 $A$ 和 $B$ 的相同数位中恰好有一位是 $1$ 时，$2^k(k\ge 0)$ 对应数位上的数字是 $1$；否则，它是 $0$。

例如，$3\oplus 5=6$（二进制为：$011\oplus 101=110$）。

一般来说，$k$ 个整数 $p_1,\dots ,p_k$ 的 XOR 定义为 $(\cdots ((p_1\oplus p_2)\oplus p_3)\oplus \cdots \oplus p_k)$。可以证明它与 $p_1,\dots ,p_k$ 的顺序无关。

思路

注意到, 点的数量不大于$10$, 直接暴搜

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;
const int N = 12, M = N * N;

int n, m;
int head[N], edge_end[M], next_edge[M], edge_index;
LL w[M];
bool vis[N];
LL res = 9e18;

void add(int ver1, int ver2, LL val) {
    edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], w[edge_index] = val, head[ver1] = edge_index++;
}

void dfs(int u, LL curr) {
    if (u == n) {
        res = min(res, curr);
        return;
    }

    for (int i = head[u]; ~i; i = next_edge[i]) {
        int ver = edge_end[i];
        if (!vis[ver]) {
            vis[ver] = true;
            dfs(ver, curr ^ w[i]);
            vis[ver] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    memset(head, -1, sizeof head);
    cin >> n >> m;

    while (m--) {
        int u, v;
        LL val;
        cin >> u >> v >> val;
        add(u, v, val);
        add(v, u, val);
    }

    vis[1] = true;
    dfs(1, 0);

    cout << res << "\n";
    return 0;
}

---

E

算法标签: 贪心, $dfs$

问题陈述

给你整数 $N,M$ 和长度为 $M$ 的三个整数序列：$X=(X_1,X_2,\dots ,X_M)$、$Y=(Y_1,Y_2,\dots ,Y_M)$ 和 $Z=(Z_1,Z_2,\dots ,Z_M)$。保证 $X$ 和 $Y$ 中的所有元素都在 $1$ 和 $N$ 之间。
我们称长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots ,A_N)$ 为好序列，当且仅当它满足以下条件时：

• 对于每一个有 $1\le i\le M$ 的整数 $i$，$A_{X_i}$ 与 $A_{Y_i}$ 的 XOR 为 $Z_i$。
  判断是否存在一个好序列 $A=(A_1,A_2,\dots ,A_N)$，如果存在，找出一个使其元素之和 $\sum _{i=1}^N{A}_i$ 最小的好序列。

关于 XOR 的说明

对于非负整数 $A$ 和 $B$，它们的 XOR $A\oplus B$ 定义如下：

• 在 $A\oplus B$ 的二进制表示中，当且仅当 $A$ 和 $B$ 的相同数位中恰好有一位是 $1$ 时，$2^k(k\ge 0)$ 对应数位上的数字是 $1$；否则，它是 $0$。
  例如，$3\oplus 5=6$（二进制为：$011\oplus 101=110$）。

思路

由题意, 分为两步

• 是否存在该序列?
• 如何最小化$A_i$

首先判断是否无解

$A_{X_i}\oplus A_{Y_i}=Z_i$, 对于异或操作有以下性质
$a\oplus b=c,a\oplus c=b,b\oplus c=a$, 异或是可逆的

因为$X_i,Y_i,Z_i$是确定的, $A_{X_i}$和$A_{Y_i}$只要确定一个数, 就可以确定另外一个数

会形成如图的连通块, 在连通块中知道确定一个数, 整个连通块的数都会被确定
如果从$u$到$v$出现了两条不一样的路径, 出现矛盾

如何找这些环的边?

维护并查集, 检查$Z=S_{pat{h}_1}\oplus S_{pat{h}_2}$, 如果不相等无解

如何维护最小值?

在连通块中确定任何一个元素就能确定任意一个元素, 考虑树的根节点

因为异或操作是逐位异或的, 因此位与位之间是独立的, 每一位单独考虑, 因为要求和最小, 因此要求$1$的数量是最小的

算法流程

1. 将图构建成生成树, 检查非树边
2. 求最小值, 逐位考虑, 看根节点是选$0$还是选$1$, 最后知道了根节点的值, 然后整个树的值就知道了

XOR 的性质

XOR 操作具有以下性质：

• 自反性：
  $$A\oplus A=0$$
• 结合律：
  $$(A\oplus B)\oplus C=A\oplus (B\oplus C)$$
• 交换律：
  $$A\oplus B=B\oplus A$$

由于这些性质，调整根节点的值 $A[root]$ 为 $A[root]\oplus off$ 会使得所有顶点的值 $A[x]$ 变为 $A[x]\oplus off$。

一致性调整

假设根节点的值被调整为 $A[root]\oplus off$，那么对于任意顶点 $x$，其值 $A[x]$ 会被调整为：

$$A[x]\oplus off=(A[root]\oplus \text{path\_xor})\oplus off=(A[root]\oplus off)\oplus \text{path\_xor}$$

其中，$\text{path\_xor}$ 是从根节点到顶点 $x$ 的路径上所有边的 XOR 值
这种调整方式确保了所有顶点的值仍然满足边的 XOR 条件

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10, M = 2e5 + 10;

int n, m;
int head[N], edge_end[M], next_edge[M], w[M], edge_index;
int res[N];

void add(int ver1, int ver2, LL val) {
	edge_end[edge_index] = ver2, next_edge[edge_index] = head[ver1], w[edge_index] = val, head[ver1] = edge_index++;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	memset(head, -1, sizeof head);
	cin >> n >> m;

	for (int i = 0; i < m; ++i) {
		int u, v, w;
		cin >> u >> v >> w;
		u--, v--;
		add(u, v, w);
		add(v, u, w);
	}

	memset(res, -1, sizeof res);

	for (int x = 0; x < n; ++x) {
		if (res[x] != -1) continue;

		vector<int> q;
		q.push_back(x);
		res[x] = 0;
		int cnt[30]{0};

		for (int i = 0; i < q.size(); ++i) {
			int u = q[i];
			for (int j = 0; j < 30; ++j) cnt[j] += res[u] >> j & 1;

			for (int j = head[u]; ~j; j = next_edge[j]) {
				int ver = edge_end[j];

				if (res[ver] == -1) {
					res[ver] = res[u] ^ w[j];
					q.push_back(ver);
				}
				else if (res[ver] != (res[u] ^ w[j])) {
					cout << -1 << "\n";
					return 0;
				}
			}
		}

		int off = 0;
		for (int j = 0; j < 30; ++j) {
			if (cnt[j] > q.size() - cnt[j]) {
				off ^= 1 << j;
			}
		}

		for (int ver : q) res[ver] ^= off;
	}


	for (int i = 0; i < n; ++i) cout << res[i] << " ";
	cout << "\n";

	return 0;
}

---

F

算法标签: 分治, 树状数组, $Fenwick-Tree$

问题陈述

给你一个整数 $N,M$ 和一个长度为 $N$ 的非负整数序列 $A=(A_1,A_2,\dots ,A_N)$。

就 $k=0,1,\dots ,M-1$ 求解下面的问题：

定义一个整数序列 $B=(B_1,B_2,\dots ,B_N)$，使 $B_i$ 除以 $M$ 后的余数是 $A_i+k$。求 $B$ 中的倒数。

什么是倒数？
序列 $(A_1,A_2,\dots ,A_N)$ 的反转数是满足 $1\le i<j\le N$ 和 $A_i>A_j$ 的整数对 $(i,j)$ 的个数。

思路

$B_i=(A_i+k)\mathrm{mod}M$. 求$B$的逆序对数量, 首先考虑简单情况, 如果没有$\mathrm{mod}M$, 输出就是原$A_i$的逆序对数量

考虑简单情况, $B_i=A_i+1$, 哪些逆序对数量发生改变?
$B_i=M-1$的那些数如果加$1$, $\mathrm{mod}M$变为$0$, 逆序对数量发生变化, 而对于$0\le B_i\le M-2$的数字, 加上$1$再对$M$取模逆序对数量不会发生变化

因此考虑$B_i=M-1$的情况

会与每一个后面的非$M-1$的位置形成逆序对, 因为在$\mathrm{mod}M$情况下, $M-1$就是最大值

逆序对的变化量$\Delta cnt=-[M-1]+[0]$, 也就是减去变化前$M-1$位置的逆序对数量, 加上变为$0$后与前面形成的逆序对数量
假设当前位置是$p$, 减去的逆序对数量等于$n-p-cn{t}_{M-1}$

因为每个数加$1$, 因此变为$0$后前面与前面形成的逆序对数量等于$p-1$
以上是$k=1$的逆序对数量, 以此类推计算到到$k=M-1$, 也就是$\mathrm{mod}M$的最大余数

第$i$个数什么时候变成$M$?
在$M-A_i$时刻$\mathrm{mod}M$变为$0$, 算法时间复杂度$O(n\log n)$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

typedef long long LL;
const int N = 2e5 + 10;

int n, m;
int w[N], tr[N];
vector<int> change[N];

int lowbit(int val) {
	return val & -val;
}

void add(int u, int val){
	for (int i = u; i <= m; i += lowbit(i)) tr[i] += val;
}

int query(int u) {
	int res = 0;
	for (int i = u; i; i -= lowbit(i)) res += tr[i];
	return res;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n >> m;

	LL res = 0;
	for (int i = 1; i <= n; ++i) {
		cin >> w[i];
		change[m - w[i]].push_back(i);
		res += query(m - w[i] - 1);
		add(m - w[i], 1);
	}

	cout << res << "\n";

	for (int k = 1; k < m; ++k) {
		// 枚举在k时刻从m - 1变为0的所有位置
		for (int j = 0, sz = change[k].size(); j < sz; ++j) {
			int p = change[k][j];
			res -= n - p - (sz - j - 1);
			res += p - 1 - j;
		}
		cout << res << "\n";
	}

	return 0;
}

---

G

算法标签: $FWT$, 状态压缩$dp$

问题陈述

有一个 $H\times W$ 网格，每个单元格都包含 $0$ 或 $1$。从顶部起第 $i$ 行和从左侧起第 $j$ 列的单元格中包含一个整数 $A_{i,j}$。

您可以按照任意顺序执行以下两种操作任意多次：

• 操作 X：选择一个整数 $x$（$1\le x\le H$）。对于每一个整数 $1\le y\le W$，将 $A_{x,y}$ 替换为 $1-A_{x,y}$。
• 操作 Y：选择一个整数 $y$（$1\le y\le W$）。对于每一个整数 $1\le x\le H$，将 $A_{x,y}$ 替换为 $1-A_{x,y}$。

求替换后 $\sum _{x=1}^H\sum _{y=1}^W{A}_{x,y}$ 的最小值。

思路

列的全部情况是$O(2^{18})$, 然后枚举行, 但是时间复杂度来到了$O(H\times 2^W)$, 因为$H$的范围是$2\times 10^5$, 会超时

考虑每一列的操作数是$X$, 设每一行的$0$的数量是$c_0$, $1$的数量是$c_1$, 当$c_0>c_1$的时候这一行不需要翻转
$c_0\le c_1$的情况下, 翻转取得的结果会变好, 因此这一行最小的$1$的数量就是$\min (c1,m-c1)$

设每一行$1$的数量是$p_i$, 那么总的$1$的数量的最小值就是

min⁡0≤X<2W{p(Bi⊕X),W−p(Bi⊕X)} \min _{ 0 \le X < 2 ^ W} \left \{ p(B_i \oplus X), W - p(B_i \oplus X) \right \} 0≤X<2Wmin​{p(Bi​⊕X),W−p(Bi​⊕X)}

动态规划: $f[X][j][c]$, 代表考虑前$j$列, 并且$B_i\oplus X$与$X$在$c$位上不同的行的数量, 换句话说, 就是列的操作数是$X$的情况下, 需要翻转的行的数量

因为每一行的最小值可以确定, 因此答案可以转化为

$$\sum _{c=0}^{W}dp[X][W][c]\times \min (c,W-c).$$

时间复杂度$O(W^2\times 2^W)$

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2e5 + 10, INF = 0x3f3f3f3f;

int r, c;
int row[N];

int f[20][20][1 << 20];
int ans = INF;
char str[20];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> r >> c;
	for (int i = 1; i <= r; ++i) {
		cin >> str;
		for (int j = 0; j < c; ++j) {
			row[i] = row[i] << 1 | (str[j] - '0');
		}
		f[0][0][row[i]] += 1;
	}

	for (int i = 1; i <= c; ++i) {
		for (int j = 0; j <= c; ++j) {
			// 枚举对列的所有操作X
			for (int k = 0; k < 1 << c; ++k) {
				// 不翻转第i列
				f[i][j][k] += f[i - 1][j][k];
				// 翻转第i列
				f[i][j + 1][k] += f[i - 1][j][k ^ (1 << (i - 1))];
			}
		}
	}

	for (int k = 0; k < 1 << c; ++k) {
		int sum = 0;

		// 枚举翻转的列数
		for (int j = 0; j <= c; ++j) {
			sum += f[c][j][k] * min(j, c - j);
		}
		ans = min(ans, sum);
	}

	cout << ans << "\n";
	return 0;
}