2014codeforces

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

进度:20

CF263E

观察+前缀和。

可以把这个图形转化成一些前缀和相加减的形式……维护两种对角线的前缀和的前缀和就行了……大概是这样。还是集训队大爷的解题报告写得好……

CF293B

搜索

一条路径有n+m-1个点,如果比k大,一定无解。
然后考虑搜索,强制让先出现的颜色标号小,然后对于一种合法方案,设用了num种颜色,已经确定的颜色有cnt种,那么对答案的贡献相当于是从k-cnt中选num-cnt种,任意排列的方案数=p[k-cnt]/p[k-num],p[i]表示i的阶乘。

CF235E

莫比乌斯反演(+结论)

一个神乎其神的结论,反正考试的时候我肯定猜不出来。
还有一种硬搞法:

第一部分暴力,第二部分枚举e,看对每个g的贡献就可以了。
然后O(ab)合并。

CF325E

构造

奇数的话无解。偶数的话把相邻两个点看成一个组,每个点只会和一个组里的点连边。然后把点之间的连边看成组和组之间的连边,那么每个组的入度出度都是2。然后就变成了找欧拉回路了,再搞搞对应回去就行了。

CF260E

暴力+二分+可持久化线段树

暴力枚举a1...a9对应的位置,然后对于横竖二分找到每一条线的位置,再用可持久化线段树搞出每一段的和搞出来验证一下就行了。

CF325D

并查集

先把图复制一遍接在右面,那么加入一个点后不存在从上到下的4连通路经等价于这个点和在右侧图中的这个点存在8连通路径。然后并查集判一下就好了。

CF360D

bsgs+容斥

转化公式

Ind(c)=0, 所以满足条件的数都是这样形式,记ind(Ai)=x
,其中a可以是任意整数。
那么每一个满足条件的数就一定会满足是gcd(x*gcd(b1,b2….bm),p-1)的倍数,这点想一想就可以明白。
对于每个集合,我们记能表示出的最小数为x,那么x一定是p-1的约数,并且x和x的倍数一定在集合中。
于是我们筛出所有p-1的约数,看每个约数是否在集合中。然后利用容斥原理搞一下就可以了。
复杂度:设bsgs的块大小为k,预处理复杂度为k,处理查询复杂度为np/k,设约数个数为x(x最大1000左右),判断每个约数能否被表示:nx,容斥原理x*x。

CF267C

高斯消元

考虑每个点的值,令f[u]表示从1到u的某条路径的流量和。则我们可以列出n个方程,一条边(u,v)的流量就是f[v]-f[u],用流量平衡可以解出f[i],然后考虑w[i]的限制。不妨令f[1]=0,f[n]=1,这样f[i]都在[0,1]中,我们取最小的
(w[i]/fabs(f[v[i]]-f[u[i]])),然后每个点的f值都乘以这个值就行了。
求最大流就把所有从1号点流出的流量算出来就可以了。

CF235C

后缀自动机

先把串的后缀自动机建出来,然后把串复制一遍接在后面,放到自动机里跑,当匹配成功了后,就让起始位置往后挪一位(如果出现重复了就退出),继续匹配。挪的时候如果当前匹配到的点的的父亲的len恰好等于串长-1,那么当前点就要往上走一步,否则不用管。

CF335E

概率与期望

给出B求A很容易,假设有一条高度为t的索道,那么这条索道期望经过的楼数等于
1+p+p^2+...=1/(1-p),p=(1-2^t)
也就是2^t,所以第一问的答案就是n
给出A求B难一点,考虑逐层来推,推到第i层时,只需要算出第i层对答案的贡献减去第i-1层被覆盖的贡献就可以了。
怎么推呢,高度为h的地方有一条长度为L轨道,位置有n-L种,每个位置上要求首尾高度都是h,中间高度小于h,贡献就是2^i,被搞掉的贡献就是2^(i-1)*(L-1个楼中有高度为h-1的楼的期望个数+1),期望个数本来是(L-1)/2^(h-1),但是因为我们是在高度小于h的情况下讨论,所以概率是(L-1)/(2^(h-1)-1)
把上面这些求个和就行了。

CF339E

搜索

从结束状态往前搜每次怎么转的,每次转之后一定会合并至少一段有序的区间。纯暴力就行了……

CF286E

FFT

这是一道去年国赛前培训考试的题,当时too naive连fft都不会,这题压根不懂……然而今天再看一下发现好像并不难……
因为给出了背包的结果,我们只需要对背包结果求一个卷积就可以得到这些元素能表示的所有元素了,如果某个元素能被表示,那就不需要加入答案,如果能被表示且未在初始的背包结果里出现则无解。

CF331D3

线段树+倍增+巨多的细节

用线段树处理出每个箭头,每个点第一次到达的箭头,然后倍增求出到达的第2^k次方个箭头是什么和所需时间,然后就是一顿讨论了。

CF240F

线段树

对于一次操作,先统计出每个字符出现的次数,然后进行最多52次区间覆盖(也可以一起做一次)就可以了,实现的时候要注意常数,然而cf数据好水。

CF241D

结论+DP

只对前32个数暴力dp搞就好了,异或等于0的概率是1/32,模p等于0的概率是2^32/p,乘起来还是概率挺大的。

CF280E

数论+dp

好神的一道题……
最终的答案是一堆二次以下函数的加和,于是这个函数的导数是单调增的,然后令f[i]表示前i个数的导函数,然后更新f[i+1]的时候我们发现只需要把f[i]从f[i]的零点断开,左边右移a,右边右移b,中间添0,再把x[i+1]对应的导函数加上就行了,这个过程可以O(n^2)维护,平衡树可以做到nlogn。
最后,ans[n]就等于f[n]的零点,然后倒着就能推回来。

CF261D

dp

暴力题……
注意它最多循环min(maxb,n)层,而maxb*n<=20000000……
于是把序列搞出来,令f[i]表时结尾<=i的LIS长度,那么加入一个数x,用f[x-1]一直往下更新,直到更新失败,每一次成功的更新,会使一个值增大1,代价O(1),那么一共只会更新最多n*maxb次,所以233……

CF311E

最小割

裸的文理分科,不想说了.

CF306D

乱搞

让每次转个角度随机走一点就行了.

CF295D

dp

朴素的dp+一堆前缀和优化,我写的巨渣……f[i][j]表示i层最下层宽度j的方案,g[i][j]类似,但是要保证倒数第二层比最后一层窄,然后随便转移

CF354D

dp

用第二种覆盖的金字塔高度一定不会超过1000,所以我们暴力dp就可以了

CF240E

朱刘算法

裸题