lyzqs的博客课件
Xylophone
来源：
IOI2018 练习赛T2
题意：
有一个乱序序列0~n-1，可以询问一个区间最大值-最小值，不超过1e5次询问出整个序列，保证0在n-1左边。n<5e4。
交互题
题解：
询问每两个相邻和每三个相邻的数然后讨论一下就可以了
Bubble Sort 2
来源：
IOI2018 练习赛T3
题意：
给一个序列，有一个操作，可以扫一遍数，如果$a_i>a_{i+1}$就交换，有q次修改，每次询问要多少次操作可以让序列有序。
$n \leq 5e5 $
题解：
可以发现每次每个数前面的一个最大数都会放到它后面去。
答案就是max{一个数前面比它大的数}
也就是max{i-"前面$\leq a_i$的数的个数"}
然后就可以用树套树或者KD-Tree维护这个信息
注意到前后有两个数x,y且$x \leq y$那么x不可能成为答案
于是可以把刚才的式子改成max{i-"$\leq a_i$的个数"}
然后就可以用线段树维护了
Road Service
来源：
IOI2018 练习赛T4
题意：
题答
给一棵n个点的树，
需要加k条边，使所有点对之间距离和最小。
根据答案给分。
$n=1000,k=300$
或$n=1000,k=100$
或$n=20,k=4$
题解：
爬山？
考虑选出的k个点的集合，进行随机调整，更优就记录。
可以爬很高的分
DP？
假装我们要选k个关键点，使所有点到关键点的距离最小。
不考虑两点直达的情况。
假装最优解里每个点到关键点的距离不会太大（比如不超过10）。
然后可以多项式时间DP，可以拿满分。
组合动作
来源：
IOI2018 D1T1
题意:
交互题
懒得写了
题解：
用两次询问确定首字母
然后就每次在知道的后面加一个字符就好，询问次数2n+2，30分
设已知串为s
可以问sBsXBsXXsXY
然后分类讨论
如果是|s|+1,下一位是B，如果是|s|+2，就是X，否则是Y
询问次数n+2，可以拿100分。
狼人
来源：
IOI2018 D1T3
题意：
交互题
懒得写了
题解：
考虑询问一个中间点能否满足要求
把边权设置成$min(a_i,b_i)$,然后求Kruskal重构树。
Seats
来源：
IOI2018 D1T2
题意：
懒得写
题解：
是D1最难的题
没懂，不会
Rainbow
来源：
APIO2017 T1
题意：
懒得写
题解：
欧拉定理
假设河流为黑点，陆地为白点
考虑白点数量-$1*2$白矩形数量-$2*1$白矩形+$2*2$白矩阵数量
中间漏了点东西没看到
然后用主席树维护矩阵信息
Rikka with Consistency
来源：
Rikka with Consistency
2018-2019,Xuzhou Regional Contest, C
题意：
有一条折线，每个拐点为$(i,H_i)$。其中$H_0=H_n=0$。
两个人沿折线走
必须满足每时每刻y一样。
两个人走到对面。
求最小路程和。
题解：
我一开始想的是dp。
然后就啥都不会了。
题解也果然是dp。
在所有的$(i,j,H_i)$建状态如何跑最短路orz。
Rikka with Data Structures
来源：
Rikka with Data Structures
2018-2019,Xuzhou Regional Contest, E
题意：
维护一个序列，要支持：
- 区间加
- 区间赋值
- 给出x和一个区间[l,r]，问[l,r]之间有多少个y，满足$A[x...y]$的最大值$=max(A[x],A[y])$
$n,m\leq 10^5$
题解：
假设x<l。如果x在中间拆成两个区间就好了。
考虑[x,l]最大值v，那么从v开始的不递减序列都合法。
有一些细节特判下。
相当于一直往后跳比它大的，求能跳几次，出来是什么。
线段树维护区间最大值，。
询问时讨论v和左区间最大值关系就可以递归到左右，复杂度$O(log n)$。
Rikka with Sorting Networks
来源：
Rikka with Sorting Networks
2018-2019,Xuzhou Regional Contest, I
题意：
按顺序给出k个比较器(u,v)，如果A[u]>A[v]就交换u,v。
问有多少个$1$~$n$的排列经过$k$个比较器后，最长上升子序列的长度至少为$n-1$。
100组数据。$n\leq 50,k\leq 10$。
题解：
最长上升子序列为n-1的只有$n^2$个
那么直接枚举最终排列，O($2^k$)倒推回去判断是否有矛盾就可以了。
复杂度$O(Tn^22^n)$
(这时间不是爆炸了吗。
Rikka with Grid Graghs
来源：
Rikka with Grid Graghs
2018-2019,Xuzhou Regional Contest, L
题意：
给一个图一堆边，求删除哪些边没有环。
题解：
插头dp不会。
Tournament
来源：
Tournament
2018-2019,Qingdao regional Contest, F
题意：
n个骑士决斗，有k轮。每轮每个骑士都要和另一个单挑。
满足:
- 任意两个只会单挑一次
- 两场决斗中,第一轮A和B单挑，C和D单挑，如果第二轮A和C，那么B必须和D单挑。
输出字典序最小解或者无解。
题解：
构造题
第i次1和i+1打，然后到2的幂次为止都可以由前面构造，然后平移就可以了。
$k\leq lowbit(n)$时无解
Counting Sheep in Ami Dongsuo
来源：
2018-2019,Shengyang Regional Contest, F
题意：
有一个n个点的拓扑图，每个点一个权值。每个权值不超过w。
三个人从同一个点出发，走三条不同路线，这个方案的权值就是最后停在三个点的权值和。
对于k=0~3w，求有多少个方案权值为k。
$ n\leq 1e4,m \leq3e4 ,w \leq400$
题解
三条路线要不同限制容斥一下
然后后面因为某些原因没记录了qwq（其实是电脑没电
0 条评论