IOI2018中国国家集训队作业围观

我已经鏼了4

agc001_d

一脸不会,看了题解才会做QAQ

我们发现这样的一种构造很优雅,若Ax_{1},x_{2},...,x_{m},那么Bx_{1}-1,x_{2},...,x_{m}+1

但是这样的构造在A存在奇数的时候,会GG,那这种做法是不是辣鸡做法呢?

不妨设A中有O_{a}个奇数,那么很显然,会有\frac{N-O_{a}}{2}个弧能连接两个端点。B同理。那么总共有\frac{N-O_{a}}{2}+\frac{N-O_{b}}{2}个弧能连接两个端点。为了连接N个点,那么至少要有N-1条连接两个端点的弧,所以也就有\frac{N-O_{a}}{2}+\frac{N-O_{b}}{2}\geq N-1。易得O_{a}+O_{b}\leq 2,故我们只需要考虑三种情况即可。顺带要特殊考虑M=1以及a_{i}=1的情况。

怎么修正我们的构造?把奇数的东西放到两边即可。

agc001_e

好的实话实说。。我似乎看了题解QAQ,好难嘛人家不会做了啦(╯‵□′)╯︵┻━┻

很容易发现题目是在求这个玩意\sum_{i=1}^{N}\sum_{j=1}^{i-1}\binom{A_{i}+A_{j}+B_{i}+B_{j}}{A_{i}+A_{j}}

不难发现这玩意其实就是网格图上从(-A[i],-B[i])(A[j],B[j])的方案数,于是我们就可以整体处理所有询问,但是这样会重复计算,所以把(-A[i],-B[i])(A[i],B[i])的减去,再除以二就可以啦(因为数对要有序)

agc002_d

终于有一道题是自己想出来的了1

显然看到这个最大值最小,不难想到二分,于是登登登!我们有了一个O(QM\alpha(N)\log M)的做法啦!

然后。。没有修改,整体二分啦!于是我们有了一个O(M\log M)的算法啦!因为要撤销合并的操作,得按秩合并。

agc002_e

终于有一道题。。。TM又是看题解的

首先这题目BB了一堆不知道在BB什么,我们把它画出来,先从大到小排序。

那么操作一对应着删去最左边,操作二对应着删去底下一行

更形象的来说,等价于从(0,0)开始,向上或者向左移动,直到移动到边界。

显然边界一定是必胜态,那么不难用归纳法证明sg[i][j]=sg[i+1][j+1],于是我们找到这样的一个地方,那么对于后手来说,他赢只可能是向上走或者向右走都是必胜态,然后直接判下就行了,时间复杂度O(n)

agc002_f

agc003_d
agc003_e
agc003_f
agc004_c
agc004_d
agc004_e
agc004_f
agc005_c
agc005_d
agc005_e
agc005_f
agc006_c
agc006_d
agc006_e
agc006_f
agc007_c
agc007_e
agc007_f
agc008_d
agc008_e
agc008_f
agc009_b
agc009_c
agc009_d
agc009_e
agc010_c
agc010_d
agc010_e
agc010_f
agc011_c
agc011_d
agc011_e
agc011_f
agc012_c
agc012_d
agc012_e
agc013_c
agc013_d
agc013_e
agc014_d
agc014_e
agc015_c
agc015_d
agc015_e
agc015_f
agc016_b
agc016_c
agc016_d
agc016_e
agc016_f
agc017_d
agc017_e
agc017_f
agc018_b
agc018_c
agc018_d
agc018_e
agc018_f
agc019_c
agc019_d
agc019_e
agc019_f
arc058_d
arc062_e
arc062_f
arc063_e
arc063_f
arc064_f
arc065_e
arc065_f
arc066_e
arc066_f
arc067_f
arc068_e
arc068_f
arc069_f
arc070_f
arc071_f
arc072_e
arc072_f
arc073_e
arc073_f
arc074_e
arc074_f
arc075_f
arc076_e
arc076_f
arc077_e
arc077_f
arc078_e
arc078_f
arc079_f
arc080_e
arc080_f
arc081_f
arc082_e
arc082_f
arc083_e
arc083_f

IOI2018中国国家集训队作业围观》上有3条评论

发表评论