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

dzy posted @ 2015年4月04日 23:52 in 专题 with tags bzoj , 2687 阅读

好久没炖题了。。上一次愉快的没有全部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)}$。这就可以递推了。


【3932: [CQOI2015]任务查询系统】

抄多校题哎。扫描线从左到右建主席树。查询的时候在树上二分即可。


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

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


【3928: [Cerc2014] Outer space invaders】

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


【3235: [Ahoi2013]好方的蛇】

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


 

Avatar_small
fullpower 说:
2015年4月17日 18:15

mlgb你们都欺负我!

Avatar_small
dzy 说:
2015年4月17日 22:57

@fullpower: 然而气势还不够。。


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
dzy493941464
Music
搜索
计数器
120332

Copyright © 2007

Webdesign, tvorba www stránek

Valid XHTML 1.1