Difference between revisions of "2018 Multi-University, Nowcoder Day 6"

From EOJ Wiki
Jump to navigation Jump to search
Line 29: Line 29:
 
Upsolved by ultmaster.
 
Upsolved by ultmaster.
  
待补。
+
题意:初始给一个字符串,对于每一个可能的字符都定义一个字符串(长度大于 1),每一秒后,字符串中每一个字符都会替换成那个字符对应的字符串。问最少几秒后模式串会出现在该串内?
 +
 
 +
题解:首先可以观察到至多 10 秒后,一个字符就会变成一个长度超过模式串的字符串。所以讨论下面两种情况:
 +
 
 +
1. 模式串在 10 秒内就出现了。
 +
 
 +
2. 考虑 $ans-t$ ($t \le 10$) 的情况。我们从最后出现的时间往前看几秒,这个模式串那时候一定还是一个字符或者两个相邻字符。
 +
 
 +
所以我们需要 BFS 跑出所有一个字符和相邻的两个字符第一次出现的时间。然后需要快速地知道某个字符 $i$ 经过 $j$ 秒成长出来的字符串,在已经匹配了 $k$ 个字符的前提下,匹配该字符串后会匹配多少个字符。记为 $f(i,j,k)$。注意到该功能与 KMP 上的 DFA 非常接近,只是用这个 $f$ 优化转移。计算的话,对于 $i$ 的展开式 $s_1,s_2,\ldots,s_k$,$f(i,j,k) = f\cdots f(s_3,j-1,f(s_2,j-1,f(s_1,j-1,k)))\cdots )$。注意把终态记为 -1 即时跳出。(因为目标是匹配,不是计数)另外暴力计算 $f$ 是不可行的,因为 10 秒内有的字符可能会变得很长很长。
 +
 
 +
上面的两种情况,一种直接可以用 $f$ 快速地处理好,另外一种在 BFS 之后也可以处理。BFS 的时候要注意 $n=1$ 的情况,如果刚开始只有一个字符,要手动地展开一步,把相邻的字符添加到 "两个字符" 的队列里去。
  
 
== Problem F ==
 
== Problem F ==

Revision as of 02:11, 15 August 2018

Problem A

Solved by zerol. 00:34 (+)

题意:$2^n$ 个人按完全二叉树进行比赛,每轮用掉 n 个数中的一个,大的获胜,问胜者是谁。

题解:模拟。每次胜者用掉比对方最大的更大一些的数。

Problem C

Solved by ultmaster. 01:05 (+2)

题意:$S_n$ 是一个由 $1$ 到 $m$ 的数组成的集合,对于 $i<n$,$S_i \subseteq S_{i+1}$,求所有集合的方案数。

题解:(kblack 想出来的) 先枚举集合的大小,只要计算集合大小上升的位置的方案数。这是 $\binom{n-1}{x-1}$ 如果上升了 $x-1$ 次的话。如果上升了 $x-1$ 次,那么枚举的具体数字的数量是 $P(m,x)$。所以答案是 $\sum_{x=1}^{\min(n,m)} \binom{n-1}{x-1} P(m,x)$。处理边界的时候要小心一点。

ultmaster: Case 没写 WA1。

Problem D

Solved by zerol. 00:17 (+)

题意:给一个二分图,左边对右边是一对多,右边对左边是一对一,问最大权匹配。

题解:签到。对于右边每一个,选最大的左边进行匹配。

Problem E

Upsolved by ultmaster.

题意:初始给一个字符串,对于每一个可能的字符都定义一个字符串(长度大于 1),每一秒后,字符串中每一个字符都会替换成那个字符对应的字符串。问最少几秒后模式串会出现在该串内?

题解:首先可以观察到至多 10 秒后,一个字符就会变成一个长度超过模式串的字符串。所以讨论下面两种情况:

1. 模式串在 10 秒内就出现了。

2. 考虑 $ans-t$ ($t \le 10$) 的情况。我们从最后出现的时间往前看几秒,这个模式串那时候一定还是一个字符或者两个相邻字符。

所以我们需要 BFS 跑出所有一个字符和相邻的两个字符第一次出现的时间。然后需要快速地知道某个字符 $i$ 经过 $j$ 秒成长出来的字符串,在已经匹配了 $k$ 个字符的前提下,匹配该字符串后会匹配多少个字符。记为 $f(i,j,k)$。注意到该功能与 KMP 上的 DFA 非常接近,只是用这个 $f$ 优化转移。计算的话,对于 $i$ 的展开式 $s_1,s_2,\ldots,s_k$,$f(i,j,k) = f\cdots f(s_3,j-1,f(s_2,j-1,f(s_1,j-1,k)))\cdots )$。注意把终态记为 -1 即时跳出。(因为目标是匹配,不是计数)另外暴力计算 $f$ 是不可行的,因为 10 秒内有的字符可能会变得很长很长。

上面的两种情况,一种直接可以用 $f$ 快速地处理好,另外一种在 BFS 之后也可以处理。BFS 的时候要注意 $n=1$ 的情况,如果刚开始只有一个字符,要手动地展开一步,把相邻的字符添加到 "两个字符" 的队列里去。

Problem F

Solved by ultmaster. 03:27 (+2)

题意:给一棵有根树,叶子上每个节点都是随机的 0 和 1。每个非根节点上有 16 种真值表,要求选择适当的真值表使得所有节点的取值的组合得到的 1 节点的值的和最大。

题解:对于每个点,维护两种套餐,一种是 1 的个数最多,一种是 0 的个数最多。然后暴力转移一下就好了。需要高精,上了个 python。没加 Case 再次 WA1。还有递归爆炸(发现根本不用递归)。

Problem G

Solved by zerol. 03:49 (+2)

题意:给一棵树 T,并由此生成图 G,G 两点之间的容量定义为在 T 中的距离。问对于所有的点对在 G 中的最大流的和。

题解:发现 u,v 的最大流就是 min{与 u 相邻的边的容量和,与 v 相邻的边的容量和}。然后处理出每个点到所有点的距离和并排序即可。注意会爆 long long。

Problem I

Solved by kblack. 03:18 (+5)

题意:给若干区间,查若干点,点碰到的区间全部删光,求删的情况,强制在线。

题解:借鉴 ST 表的思想,将一个区间分成两个长度为 2 的幂的区间按大小扔 set 顺便以左端点排序,查点的时候遍历长度,就知道哪些区间被碰到了,之后从 set 里面删掉这些区间。文件大小极大,需要输入输出优化。

Problem J

Solved by kblack. 00:29 (+2)

题意:生成 $10^7$ 的随机数,求 $ \max_{1 \leq i < j \leq n}{lcm(a_i, a_j)}$。

题解:由于是随机数,大概率互质,用 nth_element 找出最大的一些(比如100个),枚举一下就好了。

冰冷的签到。