10
13
2014
0

【跟风向】NOIP2014前的Codeforces刷水记录

sone:“你还在刷BZOJ?快来刷CF,BZOJ那些xx题。”

gy偶回机房:“你还在刷BZOJ?最近他们不都刷CF了么。”

wwt:“每天一场vp div1,不进前20简直弱爆。”

想想也是,BZOJ除了波兰人系列之外数据结构题越来越多了。。。NOIP前还是做点正常题比较好。


先乱入一题BZOJ题。

3739: DZY loves math VIII:由于常数卡了好久不写题解不开心。QAQ

先说一句,这题的T这么小是迷(dou)惑(ni)你(wan)的。。

[tex] \sum_{i=1}^{n}{\sum_{j=1}^{i}{\mu(lcm(i,j)^{gcd(i,j)})}}[/tex]

[tex]= \sum_{i=1}^{n}{\sum_{j=1}^{i}{\mu((\frac{ij}{gcd(i,j)})^{gcd(i,j)})}}[/tex]

根据[tex]\mu(x)[/tex]的定义,可知[tex]gcd(i,j)>1[/tex]时对答案无贡献,故

[tex] =\sum_{i=1}^{n}{\sum_{j=1}^{i}{\mu(ij)}}[/tex]

[tex] =\sum_{i=1}^{n}{\sum_{j=1}^{i}{\mu(i)\mu(j)e(gcd(i,j))}}[/tex]

[tex] =\sum_{i=1}^{n}{\sum_{j=1}^{i}{\mu(i)\mu(j)\sum_{d|gcd(i,j)}{\mu(d)}}}[/tex]

[tex] =\sum_{i=1}^{n}{\mu(i)\sum_{j=1}^{i}{\mu(j)\sum_{d|gcd(i,j)}{\mu(d)}}}[/tex]

[tex] =\sum_{i=1}^{n}{\mu(i)\sum_{d|i}{\mu(d)\sum_{j=1}^{\frac{i}{d}}{\mu(jd)}}}[/tex]

[tex] g(n)=\sum_{d|n}{\mu(d)\sum_{j=1}^{\frac{n}{d}}{\mu(jd)}}[/tex]

如果我们可以快速求出所有[tex]g(n)[/tex],就可以计算出所有答案,所我们探寻[tex]g(n)[/tex]的性质。

我们发现直接求约数是很不靠谱的,我们探寻每个约数对答案的贡献,发现[tex]d~to~\lfloor\frac{n}{d}\rfloor d[/tex]枚举约数倍数的时候,对于一个[tex]jd[/tex],会对[tex]jd~to~\lfloor\frac{n}{d}\rfloor d[/tex]都产生一个[tex]\mu(jd)[/tex]的影响,所以一个算法就显而易见了,枚举约数做筛法,统计前缀和计入[tex]g(n)[/tex],由于答案最外面还有前缀和,再做一层前缀和就好了。

现在的复杂度是[tex]O(nlnn+T)[/tex]

这个做法我第一次交的时候过了,然后jry大大把我卡掉了,原因是非标算。。

尝试优化。

我们发现[tex]\mu(n)[/tex]是有很多零的,到底有多少呢,jry大大给出了一个渐进值:

[tex]\sum_{i=1}^{n}{\mu(i)^2}=\frac{6n}{\pi^2}+O(\sqrt{n})}[/tex]

乘上去的话大概就是一个[tex]\frac{2}{3}[/tex]的常数,回过头来看上面那个式子:

[tex] \sum_{i=1}^{n}{\mu(i)\sum_{d|i}{\mu(d)\sum_{j=1}^{\frac{i}{d}}{\mu(jd)}}}[/tex]

显然[tex]\mu(d)=0[/tex]的时候无需统计,[tex]\mu(j)=0[/tex]同理,这样我们预处理不等于零的[tex]\mu(n)[/tex]有多少存在一个数组里,之后直接调用,复杂度就小了很多。

但是还是过不了T_T,然后就是卡常数时间,卡着卡着就过了QAQ。

至于标算是啥。。留给jry大大自己讲吧,我没怎么看懂所以就不口胡大家了囧。。看上去很厉害的样子


478D Red-Green Towers:最优情况是

[tex]\frac{h(h+1)}{2}=r+g[/tex]

所以很显然[tex]h<=\sqrt{2r+2g}+1[/tex],直接dp

476E Dreamoon and Strings:DP

476D Dreamoon and Sets:事实证明想太多就是作死。因为最优解是奇数全取,构造一下就发现每6个可以取4个。

475D CGCDSSQ:显然不会太多gcd不同的值,枚举i二分j就可以了。

479D Long Jumps:特判一下1的情况。

479E Riding in a Lift:DP

111D Petya and Coloring:求出每种颜色的方案数,组合数搞搞就好了。

480E Parking Lot:倒着做,每次删除一个点,然后向四周拓展更新答案。

480D Parcels:排个序DP,[tex]f_{i,j}[/tex]表示当前为在做第[tex]i[/tex]个物品载重为[tex]j[/tex]的答案。

331E1 Deja Vu:一个合法路径一定有一条边包含u或者v,找出这样的边向两边拓展。

477D Dreamoon and Binary:有个很显然的[tex]O(n^3)[/tex]DP我就不说了,考虑优化,预处理lcp,然后比较大小就可以[tex]O(1)[/tex]了。

331C123 The Great Julya Calendar:记忆化搜索DP。[tex]f_{i,j}[/tex]表示要处理[tex]j[/tex],之前最大值为[tex]i[/tex]的值。

425C Sereja and Two Sequences:这场CF也是醉了,各种条件限制导致暴力复杂度有保证。。由于答案最多只有[tex]s/e[/tex],所以直接DP。

425D Sereja and Squares:同样暴力也是有复杂度保证的。。统计出每个点向上向左的点,然后枚举点再枚举边并判断是否合法,因为最坏情况是所有点构成一个正方形,复杂度最坏还是[tex]O(n\sqrt{n})[/tex],map会T,用hash就好了。

425E Sereja and Sets:DP,[tex]f_{i,j}[/tex]表示做到第[tex]i[/tex]位,最多不相交子集为[tex]j[/tex]的方案数,转移枚举上个位置进行转移。

414D Mashmokh and Water Tanks:先吐槽一下题面,开vp的时候英语弱愣是看不懂。题解:当然选择一波带走,所以我们一定是选择在深度的一段区间里放水,枚举右端点,左端点具有单调性,然后就好了。

100222J Truth:[tex]O(n^3)[/tex]无脑DP

100222G Refrain:后缀数组悬线法求最大矩形。

100222C Decoding Martian Messages:[tex]O(d^2k)[/tex]预处理两两可以转移的集合串,然后[tex]O(nd^2)[/tex]的DP,由于会爆精度所以要取log乘法转加法。

100340G Hungry Queen:每层之间横向转移,上下之间转移用map。ps:输出方案特别胖QAQ。

100340J New Year Tree Transportation:又见树形贪心。。如果没超过K就返回上一层,否则切掉大的子树,如果还是大于K就切掉另外一个子树,因为是二叉树可以证明这是对的。

100340I Longest Common Subpair:无脑签到题。

403C Strictly Positive Matrix:只有当整张图构成一个环的时候才会是YES,直接tarjan好了。

100243A Circular Roads:三分套三分能过?我只能默认题目给出的条件是两个圆不相交了。。所以说英语好是多么必要。。

100243I Black and White Segments:线段树hash。。。

100247G City Square:基础方块(平移之前由不同颜色组成的方块)一定是一个大正方形拼小正方形(小正方形边长可为0),所以判断是否是勾股数。

100247H Secret Information:任何看起来比较炫酷的操作都可以被朴素的操作完艹。。所以直接贪心就好了。。

65D Harry Potter and the Sorting Hat:可以证明状态数最多只有13,直接DP。

74C Chessboard Billiard:可以证明长边所有点射出去能射就射一定是最优的,所以记录一下每条斜线是否被射过了就好了。


loading

Category: Codeforces | Tags: codeforces Problem sets | Read Count: 4077

Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com