Mar
8
今天下午在实验室一个人做的。
一共写了5题，3AC，1WA，1没交。
A, Problem 1398 - Stock Exchange
最长递增自序列。因为是n <= 100000的数据量，所以显然N^2的程序是不行的，
google到了一个Nlog(N)的程序，基本上看懂了，自己写了一遍，AC，顺便贴在后面吧。
B, Problem 1399 - Sky Code
不会，嗯。完全没思路。我讨厌纯数学题=.=
C, Problem 1400 - Perfect Election
暴力写了个，没过样例，于是没交。
——2SAT问题，合取，析取，范式，DFS，强联通分量。晚上跑步的时候feli说的。不很懂，详见Baidu Or Google
D, Problem 1401 - Lucky Cities
没看，貌似图论，想必是不会。
E, Problem 1402 - Build Your Home
顺序(顺时针或者逆时针)给出多边形(不一定是凸多边形)的顶点，求面积。
用三角形的方法写了一个，WA了。后来张文说他用的梯形写的，AC了，于是改了一下，我也AC了。
看来还是要注意，sqrt尽量少用，嗯。代码也贴后面吧。
F, Problem 1403 - Quick Answer
并查集，看起来不难阿，代码也写得蛮快，就TMD的总是wa，我郁闷。回头学习下别人的代码吧。。WA的代码就不贴了
＠2009-03-09 AC了，我的思路是基本上是正确的，有2个小错
a. 输入有点小问题；因为题目的输入数据有一些trailing space，囧。
b. q x y，当x==y的时候输出的是NO。
代码也附在后面吧，我不会标准的并查集写法，这是按自己的想法写的。
G, 没看。
H, Problem 1406 - Internet Service Providers
纯数学题，蛮简单，代码贴后面，不写什么了。
I, Problem 1405 - GCD Determinant
没做，看群里的说法，也是纯数学题=.= 貌似是把欧拉函数乘起来就好了，不要算行列式，嗯。
一共写了5题，3AC，1WA，1没交。
A, Problem 1398 - Stock Exchange
最长递增自序列。因为是n <= 100000的数据量，所以显然N^2的程序是不行的，
google到了一个Nlog(N)的程序，基本上看懂了，自己写了一遍，AC，顺便贴在后面吧。
B, Problem 1399 - Sky Code
不会，嗯。完全没思路。我讨厌纯数学题=.=
C, Problem 1400 - Perfect Election
暴力写了个，没过样例，于是没交。
——2SAT问题，合取，析取，范式，DFS，强联通分量。晚上跑步的时候feli说的。不很懂，详见Baidu Or Google
D, Problem 1401 - Lucky Cities
没看，貌似图论，想必是不会。
E, Problem 1402 - Build Your Home
顺序(顺时针或者逆时针)给出多边形(不一定是凸多边形)的顶点，求面积。
用三角形的方法写了一个，WA了。后来张文说他用的梯形写的，AC了，于是改了一下，我也AC了。
看来还是要注意，sqrt尽量少用，嗯。代码也贴后面吧。
F, Problem 1403 - Quick Answer
并查集，看起来不难阿，代码也写得蛮快，就TMD的总是wa，我郁闷。回头学习下别人的代码吧。。WA的代码就不贴了
＠2009-03-09 AC了，我的思路是基本上是正确的，有2个小错
a. 输入有点小问题；因为题目的输入数据有一些trailing space，囧。
b. q x y，当x==y的时候输出的是NO。
代码也附在后面吧，我不会标准的并查集写法，这是按自己的想法写的。
G, 没看。
H, Problem 1406 - Internet Service Providers
纯数学题，蛮简单，代码贴后面，不写什么了。
I, Problem 1405 - GCD Determinant
没做，看群里的说法，也是纯数学题=.= 貌似是把欧拉函数乘起来就好了，不要算行列式，嗯。
Mar
8
抽象题意：给出最多200,000个不超过1000的非负整数，对最多200,000次以下两类操作进行处理
1. M x y ——求第x到第y个整数之间的所有整数的和。
2. S x v ——将第x个整数的值置为v。
显然，硬搞要TLE的，稍微想了一下，就知道应该用线段树(或者树状数组?)来完成。
关于线段树可以参考 http://acm.whu.edu.cn/blog/read.php?26 以及 http://acm.whu.edu.cn/blog/read.php?51
简单的说，就是用一个平衡二叉树来存储这些东西，
每个叶节点存放一个整数(一个单位"线段")，
而每个分支节点存放的是一条"线段"
在M操作的时候，只要递归地将线段xy分割，能够在logN的时间内查询出
在S操作的时候，只要递归地找到对应的叶节点更新，并在返回的时候一层层更新涉及到的分支节点即可，也是logN。
好久没有写稍长的代码了，这个线段树的具体实现也忘得差不多了，还是去翻了一下yyt的论文。
不过这次写得顺利多了，思路比较清晰。
具体的代码为
1. M x y ——求第x到第y个整数之间的所有整数的和。
2. S x v ——将第x个整数的值置为v。
显然，硬搞要TLE的，稍微想了一下，就知道应该用线段树(或者树状数组?)来完成。
关于线段树可以参考 http://acm.whu.edu.cn/blog/read.php?26 以及 http://acm.whu.edu.cn/blog/read.php?51
简单的说，就是用一个平衡二叉树来存储这些东西，
每个叶节点存放一个整数(一个单位"线段")，
而每个分支节点存放的是一条"线段"
在M操作的时候，只要递归地将线段xy分割，能够在logN的时间内查询出
在S操作的时候，只要递归地找到对应的叶节点更新，并在返回的时候一层层更新涉及到的分支节点即可，也是logN。
好久没有写稍长的代码了，这个线段树的具体实现也忘得差不多了，还是去翻了一下yyt的论文。
不过这次写得顺利多了，思路比较清晰。
具体的代码为
Feb
25
这篇看起来忒有意思，回头有空了我翻译一下。
How To Read C Declarations
zz from http://blog.chinaunix.net/u1/36290/showart_443799.html
Even experienced C programmers have difficulty reading declarations that go beyond simple arrays and pointers. For example, is the following an array of pointers or a pointer to an array?
What the heck does the following mean?
Naturally, it's a pointer to an array of pointers to functions returning integers. ;)
This short article tells you how to read any C declaration correctly using a very simple technique. I am 99% certain that I read this in a book in the late 1980s, but I can't remember where. I doubt that I discovered this on my own (even though I've always been delighted by computer language structure and esoterica). I do remember, however, building a simple program that would translate any declaration into English.
The golden rule
The rule goes like this:
The degenerate case is:
How To Read C Declarations
zz from http://blog.chinaunix.net/u1/36290/showart_443799.html
Even experienced C programmers have difficulty reading declarations that go beyond simple arrays and pointers. For example, is the following an array of pointers or a pointer to an array?
int *a[10];
What the heck does the following mean?
int (*(*vtable)[])();
Naturally, it's a pointer to an array of pointers to functions returning integers. ;)
This short article tells you how to read any C declaration correctly using a very simple technique. I am 99% certain that I read this in a book in the late 1980s, but I can't remember where. I doubt that I discovered this on my own (even though I've always been delighted by computer language structure and esoterica). I do remember, however, building a simple program that would translate any declaration into English.
The golden rule
The rule goes like this:
引用
"Start at the variable name (or innermost construct if no identifier is present. Look right without jumping over a right parenthesis; say what you see. Look left again without jumping over a parenthesis; say what you see. Jump out a level of parentheses if any. Look right; say what you see. Look left; say what you see. Continue in this manner until you say the variable type or return type."
The degenerate case is:
Feb
19
众所皆知，以下代码可以实现两个变量的交换：
于是用这个写了一个随机化快速排序(防止特殊情况下的算法退化，代码很简单，如果认识快排，应该不难读懂)
看起来不错，可是运行结果不对，为什么呢？
因为
int a, b;
a = a ^ b;
b = a ^ b;
a = a ^ b;
a = a ^ b;
b = a ^ b;
a = a ^ b;
于是用这个写了一个随机化快速排序(防止特殊情况下的算法退化，代码很简单，如果认识快排，应该不难读懂)
void qsort(int a[], int s, int e){
int i = s, j = e, t, p;
if (s < e){
p = rand() % (e - s + 1) + s;
a[s] ^= a[p], a[p] ^= a[s], a[s] ^= a[p];
t = a[s];
while(i != j){
while(i < j && a[j] > t) j--;
if(i < j) a[i++] = a[j];
while(i < j && a[i] < t) i++;
if(i < j) a[j--] = a[i];
}
a[i] = t;
qsort(a, s, i - 1);
qsort(a, i + 1, e);
}
}
int i = s, j = e, t, p;
if (s < e){
p = rand() % (e - s + 1) + s;
a[s] ^= a[p], a[p] ^= a[s], a[s] ^= a[p];
t = a[s];
while(i != j){
while(i < j && a[j] > t) j--;
if(i < j) a[i++] = a[j];
while(i < j && a[i] < t) i++;
if(i < j) a[j--] = a[i];
}
a[i] = t;
qsort(a, s, i - 1);
qsort(a, i + 1, e);
}
}
看起来不错，可是运行结果不对，为什么呢？
因为
Feb
11
今天回顾汇编，顺手写了一个，居然还可以运行，挖咔咔，自恋一下
datas segment use16
str1 db "hello world!", 0dh, 0ah, "$"
datas ends
stacks segment use16
db 256 dup(0)
stacks ends
codes segment use16
assume cs:codes, ds:datas, ss:stacks
start: mov ax, datas
mov ds, ax
lea dx, str1
mov ah, 09h
int 21h
mov ah, 4ch
int 21h
codes ends
end start
Feb
5
这篇文章尾烂了，大家多给点意见，好充实其中的内容；也提出里面的不足。
---
我觉得这样的文章应该有人写过的，但是Google里面貌似没有(或许有英文版)
Baidu给了一个，不过不是很像样 http://baike.baidu.com/view/94274.htm
那我就写一个吧，这也是momodi大牛在上个学期初委托给我的一件事情。
这篇文章面向的对象是没有多少基础，或者是才学C语言或数据结构的同鞋们。
--
首先，什么是acm/icpc？ACM/ICPC(ACM International Collegiate Programming Contest, 国际大学生程序设计竞赛)是由国际计算机界历史悠久、颇具权威性的组织ACM(Association for Computing Machinery，国际计算机协会)主办的，世界上公认的规模最大、水平最高的国际大学生程序设计竞赛。
——这段定义来自 百度百科 -> ACM/ICPC，其实说简单了就几个字：想算法，写程序，解题目。
---
我觉得这样的文章应该有人写过的，但是Google里面貌似没有(或许有英文版)
Baidu给了一个，不过不是很像样 http://baike.baidu.com/view/94274.htm
那我就写一个吧，这也是momodi大牛在上个学期初委托给我的一件事情。
这篇文章面向的对象是没有多少基础，或者是才学C语言或数据结构的同鞋们。
--
首先，什么是acm/icpc？ACM/ICPC(ACM International Collegiate Programming Contest, 国际大学生程序设计竞赛)是由国际计算机界历史悠久、颇具权威性的组织ACM(Association for Computing Machinery，国际计算机协会)主办的，世界上公认的规模最大、水平最高的国际大学生程序设计竞赛。
——这段定义来自 百度百科 -> ACM/ICPC，其实说简单了就几个字：想算法，写程序，解题目。
Jan
11
Jan
9
这是今天算法考试的最后一题，设计一个动态规划的算法来求两个字符串的编辑距离。
以为自己做对了，很happy —— 其实错了，好笨，sigh.
--
Levenshtein Distance (LD, 来文史特距离)也叫edit distance(编辑距离)，它用来表示2个字符串的相似度，LD定义为需要最少多少步基本操作才能让2个字符串相等，基本操作包含3个：插入, 删除, 替换；比如，kiteen和sitting之间的距离可以这么计算：
1，kitten -- > sitten, 替换k为s；
2，sitten -- > sittin, 替换e为i;
3，sittin -- > sitting, 增加g；
所以，其LD为3。
设计状态d[m][n] = d(A[1..m], B[1..n])，易知：
d[0][0] = 0;
d[i][0] = i;
d[0][j] = j;
d[i][j] = min( d[i-1][j-1] + (If A[i]=B[j] Then 0 Else 1 End If), //修改一个字符
d[i-1][j] + 1, //插入一个字符
d[i][j-1] + 1 //删除一个字符
于是可以递推地填满一个 m * n 的矩阵，即得答案。
计算LD的算法表示为(C++代码)：
这个算法其实就是一个矩阵的计算：
最后的d[m][n]就是求得的答案。
@ 2009-06-14
贴一个优化空间复杂度为O(n)的代码(滚动数组)：
以为自己做对了，很happy —— 其实错了，好笨，sigh.
--
Levenshtein Distance (LD, 来文史特距离)也叫edit distance(编辑距离)，它用来表示2个字符串的相似度，LD定义为需要最少多少步基本操作才能让2个字符串相等，基本操作包含3个：插入, 删除, 替换；比如，kiteen和sitting之间的距离可以这么计算：
1，kitten -- > sitten, 替换k为s；
2，sitten -- > sittin, 替换e为i;
3，sittin -- > sitting, 增加g；
所以，其LD为3。
设计状态d[m][n] = d(A[1..m], B[1..n])，易知：
d[0][0] = 0;
d[i][0] = i;
d[0][j] = j;
d[i][j] = min( d[i-1][j-1] + (If A[i]=B[j] Then 0 Else 1 End If), //修改一个字符
d[i-1][j] + 1, //插入一个字符
d[i][j-1] + 1 //删除一个字符
于是可以递推地填满一个 m * n 的矩阵，即得答案。
计算LD的算法表示为(C++代码)：
int d[1010][1010];
int dist(string a, string b){
int m = a.size(), n = b.size(), i, j;
for(i = 0; i <= m; ++i) d[i][0] = i;
for(j = 0; j <= n; ++j) d[0][j] = j;
for (i = 1; i <= m; ++i){
for(j = 1; j <= n; ++j){
// -------------- a, b是从0开始计数的
d[i][j] = d[i-1][j-1] + (a[i-1]==b[j-1]?0:1); //修改一个字符
d[i][j] = min(d[i][j], d[i-1][j] + 1); //插入一个字符
d[i][j] = min(d[i][j], d[i][j-1] + 1); //删除一个字符
}
}
for (i = 0; i <= m; ++i){ //打印矩阵
for(j = 0; j <= n; ++j)
printf("%5d ", d[i][j]);
printf("\n");
}
return d[m][n];
}
int dist(string a, string b){
int m = a.size(), n = b.size(), i, j;
for(i = 0; i <= m; ++i) d[i][0] = i;
for(j = 0; j <= n; ++j) d[0][j] = j;
for (i = 1; i <= m; ++i){
for(j = 1; j <= n; ++j){
// -------------- a, b是从0开始计数的
d[i][j] = d[i-1][j-1] + (a[i-1]==b[j-1]?0:1); //修改一个字符
d[i][j] = min(d[i][j], d[i-1][j] + 1); //插入一个字符
d[i][j] = min(d[i][j], d[i][j-1] + 1); //删除一个字符
}
}
for (i = 0; i <= m; ++i){ //打印矩阵
for(j = 0; j <= n; ++j)
printf("%5d ", d[i][j]);
printf("\n");
}
return d[m][n];
}
这个算法其实就是一个矩阵的计算：
引用
调用dist("abcdef", "acddaf")可以得到输出为:
0 1 2 3 4 5 6
1 0 1 2 3 4 5
2 1 1 2 3 4 5
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 3 3
0 1 2 3 4 5 6
1 0 1 2 3 4 5
2 1 1 2 3 4 5
3 2 1 2 3 4 5
4 3 2 1 2 3 4
5 4 3 2 2 3 4
6 5 4 3 3 3 3
最后的d[m][n]就是求得的答案。
@ 2009-06-14
贴一个优化空间复杂度为O(n)的代码(滚动数组)：
int diff(char *a, char *b){
int *d[2], i, j;
int m = strlen(a), n = strlen(b);
d[0] = new int[n + 1];
d[1] = new int[n + 1];
int turn = 0, pre, t;
for (i = 0; i <= n; ++i) d[turn][i] = i;
for (i = 1; i <= m; ++i){
pre = turn;
turn = (turn + 1) % 2;
d[turn][0] = i;
for(int p=0;p<=n;p++)printf("%d ",d[pre][p]);printf("\n");
for(j = 1; j <= n; ++j){
t = d[pre][j-1] + (a[i-1] == b[j-1] ? 0 : 1);
t = min(t, d[pre][j] + 1);
d[turn][j] = min(t, d[turn][j-1] + 1);
}
}
for(int p=0;p<=n;p++)printf("%d ",d[turn][p]);printf("\n");
t = d[turn][n];
delete[] d[0];
delete[] d[1];
return t;
}
int *d[2], i, j;
int m = strlen(a), n = strlen(b);
d[0] = new int[n + 1];
d[1] = new int[n + 1];
int turn = 0, pre, t;
for (i = 0; i <= n; ++i) d[turn][i] = i;
for (i = 1; i <= m; ++i){
pre = turn;
turn = (turn + 1) % 2;
d[turn][0] = i;
for(int p=0;p<=n;p++)printf("%d ",d[pre][p]);printf("\n");
for(j = 1; j <= n; ++j){
t = d[pre][j-1] + (a[i-1] == b[j-1] ? 0 : 1);
t = min(t, d[pre][j] + 1);
d[turn][j] = min(t, d[turn][j-1] + 1);
}
}
for(int p=0;p<=n;p++)printf("%d ",d[turn][p]);printf("\n");
t = d[turn][n];
delete[] d[0];
delete[] d[1];
return t;
}
