2020-2021:teams:mian:cf_mashup:20200730
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:cf_mashup:20200730 [2020/07/31 11:10] gary |
2020-2021:teams:mian:cf_mashup:20200730 [2020/08/04 19:19] (当前版本) grapelemonade [解法] |
||
|---|---|---|---|
| 行 268: | 行 268: | ||
| ===== B - Destroying Roads (543B) ===== | ===== B - Destroying Roads (543B) ===== | ||
| - | * Solved by **//QwQ//** | + | * Solved by **//Gary//** |
| ==== 题意 ==== | ==== 题意 ==== | ||
| 行 274: | 行 274: | ||
| 连通图问最多删除多少遍可以仍使得$distance(s1,t1)\le l1,distance(s2,t2)\le l2$ | 连通图问最多删除多少遍可以仍使得$distance(s1,t1)\le l1,distance(s2,t2)\le l2$ | ||
| - | $1\le n,m \le 3e5$ | + | $1\le n,m \le 5\times 10^3$ |
| ==== 解法 ==== | ==== 解法 ==== | ||
| 行 340: | 行 340: | ||
| ===== G - Mike and Frog (547A) ===== | ===== G - Mike and Frog (547A) ===== | ||
| - | * Solved by **//QwQ//** | + | * Solved by **//Gary//** & **//Pantw//** |
| ==== 题意 ==== | ==== 题意 ==== | ||
| + | |||
| + | $h1=(h1*x1+y1)%m,h2=(h2*x2+y2)%m$,问多少轮后恰好$h1=a1，h2=a2$; | ||
| + | |||
| + | $1\le m le 2\times 10^6$ | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| + | |||
| + | 找到第一次出现a1，a2的位置，再找出运算出现循环的长度，可以保证这些值如果存在会在m次内找到 | ||
| + | |||
| + | 枚举h1循环了多少次后，判断时候恰好都相同(感觉会在m次循环内重合，不太会证) | ||
| + | |||
| + | 有一个细节是a1或a2有可能在循环节出现前出现，也就是不在循环中，需要特判一下 | ||
| ===== H - Mike and Feet (547B) ===== | ===== H - Mike and Feet (547B) ===== | ||
| - | * Solved by **//QwQ//** | + | * Solved by **//Gary//** |
| ==== 题意 ==== | ==== 题意 ==== | ||
| + | |||
| + | 一个长n的序列a，问长度为i的所有子串串内最小值的最大值，$(1\le i \le n)$ | ||
| + | |||
| + | $1\le n \le 2\times 10^5$ | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| + | |||
| + | 对每个数维护其两侧第一个比它小的数的位置l和r,可以发现长度r-l-1以内的子串的答案都会被$a_i$更新一遍 | ||
| + | 所以只需要两次单调栈维护出l和r，在线段树上更新区间最大值，最后在线段树上查询n次 | ||
| ===== I - Mike and Foam (547C) ===== | ===== I - Mike and Foam (547C) ===== | ||
| 行 507: | 行 524: | ||
| 亦即我们可以仅对与 $m$ 数量级相当（或比其小）的砝码搜索。 | 亦即我们可以仅对与 $m$ 数量级相当（或比其小）的砝码搜索。 | ||
| - | 当 $n=5$ 时，只需搜索到 $5^13=1,220,703,125$ 即可。 | + | 当 $n=5$ 时，只需搜索到 $5^{13}=1,220,703,125$ 即可。 |
| 可见 $n>5$ 时，需要考虑的元素数量不超过 $13$。 | 可见 $n>5$ 时，需要考虑的元素数量不超过 $13$。 | ||
| 行 568: | 行 585: | ||
| Code as follows: | Code as follows: | ||
| - | <hidden><code> | + | <hidden><code python> |
| S = input() | S = input() | ||
| N = len(S) | N = len(S) | ||
| 行 606: | 行 623: | ||
| ===== W - Case of Fugitive (555B) ===== | ===== W - Case of Fugitive (555B) ===== | ||
| - | * Solved by **//QwQ//** | + | * Solved by **//Withinlover//** |
| ==== 题意 ==== | ==== 题意 ==== | ||
| + | |||
| + | 无限长的河流上有 $n$ 块石头，每一块用一个区间 $[l, r]$ 表示，你有 $m$ 块木板，每块的长度固定。 | ||
| + | |||
| + | 你需要依次将着 $m$ 块石头用木板连起来，即1连2，2连3，3连4…… | ||
| + | |||
| + | 询问是否存在摆放木板的方案，如果有，输出方案。 | ||
| ==== 解法 ==== | ==== 解法 ==== | ||
| + | $n$ 块石头之间需要 $n - 1$ 块木板，对木板长度的要求可以转换成 $n - 1$ 条形如 $[l, r]$ 的限制条件。木板的长度视为单点，就转换成了一个经典的贪心。 | ||
| ===== X - Case of Chocolate (555C) ===== | ===== X - Case of Chocolate (555C) ===== | ||
| 行 656: | 行 680: | ||
| 一些关键代码如下。 | 一些关键代码如下。 | ||
| - | <hidden><code> | + | <hidden><code cpp> |
| tuple<Interval, Interval, int> Split (int pos, Direction dir) const { | tuple<Interval, Interval, int> Split (int pos, Direction dir) const { | ||
| if(dir == UP) | if(dir == UP) | ||
2020-2021/teams/mian/cf_mashup/20200730.1596165030.txt.gz · 最后更改: 2020/07/31 11:10 由 gary
