300iq Contest 简单题选做

wyr 看了某场 ACM，并惊奇的发现他不会签到题。

比赛链接。

L. Modulo Magic

题意

求 中有多少个不同的数字。

。

题解

不妨假设 ，求出 有多少不同的值，可以发现 的情况放进去没有影响。

考虑对于 的情况， 的值应当等于 。

而这些数字覆盖了所有 的整数。

可以发现此时 的数字，。所以他们对答案没有贡献。

最终答案为 内整数个数，即 。

提交记录。

K. Number Theory

题意

给定质数 ，令 表示最小的 使得存在 满足 。

求 。

。

题解

考虑先预处理出哪些数字能被表示 。

根据数论相关的知识，可以知道恰好有一半的数字能被表示出来。

考虑从小到大枚举 ，然后对于每一个数字依次判断是否存在 。直到所有数字都能被表示出来。

若答案为 ，则复杂度为 。 最大期望在 级别，因此 应该不大，可以通过。

打表可知在 时答案为 ，为 中的最大值。

提交记录。

H. Equal MEX

题意

给定一个长为 的序列 。

现在你需要将整个序列划分为若干段，使得所有段的 值相同。求方案数。

。

题解

设整个序列的 值为 ，最后划分为若干段 的段。

首先可以知道一定有 。

若 ，可以知道整个序列中肯定有值为 的元素，不然 应当 。

而划分出的所有段 都为 ，这说明所有段里都没有值为 的元素。

这矛盾了，说明不可能 。那么一定有 。

那么这就相当于问：有多少方案将整个序列划分为若干段，使得每一段的 是一个数字 。

这就可以 dp 了，令 表示将前 个元素划分为若干段的方案数。

那么如何转移呢，如果 能转移到 ，那么说明 这段区间的 是 。

可以发现满足条件的 是一段前缀，那么直接双指针一下，顺便维护 即可。

具体细节可以看代码，复杂度 。提交记录。

B. MST

题意

给定一个长为 的序列 。

现在有一个 个点的无向完全图，两个点 之间的边权是 。

求最小生成树边权和。

。

题解

有一个 Boruvka 的 做法，但有点无聊。可以去看官解。

首先如果 ，那么答案是 。

然后考虑这么一件事情，设整个序列中最大的数字是 。

若 ，那么可以发现点 最多连了一条边。

为什么呢，假设有两个点 都与点 有连边，那么把 这条边改成 ，总边权显然变小，连成的边仍然是一棵树。

假设全局最小值是 ，那么可以知道点 一定只和点 有连边，那么整体答案就是前 个位置的答案 。

否则有 时，可以发现，对于点 内的所有点，肯定独立连成了一个连通块。证明比较简单，和上面一样调整一下就好了。

考虑这个连通块内部的连边。

对于一个点 ，要么和 连边，要么和 的点里边权最小的点连边，那么直接从后往前 for 一遍求出内部边权。

设 这一段里最小值是 。

考虑连通块外部的连边，可以发现 的点如果要和 的点连边，肯定只能和点 连边。

那么我们令 ， 然后剩下的部分相当于 内点的答案。

提前预处理每一个前缀，最小值和最大值的位置，即可 解决。

提交记录。

G. Circle Convertation

题意

给定两个字符串 。

定义一次操作为选择一个 ，使得 ，然后翻转这两个字符。

构造一组操作次数不超过 的方案，使得最终 ，数据保证有解。

。

题解

没有 300iq，做不出来这题。

令 ，然后分类讨论。

当 为奇数的时候，可以发现一定可以将 变为全 或全 的。

具体操作是这样的，如果 当前不是全 或全 ，考虑将 划分为若干连续段。

容易发现一定能划分为 个偶数段。

而这意味着一定存在一段长度为偶数，那么我们把这个偶数段整个 flip 一下，连续段个数一定减少。

一直做这个操作，直到只剩到一个连续段，此时 一定只存在一种元素。

那么这就将 变成了全 或全 。

注意到操作并不会改变 个数的奇偶性，那么 可以变为全 和可以变为全 一定恰好满足一种。

然后我们把 操作成全 或全 ，然后把操作倒着拼后面就好了。

为偶数时：考虑把 所有偶数位上元素 flip 一下。

这样操作就变成了交换相邻两个元素，冒泡排序一下，然后把 的操作一样倒着拼后面。

提交记录。

F. Good Coloring

题意

现在有一个 个点 条边的无向图。

现在给定了一个这张图的 染色方案，第 个点颜色为 ，满足一条边连接的两个点颜色不同。

现在你需要给出一个 染色方案，满足 ，且存在一条恰好有 个点的路径，使得这个路径上 种颜色都出现了。

。

题解

没有 300iq，做不出来这题。

考虑给所有边定向，方向为从颜色小的点指向颜色大的点，这样整张图就变成了一个 DAG。

最终每一个点的颜色为，其所有前驱中颜色最大的点，颜色 +1。

可以发现，若一个点颜色为 ，则要么 ，要么其存在一个前驱颜色为 。

那么我们找一个颜色最大的点，一直跳前驱，就能找到一个恰好有 个颜色的路径。

提交记录。

C. Tree Circles

题意

现在有一棵 个点的树，第 条边连接了两个点 。

定义一个以点 为直径， 为半径的圆为：只保留编号 的边所形成的连通块内点。

现在有 组询问，每一组询问给出 个点 。

求有多少组直径 ，满足对于 有 。

。

题解

这题找到一个能过的解倒是不难，但是很难找到一个好写的解。

考虑两个圆不相交，其实相当于每一个圆没有覆盖别的关键点。

令 表示最大的 ，使得 不覆盖别的关键点，那么答案为 。

问题在于 怎么算。

考虑建出一个类似于最小生成树的重构树的东西，然后按照中序遍历存下每一个点。

那么两个点 之间编号最大的边，就是他们在这个中序遍历上，中间边权最大的边。

直接把 个点按照序列上的顺序排序，那么 就是点 和左右两侧点询问的 min。

st 表处理 rmq 即可。

时间复杂度 。

提交记录。

A. Zero Sum

题意

现在有一个 的数组，第 行第 列元素是 ，列从 到 编号。

现在你需要选择 个下标 ，满足 。

找出最小的 。

，。

题解

这题这么水怎么过的人这么少。

设 表示确定完了前 个下标，当且所有下标的和是 ，最小的 和是多少。

显然这是一个 的做法，过不了。

考虑将这个数组的所有行随机打乱，那么最优方案期望的 应当是 这个级别左右的。

考虑取 ，在做 dp 的时候只保留 的状态，期望可以通过。

时间复杂度 。 取 就是 的。

提交记录。

D. Angle Beats 2.0

题意

现在有一个 的矩阵，每一个格子上是 .* 两种符号之一。

定义一个图案是一个 * 和两个与这个 * 相邻的 .，并且他们组成了一个 L 形。

问有多少种方案，画出若干不相交的图形，使得每一个 * 都在一个图形中。

。

题解

读懂题意就是简单题啊。

考虑一个 * 一定有一个左右的 . 和一个上下的 . 要和他匹配。

考虑把每一个 . 当成点建一个图，一条边表示其连接的两个点至少有一个需要选择。

那么对于一个 *，就将其上下两个位置的 . 连一条边，如果只有一个位置有 .，那就给这个位置连自环。

显然，建好图之后形成了若干个连通块，考虑分类讨论。

第一种情况是边数>点数，此时显然无法满足要求。

第二种是边数=点数，这种情况是一棵基环树。

此时每一条边需要选择其两个端点之一，显然下面的树只有唯一的选择，环上有两种方案。

值得注意的是，如果这个环是自环，那么只有一个方案。

第三种情况是边数<点数，此时显然 边数=点数-1，那么方案数就是连通块内点的个数。

所有连通块答案乘起来即可。

提交记录。

I. Cactus is Money

题意

给定一个 个点 条边的无向图，保证一条边最多出现在一个简单环种。

第 条边有两个权值 。

现在你需要选出一棵生成树，使得 最小。

。

题解

考虑只有一个环可以选出哪些生成树。

可以发现一个 个点的环对应了 种方案，而最优解只可能出现在这些点构成的下凸壳上。

现在相当于我们要在若干个下凸壳上各选出一个点，使得代价最小。

可以发现这相当于是需要合并下凸壳。

使用闵可夫斯基和，每一次启发式合并最小的两个凸壳即可。

复杂度 。好难写。

提交记录。

E. LIS

题意

给定 个长为 的序列 。

建立一张 个点的有向图，有边 当且仅当 且 。

求这张图的最长路。

。

题解

考虑 dp，用 表示以 结尾的最长路。

考虑使用线段树套李超树进行维护，外层的线段树，区间 维护所有 的直线。

查询 的时候，在外层线段树上进行线段树二分，查询 是否可以为 ，相当于 这个区间的直线里，是否有 这个地方的点值 的。

查询值之后，将点 的线段 插入到 这个位置即可。

时间复杂度 。

提交记录。

其实就剩一个题了但我还没琢磨懂这个题解。