Moscow Pre-Finals Workshop 2016 National Taiwan U Selection

From EOJ Wiki
Jump to navigation Jump to search

_

本来可以超 F0RE1GNERS 一题的, Xiejiadong 一番操作以后,差点签到都直接没了。

Problem A

Solved by Xiejiadong. 3:14 (+3)

题意:求一段子串里面子序列包含多少个不连续的 "easy" 。

题解:考虑倍增,用数组 $f[i][j]$ 表示位置 $i$ 之后的 $2^j$ 个 "easy" 的结束位置。

不需要考虑段与段之间连接的时候产生问题,这一点可以通过只考虑 "e" 作为开始的位置来证明。

暴力转移以后,每次贪心的取,不断的截取,获得答案即可。

明明可以暴力求幂的,偏要写快速幂,写了快速幂还写错了,身败名裂。

Problem B

Upsolved by Xiejiadong. (-3)

题意:求最小生成树,边权为两点值得异或。

题解:建立 Trie 。显然产生生成树的方式是子树中的点联通以后,再通过 lca 连接。

因为异或我们可以把长度补成一样的,所以只有最底层的叶子结点是有效的信息。

问题转换成了对于一个既有左孩子,又有右孩子的节点,需要在两边各找一个点,使得他们的异或结果是最小的。

考虑启发式合并,枚举小的一部分中的状态,在另一部分的 Trie 上贪心的跑。

$10^9$ 的数,二进制只开了 $20$ ,最后一个小时意识模糊,啥也没发现,背大锅。

Problem C

Unsolved.

Problem D

Solved by Kilo_5723. 2:41 (+1)

题意:给定一个平面上数个整点,每一次可以在两点间划一条线段,但不能和已有的线段或点发生冲突。双方玩家采取最优策略,先不能连边的玩家输,问采取最优策略的情况下先手赢还是后手赢。

题解:直觉猜出来对于确定的整点集合,无论怎么连边,最后划出的总线段数量都是确定的。

猜出来这个之后,只要用凸包和一些搞法求出任意一种完全连边方案中边的条数,判断奇偶即可。

Problem E

Unsolved.

Problem F

Solved by Weaver_zhu. 0:25 (+)

温暖的签到

Problem G

Unsolved.

Problem H

Upsolved by Weaver_zhu

题意:给出字符串hash,求出冲突情况的字符串对。

题解:$dp[i]$表示值为$i$的不同字符串,然后倍增+卷积运算。fft精度爆炸,可以用拆分fft或者双模数ntt。

Problem I

Solved by Weaver_zhu. 3:34 (+4)

题意:找出区间内满足数位数字单调不减或单调不增的数字

题解:数位dp,注意前导0不要放到记忆化搜索,占用大量机时

Problem J

Solved by Kilo_5723. 0:53 (+4)

题意:$\{a_n\}$,$\{b_n\}$ 都是 $1$ ~ $n$ 的随机全排列,求 $\{c_n\}$,使得 $c_i=\max (a_j+b_k)$ $(j+k)%n=i$。

题解:当 $n$ 很小时,$O(n^2)$ 求出 $\{c_n\}$。

当 $n$ 很大时,选出 $\{a_n\}$,$\{b_n\}$ 中最大的 $2000$ 个数平方枚举 $c_i$。此时,我们可以保证所有 $c_i>2 \times n - 2000$ 的值都已经被枚举出来。

由于数据是随机的,所以一共 $2*10^6$ 对 $a_i+b_j>2 \times n - 2000$ 被随机选出,此时每一个 $c_i$ 没有被选到的概率极低,只要对没有被选到的 $c_i$ $O(n)$ 求出准确值即可。