是时候炖一波BZOJ了[完结]

好久没炖题了。。上一次愉快的没有全部AC。。果然一定要先用小号交一遍才保险。。（目测进度会很慢。。

[UPD 4.11]赛程过半

[UPD 4.16]完结撒花！

[UPD 4.17]终于成功地在不手贱的情况下交完了！~

现在几题了？

50/50

//以下是正文

【3812: 主旋律】

膜陈老师。。基本是对着题解和AC程序码的。。实在太神。。

【3622: 已经没有什么好害怕的了】

$f(n,k)$表示前$n$个，至少有$k$个满足前者大于后者。然后用$g(n,k)$表示恰好$k$个满足。容斥一下即可。

【2823: [AHOI2012]信号塔】

随意切水。裸的最小圆覆盖。

【3967: [WF2013]Factors】

把$k$质因数分解之后，$f(k)$一定是和质因子幂次有关的一堆组合数的乘积。然后爆搜幂次即可。

【3969: [WF2013]Low Power】

从小到大排序后二分答案，能放的就放，不放的往前面的空位里放。

【3962: [WF2011]Coffee Central】

坐标转化一下，变成维护正方形内的点数和就好了。

【2764: [JLOI2011]基因补全】

随便切了道水，好像就是个高精度。

【3861: Tree】

把每个集合看成左边的点。右边一排$n$个点。左边的点能往不属于这个集合的点连边。然后询问的是左边的点都匹配上的方案数。用$f_{i,j}$表示前$i$个集合，已经匹配好$j$个的方案数。转移的时候，只要枚举当前选 集合中的多少个点，然后和 之前未匹配上的集合 连边即可。

【3990~3995】戳这里

【3868: The only survival】

枚举每个点的距离编号->枚举每种距离编号有几个。然后dp一次是$O(n^2)$。

【2751: [HAOI2012]容易题(easy)】

显然答案是每一位能取的数之和的乘积。那么排序扫一遍就没了。

【2749: [HAOI2012]外星人】

因为一个$p^a$取$\phi$后变成了$(p-1)p^{a-1}$，然后$p-1$继续分解质因数下去。最后得到的是一坨2。

所以只要处理每个质因子能分解出多少2了。显然对于奇数$n$有$f(n)=f(\phi(n))$，偶数$n$有$f(n)=f(n/2)+1$。

如果最后的$n$是奇数还得先加一，因为一开始没有2。

【3512: DZY Loves Math IV】

考虑如何计算$S(n,m)=\sum_{i=1}^{m}\phi(ni)$。

对于Square-Free数$n$，有$\phi(ni)=\phi(n)\sum_{k|(n,i)}\phi(n/k)$。把它带入到上式，化简可以得到$S(n,m)=\sum_{d|n}\phi(n/d)S(d,m/d)$。

那么对于$\mu(n)=0$的$n$，我们找到一个最大的$k\leq n,k|n,|\mu(k)|=1$，得到$S(n,m)=nS(k,m)/k$。

最后要做的是求$\phi$的前缀和。用$O(n^{2/3})$即可。

【1179: [Apio2009]Atm】

跑一遍tarjan，然后在DAG上dp一下即可。

【3931: [CQOI2015]网络吞吐量】

为了做出一副完整的把CQOI15做完的样子。把这题写了一下。把最短路和网络流一起考很有意思？。。

【3956: Count】

作为一个逗比把$\forall$看成$\exists$的我需要去冷静一下。之后就会发现这玩意儿的个数是$O(n)$了。最后用个主席树啥的在线询问一下即可。

【3944: Sum】

考虑到对于积性函数$g$和$f$，有$g(n)=\sum_{d|n}f(d)$。经过推倒可以得到$G(n)=\sum_{i=1}^{n}F(\lfloor \frac{n}{i} \rfloor)$。其中$G$和$F$是对应的函数的前缀和。关注到$\phi$对应的$g(n)=n$，$\mu$对应的$g(n)=[n==1]$。然后预处理小范围的值，大的记忆化，可以得到$O(n^{2/3})$的复杂度。

【3943: [Usaco2015 Feb]SuperBull】

其实就是求了个最大生成树，prim搞搞。

【3942: [Usaco2015 Feb]Censoring】

应该是直接KMP然后在上面走的。方便起见我就把gold的AC自动机的代码粘过来了。

【3929: [Seerc2014]Circle of digits】

显然答案的位数是固定的，一定是$\lfloor n/k \rfloor$。那就可以把所有长度为这个的子串拎出来排序。在上面二分答案。判定的时候，只用从最前面的$\lfloor n/k \rfloor$开始往后走，每个都走$k$步，检查答案是否合法。那么复杂度就是$O(n\log n)$了。听说有点卡常数，其实可以不用把串复制一遍，可以只加上前$\lfloor n/k \rfloor$个字符，会快很多233

【3916: [Baltic2014]friends】

直接上哈希。

【3917: [Baltic2014]sequence】

枚举最后一位的数字，然后规模缩减成原来的1/10。注意如果强制要前导零需要在前面加一。

【3862: Little Devil I】

树链剖分。一颗线段树维护重链的翻转情况。另一颗线段树维护每个点连出去的轻边的翻转情况即可。

【1068: [SCOI2007]压缩】

暴力记忆化区间dp。

【2817: [ZJOI2012]波浪】

$f[i][j][k][s]$表示当前要插第$i$个数，已经形成了$j$段，贡献和为$k$，两端的情况为$s$的方案数。然后大力dp。

【3939: [Usaco2015 Feb]Cow Hopscotch】

开一维线段树dp即可。

【3940: [Usaco2015 Feb]Censoring】

把ac自动机建出来，然后在上面走一遍。

【1880: [Sdoi2009]Elaxia的路线】

先把最短路图建出来，然后在上面找最长链。

【1879: [Sdoi2009]Bill的挑战】

压匹配状态即可。

【3870: Our happy ending】

把能拼成的数压位即可。感觉很暴力但是状态好像不大多？。。

【3934: [CQOI2015]标识设计】

用$f[d][i][j][k]$来表示第$d$列时，三个L的状态为$(i,j,k)$时的方案数。状态有三种：①$i=0$ 表示还没有开启 ②$1\leq i \leq n$ 表示已经开启了L（L的横条长度大于等于2），现在L的下端正占据着第$i$行 ③$i=n+1$ 表示L已经关闭。那答案自然就是$\sum f[d][n+1][n+1][n+1]$。dp的时候为了方便，我们可以把每一位能转移的状态都列出来，然后暴力判是否合法即可。时间复杂度是$\text{O}(n^5)$的。

【3933: [CQOI2015]多项式】

把$x$用$x+t$代进去得到关于$b_m$的式子。python大法好！

【3900: 交换茸角】

用集合dp。

每个状态只可能从两个子集合并得来。不然就自身通过 个数-1 次操作交换完成。

【3294: [Cqoi2011]放棋子】

跑两边dp。第一遍记录恰好占据$i$行$j$列的方案数。第二遍把第一遍的结果合并起来。

【3532: [Sdoi2014]Lis】

学习了一下退流的姿势。就是对于$u\rightarrow v$这条边，从$T$到$v$跑一遍流，从$u$到$S$跑一遍流即可。

【2306: [Ctsc2011]幸福路径】

注意到答案一定是一条链+一个环。那就可以$O(n^2m)$处理出$f[d][i][j]$，表示$i\rightarrow j$长度为$d$的方案数。环的话用等比数列求和即可。

【3902: 三向投影】

tc的原题咯。两个数组都排好序，然后$(i,j)$的取值最大是$\min(a_i,b_j)$。取值相同的合并在一起算。我是暴力容斥的TAT，跑的好慢。

【3620: 似乎在梦中见过的样子】

无聊的KMP裸题。$O(n^2)$暴力即可。

【3930: [CQOI2015]选数】

先除以k，然后用$\sum_{d}\mu(d)(\frac{r}{d}-\frac{l-1}{d})^n$奇怪的混过去了。

【3864: Hero meet devil】

压LCS的状态就可以dp了。复杂度$O(2^n(n+m))$

【3213: [Zjoi2013]抛硬币】

先用KMP把每个位置的两个转移都求出来。然后令$f(i)$为从第$i$个节点出发的期望次数。那么有$f(i)=p(0) f(trans(i,0))+p(1) f(trans(i,1))+1$。因为其中有一个一定是$i+1$，那么就有$f(i+1)=\frac{f(i)-p(1-t)f(trans(i,1-t))}{p(t)}$。这就可以递推了。

【3926: [Zjoi2015] 诸神眷顾的幻想乡】

考场上没看出叶子唉。把每个叶子当成根BFS一遍，然后把这棵树插进SAM即可。

【3928: [Cerc2014] Outer space invaders】

抽象成一条条线段，从低到高做，简单的$O(n^3)$区间dp。

【3235: [Ahoi2013]好方的蛇】

枚举分界线，然后减去重复计算的部分。

• 相关文章