codechef MAY16

r_64 posted @ 2016年5月16日 17:03 in 未分类 with tags codechef , 749 阅读

cc改版了,就在MAY16开始前几个小时。

挺漂亮的。

不过有个缺点是,墙内上不了?

更正: (5.8早上)

  firefox chromium
墙内 上不了 上不了
墙外 基本上得了 偶尔上得了

再更:墙内突然上得了了 (5.8晚上)


按AC时间顺序写咯

LADDU

模拟题,论strcmp的使用。

FORESTGA

二分答案,注意别爆long long了。$O(N\log W)$。

CHEFSOC2

普及组级别的dp题。。(真的是普及组某题改,至少很像

$f_{i,j}$表示第$i$轮的时候球在第$j$条狗手上的方案数,转移随手写

SEAGCD2

开始以为是数论,容斥,反演,瞎jb搞搞

后来发现是瞎jb搞搞

枚举$A$中有多少个$1$,剩下的数肯定互不相同,考虑$\gcd(a,b)>1$就给$a,b$连一条边,相当于枚举图的独立集,因为出题人是sereja,所以可以猜测这样的独立集个数不会很多,就可以做出来辣

不过写了一发好像过不了。。这是因为图中有一些孤立的点($>50$的质数),把它们单独拎出来就好,剩下90个点的独立集个数就真的不多了,搜索一遍大概2s的样子

用$h_{i,j}$表示$M=j$的时候选$i$个不同的数(组成集合,不是排成数组)的方案数,且每一个数都不能是$>50$的质数。这个直接搜吧

然后用$f_{i,j}$表示$M=j$的时候选$i$个不同的数的方案数,可以选$>50$的质数。枚举选几个这种质数,设为$K$个,那么就有

$$f_{i,j}=\sum_{K=0}^{\min(f(j),i)}\binom{f(j)}{K}h_{i-K,j}$$

其中$f(j)$是$51\sim j$内的质数个数。那么一次搜索就可以干掉所有$f$值。

然后要计算答案的话就是

$$\sum_{t=0}^N\binom{N}{t}f_{N-t,M}(N-t)!$$

这题通过人数居然只有CHEFMATH的一半。。窝不服

CHBLLS

455 vs 112

天平返回-2,-1,0,1,2分别表示1,2,3,4,5,一次出答案→_→

就酱

CHEFNUM

这个题代码长度限制50000B简直就是福利啊 本题解结束

呃还是写一些正常的东西吧,考虑求$f(l)+f(l+1)+\dots+f(r)$。分段打表,求出$f(1)+\dots+f(s),f(s+1)+\dots+f(2s),f(2s+1)+\dots+f(3s)$,直到$f(10^9)$为止(这个可以花很长时间打表),然后得到$10^9/s$个数打进源程序里面。这样对于一次询问我们只需要求不超过$s$个数的$f$值就好。我取$s=250000$效果不错,只打了40K,官方数据0.3s一个点(10 querys)。

DISTNUM2

AFO多年已经不会写主席树辣

考虑$L_i$为最大的$j$使得$A_j=A_i,j<i$。如果不存在那么就是$-1$。(在处理DISTNUM的时候我们就是这么玩的

问题变成$l\le i\le r,L_i<l$的数中第$k$大。平面上$N$个点,每个点有一个权值,每次在线询问求矩形中第$k$大的点。k-d tree套主席树。时间复杂度$O(Q\sqrt{n}\log n)$,空间复杂度$O(n\log^2 n)$。

常数优化:

  • 离散化,主席树深度能小就小
  • 在询问的时候一些节点已经是$0$了就不要管了。

STARROAD

出题人语死早辣

问题应该是这样的:$f_{i,j}$为原图中点$i$与点$j$之间长度$\le K$的不一定简单的路径条数,构造一个新图,$i,j$之间有$f_{i,j}\bmod X$条边,求新图的生成树个数,需要高精度。

矩乘求$f$,基尔霍夫矩阵求生成树个数。答案上界约为$10^{878}$。取$Q=100$个$10^9$级别质数然后crt。

crt这么玩:设模数是$p_1,p_2,\dots,p_{100}$,其乘积为$P$,答案为$a_1,a_2,\dots,a_{100}$,找出$q_i$使得$q_i\equiv 1 \pmod p_i$,$q_i\equiv 0\pmod p_j(j\ne i)$,求$\sum q_ia_i\bmod P$即可。如何求$q_i$呢?令$P_i=\frac{P}{p_i}$,其实$q_i$就是$P_i$在模$p_i$意义下的逆元,再乘以$P_i$。记$r_i$为$P_i$在模$p_i$意义下的逆元。要求$\sum q_ia_i$即求$\sum P_ia_ir_i\bmod P=(\sum P_i\times (a_ir_i\bmod p_i))\bmod P$。如果要求高除高的余数。。因为商不超过$100$,所以暴力就好了。。

需要用到高*低,高/低,高+高,高-高。

复杂度:矩乘$O(N^3\log K)$,基尔霍夫矩阵$O(100N^3)$,高精度合答案$O(1000\times 100)$。好像可以过的样子,最终3s+过辣。

SHOP2

真的没兴趣做cha题

CHEFMATH

一觉醒来(5月16日早上)快400人过了这个题。。好方

吓得我赶紧去补了一发

总共$43$个斐波那契数。考虑meet-in-the-middle,搜出所有$6$个斐波那契数加起来的方案,一共有$\binom{48}{6}$种,存起来。然后对于一次询问搜索最小的$4$个数是哪些,一共$\binom{46}{4}$种。需要用到“所有数都大于$f(x)$的选择方案中,恰好凑出$y$的方案数”。

复杂度$\binom{48}{6}+\binom{46}{4}Q$,可能多一些log。卡卡常就不小心过了。

 

nonsense

5月22日晚上。。Space Colony又要翻新了。。一首歌唱三遍也是厉害

不过话说组织最近很勤快啊


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter