9月刷题记录
站在2015与2016的路口

NOIp前的BZOJ泛做

RXDoi posted @ 2015年10月18日 21:28 in BZOJ , 133 阅读

太弱了太弱了。

Upd 11.2.此坑暂停。


Upd 10.26:

昨天CF看题跑……BZOJ经过几周大力刷水终于刷上了600道。感人。

4034:[HAOI2005] T2:子树加路径求和。按深度算贡献。

3382:[USACO2004Open] 洞穴里的牛之三:SB题。

1493:[NOI2007] 项链工厂:注意到他旋转/翻转的操作都不影响珠子相对的位置关系。那么一棵线段树就行了。还是挺好写的。

3928/4048:[CERC2014] Outer Space invaders:感觉有点厉害的区间DP。f[i][j]表示把时间完全在这个区间内的外星人搞掉的代价。最大的那个肯定是要搞一次的,那么枚举最大的在哪里搞,转移即可。

4065:[CERC2012] Graphic Madness:有点厉害的题,递推,一个子树如果有2个叶子结点则必须从它绕过去并砍掉父边,否则就无解。然后搞完再DFS一遍输方案即可。关键是注意到树中每个点只有一个祖先的性质。

4291:[PA2015] Kiesonkowe:SB题。

4275:[ONTAK2015] Badania naukowe:设f[i][j]表示LCS,g[i][j]是反向的LCS,求出ai,bi表示从i开始匹配完C串要到哪里,Ans=max(Ans,f[i][j]+g[a[i]][b[i]]+c).

4298:[ONTAK2015] Bajtocja:启发式合并。大暴力。哈希。要写带内存回收的挂链Hash。真是没啥意思。


Upd 10.24:

做了一套Day1Day2模拟赛,Day1数组开小爆了10分,Day2自我感觉发挥不错了还是没能翻盘……感人肺腑。

3526:[POI2014] Card:比较巧妙的题。线段树维护:当这个区间最左边是Ai/Bi时右边最小的值。就没了。

4059:[CERC2012] Non-Boring sequences:比较巧妙的题。假如这个区间中有某个独一无二的数字,那么所有跨越它的区间都是不无聊的,可以分别做左右部分,否则整个区间就是无聊的。对于维护区间内出现1次的数字,标算是从两边往中间暴力找,据说复杂度是\(O(n log n)\)的。我感觉不是很资瓷,就写了更直观的扫描线线段树。

4060:[CERC2012] Word Equations:一开始我以为只是个字符串大模拟居然试图直接把整个字符串搞出来……出来……要维护第i个单词从P的j位开始匹配能匹配到的最远长度,然后就可以转移了。RE了一下午又是数组开小了……日……

3373:[USACO2004Mar] 说谎的牲畜:有向图DFS判环。

4064:[CERC2012] The Dragon and the Knights:不错的题。一个区域与所有直线的相对上下关系是确定的,因此区域可以用一个二进制串表示出来。由于每个点必定属于一个区域,只要统计点匹配了多少个区域即可。注意平行线。

4061:[CERC2012] Farm and Factory:不错的题。设f为第一次距离,g为第二次距离。设c为新加进去的点,根据三角形不等式以及不能改变最短路的限制可以得出\(E(c,u) \geq max{|g(u,1)-f(c,1)|,|g(u,2)-f(c,2)|}\)。而且似乎可以证明这个等号一定是取得到的。然后要求的东西可以用\(g(c,1)\)和\(g(c,2)\)表示出来(或者是我对g的定义理解错了?)。然后就是切比雪夫距离转曼哈顿距离求一下即可。卡SPFA。


Upd 10.22:

4293:[PA2015] Siano:不错的题,按生长速度排个序,草的高度就永远是不递减的了,线段树维护下就可以了。

4276: [ONTAK2015]Bajtman i Okrągły Robin:比较厉害的题,题目是和下一道一样的,但是区间范围小一点,可以线段树优化网络流连边。也可以用下面的方法做。

2034:[2009国家集训队] 最大收益:有个结论:每个区间都搞出一个>Si的第一个点,要互不相同,总共n个,成为活跃点,最终答案一定是在活跃点上取到。然后就可以贪心了。按权值从大到小排序,如果这个加进去能与前面的共存就加进去。判断一个集合的区间能否共存是按右端点排序,优先放右端点小的。那么每次O(n)扫一遍,类似匈牙利,把已经匹配的点尽量往后移就可以了。

3157/3516:国王奇遇记:设\(f(k)=\sum_1^n{i^k*m^i}\),用扰动法推推公式就好了,可以O(m^2)做。然而并不明白他是怎么想到设这个的。O(m)的暂时不会。

3155:Preprefix Sum:SB题。

4057:[CERC2012] Kingdoms:状压DP。

3115:[CERC2012] Chemist:记忆化搜索。

3169:[CERC2012] Conversation:拓扑排序,每次把同一颜色的全部搞掉就最优。


Upd 10.21:

3896:求和:孟爷的模拟赛出过加强版。幂和数列果断伯努利数,公式推推就好了。公式再推下去后面是个点积,翻转数组变成卷积,伯努利数用展开生成函数多项式求逆的求法,就可以O(n log n)了。只不过这题模数不资瓷。

4300:绝世好题:两个数and !=0的条件是至少有一位都为1.f[i]表示第i位为1的方案。DP就行了。

3070:[PA2011] Prime prime power 质数的质数次方:胖题。对3~61的每个指数维护一个堆,指数为2的暴力往下枚举,Miller-Rabin判素数即可。然后卡。常。数。40+个点,BZOJ总时限10s实在是有点紧……然后我加了各种特技,最后观察到数据在9.8e17以上耗时较大,就把这段每隔1000个k打一个表,前后1000个暴力做,中间直接一段段跳……交了39k的表终于贴着时限爆过去了……

4269:再见Xor:线性基。

打了人生中第一次TC,Div2,很快做完了,然后实力1000pts FST,一个j打成了i。比较伤心,就刷了一波水。

1726:[USACO2006Nov] 第二短路:SPFA。

1579:[USACO2009Feb] 道路升级:分层图SPFA。

1572:[USACO2009Open] 工作安排:堆。

1708:[USACO2007Oct] 奶牛的硬币:背包。

1106:[POI2007] 立方体大作战:按顺序做过去,维护一个栈,第二个进来了就暴力交换过去。

1102:[POI2007] 山峰和山谷:Floodfill。

1043:[HAOI2008] 下落的圆盘:n^2枚举,一个圆对另一个圆覆盖的贡献可以表示成一个圆心角区间,用余弦定理可以算出来。然后线段求并算下答案即可。


Upd 10.18:

最近NOIp模拟赛总是暴蛋……不是很难的题总是把问题复杂化,往错误的方向想很久。看来是题目做得太少……好长一段时间没有刷BZOJ了,刷题量还停留在几个月前的水平。值此联赛还有三周之际,是时候临时抱佛脚来一波了。

4152:[AMPPZ2014] The Captain:经典问题,按两维分别排序取相邻边跑即可。又T又WA居然是远古Dij模板写错了……

4242:水壶:比较好的题,要求路径上每一段的最大值最小。等价于先跑出建筑物之间的最短路MST然后查链上Max。建MST可以对每个点记录离他最近的建筑物,如果一条边两侧最近建筑物不同,这个值就可以作为这两个建筑物之间的一条边。由于是在最小生成树上找最大边,先加入的边是不影响答案的,那么合并并查集时可以把边连到祖先上面。这样就可以控制树的形态了,就可以按秩合并了,就可以爬树高了。

4144:[AMPPZ2014] Petrol:同上。


 


登录 *


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