WC2023(授课与讨论4)

PO-Final 2022 三角形演讲(1)

排序后，显然每一组是一个区间，设分别为\([1,x],(x,y]\)和\((y,n]\)

枚举\(y\)并对前两段分类讨论，限制即\(\begin{cases}a_{x}\le n-y\\a_{y}\le x\\a_{n}\le y-x\\\end{cases}\)或\(\begin{cases}a_{x}\le y-x\\a_{y}\le n-y\\a_{n}\le x\end{cases}\)

显然两者分别可以贪心取\(x=a_{y}\)或\(a_{n}\)并验证，时间复杂度为\(O(n)\)

EGOI 2022 玩具设计(1)

显然能且仅能判断原图的连通性，因此只要得到连通块即可

维护当前联通情况及前若干个连通块连通的版本，加入时二分即可

操作次数为\(O(n\log n)\)，但并跑不满

Flight to the Ford(4)

参考这里

Climbers(1)

定义\(f_{i,j}\)表示其中一个人在\(i\)且另一个人在\([j,j+1)\)中的最少代价

转移对每个人向左/右分类讨论，跑最短路即可，时间复杂度为\(O(n^{2}\log n)\)

Where Is the Root?(2)

记\(rt\)为答案，任选一个度数\(\ge 3\)的点\(k\)为根建树

询问集合\(S\)，满足\(|S|\ge 2\)且其中任意两点无祖先-后代关系

不难发现，答案为Yes当且仅当\(rt\)在某个\(x\in S\)的子树中

维护当前答案集合\(T\)，每次即选择上述\(S\)使得\(\sum_{x\in S}|sub_{x}\cap T|=\lceil\frac{T}{2}\rceil\)

关于\(S\)的构造，即不断选\(T\)中最深的节点，并删去子树内已选的点

为了保证\(|S|\ge 2\)，有以下实现细节：

• 若\(T\)在\(k\)某个儿子的子树中，则最终将\(k\)另一个儿子加入\(S\)即可
• 若\(T\)在至少两颗子树中，则最初的两个节点选在不同子树中即可

每次\(|T|\rightarrow \lceil\frac{|T|}{2}\rceil\)，询问次数即\(\lceil\log_{2}n\rceil\le 9\)

Prize

咕咕咕

OIE 2022 最大公约数(2)

查询\((0/1,0/1)\)，其中恰有一项\(gcd\)为偶数，即得到\(x\)和\(y\)的\(2\)进制下最低位

类似的，在\((a,b)\)基础上查询\((a/a\oplus 2^{k},b/b\oplus 2^{k})\)，即可确定\(x\)和\(y\)的第\(k\)位

由于\(|x|,|y|<2^{60}\)，总查询次数为\(4\times 60=240\)，考虑以下优化：

• （除最低位外）上一轮已查询\((0,0)\)的结果，仅需查询其余三项
• 将初始的\(a,b\)在\([0,2^{60})\)中随机，则结果均匀分布，期望仅需\(\frac{0+1+2+3}{4}=\frac{3}{2}\)次

（期望）总查询次数为\(1+\frac{3}{2}\times 60=91\)次

SOI 2021/2022 爪式排序(3)

为了方便，这里将卡片上的数均\(+1\)，并假设初始机器抓着\(0\)

考虑操作\(><>\)，即可使机器和其下方的数均右移

考虑每次移动到\(n\)放\(n\)和\(n-1\)，并将序列翻转转化为\(n-2\)的子问题

以\(3n\)次操作完成\(2\)个数，求和后约为\(\frac{3}{4}n^{2}\)，下面考虑实现细节——

为了保证子问题形式相同，也即要实现以下过程：

• 初始：机器位于\(1\)且抓着一张卡，位置\([1,n]\)上均有卡
• 最终：机器位于\(n-2\)且抓着一张卡，其中\(n\)和\(n-1\)上为对应卡

记\(n\)和\(n-1\)上对应卡的初始位置为\(x\)和\(y\)（抓着则为\(0\)），并分类讨论：

• 若\(x=0\)且\(y=1\)，则执行\(n-1\)次\(><>\)和\(2\)次\(<\)
• 若\(x=0\)且\(y>1\)则执行\(1\)次\(><\)，转换为\(x=1\)
• 若\(0<x<y\)，则执行\(x-1\)次\(>\)、\(y-x-1\)次\(><>\)、\(1\)次\(>\)、\(n-y\)次\(><>\)和\(2\)次\(<\)
• 若\(x>y\)，则将\(x,y\)交换后做上述过程，并在最后做\(1\)次\(>><<\)

操作次数最多为\(3(n+1)\)，且需要特判\(n\le 2\)时（注意此时机器并不一定抓着\(0\)）

当\(n=300\)时，总操作次数最多为\(7+\sum_{4\le i\le 300,2\mid i}3(i+1)=68398\)