2025 Asia EC Online（1）补题

A. Who Can Win

statement

大模拟。比较细节。
submission

B. Creating Chaos

statement

solution

输出 $1,2,…,n$ 即可。感性理解扩大取值范围一定不会使答案更优。
submission

C. Canvas Painting

statement

一个画布被划分为 $1 \le n \le 10^9$ 个连续段 $1,2,…,n$ ，Cryslea拥有 $1 \le m \le 2 \times 10^5$ 种魔法，每次施法可以在某个区间内选择两个位置 $u$ 和 $v$ $(l \le u \le v \le r)$ ，并用 $v$ 的颜色重新涂色 $u$ 所在的段。每个魔法可以使用一次，且可以按任意顺序使用。施法后，画布上的颜色会发生变化。目标是通过施法，使得画布上不同颜色的数量最少。

Solution

将相邻的两个段缩为一个点，并将施法区间的右端点 $-1$ ，这样就转化成了 $n-1$ 个点和 $m$ 个线段的匹配问题，求最大的匹配数量。

将线段按右端点从小到大排序，尽量选择区间内最靠左的点。可以用 set 维护未被选择的点段，并用 std::set.lower_bound 进行二分查找,这样就避免将高达 1e9 的 $n$ 引入复杂度。

时间复杂度 $\text{O}{(m\log{m})}$ 。

submission

D. Min-Max Tree

statement

给定一棵无根树，每个顶点有一个权值。通过删除一些边，将树划分成若干个连通块，使得所有块的最大点权减最小点权之和最大。求这个最大和。
$1 \le n \le 10^6,1 \le a_i \le 10^9$ 。

Solution

很神秘，树上dp。

设 $dp_{u,0/1/2}$ 为以 $u$ 为根的子树，是 若干个完整的块 / 有一个最小值未和最大值匹配 / 有一个最大值未和最小值匹配。

令 $\text{sum}=\sum\limits_{v}\text{dp}_{v,0}$ ，有如下状态转移：

• 所有子节点是独立的子树，$u$ 孤立：

$$dp_{u,0} \leftarrow \text{sum}$$

• $v$ 子树中已有最小值/最大值，且 $u$ 是与之匹配的最大值/最小值。

$$dp_{u,0} \leftarrow \text{sum} - dp_{v,0} + dp_{v,1} + a_u$$

$$dp_{u,0} \leftarrow \text{sum} - dp_{v,0} + dp_{v,2} - a_u$$

• $v$ 子树中已有最小值/最大值，但 $u$ 不是与之匹配的最大值/最小值。

$$dp_{u,1} \leftarrow \text{sum} - dp_{v,0} + dp_{v,1}$$

$$dp_{u,2} \leftarrow \text{sum} - dp_{v,0} + dp_{v,2}$$

• 所有子树已形成完整的块，$u$ 是最大值/最小值。

$$dp_{u,1} \leftarrow \text{sum} - a_u$$

$$dp_{u,2} \leftarrow \text{sum} + a_u$$

• 两个子树通过 $u$ 形成完整的块，一个包含最大值，一个包含最小值。

$$dp_{u,0} \leftarrow \text{sum} + \max \left(dp_{v,1} - dp_{v,0} \right) + \max \left(dp_{v,2} - dp_{v,0} \right)$$

submission

I. Knapsack Problem

给定一个无向图，有边权为 $w_i$ 。每次经过一条边，将该边的物品放入背包。背包容量为 $V$，若无法容纳当前物品则需换新背包（丢弃旧背包）。对于每个起点 $ s \in [1, n] $，需找到从 $s$ 到指定终点 $T$ 的路径，使得所需的最少背包数。$n,m \le 10^5$ 。

solution

简单的最短路变式。

原题中是多源到一个终点的最短路，可以证明将起点与终点反转，答案不改变。于是问题转化为单源最短路问题。
submission

M. Teleporter

statement

计算 $n$ 个点的树的旅行成本。树之外还有 $m$ 条传送路径，权值为 $0$。使用传送的次数不能超过 $k$ 次。对于每个 $k \in [0,n]$ ， 计算所有城市 $u$ 到城市 $1$ 的最小旅行时间之和。$n \le 5000,m \le 10000$ 。

solution

分层图最短路。但我们不必真的建出 $n$ 层图，由于层之间连边的特性，我们可以直接在当前的 dis 数组上构建下一层分层图：

for(auto e:tl){
    int u=e.first,v=e.second;
    dc[u]=min(dc[u],dis[v]);
    dc[v]=min(dc[v],dis[u]);
}
for(int i=1;i<=n;i++){
    dis[i]=dc[i];
}

下一次 dijkstra 之前，需要把下一层的节点加入堆 Q 并重置松弛状态 vis 。

for(int i=1;i<=n;i++){
    vis[i]=0;
    if(dis[i]!=INF){
        Q.push({dis[i],i});
    }
}

submission