WC2023 zc 讲课听课记录

PO Final 2022 Day2 三角形演讲

比较简单！

考察最大值所在的集合，一定可以是一段值域后缀，仔细想想就可以知道另外一个一定可以是一段值域前缀。

这个枚举一下后缀长度，是比较好做的。

官方做法利用了进一步的结论，一定存在一个方案使得第二组大小等于第一组最大值。

EGOI2022 玩具设计

憨憨题。

增量地加入每个数，在之前每个连通块二分一下，我们只要每次 push 新连通块的时候把之前的前缀并上就好了。

BalticOI2022 信息传递

联考考过，很难！！！

我们不妨在发送/接收信息的过程中维护两个集合 \(S_0,S_1\)，表示上次询问得到错误/正确答案对应的答案集合，由于值域过大只需存若干值域区间。

我们尝试给 \(S_0,S_1\) 中每个数字一个 bit，当前发送的 bit 就代表答案在哪个集合里。

我们考虑发送一个 bit 得到的信息：由于信息的最后两位不能同时取反，我们可以将 \(S_0\) 中不是这个 bit 的数去掉。

于是我们将 \(S_0,S_1\) 劈成两半，前一半赋 \(0\)，后一半赋 \(1\) 即可。

当然也可以精细一点，值域大劈成两半，值域小 dp，不过这就是 CF1746E2 Joking (Hard Version) 的内容了。

RMI2018 登山者

笨蛋题。

首先把序列变成峰谷峰谷峰谷形式，然后直接拉出至多 \(O(n^2)\) 对位置跑最短路就好啦。

复杂度 \(O(n^2\log n)\)，常数很小，因为合法状态不多。

EJOI2022 寻找树根

为啥不会！

构造一个序列，前面是叶子节点后面是非叶结点，在这个序列上二分最短合法前缀。

唯一的 corner case 是前缀长度为 \(2\)，我们随便拉一个叶子结点出来一起询问一下就好了。

CEOI2022 奖品

很怪的题目。

选择第一棵树的 dfs 序前 \(k\) 个点，那么第一棵树的虚树没有其他点，我们注意力可以放在第二棵树的虚树上。

我们将这些点按照第二棵树的 dfs 序排序并询问相邻的，考虑能不能推断出所有信息：

我们每次可以得到两条 \(d_x-d_l=w\) 的信息，我们发现这些信息剋也使得每个虚树上的非关键点被询问到，且这些信息能让所有关键点两两互推。

于是直接 dfs 解出所有值就好了。

OIE2022 最大公约数

从低到高确定 gcd 的每一位可以获得一个 \(4\log V\) 做法。

事实上我们可以一次确定两位，我们在最开始去除公共后缀 \(0\)，每次最后两位都是 \(01,10,11\)，两次询问足以确定。

SOI2021/2022 爪式排序

不妨假设初始抓住卡 \(0\)。

组合出一种基本操作：><>，表示将自己手上拿的与目前下方的数向右平移。

我们尝试每次把最大的两个数移到最右边，具体地，我们需要保持以下子问题：

开始时，位置为 \(1\) 且手上有卡，其他卡片均位于 \([1,n]\)；结束时，位置为 \(n-2\) 且手上有卡，其他卡片均位于 \([1,n-2]\)，且 \(n-1,n\) 已经还原。

设两个数的位置分别为 \(x,y\)，一个大致的想法是把爪子移到 \(x\)，然后把 \(x\) 平移到 \(y\) 前面，然后将 \(x,y\) 一同平移到后面。

我们可以列出以下操作：\(x-1\) 次 >，\(y-x-1\) 次“平移”，\(1\) 次 >，\(n-y\) 次平移，\(2\) 次 <。

当然有一些 corner，我们直接将其通过 \(O(1)\) 次移动归至上述问题：

• \(x\) 初始在手上：
• • 若 \(y\) 在 \(x\) 下面：\(1\) 次平移，\(2\) 次 <。
• • 否则：\(1\) 次 ><。
• \(x>y\)：交换 \(x,y\)，最后执行 >><<。

操作次数是 \(\frac{3n^2}{4}\) 级别的。