Dec
8
在有些算法中，比较关键的步骤包含了少量数据的处理。以拷贝为例，在这种情况下如果可以进行优化，也能带来不错的效率提升。
假设有2个数组 int a[100], b[100]; 想把a的数据拷贝到b中去，作为一个ACMer可能会想用最简洁的方式来实现：
这一句最便捷了，不过效率上应当是不如一个循环(后注：这里可能有误导，参见后文)：
循环的效率是比较低的。由此可以想到，如果每次循环的时候拷贝多一点，减少循环次数，也能够提高效率。假设是32bit的机器，用int拷贝基本上就把CPU指令集的效率挖得差不多了（如果不考虑SIMD指令的情况），更进一步的话，则考虑用顺序结构取代循环：
当然，极端情况可以写100个顺序语句出来，就是繁琐了一点，这里取4，主要是方便演示代码。对于n比较大的情况，全部写出来效果不一定好（不一定所有代码/数据都能放进CPU的一级缓存）；如果n特别大，基本上取决于内存的限制，这个优化就不明显了。对于不够整(n % 4 != 0)的情况，可以先把整的那一部分拷贝完毕，然后再用一个小循环把剩余的拷贝完：
看到这里可能你就会想起duff's device(达夫设备)，思路上与上面的代码一致，就是实现起来很独特:
http://triviasecurity.com.ru/file/Exploitation/Generic%20Programming%20Typed%20Buffers.htm
这个链接里面提到一个关于memcpy的情况：对于x86 CPU，memcpy很可能是使用REP STOS这样的指令实现的，效率应当比一个简单的for循环要高。
以上是对于较小的n的说明，关于大量拷贝更细致的优化，可以参考Glibc中qsort的实现。在一些情况下，我们会遇到很小的n，比如小于10。这时如果不写循环，而是直接写死代码，是个可行的优化。举个例子：
但是对于可能会变化的n值呢？这时候如果能够允许程序在执行过程中生成可执行代码，是最好不过了，不过对于编译型的代码，这个实现起来比较有难度；而解释型的语言，这个优化又不是很有必要。想了想，在C中的一个替代方案是，写n个函数，保存在函数指针数组中，n作为索引来进行调用。
思源枯竭，到此为止。
假设有2个数组 int a[100], b[100]; 想把a的数据拷贝到b中去，作为一个ACMer可能会想用最简洁的方式来实现：
memcpy(b, a, sizeof(a));
这一句最便捷了，
for (i = 0; i < 100; i++) b[i] = a[i];
毕竟这个只需要100个循环，每次拷贝sizeof(int)个字节，而memset则是执行100*sizeof(int)个字节。循环的效率是比较低的。由此可以想到，如果每次循环的时候拷贝多一点，减少循环次数，也能够提高效率。假设是32bit的机器，用int拷贝基本上就把CPU指令集的效率挖得差不多了（如果不考虑SIMD指令的情况），更进一步的话，则考虑用顺序结构取代循环：
for (i = 0; i < 100; )
b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++;
b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++;
当然，极端情况可以写100个顺序语句出来，就是繁琐了一点，这里取4，主要是方便演示代码。对于n比较大的情况，全部写出来效果不一定好（不一定所有代码/数据都能放进CPU的一级缓存）；如果n特别大，基本上取决于内存的限制，这个优化就不明显了。对于不够整(n % 4 != 0)的情况，可以先把整的那一部分拷贝完毕，然后再用一个小循环把剩余的拷贝完：
int loops = n - n % 4, i = 0;
while (i < loops)
b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++;
for (i = loops * 4; i < n; i++) b[i] = a[i]
while (i < loops)
b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++, b[i] = a[i], i++;
for (i = loops * 4; i < n; i++) b[i] = a[i]
看到这里可能你就会想起duff's device(达夫设备)，思路上与上面的代码一致，就是实现起来很独特:
void* duffcpy(char *to, char *from, int count) {
register int n = (count + 7) / 8; /* 假定 count > 0 */
switch (count % 8) {
case 0:do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while (--n > 0);
}
return to;
}
p.s. 这个代码虽然很奇怪（如果你之前没看过，建议再看一遍），但是 是可以编译运行的；拷贝并修改自 http://c-faq-chn.sourceforge.net/ccfaq/node380.html；这是某次极限编程比赛的代码，比较有争议，如果你觉得很有意思，可以看看这里进一步的说明和比较：register int n = (count + 7) / 8; /* 假定 count > 0 */
switch (count % 8) {
case 0:do { *to = *from++;
case 7: *to = *from++;
case 6: *to = *from++;
case 5: *to = *from++;
case 4: *to = *from++;
case 3: *to = *from++;
case 2: *to = *from++;
case 1: *to = *from++;
} while (--n > 0);
}
return to;
}
http://triviasecurity.com.ru/file/Exploitation/Generic%20Programming%20Typed%20Buffers.htm
这个链接里面提到一个关于memcpy的情况：对于x86 CPU，memcpy很可能是使用REP STOS这样的指令实现的，效率应当比一个简单的for循环要高。
以上是对于较小的n的说明，关于大量拷贝更细致的优化，可以参考Glibc中qsort的实现。在一些情况下，我们会遇到很小的n，比如小于10。这时如果不写循环，而是直接写死代码，是个可行的优化。举个例子：
int sum = 0;
for (i = 0; i < 4; i++)
for (j = i + 1; j < 4; j++)
sum += x[i][j];
在这段代码中，实际只需要执行6次加法运算，但是却有两层循环，在循环上带来了大量的开销。如果把循环直接展开，则会得到很好的效果：for (i = 0; i < 4; i++)
for (j = i + 1; j < 4; j++)
sum += x[i][j];
sum = x[0][1]+x[0][2]+x[0][3]+x[1][2]+x[1][3]+x[2][3];
但是对于可能会变化的n值呢？这时候如果能够允许程序在执行过程中生成可执行代码，是最好不过了，不过对于编译型的代码，这个实现起来比较有难度；而解释型的语言，这个优化又不是很有必要。想了想，在C中的一个替代方案是，写n个函数，保存在函数指针数组中，n作为索引来进行调用。
思源枯竭，到此为止。
Dec
2
Ubuntu Server 10.04 x86和x86_64下是8MB，RHEL4 x86下是10MB。开线程的开销真大。
#include <pthread.h>
#include <stdio.h>
void *thread(void *arg)
{
size_t stacksize;
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_getstacksize (&attr, &stacksize);
printf("Default stack size = %lu KB\n", stacksize / 1024);
}
int main(int argc, char *argv[])
{
void *x;
pthread_t t;
pthread_create(&t, NULL, thread, NULL);
pthread_join(t, &x);
return 0;
}
#include <stdio.h>
void *thread(void *arg)
{
size_t stacksize;
pthread_attr_t attr;
pthread_attr_init(&attr);
pthread_attr_getstacksize (&attr, &stacksize);
printf("Default stack size = %lu KB\n", stacksize / 1024);
}
int main(int argc, char *argv[])
{
void *x;
pthread_t t;
pthread_create(&t, NULL, thread, NULL);
pthread_join(t, &x);
return 0;
}
Dec
2
前一阵发现"gcc -static -lm a.c"总是会出现编译错误，后来不得已改成"gcc -static -lm a.c /usr/lib/libm.a"，才通过，也算是歪打正着。最近int ijk同学在使用我的woj-land，给我反馈了这个BUG，mark一下，并查到了原始文档，详情如下：
zz from http://gcc.gnu.org/onlinedocs/gcc/Link-Options.html
3.13 Options for Linking
......
-llibrary
-l library
Search the library named library when linking. (The second alternative with the library as a separate argument is only for POSIX compliance and is not recommended.)
It makes a difference where in the command you write this option; the linker searches and processes libraries and object files in the order they are specified. Thus, `foo.o -lz bar.o' searches library `z' after file foo.o but before bar.o. If bar.o refers to functions in `z', those functions may not be loaded.
The linker searches a standard list of directories for the library, which is actually a file named liblibrary.a. The linker then uses this file as if it had been specified precisely by name.
The directories searched include several standard system directories plus any that you specify with -L.
Normally the files found this way are library files—archive files whose members are object files. The linker handles an archive file by scanning through it for members which define symbols that have so far been referenced but not defined. But if the file that is found is an ordinary object file, it is linked in the usual fashion. The only difference between using an -l option and specifying a file name is that -l surrounds library with `lib' and `.a' and searches several directories.
zz from http://gcc.gnu.org/onlinedocs/gcc/Link-Options.html
3.13 Options for Linking
......
-llibrary
-l library
Search the library named library when linking. (The second alternative with the library as a separate argument is only for POSIX compliance and is not recommended.)
It makes a difference where in the command you write this option; the linker searches and processes libraries and object files in the order they are specified. Thus, `foo.o -lz bar.o' searches library `z' after file foo.o but before bar.o. If bar.o refers to functions in `z', those functions may not be loaded.
The linker searches a standard list of directories for the library, which is actually a file named liblibrary.a. The linker then uses this file as if it had been specified precisely by name.
The directories searched include several standard system directories plus any that you specify with -L.
Normally the files found this way are library files—archive files whose members are object files. The linker handles an archive file by scanning through it for members which define symbols that have so far been referenced but not defined. But if the file that is found is an ordinary object file, it is linked in the usual fashion. The only difference between using an -l option and specifying a file name is that -l surrounds library with `lib' and `.a' and searches several directories.
Dec
1
防火墙只开了80端口，因此在外网连接服务器的ssh比较麻烦。不过可以通过apache提供的proxy模块来绕过这个限制。
在Ubuntu下面：
$ sudo a2enmod proxy
$ sudo a2enmod proxy_connect
$ vi /etc/apache2/mod-enabled/proxy.conf
$ sudo apache2ctl restart
然后就可以通过apache提供的http代理来连接服务器的22端口了。
因为ProxyRequests On，以及AllowConnect 22，所以可连到任意网站22端口，所以最好在Allow from all上面做一点限制，避免这个http proxy被滥用。如果需要访问其他服务，可以在AllowConnect后面增加更多端口，比如AllowConnect 22 443，这样就支持https的代理了。
在Ubuntu下面：
$ sudo a2enmod proxy
$ sudo a2enmod proxy_connect
$ vi /etc/apache2/mod-enabled/proxy.conf
引用
<IfModule mod_proxy.c>
ProxyRequests On
<Proxy *>
AddDefaultCharset off
Order deny,allow
Allow from all
</Proxy>
ProxyVia On
AllowConnect 22
</IfModule>
ProxyRequests On
<Proxy *>
AddDefaultCharset off
Order deny,allow
Allow from all
</Proxy>
ProxyVia On
AllowConnect 22
</IfModule>
$ sudo apache2ctl restart
然后就可以通过apache提供的http代理来连接服务器的22端口了。
因为ProxyRequests On，以及AllowConnect 22，所以可连到任意网站22端口，所以最好在Allow from all上面做一点限制，避免这个http proxy被滥用。如果需要访问其他服务，可以在AllowConnect后面增加更多端口，比如AllowConnect 22 443，这样就支持https的代理了。
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
