8
30
2014
0

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

既然最近没什么事情干那就继续屯题吧...

第二次达成日AC50题成就。这一次比上一次快多了...果然是背负了写什么东西才会有动力吗> <

顺便庆祝一下CF红名

现在屯了几道:

50

【BZOJ3683】【Shinrein祭#1】Falsita DFS序加树链剖分,一棵线段树一棵树状数组,爆交n遍最后发现是文件没有去T^T

【BZOJ3218】a + b Problem 好神的题目...用主席树来优化网络流。

【BZOJ3681】【Shinrein祭#1】Arietta Orz...用线段树合并再可持久化来优化网络流。空间似乎是log^2的但是貌似常数很小?MLE了4发然后莫名其妙的A了

【BZOJ3682】【Shinrein祭#1】Phorni 似乎自己YY出了类似后缀平衡树的东西...动态标号法,用替罪羊树实现。历时N久终于把这套比赛做完了...真是“小清新治愈系”数据结构专场

【BZOJ3600】【湖北省队互测Week1】没有人的算术 也是动态标号问题...脑洞大用了替罪羊树。

【BZOJ3678】wangxz与OJ 最近代码能力实在是差...直接splay,每个节点维护一个区间

【BZOJ3637】QtreeVI 每个节点的答案等于和它相连的最浅节点的答案,于是就可以用维护子树的方法维护了。DFS序+树状数组

【BZOJ3679】QtreeVII 每个节点的答案等于和它相连的最浅节点的答案,用两棵LCT来分别维护黑点和白点。用splay维护实边的信息,每个节点一个set维护虚边的信息。(常数大慢哭了> <

【BZOJ3687】简单题 很显然是背包...不压位贴着时限过去了,压30位后就跑得很快了。

【BZOJ3685】普通的van Emde Boas树 直接线段树就可以水了(开始写了treap和set都翔了 

【BZOJ3688】折线统计 终于有一道1A的题目了..感人肺腑。没看到k的数据范围时还以为是神题。既然k<=10那么直接暴力树状数组就好了

【BZOJ3689】异或之 类似于超级钢琴,可持久化Trie+堆。

【BZOJ3696】化合物 O(nh^2)很好想,然后用FWT优化就可以过了

【BZOJ3695】滑行 很容易想到二分第一个入射角。开始爆精度WA了很久T^T

【BZOJ3694】最短路 显然每个点是先往下走一段然后跳到其它地方再走到根。因此每一条非树边影响到的只是路径除LCA的点,暴力做即可。

【BZOJ3519】【ZJOI2014】消棋子 回头做做当初坑死我的题目。也不是特别难写?set乱搞就可以了。因为逗逼的输入蛋疼了半天T^T

【BZOJ3693】圆桌会议 把环复制两遍拆成链,按照右端点升序排序离散化后再用线段树搞搞。

【BZOJ3692】愚蠢的算法 好神的题目> <很显然f就是逆序对个数。然后令w[i][j]表示考虑了1到i,后j位对g有贡献的方案数,DP即可

【BZOJ3690】棋盘 高斯消元很显然,然后可以发现确定了前两行第一列后其它的情况唯一,然后矛盾只可能在后两行最后一列。高斯消元即可

【BZOJ3691】游行 可以发现成环(@裴某人)和连接两个连通块减少的代价都是C。于是可以先不考虑C,把每个点拆成两个点,然后连上最短路的费用,预处理出所有增广路的费用然后取最优就可以了。

【BZOJ3701】Olympics Games 数据范围这么小很容易想到枚举一维然后计算。用莫比乌斯函数搞搞就可以了。

【BZOJ3702】二叉树 POI2011原题,本来是用splay启发式合并写的,结果T了,重写了一个DFS序+线段树。

【BZOJ3704】昊昊的机油之GRST ZLD和他的基友之间的感♂情真是...好神的题目,膜拜了题解。先构造一个解然后贪心逼近最优解。

【BZOJ1414】【ZJOI2009】对称的正方形 先用manacher预处理出来每一行每一列的回文串,然后再用ST表搞出每个点上下左右最多能延伸多少即可。

【BZOJ3705】对称的正方形 同上

【BZOJ3697】采药人 显然是点分治,样例中混入的l是闹咋样?细节搞搞就好了。

【BZOJ3127】【Usaco2013 Open】Yin and Yang 同上

【BZOJ1018】【SHOI2008】堵塞的交通 开始懒得写线段树开始写Lich的n^1.5分块并查集做法...然后写了一半发现时限3S。线段树又被细节坑到了凌晨,代码能力差没话说T^T

【BZOJ3676】【APIO2014】回文串 manacher每次枚举到的串都是本质不同的回文串,应用这一点配上后缀数组就可以做了。

【BZOJ3677】【APIO2014】连珠线 如果在现场我一定过不了这道题...开始直接想O(n)算法导致合法的条件有点模糊。后来索性先码了枚举第一个珠子的暴力然后思路就清晰了。

【BZOJ3668】【NOI2014】起床困难综合症 分位考虑即可。(看到NOI2014的题目真想切腹自尽)

【BZOJ3669】【NOI2014】魔法森林 这种LCT我现在居然一遍写不对真是没救了。(看到NOI2014的题目真想切腹自尽)

【BZOJ3670】【NOI2014】动物园 考场上我怎么会那么傻逼...KMP然后DFS一遍就好了。(看到NOI2014的题目真想切腹自尽)

【BZOJ3671】【NOI2014】随机数生成器 妈的这真的是普及组难度的题,考场上的确想到了n^2的做法,但是想想怎么会这么简单然后就不知道怎么的分析成n^3了。我*这出题人。(看到NOI2014的题目真想切腹自尽)

【BZOJ3672】【NOI2014】购票 树上CDQ分治,实在是优美的想法。(看到NOI2014的题目真想切腹自尽)

【BZOJ1019】【SHOI2008】汉诺塔 直接递推即可

【BZOJ1021】【SHOI2008】循环的债务 以前一直以为是神网络流...看到数据范围感觉可以爆搜?最后发现是DP。。

【BZOJ1028】【JSOI2007】麻将 暴力

【BZOJ1034】【ZJOI2008】泡泡堂BNB 记得以前做过数据范围2000的版本?记得是贪心+DP来着。然后数据范围10W就只好膜拜题解了...好神的贪心(果然太弱不能在ZJ待啊...

【BZOJ1037】【ZJOI2008】生日聚会party 裸的DP

【BZOJ1040】【ZJOI2008】骑士 基环外向树,断掉环上一条边做两次DP,重边比较坑爹。(印象中以前看着道题看了好多遍都不会做,现在真的开始怀疑以前的水平了...

【BZOJ1042】【HAOI2008】硬笔购物 挺神的题目..根本没有往容斥方面想T^T只好去膜拜题解了

【BZOJ1044】【HAOI2008】木棍分割 先二分出答案然后前缀和优化DP

【BZOJ1049】【HAOI2006】数字序列 YY了半天只会n^2的,然后就去膜拜题解了。标算居然是n^2的...随机数据果然可怕

【BZOJ1057】【ZJOI2007】棋盘制作 直接DP就好了

【BZOJ1059】【ZJOI2007】矩阵游戏 二分图匹配,i行j列为1就连一条边

【BZOJ1060】【ZJOI2007】时态同步 简单的树形DP,BZ上数据错了...

【BZOJ1084】【SCOI2005】最大子矩阵 直接DP就好了

【BZOJ1087】【SCOI2005】互不侵犯 状压DP水过(其实我一开始想搜索的

【BZOJ1188】【HNOI2007】分裂游戏 果然我博弈论实在是太弱了...sg函数,每个石子都是独立的,剩下暴力就可以了

Category: 论逗逼的自我修养系列 | Tags: | Read Count: 2756

登录 *


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