Difference between revisions of "2018 Multi-University, Nowcoder Day 1"
Line 41: | Line 41: | ||
题意:求 $\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\}$ | 题意:求 $\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$ | + | 题解:对原数组排序,枚举 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 == | == Problem H == |
Revision as of 17:10, 19 July 2018
数数题超多。
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 (+)
Problem J
Solved by kblack. 00:21 (+)
题意:求一个前缀+一个后缀出现的不同数字数量。
题解:复制两份,转化成对区间的询问,树状数组模板。