2020-2021:teams:i_dont_know_png:multi2020-nowcoder-3
| 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-3 [2020/07/18 21:41] nikkukun 创建题解 |
2020-2021:teams:i_dont_know_png:multi2020-nowcoder-3 [2020/08/07 09:55] (当前版本) potassium G |
||
|---|---|---|---|
| 行 25: | 行 25: | ||
| 显然有鱼时一定抓鱼，于是变成决策仅有蛤的时候是抓蛤还是抓鱼。考虑每个仅有蛤的位置贪心与其之后的空池塘匹配，剩余的仅有蛤的位置贪心匹配即可。 | 显然有鱼时一定抓鱼，于是变成决策仅有蛤的时候是抓蛤还是抓鱼。考虑每个仅有蛤的位置贪心与其之后的空池塘匹配，剩余的仅有蛤的位置贪心匹配即可。 | ||
| + | ===== B - Classical String Problem ===== | ||
| + | Solved by qxforever & nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一个长度 $n$ 的字符串，$q$ 次操作 | ||
| + | * 将最左边 $x$ 个字符移到最右边或将最右边的字符移到最左边 | ||
| + | * 询问下标 $x$ 对应的字符 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 第一种操作相当于移动字符串起始位置的下标。维护这个下标即可。 | ||
| + | |||
| + | ===== C - Operation Love ===== | ||
| + | |||
| + | Solved by qxforever. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给定一个多边形，表示右手的形状。有 $t$ 组询问，每组询问给 $20$ 个点，判断这些点形成的是右手还是左手。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 比赛时没细想，直接当成判断两个多边形是否全等做了。枚举起点，依次判断角度及边长，$O(n^2)$ 。可以 hash + kmp 做到 $O(n)$ 。 | ||
| + | |||
| + | 其实因为给定的一定是左手或者右手，只需要判断最长边的下一条边的长度。 | ||
| + | |||
| + | |||
| + | ===== D - Points Construction Problem ===== | ||
| + | |||
| + | Solved by qxforever. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 在二维平面上选 $n$ 个整点染为黑色，其他整点为白色。问是否存在一种方案使得恰好有 $m$ 对黑白点对的曼哈顿距离为 $1$ 。$n\le 50$ | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | 考虑按矩形填充黑点。设 $f_{i,j}$ 表示 $i$ 个黑点，围成底边长为 $j$ 的矩形的点对数量，这个比较容易计算。 | ||
| + | 再设 $dp_{i,j}$ 表示 $i$ 个黑点，形成 $j$ 对点对是否可行。由 $f$ 进行 dp 的转移，类似背包的过程。时间复杂度 $O(n^4)$ 。 | ||
| 行 46: | 行 85: | ||
| ==== 解题思路 ==== | ==== 解题思路 ==== | ||
| - | 【留给 qxforever 的部分】 | + | 显然最小是 $1 \sim 2,\ 2 \sim 3,\ \ldots,\ n-1 \sim n$ 这样的匹配。手玩之后发现第二小的匹配可以分成很多段长度为 4 或长度为 6 的段，段内匹配为 $1 \sim 3,\ 2 \sim 4$ 和 $1 \sim 3,\ 2 \sim 5,\ 3 \sim 6$，DP 即可。 |
| 行 76: | 行 115: | ||
| 特殊地，如果 $b = p^k$ 是一个质数的幂，则可以取 $d = p,\ f = p^{k-1}$，只不过此时需要特判一下 $p \mid a$ 是否成立，其他地方同上。最后再判一下 $b = 1$ 时无解即可。 | 特殊地，如果 $b = p^k$ 是一个质数的幂，则可以取 $d = p,\ f = p^{k-1}$，只不过此时需要特判一下 $p \mid a$ 是否成立，其他地方同上。最后再判一下 $b = 1$ 时无解即可。 | ||
| + | |||
| + | |||
| + | ===== G - Operating on a Graph ===== | ||
| + | |||
| + | Solved by Potassium & nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | 给一棵树， $q$ 次操作，每次将选定点所在集合连接的所有点合并成一个集合，求最终每个点所属集合。$1\le n,m,q\le 8e5$。 | ||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 暴力模拟，启发式合并邻接表即可。 | ||
| + | |||
| + | 要学会集合交换函数：s1.swap(s2) 。 | ||
| + | |||
| + | |||
| + | ===== H - Sort the Strings Revision ===== | ||
| + | |||
| + | Upsolved by nikkukun. | ||
| + | |||
| + | ==== 题目描述 ==== | ||
| + | |||
| + | **为了方便说明，下标使用和原题有所不同。** | ||
| + | |||
| + | 有一个长度为 $n \leq 2 \times 10^6$ 的串 $s_0 = \mathtt{"01234567890123.."}$。现在按照如下方法构造 $s_1, s_2, \ldots, s_n$： | ||
| + | |||
| + | - 题目给定一个 $1 \sim n$ 的排列 $p_1, p_2, \ldots, p_n$，和一个范围在 $[0, 9]$ 的数组 $d$； | ||
| + | - 对 $i = 1, 2, \ldots, n$，将 $s_{i-1}$ 的第 $p_i$ 个位置修改为 $d_i$，获得 $s_i$。 | ||
| + | |||
| + | 最后对 $n + 1$ 个二元组 $(s_i, i)$ 升序排序，给出在此结果下每个 $i$ 的名次。你需要给出一个 $O(n)$ 的算法。 | ||
| + | |||
| + | |||
| + | |||
| + | |||
| + | ==== 解题思路 ==== | ||
| + | |||
| + | 先假设第 $k$ 次操作修改了第一个值（即 $p_k = 1$），且修改后的值 $d_i$ 与原来的值不同，则当值被往大改时，$[1, k-1]$ 的排名一定永远小于 $[k, n]$；当值被往小改时，$[1, k-1]$ 的结果永远大于 $[k, n]$。这样问题就可以递归下去：找到区间中 $p_i$ 最小的位置，若右边的区间较大，则给右边区间的排名整体加一个偏移量，接着递归两个子区间。整体加偏移量的操作用前缀和差分就能实现，而递归找最小值的操作正是笛卡尔树做的事。 | ||
| + | |||
| + | 有个 tricky 的技巧：若某次修改前后相等，则可以令 $p_i = n + i$，这样就可以将本次操作放到所有使 $s$ 改变的操作之后，得到正确答案。 | ||
| + | |||
2020-2021/teams/i_dont_know_png/multi2020-nowcoder-3.1595079700.txt.gz · 最后更改: 2020/07/18 21:41 由 nikkukun
