IOI2022
鲶鱼塘(2)
记第\(i\)列的堤为\([0,l_{i}),\)贡献区间为\([l_{i},r_{i}]\)，则限制即\(l_{i}>r_{i}\)或\(r_{i}<\max(l_{i-1},l_{i+1})\)
- 若\(l_{i}>r_{i}\)或\(r_{i}<l_{i-1}\)，即\(r_{i}\)的条件已经满足，仅关心于\(l_{i}\)
- 若\(l_{i}\le r_{i}\)且\(r_{i}\ge l_{i-1}\)，则\(l_{i}<r_{i}<l_{i+1}\le r_{i+1}\)，即\(l_{i}\)无贡献，仅关心于\(r_{i}\)
同时，显然可以钦定\((i,l_{i})\)和\((i,r_{i})\)处有鱼或\(l_{i}=n,r_{i}=n-1\)
定义\(f_{i,j,0/1}\)表示前者/后者中\(l_{i}/r_{i}=j\)的最大答案，转移即
\[\begin{cases}f_{i,n,0}=\max f_{i-1,j,0/1}\\f_{i,j,0}=\max_{j<j'}f_{i-1,j',0}+w_{i}[j,j')\\ f_{i,j,1}=\max\{\max_{j'\le j}f_{i-1,j,0}+w_{i}[0,j]\ ,\ \max_{j'<j}f_{i-1,j',1}+w_{i}(j',j]\}\end{cases} \]双指针实现即可，时间复杂度为\(O(n+m\log m)\)
囚徒挑战(3)
以二进制按位传递，具体做法如下：
- 第\(1\)个人询问\(A\)，并返回二进制下最高位
- 第\(2\)个人询问\(B\)，判断最高位（是否与\(A\)相同）与并返回二进制下次高位
以此类推，每个人消耗两个数，注意到\(5000<2^{13}\)，值域为\(2\times 13=26\)
改为使用三进制，注意到\(5000<3^{8}\)，值域为\(3\times 8=24\)
更本质的，可以看作将区间划分为若干段，即\(f(n)=\min_{2\le i\le n}f(\lceil\frac{n}{i}\rceil)+i\)
由于两数不同，在端点处可直接回答，即\(f'(n)=\min_{2\le i\le n}f'(\lceil\frac{n-2}{i}\rceil)+i\)
由于现在的区间划分并不规整，在实现上有一些细节：
- 每层所分段数需相同，并根据\(x\)判断层数
- 根据层数奇偶性判断所查询数，并检验最后一步是否与\(x\)相同
- 若不同即直接回答，否则返回下一步的信息
经计算，值域为\(f'(5000)=20\)，一种可行方案为\(2,3,3,3,3,2,2,2\)
无线电信号塔(4)
参考这里
数字电路(3)
从底向上考虑，设节点\(k\)有\(c_{0/1}\)个儿子为\(0/1\)，则分别有\(c_{0/1}\)种参数选择为\(0/1\)
注意到这等价于选择\(k\)的一个儿子，将该儿子的权值作为其权值
预处理出每个节点为\(1\)的贡献，即除其到根路径上节点外的儿子个数乘积
（由于模数不为质数，这个过程的实现不能用逆元）
在此基础上，区间翻转显然可以用线段树维护，时间复杂度为\(O(n+m+q\log m)\)
最罕见的昆虫(2)
定义\(f(x)\)表示依次加入\(n\)只昆虫并询问，若结果\(>x\)则取出，最终剩下的昆虫数
注意到\(f(1)\)即昆虫类型数，而答案\(\ge x\)也即等价于\(f(x)=xf(1)\)
二分答案，每次求\(f(x)\)的操作次数为\(n\)，总操作次数为\(O(n\log n)\)
设当前二分到的区间为\([l,r]\)，并对答案分类讨论：
- 若答案\(\ge mid\)，则不妨保留已经加入机器的昆虫（不取出）
- 若答案\(<mid\)，则不妨删除未被加入机器的昆虫
此时，每种昆虫数量\(\in [l,r+1]\)，且其中\(l\)只在机器内，因此操作次数\(\le (r-l+1)f(1)\)
初始取\(l=1,r=\lfloor\frac{n}{f(1)}\rfloor\)，则操作次数可以估计为\(n+\frac{n}{2}+\frac{n}{4}+...\le 2n\)
总操作次数约为\(3n\)，由于二分最坏是向上取整，需要一定常数优化
千岛(4)
独木舟可以看作将边定向，并在每次经过后反向，要求最终每条边方向不变
在此基础上，考虑以下两种情况：
-
对于出度为\(0\)的点，到达其后仅能原路返回，不妨删除
-
若起点出度为\(1\)，显然第一步移动唯一，移动后起点出度变为\(0\)，仅能从该边返回（并结束）
换言之，可以将该点删除并将起点移动到出边终点
重复上述过程，若起点被删除则无解，否则对所有点仅保留一条出边
此时构成基环内向树，可以从起点到环绕一圈后返回，但环上的边方向改变
利用起点出度\(\ge 2\)，交替选择两条出边各两次即可，路径长度至多为\(8n\)
一个特殊情况时是两条出边相互影响（参考1-02.in），此时仅需做\(3\)轮即可
时间复杂度为\(O(n+m\log m)\)
标签：le,frac,log,ge,出边,IOI,起点 From： https://www.cnblogs.com/PYWBKTDA/p/17064364.html