2015codechef

2016.05.10 00:00 Tue | 223次阅读 | 旧日oi | 固定链接 | 源码

进度:15

Codechef NOV12 Arithmetic Progressions

分块+FFT

设一个block,大约2000左右,然后把至少有两个位置的距离小于block的(i,j,k)暴力算出来,复杂度block*n
对于然后对于都大于2000的,我们对每个块,把左边和右边分别建成一个数组,第i项表示值为i的有多少个,然后FFT一下就可以了。复杂度n/block*limloglim,lim是最大元素大小。

Codechef August 2013 Challenge

树分治+FFT。

先树分治,设当前分治中心是i,那么遍历i的子树,令f[i]表示深度为i的有多少个。对f求下卷积,然后暴力枚举质数,统计答案。此时会有重复,只需要对每个子树再做一遍去重就好了。
复杂度nlog^2n

Codechef July14 Sereja and Equality

dp+组合数

f[i][j]表示i个数的排列中逆序对<=j的个数,可以O(n^3)处理出来。
然后对于每个询问,枚举区间的长度。社长度为i,对于第一个区间,相当于从n个数里选i个,放在n-i+1个位置上,剩下的任意排列,这i个数的逆序对不能大于E的,此时对于第二个区间,就是n个数里选i个,剩下任意排列,位置固定,这i个数的排列也固定。随便乘一乘就好了。
复杂度O(n^3+Tn).

Codechef March Challenge 2014 The Street

线段树(+splay维护凸包)

考试的时候写了一发splay维护凸包,最后5分钟写完了,然后没时间改动态开点了,然后爆零,然后数据错了,然后有了70……后来改成动态开点之后本机过掉了,但是在cc,清澄上都a不了。
虽然复杂度一样,正解是个挺神奇的做法,两个操作分别可以看成是求一些1次函数在某个点的最大值或者和。和用线段树的话很好求。
最大值的求法:对于这个函数覆盖的一段区间,如果这个区间没有函数覆盖,直接让这个函数覆盖这个区间,否则比较一下当前覆盖区间的函数和新来的函数,如果完全小于或完全大于,就不管或者直接替换。否则求出大小交换的位置,选择一边传下去其中一条直线就可以了。查询的时候用一路上所有经过区间的覆盖直线更新答案。

CodeChef JAN 12 Misinterpretation 2

数论

奇数时的答案ans[i]等于ans[i-1]*26,下面讨论偶数
题里的变换可以看成是一个f[i]=2i(mod x+1)的置换,我们要求的就是有几个循环。
gcd(i,x+1)=p的个数为$\phi((x+1)/p)$,而$gcd(i,x+1)=p$对应的i所在的置换群大小是满足$2^k=1 mod (x+1)/p)$的最小的k,也就是2关于(x+1)的指标,记为ord((x+1)/p)。
那么我们要求的置换群个数$G=\sum_{p|x+1}{\frac{\phi(p)}{ord(p)}}$
假设x=x'*p^q,那么ord(x)=lcm(ord(x'),ord(p^q))。于是我们可以暴力处理出p^q的ord,就可以类似线性筛的处理出ord(x)。我们把x+1质因数分解,然后用搜索的方式枚举每一种质因数的次数,顺便把phi和ord都维护出来就可以了。
需要预处理出质数表,p^q的ord。对于每组询问,一起处理出所有数的质因数分解(调和级数那个做法),然后一个一个算就可以了。
复杂度每一项都不太大……

Codechef JAN 12 Card Shuffle

Splay

SB splay

Codechef June Challenge 2014 Sereja and Arcs

分块+树状数组

定义阈值block,把相交的弧分为两类,一类是其中一种颜色出现次数大于block的,一类都小于。对于第二种,我们直接暴力统计就好了。对于第一种,枚举每一种出现次数超过block的颜色,这样的个数不会超过n/block个,然后维护一个前缀和sum。然后枚举每一种其它的颜色,设v表示这个颜色出现位置的集合,那么这个颜色和第一次枚举的颜色的相交圆弧个数就是$\sum_{i=1}{sum[i]\sum_{j>i}{(sum[j]-sum[i])}}$,同样的,对后缀也这么搞一遍就可以了,block设为$\sqrt{n/log(n)}$时最优,复杂度$n\sqrt{nlog(n)}$

Codechef June Challenge 2014 Two Companies

树链剖分+最小割

源点连第一种集合里的点,汇点连第二种的,流量就是各自的满意度,相交的点连容量inf的边跑最小割就是答案。
怎么求相交?先树剖一下,然后把第一个集合里的路径扔到线段树里,用一个bitset维护每个点出现多少次。然后对第二个集合里的点查就可以了。
复杂度$O(maxflow(m1+m2,(m1+m2)^2)+m^2log^2n/32)$

Codechef DEC14 RIN

网络流

对每一学期的每一门课新建一个点,同一门课相邻两个学期之间连一条容量为后一个学期费用的边,若a是b的前置课程,那么从第i个学期的a,向第i+1个学期的b连一条容量inf的边,然后跑最小割就是答案了,挺形象的。

CodeChef March 2015 Counting on a Tree

容斥+并查集

Codechef 2015 Aug - DISTNUM

树套树

数据集1:直接模拟每次操作就可以了,元素判重可以用map或者hash表或者预先离散化。
数据集2:没有插入和删除,这是个经典问题。对于第i个数找到上一个和这个数相同的位置,记为pre[i],那么一个询问[l[i],r[i]]就相当于求l[i]-r[i]内pre[i]<l[i]的数的个数,一个二维数点问题,直接排个序+树状数组就可以了。
数据集3:把公式变一下形,


于是我们只需维护出每个元素的0,1,2,3次方和就可以了,和数据集2的搞法一样。
数据集4,5:有了修改操作,那么我们可以再套一层数据结构解决,我选择的树状数组套线段树。修改位置x的元素时,若有某个pre[i]=x,那么把pre[i]改成pre[x],还要在树套树中删掉(x,pre[x])这个点,然后更改x位置的元素的值,重新计算pre[x],如果之前有某个位置的pre[i]=pre[x],那么把pre[i]改为x,所有的操作都可带两个log完成,修改的时候同时维护那几个信息即可。
数据集7,8:
做法1:树状数组套线段树不太支持插点,因为会使范围变大。但是因为操作可以离线,那么我们可以预先扩大范围,预先处理出每个元素要插在什么位置,这步用一个平衡树就可以实现,只要预先把所有插入操作做一遍,然后看每个元素所在的位置就好了。由于扩大了范围,坐标变的不连续,找到下标为x的元素还需要一个二分答案+树状数组的过程,其它就和数据集4,5相同了。
做法2:直接替罪羊树套线段树,不加赘述……

CodeChef May Challenge 2015 Chef and Balanced Strings

分块

分块+hash,将每个前缀hash为一个26位的串,表示每个字母出现过奇数次还是偶数次,然后再离散化一下。
然后考虑分块,如果询问在同一个块或相邻块,那么直接暴力,从左到右枚举,扫到一个数,先统计答案,再把这个数加到一个hash表里,统计答案的话就是把公式拆开,分别维护一下几项的和就可以了。
对于不同块的,我们预处理出第i块到第j块的答案和第i个点到每个块的答案就可以了。
时空复杂度都是nsqrt(n)
虽然看起来很简单,但是很难写……卡空间+卡常数……

Codechef JULY15 HAMILG

带花树+组合游戏

找出图的一个最大匹配,那么我们的起点只要选择一个非匹配点,那么对方一定会走到一个匹配点上,我们只需走对方走的点的匹配点就好了。
那么如何确定哪些点不一定在最大匹配上呢?任找一个最大匹配,然后从那些未匹配点再找一遍增广路,此时在队列里出现过的点都不一定在最大匹配中。

Codechef JULY 2015 EASYEX

数学+FFT

令x[i][j]表示第i面的j轮是否朝上,朝上为1,否则为0
把公式展开,变成:

把其中一部分

暴力展开,我们可以得到一个大的多项式,其中每一个变量组都由f个变量相乘,再把整个多项式展开,就会得到很多长度为L*f的变量组.如果这一个变量组有贡献,那么就是说这个变量组里所有变量都是1,如果这个变量组中存在两个变量x[i][k]和x[j][k]其中i!=j,那么这组的贡献一定是0,所以我们可以单独求对于每一个i,
中有任意数量的不同的j的变量组个数,这个不同的j的数量也就相当于第i个面朝上的轮数.设这个东西的生成函数为G(x),G(x)的第i项系数表示轮数为i变量组个数.如果我们知道了这个,那么把这个多项式求一个L次幂,得到的多项式的第i项的系数,就代表了


中进行了i轮变量组个数.
G(x)的系数怎么求?我们强制让选择的不同的j是从1开始的连续的正整数,那么可以得到

s[f][i]代表多项式经过f次幂之后第i项的系数.s[f][0]=0
那么最终G(x)=s[f][0]+s[f][1]x+s[f][2]x^2+…+s[f][f]x^f.
令g(x)= G(x)^L
最后枚举轮数,进行了p轮对答案的贡献就是

g[x][p]表示g(x)^L次方的第p项系数.
多项式快速幂用fft解决就好,精度要求不大.
注意fft的范围其实只需要到2003,因为 当p>mod一定为0.

Codechef JUNE 2015 CHEFBOOK

线性规划+费用流+差分约束

神题!线性规划搞一搞,然后转化成费用流,跑出来解之后回来再用差分约束搞一搞……哎,太神了……