Memphis's Blog

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