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

From EOJ Wiki
Jump to navigation Jump to search
 
(4 intermediate revisions by 2 users not shown)
Line 22: Line 22:
  
 
补:把矩阵看成无向图。$f(n) = (n-1) f(n - 2) + \sum_{k < n - 2} (n-1)! f(k) / k! / 2$。第一种情况是两个点直接配对,第二种情况是选出某些组成一个环,注意环有正反重复,所以结果要除以 2。
 
补:把矩阵看成无向图。$f(n) = (n-1) f(n - 2) + \sum_{k < n - 2} (n-1)! f(k) / k! / 2$。第一种情况是两个点直接配对,第二种情况是选出某些组成一个环,注意环有正反重复,所以结果要除以 2。
 +
 +
== Problem C ==
 +
 +
Upsolved by ultmaster.
 +
 +
题意:有 $m$ 盏灯一开始都是亮着的,现在有 $n$ 个长度为 $m$ 的 01 串,串上第 $i$ 位为 0 表示选择该串会改变灯 $i$ 的状态。选择某些串组成一个集合 $S$,定义 $f(S)$ 为选择这些串后有哪些灯亮着。求对所有 $2^n$ 个集合的 $\sum f^3(S)$。
 +
 +
题解:经 kblack 提示,这个三次方(显然)是要展开的。我们设 indicator variable $x_i$ 为第 $i$ 盏灯的状态。则 $f^3(S) = \sum_{i=1}^m \sum_{j=1}^m \sum_{k=1}^m x_i x_j x_k$。所求为 $\sum_S f^3(S)$,交换求和号顺序,答案就是对所有的 $i,j,k$ 有多少个子集异或和在 $i,j,k$ 位上恰好都是 0,然后对所有 $i,j,k$ 求和。
 +
 +
朴素做法显然是 $m^3$ 遍历,但是复杂度过高。考虑选取任意三列,组成一个 $n \times 3$ 的矩阵,则可行的方案数与矩阵的 rank 有关:$2^{n-rank(M)}$。注意到行秩 = 列秩,所以先把矩阵转置。然后枚举三元组中的第一行 ($m$),用这一行对所有行进行消元,用一个 counter 统计。同时,rank 一定是 0, 1, 2, 3。下面分别统计:
 +
 +
* rank = 1:在 counter 中选了两个 0(消元后);
 +
* rank = 2:在 counter 中选了一个 0 和一个其他的;或者两个相同的非 0;
 +
* rank = 3:在 counter 中选了两个不同的非 0。
 +
 +
如果这一行本身就是 0,rank 自动减 1。
  
 
== Problem D ==
 
== Problem D ==
Line 37: Line 53:
 
题意:求把一个数列删除恰好 $m$ 元素之后有多少种不同的结果数列。
 
题意:求把一个数列删除恰好 $m$ 元素之后有多少种不同的结果数列。
  
题解:CCCC 原题。
+
题解:CCCC 原题。EOJ 3547。
  
 
ultmaster: 隔壁队免费送的。
 
ultmaster: 隔壁队免费送的。
Line 58: Line 74:
  
 
题解:对原数组排序,枚举 max,对于 max 在 $a_i$ 与 $a_{i-1}+1$ 之间的值,由 $\sum_{i=l}^r (i^k-(i-1)^k)i = \sum_{i=l}^r (i^{k+1}-(i-1)^{k+1}-(i-1)^k) = r^{k+1}-(l-1)^{k+1}-\sum_{i=l}^r (i-1)^k$,这部分的贡献为 $(\prod_{k=1}^{i-1}a_k) (r^{k+1}-(l-1)^{k+1}-\sum_{i=l}^r (i-1)^k)$ (其中 $k=n-i+1, r=a_i,l=a_{i-1}+1$),其中包含一个等幂求和,可以拉格朗日插值或者伯努利数。
 
题解:对原数组排序,枚举 max,对于 max 在 $a_i$ 与 $a_{i-1}+1$ 之间的值,由 $\sum_{i=l}^r (i^k-(i-1)^k)i = \sum_{i=l}^r (i^{k+1}-(i-1)^{k+1}-(i-1)^k) = r^{k+1}-(l-1)^{k+1}-\sum_{i=l}^r (i-1)^k$,这部分的贡献为 $(\prod_{k=1}^{i-1}a_k) (r^{k+1}-(l-1)^{k+1}-\sum_{i=l}^r (i-1)^k)$ (其中 $k=n-i+1, r=a_i,l=a_{i-1}+1$),其中包含一个等幂求和,可以拉格朗日插值或者伯努利数。
 +
 +
== Problem G ==
 +
 +
Upsolved by zerol.
 +
 +
题意:求斯坦纳树的个数。
 +
 +
题解:dp 转移时有两种形态,分别表示分叉和根的延伸。开两个 dp 数组分别表示无限制 (g) 和最后一步必须是根的延伸 (f)。在分叉时 g 强制由若干个 f 组成,也就是需要由 g 和 f 合成,同时为了防止重复计数,规定追加的 f 中必须包含 S 中的最小元素。在松弛时对于 <= 的情况都要更新,而且同时对 f 和 g 更新。
  
 
== Problem H ==
 
== Problem H ==

Latest revision as of 11:35, 30 July 2018

如果要看代码的话,请移步 铁牌选手K 的提交。

数数题超多。

zerol 和 kblack 负责做难题,ultmaster 负责找规律和使用搜索引擎。

Problem A

Solved by ultmaster. 02:39 (+)

题意:往 $n \times m$ 的格子里填 0,1,2,求左边比右边小,上面比下面小的填法数量。

题解:找规律。

Problem B

Solved by ultmaster. 03:43 (+)

题意:见题解中的样例。

题解:OEIS A002137。

补:把矩阵看成无向图。$f(n) = (n-1) f(n - 2) + \sum_{k < n - 2} (n-1)! f(k) / k! / 2$。第一种情况是两个点直接配对,第二种情况是选出某些组成一个环,注意环有正反重复,所以结果要除以 2。

Problem C

Upsolved by ultmaster.

题意:有 $m$ 盏灯一开始都是亮着的,现在有 $n$ 个长度为 $m$ 的 01 串,串上第 $i$ 位为 0 表示选择该串会改变灯 $i$ 的状态。选择某些串组成一个集合 $S$,定义 $f(S)$ 为选择这些串后有哪些灯亮着。求对所有 $2^n$ 个集合的 $\sum f^3(S)$。

题解:经 kblack 提示,这个三次方(显然)是要展开的。我们设 indicator variable $x_i$ 为第 $i$ 盏灯的状态。则 $f^3(S) = \sum_{i=1}^m \sum_{j=1}^m \sum_{k=1}^m x_i x_j x_k$。所求为 $\sum_S f^3(S)$,交换求和号顺序,答案就是对所有的 $i,j,k$ 有多少个子集异或和在 $i,j,k$ 位上恰好都是 0,然后对所有 $i,j,k$ 求和。

朴素做法显然是 $m^3$ 遍历,但是复杂度过高。考虑选取任意三列,组成一个 $n \times 3$ 的矩阵,则可行的方案数与矩阵的 rank 有关:$2^{n-rank(M)}$。注意到行秩 = 列秩,所以先把矩阵转置。然后枚举三元组中的第一行 ($m$),用这一行对所有行进行消元,用一个 counter 统计。同时,rank 一定是 0, 1, 2, 3。下面分别统计:

  • rank = 1:在 counter 中选了两个 0(消元后);
  • rank = 2:在 counter 中选了一个 0 和一个其他的;或者两个相同的非 0;
  • rank = 3:在 counter 中选了两个不同的非 0。

如果这一行本身就是 0,rank 自动减 1。

Problem D

Solved by ultmaster. 00:59 (+)

题意:求把 $G_2$ 删掉某些边后和 $G_1$ 同构的不同的边集的数量。

题解:暴力枚举排列,然后映射,然后把要删掉的边组成位向量扔进集合。由于点数很小,位向量居然用 int 就够了。

Problem E

Solved by ultmaster. 00:23 (+)

题意:求把一个数列删除恰好 $m$ 元素之后有多少种不同的结果数列。

题解:CCCC 原题。EOJ 3547。

ultmaster: 隔壁队免费送的。

先考虑删除至多 $m$ 个元素的情况:记 $f(i,j,k)$ 为 $s[i..n]$ 上一个不删的字符是 $k$,删除至多 $j$ 个元素后,的数量。由于上一个字符是 $k$,考虑题意,我们不允许再删除 $k$,否则就重复了(要删的话一定要删第一个)。所以:

$f(i, j, k) = \begin{cases}

   f(i+1,j,s_i) & ( s_i = k ) \\
   f(i+1,j,s_i) + f(i+1,j-1,k) & ( s_i \ne k )

\end{cases}$

答案为 $f(1,m,0)-f(1,m-1,0)$。

Problem F

Solved by zerol. 00:52 (+)

题意:求 $\sum_{x_1=1}^{a_1}\sum_{x_2=1}^{a_2}\cdots \sum_{x_n=1}^{a_n} \max\{x_1, x_2, \dots, x_n\}$

题解:对原数组排序,枚举 max,对于 max 在 $a_i$ 与 $a_{i-1}+1$ 之间的值,由 $\sum_{i=l}^r (i^k-(i-1)^k)i = \sum_{i=l}^r (i^{k+1}-(i-1)^{k+1}-(i-1)^k) = r^{k+1}-(l-1)^{k+1}-\sum_{i=l}^r (i-1)^k$,这部分的贡献为 $(\prod_{k=1}^{i-1}a_k) (r^{k+1}-(l-1)^{k+1}-\sum_{i=l}^r (i-1)^k)$ (其中 $k=n-i+1, r=a_i,l=a_{i-1}+1$),其中包含一个等幂求和,可以拉格朗日插值或者伯努利数。

Problem G

Upsolved by zerol.

题意:求斯坦纳树的个数。

题解:dp 转移时有两种形态,分别表示分叉和根的延伸。开两个 dp 数组分别表示无限制 (g) 和最后一步必须是根的延伸 (f)。在分叉时 g 强制由若干个 f 组成,也就是需要由 g 和 f 合成,同时为了防止重复计数,规定追加的 f 中必须包含 S 中的最小元素。在松弛时对于 <= 的情况都要更新,而且同时对 f 和 g 更新。

Problem H

Upsolved by zerol. 04:59 (-5)

题意:给一棵带有边权的树,求从每个点出发,边权序列相邻两数之差的平方和的最大值。

题解:树形 dp + 斜率优化。从点 u 出发的路径一定可以看做先向上再向下(确切地说,是 u-down 或 u-up-down)。在树上先向下做一次 dp(向上贡献)处理所有 u-down 的最优值,再向上做一次 dp。对于 u 的所有儿子 v,v 可以选择和其他儿子向下形成一条路径(形如 v-u-v'-down),最后得到 v-up-down 的最优值传给 v 的儿子(这就是 uplink)。这部分就需要斜率优化了(参考 hdu 3507),为了避免删除的情况,将所有儿子按 x 轴排序后正反方向各计算一次,用单调栈维护凸壳。

zerol: 一开始没有理解 kblack 的精妙算法就开始写了(甚至连求什么也没想清楚),而且愚蠢地没有对儿子排序,所以还上了个 cdq 分治凭空多了个 log,以至于后来搞了一通常数优化。又 WA 又 T 之间,发现 bug 满天飞。比赛结束后发现离 AC 只有一步之遥,修 bug 的时候少改了一个地方。

Problem I

Solved by zerol. 01:25 (+)

题目:对于一个只包含 abc 的字符串,求不同构的子串个数。

题解:对于 abc 的所有轮换所得到的 6 个串,求得本质不同的子串个数为 S(这部分可以用各种姿势,推荐一下无脑的广义后缀自动机)。对于包含字符种数分别为 1,2,3 的子串,与之同构的字符串个数分别为 3,6,6。所以对于只包含一种字符的子串需要特判,设原串中连续相同字符最多有 k 个,那么答案就是 (S+3*k)/6。

Problem J

Solved by kblack. 00:21 (+)

题意:求一个前缀+一个后缀出现的不同数字数量。

题解:复制两份,转化成对区间的询问,树状数组模板。