Codeforces Round 1125(Div. 3)

A. In Search of Convenience

题意

路由器位于整数坐标点 $(x_0,y_0)$ ，信号覆盖半径为整数 $R$ 。找出任意一个整数坐标点，使它与路由器的距离恰好等于 $R$ 。

思路

沿水平方向移动 $R$ ，直接选择 $(x_0+R,y_0)$ 。

这个点的横坐标差为 $R$ ，纵坐标差为 $0$ ，所以距离为：

\sqrt{R^2+0^2}=R.

由于 $x_0$ 、 $y_0$ 、 $R$ 都是整数，答案的坐标也都是整数，满足要求。

时间复杂度为 $O(1)$ ，额外空间复杂度为 $O(1)$ 。

代码

C++
void Solve() {
    int x0, y0, R;
    std::cin >> x0 >> y0 >> R;
    std::cout << x0 + R << ' ' << y0 << '\n';
}

B. Did Not Go to Print

题意

有 $n$ 份文档，第 $i$ 条指令对应编号为 $i$ 的文档。打印机的内存采用后进先出的方式存放文档，指令有三种：

1：把文档 $i$ 放到内存顶部。
2：内存非空时，打印并移除顶部文档；内存为空时，打印文档 $i$ 。
3：直接打印文档 $i$ ，不改变内存中的文档。

找出所有没有被打印的文档编号，并按升序输出。

思路

“放到顶部、取出顶部”正好对应栈，因此用 std::stack<int> 模拟打印机内存。

另外，用布尔数组 v 记录每份文档是否被打印：

遇到 1，将当前编号 $i$ 入栈。
遇到 2 且栈非空，将栈顶编号标记为已打印，然后弹出栈顶。
其余情况，即 2 且栈为空，或指令为 3，将当前编号 $i$ 标记为已打印。

所有指令处理完后，从 $1$ 到 $n$ 扫描 v，把未打印的编号放进答案数组。扫描顺序已经是升序，无需额外排序。

例如，指令为 12：先将文档 $1$ 入栈，再打印栈顶文档 $1$ ，因此文档 $2$ 没有被打印。

每条指令只进行常数次栈操作，时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

代码

C++
void Solve() {
    int n; std::string s; std::cin >> n >> s;
    std::stack<int> st;
    std::vector<bool> v(n + 1, false);
    for (int i = 1; i <= n; ++i) {
        if (s[i - 1] == '1') {
            st.push(i);
        } else if (s[i - 1] == '2' && !st.empty()) {
            v[st.top()] = true;
            st.pop();
        } else {
            v[i] = true;
        }
    }
    std::vector<int> ans;
    for (int i = 1; i <= n; ++i) {
        if (!v[i]) {
            ans.push_back(i);
        }
    }
    std::cout << ans.size() << '\n';
    for (int x : ans) {
        std::cout << x << ' ';
    }
    std::cout << '\n';
}

C. Unrequited Love

题意

有 $n$ 个琴键，第 $i$ 个琴键的数值为 $a_i$ 。起点为 $i$ 的三和弦使用琴键 $i$ 、 $i+2$ 、 $i+4$ ，产生的数值为：

b_i=a_i+a_{i+2}-a_{i+4}.

统计有多少对不同的三和弦，它们的数值相同，并且没有共用任何琴键。每对只计算一次，不区分选择顺序。

思路

首先确定哪些三和弦会共用琴键。设两个起点为 $j<i$ ，它们使用的琴键集合分别是：

\{j,j+2,j+4\},\qquad \{i,i+2,i+4\}.

这两个集合相交，当且仅当 $i-j$ 为 $2$ 或 $4$ ：

相差 $2$ ，共用两个琴键。
相差 $4$ ，共用一个琴键。
相差 $1$ 或 $3$ ，两组琴键的奇偶性不同，没有交集。
相差至少 $5$ ，两组琴键的范围没有交集。

因此，问题转化为：统计数值相等、起点差不为 $2$ 或 $4$ 的数对。

从左到右处理三和弦，记录前面各个数值出现的次数。处理当前起点 $i$ 时：

cnt[b[i]] 是前面所有与当前三和弦等值的三和弦数量，先加入答案。
将当前数值的出现次数加一。
如果与起点 $i-2$ 的三和弦等值，减去这一对。
如果与起点 $i-4$ 的三和弦等值，也减去这一对。

每一对都只在处理较大起点时统计，所以不会重复。

由于 $a_i\in[-10000,10000]$ ，三和弦数值的范围为 $[-30000,30000]$ 。数组下标不能为负，因此统一加上 30000，把范围变成 $[0,60000]$ 。统一平移不影响两个数是否相等。

每组时间复杂度为 $O(n)$ ，空间复杂度为 $O(n+60001)$ ；计数数组只在程序中初始化一次。

代码

C++
void Solve() {
	int n; std::cin >> n;
	std::vector<int> a(n);
	for (auto& i : a) {
		std::cin >> i;
	}
	std::vector<int> b(n - 4);
	static int cnt[60001];
	int ans = 0;
	for (int i = 0; i < n - 4; i++) {
		b[i] = a[i] + a[i + 2] - a[i + 4] + 30000;
		ans += cnt[b[i]]++;
		if (i >= 2 && b[i] == b[i - 2]) {
			ans--;
		}
		if (i >= 4 && b[i] == b[i - 4]) {
			ans--;
		}
	}
	for (const auto& i : b) {
		cnt[i] = 0;
	}
	std::cout << ans << '\n';
}

D. Precision Alignment

题意

有 $n$ 个实验室，每个实验室有三个读数 $(a,b,c)$ ，它们的顺序固定。一次操作可以在一个实验室内执行以下三种调整之一：

c\mathrel{+}=\operatorname{sgn}(a-b),\qquad b\mathrel{+}=\operatorname{sgn}(a-c),\qquad a\mathrel{+}=\operatorname{sgn}(b-c).

其中，正数的符号为 $1$ ，负数的符号为 $-1$ ，零的符号为 $0$ 。每次操作都使用当时的读数。

所有实验室合计最多进行 $k$ 次操作，希望最大化调整后各实验室三数之和的最小值。

思路

先解决一个实验室的问题：设初始总和为 $s=a+b+c$ ，将总和提高到至少 $x$ ，最少需要多少次操作。

如果 $x\le s$ ，无需操作。下面只考虑 $x>s$ 。

情况一：三个数全相等。

如果 $a=b=c$ ，三种操作的增量都是 $0$ ，无法改变任何读数，也就无法提高总和。

情况二：存在逆序。

如果 $a>b$ ，可以固定 $a,b$ ，不断执行 $c+=1$ ；如果 $b>c$ ，可以固定 $b,c$ ，不断执行 $a+=1$ 。

只要不满足 $a\le b\le c$ ，上述两种逆序至少存在一种。所以每次操作都可以使总和增加 $1$ ，提高到 $x$ 的最少操作数就是 $x-s$ 。

情况三： $a\le b\le c$ ，但不全相等。

此时还没有能使总和增加的操作，必须先制造逆序。可以选择：

连续减小 $b$ ，直到 $b<a$ ，需要 $b-a+1$ 次。
当 $a<b$ 时，连续减小 $c$ ，直到 $c<b$ ，需要 $c-b+1$ 次。

由于不全相等， $a<c$ ，所以第一种方式总能执行。如果 $a=b$ ，第一种方式只需一次，也是最优；否则两种方式都能执行。因此最少需要先减少：

d=\min(b-a,c-b)+1

次，才能制造逆序。

这个次数也是下界：首次出现逆序前，没有增加操作；要让 $a>b$ 或 $b>c$ ，至少得把对应的初始间隔缩小到负数，而一次操作至多将这个间隔缩小 $1$ 。

做完 $d$ 次减少操作后，总和从 $s$ 变为 $s-d$ 。之后利用逆序，每次增加 $1$ ，还需要 $x-s+d$ 次。因此最少操作数为：

d+(x-s+d)=x-s+2d.

例如 $(0,0,5)$ 的初始总和为 $5$ 。先将 $b$ 减到 $-1$ ，得到 $(0,-1,5)$ ，再让 $c$ 增加两次，就能让总和达到 $6$ ，总共需要 $3$ 次操作。

接下来二分最终最小和 $x$ 。要让所有实验室的总和都不低于 $x$ ，各实验室所需的最少操作数可以独立计算；这些费用之和不超过 $k$ ，目标就可行。

目标越大，需要的操作越多，因此可行性具有单调性。设初始最小和为 $l$ ：

不做操作就能达到 $l$ ，它是可行下界。
一次操作至多使某个实验室的总和增加 $1$ ，所以答案不会超过 $l+k$ 。

二分区间为 $[l,l+k]$ 。判定时逐项从剩余预算 rst 中扣除费用，费用超出预算就立即返回，避免把所有费用累加后溢出。

时间复杂度为 $O(n\log(k+2))$ ，最多约 $60$ 次判定；空间复杂度为 $O(n)$ 。

代码

C++
void Solve() {
	int n, k; std::cin >> n >> k;
	std::vector<std::pair<int, int>> v(n);
	int l = LLONG_MAX;
	for (auto &[s, w] : v) {
		int a, b, c; std::cin >> a >> b >> c;
		s = a + b + c; w = 0;
		if (a == b && b == c) {
			w = -1;
		} else if (a <= b && b <= c) {
			w = 2 * (std::min(b - a, c - b) + 1);
		}
		l = std::min(l, s);
	}
	auto check = [&](int x) {
		int rst = k;
		for (auto [s, w] : v) {
			if (x <= s) {
				continue;
			}
			if (w == -1) {
				return false;
			}
			int nd = x - s + w;
			if (nd > rst) {
				return false;
			}
			rst -= nd;
		}
		return true;
	};
	int r = l + k;
	while (l < r) {
		int mid = l + (r - l + 1) / 2;
		if (check(mid)) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	std::cout << l << '\n';
}

E. Repentance Is Already on the Way

题意

两条平行道路上各有 $n$ 座建筑。记第一行的第 $i$ 座建筑为 $A_i$ ，第二行的第 $i$ 座建筑为 $B_i$ ，所属公司的编号分别为 $a_i,b_i$ 。

可用道路只有竖边 $A_iB_i$ ，以及相邻列之间的两条斜边 $A_iB_{i+1}$ 、 $B_iA_{i+1}$ 。同公司建筑之间的道路长度为 $2$ ，不同公司之间为 $1$ 。

从 $A_1$ 出发，恰好访问每座建筑一次，可以在任意建筑结束，求路线的最大总长度。

解题思路

虽然题目要求寻找一条经过全部建筑的路径，但这张图的结构使候选路线只有 $n$ 条：每个终点 $B_j$ 对应唯一一条路线。

首先，所有边都连接两行之间的建筑，所以沿路径访问的建筑一定在 $A$ 行和 $B$ 行之间交替。总共访问 $2n$ 座建筑，从 $A_1$ 开始，终点必然在 $B$ 行。

固定终点为 $B_j$ 。考虑第 $i$ 列与第 $i+1$ 列之间的切口，只有两条道路能跨过这个切口：

A_iB_{i+1},\qquad B_iA_{i+1}.

当 $i<j$ 时，起点和终点位于切口两侧，路径跨过切口的次数必须为奇数。因此只能使用一条跨边。左侧的 $2i$ 座建筑会先被连续访问，从 $A_1$ 开始交替访问偶数座建筑后，离开左侧时必然位于 $B$ 行，所以使用的是 $B_iA_{i+1}$ 。
当 $i\ge j$ 时，起点和终点都在切口左侧，但还必须访问右侧建筑，跨过切口的次数必须为正偶数。因此两条跨边都要使用。

结合每个中间建筑必须连接两条路径边的要求，可以确定这条路线的全部边：

所有 $B_iA_{i+1}$ ，其中 $1\le i<n$ 。
前 $j-1$ 列的竖边 $A_iB_i$ 。
最后一列的竖边 $A_nB_n$ 。
从第 $j$ 个切口开始的另一条斜边 $A_iB_{i+1}$ ，其中 $j\le i<n$ 。

对应的走法是：先按 $A_1,B_1,A_2,B_2,\ldots,A_j$ 访问前缀；随后沿斜边向右，到最后一列通过竖边转向，再沿另一侧斜边向左，最终到达 $B_j$ 。

例如 $n=4,j=2$ 时，路线为：

A_1\to B_1\to A_2\to B_3\to A_4\to B_4\to A_3\to B_2.

设这条路线的长度为 $L_j$ 。先计算 $j=1$ 的情况：使用所有相邻列之间的两条斜边，加上最后一列的竖边。

L_1=1+[a_n=b_n] +\sum_{i=1}^{n-1}\left(2+[a_i=b_{i+1}]+[b_i=a_{i+1}]\right).

这里 $[P]$ 表示条件 $P$ 成立时为 $1$ ，否则为 $0$ 。

当终点从 $B_j$ 改为 $B_{j+1}$ 时，边集合只发生一个替换：删除斜边 $A_jB_{j+1}$ ，加入竖边 $A_jB_j$ 。因此：

L_{j+1}-L_j =(1+[a_j=b_j])-(1+[a_j=b_{j+1}]) =[a_j=b_j]-[a_j=b_{j+1}].

存 $L_1$ ，然后按这个差值递推所有 $L_j$ ，维护最大值即可。 $n=1$ 时没有斜边，答案就是唯一竖边的长度。

时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。

代码

C++
void Solve() {
	int n; std::cin >> n;
	std::vector<int> a(n), b(n);
	for (auto &i : a) {
		std::cin >> i;
	}
	for (auto &i : b) {
		std::cin >> i;
	}
	int cur = 1 + (a[n - 1] == b[n - 1]);
	for (int i = 0; i + 1 < n; i++) {
		cur += 2 + (a[i] == b[i + 1]) + (b[i] == a[i + 1]);
	}
	int ans = cur;
	for (int i = 0; i + 1 < n; i++) {
		cur += (a[i] == b[i]) - (a[i] == b[i + 1]);
		ans = std::max(ans, cur);
	}
	std::cout << ans << '\n';
}

F. Tea Blend

题意

有 $n$ 包茶，每包的强度是正整数 $a_i$ 。选择任意一对下标 $(i,j)$ ，先取前 $j$ 包茶，再额外取第 $i$ 包茶，混合后的强度为：

F(i,j)=a_i\prod_{k=1}^{j}a_k.

统计有多少对 $(i,j)$ ，使 $F(i,j)$ 的正约数个数为奇数。 $i$ 和 $j$ 独立选择，都在 $[1,n]$ 内，没有 $i\le j$ 的限制。

思路

第一步：将约数问题转化为完全平方数问题。

正整数的约数通常可以配成 $(d,x/d)$ 。只有当 $x$ 是完全平方数时， $\sqrt{x}$ 会与自己配对。因此，约数个数为奇数，当且仅当这个数是完全平方数。

我们需要统计使 $a_i\prod_{k=1}^{j}a_k$ 为完全平方数的数对。

第二步：只保留质因子指数的奇偶性。

若一个正整数的质因数分解为：

x=\prod_p p^{e_p},

定义它的平方自由核为：

K(x)=\prod_{e_p\text{ 为奇数}}p.

也就是去掉所有平方因子，只保留指数为奇数的质因子。例如：

K(12)=K(2^2\cdot3)=3,\qquad K(45)=K(3^2\cdot5)=5,\qquad K(4)=1.

两个数相乘成为完全平方数，当且仅当它们每个质因子的指数奇偶性都相同，即平方自由核相同。所以：

F(i,j)\text{ 是完全平方数} \iff K(a_i)=K\left(\prod_{k=1}^{j}a_k\right).

先把所有输入数字替换为各自的平方自由核，统计每个核的出现次数 cnt。由于 $i$ 可以选择任意位置，这个计数必须包含整个数组，而不仅是当前前缀。

接下来，对于每个前缀，只要求出它的平方自由核 val，就能增加 cnt[val] 个合法数对。

第三步：维护前缀中指数为奇数的质因子。

前缀乘积可能非常大，但无需真的计算这个乘积，只需维护哪些质因子的指数为奇数。

代码中的 v 保存这些质数，pos[p] 记录质数 $p$ 在 v 中的位置加一，0 表示它不在集合中。

处理一个平方自由核时，它的每个质因子只出现一次，因此对每个质因子 $p$ 切换状态：

$p$ 原本不在 v 中，就加入，表示指数从偶数变为奇数。
$p$ 原本在 v 中，就删除，表示指数从奇数变为偶数。

删除时，把 v 的最后一个元素放到待删除位置，更新该元素的 pos，再弹出最后一个元素并清空 pos[p]。这样加入和删除都只需要 $O(1)$ 时间，v 也不需要保持有序。

第四步：利用 $a_i\le10^6$ ，限制每次查询的计算量。

每个输入数字的平方自由核都不超过原数，所以一定不超过 $M=10^6$ 。

前缀的平方自由核是 v 中所有质数的乘积。计算时，一旦部分乘积超过 $M$ ，完整乘积就更不可能匹配任何输入数字的核，可以停止本次乘法。

这个循环最多检查 $8$ 个质数，因为最小的八个不同质数之积已经超过 $M$ ：

2\cdot3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19 =9699690>10^6.

在每次乘法前，val 不超过 $M$ ，质数也不超过 $M$ ，因此乘法的中间结果至多为 $10^{12}$ 。

如果 v 为空，前缀的平方自由核就是 $1$ 。如果计算结果不超过 $M$ ，就累加 cnt[val]；否则该前缀没有贡献。超过 $M$ 时只停止本次查询，质因子状态仍然完整保留，因为后续前缀可能再次消去一些质因子，使核重新变小。

例如数组为 $[2,3,6,4]$ 时，各元素的核为 $[2,3,6,1]$ ，这四种核的频次都是 $1$ ：

前缀位置 $j$	前缀乘积的平方自由核	贡献 `cnt[val]`
1	2	1
2	6	1
3	1	1
4	1	1

总答案为 $4$ 。

存 $x$ 的最小质因子，筛表只建立一次，之后用它进行分解。每组结束时，清空最终仍在 v 中的质数位置，以及本组出现过的核的计数；已从 v 删除的质数位置在删除时已经清零。

筛表的时间复杂度为 $O(M\log\log M)$ ，每组处理的时间复杂度为 $O(n\log M)$ 。所有测试合计的时间复杂度为 $O(M\log\log M+(\sum n)\log M)$ ，空间复杂度为 $O(M+n)$ 。

代码

C++
void Solve() {
	const int M = 1000000;
	static int spf[M + 1], cnt[M + 1], pos[M + 1];
	if (!spf[2]) {
		for (int i = 2; i <= M; ++i) if (!spf[i]) {
			spf[i] = i;
			if (i * i <= M) {
				for (int j = i * i; j <= M; j += i) {
					if (!spf[j]) {
						spf[j] = i;
					}
				}
			}
		}
	}
	int n; std::cin >> n;
	std::vector<int> a(n), v;
	for (auto &i : a) {
		std::cin >> i;
		int y = i; i = 1;
		while (y > 1) {
			int p = spf[y], odd = 0;
			while (y % p == 0) {
				 y /= p;
				 odd ^= 1;
			}
			if (odd) {
				i *= p;
			}
		}
		cnt[i]++;
	}
	int ans = 0;
	for (auto i : a) {
		while (i > 1) {
			int p = spf[i];
			i /= p;
			if (pos[p]) {
				int j = pos[p] - 1, q = v.back();
				v[j] = q;
				pos[q] = j + 1;
				v.pop_back();
				pos[p] = 0;
			} else {
				pos[p] = v.size() + 1;
				v.push_back(p);
			}
		}
		int val = 1;
		for (auto i : v) {
			val *= i;
			if (val > M) {
				break;
			}
		}
		if (val <= M) {
			ans += cnt[val];
		}
	}
	for (auto i : v) {
		pos[i] = 0;
	}
	for (auto i : a) {
		cnt[i] = 0;
	}
	std::cout << ans << '\n';
}