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

题意：

维护一个序列，要支持：

1. 区间加
2. 区间赋值
3. 给出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轮。每轮每个骑士都要和另一个单挑。

满足:

1. 任意两个只会单挑一次
2. 两场决斗中,第一轮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（其实是电脑没电