NOI2024前训练-一些有趣的国内外比赛

luoguP9021 [USACO23JAN] Subtree Activation P

你有一棵根为 \(1\) 的树，顶点标记为 \(1 \dots N\)。每个顶点最初都是关闭的。在一次操作中，你可以将一个顶点的状态从关闭状态切换到开启状态，反之亦然。输出一个满足以下两个条件的操作序列的最小可能长度。
\(•\) 定义以顶点 \(r\) 为根的子树由所有满足 \(r\) 位于从 \(1\) 到 \(v\) 的路径上 \((\)包括 \(v)\) , 的顶点 \(v\) 组成。每一个顶点的子树，都有一个时刻，开启状态顶点的集合恰好是该子树中的顶点。
\(•\) 在整个操作序列之后，每个顶点都是关闭的。
对于全部数据，满足 \(2 \le N \le 2 \cdot 10^5\)。

luoguP9984 [USACO23DEC] A Graph Problem P

为了丰富自己的数学知识，Bessie 选修了一门图论课程，她发现她被下面的问题困住了，请帮帮她！
给出一张连通的无向图，包含编号为 \(1\dots N\) 的节点和编号为 \(1\dots M\) 的边，下边的操作将被实施：
\(1.\) 假设集合 \(S=\{v\}\)，变量 \(h=0\)。
\(2.\) 当 \(|S|<N\)，重复执行：
\(•\) 仅有一个顶点在集合 \(S\) 中的边中，找到编号最小的那条，编号记为 \(e\)。
\(•\) 将 \(e\) 不在 \(S\) 中的那个顶点加入集合 \(S\)。
\(•\) 将 \(h\) 修改为 \(10h+e\)。
\(3.\) 返回 \(h\) 对 \(10^9+7\) 取模的值。
输出这个过程的全部返回值。
对于全部数据，满足 \(2 \le N \le 2\cdot 10^5\)，\(N - 1 \le M \le 4 \cdot 10^5\)。

luoguP10197 [USACO24FEB] Minimum Sum of Maximums P

Bessie 有一行 \(N\) 块瓷砖，依次具有丑陋度 \(a_1,a_2,\ldots,a_N\)。其中 \(K\) 块瓷砖卡住了；具体地，索引为 \(x_1,\ldots,x_K\) 的瓷砖。
Bessie 想要最小化瓷砖的总丑陋度，其中总丑陋度定义为每对相邻瓷砖的最大丑陋度之和；即 \(\sum\limits^{N−1}_{i=1}\max(a_i,a_{i+1})\)。她可以任意次执行以下操作：选择两块均未卡住的瓷砖，并交换它们。
求 Bessie 以最优方案执行操作可以达到的最小总丑陋度。
对于全部数据，满足 \(2\le N\le 300\)，\(1\le a_i\le 10^6\)，\(0\le K\le \min(N,6)\)，\(1\le x_1<x_2<\cdots<x_K\le N\)。