bzoj 2120: 数颜色 暴力 底层常数优化

一看这道题,这不是带修改的莫队嘛。但是我不会啊。

也许分块能搞一搞,但是只有分块理论,并没写过,感觉过不了。

易,网上竟然说暴力可以过。而且这暴力还加了个没有什么意义的离散化,什么鬼?

交一发试试。

woc!!!竟然这种代码都能A。含有无意义离散化的裸暴力都能a!!

那[……]

Read more

bzoj 1562: [NOI2009]变换序列 二分图匹配

这题仔细想一下可以发现其实要实现是个二分图匹配。怎么使二分图匹配得出的匹配字典序最小,跟之前写过的一道菜肴制作采取的贪心策略相同,我们不去考虑如何让前面小的合理,我们只需考虑让后面大的足够就可了。这样子我们只要注意一下加边顺序和循环顺序即可。注意有no answer的情况。
[crayon-5b7[……]

Read more

bzoj 1503: [NOI2004]郁闷的出纳员 平衡树 以加代减 splay

woc!!!!这题题意有不明确的地方,初始工资不足的不计入最后的ans。mdzz,调了半天!!!!

就平衡树搞一下就好了。每当所有人的工资都+n,我们认为工资下限-n。反之也一样。这样子我们加入的w 就是加入w – 实际上的下限 + 当前下限。我们输出的就是节点的值 + 实际下限 – 当前下限[……]

Read more

bzoj 1014: [JSOI2008]火星人prefix splay+hash+二分

看了好几个人的博客都没有看懂,自己静心想一下就好了,平时还是应该多去思考。

我们考虑splay有一个特点,中序遍历就是原序列,而且你怎么旋转,怎么正确的插入都不会影响正确性。

插入很好办,我们考虑把u转到根。然后u+1转到根的右子树,那么n+1的左子树必定是空的,可以在这进行愉快的插入。[……]

Read more

bzoj 2243: [SDOI2011]染色 树链剖分

看一下大概是树剖裸题,我们注意一下下面的就行了。

回答询问时,我们直接算ans(a,lca) + ans(b,lca) – 1就行了,这么做做必定是正确的,自己考虑一下不同情况都正确。

线段树维护左颜色,右颜色,颜色数量即可。回答时候判断如果左右区间都有涉及才去考虑是否减1的问题。[……]

Read more

bzoj 2049: [Sdoi2008]Cave 洞穴勘测 lct 动态树

简直惨绝人寰,,,,,== 写成 = debug 2个小时,,,,,,,,

QAQ

合并,我们考虑,我们把一个点转到根,那么我们就可以毫无顾虑的把他作为儿子连一条虚边到另一个点上。

删边,我们考虑,如果把一个点旋转到根。在把另外一个点access,并splay到根。那么另外一个点的[……]

Read more

bzoj 1019: [SHOI2008]汉诺塔 DP

这题好神啊。看了半天毛线博客,感觉都写得好乱,,,,,,最后自己理解了理解,又找到了一份很棒的博客然后理解了!

这题一看就不是暴力模拟能解决的问题。我们看一下数据,又让你求步数布拉布拉一大堆。感觉dp还是有机会想出来的。我们先来回顾一下最本真的汉诺塔(当时初入OI的我毅然决然的直接粘了标称给了[……]

Read more

bzoj 1022: [SHOI2008]小约翰的游戏John 博弈论

博弈论什么的,感觉很懵逼,如果所有堆都是1。那么显然可以通过堆数的奇偶来判断胜负。我们考虑一下不所有堆都为0。我们可以根据sg定理来进行解决。至于sg定理,感觉讲不明白,所以鸽了。。。

bzoj 3098: Hash Killer II 奇妙推论

HINT

如果一个房间里有23个或23个以上的人,那么至少有两个人的生日相同的概率要大于50%。

当时题面给了上面这么一句话,然后我在想,这干啥啊。乱入啊。。。。然后尝试构造了半天都失败了。后来看了题解,woc!!!!!这句话竟然是题解。大概就是脸不黑的情况下,n个数随机sqrt(n[……]

Read more