2018 Multi-University, Nowcoder Day 1

数数题超多。

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。

Problem D

Solved by ultmaster. 00:59 (+)

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

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

Problem E

Solved by ultmaster. 00:23 (+)

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

题解：CCCC 原题。

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 H

Upsolved by zerol. 04:59 (-5)

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 (+)

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

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