2018.9 ECNU ICPC/CCPC Trial Round #1&2 题解

zerol edited 6 年，3 月前

Average [Very Easy]

Provided by ultmaster. JAP First Round 2018 Problem A

模拟。

Boxed Lunch [Medium Easy]

Provided by ultmaster. JAP First Round 2017 Problem D
状压 DP

• 题意可以转化成寻找最大的子集使得子集异或和为 0。
• 当 $m$ 比较小的时候，比如不超过 22，可以用 dp[i][j] 表示前 $i$ 个数，可以异或得到 $j$，最多用多少个数。
• 当 $n$ 比较小的时候，比如不超过 22，可以直接暴搜每一种子集方案。
• $m$ 和 $n$ 不可能同时超过 22。

Cut Tree [Medium]

Provided by zerol. HackerRank
树形dp

• 树形 dp
• f[u][k] 表示结点 u 为根的子树 T 中以 u 为根的 T’ 个数，满足 T 与 T - T’ 之间至多有 k 条边相连。
• 最后枚举 T’ 的 LCA，如果不是根的话要额外多一条连向 LCA 的父亲。

DP Killer [Medium]

Provided by ultmaster. JAP Summer Camp 2017 Problem E
DP

• g[x1][y1][x2][y2] 表示 $(x_1,y_1)$ 到 $(x_2,y_2)$ 只走乘法的最大取值。
• f[x][y] 表示 $(1,1)$ 到 $(x,y)$ 走加法和乘法的最大取值。考虑怎么求 f[x][y]，只要 枚举 $(x,y)$ 左上区域内的一个点 $(i,j)$，在这个地方做最后一次加法，那么只要用 g[i+1][j][x][y] 和 g[i][j+1][x][y] 更新 f[x][y] 就好了。

Endless BFS [Medium]

Provided by ultmaster. JAP Summer Camp 2017 Problem F
Graph

• 观察一下大概可以发现二分图是布星的。
• 一个点如果现在被选中了，那么 $2t$ 秒后肯定是被选中的。
• 所以按照到达时间的奇偶性，将一个点拆成奇数时间的点和偶数时间的点，然后跑正常的 BFS 即可。

Find Palindromic Subsets [Medium]

Provided by zerol. HackerRank
线段树，数学

• 先搞棵线段树支持题目中的修改操作，以及查询区间内每种字母的个数。
• 集合中的元素能构成回文串的条件是至多有一个字符出现次数为奇数。

Gnomes [Easy]

Provided by ultmaster. NAIPC 2018 D
排序

把给出的那些数，和剩下的数，归并即可。

Here Comes A Math Problem [Medium]

Provided by zerol. HackerRank
容斥，数论

解法一：

• 问题相当于求满足 $2\le p \le q \le n,pq \le n$ 且 $(p,q)=1$ 的 $(p,q)$ 对数。
• 考虑枚举 $gcd(p,q)$，显然不超过 $\sqrt n$。
• 设 $f(n)=\sum_{p=1}^n \lfloor \frac{n}{p} \rfloor$，那么答案就是 $\sum_{g=1}^{\lfloor \sqrt n\rfloor} \mu(g) f(n)$，由于没考虑 $2\le p$ 的条件，最后答案减去 $n$。

解法二：

• 设 $g(n)=2(f(n)+1)$，$g(n)$ 也就是忽略 $2\le p \le q \le n$ 这个条件的 $f(n)$。
• 发现 $g(n)$ 是一个积性函数，且 $g(p^c)=2$，用亚线性筛可求积性函数前缀和。

zerol: 发现没人用反演，都是容斥，谁能写个容斥题解补上。

Intersections [Easy]

Provided by ultmaster.
Graph

拎住网格的一个角，然后逐一考虑每个点，由于每个点都已经有旁边的点固定的，所以每次要选的点度数是一个定值，且相邻点中一定有某个点。

Jim and the Skyscrapers [Easy]

Provided by zerol. HackerRank
单调栈

• 扫一遍，用单调栈维护一下比当前元素小的元素及其个数。

KBlack Playing Cards [Easy]

Provided by kblack.
贪心构造

• 可以发现卡牌的作用等价于，若 $x<a_i$ 则 $ ++ x$，小的卡牌容易无效化，而大的则不容易。
• 贪心地从大到小使用卡牌，同时降低目标 $k$，当某次卡牌无法使用或使用后会使 $k < 0$，那么就不存在方案。否则将其他卡牌放在最顶上就可以了

Lena Sort [Medium]

Provided by zerol. HackerRank
构造，智商

解法一：

• 计算出对于一定长度的数列的比较次数的上限和下限
• 然后进行试探性安排，如果成功保证接下来的解依旧存在，那么递归求解。

解法二：

• 考虑递归排序的中基准元形成的二叉树，那么总比较次数就是二叉树结点的深度和。
• 具体构造方法是逐步调整法。如果深度为 x 的那一层没有满，就可以把一个深度为 y 叶节点的深度变为 x，深度和减少了 y-x。先把树造成一条链，然后从末端进行调整。

Memory Penalty [Easy]

Provided by ultmaster.

$\sum_{i=l}^r i = -\frac{1}{2} (-1 + l - r) (l + r)$。尝试每个因数解方程即可。

Nale Sort [Medium]

Provided by ultmaster.
笛卡尔树

• 考虑由这个 Nale Sort 生成的二叉树，答案就是二叉树所有结点的深度和。
• 剩下的就是由构造笛卡尔树了，可以线性构造。（出题人很良心，有 $\log$ 也能过。）

Oxx Playing Pokemon Go [Medium Easy]

Provided by kblack. coci r7 t3
dp

• dp[u][v][t] 状态表示当前在 u，且 u 与 v 之间的地方已经走过了，当前的时间是 t，值表示能获得的最大收益。
• 对于 $u<v$，可能的转移是 $ (u, v) \Rightarrow (u - 1, v)$ 和 $(u, v) \Rightarrow (v + 1, u)$。
• 按 t 从小到大枚举转移即可。

zerol: 由于 COCI 数据较弱，导致无记忆化回溯（暴力）过了。

Prefix Free Code [Medium]

Provided by kblack. naipc2018 e
Trie，BIT

• 题目中保证没有一个串是另一个串的前缀，那么最后的组合串可以被唯一的分解。
• 对所有初始串建 trie，把组合串在初始串上跑可以得到分解结果。
• 对所有初始串排序，可以在 trie 上 dfs 完成（直接排序也不会超时）。
• 把组合串分解结果用初始串的字典序大小表示，那么问题转化成了这个表示是 1~n 的所有长度为 k 的排列中第几个，用类似康托展开的方法可以求出。

Query on Tree [Medium Hard]

Provided by zerol. HackerRank
树链剖分，线段树/树状数组

• 树剖是肯定要的。
• 还需要一个支持区间加等差数列区间求和的数据结构，线段树上打懒标记就好了（由于标记可加，一切都变得简单了起来），或者在区间修改区间求和的树状数组上再魔改一下。

Rabbit’s Howse [Very Easy]

Provided by ultmaster.

签到。

Substring Diff [Medium]

Provided by zerol. HackerRank
dp

解法1：

• dp[i][j] 的含义变为第一个串到第 i 个字符，第二个串到第 j 个字符，在允许至多 k 个位置不同的情况下，最长的公共子串的长度以及不相同位置的个数（保存两个量）。
• 转移时如果发现不同的字符要超过 k 了，利用类似滑动窗口的思想从公共子串的开头删除若干个字符，使得当前不同字符的个数仍然维持在 k。
• 为了快速计算需要删除几个字符，需要预处理 nxt[i][j] 表示从第一个串的第 i 个字符及第二个串的第 j 个字符开始往后看，最少几步之后会遇到不相同的字符。

解法2：

https://acm.ecnu.edu.cn/wiki/index.php?title=Jagiellonian_U_Contest_(ITMO_Day_3)#Problem_L

zerol：选完这题才发现这题在不止一个地方做过，甚至是某一场训练赛的签到题。

Transform IP Database [Medium Easy]

Provided by kblack. tehran 2017 I
模拟

• 首先读入是一个问题，可以使用 sscanf 等会方便一些，可以保存在一个闭开区间的 long long 里。
• 之后就方便了，排序后合并连续区间，从每个开头，从 $lowbit(x)$ （特判 $0$）开始向下枚举掩码长度，把区间吃光就好了。

Ultmaster Dividing The Cake [Medium Easy]

Provided by ultmaster. Latin American Regional 2015 Problem C

• 题意是要选一个点，使得从这个点拉出来的线分出来的较大的一半尽可能大。
• 用类似滑动窗口的方法，枚举一边的端点，使得另一边的端点划出来的另一半尽可能接近一半但不超过一半，然后移动这边的端点的时候，只要减掉一个三角形的面积即可。
• 作为一道计算几何，本题好写、无坑。

Viva La Vida [Easy]

Provided by kblack. coci 2017-2018 #5 T3
模拟

• 首先观察顺序，发现就是每个人处理了一个 order，每人的受益是所有他奴隶的收益之和加上子树大小，题中给出的树表示很友好，从后向前更新子树大小和收益即可。

Weight of Subsequence [Medium Easy]

Provided by zerol. HackerRank
单调set/数据结构

• 在 $n^2$ 的 dp 基础上优化转移。
• 维护一个单调 set，使得结尾的数字越大，权值和越大。插入时需要向后检查，将不符合单调性的元素移除 set。
• 用数据结构维护亦可（bit/线段树）。

X Window [Medium]

Provided by kblack.
dp

• 首先把所有点翻折到第一象限。
• 如果点 A 在点 B 的左下方，那么点 A 可以删掉。
• 剩下的点会形成 x 升序，y 降序的形式。
• 用于覆盖的矩阵肯定是覆盖一段连续的点。
• $dp[i] = min{dp[j]+a[j+1].y \cdot a[i].x | \forall j < i}$

You Only Live Once [Easy]

Provided by kblack. coci 2017 r6 t4
bfs

• 在普通 bfs 的基础上，每搜 k 层都要更新一下地图。

Zerol and KBlack [Medium Easy]

Provided by zerol. HackerRank
博弈，智商

• 按照 $A_i+B_i$ 排序，然后模拟两人依次选的过程。
• 给一个自己发明的证明：修改这个游戏，两人的初始分数是自己数组的和，选了一个下标的时候给自己加一个自己数组中的对应分数，再给对面扣对面数组中的对应分数，游戏结束后，双方的分数是原游戏的两倍。那么这两个游戏是等效的，而这个新的游戏考虑选择对双方分差的影响，那么最优策略也就显而易见了。

Comments