4
8
2015
1

【除草】BZOJ泛做②

刷题速度奇慢无比


upd 4.8

2320: 最多重复子串:后缀数组好题,详见Seter题解,把hash+二分改成SA。。跑得没hash快。。

3922: Karin的弹幕:考虑分块,公差大于S暴力,小于S分块,信息记在起始端,[tex]a_{i,j,k}[/tex]表示第i个节点开始公差给j的序列第k项是什么,考虑空间可能不够,对k再分块,复杂度依然是不变的,对k分块的每块可以用个堆,然而我用了set,复杂度是[tex]O(n\sqrt{n\log n})[/tex]

2176: Strange string:最小表示法,感性地理解一下还是挺水的。

2662: [BeiJing wc2012]冻结:分层图最短路

2882: 工艺:最小表示法

3037: 创世纪:环套外向树DP

3926: [Zjoi20150]诸神眷顾的幻想乡:SAM裸题啊啊啊啊。。。说好的不考SAM呢。。T T。。。

3925: [Zjoi20150]地震后的幻想乡:解法多样。。标算多项式啦。。其实转化为计数问题更好一点,假设我们在做kruskal,[tex]f_{S,j}[/tex]表示点集为S时仅用前j小的边就使S的联通的方案数,转移枚举从小到大点集,枚举子集和补集,找出子集和补集之间的边,枚举子集用了u条边,补集用了v条边,加上之间的一条边转移到[tex]f_{S,u+v+1}[/tex],然后考虑一些不是用来构成mst的边,之后做个背包就可以了,设全集为U,总边数m,最后[tex]f_{U,i}-f_{U,i-1}*(m-i+1)[/tex]就代表以第i小的边为mst中最大边的方案数,计算贡献即可。复杂度[tex]O(3^nm^2)[/tex]

3913: Jabby's newwork:cc原题?23333,有点神的,爆推

3931: [CQOI2015]网络吞吐量:倒着跑一边最短路,对最短路径图建反向边并拆点,跑最大流

3932: [CQOI2015]任务查询系统:函数式线段树

3930: [CQOI2015]选数:容斥递推,先把L,H都除K,[tex]f_i[/tex]表示GCD恰为i的方案数,先统计为i的倍数的方案数,那就是[tex](\lfloor\frac{H}{i}\rfloor -\lfloor \frac{L-1}{i}\rfloor)^n-(\lfloor\frac{H}{i}\rfloor -\lfloor\frac{L-1}{i}\rfloor)[/tex],然后减去[tex]\sum_{i=2}^{i*k<=H-L+1}{f_{i*k}}[/tex],最后特判L=1的情况,全选K也是可行的,答案+1

2144: 跳跳棋:HZWER的题解很详细。。中间可以往外跳,两个儿子,外面只有一个能往里跳,一个父亲,我们发现往里跳的过程类似辗转相除法,终态是固定的,然后我们判一下两个状态的终态是否相等,不等就是无解,否则即为寻找LCA求最短路径,倍增。两个log。

2555: SubString:SAM套LCT,即加入一个字符后对fail的所有节点贡献+1,暴力能过。。

3924: [Zjoi2015]幻想乡战略游戏:考场上的做法。。3个log,点分+点分+树剖

3938: Robot:lc线段树大法好!线段树维护折线。

3862: Little Devil I:LCT。。挺无脑的。。第一个操作直接做,第二个操作只需要在链上打个标记,access拼接和断开的时候翻转儿子就可以了。说到这里我再来宣传一下3914: Jabby's shadows,大水题。


upd 4.9

3868: The only survival/3864: Hero meet devil/3905: Square:详见陈老师WC课件


upd 4.10

3840: ZCC Loves COT:把xOy,yOz的平分平面和xOy平面以及垂直于xOz平面且垂直于x轴于(n,0,0)点处的平面交出来一个正四面体,脑补一下大概是这样的

然后按照x轴分开看,每块是一个直角三角形,对于每个更改每块打个标记,做几次前缀和就好辣,复杂度nq

3939: [Usaco2015 Feb]Cow Hopscotch:线段树动态开点。。

3943: [Usaco2015 Feb]SuperBull:最小生成树

3940: [Usaco2015 Feb]Censoring:AC自动机?。trie图,新姿势get

3942: [Usaco2015 Feb]Censoring:KMP。直接贴上一份代码了

3846: ZCC loves words:trie图建出来就可以搞出dp方程,搞成矩阵快速幂,由于有位置影响,模数是三个很小的模数乘起来,每个小模数可能的矩阵只有P个,爆搞搞出来中国剩余定理合并。


upd 4.11

1129: [POI2008]Per:先考虑模数为质数的情况,考虑从后往前放,每次放一个元素在bit里面维护前缀和,用排列的式子就是[tex]\frac{tot!}{\prod{C_i!}}[/tex]其中[tex]C_i[/tex]表示每同种元素的个数,[tex]\sum{C_i}=tot[/tex],每次维护插入一遍总的答案,求比原排列小的就是在bit里拿出这一位比原排列小的个数乘上维护的答案/tot,相当于把这一位定住的贡献。以上都是比较容易想到的,然后比较恶心的是模数非质数,其实用很老套的方法就可以了,把模数拆分,struct重定义int,把int都里拥有模数的质因数都提出来存着,每个struct存log个变量和一个和模数互质的元素,然后除法乘法都可以在log的时间内完成,bit里还是维护原来的int,因为只涉及最后乘一下,复杂度依旧是[tex]O(n\log n)[/tex]

upd 4.13:后来发现乘的时候还有快速幂囧。。复杂度是[tex]O(n\log^2 n)[/tex]

1517: [POI2006]Met:好题啊。。首先可以证明答案一定是一棵树,并且可以证明答案一定包含某条直径,于是找出直径的一个端点往下贪心找2*K-1条链,每次找到一条最长的删掉。这样爆搞是[tex]O(n\log n)[/tex],可以过了。同样的思路,比较厉害的一种想法把这棵以直径的一个端点为根的树按照深度树剖,把每个叶子表示为向上的延伸的最长长度,把叶子基数排序一下取前2*K-1个即可,这样就是[tex]O(n)[/tex]。还有一种更厉害的想法,丢掉上面所有想法,不设根,从叶子开始,每次把树最外一层叶子剥掉,记录数量,和2*K取min加入答案即可。以上三种做法,前两种证明比较显然,最后一种比较意识流,表示不会证。

upd 4.15:窝来口胡一下最后一种做法的证明(真的完完全全是口胡),首先k条路径肯定都是从叶子开始,叶子结束,我们剥掉了一层叶子,这层叶子中可以乱选2*K个,都可以和剥掉后的树构成一个解,然后剥掉后的树成为了一个子问题,所以是可行解,同时对于每层叶子我们最多只能选2*K个,也是最优解。

3843: ZCC loves Army:LCT套splay维护儿子就可以了,这是强行cosplay Toptree还是闹哪样。BZOJ上数据错的,标程没有判一个点是另外一个点祖先的情况。HUD上交了下过样例1A了。。这不科学。。


upd 4.12

好颓啊。。。。然而我还在计数问题的汪洋中挣扎。。。随便切道题签到一下吧。

3956: Count:正反用单调队列建两棵主席树就好辣


upd 4.14

3962: [WF2011]Coffee Central:可以直接维护那个菱形。。然而我转了一下坐标,维护正方形就方便许多了(可转坐标不方便啊

3953: [WF2013]Self-Assembly:26*2个节点,一个节点向同块另一类节点的配对节点连单向边,表示可以走出去,然后传递闭包跑一下有环就是unbounded

3972: [WF2013]Pirate Chest:枚举上下界限,左右用单调队列找出左右界限,然后就是[tex]O(n^3)[/tex],要卡常数

3969: [WF2013]Low Power:排个序就可以二分贪心了,能放就放,不能放就塞到前面的机器人不用的电池去

3960: [WF2011]Ancient Messages:数联通块个数

3944: Sum:筛筛筛!网上有题解。有必要补到数论专题去?


upd 4.15

3983: [WF2012]Takeover Wars:显然只有最大的干掉另外一个最大的才有意义,但是也不一定是最优的,所以一方能保证合并第二大以后依然比另一方最大大或者最大的比另一方最大的小的话就合并,用个堆维护就好了。

1912: [Apio2010]patrol 巡逻:最长路+次长路

3136: [Baltic2013]brunhilda:应该不是标解把。。直接用筛法+堆跑一遍,复杂度是[tex]O(n\ln n \log n)[/tex],或者更小?因为不需要更新的时候可以跳着更新。。

3841: ZCC Loves Intersection:数学题。。

3844: ZCC loves cards:爆搜,然后用线性基判一些元素是否存在进行剪枝

3851: 2048:暴力+背包


upd 4.16

2749: [HAOI2012]外星人:奇数求phi一定是偶数,偶数除了2求phi还是偶数,如果一个数有一堆2的质因子,每次求phi只能删去一个,所以就是数每种质因子求phi分解出来的2的个数,预处理dp,然后如果初始为奇数特判+1

3971: [WF2013]Матрёшка:区间DP,[tex]f_{i,j}[/tex]表示区间[tex](i,j)[/tex]合并起来最少需要几次拆分,非法区间不用管,最后统计答案不会算进去,对于两个区间a,b合并,就是数一数a区间比b区间最小值大的有几个,b区间比a区间最小值大的有几个,这个可以预处理,最后再做个dp把合法区间的状态转移一下即可。

2141: 排队:归并排序求出初始解,然后每次操作都可以[tex]O(n)[/tex]维护

3979: [WF2012]infiltration:因为是完全图,答案不会很大,直接爆搜,剪枝加几个就可以了。


 

Category: BZOJ | Tags: Problem sets | Read Count: 3731
Avatar_small
icerupt said:
Wed, 07 Oct 2015 10:56:26 +0800

您好,可不可以看一下您3922是怎么用set做的,不是很理解,看了王悦同的论文只想到了用线段树的做法。谢谢。我的邮箱是icerupt@126.com


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com