作者存档：edward_mj

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