Nov
23
虽然说最后的结果没有比我预期的差，但是过程还是很囧的。鉴于这里是我自己的博客，废话就多写一点。
总之就是从10月的某个Hi消息开始的，jieyu突然告诉我，搞到了一个福州赛区的名额，和ldl同学一起，组个队伍，参加区域赛。缘由很简单，他想公费回家，顺便打个酱油。于是名叫烤馍馍（OpenKaomomo）的酱油队诞生。
真是很久没有做题了。做题的日子是很快乐的，至少可以把日子过得很简单的，其他七七八八的事情可以暂时放到一边，虽然有些不负责，但是突然觉得一切都变简单了；除了那些迫在眉睫的事情不得不分出时间来处理之外。
于是开始到机房和ldl一起做比赛，并且开始在WOJ上面刷题。大概做了四场比赛吧，WOJ的题目也刷七十多道（当然基本都是简单题），慢慢的找回了大二时的那种感觉（其实就是花大把的时间DEBUG那些BUGGY CODE）。不过之前不是搞得特别清楚的东西，在时间的积淀下，很多都豁然开朗，写起代码来也顺畅多了。
前往福州的旅程是比较曲折的。其实那一堆人里面我是最没有区域赛参赛经验了——因为这是我第一次（估计也是最后一次）参加Regional。所以在出发前两天（周三），我也还等着通知，在群里头问何时何地集合。然后发现原来大家也都在等。于是只好给董哥打电话，问。说是车票买的周五的，不是周四，要和实践办的叶主任一起去。于是给叶主任电话，约好，第二天到他办公室，谈清细节（到BBS上发集合帖），领了400块钱，下午拉上钟安原和FOUR两位同学一起到学院旁的自强去采购了320块钱的食品。真重。
周五下午3点机房集合了，把吃的东西分发，然后13个人（包括甜菜和CW）挤上一辆面包车开往武昌火车站，吃零食，看小说，看电影，睡觉（还是甜菜比较简单，从上车睡到下车），早上10点，抵达福州。真暖和。穿太多了。领着大家在公交车站等了半天308，到宾馆把房间开了，然后在天峰宾馆站等了半天91，然后在福大东门又等了好一会儿96，好不容易到福大，才跟志愿者MM碰上面。顺便说一句，志愿者MM也是福一中的，高中学妹啊。在福大食堂吃饭，jieyu和ldl随后赶到，一起吃饭去参加练习赛。进场的时候就已经迟了一点。
总算切入主题，练习赛。练习赛一共五题，ldl从后往前看，我从前往后看，jieyu看中间。A是简单的字符串处理，ldl速度上去敲，居然WA了。然后是我看的E题，素数筛法+因式分解，ldl上去敲，但是他筛法什么记不太清楚了，于是换我（正好前一阵写了好几题类似的），敲出来没有过样例，打印代码。帮ldl看A题，发现是题意没看清，100个word看成100个字符，AC。然后看自己的代码，发现有两个BUG，改了提交，AC。接着是B题，刚开始觉得最小生成树是错的，后来jieyu仔细考虑，发现如果用kruscal是可以保证正确性的。ldl敲。WA。WA。WA。看了一遍代码以后，发现是找边的循环退出条件位置不对，如果最小生成树只有1～2条边，就会出错，改之，AC。于是发现自己还是很适合搞DEBUG。这是好事还是坏事？考虑C题，SPlay有模板，不过题目的难点不在于SPlay，而在于树的输出，考虑了很久，最后放弃了。D题的图着色，写了暴力算法，不过没交。比赛结束，3题，排名78左右。练习赛的总结是，必须要给出一些极端测试数据，不能乱交。
结束后回去等车等得很痛苦，尤其是福大东门的91路……等了四五十分钟，最后还是让老妈和舅开车过来把大家接到南洋饭店吃了顿好的。晚上睡得不安稳，4点多被噩梦闹醒，然后噩梦不断，迷糊到早上7点出头，被闹钟吵醒。下楼吃了早餐（这个酒店的早餐不给力啊），然后坐车。志愿者说武大的队伍在10号车，上车坐了好一会儿说是错了，应该在14号车，结果走过去又说是13号车，上车后董哥电话问：你们上了3号车没……真是攒足了RP啊。
决赛奇葩地在9点30开始。10题，照例ldl从头，我从后，杰瑜中间。
最初是暴力的j题在100分钟AC的。首先是过不了样例，发现是忘了处理不合法的前导零。然后发现程序还有BUG，数组索引有错。然后提交，WA。jieyu检查发现是因为直接用除法，没有考虑整除。我则认为可能会溢出，改用long long进行乘法。于是AC。
第3个开的，F题是个AC自动机，就是数据量BT了一点。ldl敲完标程，过了样例，但是我出了个很弱的数据就跑错了。修改了以后提交，TLE。TLE。TLE。ldl一直比较紧张，到最后才45min的时候才静下心把问题找出来，AC。
第4个开的题目应该是B题吧。无向图最小割，被我读成了N个最大流，又是我的错-。- 总之就是TLE+TLE，在比赛最后7分钟的时候貌似还提交了一次，TLE，放弃。
H题，这题就是个大杯具，开的第2个题，AC的最后一个题。问题大概应该算在我头上吧，因为最初的时候没有把题意完全看清楚（固定的5分钟间隔），导致思考的时候出现各种偏差，提交了3次，都WA了。最后一小时我提出一个很繁琐的算法：记f[i][j]是表示在i分钟第一次选(0<=i<=4)，到第i+5*j分钟可以得到的最大值，for (i = 0; i < 5; i++) f[i][j] = max{ f[i][k]+g(i+5*j) | 0<=k<j }, 其中j是选择的时间点，g(i+5*j)的值是0或1，由一个辅助的数组G[k][1..N]来导出，G[k][t]表示第t个课程在前i+5*k分钟是否被选中（且每次确定G[j][1..N]需要由G[k][1..N]更新）。此算法虽然繁琐且效率低，但是因为每一次往前都能保证最优，可以保证正确性。jieyu大致是从这里得到一点启发，想出正确的贪心算法，终于在269min，也就是最后半小时的时候AC了这题。
我们还在最后半小时的时候开了G题，在DAG上的一个简单DP，编码完全没有难度，感觉比J题还简单。这题是我去写的，思路很清晰，就是最后了比较紧张，出了两个BUG，没能在结束之前通过样例，怨念。关于这题的另一个怨念在于，开场我就看过了这题，之所以没有之前就考虑它，是因为它那OOXX的输入格式很让人纠结，跟jieyu提了一下，他说这题很有意思。然后就撂着了。杯具啊。
除了以上的题目，我们还考虑过E题（四边形费马点）、D题（XOR那题）。E题之所以没有去写，是因为杰瑜读错了题目，他问我Quadrangle这个词什么意思，我说不知道，不过Angle是角，Quadr含有4的意思，于是他认为是四面体。于是这题就废了。（字典啊字典……还是应该带上字典的，ldl同学。。）
比赛完基本上可以确定是打铁了。稍微有点失落，毕竟是第一次也是最后一次参加区域赛吧，没能拿牌还是挺遗憾的。尤其是在发挥正常的情况下至少还有2道题是确定可以出的，并且之前的题目过程太纠结。总之就是不甘+怨念。
比赛完去采购，买了很多东西。其实额外买了一瓶蜂蜜是想送给志愿者mm慰劳一下，不过出来以后才想起除了志愿者mm，还有一个志愿者gg，所以就一直没好意思拿出来~.~ 然后大家在草地上等吃饭，jieyu则干脆先跑去玩了。
大约4点50的时候，该mm说，我们有两只队伍获奖了，应该是Valor和烤馍馍，需要提前去颁奖会场做准备。过山车啊这是。。。后来在饭桌上跟大家提起，说是不对，Forward在封榜前就3题了，不应该在烤馍馍后面的。于是打电话给该mm询问，说是只确定是两支，不确定是哪两只。过山车啊这是。。。看来是确定铁牌了。5点45的时候再跟着志愿者走到颁奖会场，登记的时候神奇地发现，武大有三支队伍获奖，烤馍馍耗尽RP，排在了名单倒数第二的位置。过山车啊这是。。。
幸好过山车到站，最后顺利领到牌子……最终成绩是Valor，5题，铜牌第一；Forward，3题，铜牌30左右；烤馍馍，3题，铜牌倒二。
这里顺便提一下颁奖晚会的俩奇葩舞蹈，一个是劲舞（名字不太记得），前面两排mm，大都很漂亮，后面一排gg，大都很帅，不过最中间的那个mm明显不给力，腰围的绝对值比较大，其中一个做俯卧撑的动作，很吃力。另外一个舞蹈叫《女人花》，大多数mm都很不错，但是最核心的那个……腰围更粗，明显赘肉在颤，摆出各种S型，还叼花……我只能联想起当年那个“芙蓉姐姐 叼花”的照片，你去百度图片搜一下，第一张那个……
终于领了证书，坐上回程的车，回到宾馆，至此，福州比赛结束。最终的结果差强人意。虽然早先jieyu说应该拿个silver，但是根据现场的情况来看，正常发挥应该也就是5题，还是bronze，所以就不需要太怨念了。
----分割线----
最后是Felix021@烤馍馍的比赛总结：
· 看清题意。还是太忽视了一点。如果决定开始做一道题目，应该要有两个人看清题意，并且在细节上达成一致，这样才能保证不会出现各种糊涂问题，比如此次的E、H题。
· 每个人都应该把每题都大概看过，至少稍微思考一下，不至于漏掉G那样的简单题。
· 这次比赛对Board的关注太少了，以至于G这样的题目到最后半小时才开始考虑，实在是太过分了。
· 如果某人开了一题，条件允许的情况下，应该有人帮忙出测试数据。这次正式比赛的时候我们这个约定没被贯彻好。
· 大家都太紧张了，应该早点喝红牛的。
总之就是从10月的某个Hi消息开始的，jieyu突然告诉我，搞到了一个福州赛区的名额，和ldl同学一起，组个队伍，参加区域赛。缘由很简单，他想公费回家，顺便打个酱油。于是名叫烤馍馍（OpenKaomomo）的酱油队诞生。
真是很久没有做题了。做题的日子是很快乐的，至少可以把日子过得很简单的，其他七七八八的事情可以暂时放到一边，虽然有些不负责，但是突然觉得一切都变简单了；除了那些迫在眉睫的事情不得不分出时间来处理之外。
于是开始到机房和ldl一起做比赛，并且开始在WOJ上面刷题。大概做了四场比赛吧，WOJ的题目也刷七十多道（当然基本都是简单题），慢慢的找回了大二时的那种感觉（其实就是花大把的时间DEBUG那些BUGGY CODE）。不过之前不是搞得特别清楚的东西，在时间的积淀下，很多都豁然开朗，写起代码来也顺畅多了。
前往福州的旅程是比较曲折的。其实那一堆人里面我是最没有区域赛参赛经验了——因为这是我第一次（估计也是最后一次）参加Regional。所以在出发前两天（周三），我也还等着通知，在群里头问何时何地集合。然后发现原来大家也都在等。于是只好给董哥打电话，问。说是车票买的周五的，不是周四，要和实践办的叶主任一起去。于是给叶主任电话，约好，第二天到他办公室，谈清细节（到BBS上发集合帖），领了400块钱，下午拉上钟安原和FOUR两位同学一起到学院旁的自强去采购了320块钱的食品。真重。
周五下午3点机房集合了，把吃的东西分发，然后13个人（包括甜菜和CW）挤上一辆面包车开往武昌火车站，吃零食，看小说，看电影，睡觉（还是甜菜比较简单，从上车睡到下车），早上10点，抵达福州。真暖和。穿太多了。领着大家在公交车站等了半天308，到宾馆把房间开了，然后在天峰宾馆站等了半天91，然后在福大东门又等了好一会儿96，好不容易到福大，才跟志愿者MM碰上面。顺便说一句，志愿者MM也是福一中的，高中学妹啊。在福大食堂吃饭，jieyu和ldl随后赶到，一起吃饭去参加练习赛。进场的时候就已经迟了一点。
总算切入主题，练习赛。练习赛一共五题，ldl从后往前看，我从前往后看，jieyu看中间。A是简单的字符串处理，ldl速度上去敲，居然WA了。然后是我看的E题，素数筛法+因式分解，ldl上去敲，但是他筛法什么记不太清楚了，于是换我（正好前一阵写了好几题类似的），敲出来没有过样例，打印代码。帮ldl看A题，发现是题意没看清，100个word看成100个字符，AC。然后看自己的代码，发现有两个BUG，改了提交，AC。接着是B题，刚开始觉得最小生成树是错的，后来jieyu仔细考虑，发现如果用kruscal是可以保证正确性的。ldl敲。WA。WA。WA。看了一遍代码以后，发现是找边的循环退出条件位置不对，如果最小生成树只有1～2条边，就会出错，改之，AC。于是发现自己还是很适合搞DEBUG。这是好事还是坏事？考虑C题，SPlay有模板，不过题目的难点不在于SPlay，而在于树的输出，考虑了很久，最后放弃了。D题的图着色，写了暴力算法，不过没交。比赛结束，3题，排名78左右。练习赛的总结是，必须要给出一些极端测试数据，不能乱交。
结束后回去等车等得很痛苦，尤其是福大东门的91路……等了四五十分钟，最后还是让老妈和舅开车过来把大家接到南洋饭店吃了顿好的。晚上睡得不安稳，4点多被噩梦闹醒，然后噩梦不断，迷糊到早上7点出头，被闹钟吵醒。下楼吃了早餐（这个酒店的早餐不给力啊），然后坐车。志愿者说武大的队伍在10号车，上车坐了好一会儿说是错了，应该在14号车，结果走过去又说是13号车，上车后董哥电话问：你们上了3号车没……真是攒足了RP啊。
决赛奇葩地在9点30开始。10题，照例ldl从头，我从后，杰瑜中间。
最初是暴力的j题在100分钟AC的。首先是过不了样例，发现是忘了处理不合法的前导零。然后发现程序还有BUG，数组索引有错。然后提交，WA。jieyu检查发现是因为直接用除法，没有考虑整除。我则认为可能会溢出，改用long long进行乘法。于是AC。
第3个开的，F题是个AC自动机，就是数据量BT了一点。ldl敲完标程，过了样例，但是我出了个很弱的数据就跑错了。修改了以后提交，TLE。TLE。TLE。ldl一直比较紧张，到最后才45min的时候才静下心把问题找出来，AC。
第4个开的题目应该是B题吧。无向图最小割，被我读成了N个最大流，又是我的错-。- 总之就是TLE+TLE，在比赛最后7分钟的时候貌似还提交了一次，TLE，放弃。
H题，这题就是个大杯具，开的第2个题，AC的最后一个题。问题大概应该算在我头上吧，因为最初的时候没有把题意完全看清楚（固定的5分钟间隔），导致思考的时候出现各种偏差，提交了3次，都WA了。最后一小时我提出一个很繁琐的算法：记f[i][j]是表示在i分钟第一次选(0<=i<=4)，到第i+5*j分钟可以得到的最大值，for (i = 0; i < 5; i++) f[i][j] = max{ f[i][k]+g(i+5*j) | 0<=k<j }, 其中j是选择的时间点，g(i+5*j)的值是0或1，由一个辅助的数组G[k][1..N]来导出，G[k][t]表示第t个课程在前i+5*k分钟是否被选中（且每次确定G[j][1..N]需要由G[k][1..N]更新）。此算法虽然繁琐且效率低，但是因为每一次往前都能保证最优，可以保证正确性。jieyu大致是从这里得到一点启发，想出正确的贪心算法，终于在269min，也就是最后半小时的时候AC了这题。
我们还在最后半小时的时候开了G题，在DAG上的一个简单DP，编码完全没有难度，感觉比J题还简单。这题是我去写的，思路很清晰，就是最后了比较紧张，出了两个BUG，没能在结束之前通过样例，怨念。关于这题的另一个怨念在于，开场我就看过了这题，之所以没有之前就考虑它，是因为它那OOXX的输入格式很让人纠结，跟jieyu提了一下，他说这题很有意思。然后就撂着了。杯具啊。
除了以上的题目，我们还考虑过E题（四边形费马点）、D题（XOR那题）。E题之所以没有去写，是因为杰瑜读错了题目，他问我Quadrangle这个词什么意思，我说不知道，不过Angle是角，Quadr含有4的意思，于是他认为是四面体。于是这题就废了。（字典啊字典……还是应该带上字典的，ldl同学。。）
比赛完基本上可以确定是打铁了。稍微有点失落，毕竟是第一次也是最后一次参加区域赛吧，没能拿牌还是挺遗憾的。尤其是在发挥正常的情况下至少还有2道题是确定可以出的，并且之前的题目过程太纠结。总之就是不甘+怨念。
比赛完去采购，买了很多东西。其实额外买了一瓶蜂蜜是想送给志愿者mm慰劳一下，不过出来以后才想起除了志愿者mm，还有一个志愿者gg，所以就一直没好意思拿出来~.~ 然后大家在草地上等吃饭，jieyu则干脆先跑去玩了。
大约4点50的时候，该mm说，我们有两只队伍获奖了，应该是Valor和烤馍馍，需要提前去颁奖会场做准备。过山车啊这是。。。后来在饭桌上跟大家提起，说是不对，Forward在封榜前就3题了，不应该在烤馍馍后面的。于是打电话给该mm询问，说是只确定是两支，不确定是哪两只。过山车啊这是。。。看来是确定铁牌了。5点45的时候再跟着志愿者走到颁奖会场，登记的时候神奇地发现，武大有三支队伍获奖，烤馍馍耗尽RP，排在了名单倒数第二的位置。过山车啊这是。。。
幸好过山车到站，最后顺利领到牌子……最终成绩是Valor，5题，铜牌第一；Forward，3题，铜牌30左右；烤馍馍，3题，铜牌倒二。
这里顺便提一下颁奖晚会的俩奇葩舞蹈，一个是劲舞（名字不太记得），前面两排mm，大都很漂亮，后面一排gg，大都很帅，不过最中间的那个mm明显不给力，腰围的绝对值比较大，其中一个做俯卧撑的动作，很吃力。另外一个舞蹈叫《女人花》，大多数mm都很不错，但是最核心的那个……腰围更粗，明显赘肉在颤，摆出各种S型，还叼花……我只能联想起当年那个“芙蓉姐姐 叼花”的照片，你去百度图片搜一下，第一张那个……
终于领了证书，坐上回程的车，回到宾馆，至此，福州比赛结束。最终的结果差强人意。虽然早先jieyu说应该拿个silver，但是根据现场的情况来看，正常发挥应该也就是5题，还是bronze，所以就不需要太怨念了。
----分割线----
最后是Felix021@烤馍馍的比赛总结：
· 看清题意。还是太忽视了一点。如果决定开始做一道题目，应该要有两个人看清题意，并且在细节上达成一致，这样才能保证不会出现各种糊涂问题，比如此次的E、H题。
· 每个人都应该把每题都大概看过，至少稍微思考一下，不至于漏掉G那样的简单题。
· 这次比赛对Board的关注太少了，以至于G这样的题目到最后半小时才开始考虑，实在是太过分了。
· 如果某人开了一题，条件允许的情况下，应该有人帮忙出测试数据。这次正式比赛的时候我们这个约定没被贯彻好。
· 大家都太紧张了，应该早点喝红牛的。
Nov
17
数码相机拍下来的照片普遍偏大，在很多情况下，需要保存的照片并不需要很高的分辨率和压缩质量，所以会用一些程序，比如ACDSee、QQ影像、ImageMagick之类的程序来批处理照片，将它们的尺寸缩小，并适当降低压缩比，使得照片的存储、传输更方便。
这样一来会遇到的问题是，EXIF信息的丢失。上述的这些工具在处理照片的时候都有意无意地忽略了EXIF，让人很郁闷（令人感到惊奇的是，粗糙的windows画图板在缩放、保存图片的时候EXIF信息是不会丢失的）。
最近处理WHUMSTC10周年party照片的时候就遇到这个问题。照片总共有605张，使用Canon 450D最高分辨率拍摄，一共2.4G+，一张照片平均有4MB。通过QQ影像压缩到原来的1/4，并且压缩质量调整为85%，所有照片的体积立即缩小为176M左右。但是EXIF信息的丢失，使得很有含金量的“照片拍摄时间”也随之丢失。
于是试着去解决。本来想用PHP自带的EXIF库（最熟PHP，没办法-.-），但是发现它只支持Read，不支持Write。又找了找PYTHON的，挺多，但是用起来总不对头，就没继续折腾。最后还是在Ubuntu下apt-cache search exif，发现了exiv2这个实用工具，非常赞。
对一张照片处理，执行：(ex=extract)会将照片的exif信息保存到同文件夹下的xxx.exv文件中；(in=insert)则会将同文件夹下的xxx.exv信息插入到xxx.jpg中。
需要批量处理的话，完整过程是这样：
1. 使用QQ影像或者使用命令行的ImageMagick将src/*.jpg压缩转换，保存到dest/*.jpg。注意相同文件的文件名保持不变。
2. 在src下面执行将所有文件的exif信息导出
3. 将所有exv文件拷贝到dest文件夹
4. 恢复exif信息
如果是windows，可以從這裡下載exiv2的可執行文件：http://www.exiv2.org/download.html ；如果有Ubuntu的話，直接apt-get install exiv2就好，當然也可以自己編譯安裝，只要身體裡兩個圓形的器官不會隱隱作痛就行。。
終り.
这样一来会遇到的问题是，EXIF信息的丢失。上述的这些工具在处理照片的时候都有意无意地忽略了EXIF，让人很郁闷（令人感到惊奇的是，粗糙的windows画图板在缩放、保存图片的时候EXIF信息是不会丢失的）。
最近处理WHUMSTC10周年party照片的时候就遇到这个问题。照片总共有605张，使用Canon 450D最高分辨率拍摄，一共2.4G+，一张照片平均有4MB。通过QQ影像压缩到原来的1/4，并且压缩质量调整为85%，所有照片的体积立即缩小为176M左右。但是EXIF信息的丢失，使得很有含金量的“照片拍摄时间”也随之丢失。
于是试着去解决。本来想用PHP自带的EXIF库（最熟PHP，没办法-.-），但是发现它只支持Read，不支持Write。又找了找PYTHON的，挺多，但是用起来总不对头，就没继续折腾。最后还是在Ubuntu下apt-cache search exif，发现了exiv2这个实用工具，非常赞。
对一张照片处理，执行：
引用
$ exiv2 ex xxx.jpg
引用
exiv2 in xxx.jpg
需要批量处理的话，完整过程是这样：
1. 使用QQ影像或者使用命令行的ImageMagick将src/*.jpg压缩转换，保存到dest/*.jpg。注意相同文件的文件名保持不变。
2. 在src下面执行
引用
~/src$ exiv2 ex *.jpg
3. 将所有exv文件拷贝到dest文件夹
引用
~/src$ mv *.exv ~/dest
4. 恢复exif信息
引用
~/dest$ exiv2 in *.jpg
如果是windows，可以從這裡下載exiv2的可執行文件：http://www.exiv2.org/download.html ；如果有Ubuntu的話，直接apt-get install exiv2就好，當然也可以自己編譯安裝，只要身體裡兩個圓形的器官不會隱隱作痛就行。。
終り.
Nov
8
2年多以前看的算法，当时基本看懂了（实际上还是有问题的），今天再翻出来，感觉基本忘了，重新实现一遍，试着自己把推导过程也写写。非常赞的算法。
RMQ: Range Minimum Query, 区间最小值查询。已知数组在区间 [0, n) 有定义，给出 i, j (0 <= i < j <=n)，求 [i, j) 之间的最小值。
朴素算法非常简单，但是显然，每次查询是O(N)的，效率很低：
由于经常遇到需要多次查询的情况，所以朴素算法不合意。一个比较好的改进是使用线段树/树状数组，首先通过O(NlogN)预处理，让每个分支节点保存了其所有叶子节点的最小值（由底向上递推)。这样每次查询的时候，就可以在O(logN)的时间内得到结果。具体代码稍繁琐，这里不写了。
最好的方法，是用叫做sparse_table的算法，其思路和线段树很像，区别是通过O(NlogN)的预处理，可以让查询的时间复杂度降低到O(1)。其具体思路为：
预处理：
1. 记F[s][p] = min{ arr[i] | s <= i < s + 2^p} = min(arr[s..(s + 2^p - 1)])。例如， F[1][2] = min{ arr[i] | 1<= i < 5} = min(arr[1..4])。
2. 由1，易推知，F[s][0] = min { arr[i] | s <= i < s + 1} = arr[s].
3. 通过由底向上递推的预处理得到所有满足（s + 2^p <= n, 即区间[s, s + 2^p) 包含于[0..n)区间内）的F[s][p] = min(F[s][p-1], F[s+2^(p-1)][p-1])。例如， F[2][3] = min(arr[2..9]) = min(min(arr[2..5]), min(arr[6..9])) = min(F[2][2], F[6][2]) = min(F[2][3-1], F[2 + 2^(3-1)][3-1])。
查询[i, j)：
1. 令 k = log2(j - i)取整，则 (j - 2^k) <= (i + 2^k)，即区间 [i, i + 2^k) 和 [j - 2^k, j) 必定覆盖 [i, j)。例如，区间[3, 8)，k = log2(8-3)取整 = 2，则 [3, 7), [4, 8) 覆盖 [3, 8)。
2. RMQ[i, j) = min(F[i][k], F[j - 2^k][k]).
----扩展---
LCA（树中任意两个节点的最近公共祖先）问题，是可以通过RMQ+DFS来完成的，详见LCA问题。ZOJ 1141是一道纯LCA问题。
具体实现和检验代码如下（做了一点改进，F[s][p]中存放的是[s, s + 2^p)中最小值在数组中的索引）：
RMQ: Range Minimum Query, 区间最小值查询。已知数组在区间 [0, n) 有定义，给出 i, j (0 <= i < j <=n)，求 [i, j) 之间的最小值。
朴素算法非常简单，但是显然，每次查询是O(N)的，效率很低：
min = +INFINITE
FOR k = i TO j - 1
IF min > arr[k]
min = arr[k]
END IF
END FOR
RETURN min
FOR k = i TO j - 1
IF min > arr[k]
min = arr[k]
END IF
END FOR
RETURN min
由于经常遇到需要多次查询的情况，所以朴素算法不合意。一个比较好的改进是使用线段树/树状数组，首先通过O(NlogN)预处理，让每个分支节点保存了其所有叶子节点的最小值（由底向上递推)。这样每次查询的时候，就可以在O(logN)的时间内得到结果。具体代码稍繁琐，这里不写了。
最好的方法，是用叫做sparse_table的算法，其思路和线段树很像，区别是通过O(NlogN)的预处理，可以让查询的时间复杂度降低到O(1)。其具体思路为：
预处理：
1. 记F[s][p] = min{ arr[i] | s <= i < s + 2^p} = min(arr[s..(s + 2^p - 1)])。例如， F[1][2] = min{ arr[i] | 1<= i < 5} = min(arr[1..4])。
2. 由1，易推知，F[s][0] = min { arr[i] | s <= i < s + 1} = arr[s].
3. 通过由底向上递推的预处理得到所有满足（s + 2^p <= n, 即区间[s, s + 2^p) 包含于[0..n)区间内）的F[s][p] = min(F[s][p-1], F[s+2^(p-1)][p-1])。例如， F[2][3] = min(arr[2..9]) = min(min(arr[2..5]), min(arr[6..9])) = min(F[2][2], F[6][2]) = min(F[2][3-1], F[2 + 2^(3-1)][3-1])。
查询[i, j)：
1. 令 k = log2(j - i)取整，则 (j - 2^k) <= (i + 2^k)，即区间 [i, i + 2^k) 和 [j - 2^k, j) 必定覆盖 [i, j)。例如，区间[3, 8)，k = log2(8-3)取整 = 2，则 [3, 7), [4, 8) 覆盖 [3, 8)。
2. RMQ[i, j) = min(F[i][k], F[j - 2^k][k]).
----扩展---
LCA（树中任意两个节点的最近公共祖先）问题，是可以通过RMQ+DFS来完成的，详见LCA问题。ZOJ 1141是一道纯LCA问题。
具体实现和检验代码如下（做了一点改进，F[s][p]中存放的是[s, s + 2^p)中最小值在数组中的索引）：
Nov
2
C标准中的qsort函数，可以对任意类型的数组进行快速排序，用起来也还算方便，不过行为有一点诡异。加上之前曾经看过一篇文章（沈大写的，曾经登上过ecom的双周刊，居然在这个youalab.com也等出来了-。-），说是qsort不是线程安全的，所以把glibc的代码翻出来，看看qsort的具体实现。
用Ubuntu的话，找代码就很容易了：
可以看到qsort是在stdlib.h里面的，源码在msort.c 302行，调用了qsort_r函数：
qsort_r函数也在msort.c中，约164行起。为了榨干CPU的性能，写了很多代码来优化效率，其流程大致是：
1. 判断额外所需内存大小，如果很小(<1024B)，在栈上分配；否则获取系统内存参数——如果比可用内存小，试图在堆上分配；如果所需内存超过物理内存（为防出现不得不使用交换分区的情况致使性能恶化，故不分配），或者分配失败（可用空间不足），使用性能较差的stdlib/qsort.c中的_quicksort函数来排序。
1.1. _quicksort位于 stdlib/qsort.c，对快排进行了两个改进：1. 将递归转化为递推; 2. 使用插入排序来处理4个元素以内的区间。不过用于交换两个元素的宏SWAP(a, b, size)没有额外的优化，比较意外（本来以为会考虑一次多个字节拷贝，或者使用duff device来减少循环）。
2. 分配成功的情况下，使用额外分配的空间，调用 msort_with_tmp() 函数来进行排序。
2.1. 如果单个元素的大小超过32个字节，那么使用间接排序，分配空间时就有额外的判断，如果需要间接排序，则额外分配2n个指针的空间，前n个空间用于存放原指针，后n个空间用于按照所指元素大小存放排序好的指针。最后再按照排序好的指针顺序将元素拷贝。(注释中提到了Knuth vol. 3 (2nd ed.) exercise 5.2-10.，应该是指这个算法出自Knuth的《The Art of Computer Programming》卷3吧)
2.2. 否则使用直接排序。这里也进行了一些优化，主要是为msort_with_tmp()提供p.var参数，完成针对元素的大小进行拷贝的优化：默认是使用gcc内置的__builtin_mempcpy来拷贝。
2.3. msort_with_tmp对典型的快排也进行了非常赞的优化。
2.3.1. 从msort_with_tmp的函数名和代码可以看出，这个算法不是就地排序，而是使用了第一步分配的O(N)的额外空间，这样可以让排序时的拷贝效率更高（这个优化应该对CPU的cache命中率也有较大的提高）。
2.3.2. qsort_r传进来的参数p有个属性var
(1) 默认情况下p.var = 4，使用mempcpy来进行拷贝。
(2) 如果单个元素大于32bytes，p.var = 3, 表示是间接排序，拷贝的是指针，不是元素
(3) 如果数组是按uint32_t对其的，且元素的大小是uint32_t的倍数，则可以进一步优化到每次按照uint32_t/uint64_t/unsigned long来进行拷贝，一次拷贝4或者8个字节，此时p.var = 0,1,2表示按照uint32_t, uint64_t, unsigned long拷贝。
直接在里头做了些注释，有兴趣的话可以更仔细地看看。可以的话自己去下了glibc的源码阅读，更有意思:D
用Ubuntu的话，找代码就很容易了：
引用
$ apt-get source libc6
$ cd eglibc-xxxx
$ grep -r . -Hne qsort | grep void
$ cd eglibc-xxxx
$ grep -r . -Hne qsort | grep void
可以看到qsort是在stdlib.h里面的，源码在msort.c 302行，调用了qsort_r函数：
void
qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
{
return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
}
其中__compar_fn_t就是 int (*)(const void *, const void *)类型的函数指针，__compar_d_fn_t则是 int (*)(const void *, const void *, void *)类型的函数指针(为什么还有个void *呢?很神奇~求解)。qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
{
return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);
}
qsort_r函数也在msort.c中，约164行起。为了榨干CPU的性能，写了很多代码来优化效率，其流程大致是：
1. 判断额外所需内存大小，如果很小(<1024B)，在栈上分配；否则获取系统内存参数——如果比可用内存小，试图在堆上分配；如果所需内存超过物理内存（为防出现不得不使用交换分区的情况致使性能恶化，故不分配），或者分配失败（可用空间不足），使用性能较差的stdlib/qsort.c中的_quicksort函数来排序。
1.1. _quicksort位于 stdlib/qsort.c，对快排进行了两个改进：1. 将递归转化为递推; 2. 使用插入排序来处理4个元素以内的区间。不过用于交换两个元素的宏SWAP(a, b, size)没有额外的优化，比较意外（本来以为会考虑一次多个字节拷贝，或者使用duff device来减少循环）。
2. 分配成功的情况下，使用额外分配的空间，调用 msort_with_tmp() 函数来进行排序。
2.1. 如果单个元素的大小超过32个字节，那么使用间接排序，分配空间时就有额外的判断，如果需要间接排序，则额外分配2n个指针的空间，前n个空间用于存放原指针，后n个空间用于按照所指元素大小存放排序好的指针。最后再按照排序好的指针顺序将元素拷贝。(注释中提到了Knuth vol. 3 (2nd ed.) exercise 5.2-10.，应该是指这个算法出自Knuth的《The Art of Computer Programming》卷3吧)
2.2. 否则使用直接排序。这里也进行了一些优化，主要是为msort_with_tmp()提供p.var参数，完成针对元素的大小进行拷贝的优化：默认是使用gcc内置的__builtin_mempcpy来拷贝。
2.3. msort_with_tmp对典型的快排也进行了非常赞的优化。
2.3.1. 从msort_with_tmp的函数名和代码可以看出，这个算法不是就地排序，而是使用了第一步分配的O(N)的额外空间，这样可以让排序时的拷贝效率更高（这个优化应该对CPU的cache命中率也有较大的提高）。
2.3.2. qsort_r传进来的参数p有个属性var
(1) 默认情况下p.var = 4，使用mempcpy来进行拷贝。
(2) 如果单个元素大于32bytes，p.var = 3, 表示是间接排序，拷贝的是指针，不是元素
(3) 如果数组是按uint32_t对其的，且元素的大小是uint32_t的倍数，则可以进一步优化到每次按照uint32_t/uint64_t/unsigned long来进行拷贝，一次拷贝4或者8个字节，此时p.var = 0,1,2表示按照uint32_t, uint64_t, unsigned long拷贝。
直接在里头做了些注释，有兴趣的话可以更仔细地看看。可以的话自己去下了glibc的源码阅读，更有意思:D
Nov
2
上一篇谈到：“典型的情况是某些非法内存访问，Glibc会open("/dev/tty",...)，write()一些错误信息，然后open("/proc/self/maps", ...)把进程的内存映射表输出。还有一个更常见的情况，那就是用qsort。GCC的qsort实现，会主动open(/proc/meminfo)，获取一些信息，通过这些信息来最优化排序时的内存管理。” 通过执行
对于这类情况，ptrace监控进程open系统调用，并获取文件名，检查文件名是否合法，如果合法，予以放行，这样就可以避免上述RE被误判为RF的情况了。
说起来很简单，但是具体做起来就有点麻烦。不过可以从我写woj-land的时候参考的ptrace教程《Playing with ptrace, 玩转ptrace》入手。这篇非常不错，强烈推荐有兴趣的同学学习学习：
Playing with ptrace, Part I — 玩转ptrace(一) http://www.kgdb.info/gdb/playing_with_ptrace_part_i/
Playing with ptrace, Part II — 玩转ptrace(二) http://www.kgdb.info/gdb/playing_with_ptrace_part_ii/
上篇以write系统调用为例，介绍了write系统调用的等价汇编码（当然是早期的了，现在的pc上linux貌似不用0x80了）、截获write系统调用，获取write系统调用的参数和返回值、甚至反转write系统调用的输出。具体的看原文了。
在这里，我需要peek的是read系统调用的参数。以x86为例，一个最简单的read系统调用：
注意：虽然ebx中存放的是地址，但是不是用户程序可以直接读取的，需要通过ptrace的PTRACE_PEEKDATA命令来获取。该命令一次可以获取sizeof(long)个字节的内容，如果要获取字符串的所有内容，就得通过循环来完成。
此外，为了保证代码能够在x86_64架构下通过编译，需要把上述代码做个小修改：
通过这种方式，能够识别出open系统调用打开的文件，在保证系统安全的情况下，改善了Judge的识别能力。
更具体的代码可以参见：
http://code.google.com/p/woj-land/source/browse/trunk/code/judge/judge.h?spec=svn150&r=150#671
strace ./a.out 2>&1 | grep open
可以看到进程执行的open系统调用。对于这类情况，ptrace监控进程open系统调用，并获取文件名，检查文件名是否合法，如果合法，予以放行，这样就可以避免上述RE被误判为RF的情况了。
说起来很简单，但是具体做起来就有点麻烦。不过可以从我写woj-land的时候参考的ptrace教程《Playing with ptrace, 玩转ptrace》入手。这篇非常不错，强烈推荐有兴趣的同学学习学习：
Playing with ptrace, Part I — 玩转ptrace(一) http://www.kgdb.info/gdb/playing_with_ptrace_part_i/
Playing with ptrace, Part II — 玩转ptrace(二) http://www.kgdb.info/gdb/playing_with_ptrace_part_ii/
上篇以write系统调用为例，介绍了write系统调用的等价汇编码（当然是早期的了，现在的pc上linux貌似不用0x80了）、截获write系统调用，获取write系统调用的参数和返回值、甚至反转write系统调用的输出。具体的看原文了。
在这里，我需要peek的是read系统调用的参数。以x86为例，一个最简单的read系统调用：
read("/proc/meminfo", O_RDONLY)
，大致等同于movl $5, %eax ;open的系统调用编号
movl $filename, %ebx ;文件名地址(这里不一定对)
movl $0, %ecx ;open的flags: O_RDONLY
int $0x80
也就是说，可以通过获取x86 CPU寄存器的值来取得系统调用的参数，具体代码如下：movl $filename, %ebx ;文件名地址(这里不一定对)
movl $0, %ecx ;open的flags: O_RDONLY
int $0x80
user_regs_struct regs;
ptrace(PTRACE_GETREGS, child, NULL, ®s);
syscall_id = regs.orig_eax; //因为eax也是用来填写函数返回值的，所以该struct额外增加了一个orig_eax
params[0] = regs.ebx;
params[1] = regs.ecx;
union u{ unsigned long val; char chars[sizeof(long)]; }data;
data.val = ptrace(PTRACE_PEEKDATA, child, params[0], NULL);
ptrace(PTRACE_GETREGS, child, NULL, ®s);
syscall_id = regs.orig_eax; //因为eax也是用来填写函数返回值的，所以该struct额外增加了一个orig_eax
params[0] = regs.ebx;
params[1] = regs.ecx;
union u{ unsigned long val; char chars[sizeof(long)]; }data;
data.val = ptrace(PTRACE_PEEKDATA, child, params[0], NULL);
注意：虽然ebx中存放的是地址，但是不是用户程序可以直接读取的，需要通过ptrace的PTRACE_PEEKDATA命令来获取。该命令一次可以获取sizeof(long)个字节的内容，如果要获取字符串的所有内容，就得通过循环来完成。
此外，为了保证代码能够在x86_64架构下通过编译，需要把上述代码做个小修改：
#if __WORDSIZE == 32
syscall_id = regs.orig_eax;
params[0] = regs.ebx;
params[1] = regs.ecx;
#else
syscall_id = regs.orig_rax;
params[0] = regs.rdi;
params[1] = regs.rsi;
#endif
syscall_id = regs.orig_eax;
params[0] = regs.ebx;
params[1] = regs.ecx;
#else
syscall_id = regs.orig_rax;
params[0] = regs.rdi;
params[1] = regs.rsi;
#endif
通过这种方式，能够识别出open系统调用打开的文件，在保证系统安全的情况下，改善了Judge的识别能力。
更具体的代码可以参见：
http://code.google.com/p/woj-land/source/browse/trunk/code/judge/judge.h?spec=svn150&r=150#671
Nov
1
因为这两个东西占了地方，每次选盘符时总需要往下拉滚动条，很不爽。在网上搜到3篇文章，这里转载记录一下。
http://bbs.pcbeta.com/viewthread.php?tid=729301
http://bbs.pcbeta.com/viewthread.php?tid=729310
http://bbs.pcbeta.com/viewthread.php?tid=733262
“库” @ [HKEY_CLASSES_ROOT\CLSID\{031E4825-7B94-4dc3-B131-E946B44C8DD5}]
“家庭组” @ [HKEY_CLASSES_ROOT\CLSID\{B4FB3F98-C1EA-428d-A78A-D1F5659CBA93}]
修改注册表这里，需要右键->权限，给Administrators “完全控制” 的权限。
如果需要去掉这两项的显示，分别把键值 ShellFolder\Attributes 由原来的 b080010d 改为 b090010d，然后注销（其实Kill掉explorer也行）就行了。如果不想去掉显示，那么修改 SortOrderIndex 键值（默认是0x42、0x43），改到0x52或者更大，就会排到“计算机”后面了。
http://bbs.pcbeta.com/viewthread.php?tid=729301
http://bbs.pcbeta.com/viewthread.php?tid=729310
http://bbs.pcbeta.com/viewthread.php?tid=733262
“库” @ [HKEY_CLASSES_ROOT\CLSID\{031E4825-7B94-4dc3-B131-E946B44C8DD5}]
“家庭组” @ [HKEY_CLASSES_ROOT\CLSID\{B4FB3F98-C1EA-428d-A78A-D1F5659CBA93}]
修改注册表这里，需要右键->权限，给Administrators “完全控制” 的权限。
如果需要去掉这两项的显示，分别把键值 ShellFolder\Attributes 由原来的 b080010d 改为 b090010d，然后注销（其实Kill掉explorer也行）就行了。如果不想去掉显示，那么修改 SortOrderIndex 键值（默认是0x42、0x43），改到0x52或者更大，就会排到“计算机”后面了。
