Codeforces Round #243 (Div. 1)

本来昨天就打算打这场,战逗比sereja的。
因为和ctsc冲突了就没打。
总之:
人生若干大错觉之一:
这场比赛我去打的话rating一定能大涨(多见于赛后看题时的感觉)

A:

暴力

B:

一开始想简单了以为是条纹这样的是唯一可行解。
后来思考了一下发现格子衫的花纹才是唯一可行解。
然后yy不出来了。
发现k比较小,这个值得让人思考,我思考了十分钟出题人为何要出这么逗比的范围后。
发现如果k<n,那么肯定有一行完全没有被变换过。
否则那么2^n暴力枚举就可以了。

C:

看到这题第二句:
"One day Sereja got bored and he decided two play with them"
那个decided two play真是亮瞎狗眼。
sereja:这叫通假字你造吗?

总之这句decided two play就已经体现了此题的逗比水准
显然就是个dp,会发现e和s的倍数关系导致了消除次数最多几百。
暴力dp即可,我是暴力的……
当然也可以

D

经典题,先开的这道。
之前我写过一篇博文证明n个点的二维点集的矩形个数是的。
当时找资料的时候就顺便查到了结论n个点的二维点集的平行坐标轴的正方形个数是
有了这个结论……就知道大概暴力统计每个正方形就可以了。
事实上分块就能解决这题了(而且顺便把这个结论给证明了)
考虑点
设和它横坐标相同的点的个数是个。
如果cnt大于那么就把横坐标为x的点组成的集合称为大集合。
否则称为小集合。
一个正方形的右边的纵向边一定产生于某两个来自同一集合的点的连线(不能更显然了
对于小集合:
我们进行的枚举来枚举一个正方形的右边的纵向边具体坐标与长度。然后通过hash或二分来查找左边有没有对应的点来产生正方形。
对于大集合:
我们我们扫描所有横坐标小于x的点,那么如果正方形的左下角是枚举到的这个点,右边的边来自这个大集合的两点的连线,那么边长就确定了,这个正方形也就确定了。

这样就能完成暴力枚举了。
我用的是二分确定一个点的存在性。
总复杂度是
这题也是ontak2010的garden一题。
sereja你出原题真的没关系么。
代码只要1.1k(我还写冗了),不知道bzoj那些写了2k+的脑子怎么想的。

E

sereja的E题必水定律。
没见过这么水的E。
考虑一下对于一些区间我们是怎么求的。
显然就是按照右端点排序,然后贪心就好了。
那么定义
表示选出的区间集合中,贪心最后得到的右端点为i,成功选出j个区间的集合数。
递推很显然。
我们考虑对它的贡献。
显然我们必须要选一个右端点为i,并且左端点大于的区间,来保证贪心最后得到的右端点为i。
然后那些其它区间一定要跨越x,也就是说左端点小于等于,右端点小于等于的区间。
选出这些区间之后就可以保证能够转移了。
第一种区间有个。
第二种区间有个。
乘起来就得到了转移方程

既然你点进来看到这里我就再写点什么吧。

bzoj3551

我就不喷那些出xx加强版的人了。
又没加强多少也想出题?
真是有够无聊的。

在线段树合并推广之前,大部分人都是写平衡树启发式合并的吧。
所以我看到这题后就想到了炫酷的函数式平衡树合并的做法。
当然如果会线段树合并的话而且离线版写的也是这个的话,基本代码改不了几行就能做这题了。
不吐槽。
现在往bzoj上传的题目都这么蛇精病么……

3550

杜教一年前的博文里表示这是费用流经典题
诚实地说除了用类似志愿者招募里的用线性规划构造费用流模型的方法之外,
我根本就不会徒手构图(据说可以转化为k区间覆盖模型,构出的图也确实挺像这个的)
总之我就写了个单纯形交上去了。
结果发现了以前的单纯形模板有小问题……

Comments

comments powered by Disqus