Difference between revisions of "ACM-ICPC 2018 Jiaozuo Online Contest"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| Line 87: | Line 87: | ||
题解：上两个字符作为 DP 状态，用矩阵乘法优化。 | 题解：上两个字符作为 DP 状态，用矩阵乘法优化。 | ||
| − | = | + | = One,Two,Three,AK = |
| − | + | Xiejiadong：全程划水，抱紧大腿。 | |
| − | |||
| − | |||
== Problem A == | == Problem A == | ||
| − | Solved by | + | Solved by oxx1108. 0:10:55 (+1) |
| − | |||
| − | |||
== Problem B == | == Problem B == | ||
| − | Solved by | + | Solved by . 1:34:30 (+2) |
| − | + | == Problem C == | |
| − | + | Unsolved. | |
| − | == Problem | + | == Problem D == |
| − | + | Unsolved. | |
| − | + | == Problem E == | |
| − | + | Solved by Xiejiadong. 4:23:20 (+1) | |
== Problem F == | == Problem F == | ||
| − | Solved by | + | Solved by oxx1108. 4:35:30 (+4) |
| − | |||
| − | |||
| − | |||
| − | |||
== Problem G == | == Problem G == | ||
| − | Solved by | + | Solved by dreamcloud. 0:22:20 (+) |
| − | |||
| − | |||
| − | |||
| − | |||
== Problem H == | == Problem H == | ||
| − | + | Unsolved. | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Problem I == | == Problem I == | ||
| − | Solved by | + | Solved by dreamcloud. 0:11:05 (+) |
| − | |||
| − | |||
| − | |||
| − | |||
== Problem J == | == Problem J == | ||
| − | Solved by | + | Solved by dreamcloud && oxx1108. 3:36:42 (+10) |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
== Problem K == | == Problem K == | ||
| − | Solved by | + | Solved by . 0:53:47 (+1) |
| − | |||
| − | |||
| − | |||
| − | |||
== Problem L == | == Problem L == | ||
| − | Solved by | + | Solved by oxx1108 && Xiejiadong. 0:31:53 (+) |
| − | |||
| − | |||
| − | + | Xiejiadong：我就是打了个dfs。划水。 | |
Revision as of 14:18, 15 September 2018
ECNU Foreigners
终于一机了。发现可能还是浪费了一点时间。（某些题花的时间太久了）
比赛体验很不好，卡读入，卡内存，卡常，数据范围不写清楚。
Problem A
Solved by zerol. 00:07 (+)
温暖的签到。
Problem B
Solved by ultmaster. 01:03 (+)
题意：要求从 $n$ 个数中挑出 $m$ 个数，然后用加减乘除等规定的运算符号依次作用在当前的这个数上，结果尽可能大。
题解：最小可能不一定，但最大应该就是维护一个最大一个最小就好了。DP。
Problem E
Solved by kblack. 02:02 (+1)
题意：树上路径加乘、位取反、求和。
题解：位取反相当于用全 $1$ 减，可以和加乘标记合并，然后就是模板时间了。
Problem F
Solved by zerol. 04:25 (+)
题意：有若干条线段，每条有一个价值，要求选其中的一些，使得同一个点至多被覆盖 k 次，价值和最大是多少。
题解：线性规划，单纯形过了。
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$ 种硬币，求凑单方式。
题解：经典的生成函数/容斥（喜欢叫什么就叫什么）就好了。
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 . 1:34:30 (+2)
Problem C
Unsolved.
Problem D
Unsolved.
Problem E
Solved by Xiejiadong. 4:23:20 (+1)
Problem F
Solved by oxx1108. 4:35:30 (+4)
Problem G
Solved by dreamcloud. 0:22:20 (+)
Problem H
Unsolved.
Problem I
Solved by dreamcloud. 0:11:05 (+)
Problem J
Solved by dreamcloud && oxx1108. 3:36:42 (+10)
Problem K
Solved by . 0:53:47 (+1)
Problem L
Solved by oxx1108 && Xiejiadong. 0:31:53 (+)
Xiejiadong：我就是打了个dfs。划水。