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

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

好久没炖题了。。上一次愉快的没有全部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: 然而气势还不够。。

Avatar_small
AP SSC fa 2 Question 说:
2022年9月09日 20:38

Formative Assessment means not only an examination, it includes various aspects such as Examination in completed lessons, Reflections, Project work done on the allotted topic and Self also Prepared notes etc. AP SSC fa 2 Question Paper Candidates of Telugu Medium, English Medium & Urdu Medium of the AP State can download the AP 10th Class FA 4 Model Paper 2023 Pdf with answers for the regular exams conducted by the Directorate of Government Examinations, Andhra Pradesh.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter