2024 年日祭（部分）

此处仅展示了部分内容，其余内容将不会整理。

2024.10.18

由于时间久远，所以这一天的这一篇主要记录题目与思路。

• A - 字符串

  题目：给定两个字符串 ， ，且满足： ， ，求 的第 位。

  题解：事实上， 并不影响答案，因为此时长度足够长。对于一个 的“长串”，可以将其分成 四段，发现 与 相同， 与 相同。所以我们就一直从后面往前跳，直到无法跳为止。

• B - 区间

  题目：给定 个区间 ，对于一个 ，若 ，则这个区间会被分割成 与 。尝试防止 个 ，使得分割后的区间数尽量多。求最大区间数。

  题解：先离散化，记录下每个区间的长度与价值（被几个原来的区间覆盖），再对新区间按价值排序去取 。

• C - 构树

  题目：给定一棵有 个结点的树，边有边权。判断是否有一个有 个点的完全图，其边权都是 的不同整数，且给定的树是这个完全图的最小生成树。若有，输出完全图的数量与一种方案；若没有也请报告。

  题解：显而易见，我们将两个树（并查集）合并时，会产生一定数量的“废物”边（也就是连接这两个树的其它的边）。而如果有一条边的边权比生成树中一条边的边权小且这条边没有被选，那么这条边肯定就是一条“废物”边，根据这个结论计算答案。构造时，把“废物”边甩到一个 queue 里面，要用“废物”边时从里面取一个即可。

• D - 字典树

  题目：有 个数字串，对于每一个数字串都会以相同的几率变为它自己的一种排列。将这些数字串放到字典树里，求字典树大小的期望值。

• P9912 [COCI 2023/2024 #2] Zatopljenje

  题解

2024.10.19

• A - Soso的并查集写挂了

  题目：维护并查集的查询与合并。其中用 寻找 的祖先时，操作的代价是 到根的路径上每个点的点权之和。求总代价。

  题解：我们知道每个点到根的距离，而当根更新时，向下传递增加的点权即可。

• B - 迁跃

  题目：给定一棵树，最开始你在 号点（根）。接下来，你可以向下走，每经过一条边就可以获得这条边的权值。你可以花 的代价向上走一条边，但一条边最多被经过两次（下去与上来）。你可以停在任意结点。问你最多获得多少的价值。

  题解：第一遍 dfs 处理出以每个点为根并最终回到根所能获得的最大价值；遍历子树时，若这颗子树的价值大于 ，则选择这棵子树能带来正收益。第二遍 dfs 枚举最终在哪棵子树中停下：若这棵子树带来了正收益，则将答案减去这棵子树的答案并加上向上走所花费的 ，否则加上边权；接下来再继续向下遍历。

• C - 回文回文回IV

  题目：给定数组 ，问有多少种 的排列，使得 的前缀和数组 是回文的。

  题解：可以注意到，若要满足前缀和数组是回文的，需要满足 。我们记 为数 出现的次数。

  • 当 是奇数时，只能存在一对 ，多出来的那一个放在第一位。若不止一组或是相差超过 ，则无法满足上述条件。
  • 当 是偶数时，一定会有一个 放在中间。所以要么所有数出现的次数都是偶数且至少有两个 （一个 放在开头，一个 放在中间），要么有奇数个 且除此之外有且仅有一组 。同理，若不止一组或是相差超过 ，则无法满足上述条件。

  根据上面的条件，可以轻松得判断是否合法，但是如何计算还是一个大问题。

  • 把每一对数看做整体，要在 个位置里面放置 对，方案数： 。
  • 第一位： 。
  • 为偶数时中间的 ： 。
  • 的方案数： 。对于这些零的所有排列，要除以一个对中重复的情况与每个对的排列情况。
  • 对于其它正负数对： 。

• D - 紫藤萝瀑布

  题目：有 朵花，每朵花有每朵花的颜色。有两种询问，第一种是要求两朵花的颜色相同（不独立），第二种是询问要使满足所有条件，要改变至少几朵花的颜色（独立）。

  题解：显而易见，对于要求颜色相同的花可以看成一个连通块，需要修改的次数就是这个连通块的大小减去这个连通块的众数的个数。对于每个连通块维护权值线段树，合并两个块时也合并两个线段树即可。

• [CF1913D] Array Collapse

  设 表示前 位是否保留第 位的总种类数。若不留下，第 位可以被第 位前面的第一个比它小的数删掉，也可以让这个比较小的数与这个数一起被前面的更小的数删掉。若留下第 位，那么考虑在哪些区间中它最小即可。用前缀和与单调栈维护。

  补充[于2025.1.18]：这个题还可以用笛卡尔树来做。

周六ABC打得还好，E做出来了，还是比较简单的。

第一次打CF，打了两场 CF Div.2 ，做得烂得一批。感觉我做不动结论题，猜推不出结论。

2024.10.21

• A - 雷暴

  题目：给定一个 的矩阵，每个位置有颜色。对于每一种颜色的所有格子，你要用一个尽可能小的正方形覆盖它们。输出对于每个颜色，正方形的最小面积。

  题解：处理出 即可。

• B - 神力

  题目：你喜欢在树数轴上随机游走。最初你在原点。给定一个序列，由 与 组成，表示第 个时刻你会向正或负方向移动一格。但是对于每个时刻，你有 的概率不移动。问经过数轴上每个点的概率。

  题解：设 为移动后 次后经过 的概率。对于移动与不移动两种情况分别讨论即可。

• C - 之缘千里

  题目：给定一个长度为 的序列 ，其中 到 各出现两次。尝试构造一个合法的且字典序尽量小的括号序列 ，使得当 时， 。若不存在满足条件的括号序列，请报告。

  题解：显而易见，第 个左括号一定会出现在位置 之前，否则序列不合法。用 set 维护当前哪些位置之前还需要左括号。对于某一个位置与它的 friend ，尽量填左括号，在 set 中验证合法性并删除位置。若最终 set 不为空，则不存在合法的括号序列。

2024.10.22

今天是很水的一天，主要都在写 OIers' Lives 。

• [CF1919D] 01 Tree

  我们可以看成最开始只有一个叶节点（根），再不断把现在已有的叶节点“分裂”成两个新的叶节点。我们把权值看成一个数组，那么分裂操作就是选择一个数 并将 放在它的左侧或右侧。由此可得，这个序列中有且仅有一个 ；而对于权值不为 的位置，要么它左侧第一个比它小的恰好比它小一，要么它右侧第一个比它小的恰好比它小一。否则无解。用单调栈维护即可。

• P9744 消除序列

  可以注意到，最优答案一定满足：对于某一个最终为 的位置 ，将 涂 、将 中是 的位置涂 ，将 中是 的位置涂 。另外，我们将操作一、二放在一起用，可能能以更低的代价将 变为 。维护前后缀并对于每一个最终为

2024.10.23

今天略水。把 OIers' Lives 写完了，开始写 OI Cards Game 了。

今天的考试题是 【MX-S4】梦熊 CSP-S 2024 模拟赛。话说这个出题人上辈子怕不是数据结构 + 二分和DP。

• A - P11217 youyou 的垃圾桶。

  看起来还是一个比较板的数据结构（我写的线段树），但是要写一个线段树二分。最开始写的是一个双 （二分 + 查询），但是感觉可能被卡。后来自己想了一下，直接在线段树上二分，拿现成的区间和用，单 解决。

• B - P11218 youyou 不喜欢夏天。

  对于对应位置的几种情况，贪心地尽量选价值大的即可，最后处理成最大子段和即可。

2024.10.24

今天有一点水。。。该听的题都听了，但是不想写。。。

• A - 高维字符串匹配

  题目： 维字符串匹配。

  题解：暴力。

• B - k 短路

  题目：给定一个有向图，保证两点之间只有一条简单路径且每一个点最多在一个环中。求 短路长度。

  题解：显而易见，最终的路径一定是一条简单路径上挂一些环。算出路径长度与路径上每个点所在环的长度，之后二分或背包即可。