【学习笔记】AGC022

Shopping

• 万物皆可构造
• 我们只关心最少的趟数
• 显然可以$t[i]\to t[i]\mathrm{mod}2L$，然后直接加到答案里面
• 显然可以每走到一个商场停留$2L$时间购物，然后走到下一个商场，答案是$n+1$
• 还是考虑依次处理每个商场
• 记$l[i]=[t[i]\le 2(L-x[i])]$
• $r[i]=[t[i]\le 2x[i]]$
• 假设$i<j$，并且$l[j]=r[i]=1$，那么我在$2L$的时间内可以先到$j$商场，购物完后再回到$i$商场，再从$i$商场出发
• 注意到如果$l[i]=1,r[i]=0$，那么$x\le \frac{L}{2}$
• 如果$l[i]=0,r[i]=1$，那么$x\ge \frac{L}{2}$
• 因此只能$l[i]=r[i]=1$与上述两种点匹配
• 显然$l[i]=r[i]=0$的情况只能在原地等
• 注意细节，如果$l[n]=1$的话可以单独把这个点消掉让答案减少$1$
• 复杂度$O(n)$

Snuke and Spells

• 考虑求出一个序列最多的不修改的球的数目
• 如果当前值为$x$的球保留了$i$个，那么下一个保留的球的值最多为$x-i$
• 显然这个构造是合法的，因为被改变了的球可以任意填坑
• 显然可以暴力$dp$做到单次查询$O(n)$
• 但是这样太慢了考虑继续推性质
• 然后想歪了去推优化$dp$了
• 假设对于值$x$覆盖区间$[x-i+1,x]$
• 那么能保留的球的数目上界就是区间覆盖的并的长度
• 复杂度$O(n+q)$
• 说白了还是构造$dp$然后优化

Construction of a tree

• 万物皆可构造

Sorting a Grid

• 考虑暴力匹配
• 假设我们已经匹配了前$i-1$列
• 考虑构造二分图完美匹配
• 证明利用Hall定理+鸽巢原理
• 复杂度$O(n^4)$

Skolem XOR Tree

• 万物皆可构造
• 考虑菊花图的构造
• 水逆了呵呵 考虑将$1$作为根
• 显然不能只挂长为$1$的链
• 为什么没有想到挂长为$2$的链啊该死
• 我们只需要将剩下的点两两配对使得$x\oplus y=1$
• 显然$n$是奇数就做完了
• 显然$n$是偶数的话$n=2^k$是无解的
• 显然直接找$\text{lowbit(n)}\to 1\to n-\text{lowbit(n)+1}$即可

Two Histograms