10
13
2014
1

【跟风向】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: 4160
Avatar_small
pavzi.com said:
Mon, 08 Jan 2024 18:07:10 +0800

Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.


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