Mar
9
前些天从某网站下载到了POJ的程序(不是源码) ( @ http://www.dssz.com/250473.html )
要1个积分的。1个积分要1个大洋的。一次性最少充10个积分的。于是我就少了10个大洋。于是就down到了POJ。
down下来是12MB，解压后大几十MB，发现里面带有一个3.4.2版的gcc，40+MB，Orz。去掉那个gcc打包，2MB。
在自己机器上架起来了。Windows(XP) + Tomcat(5.5.27) + JDK(6)。可以正常运行。
反正某一次我去申请了，填了个表，但是PKU那边根本没回复。
刚刚到POJ上面去看了一遍，貌似以前的申请已经被通过了，再次点开那个页面就可以下载了，我囧。
下载下来一看，12.9MB，gcc还是3.4.2。原来是我浪费了10个大洋。
down下来的包里面有一个license.txt，全英文的(真无聊。。)，之前down下来懒得看
这回直接贴到translate.google.com，然后看到超搞笑的翻译：
看来那个站点还是违反的这个license的，嗯。
看到第六点：
看来还是不允许随便流传的。。。
要1个积分的。1个积分要1个大洋的。一次性最少充10个积分的。于是我就少了10个大洋。于是就down到了POJ。
down下来是12MB，解压后大几十MB，发现里面带有一个3.4.2版的gcc，40+MB，Orz。去掉那个gcc打包，2MB。
在自己机器上架起来了。Windows(XP) + Tomcat(5.5.27) + JDK(6)。可以正常运行。
反正某一次我去申请了，填了个表，但是PKU那边根本没回复。
刚刚到POJ上面去看了一遍，貌似以前的申请已经被通过了，再次点开那个页面就可以下载了，我囧。
下载下来一看，12.9MB，gcc还是3.4.2。原来是我浪费了10个大洋。
down下来的包里面有一个license.txt，全英文的(真无聊。。)，之前down下来懒得看
这回直接贴到translate.google.com，然后看到超搞笑的翻译：
引用
...the source code of the Software. ---- ...源代码的软件
引用
5. LIMITATION OF LIABILITY
In no event will PKU ACM Team be liable for any damages, including but not limited to any loss of revenue, profit, or data, however caused, directly or indirectly, by the Software or by this Agreement.
5 。责任限制
在任何情况下，北京大学计算机小组须承担任何赔偿，包括但不限于任何损失的营业收入，利润，或数据，但是造成的直接或间接的软件或通过本协定。
In no event will PKU ACM Team be liable for any damages, including but not limited to any loss of revenue, profit, or data, however caused, directly or indirectly, by the Software or by this Agreement.
5 。责任限制
在任何情况下，北京大学计算机小组须承担任何赔偿，包括但不限于任何损失的营业收入，利润，或数据，但是造成的直接或间接的软件或通过本协定。
看来那个站点还是违反的这个license的，嗯。
看到第六点：
引用
6. DISTRIBUTION
No distribution is to be made of the Software by the Licensee. The Licensee may make one copy of the Software for backup purpose only.
//Google的翻译
6 。分布
没有分配将软件由持牌人。持牌人可一复制的软件，如备份用途。
No distribution is to be made of the Software by the Licensee. The Licensee may make one copy of the Software for backup purpose only.
//Google的翻译
6 。分布
没有分配将软件由持牌人。持牌人可一复制的软件，如备份用途。
看来还是不允许随便流传的。。。
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
