好久没炖题了。。上一次愉快的没有全部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]好方的蛇】
枚举分界线,然后减去重复计算的部分。
2015年4月17日 18:15
mlgb你们都欺负我!
2015年4月17日 22:57
@fullpower: 然而气势还不够。。