Dec
26
写代码的时候总是觉得printf打起来很麻烦，malloc的强制转换和sizeof很罗嗦，写几个宏，方便多了
#define P(a, b) printf(#b ": %" #a "\n", b)
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
#define Ps(a, c, b) P(a, (c)->b)
#define alloc(name, type, n) type *name = (type *) malloc(sizeof(type) * (n))
#define allocs(name, type, n) alloc(name, struct type, (n))
Dec
22
工具->宏->Visual Basic编辑器，工程框中，右击Sheet1，插入模块，在模块1中加入如下代码
如果需要修改单元格的内容：
Sub iterate()
Dim row, col, i, j As Integer
Dim str, addr As String
row = ActiveSheet.UsedRange.rows.Count
col = ActiveSheet.UsedRange.Columns.Count
MsgBox row & " " & col, vbOKOnly
For i = 0 To row - 1
For j = 0 To col - 1
addr = Chr(65 + j) & Chr(i + 48 + 1)
MsgBox Range(addr).Text
Next
Next
End Sub
Dim row, col, i, j As Integer
Dim str, addr As String
row = ActiveSheet.UsedRange.rows.Count
col = ActiveSheet.UsedRange.Columns.Count
MsgBox row & " " & col, vbOKOnly
For i = 0 To row - 1
For j = 0 To col - 1
addr = Chr(65 + j) & Chr(i + 48 + 1)
MsgBox Range(addr).Text
Next
Next
End Sub
如果需要修改单元格的内容：
Range(addr).Select
ActiveCell.FormulaR1C1 = "ooxx"
ActiveCell.FormulaR1C1 = "ooxx"
Dec
13
由于上次和slyar同学提起这个问题，所以才想着还是自己再写一下，而且其实还有自己没解决的问题，希望能抛砖引玉。
剧透
本篇未解决的问题是：在n个数字里面，如果只有3个数字是没有凑对的，能否用O(n)的方法找出来？超过3个又远小于n个的情况呢？
===
WOJ上有2道连在一起的题目，很赞。
找不同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1202
找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1203
找不同：给你n*2+1个数，其中有n对是一样的，让你找出没有相同数字的那一个（真寂寞）。
如果我们能把所有的数字按大小排序，那么只要两个两个拿出来
第一次出现不一致的情况或者剩下最后一个数字的情况，就是找到寂寞数字了时候。
可是这样效率太低，就算用基数排序，那个常数也是够大的。
换个思路，由按位异或操作的性质可以知道 a | a = 0 且 (a | b) | c = a | (b | c)
也就是说，按位异或这个“按位模2加”操作的性质是同一个数与自身异或得0，且该操作是可交换的。
所以如果我们将所有数字串起来异或，其实就等于把所有数字排序后再串起来异或。
所有相同的数字想异或都得0，最后异或的结果就是最寂寞的那个。。
找相同：有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来
可以证明，如果反复地执行这一操作【从这2*n+1个数里面取出两个数ab，如果a，b相同，放回去，如果a，b不同，都舍弃】直到剩下来的所有数字都相同（这一定是可以达到的）。所以只要设计一个最高效的方式来实现这个过程就行了。
最简单的方式是O(n)的，用栈。伪码如下
如果有同学看看1204的话，就会知道，这题是
继续找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1204
描述：有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=500000)
跟前面那道题的只有一点点的区别，多了一种情况就是，有一个数字可能正好出现一半次。
直接用上面那种方法肯定没法处理了，但是只要稍微想想，其实还是很容易的：
用上面的方法处理前1～n-1个数字，到了最后一个数字的时候，看看和栈里面那个数字是不是一样
如果一样，说明这个数字出现了超过一半次，输出
如果不一样，那么栈里肯定只剩下一个数字，能出现一半次的，肯定是这两个数字之一，重新扫一次数组就行了。
WOJ关于找相同和不同的貌似就只有三道题，但是“继续”其实还没完。
继续找不同：有2n个数字，其中2n-2个数字是两两凑对的，剩下两个数字很寂寞，请找出来。
这题和前面的找不同也很像，解决方法是可以“复用”的。
以前的一篇日志里面有：http://www.felix021.com/blog/read.php?1243
解法是momodi给出的，将全部数字异或以后等到的C = A ^ B != 0 (若C==0则A==B，不符合要求)
然后扫描C的每一bit，如果bit[k] == 1，那么将C和给出的数据中所有bit[k] == 1的整数异或
得出的就是其中一个数字A，然后A ^ C = B
这种解法也是O(n)的，只需要扫描两遍，还是比较快的。
-------------------------------------
最后，重点：
如果是3个数，或者更多一些，有没有O(n)的解法？
当然，用O(n)的基数排序处理以后再遍历，的确是O(n)的效率，但是就是效率太低了，而且需要多次遍历。
假设数字的量超过1000亿，需要存放在硬盘中（也就是扫描次数越少越好），这该怎么办呢？
心里已经有些想法了，不过暂时不想写出来，再想想明白。
如果哪位大牛有好的想法，希望互相交流一下:)
剧透
本篇未解决的问题是：在n个数字里面，如果只有3个数字是没有凑对的，能否用O(n)的方法找出来？超过3个又远小于n个的情况呢？
===
WOJ上有2道连在一起的题目，很赞。
找不同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1202
找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1203
找不同：给你n*2+1个数，其中有n对是一样的，让你找出没有相同数字的那一个（真寂寞）。
如果我们能把所有的数字按大小排序，那么只要两个两个拿出来
第一次出现不一致的情况或者剩下最后一个数字的情况，就是找到寂寞数字了时候。
可是这样效率太低，就算用基数排序，那个常数也是够大的。
换个思路，由按位异或操作的性质可以知道 a | a = 0 且 (a | b) | c = a | (b | c)
也就是说，按位异或这个“按位模2加”操作的性质是同一个数与自身异或得0，且该操作是可交换的。
所以如果我们将所有数字串起来异或，其实就等于把所有数字排序后再串起来异或。
所有相同的数字想异或都得0，最后异或的结果就是最寂寞的那个。。
找相同：有一组数,很多很多个数,里面有一个数出现了超过一半次,请你把它找出来
可以证明，如果反复地执行这一操作【从这2*n+1个数里面取出两个数ab，如果a，b相同，放回去，如果a，b不同，都舍弃】直到剩下来的所有数字都相同（这一定是可以达到的）。所以只要设计一个最高效的方式来实现这个过程就行了。
最简单的方式是O(n)的，用栈。伪码如下
init stack(s)
for x in a[1..n]
if empty(s) or s.top() == x
s.push(x)
else
s.pop()
return s.top()
for x in a[1..n]
if empty(s) or s.top() == x
s.push(x)
else
s.pop()
return s.top()
如果有同学看看1204的话，就会知道，这题是
继续找相同：http://acm.whu.edu.cn/oak/problem/problem.jsp?problem_id=1204
描述：有 n 个整数, 其中有且仅有一个整数出现了 >= n/2.0 次 (n<=500000)
跟前面那道题的只有一点点的区别，多了一种情况就是，有一个数字可能正好出现一半次。
直接用上面那种方法肯定没法处理了，但是只要稍微想想，其实还是很容易的：
用上面的方法处理前1～n-1个数字，到了最后一个数字的时候，看看和栈里面那个数字是不是一样
如果一样，说明这个数字出现了超过一半次，输出
如果不一样，那么栈里肯定只剩下一个数字，能出现一半次的，肯定是这两个数字之一，重新扫一次数组就行了。
WOJ关于找相同和不同的貌似就只有三道题，但是“继续”其实还没完。
继续找不同：有2n个数字，其中2n-2个数字是两两凑对的，剩下两个数字很寂寞，请找出来。
这题和前面的找不同也很像，解决方法是可以“复用”的。
以前的一篇日志里面有：http://www.felix021.com/blog/read.php?1243
解法是momodi给出的，将全部数字异或以后等到的C = A ^ B != 0 (若C==0则A==B，不符合要求)
然后扫描C的每一bit，如果bit[k] == 1，那么将C和给出的数据中所有bit[k] == 1的整数异或
得出的就是其中一个数字A，然后A ^ C = B
这种解法也是O(n)的，只需要扫描两遍，还是比较快的。
-------------------------------------
最后，重点：
如果是3个数，或者更多一些，有没有O(n)的解法？
当然，用O(n)的基数排序处理以后再遍历，的确是O(n)的效率，但是就是效率太低了，而且需要多次遍历。
假设数字的量超过1000亿，需要存放在硬盘中（也就是扫描次数越少越好），这该怎么办呢？
心里已经有些想法了，不过暂时不想写出来，再想想明白。
如果哪位大牛有好的想法，希望互相交流一下:)
Dec
10
在int32(64位机器则为int64)的范围内的证书作为数组索引来存储数据的话，
在php中，会自动将这种可以转换成int的字符串转换成int作为索引使用。
以下面这一段脚本的输出来说明这个问题：
在php中，会自动将这种可以转换成int的字符串转换成int作为索引使用。
以下面这一段脚本的输出来说明这个问题：
<?php
$arr = array(
123 => 'a',
'123' => 'b',
0123 => 'c',
'0123' => 'd',
);
var_dump($arr);
?>
输出：
array(3) {
[123]=>
string(1) "b" //第一个123的a消失了，却出来了一个b，说明"123"在索引中被当作int处理了，并覆盖了之前123索引对应的值
[83]=> //0123是八进制的83
string(1) "c"
["0123"]=> //字符串
string(1) "d"
}
$arr = array(
123 => 'a',
'123' => 'b',
0123 => 'c',
'0123' => 'd',
);
var_dump($arr);
?>
输出：
array(3) {
[123]=>
string(1) "b" //第一个123的a消失了，却出来了一个b，说明"123"在索引中被当作int处理了，并覆盖了之前123索引对应的值
[83]=> //0123是八进制的83
string(1) "c"
["0123"]=> //字符串
string(1) "d"
}
Nov
24
zz from http://hi.baidu.com/whuisland/blog/item/17ba47ce6920340993457e4b.html
我是一个硬盘。
在一个普普通通的台式机里工作。别人总认为我们是高科技白领，工作又干净又体面，似乎风光得很。也许他们是因为看到洁白漂亮的机箱才有这样的错觉吧。其实象我们这样的小台式机，工作环境狭迫，里面的灰尘吓得死人。每天生活死水一潭，工作机械重复。跑跑文字处理看看电影还凑活，真要遇到什么大软件和游戏上上下下就要忙的团团转，最后还常常要死机。
我是一个硬盘。
在一个普普通通的台式机里工作。别人总认为我们是高科技白领，工作又干净又体面，似乎风光得很。也许他们是因为看到洁白漂亮的机箱才有这样的错觉吧。其实象我们这样的小台式机，工作环境狭迫，里面的灰尘吓得死人。每天生活死水一潭，工作机械重复。跑跑文字处理看看电影还凑活，真要遇到什么大软件和游戏上上下下就要忙的团团转，最后还常常要死机。
Nov
22
不解释，就让你看得蛋疼。
#include <iostream>
using namespace std;
class T {
typedef void (T::*Tptr)(void);
Tptr p;
public:
void a() { cout << "a" << endl; }
void b() { cout << "b" << endl; }
void call(Tptr _p) {
p = _p;
(this->*p)();
}
};
int main() {
T t1;
t1.call(&T::a);
t1.call(&T::b);
return 0;
}
using namespace std;
class T {
typedef void (T::*Tptr)(void);
Tptr p;
public:
void a() { cout << "a" << endl; }
void b() { cout << "b" << endl; }
void call(Tptr _p) {
p = _p;
(this->*p)();
}
};
int main() {
T t1;
t1.call(&T::a);
t1.call(&T::b);
return 0;
}
Nov
22
丢失了3篇日志和5篇评论。
不过幸好，Google Reader非常称职地保存了我那两篇日志，所以还是恢复过来了，差一个成员函数指针的，现在补一下吧。
看来备份工作还是要多多注意啊！
不过幸好，Google Reader非常称职地保存了我那两篇日志，所以还是恢复过来了，差一个成员函数指针的，现在补一下吧。
看来备份工作还是要多多注意啊！
Nov
22
在EB的Hi群里大家聊到了CSRF攻击的问题。
关于CSRF攻击，网上资料很多，简单说几句：现在很多网站对提交的请求不检查来源，攻击者可以简单地构造一个页面，页面包含一个大小为0x0的iframe，内含一个修改管理员密码或者创建新特权用户或为现有用户提升权限的表单，当页面载入的时候由javascript控制该表单post到abc.com的某个页面。然后攻击者将此url发送给abc.com的管理员，引诱其点击，如果管理员此时已经登录，就会在管理员不知情的情况下获得权限。具体的原理，如果不很了解，建议先学习一下HTTP协议，重点是GET/POST，Cookie/Sessoin，Referer。解决的办法比如限制referer，或者增加页面校验码等。
看了一下这个Bo-blog(2.1.0)，居然没有这个检查。。。囧。想起2.1.1，这个版本推出挺久了，因为2.1.0有些BUG折磨了我挺久（最近解决了一个，下载的问题，还有一个是rss在google reader总是少一篇），于是就去下了新版本在本地搭起来。看了一下，发现没有什么大的改动，对CSRF的攻击也完全不设防。而且由于现在这个版本我自己改了好多地方，比如根据IP直接显示地址，以及评论留言的邮件通知等，如果升级了还得重新改，太麻烦，所以完全没有升级的动力。到Bo-blog的bbs去提了个BUG报告。Bo-Blog的更新实在太少。。
@1:00 p.s. 已经修改，增加了检查POST时的Referer，GET就不检查了，这个。。真不能检查。。验证码就先不做了，每个页面都要去加，真不爽。这时候觉得bo-blog统一入口的原则真好，改动只有一个地方，加了几行就OK~
关于CSRF攻击，网上资料很多，简单说几句：现在很多网站对提交的请求不检查来源，攻击者可以简单地构造一个页面，页面包含一个大小为0x0的iframe，内含一个修改管理员密码或者创建新特权用户或为现有用户提升权限的表单，当页面载入的时候由javascript控制该表单post到abc.com的某个页面。然后攻击者将此url发送给abc.com的管理员，引诱其点击，如果管理员此时已经登录，就会在管理员不知情的情况下获得权限。具体的原理，如果不很了解，建议先学习一下HTTP协议，重点是GET/POST，Cookie/Sessoin，Referer。解决的办法比如限制referer，或者增加页面校验码等。
看了一下这个Bo-blog(2.1.0)，居然没有这个检查。。。囧。想起2.1.1，这个版本推出挺久了，因为2.1.0有些BUG折磨了我挺久（最近解决了一个，下载的问题，还有一个是rss在google reader总是少一篇），于是就去下了新版本在本地搭起来。看了一下，发现没有什么大的改动，对CSRF的攻击也完全不设防。而且由于现在这个版本我自己改了好多地方，比如根据IP直接显示地址，以及评论留言的邮件通知等，如果升级了还得重新改，太麻烦，所以完全没有升级的动力。到Bo-blog的bbs去提了个BUG报告。Bo-Blog的更新实在太少。。
@1:00 p.s. 已经修改，增加了检查POST时的Referer，GET就不检查了，这个。。真不能检查。。验证码就先不做了，每个页面都要去加，真不爽。这时候觉得bo-blog统一入口的原则真好，改动只有一个地方，加了几行就OK~
