【2022暑假第一期】例题集锦

LCat90 · 2022-07-27 08:20:29 · 个人记录

Day 1

简单计算器

公交换乘

发牌者

A 性格公交车

每排有两个座位，所以只可能是一个内向的先坐下，然后一个外向的再坐下。同时，要考虑座位的宽度。

不难想到定义一个小根堆和一个大根堆，分别表示内向和外向的人可以坐的座位。开始时，所有座位的宽度放到小根堆里，每次内向的人就选顶部的座位。同时，把这个选择的座位放进大根堆里。这个座位就满足已经有一个内向的人。

时间复杂度 O(n\log n)。

C 题海战

看到输入可能有重复，不难想到用 set 去重。每次用所有题目的全集在参加学生中筛选题目。对于比赛，只要学生的题目和目前的题目有重复，那就删掉它；对于训练，如果目前某一题目有人没有做过（即没有重复），就删掉它。

输出从小到大，而 set 内部有序，直接输出剩下的题目。

因为每次要不断删除题目，局部接近 log 级，时间复杂度为 \Omega(nk\log m)（也许并不准确）。

Day 2

D 01背包第k优解

首先，第 k 优解必定由目前的前 k 优解转移过来。注意原先的转移方程：dp_j=\max(dp_j,dp_{j-w_i}+v_i)。不难想到用两个数组记录下 max 里的两个值。在原有的 dp 基础上再加一维，表示第几优解。

利用归并排序的思想，不断用两个数组的值更新前 k 优解。

时间复杂度 O(nvk)。

for(int i = 1;i <= n; ++i)
    for(int v = V;v >= w[i]; --v) {
        int a[Maxn], b[Maxn];
        for(int j = 1;j <= k; ++j)
            a[j] = dp[v - w[i]][j] + c[i], b[j] = dp[v][j];
        int x = 1, y = 1, z = 1;
        a[k + 1] = b[k + 1] = -1; 
        while(z <= k and (a[x] != -1 or b[y] != -1)) {
            if(a[x] > b[y]) dp[v][z] = a[x++];
            else dp[v][z] = b[y++];
            if(dp[v][z] != dp[v][z - 1]) z ++;
        }
    }

Day 3

银河英雄传说

难点是求间隔的战舰。

分别记录每个点到根节点的距离，并查集的长度。

合并两个并查集 x 和 y 时，可以对并查集的长度进行修改。将 y 到 x 的距离更新为原来 x 的长度。

这样就有效处理了根节点，那每个子节点怎么更新呢？

只需要在查找的时候，顺带把子节点加上父节点到根的长度。

团伙

朋友之间不难求，但是敌人呢？

构造虚点，把敌人归在 [n+1,2n] 的编号中，这样敌人的敌人还是会在 [1,n] 中并与这个人属一个集合。统计时，还是只看 [1,n]，忽略敌人。

格子游戏

封圈时，圈中的所有点都是连通的。只要加入这个两点的时候发现它们在同一个并查集中，就是封圈。

注意点的存储，为避免重复，把二维坐标转化成点 x * n + y。

Day 4

造船

单独地维护奇偶不好弄，尝试定下一个标准，去更新其它的。

直接用 1 代表奇数，0 代表偶数。我们固定每个长度大于 1 并查集的叶子节点必须为奇数，每次合并进行判断。（这里让 x 接到 y 上）

• 将 x 变为 1。
• 若 x 已经为 1，则让 y 反转 。（0 变 1，1 变 0）

这样，答案就是每个点的值（0 或 1）相加。

关押罪犯

明辨是非

快餐问题

邮局问题

Day 5

D 教练

ps：搬运的时候简化了很多，一些原因解释的不详细，也删除了部分细节。详见 原帖。

当输入完后，就可以提前算出一部分可以确定的组队方案。

但后面，还剩下一些不确定的人需要互相组合，设当前元素为 i，所在集合的长度为 size_i。讨论 3 种情况：

• + 找另一个 $j$（$size_j=2$）。但因为上面已经处理了 $size_i=2$ 的情况，也就意味着 $size_i=2$ 的人已经确定了。所以现在肯定没有 $size_j=2$ 能与之匹配。 + 再找两个 $j$ ($size_j=1$)。实际上就是把所有的 $1$ 合并。

将所有不确定的人组完队后，我们只需要判断 i 所在的团队长度是否为 3 即可。

时间复杂度 O(n^2\log n)。

Day 6

加法

很好的题，综合考察二分，优先队列和树状数组/差分。

看到最小值的最大值，想到二分答案。

校门外的树

Stars

楼兰图腾

Day 7

E 火神之友

调度CPU

夏季特惠

叶子清除计划

Day 15

A 新的开始

枚举起点，分别构造最小生成树。

把每个点连接的边权 d_i 事先设成 v_i，在求解过程中再更新 d_i。

时间复杂度 O(n^3)。

不难发现：建造一个发电站，就是一个自环，如何处理呢？对于每个点，都有一个自环。而且必须保证至少有一个点要走这个自环。不妨引入一个虚点 0，让每个点的自环都变成 0 到 i 的边。讨论正确性。

最小生成树是图中的一个联通块。因为必须有一个点与 0 连接，所以加上 0 之后，仍是连通的。

时间复杂度 O(n^2)。

C 棋盘上的守卫

易得守卫有 n+m 个，思考怎么维护代价。

观察到 n,m,nm\leq 10^5，正常的二维数组存储肯定会爆，想到图。

把它的横纵坐标分别作为起点和终点，为了避免点重复，将终点加上 n，这样就变成 i 到 j+n 之间存在一条长度为 w_{i,j} 的边。

每一行 i 与某一列 j 相连，维护的是行。某一列 j 与某一行 i 相连且不重复，维护的是列。

这样最小生成树跑出来是 n+m-1 条边，而要使边数为 n+m，相当于要在树上再连一条边，形成基环树。

求最小基环树即可，类似于 kruskal。

时间复杂度 O(nm\log(n+m))。

求最小奇环数的具体方法以及更详细的题解

D Kuglarz

一眼区间dp，对于每个 [i,i]，可以确定 i 是否有球。同样，知道 [i,j] 和 [i + 1,j] 也可以判定。

时间复杂度 O(n^3)。

考虑优化。借助上面的思想，换一种角度：把每个 [i,j] 看作图中的一条边。由于存在有意义的自环 [i,i]，为了不影响结果，只需要看作是 [i-1,i] 即可。因此，存的 [i,j] 也要变成 [i-1,j]。（可以理解为构造虚点）

要知道每个杯子的情况，即要使 [i-1,i] 连通，也就是让整个图连通，又要花费最小，而花费又是边权，问题就转化成了求最小生成树。

时间复杂度 O(n^2)。

Day 16

田忌赛马

JM的西伯利亚特快专递

Day 17

C 徒步旅行

D 情报机器人

Day 18

B 流浪月球

C 统计小猪猪

D 真正的骗子