Difference between revisions of "2019 CCPC Online Contest"

From EOJ Wiki
Jump to navigation Jump to search
 
(2 intermediate revisions by one other user not shown)
Line 49: Line 49:
 
用 $path_u$ 代表一条从 $u$ 出发的可能为 $0$ 的路径,用 $Pset(u)$ 代表从 $u$ 出发的所有路径的集合,$next(path_u)$ 代表按长度顺序访问 $Pset(u)$ 中所有的路径时,$path_u$ 的下一条路径。那么首先,对于所有的 $path_u$,它肯定能表示为 $(u,v)$ 或 $(u,v)+route(v)$,其中 $(u,v)$ 代表一条从 $u$ 到 $v$ 的路径。
 
用 $path_u$ 代表一条从 $u$ 出发的可能为 $0$ 的路径,用 $Pset(u)$ 代表从 $u$ 出发的所有路径的集合,$next(path_u)$ 代表按长度顺序访问 $Pset(u)$ 中所有的路径时,$path_u$ 的下一条路径。那么首先,对于所有的 $path_u$,它肯定能表示为 $(u,v)$ 或 $(u,v)+route(v)$,其中 $(u,v)$ 代表一条从 $u$ 到 $v$ 的路径。
  
我们发现,$Pset(u)=\{0\}+\sum_{(u,v)exists}\{path_u|path_u=(u,v)+path_v\}$。要顺序访问 $Pset(u)$ 中的每一条路径,如果能顺序访问 $Pset(v)((u,v)exists)$ 中的路径,就相当于是:
+
我们发现,$Pset(u)=\{0\}+\sum_{(u,v)exists}\{path_u|path_u=(u,v)+path_v\}$。要顺序访问 $Pset(u)$ 中的每一条路径,如果能顺序访问 $Pset(v)((u,v)exists)$ 中的路径,就相当于每次对当前每个 $v((u,v)exists)$ 所枚举到的路径 $path_v$,找到其中 $(u,v)+path_v$ 最小的,取出并将 $path_v$ 替换成 $next(path_v)$(如果 $next(path_v)$ 不存在则只删除 $path_v$)。我们将这种操作称为对 $u$ 的拓展,这种操作可以用优先队列维护。
 +
 
 +
之后,就是找到所有路径中第 $k$ 大的。我们可以先将所有点出发的路径集合设为只有 $0$,每次选择当前所有 $path_u$ 中最小的并拓展 $u$(如果无法拓展,即已经枚举完 $u$ 出发的所有路径,则不进行操作,否则将 $next(path_u)$ 加入集合)。由于要以 $(u,v)+path_v$ 拓展 $path_u$,则 $path_v$ 一定已经被拓展过(因为每条边的长度都 $>0$),所以可以保证在有新路径存在的情况下拓展操作不会中途停止。
 +
 
 +
只要拓展 $max(k)$ 次,就能找到每一个第 $k$ 大的路径。
  
 
== Problem E ==
 
== Problem E ==
  
 
Solved by Weaver_zhu. 01:03:31 (+)
 
Solved by Weaver_zhu. 01:03:31 (+)
 +
 +
题意:$f(n,a,b) = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}gcd(i^a-j^a, i^b-j^b), (a,b) = 1$
 +
 +
题解:$gcd(i^a-j^a,i^b-j^b) = i-j$,然后随便化一下套个杜教筛就过了
  
 
== Problem F ==
 
== Problem F ==

Latest revision as of 01:19, 3 September 2019

Problem A

Solved by Xiejiadong. 00:19:03 (+1)

题意:给出 $A$ 和 $B$ ,求最小的 $C$ 使得 $(A\; xor \; C)\; and \; (B\; xor\; C)$ 。

题解:按位考虑,显然只有在 $A$ 和 $B$ 同时为 $1$ 的时候, $C$ 才需要为 $1$ 。

那么显然,其他情况肯定是 $0$ 最优。

但又需要保证是正整数,所以想办法在 $A$ 和 $B$ 不想等的位置上,让 $C=1$ ,这样可以不影响 $(A\; xor \; C)\; and \; (B\; xor\; C)$ 的结果。

如果不存在这样的位置,那就只能 $C=1$ 让结果变大了。

Problem B

Solved by Xiejiadong && Kilo_5723. 04:27:56 (+2)

题意:要求支持两个操作,给一个数增加 $10^7$ ,询问一个前缀区间,求一个数,满足 $\ge k$ ,且与前缀区间中的每一个数都不同。

题解:每一个数增加了就是增加 $10^7$ ,而 $k\le 10^6$ ,相当于从区间里删掉了这个数。

给出的是一个排列,考虑维护每一个数所在的位置,于是就变成了求后缀区间第一个大于 $r$ 的位置。

线段树维护一下就好了。

Problem C

Solved by Xiejiadong. 03:00:29 (+)

题意:求字符串中和一个子串相同的第 $k$ 次出现的开始位置。

题解:无脑上 SAM ,对于每一个询问,找到询问的子串所在的结点。

方法是,先定位到 endpos $=r$ 的结点,然后在后缀树上二分向上倍增找到子串所在的状态。

于是剩下的问题,就是询问每一个状态的 endpos 集合中第 $k$ 大数,可以在树上启发式合并,用平衡树维护一下第 $k$ 大数就好了。

好像是个 SA 的经典题,直接在 height 上搞就好了。

Problem D

Solved by Kilo_5723. 03:06:41 (+1)

题意:给定一张有向图,每次询问其中第 $k$ 大的路径。

题解:对所有路径排序吼,考虑每次找到比当前路径的下一条路径。

用 $path_u$ 代表一条从 $u$ 出发的可能为 $0$ 的路径,用 $Pset(u)$ 代表从 $u$ 出发的所有路径的集合,$next(path_u)$ 代表按长度顺序访问 $Pset(u)$ 中所有的路径时,$path_u$ 的下一条路径。那么首先,对于所有的 $path_u$,它肯定能表示为 $(u,v)$ 或 $(u,v)+route(v)$,其中 $(u,v)$ 代表一条从 $u$ 到 $v$ 的路径。

我们发现,$Pset(u)=\{0\}+\sum_{(u,v)exists}\{path_u|path_u=(u,v)+path_v\}$。要顺序访问 $Pset(u)$ 中的每一条路径,如果能顺序访问 $Pset(v)((u,v)exists)$ 中的路径,就相当于每次对当前每个 $v((u,v)exists)$ 所枚举到的路径 $path_v$,找到其中 $(u,v)+path_v$ 最小的,取出并将 $path_v$ 替换成 $next(path_v)$(如果 $next(path_v)$ 不存在则只删除 $path_v$)。我们将这种操作称为对 $u$ 的拓展,这种操作可以用优先队列维护。

之后,就是找到所有路径中第 $k$ 大的。我们可以先将所有点出发的路径集合设为只有 $0$,每次选择当前所有 $path_u$ 中最小的并拓展 $u$(如果无法拓展,即已经枚举完 $u$ 出发的所有路径,则不进行操作,否则将 $next(path_u)$ 加入集合)。由于要以 $(u,v)+path_v$ 拓展 $path_u$,则 $path_v$ 一定已经被拓展过(因为每条边的长度都 $>0$),所以可以保证在有新路径存在的情况下拓展操作不会中途停止。

只要拓展 $max(k)$ 次,就能找到每一个第 $k$ 大的路径。

Problem E

Solved by Weaver_zhu. 01:03:31 (+)

题意:$f(n,a,b) = \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}gcd(i^a-j^a, i^b-j^b), (a,b) = 1$

题解:$gcd(i^a-j^a,i^b-j^b) = i-j$,然后随便化一下套个杜教筛就过了

Problem F

Solved by Kilo_5723. 00:17:27 (+1)

题意:给出一副写有数字的牌,每一次把一个数字的牌抽到第一张,求最后的牌的序列。

题解:按照抽牌的倒序拿出还未拿出的牌,再在原来的牌里顺序拿出还未拿出的牌。

Problem G

Solved by Kilo_5723. 00:06:32 (+)

题意:按题意生成一个 $2^k \times 2^k$ 的 $C/P$ 矩阵。

题解:根据题意模拟。

Problem H

Solved by Kilo_5723. 01:16:27 (+)

题意:池塘里有 $n$ 条鱼,抓一条鱼上来要 $k$ 分钟,煮第 $i$ 条鱼需要 $t_i$ 分钟。同一时间只能煮一条鱼,鱼一旦开始煮,直到煮好都不能拿出,求最少花多少时间把所有鱼都钓上来煮好。

题解:首先,我们要花费 $k$ 分钟钓上第一条鱼。接下来,可以证明模型可以转化为把 $n-1$ 次钓鱼时间分配给每一个 $t_i$,而每一条鱼花费的时间是煮的时间与分配的钓鱼时间的较大值。

对于每一个 $t_i$,可以免费分配 $\lfloor \frac{t_i}{k} \rfloor$ 次,这之后分配一次的代价是 $k- t_i\;{\rm mod}\;k$。对每一个 $k- t_i\;{\rm mod}\;k$ 排序,选出其中较小的几个和之前免费分配的凑出 $n-1$。

Problem I

Unsolved.

Problem J

Unsolved.

Problem K

Unsolved.