BZOJ 泛做 #1 (Updating)
NOIp前的BZOJ泛做

9月刷题记录

RXDoi posted @ 2015年9月08日 22:17 in BZOJ , 163 阅读

8月浪了一个月,滚回了普及组水平(从来都是这水平)

新学期开始了,班主任要求好好上课做作业,野花经常性煽动不做作业不听课……T_T

求每天有点输出……

[Upd 10.1] 9月结束了,居然只做了这么点题……实在是浪……

Counter:30

9.29~9.30:

CC:XRQRS:在后面加数删数,求区间k大、区间与x最大异或。函数式Trie、函数式线段树。

CC:SEAARC:n个点,相同颜色之间连弧,问不同色弧相交了多少次。花式问题转化,花式前缀和。


9.23~9.28:

怎么突然过了这么多天……意识模糊。

CC:RIN:每门课要选一个时间上,课程之间有拓扑关系,每门课每个时间有个价值,要价值最大。最小割。

CC:CHEFBOOK:一个矩阵,可以把每行所有非空的数+Pi,每列非空的数-Qi。要求后来每个非空格子的权值都在Sij~Tij的范围内。并且要所有权值和最大。有点神奇巧妙的线性规划。

BZOJ:4245:[ONTAK2015] OR-XOR:把一个序列分成m段,使每段xor的or值最小。作出前缀异或和然后从高位往低位贪心。一位是0的条件是包括An在内有m个数这位是0.然后把不能选的数去掉就行了。

BZOJ:1061:[NOI2008] 志愿者招募:每个变量只在两个限制中出现且系数是正负1的线性规划问题,加上Δ差分后费用流跑一下就行了。队列开小调了一下午。excited。

BZOJ:4260:Codechef REBXOR:n个数,选两段不相交区间xor之和最大。从前从后各做一遍Trie就行了。

BZOJ:4151:[AMPPZ2014] The Cave:一棵树,找到一个点x,满足所有形如Dis(x,Ai)+Dis(x,Bi)<=Di的限制。有点厉害的题。假设1号点满足条件就输出1号点,否则不满足了一个限制肯定要往它们LCA的方向爬到深度>=a为止。所有的限制要取个交集。那么直接找到限制深度最大的那条限制的最浅点,检查是否满足所有限制就行了。

BZOJ:4149:[AMPPZ2014] Global Warming:要求一个最长的区间使得它最大值唯一,最小值也唯一。维护出每个点为最小最大值的区间,枚举每个点作为最小值,线段树查找点在左边,最大值尽量靠右或点在右边最大值尽量靠左。


9.20~9.22:

CC:FNCS:有一个数列,有一些函数是求区间和的。要支持数列中单点修改,查询一段连续的函数的和。比较无脑的分块。块内标记,块外暴力。块开成 \( \sqrt{ \frac{n}{log n} } \) 最合适但是空间有点不够。好在不卡常数。WA1个点是因为要开unsigned long long。

CC:DISTNUM:感人肺腑。在哲大爷的教导下爆过了这道题……插入、删除、修改,查询区间内不同的数的0、1、2、3次方和。用Splay维护出最终的序列,然后每个点记一下前驱,查询的时候树套树就行了。轻松写上6k+,还卡了半天的常数。要把外层的线段树换成BIT,查询不经过的BIT结点就不要修改……从昨天中午开始搞到今天中午……


9.17~9.18:

16号整天无自修课,中午做初赛,晚上做作业到半夜T_T……17~18主要在打Gym。

CF Gym:[ASC34] H:Peaks:省选讲课题。我看了一中午的题解没看懂暴力,问灿爷才明白……求n个数的排列,“峰”的个数为k的方案数,%239。f[i][j]=f[i-1][j]*2j+f[i-1][j-1]*(i-2(j-1))。其实就是考虑最大的那个放在哪里。放在原先的峰旁边峰数不变,否则+1。然后n很大k很小,可以矩乘,转移矩阵和i有关,由于模数小,就可以搞出239个转移矩阵,合起来转移,剩下的再暴力乘上去就行了。

[某3星Gym] ABDFGKL。。

BZOJ:3551:[ONTAK2010] Peaks加强版:学了Kruskal重构树,就是做Kruskal的时候把边新建成点连边过去。这样有几个比较好的性质:是个大根堆;点数是O(n);原图中两点路径上最大边权就是新图中两点LCA的权值。那么询问就是倍增下祖先,查询子树K小。


9.15:

BZOJ:1206:[HNOI2005] 虚拟内存:用堆维护一下,取最小值的时候更新Lazy直到Lazy为空。

BZOJ:1224:[HNOI2002] 彩票:不要想太多太复杂的剪枝,用小数表示加上上下界剪枝就行了。一开始整数表示分母大力gcd结果T了……


9.14:

英语单元考失意地滚粗了。只能靠刷点水寻找慰藉了。求每天过题量英姿。

BZOJ:1014:[JSOI2008] 火星人:Splay维护Hash值,二分+Hash。

BZOJ:1294:[SCOI2009] 围豆豆:射线法判点在多边形内。经过横向直线不算,上闭下开就能搞好边界了。BFS之。

BZOJ:1217:[HNOI2003] 消防局的设立:f[x][i]表示x的子树最近的消防局距离为i。i≤5.DP。

BZOJ:1299:[LLH邀请赛] 巧克力棒:先手取出一个Nim游戏的必败态,即极多的数异或起来=0.后手不管怎么搞都是一个Nim必胜态。

刷的题实在太水有点不好意思……


9.9~9.12:

BZOJ:3589:动态树:子树加,求5条链的并的和,容斥下,考虑维护每个点到根的和。两个BIT维护下就行了。

BZOJ:3276:磁力:把点按照距离排序,线段树维护重量最小值就行了。

CF:145C:对于非Lucky number直接算,Lucky number暴力背包即可。

CF:356E:大大大大大大大暴力。暴力枚举每个点修改成什么,减去原先的贡献,然后去暴力DFS加上新的贡献就行了。约束有点多所以效率还不错。考虑一个Lucky string,假如当前修改的字符可以影响到它,一定是修改的字符为中心的一个Lucky string是其子串。往两边不停拓展就行啦。代码实现挺有技巧性的。做完这种题总感觉“写出标程的人和出题人是一伙的”。


Before 9.8:

BZOJ:1533:[POI2005] Lot-A Journey to Mars:A的前缀和的每个值都不小于B的前缀和对应值即可,CF上有类似的题,当时我好像是线段树维护A-B的最小值什么的,其实单调队列就行了。

BZOJ:1113:[POI2008] 海报:单调栈。两边低中间高答案就能-1.

BZOJ:2648:SJY摆棋子/2716:[Violet 3] 天使玩偶/3053:The Closest M Points:KD-Tree模板

BZOJ:2762:[JLOI2011] 不等式组:BIT。边界搞搞。


登录 *


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