Difference between revisions of "ACM-ICPC 2018 Nanjing Online Contest"
(44 intermediate revisions by 5 users not shown) | |||
Line 1: | Line 1: | ||
= ECNU Foreigners = | = ECNU Foreigners = | ||
+ | |||
+ | 本场贡献最佳:场外选手 zerol。 | ||
+ | |||
+ | ultmaster 和 kblack 两个人组团在机房吃大便。 | ||
+ | |||
+ | 听说计蒜客会吃账号,所以搞了一个仓库。本场代码 [https://github.com/F0RE1GNERS/JisuankeEatsMyCode/tree/master/1555 地址点这里]。 | ||
== Problem A == | == Problem A == | ||
Solved by Mathematica. 00:13 (+) | Solved by Mathematica. 00:13 (+) | ||
+ | |||
+ | <pre> | ||
+ | Simplify[Mod[Sum[i!*i, {i, 1, n - 1}], n]] | ||
+ | </pre> | ||
+ | |||
+ | 输出 | ||
+ | |||
+ | <pre> | ||
+ | Mod[-1 + n!, n] | ||
+ | </pre> | ||
== Problem B == | == Problem B == | ||
− | Solved by ultmaster. 01:04(+) | + | Solved by ultmaster. 01:04 (+) |
+ | |||
+ | 题意:求 $nm$ 的矩阵上有若干个位置禁手,为不禁手的地方能拉出多少个不同的矩阵。 | ||
+ | |||
+ | 题解:只要做过此类问题的集大成者:EOJ 3514 五彩地砖,就会发现这题就是个。。。裸题。从大到小枚举矩阵的开始的列,然后考虑可以放的区域,发现是一个 histogram。就是求 histogram 里可以放的不同的矩阵的数量。从大到小枚举矩阵的开始行,然后用一个单调栈维护就好了。 | ||
== Problem C == | == Problem C == | ||
Solved by ultmaster. 03:24 (+4) | Solved by ultmaster. 03:24 (+4) | ||
+ | |||
+ | 题意:有一种非常类似斗地主的游戏,然后给出一堆牌(牌的顺序也告诉你了),然后告诉你几个人玩,让你求最后结果。 | ||
+ | |||
+ | 题解:按题意模拟即可。有一个 else if 漏写了 else 搞自闭了。 | ||
== Problem D == | == Problem D == | ||
Solved by ultmaster. 04:17 (+2) | Solved by ultmaster. 04:17 (+2) | ||
+ | |||
+ | 题意:干两件事情:1. 把凸多边形缩小 $r$;2. 求缩小后的凸多边形上的三个点使得组成的三角形面积最大。 | ||
+ | |||
+ | 题解:1. 这题做过;2. 枚举两个点,三分找第三个点就好了。 | ||
== Problem E == | == Problem E == | ||
Solved by ultmaster. 00:35 (+) | Solved by ultmaster. 00:35 (+) | ||
+ | |||
+ | 题意:给出一系列物品和物品获得之间的依赖关系,物品获得的价值和物品本身的属性和获得的顺序有关。求最大收益。 | ||
+ | |||
+ | 题解:状压记忆化搜索即可。对于某一个状态,枚举最后一个获得的物品,然后检查是不是其他东西都已经获得,如果是,更新答案。 | ||
== Problem F == | == Problem F == | ||
− | Solved by zerol. | + | Solved by zerol. 03:48 (+5) |
题意:给一棵树,要求支持以下操作: | 题意:给一棵树,要求支持以下操作: | ||
Line 34: | Line 66: | ||
题解:蒙特卡洛可以发现询问就是求 (sz[u]-1)/d[u]*2,其中 sz[u] 是联通块大小,d[u] 是度数。然后就是一个很经典的维护子树大小的 lct 了。 | 题解:蒙特卡洛可以发现询问就是求 (sz[u]-1)/d[u]*2,其中 sz[u] 是联通块大小,d[u] 是度数。然后就是一个很经典的维护子树大小的 lct 了。 | ||
+ | |||
+ | zerol:WA 了那么多次的原因是 lct 在找父亲是没有下传标记,导致看起来是右儿子但其实是左儿子。 | ||
== Problem G == | == Problem G == | ||
− | Solved by kblack. | + | Solved by kblack. 02:58 (+) |
+ | |||
+ | 题意:一排房间装着灯,每月买新的节能灯替换,每次找最前面的能完整替换的房间完整替换,求过程。 | ||
+ | |||
+ | 题解:开个线段树,按灯数量排序,维护最前(原本的)位置,模拟一下就好了。 | ||
== Problem H == | == Problem H == | ||
− | Solved by zerol. | + | Solved by zerol. 04:47 (+3) |
题意:一开始每个集合里有一个数。要求支持操作: | 题意:一开始每个集合里有一个数。要求支持操作: | ||
Line 52: | Line 90: | ||
题解:首先发现询问 3 就是相当于求把所有数字倒过来插入一个 trie 以后某个节点上的和。把一个 trie 上的数字 +1,相当于交换 0/1 然后在左子树(0) 下递归交换。集合合并就是类似于动态开点的线段树的合并。当然这里的数据结构像是介于 trie 和 主席树之间的东西。 | 题解:首先发现询问 3 就是相当于求把所有数字倒过来插入一个 trie 以后某个节点上的和。把一个 trie 上的数字 +1,相当于交换 0/1 然后在左子树(0) 下递归交换。集合合并就是类似于动态开点的线段树的合并。当然这里的数据结构像是介于 trie 和 主席树之间的东西。 | ||
+ | |||
+ | zerol:最后只想着 AK 了,就随便交了。因为空间没开够(用的是持久化数据结构)所以 TLE/RE 了两发。不过能写对还是很幸运的。 | ||
== Problem I == | == Problem I == | ||
− | Solved by zerol. | + | Solved by zerol. 02:26 (+) |
题意:求一个数字串中所有本质不同的回文子串之和。 | 题意:求一个数字串中所有本质不同的回文子串之和。 | ||
Line 63: | Line 103: | ||
== Problem J == | == Problem J == | ||
− | Solved by zerol. | + | Solved by zerol. 00:17 (+) |
题意:求某个积性函数的前缀和。 | 题意:求某个积性函数的前缀和。 | ||
− | 题解:上个板子就好了。(这里我用了 min_25 | + | 题解:上个板子就好了。(这里我用了 min_25 筛,但感觉数据范围有点小。所以其实直接线性筛就好了。) |
+ | |||
+ | == Problem K == | ||
+ | |||
+ | Solved by kblack. 01:53 (+) | ||
+ | |||
+ | 题意:给一个函数生成高精量的数,求异或和不为 $0$ 的子集数。 | ||
+ | |||
+ | 题解:函数循环最大 $2^{12}$,将数列看成 $01$ 向量,组成矩阵 $A$,答案即是 $2^n-2^{(n-r(A))}$,向量长度 12,将循环里(本质不同)的数高斯消元就能方便求到秩了。 | ||
+ | |||
+ | == Problem L == | ||
+ | |||
+ | Solved by ultmaster. 01:26 (+5) | ||
+ | |||
+ | 题意:求至多可以让 $k$ 条边免费的最短路径。 | ||
+ | |||
+ | 题解:建 $n(k+1)$ 个点,然后直接跑最短路。复杂度是 $O(nk \log n)$。<del>是不对的,但是过了。</del> | ||
+ | |||
+ | ultmaster: 听说这题卡了 SPFA,可是 kblack 明明写的是 Dijkstra。kblack 说他军训累了,你就放他过了吧。但是你就是给他 TLE。你考虑过这些吗?没有,你只考虑你自己。 | ||
+ | |||
+ | kblack: 叮咚,你的罚了吗外卖,点个好评谢谢。_(xз」∠)_ | ||
+ | |||
+ | = One,Two,Three,AK = | ||
+ | |||
+ | Xiejiadong:整场比赛的锅都是我的。SPFA被卡,SB题卡了3h。自闭。 | ||
+ | |||
+ | == Problem A == | ||
+ | |||
+ | Solved by oxx1108. 0:04:35(+) | ||
+ | |||
+ | 题意:签到题,猜结论 | ||
+ | |||
+ | 题解:看看样例就知道了 | ||
+ | |||
+ | == Problem B == | ||
+ | |||
+ | Solved by dreamcloud. 1:40:13(+) | ||
+ | 题意:求 nm 的矩阵上有若干个位置禁手,问总共有多少个不包含禁手的子矩阵。 | ||
+ | |||
+ | 题解:首先先对每一个格子求出最多向下多少个。然后枚举以每个格子为左上角有多少个矩阵,从左往右看,依次看每列向下能有多少个矩阵,显然是单调递减的,那么前面格子向下的数量会限制后面的。所以我们只需往后找到第一个比当前向下数量小的格子,那么中间一段都更新为当前一段(不需要真的更新,直接算出值即可),后面则不变。往后找到第一个的方法就是单调队列。 | ||
+ | |||
+ | == Problem C == | ||
+ | |||
+ | Upsolved by oxx1108. 4:59:46(-7) | ||
+ | |||
+ | 题意:模拟一个扑克牌游戏 | ||
+ | |||
+ | 题解:模拟一下即可,$multiset$ 的 $erease$ 用错了导致一直Wa。 | ||
+ | |||
+ | == Problem D == | ||
+ | |||
+ | Solved by oxx1108. 3:23:04(+2) | ||
+ | |||
+ | 题意:干两件事情:1. 把凸多边形缩小 $r$;2. 求缩小后的凸多边形上的三个点使得组成的三角形面积最大。 | ||
+ | |||
+ | 题解:半平面交套个凸包内最大三角形面积(旋转卡壳)模板即可。 | ||
+ | |||
+ | == Problem E == | ||
+ | |||
+ | Solved by Xiejiadong. 3:29:38(+5) | ||
+ | |||
+ | 题意:给出解每道题目之前必须要解决的一些题目,求做多可以获得的分数。 | ||
+ | |||
+ | 题解:一开始觉得是在拓扑图上搞。写了贪心,Wa了;写了dp,Tle了。自闭。 | ||
+ | |||
+ | 然后发现直接状态压缩一下,跑个dp,用宽搜来实现就可以了。 | ||
+ | |||
+ | == Problem F == | ||
+ | |||
+ | Unsolved. | ||
+ | |||
+ | == Problem G == | ||
+ | |||
+ | Solved by dreamcloud. 4:08:09(+1) | ||
+ | |||
+ | 题意:$n$个房间,每个房间装着$k_i$灯,每月买$m$个新的节能灯替换,每次找最前面的能全部替换的房间替换,求过程。 | ||
+ | |||
+ | 题解:用线段树,维护最小值,每次找比小于等于当前有的节能灯数量的第一个位置。 | ||
+ | |||
+ | == Problem H == | ||
+ | |||
+ | Unsolved. | ||
+ | |||
+ | == Problem I == | ||
+ | |||
+ | Solved by Xiejiadong. 2:56:25(+) | ||
+ | |||
+ | 题意:求字符串中所有回文字串的和。 | ||
+ | |||
+ | 题解:回文自动机模板题。加一个处理回文子串大小的东西,最后把本质不同的回文子串全部相加就好了。 | ||
+ | |||
+ | == Problem J == | ||
+ | |||
+ | Solved by dreamcloud. 0:26:57(+) | ||
+ | |||
+ | 题意:签到题,积性函数求个前缀和 | ||
+ | |||
+ | 题解:线性筛搞一下就行 | ||
== Problem K == | == Problem K == | ||
− | + | Upsolved by dreamcloud | |
+ | |||
+ | 题意:含$n$($n \le 10^{10000000}$)个元素的数组,$a_n = f(a_{n-1})\%k$,($k \le 2^{12}$),求异或和不为 0 的子集数。 | ||
+ | |||
+ | 题解:计算出异或和为0的子集数,再通过$2^n$减去即可得到答案。数组中不同元素个数不超过k。将每个数看作二进制,要满足通过取或者不取,使得每一位二进制异或和都是0,这可以通过高斯消元求出自由元个数为r,答案即是 $2^n - 2^{n-r}$。 | ||
== Problem L == | == Problem L == | ||
− | Solved by | + | Solved by oxx1108 && Xiejiadong. 1:36:03(+4) |
+ | |||
+ | 罚时是Xiejiadong贡献的。SPFA被卡了。 | ||
+ | |||
+ | 题意:可以将$k$条边的权值变为0,求从$1$到$n$的最短路径。 | ||
+ | |||
+ | 题解:按照$k$,把每一个点都拆成$k$个点来跑最短路。 | ||
+ | |||
+ | Xiejiadong写了个SPFA被卡了,不知道为什么。听出题人说并没有可以卡SPFA,验题人还用SPFA拆点最短路跑过去了。可能是写的太丑了。oxx1108重写了一遍dij就过了。 |
Latest revision as of 14:46, 9 September 2018
ECNU Foreigners
本场贡献最佳:场外选手 zerol。
ultmaster 和 kblack 两个人组团在机房吃大便。
听说计蒜客会吃账号,所以搞了一个仓库。本场代码 地址点这里。
Problem A
Solved by Mathematica. 00:13 (+)
Simplify[Mod[Sum[i!*i, {i, 1, n - 1}], n]]
输出
Mod[-1 + n!, n]
Problem B
Solved by ultmaster. 01:04 (+)
题意:求 $nm$ 的矩阵上有若干个位置禁手,为不禁手的地方能拉出多少个不同的矩阵。
题解:只要做过此类问题的集大成者:EOJ 3514 五彩地砖,就会发现这题就是个。。。裸题。从大到小枚举矩阵的开始的列,然后考虑可以放的区域,发现是一个 histogram。就是求 histogram 里可以放的不同的矩阵的数量。从大到小枚举矩阵的开始行,然后用一个单调栈维护就好了。
Problem C
Solved by ultmaster. 03:24 (+4)
题意:有一种非常类似斗地主的游戏,然后给出一堆牌(牌的顺序也告诉你了),然后告诉你几个人玩,让你求最后结果。
题解:按题意模拟即可。有一个 else if 漏写了 else 搞自闭了。
Problem D
Solved by ultmaster. 04:17 (+2)
题意:干两件事情:1. 把凸多边形缩小 $r$;2. 求缩小后的凸多边形上的三个点使得组成的三角形面积最大。
题解:1. 这题做过;2. 枚举两个点,三分找第三个点就好了。
Problem E
Solved by ultmaster. 00:35 (+)
题意:给出一系列物品和物品获得之间的依赖关系,物品获得的价值和物品本身的属性和获得的顺序有关。求最大收益。
题解:状压记忆化搜索即可。对于某一个状态,枚举最后一个获得的物品,然后检查是不是其他东西都已经获得,如果是,更新答案。
Problem F
Solved by zerol. 03:48 (+5)
题意:给一棵树,要求支持以下操作:
1. u v 连边
2. 以 u 为根,把 v 和它父亲的边切开
3. 询问以 u 为根,一个生物在 u,以等概率移动到相邻结点,问最后回到 u 的经过边数的期望。
题解:蒙特卡洛可以发现询问就是求 (sz[u]-1)/d[u]*2,其中 sz[u] 是联通块大小,d[u] 是度数。然后就是一个很经典的维护子树大小的 lct 了。
zerol:WA 了那么多次的原因是 lct 在找父亲是没有下传标记,导致看起来是右儿子但其实是左儿子。
Problem G
Solved by kblack. 02:58 (+)
题意:一排房间装着灯,每月买新的节能灯替换,每次找最前面的能完整替换的房间完整替换,求过程。
题解:开个线段树,按灯数量排序,维护最前(原本的)位置,模拟一下就好了。
Problem H
Solved by zerol. 04:47 (+3)
题意:一开始每个集合里有一个数。要求支持操作:
1. 合并两个集合
2. 把一个集合里的数都 +1
3. 询问一个集合里满足 $x \equiv a \pmod {2^k}$ 的 $x$ 的个数。
题解:首先发现询问 3 就是相当于求把所有数字倒过来插入一个 trie 以后某个节点上的和。把一个 trie 上的数字 +1,相当于交换 0/1 然后在左子树(0) 下递归交换。集合合并就是类似于动态开点的线段树的合并。当然这里的数据结构像是介于 trie 和 主席树之间的东西。
zerol:最后只想着 AK 了,就随便交了。因为空间没开够(用的是持久化数据结构)所以 TLE/RE 了两发。不过能写对还是很幸运的。
Problem I
Solved by zerol. 02:26 (+)
题意:求一个数字串中所有本质不同的回文子串之和。
题解:建回文自动机,在转移边上 dfs 统计一下。
Problem J
Solved by zerol. 00:17 (+)
题意:求某个积性函数的前缀和。
题解:上个板子就好了。(这里我用了 min_25 筛,但感觉数据范围有点小。所以其实直接线性筛就好了。)
Problem K
Solved by kblack. 01:53 (+)
题意:给一个函数生成高精量的数,求异或和不为 $0$ 的子集数。
题解:函数循环最大 $2^{12}$,将数列看成 $01$ 向量,组成矩阵 $A$,答案即是 $2^n-2^{(n-r(A))}$,向量长度 12,将循环里(本质不同)的数高斯消元就能方便求到秩了。
Problem L
Solved by ultmaster. 01:26 (+5)
题意:求至多可以让 $k$ 条边免费的最短路径。
题解:建 $n(k+1)$ 个点,然后直接跑最短路。复杂度是 $O(nk \log n)$。是不对的,但是过了。
ultmaster: 听说这题卡了 SPFA,可是 kblack 明明写的是 Dijkstra。kblack 说他军训累了,你就放他过了吧。但是你就是给他 TLE。你考虑过这些吗?没有,你只考虑你自己。
kblack: 叮咚,你的罚了吗外卖,点个好评谢谢。_(xз」∠)_
One,Two,Three,AK
Xiejiadong:整场比赛的锅都是我的。SPFA被卡,SB题卡了3h。自闭。
Problem A
Solved by oxx1108. 0:04:35(+)
题意:签到题,猜结论
题解:看看样例就知道了
Problem B
Solved by dreamcloud. 1:40:13(+) 题意:求 nm 的矩阵上有若干个位置禁手,问总共有多少个不包含禁手的子矩阵。
题解:首先先对每一个格子求出最多向下多少个。然后枚举以每个格子为左上角有多少个矩阵,从左往右看,依次看每列向下能有多少个矩阵,显然是单调递减的,那么前面格子向下的数量会限制后面的。所以我们只需往后找到第一个比当前向下数量小的格子,那么中间一段都更新为当前一段(不需要真的更新,直接算出值即可),后面则不变。往后找到第一个的方法就是单调队列。
Problem C
Upsolved by oxx1108. 4:59:46(-7)
题意:模拟一个扑克牌游戏
题解:模拟一下即可,$multiset$ 的 $erease$ 用错了导致一直Wa。
Problem D
Solved by oxx1108. 3:23:04(+2)
题意:干两件事情:1. 把凸多边形缩小 $r$;2. 求缩小后的凸多边形上的三个点使得组成的三角形面积最大。
题解:半平面交套个凸包内最大三角形面积(旋转卡壳)模板即可。
Problem E
Solved by Xiejiadong. 3:29:38(+5)
题意:给出解每道题目之前必须要解决的一些题目,求做多可以获得的分数。
题解:一开始觉得是在拓扑图上搞。写了贪心,Wa了;写了dp,Tle了。自闭。
然后发现直接状态压缩一下,跑个dp,用宽搜来实现就可以了。
Problem F
Unsolved.
Problem G
Solved by dreamcloud. 4:08:09(+1)
题意:$n$个房间,每个房间装着$k_i$灯,每月买$m$个新的节能灯替换,每次找最前面的能全部替换的房间替换,求过程。
题解:用线段树,维护最小值,每次找比小于等于当前有的节能灯数量的第一个位置。
Problem H
Unsolved.
Problem I
Solved by Xiejiadong. 2:56:25(+)
题意:求字符串中所有回文字串的和。
题解:回文自动机模板题。加一个处理回文子串大小的东西,最后把本质不同的回文子串全部相加就好了。
Problem J
Solved by dreamcloud. 0:26:57(+)
题意:签到题,积性函数求个前缀和
题解:线性筛搞一下就行
Problem K
Upsolved by dreamcloud
题意:含$n$($n \le 10^{10000000}$)个元素的数组,$a_n = f(a_{n-1})\%k$,($k \le 2^{12}$),求异或和不为 0 的子集数。
题解:计算出异或和为0的子集数,再通过$2^n$减去即可得到答案。数组中不同元素个数不超过k。将每个数看作二进制,要满足通过取或者不取,使得每一位二进制异或和都是0,这可以通过高斯消元求出自由元个数为r,答案即是 $2^n - 2^{n-r}$。
Problem L
Solved by oxx1108 && Xiejiadong. 1:36:03(+4)
罚时是Xiejiadong贡献的。SPFA被卡了。
题意:可以将$k$条边的权值变为0,求从$1$到$n$的最短路径。
题解:按照$k$,把每一个点都拆成$k$个点来跑最短路。
Xiejiadong写了个SPFA被卡了,不知道为什么。听出题人说并没有可以卡SPFA,验题人还用SPFA拆点最短路跑过去了。可能是写的太丑了。oxx1108重写了一遍dij就过了。