codeforces#221(div1)&&codeforces#219(div1)

火星了很久最后还是决定来补一个题解。
感觉这两场比赛算Div 1里面比较简单友好的一场了。

终于有能做的chinese round了……喜大普奔

CF#219

A

我是二分加贪心的……实际上可以O(n)排序之后O(n)扫

B

四维前缀和……我个,b自己手写了16种容斥情况……不能更蠢

C

傻×单调队列dp

D

由于做过Croc Champ 2012 - Round 2 E.Archaeology
所以没有想太久
但是喜闻乐见的忘记结论了……回忆了好久

E

反演……数平行四边形个数……

反演之后得到的直线……因为某些,b原因……我算倾斜角算出了大于180度的情况……结果wa on 6两次……

CF#221

A

乱搞……考试的时候看这题手速……next_permutation生成1,4,6,9的全排列,然后记录这个全排列看成4位数后模7的值就可以乱搞了……

这题在考试时出得快慢可能会有一点影响最终排名?表示看到kzf神手写4!种全排列感觉神爆了……

B

详见CEOI2009 logs……大原题一道……

乱搞就可以了
我直接拉自己bzoj上代码的TAT……复杂度n^2lgn……当然可以弄到n^2
代码非常好写……

C

首先bomb可以看成val为-inf的treasure……这是一个废条件
然后题目中给了你判断一个点在复杂多边形内的方法,
我们弄个状压[i][j][S]表示当前在(i,j),S为所有treasure往上射线穿过边的奇偶性
然后bfs即可

D

一种显然的做法就是莫队……但是O(n^1.5lgn)居然能过……我还有什么话可说呢?我懂得傻×foreseeable之所以默无声息的缘由了……
还有一种显然的做法就是合并平衡树……

询问离线之后……dfs一遍,对于每个节点建立以出现次数为关键字的平衡树

对于节点v,我们可以通过合并v的子节点的平衡树得到v的……然后用splay就nlgn了

好像也可以线段树合并……我没有写……

我打算写莫队的
主席吐槽我说线段树合并绝对比这个好写……
还是太naive了……

E

这题还是比较强的……比赛时无人能过……

clj的O(n^3)dp么……呵呵……

还是单纯形骗过去比较靠谱……

Comments

comments powered by Disqus