Difference between revisions of "2018 Multi-University, Nowcoder Day 6"
Jump to navigation
Jump to search
| Line 1: | Line 1: | ||
== Problem A == | == Problem A == | ||
| − | Solved by zerol. 00:34 (+) | + | Solved by zerol. 00:34 (+) |
题意：$2^n$ 个人按完全二叉树进行比赛，每轮用掉 n 个数中的一个，大的获胜，问胜者是谁。 | 题意：$2^n$ 个人按完全二叉树进行比赛，每轮用掉 n 个数中的一个，大的获胜，问胜者是谁。 | ||
Revision as of 08:57, 4 August 2018
Problem A
Solved by zerol. 00:34 (+)
题意：$2^n$ 个人按完全二叉树进行比赛，每轮用掉 n 个数中的一个，大的获胜，问胜者是谁。
题解：模拟。每次胜者用掉比对方最大的更大一些的数。
Problem C
Solved by ultmaster. 01:05 (+2)
Problem D
Solved by zerol. 00:17 (+)
题意：给一个二分图，左边对右边是一对多，右边对左边是一对一，问最大权匹配。
题解：签到。对于右边每一个，选最大的左边进行匹配。
Problem F
Solved by ultmaster. 03:27 (+2)
题意：给一棵有根树，叶子上每个节点都是随机的 0 和 1。每个非根节点上有 16 种真值表，要求选择适当的真值表使得�所有节点的组合得到的 1 节点的值的和最大。
题解：对于每个点，维护两种套餐，一种是 1 的个数最多，一种是 0 的个数最多。然后暴力转移一下就好了。需要高精，上了个 python。没加 Case 再次 WA1。还有递归爆炸（发现根本不用递归）。
Problem G
Solved by zerol. 03:49 (+2)
Problem I
Solved by kblack. 03:18 (+5)
题意：给若干区间，查若干点，点碰到的区间全部删光，求删的情况，强制在线。
题解：借鉴 ST 表的思想，将一个区间分成两个长度为 2 的幂的区间按大小扔 set 顺便以左端点排序，查点的时候遍历长度，就知道哪些区间被碰到了，之后从 set 里面删掉这些区间。文件大小极大，需要输入输出优化。
Problem J
Solved by kblack. 00:29 (+2)