Jan
13
google搜到的一篇Disable Outlook's Junk E-mail Filter @
http://www.outlook-tips.net/howto/disable_junkfilter.htm
需要打开注册表编辑器，C:\Windows\regedit.exe
如果是Outlook 2007，修改 (如果没有就创建):
HKEY_CURRENT_USER\Software\Policies\Microsoft\office\12.0\outlook
DWord: DisableAntiSpam
Value: 1
如果是Outlook 2010，那么路径中的12变成14，其他不变：
HKEY_CURRENT_USER\Software\Policies\Microsoft\office\14.0\outlook
删掉这个键可以恢复垃圾邮件过滤。
--
p.s. 在outlook 2010中，“最小化到托盘”的设置不知道在哪里，我也是通过直接修改注册表实现的：
在上述路径下创建Dword键MinToTray值为1即可。
正如sandy所言，“折腾了很久，我决定放弃了，还是去下载office03算了，一个软件能做到如此难以掌握也亏M$费心了。”
http://www.outlook-tips.net/howto/disable_junkfilter.htm
需要打开注册表编辑器，C:\Windows\regedit.exe
如果是Outlook 2007，修改 (如果没有就创建):
HKEY_CURRENT_USER\Software\Policies\Microsoft\office\12.0\outlook
DWord: DisableAntiSpam
Value: 1
如果是Outlook 2010，那么路径中的12变成14，其他不变：
HKEY_CURRENT_USER\Software\Policies\Microsoft\office\14.0\outlook
删掉这个键可以恢复垃圾邮件过滤。
--
p.s. 在outlook 2010中，“最小化到托盘”的设置不知道在哪里，我也是通过直接修改注册表实现的：
在上述路径下创建Dword键MinToTray值为1即可。
正如sandy所言，“折腾了很久，我决定放弃了，还是去下载office03算了，一个软件能做到如此难以掌握也亏M$费心了。”
Jan
12
今天跟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整理的
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就会从大到小排序。可参见源码：
sort_heap(_RandomAccessIterator __first, _RandomAccessIterator __last,
_Compare __comp)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap_pred(__first, __last, __comp);
while (__last - __first > 1)
std::pop_heap(__first, __last--, __comp);
}
_Compare __comp)
{
// concept requirements
__glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<
_RandomAccessIterator>)
__glibcxx_requires_valid_range(__first, __last);
__glibcxx_requires_heap_pred(__first, __last, __comp);
while (__last - __first > 1)
std::pop_heap(__first, __last--, __comp);
}
-----
以下是sandy整理的
引用
1、heap算法虽然默认都使用的是operator <，但是建立的却是大根堆
2、sort_heap，是对已经成为heap的序列进行sort。本质上就是不断循环pop_heap而已。
3、sort_heap默认使用的也是operator <，排序出来的结果是从小到大的序列。
4、sort_heap算法使用的判别式，必须和之前建立heap的时候使用的判别式一致，比如都是operator <，或者都是operator > 。否则不能保证排序出来的结果是正确的。
5、简而言之，对大根堆进行sort_heap，必须使用operator <，对于小根堆进行sort_heap，必须使用operator >。
6、如果想让大根堆变成一个从大到小的序列，或者想让小根堆变成一个从小到大的序列，不能简单的改变判别式（原因如上所述），而应该保持原有判别式排序，然后调用std::reverse。
7、如果仅仅是想要用堆排序，这样自己封装一个heap_sort函数会更安全：
void heap_sort(RAIterator begin, RAIterator end , Comp op) {
make_heap(begin, end, op);
sort_heap(begin, end, op);
}
这样就可以保证建堆的时候和排序的时候用的都是同样的判别式。
8、n次push_heap的算法貌似是O(nlogn)的。。
2、sort_heap，是对已经成为heap的序列进行sort。本质上就是不断循环pop_heap而已。
3、sort_heap默认使用的也是operator <，排序出来的结果是从小到大的序列。
4、sort_heap算法使用的判别式，必须和之前建立heap的时候使用的判别式一致，比如都是operator <，或者都是operator > 。否则不能保证排序出来的结果是正确的。
5、简而言之，对大根堆进行sort_heap，必须使用operator <，对于小根堆进行sort_heap，必须使用operator >。
6、如果想让大根堆变成一个从大到小的序列，或者想让小根堆变成一个从小到大的序列，不能简单的改变判别式（原因如上所述），而应该保持原有判别式排序，然后调用std::reverse。
7、如果仅仅是想要用堆排序，这样自己封装一个heap_sort函数会更安全：
void heap_sort(RAIterator begin, RAIterator end , Comp op) {
make_heap(begin, end, op);
sort_heap(begin, end, op);
}
这样就可以保证建堆的时候和排序的时候用的都是同样的判别式。
8、n次push_heap的算法貌似是O(nlogn)的。。
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
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;
}
