Difference between revisions of "ACM-ICPC 2018 Jiaozuo Online Contest"
(15 intermediate revisions by 3 users not shown) | |||
Line 18: | Line 18: | ||
题解:最小可能不一定,但最大应该就是维护一个最大一个最小就好了。DP。 | 题解:最小可能不一定,但最大应该就是维护一个最大一个最小就好了。DP。 | ||
+ | |||
+ | == Problem D == | ||
+ | |||
+ | Upsolved by ultmaster. | ||
+ | |||
+ | 题意:由 $1$ 到 $n$ 组成的长度为 $m$ 的不严格单增数列,求众数出现次数的期望。 | ||
+ | |||
+ | 题解:单增数列的个数其实就是 $\binom{n+m-1}{n-1}$(插板法)。接下来只要算出众数出现次数不超过 $1,2,3,4,\ldots,m$ 的方案数,就可以算出答案。 | ||
+ | |||
+ | 考虑计算众数出现次数不超过 $k$ 的方案数,那么根据容斥,答案就是 $\sum_{i=0}^n (-1)^i \binom{n}{i} \binom{n+m-1-(k+1)i}{n-1}$(有 $i$ 个数出现次数超过 $k$,然后把 $(k+1)i$ 减掉之后,剩下的就是插板法)。这里的 $i$ 其实只要枚举到 $m/(k+1)$ 就够了(后面的全是 0)。算组合数的时候用递推预处理。 | ||
+ | |||
+ | 最后要求浮点(如果取模的话 kblack 大概现场就过了)。由于数据规模较大,浮点会挂掉,需要高精。 | ||
== Problem E == | == Problem E == | ||
Line 34: | Line 46: | ||
题解:线性规划,单纯形过了。 | 题解:线性规划,单纯形过了。 | ||
+ | |||
+ | ultmaster: 一直不上的原因是 一直认为单纯形会出现解(方案)是分数的问题。后来构造(猜测)了一下好像根本不会出现。然后一下子就过了。 | ||
== Problem G == | == Problem G == | ||
Line 78: | Line 92: | ||
题解:经典的生成函数/容斥(喜欢叫什么就叫什么)就好了。 | 题解:经典的生成函数/容斥(喜欢叫什么就叫什么)就好了。 | ||
+ | |||
+ | ultmaster: kblack 居然被卡读入了。。。 | ||
== Problem L == | == Problem L == | ||
Line 94: | Line 110: | ||
Solved by oxx1108. 0:10:55 (+1) | Solved by oxx1108. 0:10:55 (+1) | ||
+ | |||
+ | 题意:签到 | ||
+ | |||
+ | 题解:签到 | ||
== Problem B == | == Problem B == | ||
− | Solved by | + | Solved by oxx1108 1:34:30 (+2) |
+ | |||
+ | 题意:要求从 $n$ 个数中挑出 $m$ 个数,然后用加减乘除等规定的运算符号依次作用在当前的这个数上,结果尽可能大。 | ||
+ | |||
+ | 题解:DP维护一个最大值一个最小值就好了,一开始写了平方的T了…… | ||
== Problem C == | == Problem C == | ||
Line 110: | Line 134: | ||
Solved by Xiejiadong. 4:23:20 (+1) | Solved by Xiejiadong. 4:23:20 (+1) | ||
+ | |||
+ | 题意:支持树上链的加、乘以及取反运算。 | ||
+ | |||
+ | 题解:取反运算其实就是$\times (2^{64}-1)-1$ | ||
+ | |||
+ | 那么,接下来所有的运算都变成了加和乘 | ||
+ | |||
+ | 树链剖分模板题+线段树维护加乘模板题。 | ||
== Problem F == | == Problem F == | ||
Solved by oxx1108. 4:35:30 (+4) | Solved by oxx1108. 4:35:30 (+4) | ||
+ | |||
+ | 题意:有若干条线段,每条有一个价值,要求选其中的一些,使得同一个点至多被覆盖 k 次,价值和最大是多少。 | ||
+ | |||
+ | 题解:单纯形,被卡常了,最后极限卡过去了…… | ||
+ | 费用流也可以做,训练指南上有类似的建图模型。 | ||
== Problem G == | == Problem G == | ||
Line 125: | Line 162: | ||
== Problem H == | == Problem H == | ||
− | + | Upsolved by dream_cloud. | |
+ | |||
+ | 题意:求一个字符串中出现次数在 L~R 之间的子串个数。 | ||
+ | |||
+ | 题解:建立后缀自动机。求出$cnt[i] = 1 + \sum_{fa[u] = i}cnt[u]$, 对于$cnt[i]$在L~R范围内的答案加上$len[i] - len[fa[i]]$ | ||
+ | |||
+ | 由于某些人读错题目读成了字符串只含A,B字母,wa的不要不要的。 | ||
== Problem I == | == Problem I == | ||
Line 131: | Line 174: | ||
Solved by dreamcloud. 0:11:05 (+) | Solved by dreamcloud. 0:11:05 (+) | ||
− | 题意:给你一个$A\ | + | 题意:给你一个$A\times B \times C$的长方体,问你能否用$1 \times 1 \times 2$的长方体铺满 |
− | 题解:签到题,判$A\ | + | 题解:签到题,判$A \times B \times C$是否是偶数 |
== Problem J == | == Problem J == | ||
Solved by dreamcloud && oxx1108. 3:36:42 (+10) | Solved by dreamcloud && oxx1108. 3:36:42 (+10) | ||
+ | |||
+ | 题意:判一个大数是否为平方数。 | ||
+ | |||
+ | 题解:牛顿迭代优化一下初始值大约在根号附近即可,跑得还飞快。 | ||
+ | |||
+ | 正解:取若干素数判是否都为二次剩余,都为则是平方数。 | ||
== Problem K == | == Problem K == | ||
− | Solved by . 0:53:47 (+1) | + | Solved by dream_cloud. 0:53:47 (+1) |
+ | |||
+ | 题意:有$n$个码头,第$i$码头有$c_i$艘同样的船,每艘船都能运$w_i$吨的货物,问你运$s$吨的货物有多少种不同的对船的安排。 | ||
+ | |||
+ | 题解:dp式子,$dp[i][j]$,只用前$i$个码头的船运$j$吨的货物有多少种不同的方案数,$dp[i][j] = \sum_{k = 0}^{k <= min(c_i,\lfloor \frac{j}{w_i}\rfloor)} dp[i-1][j-k\times w_i]$,虽然乍看上去是三方式子,但是每次枚举$j$的时候,不是直接$++j$,而是$j+=w_i$,用单调栈维护$ dp[i-1][j-k \times w_i], (k <= min(c_i,\lfloor \frac{j}{w_i}\rfloor))$ | ||
== Problem L == | == Problem L == | ||
Line 148: | Line 201: | ||
Xiejiadong:我就是打了个dfs。划水。 | Xiejiadong:我就是打了个dfs。划水。 | ||
+ | |||
+ | oxx:我就是套了个模板。划水。 |
Latest revision as of 13:13, 18 September 2018
ECNU Foreigners
终于一机了。发现可能还是浪费了一点时间。(某些题花的时间太久了)
比赛体验很不好,卡读入,卡内存,卡常,数据范围不写清楚。
Problem A
Solved by zerol. 00:07 (+)
温暖的签到。
Problem B
Solved by ultmaster. 01:03 (+)
题意:要求从 $n$ 个数中挑出 $m$ 个数,然后用加减乘除等规定的运算符号依次作用在当前的这个数上,结果尽可能大。
题解:最小可能不一定,但最大应该就是维护一个最大一个最小就好了。DP。
Problem D
Upsolved by ultmaster.
题意:由 $1$ 到 $n$ 组成的长度为 $m$ 的不严格单增数列,求众数出现次数的期望。
题解:单增数列的个数其实就是 $\binom{n+m-1}{n-1}$(插板法)。接下来只要算出众数出现次数不超过 $1,2,3,4,\ldots,m$ 的方案数,就可以算出答案。
考虑计算众数出现次数不超过 $k$ 的方案数,那么根据容斥,答案就是 $\sum_{i=0}^n (-1)^i \binom{n}{i} \binom{n+m-1-(k+1)i}{n-1}$(有 $i$ 个数出现次数超过 $k$,然后把 $(k+1)i$ 减掉之后,剩下的就是插板法)。这里的 $i$ 其实只要枚举到 $m/(k+1)$ 就够了(后面的全是 0)。算组合数的时候用递推预处理。
最后要求浮点(如果取模的话 kblack 大概现场就过了)。由于数据规模较大,浮点会挂掉,需要高精。
Problem E
Solved by kblack. 02:02 (+1)
题意:树上路径加乘、位取反、求和。
题解:位取反相当于用全 $1$ 减,可以和加乘标记合并,然后就是模板时间了。
Problem F
Solved by zerol. 04:25 (+)
题意:有若干条线段,每条有一个价值,要求选其中的一些,使得同一个点至多被覆盖 k 次,价值和最大是多少。
题解:线性规划,单纯形过了。
ultmaster: 一直不上的原因是 一直认为单纯形会出现解(方案)是分数的问题。后来构造(猜测)了一下好像根本不会出现。然后一下子就过了。
Problem G
Solved by zerol. 00:25 (+)
题意:略(反正是签到)
题解:$2^{n-1}$
Problem H
Solved by zerol. 03:26 (+2)
题意:求一个字符串中出现次数在 L~R 之间的子串个数。
题解:后缀自动机裸题。但是交了 MLE 才发现 2E6 的范围只给了 64MB 内存,若干小时后,发现几百个人过了,于是把数组改小了,assert 一个字符串不超过 2E5 大小,结果就过了。
zerol: 数据范围不写清楚,内存又给得那么吝啬,比赛中还不更正题面。出题人你过来,保证不打死你。
Problem I
Solved by zerol. 00:15 (+)
题意:问 A×B×C 的立方体能否被 1×1×2 完全填充。
题解:当且仅当 A×B×C 为偶数时可以(证明显然)。
Problem J
Solved by ultmaster. 02:27 (+1)
题意:问一个数是否是完全平方数,问 $1+2+\cdots+k$ 是否是完全平方数。
题解:二分,大数。有点卡常,后面一问优化了常数才过。
另解:模质数做二次剩余,但是被队友拦住了。
Problem K
Solved by kblack. 00:46 (+2)
题意:$n$ 种硬币,求凑单方式。
题解:经典的生成函数/容斥(喜欢叫什么就叫什么)就好了。
ultmaster: kblack 居然被卡读入了。。。
Problem L
Solved by kblack. 00:19 (+)
题意:求长度为 $n$,字符集大小 $3$ 的,且不包含特殊模式的串。
题解:上两个字符作为 DP 状态,用矩阵乘法优化。
One,Two,Three,AK
Xiejiadong:全程划水,抱紧大腿。
Problem A
Solved by oxx1108. 0:10:55 (+1)
题意:签到
题解:签到
Problem B
Solved by oxx1108 1:34:30 (+2)
题意:要求从 $n$ 个数中挑出 $m$ 个数,然后用加减乘除等规定的运算符号依次作用在当前的这个数上,结果尽可能大。
题解:DP维护一个最大值一个最小值就好了,一开始写了平方的T了……
Problem C
Unsolved.
Problem D
Unsolved.
Problem E
Solved by Xiejiadong. 4:23:20 (+1)
题意:支持树上链的加、乘以及取反运算。
题解:取反运算其实就是$\times (2^{64}-1)-1$
那么,接下来所有的运算都变成了加和乘
树链剖分模板题+线段树维护加乘模板题。
Problem F
Solved by oxx1108. 4:35:30 (+4)
题意:有若干条线段,每条有一个价值,要求选其中的一些,使得同一个点至多被覆盖 k 次,价值和最大是多少。
题解:单纯形,被卡常了,最后极限卡过去了…… 费用流也可以做,训练指南上有类似的建图模型。
Problem G
Solved by dreamcloud. 0:22:20 (+)
题意:输出$2^{n-1}$
题解:如上
Problem H
Upsolved by dream_cloud.
题意:求一个字符串中出现次数在 L~R 之间的子串个数。
题解:建立后缀自动机。求出$cnt[i] = 1 + \sum_{fa[u] = i}cnt[u]$, 对于$cnt[i]$在L~R范围内的答案加上$len[i] - len[fa[i]]$
由于某些人读错题目读成了字符串只含A,B字母,wa的不要不要的。
Problem I
Solved by dreamcloud. 0:11:05 (+)
题意:给你一个$A\times B \times C$的长方体,问你能否用$1 \times 1 \times 2$的长方体铺满
题解:签到题,判$A \times B \times C$是否是偶数
Problem J
Solved by dreamcloud && oxx1108. 3:36:42 (+10)
题意:判一个大数是否为平方数。
题解:牛顿迭代优化一下初始值大约在根号附近即可,跑得还飞快。
正解:取若干素数判是否都为二次剩余,都为则是平方数。
Problem K
Solved by dream_cloud. 0:53:47 (+1)
题意:有$n$个码头,第$i$码头有$c_i$艘同样的船,每艘船都能运$w_i$吨的货物,问你运$s$吨的货物有多少种不同的对船的安排。
题解:dp式子,$dp[i][j]$,只用前$i$个码头的船运$j$吨的货物有多少种不同的方案数,$dp[i][j] = \sum_{k = 0}^{k <= min(c_i,\lfloor \frac{j}{w_i}\rfloor)} dp[i-1][j-k\times w_i]$,虽然乍看上去是三方式子,但是每次枚举$j$的时候,不是直接$++j$,而是$j+=w_i$,用单调栈维护$ dp[i-1][j-k \times w_i], (k <= min(c_i,\lfloor \frac{j}{w_i}\rfloor))$
Problem L
Solved by oxx1108 && Xiejiadong. 0:31:53 (+)
Xiejiadong:我就是打了个dfs。划水。
oxx:我就是套了个模板。划水。