Felix021

前些天写的程序在上线的时候出现BUG了，错误提示就是call_user_func_array无法调用指定的函数。

代码大概是这样的


追了一下发现是PHP版本的问题，开发环境使用的是php 5.2.17，而线上环境是旧版本的5.1.6。5.1版的php的call_user_func / call_user_func_array函数没法调用类的静态函数，所以出现了这个问题。

没有很好的解决方法，大致就是

1. 升级PHP（最后我们是这么做的）

2. 使用字符串拼出一段php代码，然后用eval来执行。很挫，但是也能用。

本文转自 酷壳(Coolshell.cn) http://coolshell.cn/articles/4102.html  酷壳这个网站非常不错，推荐大家订阅。

-----------------

有人在酷壳的留言版上询问下面的问题

  keep_walker :
    今天晚上我看到这篇文章。
      http://programmers.stackexchange.com/questions/62502/small-c-projects
    我也遇到了和提问的老外一样的问题。。能给像遇到这样烦恼的程序员一点建议嘛？谢谢！

我相信，这可能是很多朋友的问题，我以前也有这样的感觉，编程编到一定的时候，发现能力到了瓶颈，既不深，也不扎实，半吊子。比如：你长期地使用Java和.NET ，这些有虚拟机的语言对于开发便利是便利，但是对于程序员来说可能并不太好，原因有两个：

1. 虚拟机屏蔽了操作系统的系统调用，以及很多底层机制。
2. 大量的封装好的类库也屏蔽了很多实现细节。

一段时间后，你会发现你知其然，不知所以然。。我以前在CSDN上写过一篇《Java NIO类库Selector机制解析（上，下，续）》，在那篇文章中我说提到过（有讥讽的语气）Java的程序员不懂底层实现，所以很难把技术学得更扎实。此时，一部分程序员会不自然地想学学底层的技术，很自然的，C语言就被提了上来。


下面是我给这位朋友的一些建议：

· 鼓励并为你叫好。我鼓励你想要去学C语言的想法和精神，很多人都觉得C语言好学，其实并不然，现在的这个社会更多地去关注那些时髦的技术，而忽略了这个流行了40+年的C语言。一门技术如果能够流行40多年，这才是你需要去关注和学习的技术，而不是那些刚出来的技术（过度炒作的技术，Windows编程史）。这才是踏踏实实的精神。

· 不要找借口。这一条路走下来并不容易，不要给自己找借口。我最不喜欢听到的就是“很忙，没有时间”这样的借口。我以前在银行做项目，早9点到晚10点，周一到周六，我一样可以每天抽1个小时来看书和专研，一年下来也能精读5、6本书。我现在的工作项目和招聘任务很紧张，刚生的小孩只有自己和老婆两人带，还需要准备讲课，但是我还是能够找到时间看文章写文章维护酷壳。所以，我可以告诉你，“时间就像乳沟，只要你肯挤，就一定会有”。

· 学好C语言和系统编程。我认为，学好编程有四个方面：语言、算法和数据结构、系统调用和设计。

  ·· 语言。我可以告诉你C语言有两大主题你要好好学，一个是内存管理，一个是指针！这个世界上90%以上的C/C++出的严重性错误全是和这两个有关。不要看谭浩强的那本书，那本是本烂书。推荐这本书给你《C程序设计语言（第2版·新版）》

  ·· 算法和数据结构。我认为，用C语言实现算法和数据结构莫过于最爽的事情。推荐你看这本书——算法:C语言实现(第1～4部分)基础知识、数据结构、排序及搜索(原书第3版)

  ·· 系统编程。Windows下推荐两本书——《Windows 程序设计 》和《Windows核心编程》，Unix/Linux下推荐两本书——《Unix高级环境编程》和《Unix网络编程卷1，套接字》《Unix网络编程卷2，进程间通信》尤其是《Unix网络编程》这本书，一通百通，无论Windows还是Unix/Linux，都是一样的。

  ·· 系统设计。关于设计方面，我全力推荐《Unix编程艺术》，看完以后，你就明白什么是真正的编程文化了。然后，当你看到Windows的Fans的某些言论时，你就知道什么叫一笑了之了。

如果你能在2-3年内精读完这些书，并全部融会贯通，那么你就明白什么是一览众山小的感觉了！我足足花了5年时间才算是真正全部读完这些书的。最后，祝你好运！努力！

今天跟Sandy讨论的时候发现的这两个trick。其中第一个trick以前曾经知道，不过太久没用，忘了；第二个trick一直就没发现。

1. make_heap、push_heap、pop_heap默认与其他STL算法一样使用 operator < 进行比较，但是建立的是大根堆，也就是说，pop_heap取出的是heap中的最大值。

2. 在调用sort_heap(begin, end, comparor) 之前，需要保证 [begin, end) 之间是使用同一个 comparor 建立的heap。默认的排序也是使用 operator < ，效果与调用sort是一致的（即默认从小到大排序）：【不要以为】make_heap默认是大根堆，sort_heap就会从大到小排序。可参见源码：

-----

以下是sandy整理的

想起第一届Eming杯是我办的，真感慨。这次eming杯的时候我在8-活-601，WHU-WLAN非常烂，开始一个小时候才在窗台上连上。

蛋疼随便写点。

1001. 简单题，不过不知道到底有多简单，反正我是按高精度来做的，而且还考虑了正负号。

1002. 知道矩形的两个端点求面积，非常简单 fabs(x1-x2)*fabs(y1-y2);

1003. 计算元音字母的次数，考虑到大小写就行了，直接用getchar实现非常方便。

1004. 计算几何，虽然跟1002一样是有图的，但是此"图"非彼"图"，嗯。半平面交，注意考虑特殊情况（主要是三点共线）。我有另外2种算法，一个是，求出三角形两个中垂线的焦点（就是外接圆圆心）以及与四边的焦点，然后求那个多边形的面积，由于没有计算几何标称，作罢；另外一个算法是伪蒙特卡洛，计算计算平均分布的200w个点与三个点的距离，然后除以200w，可以满足三位数的精度。

1005. 这题O(N)枚举就行。O(N^2)也可以过，不过要优化常数，否则会TLE。

1006. 1005加强版，基于一个代数不等式，不断迭代收敛。岩哥给我讲过，但是记不太清了。

1007. DP（即动态规划），不太会，掠过。

其实是个比较简单的数据结构了，引用百度百科给出的说明，其对应的问题是：不断地向buffer里读入元素，也不时地去掉最老的元素（ buffer 的大小取决于移除最老元素的策略，可以是不定长的；下文假定是固定为K的），不定期的询问当前buffer里的最小的元素。

使用普通队列来实现，每个元素O(1)的操作，每次查询O(K)；用堆实现的话，每次查询是O(1)，但是每个元素是O(logK)。还有其他的实现方式，比如线段树，或者RMQ，这些都是logN量级的。

而单调队列的优势则是，每个元素是O(1)的操作，又能保证最小元素像堆一样在最前面，也就是每次查询O(1)。具体的实现也非常简单，不过它并不是通常意义上理解的队列。

以此为例：对于N=8，K=3，8个元素序列1 3 -1 -3 5 3 6 7，窗口大小为3，也就是要求出(1, 3, -1), (3, -1, -3), (-1, -3, 5), (-3, 5, 3), (5, 3, 6), (3, 6, 7)这6个序列中的最小值，结果简单，就是-1, -3, -3, -3, 3, 3.

使用单调队列，首先要有一个数据结构用于记录队列中的元素及其在输入序列中的顺序。队列的状态是这样维护的：

1: [0,  1] //队列空，[seq=0, val=1]入队
3: [0,  1], [1,  3] //3大于队尾元素，放在队尾
-1: [2, -1] //从队尾往前扫，-1小于每一个所有元素，于是把它们都T掉
-3: [3, -3] //-3把-1T掉
5: [3, -3], [4,  5] //入队尾
3: [3, -3], [5,  3] //把队尾的5T掉
6:            [5,  3], [6,  6] //队首元素seq=3太老了，T掉；6比3小，放在队尾
7: [5,  3], [6,  6], [7,  7] //入队尾

从以上的处理方法可以看出：最老的元素要么早就被T掉了，要么就是最小的元素（排在队首）。所以每次加入一个新元素的时候:
1. 把需要出队的队首元素T掉；
2. 把队尾大于或等于它的元素全部T掉，自己入队。

POJ2823 http://poj.org/problem?id=2823 是一道适合用单调队列来求解的题目，效率会特别高；不过一定要注意，由于WS的POJ会卡IO时间，所以需要自己实现一份read_int()和print_int()来替换掉scanf和printf。

最后，附上一份简单的单调队列代码：

在有些算法中，比较关键的步骤包含了少量数据的处理。以拷贝为例，在这种情况下如果可以进行优化，也能带来不错的效率提升。

假设有2个数组 int a[100], b[100]; 想把a的数据拷贝到b中去，作为一个ACMer可能会想用最简洁的方式来实现：
这一句最便捷了，不过效率上应当是不如一个循环(后注：这里可能有误导，参见后文)：毕竟这个只需要100个循环，每次拷贝sizeof(int)个字节，而memset则是执行100*sizeof(int)个字节。

循环的效率是比较低的。由此可以想到，如果每次循环的时候拷贝多一点，减少循环次数，也能够提高效率。假设是32bit的机器，用int拷贝基本上就把CPU指令集的效率挖得差不多了（如果不考虑SIMD指令的情况），更进一步的话，则考虑用顺序结构取代循环：
当然，极端情况可以写100个顺序语句出来，就是繁琐了一点，这里取4，主要是方便演示代码。对于n比较大的情况，全部写出来效果不一定好（不一定所有代码/数据都能放进CPU的一级缓存）；如果n特别大，基本上取决于内存的限制，这个优化就不明显了。对于不够整(n % 4 != 0)的情况，可以先把整的那一部分拷贝完毕，然后再用一个小循环把剩余的拷贝完：
看到这里可能你就会想起duff's device(达夫设备)，思路上与上面的代码一致，就是实现起来很独特:p.s. 这个代码虽然很奇怪（如果你之前没看过，建议再看一遍），但是 是可以编译运行的；拷贝并修改自 http://c-faq-chn.sourceforge.net/ccfaq/node380.html；这是某次极限编程比赛的代码，比较有争议，如果你觉得很有意思，可以看看这里进一步的说明和比较：
    http://triviasecurity.com.ru/file/Exploitation/Generic%20Programming%20Typed%20Buffers.htm
这个链接里面提到一个关于memcpy的情况：对于x86 CPU，memcpy很可能是使用REP STOS这样的指令实现的，效率应当比一个简单的for循环要高。

以上是对于较小的n的说明，关于大量拷贝更细致的优化，可以参考Glibc中qsort的实现。在一些情况下，我们会遇到很小的n，比如小于10。这时如果不写循环，而是直接写死代码，是个可行的优化。举个例子：在这段代码中，实际只需要执行6次加法运算，但是却有两层循环，在循环上带来了大量的开销。如果把循环直接展开，则会得到很好的效果：
但是对于可能会变化的n值呢？这时候如果能够允许程序在执行过程中生成可执行代码，是最好不过了，不过对于编译型的代码，这个实现起来比较有难度；而解释型的语言，这个优化又不是很有必要。想了想，在C中的一个替代方案是，写n个函数，保存在函数指针数组中，n作为索引来进行调用。

思源枯竭，到此为止。

虽然说最后的结果没有比我预期的差，但是过程还是很囧的。鉴于这里是我自己的博客，废话就多写一点。

总之就是从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这样的题目到最后半小时才开始考虑，实在是太过分了。

· 如果某人开了一题，条件允许的情况下，应该有人帮忙出测试数据。这次正式比赛的时候我们这个约定没被贯彻好。

· 大家都太紧张了，应该早点喝红牛的。

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)中最小值在数组中的索引）：