Dec
17
选中：在文本段落上面，双击选中一个单词（或者一个汉字词组），然后再点击一次，就是选中一个段落。如果连续（较快速）两次点击且第二次不放开进行拖动，就是按单词进行选中；连续三次点击且第三次不放开进行拖动，则是按段落选中。选中某个文本区域（单击双击三击都可，单击的话就是选择开始点），然后在结束点按住shift+单击，就是把整块都选中，而且可以连续执行shift+单击，不用一直拖动鼠标在网页上面刷了。
Win7/Vista下面Win键+上下左右可以将当前窗口 最大化、左侧放置、右侧放置、最小化；WIN+SHIFT+左右是让窗口在多个屏幕之间移动;WIN+SPACE是可以临时看一下桌面，放开就恢复。拖动某个窗口摇一摇，其他窗口全部最小化，再摇一摇就回来。在文件夹空白处按住SHIFT右键单击，可以看到“在此处打开命令行窗口”。CTRL+Shift+N是新建文件夹。
大多数浏览器支持中键点击链接后台打开；中键点击TAB关闭；CTRL+W是关闭当前TAB（包括浏览器和资源管理器）。
ALT+SPACE打开窗口快捷菜单，ALT+D是切换到地址栏，ALT+PrintScreen是对当前窗口截图，CTRL+ESC打开开始菜单，CTRL+SHIFT+ESC打开任务管理器。
不知道有多少同学真正注意到开启Aero特效的VISTA/Win7下面按住WIN+TAB是有3D桌面效果的。
最后，可以安装个KeyTweak修改自己键盘的按键，比如把Insert修改成静音。
Win7/Vista下面Win键+上下左右可以将当前窗口 最大化、左侧放置、右侧放置、最小化；WIN+SHIFT+左右是让窗口在多个屏幕之间移动;WIN+SPACE是可以临时看一下桌面，放开就恢复。拖动某个窗口摇一摇，其他窗口全部最小化，再摇一摇就回来。在文件夹空白处按住SHIFT右键单击，可以看到“在此处打开命令行窗口”。CTRL+Shift+N是新建文件夹。
大多数浏览器支持中键点击链接后台打开；中键点击TAB关闭；CTRL+W是关闭当前TAB（包括浏览器和资源管理器）。
ALT+SPACE打开窗口快捷菜单，ALT+D是切换到地址栏，ALT+PrintScreen是对当前窗口截图，CTRL+ESC打开开始菜单，CTRL+SHIFT+ESC打开任务管理器。
不知道有多少同学真正注意到开启Aero特效的VISTA/Win7下面按住WIN+TAB是有3D桌面效果的。
最后，可以安装个KeyTweak修改自己键盘的按键，比如把Insert修改成静音。
Dec
16
想起第一届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（即动态规划），不太会，掠过。
蛋疼随便写点。
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（即动态规划），不太会，掠过。
Dec
16
1. 选题
那个鸟系统实在做的很烂，勉强用用吧。
(1) 如果没有保研，或者没有跟着的老师，或者跟着的老师没有在做的项目，那么看到哪个题目有兴趣了就选上，然后跟给题的老师联系，一般来说都没问题；
(2) 如果上述条件不成立，选自己老师出的题；
(3) 如果自己老师没在上面出题，可以让他找王恒还是谁加个题目，把你填上去就行了。
(4) 最后一种情况，如果你跟某老师比较熟的话，想做什么让他去王恒那里加个也OK。
2. 毕设最重要的是什么？
不是内容，是格式。cs.whu.edu.cn/thesis首页“相关下载”里面有范文和格式，在写的时候一定要特别注意；尤其是每年可能会有些细节变动，一定要及时了解。最后交论文的时候需要交纸质版（而且是要比较贵的那种封面，一张两三块钱，封死，切割整齐），如果格式不合适的话，要重新打一遍，很贵也很麻烦。争取一次过。
3. 毕设内容怎么办？
随便忽悠，最后答辩的时候很松。
4. 答辩的情况
(1) 希望申请优秀毕业论文需要提前申报，而且会提前答辩
(2) 新大楼三四五层的某些间会作为答辩的地点。参加答辩的同学随机分组，每十来个同学分到某一个房间，每个房间两三个老师
(3) 需要准备PPT，貌似是8～10分钟吧，然后老师会问你几个可有可无的问题，大概应付一下就过了。
5. 附上我去年的相关文档
p.s. 我的论文格式是一次通过的。
下载文件 (已下载 2634 次)
6. 祝各位顺利毕业
那个鸟系统实在做的很烂，勉强用用吧。
(1) 如果没有保研，或者没有跟着的老师，或者跟着的老师没有在做的项目，那么看到哪个题目有兴趣了就选上，然后跟给题的老师联系，一般来说都没问题；
(2) 如果上述条件不成立，选自己老师出的题；
(3) 如果自己老师没在上面出题，可以让他找王恒还是谁加个题目，把你填上去就行了。
(4) 最后一种情况，如果你跟某老师比较熟的话，想做什么让他去王恒那里加个也OK。
2. 毕设最重要的是什么？
不是内容，是格式。cs.whu.edu.cn/thesis首页“相关下载”里面有范文和格式，在写的时候一定要特别注意；尤其是每年可能会有些细节变动，一定要及时了解。最后交论文的时候需要交纸质版（而且是要比较贵的那种封面，一张两三块钱，封死，切割整齐），如果格式不合适的话，要重新打一遍，很贵也很麻烦。争取一次过。
3. 毕设内容怎么办？
随便忽悠，最后答辩的时候很松。
4. 答辩的情况
(1) 希望申请优秀毕业论文需要提前申报，而且会提前答辩
(2) 新大楼三四五层的某些间会作为答辩的地点。参加答辩的同学随机分组，每十来个同学分到某一个房间，每个房间两三个老师
(3) 需要准备PPT，貌似是8～10分钟吧，然后老师会问你几个可有可无的问题，大概应付一下就过了。
5. 附上我去年的相关文档
p.s. 我的论文格式是一次通过的。
下载文件 (已下载 2634 次)6. 祝各位顺利毕业
Dec
12
不用费心机去搞 lxrandr 或者 xrandr 或者 Xorg.conf 什么的了，只要启动server的时候这样：
$ vncserver -geometry 640x480
$ vncserver -geometry 640x480
Dec
10
其实是个比较简单的数据结构了，引用百度百科给出的说明，其对应的问题是：不断地向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。
最后，附上一份简单的单调队列代码：
使用普通队列来实现，每个元素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.
使用单调队列，首先要有一个数据结构
struct node { int seq, val; }
用于记录队列中的元素及其在输入序列中的顺序。队列的状态是这样维护的：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。
最后，附上一份简单的单调队列代码：
#include<stdio.h>
int main() {
struct node {
int seq, val;
} q[100]; //q: queue
int N, k, i, f, b, t, ans[100];
scanf("%d%d", &N, &k); //不是内裤
f = b = 0; //f: front, b: back
for (i = 0; i < N; i++) {
scanf("%d", &t);
if (f < b && q[f].seq <= i - k)
f++; //把需要出队的队首元素T掉
while (f < b && q[b-1].val >= t)
b--; //把队尾不大于t的元素T掉(注意等号!)
q[b].seq = i, q[b].val = t, b++; //入队尾
ans[i] = q[f].val; //保存当前的最小值
}
for (i = k - 1; i < N; i++)
printf("%d ", ans[i]);
return 0;
}
int main() {
struct node {
int seq, val;
} q[100]; //q: queue
int N, k, i, f, b, t, ans[100];
scanf("%d%d", &N, &k); //不是内裤
f = b = 0; //f: front, b: back
for (i = 0; i < N; i++) {
scanf("%d", &t);
if (f < b && q[f].seq <= i - k)
f++; //把需要出队的队首元素T掉
while (f < b && q[b-1].val >= t)
b--; //把队尾不大于t的元素T掉(注意等号!)
q[b].seq = i, q[b].val = t, b++; //入队尾
ans[i] = q[f].val; //保存当前的最小值
}
for (i = k - 1; i < N; i++)
printf("%d ", ans[i]);
return 0;
}
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.
