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

我已经鏼了9

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

想了很久的一道题,首先我们不妨设白球从左到右所代表的编号为1,2,3...n,这点很重要,是解题的关键,对于答案我们只需要乘上\(n\)就可以得到正确的答案。

为什么这样是正确的呢?我们注意到,一旦固定了白球,那么他所代表的编号的其他球的位置都是可以随白球的编号的改变而改变。

我们把白球全部列在上面,那么考虑序列的合法性,和白球同一个编号的,必须在他之后出现。而白球之间也有出现顺序。这样使我们联想到拓扑排序。我们可以画出一个N\times N的有向图(具体可以参考官方题解)。这样我们的问题转化为求这张图的拓扑排序数,一般情况下是NP的,但是这张图很有特点,我们可以使用动态规划来求解,同类的用隔板法公式来做。

agc003_d

首先我们把所有数最小表示,去除那些三次方因子。这样我们只需要对于每一个数找一个j满足i*j是cubic即可。等价于把质因数分解后的次数填成3,但是这样是根号级别的。

考虑这样一个observation,我们只需要考虑到\leq n^{\frac{1}{3}}的质因子就行了,为什么?

因为这样的话,我们再经过一次reduction,只会剩下两种情况,一种是只剩某个质因子的平方,另一种是两个质数的乘积,因为反之你都可以把它凑成一个新的较小的三次方。

于是这道题就做完了。

agc003_e

不难注意到,若存在A_{i}\geq A_{i+1},那么A_{i}我们是完全可以忽视的。

于是我们得到了一个严格单调上增序列B

这道题正着做不好做,考虑反着做。

那么每个序列都一定是上一个序列的若干复制加上一段前缀

于是我们知道第i-1个序列在第i个序列中的出现次数

而这段前缀又一定是之前的某个序列,所以我们可以再根据这个重复上述操作

而每个序列对答案的贡献实际上是由最终剩下的那部分产生的(一定按照1~n的顺序存在)。

利用二分以及模运算的性质,这道题的实际复杂度是O(Q\log A\log N+N)

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条评论

发表评论