11
26
2014
4

论逗逼的自我修养之屯题计划第三弹

水了两届POI感觉心力憔悴...还是来看看BZ上面有没有什么人(sang)畜(xin)无(bing)害(kuang)的非权限题吧。

[11.29]感觉人生失去了希望...状态极差..

[12.4]发现BZ上的题目质量越来越差了..(似乎对着最后放上去的题目磕的时代一去不复返了?

[12.24]tj了好久...因为各种各样的事情所以就开始荒废了..现在想办法尽快结了这个坑然后再干点其他的事情把

[12.25]总算搞完50题了..明天再来一起交吧

[12.26]完结撒花,在BZ上的AC题数终于破700了> <这一次的用时意外的长..果然是越来越弱了

现在做了几题

50

 

【BZOJ3616】War 要问我现在状态有多差。。看看这道题。。毫无思维难度的一道kd-tree裸题(当然我指的是压位的做法,不压位的有些细节我现在也没理清)我就是写不对。。搞了一天最后发现我算期望的地方搞错了。。这种小学生都不会犯的错误。。感觉人生失去了希望。

【BZOJ3747】【POI2015】Kinoman 枚举左端点,每一种颜色第一次出现的贡献为正第二次为负以后都是0,这样预处理出每一个点的后继,计算时用线段树维护单点修改询问前缀和最大值即可。

【BZOJ3781】小B的询问 无脑莫队

【BZOJ3721】【PA2014】Bazarek sort以后无脑贪心

【BZOJ3744】Gty的妹子序列 直接分块,时间复杂度[tex]O(n \sqrt{n \log n})[/tex],莫名其妙的在BZ上就R1了

【BZOJ3676】A + B Prlblem加强版 呵呵

【BZOJ3760】suitang 每次一定是矩形的四个角中的一个,二分后爆搜判断

【BZOJ3761】zhenhuan 记得以前做过。。现在不会做了。二分答案后吧颜色分成[tex]1-a_1[/tex]和[tex]a_1+1-ans[/tex]两段然后求第一段的最少最多数量即可。

【BZOJ3787】Gty的文艺妹子序列 直接分块,我实在是没有看出和Gty的妹子序列之间有什么区别。时间复杂度[tex]O(n \sqrt n \log n)[/tex]

【BZOJ3625】小朋友与二叉树 多项式开根

【BZOJ2426】【HAOI2010】工厂选址 呵呵

【BZOJ3105】【CQOI2013】新NIM游戏 贪心,每次从大往小取,能取就取,这样答案最优,用高斯消元判断是否能取

【BZOJ3106】【CQOI2013】棋盘游戏 无脑记忆搜

【BZOJ3107】【CQOI2013】二进制a+b 无脑DP

【BZOJ3124】【SDOI2013】直径 拉出一条直径来,然后对于直径上每一个点判断是否与左右端点等价,然后找左端点等价点和右端点等价点之间的最短距离即可。

【BZOJ3684】大朋友与多叉树 终于从策爷口中套出了做法。

【BZOJ2741】【FOTILE模拟赛】L 分块然后用trie树搞就好了

【BZOJ3160】万径人踪灭 把它看成[tex]time_a+1[/tex]进制的数FFT就可以只做一次DFT和一次IDFT,居然跑到R1了。

【BZOJ2743】【HEOI2012】采花 离线然树状数组

【BZOJ3158】千钧一发 奇偶分成二分图跑最小割

【BZOJ3155】Preprefix sum 看成询问前缀和和后缀减,用树状数组就好了

【BZOJ2744】【HEOI2012】朋友圈 枚举A国然后B国跑匹配就好了

【BZOJ3790】神奇项链 贪心,每次走到尽可能远的地方

【BZOJ3791】作业 开始全部染成一种颜色,然后DP

【BZOJ3792】跑步 把状态设为上一次走过的边然后跑矩阵乘法

【BZOJ2115】【WC2011】Xor 找一条1到[tex]n[/tex]的路径,其余的环是可以任意的出现在路径上,用类似于高斯校园的方法判断就好了。

【BZOJ3799】字符串重组 直接贪心讨论几种情况即可

【BZOJ3609】【HEOI2014】人人尽说江南好 打表后得到最终剩下的堆数是[tex]\frac{n-1}{m}+1[/tex],判断奇偶性即可。

【BZOJ3611】【HEOI2014】大工程 建出来虚树以后直接DP

【BZOJ3613】【HEOI2014】南园满地堆轻絮 显然把数尽可能改小最优,贪心扫一遍

【BZOJ3614】【HEOI2014】逻辑翻译 用类似分治的思想,每一次求出确定了前[tex]i[/tex]个的存在状态下的系数和,最后的程序和FFT很相似。

【BZOJ3610】【HEOI2014】林中路径 开始写了一个裸的矩乘结果T了。用分治的思想,假设已经知道了长度小于等于[tex]n[/tex]的路径条数,路径条数乘长度,路径条数乘长度的平方,那么就可以更新出[tex]2n[/tex]的答案。

【BZOJ3612】【HEOI2014】平衡 一组拆分都可以看成另外一组拆分所有数加上一或者所有数加上一后再添加一个一。直接DP就好了。

【BZOJ2822】【AHOI2012】树屋阶梯 卡特兰数,写个高精度就好了

【BZOJ2823】【AHOI2012】信号塔 最小圆覆盖 随机增量法

【BZOJ2326】【HNOI2011】数学作业 按照位数分开考虑,那么就可以矩乘了。

【BZOJ3809】Gty的二逼妹子序列 莫队+对权值分块。似乎权值分块这种修改[tex]O(1)[/tex]询问[tex]O(\sqrt n)[/tex]的结构只有在莫队的时候才有更优的复杂度?

【BZOJ2282】【SDOI2011】消防 答案一定在直径上,然后用个堆在直径上面扫一下就好了。

【BZOJ3728】【PA2014Final】Zarowki 贪心,排序后用个栈找到每一个灯泡最优匹配的灯泡然后选代价最小的[tex]n-k[/tex]个。

【BZOJ3725】【PA2014Final】Matryca 二分答案后判定显然。似乎[tex]O(n)[/tex]也挺方便的,不过没有仔细想。

【BZOJ3727】【PA2014Final】Zadanie 每一个点的人数都可以用二元组[tex](a,b)[/tex]表示成[tex]an+b[/tex],然后把[tex]n[/tex]解出来就好了。

【BZOJ3140】【HNOI2013】消毒 可以暴力最小的一维然后其他的用二分图匹配求最小值,卡常数实在蛋疼。

【BZOJ3810】【COCI2015】Stanovi 每一种用了多于一个房间的分割都一定存在一条线把它划分成两个矩形,所以可以记忆搜,状压四条边和边界相邻的状态,然后再压一压常数就好了。

【BZOJ3806】【Neerc2011】Dictionary Size trie树上搞一搞就好了。

【BZOJ3813】奇数国 见清华集训题练习那篇博文

【BZOJ3812】主旋律 见清华集训题练习那篇博文

【BZOJ3816】矩阵变换 见清华集训题练习那篇博文 

【BZOJ3489】A simple RMQ problem 一道困扰我多年的题目...一直想想出线段树套堆的方法,但是就是不会..最后还是一个二维线段树。不过写写也就十几分钟还是挺方便的。

【BZOJ3750】【POI2015】Pieczec 可以找到每次左上角的位置暴力搞就好了。

【BZOJ3749】【PIO2015】Lasuchy 每一个点的选择之和前两个人有关,枚举第一个人以及最后一个人的选择然后状压前两个人的状态DP就好了。

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 2423
Avatar_small
Bakser 说:
2014年12月01日 14:53

作为出题人之一的蒟蒻求问您3744是怎么做到log在根号里面的Orz

Avatar_small
jiry_2 说:
2014年12月03日 00:06

@Bakser: 调整块的大小不就好了。。假设块的大小为[tex]S[/tex],复杂度是[tex]O(\frac{n^2}{S}+S \log n)[/tex],所以log在根号里面啊

Avatar_small
jiry_2 说:
2014年12月03日 13:53

@jiry_2: 哦应该是[tex]+Sn \log n[/tex]


登录 *


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

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