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~
Nov
19
引用
UBB内容为(开头那个下划线不需要加):
[_table]
l | r | l | c | r
左对齐|右对齐|左对齐|<a href="javascript:alert(12345)">居中啦啦啦</a>|右对齐
1|23|456|7890[newline]1234|0000
abcd|efg|hi|[-]|j
1|[-]|[-]|1|1
[/table]
[_table]
l | r | l | c | r
左对齐|右对齐|左对齐|<a href="javascript:alert(12345)">居中啦啦啦</a>|右对齐
1|23|456|7890[newline]1234|0000
abcd|efg|hi|[-]|j
1|[-]|[-]|1|1
[/table]
效果:
左对齐 | 右对齐 | 左对齐 | <a href="javascript:alert(12345)">居中啦啦啦</a> | 右对齐 |
1 | 23 | 456 | 7890 1234 |
0000 |
abcd | efg | hi | j | |
1 | 1 | 1 |
PHP代码:
function maketbl($str) {
$str = str_replace("<br/>", "\n", $str);
$str = str_replace("|", "|", $str);
$str = trim($str);
$lines = explode("\n", $str);
$firstline = explode("|", trim($lines[0]));
$conf = array();
foreach($firstline as $v) {
switch($v) {
case 'l':
$conf[] = 'left';
break;
case 'r':
$conf[] = 'right';
break;
case 'c':
$conf[] = 'center';
break;
default:
$conf[] = '';
}
}
$ncols = count($conf);
$nline = count($lines);
$ret = '<table cellspacing="0" cellpadding="3" border="1">'. "\n";
for ($i = 1; $i < $nline; $i++) {
$line = trim($lines[$i]);
if (empty($line)) continue;
$line = explode("|", $line);
$ret .= "<tr>\n";
$next = 1;
for ($j = 0; $j < $ncols; $j++) {
if ($line[$j] == "[-]") {
$next++;
continue;
}
$td = $line[$j];
//$td = htmlspecialchars($td);
$td = str_replace("[newline]", "<br/>", $td);
$ret .= <<<eot
<td align="{$conf[$j]}" colspan="{$next}">{$td}</td>
eot;
if ($line[$j] != "[-]") {
$next = 1;
}
}
$ret .= "</tr>\n";
}
$ret .= "</table>";
return $ret;
}
$str = str_replace("<br/>", "\n", $str);
$str = str_replace("|", "|", $str);
$str = trim($str);
$lines = explode("\n", $str);
$firstline = explode("|", trim($lines[0]));
$conf = array();
foreach($firstline as $v) {
switch($v) {
case 'l':
$conf[] = 'left';
break;
case 'r':
$conf[] = 'right';
break;
case 'c':
$conf[] = 'center';
break;
default:
$conf[] = '';
}
}
$ncols = count($conf);
$nline = count($lines);
$ret = '<table cellspacing="0" cellpadding="3" border="1">'. "\n";
for ($i = 1; $i < $nline; $i++) {
$line = trim($lines[$i]);
if (empty($line)) continue;
$line = explode("|", $line);
$ret .= "<tr>\n";
$next = 1;
for ($j = 0; $j < $ncols; $j++) {
if ($line[$j] == "[-]") {
$next++;
continue;
}
$td = $line[$j];
//$td = htmlspecialchars($td);
$td = str_replace("[newline]", "<br/>", $td);
$ret .= <<<eot
<td align="{$conf[$j]}" colspan="{$next}">{$td}</td>
eot;
if ($line[$j] != "[-]") {
$next = 1;
}
}
$ret .= "</tr>\n";
}
$ret .= "</table>";
return $ret;
}
Nov
19
博客出现这个问题很久了,一直懒得去整。
今天实在觉得不爽了,于是去看了一下blog的attachment.php
发现问题出在这一句:@header("Content-Type: {$contenttype}");
boblog是把附件的扩展名保留,然后用timestamp什么的作为文件名。
然后提供下载的时候自己把扩展名截出来,在自己的$MIMEType数组里找到对应的字符串放到$contenttype这里
我看了一下,也没啥问题,但是只要下载二进制文件就会发现下载下来的文件其实是原始数据被gzip压缩了的。
觉得很奇怪,就算把博客的gzip加速给关了还是有这个问题。
我想这应该是服务器做了手脚吧,强制开启gzip。
总之,注释了那句以后就OK了,原因暂时想不清楚,撂着。
如果有哪位大牛晓得原因,还望告知,多谢。
今天实在觉得不爽了,于是去看了一下blog的attachment.php
发现问题出在这一句:@header("Content-Type: {$contenttype}");
boblog是把附件的扩展名保留,然后用timestamp什么的作为文件名。
然后提供下载的时候自己把扩展名截出来,在自己的$MIMEType数组里找到对应的字符串放到$contenttype这里
我看了一下,也没啥问题,但是只要下载二进制文件就会发现下载下来的文件其实是原始数据被gzip压缩了的。
觉得很奇怪,就算把博客的gzip加速给关了还是有这个问题。
我想这应该是服务器做了手脚吧,强制开启gzip。
总之,注释了那句以后就OK了,原因暂时想不清楚,撂着。
如果有哪位大牛晓得原因,还望告知,多谢。
Nov
18
花点时间总结一下“栈”相关的内容。希望对于初学栈的同学会比较有帮助。
另外,其中涉及的一些内容也是书本上不会涉及到,或者是零零散散写出来的。看看总没坏处。
--------------传说中的分割线-------------
数据结构:栈
内容纲要
1. 什么是栈
2. 栈的实现(C语言)
a) 数组实现
b) 单链表实现
c) 两种实现的对比
3. 栈的应用
a) 在函数调用中的作用
b) 在局部变量存储中的应用
* 栈空间和系统维护的堆空间的对比
c) 在算法中的应用
另外,其中涉及的一些内容也是书本上不会涉及到,或者是零零散散写出来的。看看总没坏处。
--------------传说中的分割线-------------
数据结构:栈
内容纲要
1. 什么是栈
2. 栈的实现(C语言)
a) 数组实现
b) 单链表实现
c) 两种实现的对比
3. 栈的应用
a) 在函数调用中的作用
b) 在局部变量存储中的应用
* 栈空间和系统维护的堆空间的对比
c) 在算法中的应用
Nov
8
如果从大一算起,写C已经有3年了。其实高中也写过,但是基本可以忽略不计。代码量,比起acm/icpc正规军来说,当然还是少得多;但是应该也有几万行了。写了这么多代码,也看了不少算法,感觉就是,这样的经验需要时间的积淀。曾经觉得很难的问题,现在已经在脑子里豁然开朗。就比如八皇后问题,上一次研究它,是2007年6月的事情。那会儿应该能想的清楚了,但是对于那时候的我而言,回溯算法仍然是比较难以理解的(记得有一次想写一个生成全排列的程序,写了半天都不对,最后还是让sandy写了一个标程抄了两遍,才逐渐理解)。差不多2年半过去了,再回首这个八皇后,发现思路非常清晰,很快就把代码写出来了。
废话完回到这个问题上。它的两个难点在于:1. 如何判断某一个位置是否可以放置一个皇后;2. 回溯。
如果给这个8*8的矩阵上个坐标,横向(rows)为i = 0 to 7,纵向(columns)为j = 0 to 7。那么可以发现,在每一条斜线(/)方向上,每一个格子的横纵坐标之和(i + j)是一个固定值,从左上到右下的斜线,其值依次是0~14 (0+0; 0+1,1+0; 0+2,1+1,2+0; ... ; 6+7,7+6; 7+7)。同样地,,在每一条反斜线(\)方向上,每一个格子的横坐标与纵坐标的关系是, (i + (7 - j))是固定值,从右上到左下的斜线,其值依次是0~14。
因此,在开始寻找方案之前,给横、纵、斜线、反斜线方向各设置一个数组,所有元素初始化为0(表示可以放置),那么,在将皇后放置到(i, j)之前检查rows[i]、cols[j]、slash[i+j]、bslash[i+7-j]是否都为0,就可以判断这个位置能否放置皇后。由于放置的过程是从上到下一行一行放的,所以这个rows数组实际上可以去掉。这样第一个难点就解决了。(p.s. bslash -> backslash)
第二个难点,回溯,这个我觉得不是很容易能说清楚的。简单地说,需要回溯的就是前面提到的cols/slash/bslash数组。一行一行地来:每一行从第一个位置开始查找,当找到一个有效位置,放置一个皇后,将对应的值置为1(以后的位置就可以检测是否可放),然后继续查找下一行的位置(递归调用);如果下一行没有合适的位置(递归返回),将对应的位置重置为0,然后查找这一行下一个位置。
这个问题实在不是一个有难度的问题,我居然扯了这么多。可见我现在多闲啊。俗话说的好:经常扯蛋有助于预防蛋疼。
下附代码:
废话完回到这个问题上。它的两个难点在于:1. 如何判断某一个位置是否可以放置一个皇后;2. 回溯。
如果给这个8*8的矩阵上个坐标,横向(rows)为i = 0 to 7,纵向(columns)为j = 0 to 7。那么可以发现,在每一条斜线(/)方向上,每一个格子的横纵坐标之和(i + j)是一个固定值,从左上到右下的斜线,其值依次是0~14 (0+0; 0+1,1+0; 0+2,1+1,2+0; ... ; 6+7,7+6; 7+7)。同样地,,在每一条反斜线(\)方向上,每一个格子的横坐标与纵坐标的关系是, (i + (7 - j))是固定值,从右上到左下的斜线,其值依次是0~14。
因此,在开始寻找方案之前,给横、纵、斜线、反斜线方向各设置一个数组,所有元素初始化为0(表示可以放置),那么,在将皇后放置到(i, j)之前检查rows[i]、cols[j]、slash[i+j]、bslash[i+7-j]是否都为0,就可以判断这个位置能否放置皇后。由于放置的过程是从上到下一行一行放的,所以这个rows数组实际上可以去掉。这样第一个难点就解决了。(p.s. bslash -> backslash)
第二个难点,回溯,这个我觉得不是很容易能说清楚的。简单地说,需要回溯的就是前面提到的cols/slash/bslash数组。一行一行地来:每一行从第一个位置开始查找,当找到一个有效位置,放置一个皇后,将对应的值置为1(以后的位置就可以检测是否可放),然后继续查找下一行的位置(递归调用);如果下一行没有合适的位置(递归返回),将对应的位置重置为0,然后查找这一行下一个位置。
这个问题实在不是一个有难度的问题,我居然扯了这么多。可见我现在多闲啊。俗话说的好:经常扯蛋有助于预防蛋疼。
下附代码:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 8
int count;
int rows[N], cols[N], slash[2 * N - 1], bslash[2 * N - 1];
//每行放的位置,纵向不可放,斜向不可放(/),斜向不可放(\)
void place(int i) {
int j;
for (j = 0; j < N; ++j) {
if (cols[j] == 0 && slash[i + j] == 0 && bslash[i + (N-1) - j] == 0) {
rows[i] = j;
cols[j] = 1;
slash[i + j] = 1;
bslash[i + (N-1) - j] = 1;
if (i == N - 1) {
/*
int k;
for (k = 0; k < N; ++k) {
printf("%d ", rows[k]);
}
printf("\n");
*/
count++;
}
else {
place(i + 1);
}
//回溯
cols[j] = 0;
slash[i + j] = 0;
bslash[i + (N-1) - j] = 0;
}
}
}
int main () {
memset(rows, 0, sizeof(rows));
memset(cols, 0, sizeof(cols));
memset(slash, 0, sizeof(slash));
memset(bslash, 0, sizeof(bslash));
count = 0;
place(0);
printf("count = %d\n", count);
return 0;
}
#include <stdlib.h>
#include <string.h>
#define N 8
int count;
int rows[N], cols[N], slash[2 * N - 1], bslash[2 * N - 1];
//每行放的位置,纵向不可放,斜向不可放(/),斜向不可放(\)
void place(int i) {
int j;
for (j = 0; j < N; ++j) {
if (cols[j] == 0 && slash[i + j] == 0 && bslash[i + (N-1) - j] == 0) {
rows[i] = j;
cols[j] = 1;
slash[i + j] = 1;
bslash[i + (N-1) - j] = 1;
if (i == N - 1) {
/*
int k;
for (k = 0; k < N; ++k) {
printf("%d ", rows[k]);
}
printf("\n");
*/
count++;
}
else {
place(i + 1);
}
//回溯
cols[j] = 0;
slash[i + j] = 0;
bslash[i + (N-1) - j] = 0;
}
}
}
int main () {
memset(rows, 0, sizeof(rows));
memset(cols, 0, sizeof(cols));
memset(slash, 0, sizeof(slash));
memset(bslash, 0, sizeof(bslash));
count = 0;
place(0);
printf("count = %d\n", count);
return 0;
}
Nov
7
#include <stdio.h>
#include <stdlib.h>
/*
* Kruskal贪心算法求最小生成树(heap+并查集)
* 测试输入数据:
6 10 //6个顶点10条边
1 5 2 //从顶点1到顶点5的边权重为2
2 4 3
4 5 1
0 3 6
2 3 7
5 2 6
4 0 7
1 3 5
1 2 4
3 5 9
*/
struct edge {
int start, end, weight;
};
void siftdown (struct edge *a, int n, int i) {
struct edge t;
if (i < 1 || i > n) return;
while (i * 2 <= n) {
i *= 2;
if (i + 1 <= n && a[i].weight > a[i + 1].weight) i++;
if (a[i].weight < a[i/2].weight ) {
t = a[i];
a[i] = a[i/2];
a[i/2] = t;
}
else {
break;
}
}
}
void siftup (struct edge *a, int n, int i) {
struct edge t;
if (i < 1 || i > n) return;
while (i > 1) {
if (a[i].weight < a[i/2].weight) {
t = a[i];
a[i] = a[i/2];
a[i/2] = t;
}
else {
break;
}
i /= 2;
}
}
void makeheap(struct edge *a, int n) {
int i;
for (i = n / 2; i >= 1; --i) {
siftdown(a, n, i);
}
}
struct edge pop(struct edge *a, int *n) {
struct edge t;
t = a[1];
a[1] = a[*n];
(*n)--; //第二次挂在这里,不能写*n--(*n; n-=1;), 要写(*n)--
siftdown(a, *n, 1);
return t;
}
void dump(struct edge *a, int n) {
int i;
for (i = 0; i < n; ++i) {
printf("edge (%d, %d), %d\n", a[i].start, a[i].end, a[i].weight);
}
}
void initUnionSet(int a[], int n) {
int i;
for (i = 0; i < n; ++i) {
a[i] = i;
}
}
int getFather(int a[], int x) {
return a[x] == x ? x : (a[x] = getFather(a, a[x]));
}
void merge(int a[], int x, int y) {
x = getFather(a, x);
y = getFather(a, y);
a[x] = y;
}
int haveCommonAncestor(int a[], int x, int y) {
return (getFather(a, x) == getFather(a, y) ? 1 : 0);
}
int main () {
int m, n, i, k, *father;
struct edge *input, *output, t;
scanf("%d%d", &m, &n);
input = (struct edge *)malloc(sizeof(struct edge) * (n + 1));
for (i = 1; i <= n; ++i) {
scanf("%d%d%d", &input[i].start, &input[i].end, &input[i].weight);
}
makeheap(input, n);
dump(input+1, n);
printf("end input\n");
int n1 = n;
output = (struct edge *)malloc(sizeof(struct edge) * (m - 1));
father = (int *)malloc(sizeof(int) * n);
initUnionSet(father, m);
k = 0;
printf("\nStart:\n");
while (n1 > 0) {
t = pop(input, &n1);
printf("edge (%d,%d), %d ", t.start, t.end, t.weight);
if (0 == haveCommonAncestor(father, t.start, t.end)) {
printf("added in\n");
output[k] = t;
k++;
merge(father, t.start, t.end);
if (k == m - 1) {
printf("~~ok~~\n");
break;
}
}
else {
printf("ignored\n");
}
}
printf("\nresult:\n");
dump(output, k);
free(input);
free(output);
free(father);
return 0;
}
#include <stdlib.h>
/*
* Kruskal贪心算法求最小生成树(heap+并查集)
* 测试输入数据:
6 10 //6个顶点10条边
1 5 2 //从顶点1到顶点5的边权重为2
2 4 3
4 5 1
0 3 6
2 3 7
5 2 6
4 0 7
1 3 5
1 2 4
3 5 9
*/
struct edge {
int start, end, weight;
};
void siftdown (struct edge *a, int n, int i) {
struct edge t;
if (i < 1 || i > n) return;
while (i * 2 <= n) {
i *= 2;
if (i + 1 <= n && a[i].weight > a[i + 1].weight) i++;
if (a[i].weight < a[i/2].weight ) {
t = a[i];
a[i] = a[i/2];
a[i/2] = t;
}
else {
break;
}
}
}
void siftup (struct edge *a, int n, int i) {
struct edge t;
if (i < 1 || i > n) return;
while (i > 1) {
if (a[i].weight < a[i/2].weight) {
t = a[i];
a[i] = a[i/2];
a[i/2] = t;
}
else {
break;
}
i /= 2;
}
}
void makeheap(struct edge *a, int n) {
int i;
for (i = n / 2; i >= 1; --i) {
siftdown(a, n, i);
}
}
struct edge pop(struct edge *a, int *n) {
struct edge t;
t = a[1];
a[1] = a[*n];
(*n)--; //第二次挂在这里,不能写*n--(*n; n-=1;), 要写(*n)--
siftdown(a, *n, 1);
return t;
}
void dump(struct edge *a, int n) {
int i;
for (i = 0; i < n; ++i) {
printf("edge (%d, %d), %d\n", a[i].start, a[i].end, a[i].weight);
}
}
void initUnionSet(int a[], int n) {
int i;
for (i = 0; i < n; ++i) {
a[i] = i;
}
}
int getFather(int a[], int x) {
return a[x] == x ? x : (a[x] = getFather(a, a[x]));
}
void merge(int a[], int x, int y) {
x = getFather(a, x);
y = getFather(a, y);
a[x] = y;
}
int haveCommonAncestor(int a[], int x, int y) {
return (getFather(a, x) == getFather(a, y) ? 1 : 0);
}
int main () {
int m, n, i, k, *father;
struct edge *input, *output, t;
scanf("%d%d", &m, &n);
input = (struct edge *)malloc(sizeof(struct edge) * (n + 1));
for (i = 1; i <= n; ++i) {
scanf("%d%d%d", &input[i].start, &input[i].end, &input[i].weight);
}
makeheap(input, n);
dump(input+1, n);
printf("end input\n");
int n1 = n;
output = (struct edge *)malloc(sizeof(struct edge) * (m - 1));
father = (int *)malloc(sizeof(int) * n);
initUnionSet(father, m);
k = 0;
printf("\nStart:\n");
while (n1 > 0) {
t = pop(input, &n1);
printf("edge (%d,%d), %d ", t.start, t.end, t.weight);
if (0 == haveCommonAncestor(father, t.start, t.end)) {
printf("added in\n");
output[k] = t;
k++;
merge(father, t.start, t.end);
if (k == m - 1) {
printf("~~ok~~\n");
break;
}
}
else {
printf("ignored\n");
}
}
printf("\nresult:\n");
dump(output, k);
free(input);
free(output);
free(father);
return 0;
}
注:下面这段代码是之前写的,写了一个简单的链表+插入来实现,本来是想用队列式链表然后再排序的,但是太麻烦了,干脆直接插入排序,所以那个tail也就一点用也没有了(用在tree那个list里看起来还更NC)。其实更好的办法应该是根据输入的n动态分配足够的空间,全部输入以后然后用heap或者用qsort。