TCO Round 1A

简直不能更惨,无法直视
500因为插件的原因resub * 2,直接从330分变到170分
然后还cha错了一次。以为那个是$$O(30000 * 30000 * 50^2)$$的,其实是$$O(30000 * \log(30000) * 50 ^ 2)$$的……
好好地记住$$\frac{n}{1} + \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + … + \frac{n}{n} = n \log n$$可以不……
1000,费用流没想到一是不够熟悉(努力不够),二是没想到TC会出网络流(出乎意料),三是智商和状态问题(自身客观因素)。一看到shi哥说费用流就马上反应过来怎么做了……欧蓝德啊。
感觉水平一年一年在提高,但是这种大比赛却一年比一年挫,真不知道说什么好……
确实不够努力吧,被屠也没什么好说的。
呵呵,终究是拿不到做出1000的勋章。
洗洗睡了。

NEERC2012 搞完纪念

……其实还有一题没搞完lol,但是人家解题报告都这么说了,就不搞了吧。

D的正则表达式转NFA纠结了好一会儿……自己写出来的WA到死,于是表达式解析的部分参照AC大妈的代码写了一下,获益良多啊。以前我写的表达式解析简直是…
子曰:学而不思则罔,思而不学则殆。保证一定时间的独立思考的前提下,多看看神人的写法是有莫大好处D。

I的那个神dp又WA过好一会儿,原因是枚举一个0~3的mask,脑抽地&3取高位……真是……

HTC X920e(butterfly) 刷谷歌服务

昨天入手一部butterfly,但是国行的google服务全被阉割了……好像是之前说的那个blabla反垄断的原因。
找了很多方法,也找了客服,得到的结果是不解锁就不可能正常使用谷歌的服务。
自己也试过直接装google service freamwork,发现装了以后不能登录的。真是点点点。
-.-反正我是不能忍受google calendar,google task这种东西下下来都开不了的状况的(因为google service freamwork没有)。于是就解锁开刷了。
虽说只要解锁了,官房就不免费保修了,但是连chrome都开不了实在是太恶心了。付钱就付钱吧。
基本按照这个地址上说的一步一步做。
http://bbs.angeeks.com/thread-2508656-1-1.html
然后刷rom的那部分改成刷入这个google服务包
http://bbs.angeeks.com/forum.php?mod=viewthread&tid=2512092&highlight=%B9%C8%B8%E8
于是现在一切都work了。
至于之前那部HTC ONE X还是让他返厂去fix wifi的天线好了……

NEERC2012 Problem B Blind Problem Solving

今天去看之前训练没搞出来的题,发现这个题特别奇怪……铁枝树干和我们都没提交过,但是后面的很多队伍都搞出来了。再仔细一看题目,发现是交互式的。想了一下,好像是我们当时做的时候这个题是没法提交的,于是今天一做就坑了一下午的
Idleness limit exceeded on test 1
WTF!!!!!
完全没想通是干嘛……
调了半天,才想到可能是输出以后,缓冲区没刷新然后他就一直卡在那里,就跪了。
于是加了fflush(stdout);以后终于可以了……
但是又WA3了半天,原因是答案是0的时候没考虑到-_-b。
真是圡得没药救了。
总结一下
1、交互式使用stdio的,使用printf或者puts以后一定要注意用fflush(stdout);刷新一下,要不然真是跪成狗都不知道怎么回事……但是用cout << xxx << endl就不会有这个问题。原因是endl自带刷新输出缓存。但是如果用cout << "xxx\n";则和printf, puts情况一样,悲剧地Idleness limit exceeded on test 1。 2、当感觉自己对得不能再对的时候,一定要想想边界情况啊:( 代码

icpcarchive6041 Retrenchment

传送门
雅加达的D,今天在机场滞留的时候写的……

【题意】

给n个点,R个区域(闭合简单多边形),每次询问某个区域内离给定点(qx, qy)的最近点与次近点分别是谁。

【算法】
求平面欧几里得距离最近点显然KDTree可以搞的。
具体就先暴力射线法判点在简单多边形内,然后把区域点集塞进KDTree里面,对于询问,用经典方法找离(qx, qy)最近的点。然后把这个点删除,再找次近点。输出以后把这个删掉的点插回去就好了。因为每次都是对静态的删除以及复原,所以直接加标记lazy delete就好了。
【时间复杂度】
$$O(Q \sqrt{n})$$
KDTree还是很快的……

【空间复杂度】
$$O(n)$$
【Note】
太圡了,WA了挺久的,因为define sqr(x) ((x) * (x)),然后x是int,然后就爆了……以后得注意了
【代码】
https://gist.github.com/4626176