摘要：
首先，观察到题目要求变出一个 DAG，所以我们可以给节点一个拓扑序。设其为 \(a_0, a_1, \cdots, a_{n - 1}\)。 因为原图是完全图，所以在 DAG 中，对于所有 \(0 \le i < n\)，\(a_i\) 要连 \(a_{i + 1}, a_{i + 2}, \cdo 阅读全文
posted @ 2025-08-02 16:15
David9006
阅读(23)
评论(0)
推荐(0)
摘要：
考虑什么操作会让二叉树的形态变化。我们发现，改变子树的根会让形态变化。 所以，我们枚举根，之后递归计算两个子树的答案，最后合并即可。枚举时记录得到最优答案的那个根，之后按前序遍历（根-左-右）的顺序输出即可。 这可以用记忆化搜索优化获得 100 分。 #include <iostream> #inc 阅读全文
posted @ 2025-08-02 16:14
David9006
阅读(25)
评论(0)
推荐(0)
摘要：
1. 关于编译器 可以使用 C++14。 用 -Wall 显示更多警告。 用 -fsanitize=address,undefined 测试 RE。搭配 -g3 使用最佳。 2. 关于终端 使用 ulimit -v <内存大小> 限制程序使用内存（单位：kB）。 使用 ulimit -s <内存大小 阅读全文
posted @ 2025-08-02 16:14
David9006
阅读(14)
评论(0)
推荐(0)
摘要：
2024.10.16 估计分数：\(30 + 15 + 100 + [0, 5] = [145, 150]\)。 实际分数：\(30 + 15 + 100 + 5 = 150\)。 难度排序：T3 << T1 < T2 < T4。 开 T1，第一眼看着还行，但有趣程度有点难办。“保证答案在 unsi 阅读全文
posted @ 2025-08-02 16:14
David9006
阅读(22)
评论(0)
推荐(0)
摘要：
先说暴力。线段树维护 \(a_i - s_{i - 1}\)，每次暴力 \(O(n \log n)\) 查找 \(0\) 的位置。 这会超时，考虑加个优化： 维护一个区间 max，在查询到的区间的 max 小于 \(0\) 时退出。 设 \(p\) 为修改的位置，\(x\) 为修改成的值。在修改时把 阅读全文
posted @ 2025-08-02 16:13
David9006
阅读(54)
评论(0)
推荐(0)
摘要：
我们的策略是：每一轮把所有按钮全按一遍，如果有一个按钮空了，就把它记录下来，下一轮不按它。 首先，先把 \(a\) 升序排序。记录一个 \(l\)，表示在当前，位置 \(\ge l\) 的按钮都非空。 同时，只有 \(a_i < 0\) 了，第 \(i\) 个按钮才能不按。在 \(a_i = 0\) 阅读全文
posted @ 2025-08-02 16:13
David9006
阅读(17)
评论(0)
推荐(0)
摘要：
本文主要记录考场上可用的（玄学）技巧。 若有补充，欢迎在评论区留言。 I/O 优化 ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr) 可以关闭同步流，有时比快读快写更快。与文件读写共同使用时，需要在程序结尾加入 cout 阅读全文
posted @ 2025-08-02 16:12
David9006
阅读(34)
评论(0)
推荐(0)
摘要：
对于每个幼儿园维护婴儿 rating 的 multiset，再维护这些幼儿园最大 rating 的 multiset（设其为 \(M\)）。 修改时： 如果要修改的婴儿 rating 为原来幼儿园中的最大值，就更新 \(M\)。 如果要修改的婴儿 rating 为新的幼儿园中的最大值，也要更新 \( 阅读全文
posted @ 2025-08-02 16:11
David9006
阅读(14)
评论(0)
推荐(0)
摘要：
注意到如下结论：区间 \([l, r]\) 满足题目条件当且仅当 \(a_l\) 第一次出现，且 \(a_r\) 最后一次出现。 证明：充分性显然，下面证明必要性。 若区间 \([l, r]\) 不满足上述条件，则我们可以找到在 \(a_l\) 左边与其相同的数与 \([l + 1, r]\) 拼起 阅读全文
posted @ 2025-08-02 16:11
David9006
阅读(16)
评论(0)
推荐(0)
摘要：
设 \(S = a_{n - 1} + a_n\)，则根据题意有 \(S \le k + 1\)。又因为 \(a_{n - 1} \le a_n\)，所以 \(a_{n - 1} \le \lfloor S / 2 \rfloor\)。 我们枚举 \(S, a_{n - 1}\)，则每一种前 \(n 阅读全文
posted @ 2025-08-02 16:10
David9006
阅读(17)
评论(0)
推荐(0)
浙公网安备 33010602011771号