House Tsumugi

题意 给出一张 \( n \) 个点，\( m \) 条边的无向连通图，图中无自环、重边，初始位置为 \( s \)，每次沿边移动，移动后可以选择是否删除当前这条边。未删除的边可以多次移动，求构造 \( k \) 步移动内未删除边组成树的移动方案。 对于 \( 100 % \) 的数据，\( n \leq 10^3 \)，\( n - 1 \leq m \leq \frac{n(n - 1)}{2} \)，\( k \leq m + n \)。保证有解。 Subtask 1、2 和 4 考虑先钦定一棵生成树，在树上移动并且删除剩下不在生成树上的边。容易发现遍历整棵树时，树上每条边最多经过 \( 2 \) 次，而对于每条多余的边，一去一回删除也最多经过 \( 2 \) 次，总移动步数最多为 \( 2m \) 次，又有 \( m \leq \frac{n(n - 1)}{2} \)，则移动步数严格小于 \( n^2 \)，可通过 Subtask 1、2 和 4。 Subtask 3 \( m = n \)，基环树。判断出需要删掉的边，移动到此位置并删掉即可。移动步数严格小于 \(...

最小生成树，比 CSP-S 2025 T2 简单。（这个是可以说的吗） 题意 给你 \( n \times m \) 个点，\( p \) 种横向边链接每对 \( (e, a_i) \) 和 \( (e, b_i) \)，\( q \) 种纵向边链接每对 \( (x_i, f) \) 和 \( (y_i, f) \)，求最小生成树权值。 暴力是 \( O(nm + np + mq + (p + q) \log (p + q)) \) 的按照题意模拟跑 MST，期望 59 pts。 优化思路 考虑优化。假定存在一条横边（红色），我们将其建全后可以看为将两个纵列合并了起来（如图 1），此时当我们再尝试建纵边（绿色），对于已经合并了的列我们可以只建一条边（如图 2），此时其又会合并两个横排（如图 3）。对此我们发现每建一类边的操作相当于合并两个纵列或横排。 对于每一列和每一排考虑，再次假设建一条横边，所建的边数应该为合并后的排数（即横排数减去已建纵边数），纵边同理，再拿第二组样例举个例子如下（图 4）： 123456782 3 4 1-----2 3 53 2 71 2 61 1...

考虑动态规划。 转移方程 首先读题可以明确出一个性质：当一种技能被选择后，其熟练度在此后不会降为 \( 0 \)，否则一定有更优的取法。 这样就只需要无需考虑熟练度为负的状态。定义 dp 方程 \( f_{i, j, k, h} \) 表示第 \( i \) 天选择了第 \( h \) 个技能，剩余两个技能的未练习天数为 \( j \) 和 \( k \) 时的熟练度。使用 \( j, k = 0 \) 的情况来表示时候未选择这个技能的情况。由此可以得出转移方程如下： \( f_{i+1, nextj, nextk, h} \leftarrow \max(f_{i, j, k, h} + a_{i, h} - nextj - nextk) \) （选择当前技能的情况） \( f_{i+1, nextk, 1, h + 1} \leftarrow \max(f_{i, j, k, h} + a_{i, h+1} - nextk - 1) \) （选择下一种技能的情况） \( f_{i+1, 1, nextj, h+2} \leftarrow \max(f_{i, j, k,...

あのね、空が青いのってどうやって伝えればいいんだろうね 夜の雲が高いのってどうすれば君もわかるんだろう Y’know, how should I tell you that the sky is blue today? What should I do to tell you that the clouds are high in the night sky, so that you would understand too? ——Say It 「言って」 About Yorushika Yorushika(ヨルシカ) is a Japanese rock duo founded in 2017, composed of N-buna, a vocaloid music producer(ボカロP), and Suis, a female vocalist. The name “Yorushika” is taken from a lyric in their song “The Clouds and the Ghost”; “yoru shika mō...

机房同学借“理解题意”之名在模拟赛时打了很久的 2048。在此表示严厉谴责。 考虑怎么存储状态。进行模拟，每次入栈的元素可能为 \(2\) 或 \(4\)。 如果入栈的元素为 \(2\) 的话，可以证明（模拟）能够一直合并。 但如果入栈元素为 \(4\) 的话且栈顶为 \(2\)，\(2\) 和其以前的元素就再也无法继续合并了。但如果栈顶不为 \(2\) 仍可以合并。 因此我们只需要储存 最后一个可合并的单调递减序列。来看两个实例如下： 128 32 8 4 2 此时如果入栈为 \(2\)，最终合并结果为 \(\{ 128, 32, 16 \}\)。 此时如果入栈为 \(4\)，最终合并结果为 \(\{ 128, 32, 8, 4, 2, 4 \}\)，前面的部分已经不可合并，故只需存储 \(\{ 4 \}\)。 128 32 16 8 4 此时如果入栈为 \(2\)，结果为 \(\{ 128, 32, 16, 8, 4, 2 \}\)，依旧可以合并。 此时如果入栈为 \(4\)，最终合并结果为 \(\{ 128, 64...

题意 给你 $n$ 种手套，第 $i$ 种手套有左手套 $l_i$ 只，右手套 $r_i$ 只。找到最小值 $x$ 使得选择任意 $x$ 只手套，总能保证有 $k$ 副不同的手套。 思路 数学题，贪心。 这道题需要使用抽屉原理（鸽巢原理，the pigeonhole principle）进行贪心。 把多于 $n$ 个的物体放到 $n$ 个抽屉里，则至少有一个抽屉里的东西不少于两件。 证明（反证法）：如果每个抽屉至多只能放进一个物体，那么物体的总数至多是 $n$，而不是题设的 $n + k \ (k \geq 1)$，故不可能。 如果每副手套左右各只有一只，答案为 $n + k$。此时的策略是先取每种手套的一只，然后取 $k$ 次另外一只。此时种类数为 $k$。 如果每副手套左右有若干只，考虑最差的情况，先取完每种手套的某一只手，再选取 $k$ 种手套取另外一只手。使用贪心法，先取每种手套较多的一只手，再降序排列取 $k - 1$ 种另一只手，最后再任意取 $1$ 只，此时种类数为 $k$。若 $(l_i, r_i)$ 按照 $\min(l_i, r_i)$...

题目：CF466E 洛谷链接 CF 链接 模拟赛把 T1 跳了来写这个（T3），离线思路很简单，比 T1 思维题好想。 首先，最终状态是若干颗上下级关系的树，所以我们可以将整个问题放在最后建好的树树上考虑。 对于操作一，将 $x$ 与 $y$ 连边即可。 对于操作二，可以用并查集优化复杂度快速找出当前的最高上司。 对于操作三，我们在每次操作二时把上下两个节点 $(u_p, u_d)$ 储存下来，判断节点 $x$ 是否在路径 $i$ 上可以使用最近公共祖先（LCA），若 $\text{LCA}(u_p, x) = u_p \land \text{LCA}(x, u_d) = x$，则 $x$ 在路径上，反之则不在。 需要注意的是，最终状态不一定是一棵树，可能有多棵树，在 LCA 初始化时要处理一下。 倍增写 LCA 的话时间复杂度为 $O(n \log...

题目：CF755D 洛谷 Codeforces 这是一道数据结构大水题。 打模拟赛的时候把这道题放到了 T4，做完 T1 就看这道题有思路就写出来了。 首先考虑如何暴力模拟计算答案，当每链接一条边 $(x, x + k)$ 时，被分割的区域数 $s$ 会增加 $u + 1$，其中 $u$ 是与这条边在正多边形中有交叉的线段数量。而题目保证边数（即点数）$n$ 与 $k$ 互质，说明在每一个点都被连接后才会回到初始节点，共链接 $n$ 条边。我们把每一次的连边存下来，在新的一次连边时判断有多少条边与此时的连边相交。暴力复杂度 $O(n^2)$，期望得分 $0$ 分。 考虑优化。时间复杂度的瓶颈是计算重复的边。想出了一个很奇怪的判断方法，用两颗树状数组储存每条边的左节点和右节点，由于 $k$ 是确认的，所以只用一个节点的位置就可以求出另一个节点。对于左节点与当前边 $(l, r)$ 相交时，统计左节点在区间 $[r - k + 1, r - 1]$ 的线段数量，右节点则统计 $[l + 1, l + k - 1]$。如果节点越界的话特判一下 $\pm n$...

题目：P11838 [USACO25FEB] Printing Sequences B - 洛谷 赛场上很自然想到的是区间 DP。 定义 $dp[l][r]$ 为区间 $[l, r]$ 内最少使用 PRINT 语句的次数。考虑转移，在 $[l, r]$ 内枚举 $m$，若 $[l, r]$ 区间可以由 $[l, m]$ 循环得到，就把 $[l, m]$ 的答案转移给 $[l, r]$。如果不可以就把两个区间 $[l, m]$ 与 $[m+1,r]$ 答案相加。 转移方程如下： $$ dp[l][r]= \begin{cases} dp[l][m]+dp[m+1][r] & \text{任意情况} \ dp[l][p] & [l, r] \text{可由若干个} [l, p] \text{循环得到} \end{cases} $$ 常数不是很大，直接暴力循环判断是否满足即可。时间复杂度 $O(T \times n^4)$。 慢着，似乎哪里有问题？这个复杂度能过？ 对于任意情况的转移是 $O(T \times n^3)$。把视线放到暴力判断那一块，不难发现，在枚举...

等填坑。 二项式定理 定理： $$ (a+b)^{n} = \sum_{i=0}^{n} C_{n}^{i} a^{i} b^{n-i} $$ 当 $b=1$ 时： $$ (a+1)^n = \sum_{i=0}^{n} C_{n}^{i} a^{i} $$ 二项式反演 定理： $$f(i)=\sum_{j=i}^{n}(-1)^{j-i}C_{j}^{i} g(j) $$ $$ g(i)=\sum^{n}{j=i}C^{i}{j} f(j) $$ 证明： $$ \sum_{j=i}^{n} (-1)^{j-i} C_{j}^{i} g(j) = \sum_{j=i}^{n} (-1)^{j-i} C_{j}^{i} \sum^{n}{k=j} C^{j}{k} f(k) = \sum_{k=i}^{n} f(k) \sum_{j=i}^{k} C^j_k \times C^i_j \times (-1)^{(j-i)} $$ 上述等式中求和保证 $i \leq j \leq k \leq n$ 。 令 $\sum_{k=i}^{n}f(k)$ 右侧的系数为 $a$ ，即...