CACC 2025 Final

Written by: Joyce-Peng-GitHub

CACC 2025 Final

Day 1

A.

给定 (ai)i=0n−1∈(N∗)n (n∈N∗)(a_i)_{i=0}^{n-1}\in(\mathbb{N}^*)^n\ (n\in\mathbb{N}^*)，求区间乘积大于等于区间长度的区间数，即求满足

∏i=be−1ai≥e−b (b<e≤n)\prod_{i=b}^{e-1}a_i\geq e-b\ (b<e\leq n)

的 (b,e)∈N2(b,e)\in\mathbb{N}^2 的数量。

保证 n≤5×105, ∀i∈N∩[0,n) (ai≤103)n\leq5\times10^5,\ \forall i\in\mathbb{N}\cap[0,n)\ (a_i\leq10^3)。

不知道怎么就过了。特判 is_all_one 是因为有 10%10\% 的测试点满足全为 11，另有 10%10\% 的满足每个数要么为 11 要么为 22 。

inline void solve() {
	size_t n;
	std::cin >> n;
	std::vector<uint64_t> arr(n);
	bool is_all_one = true;
	for (auto &e : arr) {
		std::cin >> e;
		if (e != 1) is_all_one = false;
	}

	if (is_all_one) {
		std::cout << ((n * (n + 1)) >> 1) << '\n';
		return;
	}

	uint64_t ans = ((n * (n + 1)) >> 1);
	for (size_t i = 0; i < n; ++i) {
		uint64_t prod = 1;
		for (size_t j = i + 1; j < n; ++j) {
			prod *= arr[j];
			if (prod >= n - i) break;
			if (prod < j - i + 1) --ans;
		}
	}

	std::cout << ans << '\n';
}

B.

给定数轴上的 n∈N∗n\in\mathbb{N}^* 个点，坐标分别为 x⃗=(xi)i=1n∈Nn\vec{x}=(x_i)_{i=1}^n\in\mathbb{N}^n。为每个点分别指定一个非负实数 rir_i 作为半径，使得

∀i∈N∩[1,n) (xi+ri≤xi+1−ri+1),\forall i\in\mathbb{N}\cap[1,n)\ (x_i+r_i\leq x_{i+1}-r_{i+1}),

求

∑i=1nri\sum_{i=1}^nr_i

的最大值。

保证 2≤n≤1062\leq n\leq10^6，x⃗\vec{x} 单调递增且 xn≤109x_n\leq10^9。

这是一个 2n−12n-1 条约束的整数规划问题：

{r1≥0r2≥0⋮rn≥0r1+r2≤x2−x1r2+r3≤x3−x2⋮rn−1+rn≤xn−xn−1.\begin{cases} r_1\geq0\\ r_2\geq0\\ \vdots\\ r_n\geq0\\ r_1+r_2\leq x_2-x_1\\ r_2+r_3\leq x_3-x_2\\ \vdots\\ r_{n-1}+r_n\leq x_n-x{n-1} \end{cases}.

但是除了得出这个名字以外没有甚么用。

我们只考虑后 n−1n-1 条约束，也就是那些线段造成的约束。端点的半径只参与一条，其他的半径都参与两条，所以它们相对来说受到的限制更少、更自由。假如 (r1+r2)(r_1+r_2) 恰好等于 (x2−x1)(x_2-x_1)，那末它们对最终结果的贡献之和就是 (x2−x1)(x_2-x_1)。然而由于 r2r_2 受到 r2+r3≤x3−x2r_2+r_3\leq x_3-x_2 的限制，有可能因为 r2r_2 取不了很长，但 r1r_1 只受这一条限制，所以只需 r1r_1 尽可能长，就能使 (x2−x1)(x_2-x_1) 全部贡献给结果。对 rn−1r_{n-1} 和 rnr_n 也是同理。所以考虑从外向内依次确定半径，尽可能使外侧的点的半径长。

注意讨论偶数个点和奇数个点，它们在最中间稍有不同。

C.

给定一颗有根树 TT，00 为根节点。记 t(v) (v∈V(T))t(v)\ (v\in V(T)) 表示以 vv 为根的子树。初始时，树上每个点有个空篮子。进行 m∈N∗m\in\mathbb{N}^* 次操作，第 i∈N∩[0,m)i\in\mathbb{N}\cap[0,m) 次给定 ai,bi∈V(T)a_i,b_i\in V(T)，对 t(ai)∪t(bi)t(a_i)\cup t(b_i) 的每个点的篮子，放一颗颜色为 ii 的果子。需要对每个 u∈V(T)u\in V(T) 求出，有多少个 v∈V(T)v\in V(T) 满足 u,vu,v 的篮子中有同色的果子。

保证 2≤n≤2×105, m≤1052\leq n\leq 2\times10^5,\ m\leq10^5。

不会。用 std::bitset 写了个比较暴力的做法，拿了 5050 分。

D.

卡池中有 m∈N∗m\in\mathbb{N}^* 张价值为 (ai)i=0m−1∈(N∗)m(a_i)_{i=0}^{m-1}\in(\mathbb{N}^*)^m 的 A 类卡和 nn 张价值为 (bi)i=0n−1∈(N∗)n(b_i)_{i=0}^{n-1}\in(\mathbb{N}^*)^n 的 B 类卡。现在进行不放回随机抽卡，每张卡被抽中的概率正比于其价值。抽到卡池中 A 类卡抽完为止，求模 998244353998244353 意义下抽出的总卡数的期望。

保证 1≤m≤1000, 0≤n≤100, ∀i∈N∩[0,m) (ai≤500), ∀i∈N∩[0,n) (bi≤108)1\leq m\leq1000,\ {\color{red}0}\leq n\leq100,\ \forall i\in\mathbb{N}\cap[0,m)\ (a_i\leq500),\ \forall i\in\mathbb{N}\cap[0,n)\ (b_i\leq10^8)。

不会。写了 n=0n=0 的情况（答案为 mm），得了 2.12.1 分，我不知道怎么得出来的。

E.

实现 Satlike-w 算法的 void flip(int flipvar) 函数，优化其 void local_search(std::vector<int> &init_solution) 和 int pick_var() 函数。

给的傻逼代码下标越界了。傻逼 VS Code 频繁崩溃。调试也调试不了，只能用 gdb 命令行调试，但实在不方便，基本上都是古法调试。

写了 flip，本地测出来 60∼7060\sim70 分（总分 300300）。给 local_search 试了试加跳出局部最优，还没运行完比赛就结束了，幸好结果只有 2727 分，不亏。这次优化题花了几个小时（因为 A,B 都 AC 了而 C,D 感觉确实想不出），感觉时间主要花在读题、读他的狗屎代码和运行上了。

Day 2

AI 题：模型轻量化挑战

看都看不懂，skip。

安全题：分布式广播

我认为这是极好的题。

形式有点类似经典竞赛中的通信题，由相同代码创建的多个实例之间要互相通信，只不过这里直接实现了 TCP 网络协议。

实现以下算法。

Q1. 尽力而为广播（Best-Effort Broadcast）

算法描述

网络中有若干节点，分别编号为 N∩[0,n)\mathbb{N}\cap[0,n)。节点之间通过网络传递消息。

每条消息在与应用层的接口上表现为 (const std::string &msg_id, const json &data) 两个参数，即评测代码唤起 broadcast(msg)broadcast(msg) 事件和接受 deliver(msg)deliver(msg) 时，消息 mm 都由这两个参数提供。

通过网络发送的消息为一个 JSON 对象，要求至少具有以下字段：

  • type: String：信息类型。
  • signature: String：消息签名。发送信息前必须用自己的 node_id 和消息内容或哈希进行签名，以确保信息完整性。接收方也必须调用提供的 verify 接口进行校验。

对同一条消息中的每个节点：

  • 发生 broadcast(msg)broadcast(msg) 事件时：（系统会调用选手实现的broadcast(const std::string &msg_id, const json &data) 唤起选手代码）当前节点应向其他所有节点发送 send(msg)send(msg) 消息（内容可以自行决定，但赛题提供了一些建议帮助理解）。发送信号可以调用赛题提供的 send_to(int target, const json &content) 或 send_to_all(const json &content)。
  • 收到 send(msg)send(msg) 消息时：如果收到的消息 mm 还未提交过，就立刻提交（ deliver(msg)deliver(msg)，选手代码调用提供的 deliver(const std::string &msg_id, const json &data)）。

广播事件的发生不会等待上一次广播的消息全部得到提交，即网络中可能有多条内容不同的消息在同时传播。赛题代码已经做了串行处理，无需加锁。

要求
  • 有效性：诚实的节点的 broadcast(msg)broadcast(msg) 事件必定导致所有诚实的节点提交 msgmsg。
  • 不重复性：每个诚实的节点对同一条消息最多提交一次。
  • 不创造性：呈示的节点不会凭空提交没被广播过的消息。

Q2. 认证回声广播（Authenticated Echo Broadcast）

部分节点表示出任意甚至恶意的现象称为拜占庭故障。认证回声广播可以一定程度上避免拜占庭故障。

算法描述

一共有 n=3f+1n=3f+1 个节点，其中 f∈Nf\in\mathbb{N} 个是恶意节点。

对同一条消息中的每个节点：

  • 维护一个向量 echo_from_nodes=(echo_from_nodei)i=0n−1echo\_from\_nodes=(echo\_from\_node_i)_{i=0}^{n-1}。初始时全为空。

  • broadcast(msg)broadcast(msg) 事件的响应同 Q1.。

  • 收到 send(msg)send(msg) 消息时：向所有节点发送 echo(msg)echo(msg) 消息。

  • 收到来自节点 srcsrc 的 echo(msg)echo(msg) 消息时：若 echo_from_nodesrc=∅echo\_from\_node_{src}=\varnothing，则令 echo_from_nodesrc←msgecho\_from\_node_{src}\gets msg；否则忽略。

  • 如果存在消息 msgmsg 满足

    ∣{src∈N∩[0,n):echo_from_nodesrc=msg}∣≥2f+1,|\{src\in\mathbb{N}\cap[0,n):echo\_from\_node_{src}=msg\}|\geq2f+1,

    则提交 msgmsg。

要求

在 Q1. 的基础上避免重复 echoecho。存在恶意节点时，保证有诚实节点不提交恶意节点发送的消息。

Q3. 拜占庭可靠广播（Byzantine Reliable Broadcast）

算法描述

在 Q2. 的基础上加一层 readyready 检验：对某条消息，某个节点在收到回声数达到 (2f+1)(2f+1) 时，还不提交，而是再向所有节点发送 ready(msg)ready(msg) 信号。同样维护一个初始全为空的向量 ready_from_nodesready\_from\_nodes，接收到 ready(msg)ready(msg) 时，以同样的方式保存。若存在消息 msgmsg 满足

∣{src∈N∩[0,n):ready_from_nodesrc=msg}∣≥f+1,|\{src\in\mathbb{N}\cap[0,n):ready\_from\_node_{src}=msg\}|\geq f+1,

则提交 msgmsg。

要求

忘记了，总之会检查有没有真发 readyready 消息，会不会重复 readyready。

Q4. 优化认证回声广播

利用纠删码（erasure coding）优化认证回声广播。

算法描述

本题不涉及拜占庭故障。

指定参数 mm，利用 encode(m,n,msg)encode(m,n,msg) 可以将 msgmsg 编码为 nn 个块 (si)i=0n−1(s_i)_{i=0}^{n-1}，且满足其中任意 mm 块（设编号分别为 (pi)i=0m−1(p_i)_{i=0}^{m-1}）可以利用 decode((pi,spi)i=0m−1)decode((p_i,s_{p_i})_{i=0}^{m-1}) 解码恢复为 msgmsg。利用纠删码优化广播。提供哈希计算函数 SHA256SHA256 建议用 node_idnode\_id 和数据的哈希值签名而非直接用数据，以提高签名效率，因为反正内容中都要包括块信息，到时候数据会恢复出来的。

题目说这可以让每个节点的空间开销还是甚么降低为原来的 O(1m)O\left(\dfrac{1}{m}\right)。

要求

忘了。

Q5. 优化拜占庭可靠广播

没有算法的描述

利用纠删码优化 Q3.。说是要用 Merkle tree，而且给了 Merkle tree 的描述，但说是要自己实现。

要求

同 Q3.。

大力表扬这道题给的代码。十分优雅！比昨天的优化题不知道好到那里去了。

Q1.~Q4. 照着写就行。Q1.~Q3. 都 AC 了，Q4. 不知道为甚么有 1/101/10 个点没过。Q5. 说要我优化，我管他甚么纠删码优化，直接开个 O3 就交了，也过了 9/109/10 个点。满意离场。