本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-09-24 13:25:43

A

题目大意

给定 $n$ 个数 $a_i$，一次操作可以选一个数使其 $+1$ 或 $-1$，问使得能够选出三个相等的数的最小操作数。

sol.

首先最终选出的三个数的值一定是三个数初始值的中位数，比较显然，然后就只需要给 $a_i$ 排序，枚举中位数 $a_i$，对 $a_{i+1}-a_{i-1}$ 取 $\min$ 即可。

时间复杂度 $O(n \log n)$。

B

题目大意

有一个金字塔，第 $i$ 层有 $i$ 个房间，房间 $(i,j)$ 可以通向房间 $(i+1,j),(i+1,j+1)$，在房间 $(i,j)$ 放置火把可以给所有它能到达的房间增加 $1$ 的亮度值，你现在可以在若干个房间放置火把，给定 $n$，求出使得房间 $(1,1),(2,1) \dots (n,1)$ 的亮度值之和最大、对于 $[1,n]$ 每一层内的房间都有相同亮度值的方案。

sol.

首先第 $i$ 层所有房间的最大亮度值是 $i$，因为只有 $i$ 个房间能够到达 $(i,1)$，然后只需要在每一层的第一个和最后一个房间放置火把即可达到这个上界并满足限制。

C

题目大意

初始你有一个集合 $S$，包含 $1 \dots n$ 的 $n$ 个正整数，每次操作你可以选择一个正整数 $k$，删掉 $S$ 中最小的 $k$ 的倍数，并花费 $k$ 的代价，求出使得 $S$ 变成 $T$ 的最小代价。

sol.

考虑贪心，从 $1$ 到 $n$ 枚举 $k$，把能删的数全删掉。从小到大依次枚举 $k$ 的倍数 $i$，若 $i$ 需要保留，说明不能再用 $k$ 删数，直接枚举下一个 $k$，否则若 $i$ 没有被删过，则将总代价加上 $k$。

时间复杂度为调和级数 $O(n \log n)$。

代码：

#include <bits\/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAXN = 1e6+5;
 
int n;
char s[MAXN];
bool use[MAXN];
ll ans;
 
void solve() {
    for (int i = 1; i <= n; i++) use[i] = 0;
 
    scanf("%d", &n);
    scanf(" %s", s + 1);
 
    ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            if (s[j] == '1') break;
            if (!use[j]) use[j] = 1, ans += i;
        }
    }
 
    printf("%lld\n", ans);
}
 
int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

D

题目大意

$n$ 个史莱姆排成一排，第 $i$ 个血量为 $a_i$，你正在操控第 $k$ 个史莱姆。每次你可以选择和左边或右边相邻的史莱姆合并，合并后血量变为两者之和，若血量 $<0$ 则立即死亡，问最终是否能够与第 $1$ 或第 $n$ 个史莱姆合并并存活。

sol.1

现场思路。

设 $a_i$ 的前缀和数组为 $s_i$，已经合并了 $[l,r]$ 区间内的史莱姆，设当前血量为 $cur$, 则 $cur=s_r-s_{l-1}$。
考虑求出目前一直往左合并能够到达的左端点 $L$，发现需要满足 $cur+s_{l-1}-\max_{i=L}^{l-1}s_{i-1} \le 0$，可以二分求出。若 $L=1$ 那么直接返回 YES，否则考虑贪心，若区间 $[L,l-1]$ 内存在位置 $l'$ 使得 $s_{l-1}-s_{l'-1} \ge 0$，也就是可以让血量增加的位置，则执行 $l \gets l'$，不存在则不动。对右端点同样执行上述过程，若 $[l,r]$ 没有变化，则直接返回 NO。

由于每轮要么区间 $[l,r]$ 至少延长 $1$，要么返回 YES 或 NO ，二分使用 ST 表为 $O(\log n)$, 所以总时间复杂度为 $O(n \log n)$。

sol.2

如果我们现在想向左合并，那么当前血量越大越好，设 $mxR$ 为 $\max_{i=k+1}^r s_i-s_k$，$mxL$ 同理，其中 $r$ 为当左端点在取到 $mxL$ 处时，右端点所能到达的最靠右的位置，$l$ 的定义同理。初始时 $l=r=k, mxL=mxR=0$，每轮先尝试向左延长左端点，若成功则更新 $mxL$，否则向右尝试延长右端点，若成功则更新 $mxR$，否则说明已经没有史莱姆可以合并，返回 NO 即可。

两个指针最多将 $[1,n]$ 扫一遍，时间复杂度 $O(n)$。

代码：

#include <bits\/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 1e6+5;
const int Mod = 998244353;

int n, k, a[MAXN];
ll sum[MAXN];

void solve() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);

    sum[k] = 0;
    for (int i = k - 1; i; i--) sum[i] = sum[i + 1] + a[i];
    for (int i = k + 1; i <= n; i++) sum[i] = sum[i - 1] + a[i];

    int l = k, r = k;
    ll mxL = 0, mxR = 0;

    while (l > 1 && r < n) {
        if (mxR + a[k] + sum[l - 1] >= 0) mxL = max(mxL, sum[--l]);
        else if (mxL + a[k] + sum[r + 1] >= 0) mxR = max(mxR, sum[++r]);
        else break;
    }

    puts(l == 1 || r == n ? "YES" : "NO");
}

int main() {
    int T;
    scanf("%d", &T);
    while (T--) {
        solve();
    }
    return 0;
}

E

题目大意

给定一个质数 $n$ 以及长度为 $n$ 的序列 $b_i$，构造 $n \times n$ 的方阵 $a_{i,j}$，满足:

• $a_{i,i}=b_i$.
• 对于任意 $1 \le r1 < r2 \le n,1 \le c1 < c2 \le n$，$a_{r1,c1}+a_{r2,c2} \not \equiv a_{r1,c2}+a_{r2,c1} \pmod{n}$.

sol.

将第二条限制移项得到 $a_{r1,c2}-a_{r1,c1} \not \equiv a_{r2,c2}-a_{r2,c1}$，由此我们考虑到差分，设 $d_{i,j}=a_{i,j}-a_{i,j-1}$，我们有 $\sum_{i=c1+1}^{c2}d_{r1,i} \not \equiv \sum_{i=c1+1}^{c2} d_{r2,i}$，考虑如下构造 $d_{i,j}$:

$$ \begin{bmatrix} 0 &0 &\cdots &0 \ 1 &1 &\cdots &1 \ 2 &2 &\cdots &2 \ \dots &\dots &\ddots &\dots \ n-1 &n-1 &\cdots &n-1 \end{bmatrix} $$

即 $d_{i,j}=i-1$。

如此一来，设 $x=c2-c1$，那么有 $\sum_{i=c1+1}^{c2}d_{r1,i}=x(r1-1), \sum_{i=c1+1}^{c2} d_{r2,i}=x(r2-1)$。
因为 $r1 \not \equiv r2, 1 \le c1 < c2 \le n$，而以上全部为等价变换，所以限制二被满足当且仅当对于任意 $x \in [1,n-1],x \cdot r1 \not \equiv x \cdot r2$，又因为 $n$ 为质数，所以 $x$ 的逆元一定存在，也就证明了如此构造一定满足限制。

接下来只需要根据 $a_{i,i}=b_i$ 推出 $a$ 每一行的值即可。

F

题目大意

你有一个下标从 $0$ 开始的无限长的字符串 $S$，按照如下方式生成：

• $S$ 初始为 $\texttt{0}$。
• 令 $S'=S$，将 $S'$ 的每一位 0-1 翻转，然后执行 $S \gets S+S'$，重复该操作无限次。

给定 $n,m$，求出 $S_{0,\dots m-1}$ 与 $S_{n, \dots n+m-1}$ 间的汉明距离。

sol.

首先注意到 $S_i= \texttt{1}$ 当且仅当 $\operatorname{popccount} (i) \bmod 2=1$，很好证明，第 $i$ 次操作相当于给下标 $j(0 \le j < 2^i)$ 全部加上 $2^i$，$\operatorname{popccount} (j)$ 奇偶性翻转，恰好对应于 0-1 翻转。赛时降智没想到这个结论，想到了就马上会了。

那么两个位置 $S_i,S_{i+n}$ 不同当且仅当两个下标的 $\operatorname{popccount}$ 奇偶性不同，现在做法已经十分明晰了——数位 dp，设数组 $f_{i,0/1,0/1,0/1}$，表示考虑到第 $i$ 位时对应的下标 $j$ 的个数，满足 $j$ 与 $j+n$ 两个下标 $\operatorname{popccount}$ 异或结果的奇偶性、第 $i-1$ 的进位以及 $j$ 是否大于 $n$，转移比较明显。

代码：

#include <bits\/stdc++.h>
using namespace std;

typedef long long ll;
const int MAXN = 1e5+5;
const int Mod = 998244353;

ll n, m;
ll f[64][2][2][2];

inline ll dp() {
	scanf("%lld%lld", &n, &m); m--;

	memset(f, 0, sizeof(f));
	f[0][0][0][0] = 1;

	for (int i = 0; i <= 61; i++)
		for (int j = 0; j < 2; j++)\/\/异或和
			for (int k = 0; k < 2; k++)\/\/进位
				for (int l = 0; l < 2; l++) if (f[i][j][k][l]) {\/\/大小关系
					bool gm = m >> i & 1, gn = n >> i & 1;
					for (int p = 0; p < 2; p++)
						f[i + 1][j ^ p ^ (p + gn + k & 1)][gn + p + k >> 1][p > gm || (p == gm && l)] += f[i][j][k][l];
				}

	return f[62][1][0][0];
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--) {
		printf("%lld\n", dp());
	}
	return 0;
}