long1 vs longpo

屌丝们！别看片别强撸别搬砖了！！！！看看你们应该怎样逆袭！

long1 — Wed, 23 May 2012 21:40:06 +0800

屌丝需要逆袭

不需要高帅富，但需要有自我！！

520晚安！

long1 — Mon, 21 May 2012 00:54:20 +0800

世界上最遥远的距离不是生与死，而是我站在你面前，你却不知道我爱你；

　　世界上最遥远的距离不是我在站在你面前，你不知道我爱你，而是明明相爱却不能在一起；

　　世界上最遥远的距离不是明明相爱却不能在一起，而是明明无法抵挡这种思念，却还得故意装作丝毫没有把你放在心上。

　　人生总会有物是人非的感慨和无奈，而最令人心碎的莫过于错过爱情。

今天是5月20日，也就是传说中的520(我爱你),更是2012年的520，也许这一年会是世界末日，在世界末日前的520，是不是真的有一种生离死别的滋味。缘起缘灭缘自在，情深情浅不由人，在死亡面前，什么都是那么真，人这一生，能有一份真挚的感情，是多么难能可贵。

爱情这玩意，能诗能画，也可粗茶淡饭，平日里，表现的很多刻意，很多误会，原本快因爱成恨相互烦躁，突然因为简单的一句表白，顿时化开所有矛盾，原来所有的事，都因爱由生，因爱而灭。所以即使老的发俗的剧本，韩剧也能让一大堆人内流满面：

"你知道我找你有多辛苦吗，就留下一封信，还联系不上，你想让我急死吗，你为什么要把我变成这样，你为什么让我变成这副境地，昨天一天又心痛又心跳闷闷的，都快炸掉了，呼吸都困难的我，自己都不知道是怎么回事，一天到晚差点疯了，喊得撕心裂肺也没觉得舒服点，但是现在看到你的脸我知道。。。我，原来一天都在想念你，我。。。喜欢你！"

这是最近电视剧《屋塔房王世子》里男主角向女主角告白的台词，其实说的都没什么逻辑了，但似乎感情就是这样，越乱，越明白。

一个拥抱，一个吻，或许，没有什么语言比这几个简单的动作。之后，就觉得之前的行为傻乎乎，但又傻得可爱。

嘻哈四重奏4，经理傻傻的追求了小乔多次，海边浪漫又荒唐，让整个剧情变得搞笑而生动，最后在海边表白了，笑着笑着，就感动了，原来过去一幕幕傻动作，会让最后的表白如此动情，如此难以忘怀！

在师大六年了，好多520悄无声息的流逝了，快离开之际，猛然发现，美好的大学校园在某一天某一个角落，也应该留下很多难以忘怀的瞬间，哪怕似乎已近弥留之际，留下点情怀。

突然想听那首歌《海之花》，嘻哈四重奏的主题曲。

是流星就有它瞬间的美丽，是花蕾就注定有它的绽放，就像鸟儿在天空中翱翔，鱼儿在水中游弋。纵然，我的生命是一片辽阔的天空，也不愿你是一颗稍纵即逝的流星！我宁愿你的耀眼是一种永恒；我宁愿你的美丽是一种深邃；我宁愿你的微笑呈绽一种幸福；我宁愿你的不经意透视一种抚慰……

歌词：

望着这片海

泪水流下来

我的心中有无限的感慨

被风吹过的地方

看来有些乱

其实心很冷很孤单

望着这片海

幻想着未来

我的心中仿佛有了依赖 oh~

过去的伤痕留给岁月做尘埃

这些年却越变越实在

我的爱

已经消失在从前那片海

耳边却依然回荡着对海的誓言

我的爱

依然停留在从前那片海

因为爱

深深沉入这片海

（Music）啊~~~~

望着这片海

幻想着未来

我的心中仿佛有了依赖 oh~

过去的伤痕留给岁月做尘埃

这些年却越变越实在

我的爱

已经消失在从前那片海

耳边却依然回荡着对海的誓言

我的爱

依然停留在从前那片海

因为爱

深深沉入这片海

望着宁静的大海

望着再也不回来的爱和海阔天空的未来

我的爱

已经消失在从前那片海

耳边却依然回荡着对海的誓言

我的爱

依然停留在从前那片海

因为爱

深深沉入这片海

因为爱

深深沉入我心海

http://v.youku.com/v_show/id_XMzc5NzkyOTM2.html

1020 AOE网络拓扑排序

long1 — Sat, 19 May 2012 15:14:03 +0800

AOE网络

Case Time Limit:0MS

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9		Accepted: 4

Description

AOE网络：Activity on edge network，若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表示活动的开销（如该活动持续的时间），则此带权的有向图称为AOE网。如果用AOE网来表示一项工程，那么，仅仅考虑各个子工程之间的优先关系还不够，更多的是关心整个工程完成的最短时间是多少。在项目管理中，关键路径是指网络终端元素的元素的序列，该序列具有最长的总工期并决定了整个项目的最短完成时间。现在给定一个AOE网络，求出它的关键路径的长度。

Input

输入数据第一行，两个整数n和m,表示工程个数具有优先关系的工程对数。接下来一行n个数，表示完成每个工程所需要的时间，接下来m行，每行两个整数a，b,表示要完成b，需要先完成a。(1<=a,b<=n,a!=b，1<=n<=100)。

Output

输出一个整数，表示关键路径的长度，即完成整个项目需要花费的最少时间。

Sample Input

 5 5 1 2 3 4 5 1 2 1 3 1 4 2 5 3 5

Sample Output

Hint

一条关键路径为1 3 5

方法1：拓扑排序

#include

using namespace std;

int n,m;

int de[205],ans[205];

vector ne[205];

bool out[205];

int val[205];

int main(){

int i,j,cas,a,b;

while( scanf("%d%d",&n,&m) != EOF ){

for(i=1; i<=n; i++) scanf("%d",&val[i]);

for(i=1; i<=n; i++) {

ne[i].clear(); out[i]=false;

}

for(i=0; i

scanf("%d%d",&a,&b);

if(a!=b) ne[a].push_back(b);

}

bool f=0;

for(j=1; j<=n; j++){

memset(de,0,sizeof(de));

if(f) break;

for(i=1; i<=n; i++){ //拓扑排序，很土

if(out[i]) continue;

int s=ne[i].size(),k,v;

for(k=0; k

//printf("%d %d\n",i,ne[i][k]);

v=ne[i][k]; de[v]++;

}

for(i=1; i<=n; i++){ //从重的开始赋值

if(de[i]==0 && !out[i]){

ans[j]=i; out[i]=true; break;

}

if(i==0) f=1; //有环了

}

if(f) { printf("Impossible\n"); while(1); continue; }

//for(i=1; i<=n; i++) printf("%d ",ans[i]);

int res=0;

int t[205];

for(i=1; i<=n; i++) t[i]=0;

for(i=1; i<=n; i++){

int x=ans[i];

t[x]+=val[x];

res=max(res, t[x]);

for(j=0; j

t[ne[x][j]]=max(t[ne[x][j]], t[x]);

}

printf("%d\n",res);

}

return 0;

}

方法2：BFS

#include #include #define M 105 int cost[M],Indegree[M],Outdegree[M]; int map[M][M]; int Q[M],dis[M]; int solve(int n){  int L,H,i,k,y;  L=0,H=0;  for(i=1;i<=n;i++){   dis[i]=0;    //给每个项目最早完成时间赋初值    if(Indegree[i]==0){//没有前置项目的项目可以直接开始了     Q[H++]=i;   }  }  while(L<H){ //模拟拓扑排序过程，求出每个项目最早可以开始的时间    k=Q[L++];   for(y=1;y<=n+1;y++)    if(map[k][y]){     if(dis[y]<dis[k]+map[k][y])//y的所有前置项目的最晚完成时间作为它最早开始时间       dis[y]=dis[k]+map[k][y];     Indegree[y]--;     if(Indegree[y]==0){//入度为0时，表示它的前置项目都已完成       Q[H++]=y;     }    }  }  //第n+1个点是虚拟出来的，所有没有后置项目的项目作为它的前置项目   //当它所有的前置项目都完成时，表示整个项目完成   return dis[n+1]; } int main(){  int n,m,i,j,x,y;   scanf("%d %d",&n,&m);   for(i=1;i<=n;i++)    scanf("%d",&cost[i]);   memset(map,0,sizeof(map));//存储优先关系    memset(Indegree,0,sizeof(Indegree));//入度    memset(Outdegree,0,sizeof(Outdegree));//出度    while(m--&&scanf("%d %d",&x,&y)){    map[x][y]=1;    Indegree[y]++;    Outdegree[x]++;   }   for(i=1;i<=n;i++)    if(Outdegree[i]==0){//没有出度的项目作为第n+1项目的前置项目      map[i][n+1]=1;     Indegree[n+1]++;    }   for(i=1;i<=n;i++)    for(j=1;j<=n+1;j++)     if(map[i][j])map[i][j]=cost[i];//将优先关系的权值赋为前置项目要花费的时间    printf("%d\n",solve(n));  return 0; }

UVALive - 5137 Pyramids WordFinal 2011 J 搜索DP

long1 — Fri, 18 May 2012 12:32:16 +0800

这题也是去年总决赛遗憾的题，DP可以算结果，但路径很容易错，其实想到后期大部分数字都是有解的，并且路径不是很深，还是DFS好，效率也很高，就是细节还是很多的

Pyramids

Time Limit: 3000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

[Submit] [Go Back] [Status]

Description

It is not too hard to build a pyramid if you have a lot of identical cubes. On a flat foundation you lay, say, 10 x 10 cubes in a square. Centered on top of that square you lay a 9 x 9 square of cubes. Continuing this way you end up with a single cube, which is the top of the pyramid. The height of such a pyramid equals the length of its base, which in this case is 10. We call this a high pyramid.

If you think that a high pyramid is too steep, you can proceed as follows. On the 10 x 10 base square, lay an 8 x 8 square, then a 6 x 6 square, and so on, ending with a 2 x2 top square (if you start with a base of odd length, you end up with a single cube on top, of course). The height of this pyramid is about half the length of its base. We call this a low pyramid.

Once upon a time (quite a long time ago, actually) there was a pharaoh who inherited a large number of stone cubes from his father. He ordered his architect to use all of these cubes to build a pyramid, not leaving a single one unused. The architect kindly explained that not every number of cubes can form a pyramid. With 10 cubes you can build a low pyramid with base 3. With 5 cubes you can build a high pyramid of base 2. But no pyramid can be built using exactly 7 cubes.

The pharaoh was not amused, but after some thinking he came up with new restrictions.

All cubes must be used.
You may build more than one pyramid, but you must build as few pyramids as possible.
All pyramids must be different.
Each pyramid must have a height of at least 2.
Satisfying the above, the largest of the pyramids must be as large as possible (i.e., containing the most cubes).
Satisfying the above, the next-to-largest pyramid must be as large as possible.
And so on...

Drawing figures and pictures in the sand, it took the architect quite some time to come up with the best solution.

Write a program that determines how to meet the restrictions of the pharaoh, given the number of cubes.

Input

The input consists of several test cases, each one on a single line. A test case is an integer c, where 1c10⁶, giving the number of cubes available.

The last test case is followed by a line containing a single zero.

Output

For each test case, display its case number followed by the pyramids to be built. The pyramids should be ordered with the largest first. Pyramids are specified by the length of their base followed by an L for low pyramids or an H for high pyramids. If two different pyramids have the same number of cubes, list the high pyramid first. Print ``impossible" if it is not possible to meet the requirements of the pharaoh.

Follow the format of the sample output.

Sample Input

29 28 0

Sample Output

Case 1: 3H 3L 2H Case 2: impossible

whu isea 李岩的报告

J题：利用方块来建pyramid，每一层都为N*N的正方形。一种是High的，每层正方形边长递减1，一种是Low的，每层递减2。现在有N (<=10^6) 个方块，所有的都必须使用用来建立最少的pyramid。不能有相同的pyramid。相同个数最少的方案输出最大的包含方块最多的方案，依次定义优先级。输出方案。

由于平方增长的速度比较快，推测pyramid的种类并不多。用程序简单的跑一下，可以发现不同个数为320。DP的复杂度是够了，三千万，但是别激动，要输出方案。

比赛中，我很早就开了这个题，甚至有FB的幻想。但是一次又一次的WA的现实浇灭了理想，最终的board上，可以发现很多队伍也被卡在这道题目上很久，一道看上去很直接很老套的背包DP，究竟问题出在哪呢？

这场比赛我前期的主要精力都消磨在这道题了，而所有的代码实质上是一个错误的DP。这个错误却又一叶障目，让人迟迟走不出来。前面说过，DP的时间复杂度是三千万，直接做的话，空间复杂度也是三千万*数据类型，接近几G的内存要求。这在现场赛虽然是可以的，但是对于大部分时间还是刷OJ的ACMer，显然不够放心。于是试图寻找各种优化方法减小内存，就有了各种形态各异但都是错误方法的DP记录，回溯答案。

举我自己的错误方法。DP[i]记录i个方块能建立pyramid的最少值，pre[i]记录能转移过来的最小状态，输出N的拆分方案时，每次回溯到pre[n]的状态，保证当前组成的pyramid最大，递归处理。这个空间复杂度确实低，但是问题也很显然，由于输出的方案是pyramid递减的，就会遇到当前状态的pre[i]大于前一个输出的。修补方案，记录当前状态是否可行，如果出现大于的情况，枚举个数，回溯到可行的状态去。听上去挺好了，还是无情的WA。最后哑熊告诉我，DP求的都是错的，我才恍然大悟。

就不可以直接进行DP转移啊！必须记录当前使用到那一个pyramid，这样才能保证不同这个条件。也就是说，根本就绕不过去，最简单，也是最好的办法就是记录一个bool变量，记录当前方块数使用到某个pyramid是否可行，然后回溯。这道题暴露的问题就是，想问题千万不要想当然，先入为主很可怕，思路清晰严谨才是人间正途。

值得一提的是，这样写HDOJ还是过不了，虽然我建议刘老师把这个题的内存限制改大了，但由于没算好，128M还是不够用。在这儿通过的唯一方法就是暴搜。加一个最优性剪枝就行，最大的答案也只是6个而已，并且很快就找到了。

#include

using namespace std;

const int M=1000000;

const int N=1000;

int total[N],h[N],type[N];

int ind[N]; //命名index竟然编译错误，晕

int pt;

int n,limit,step[11];

bool flag;

char wd[]={'L','H'};

//int dp[M+1];

bool cmp(int a,int b){ //不建结构体，对下标排序

return total[a]>total[b];

}

void init(){

pt=0;

for(int i=2; ;i++){

int val=i*(i+1)*(2*i+1)/6;

//total[pt]=total[pt]+i*i; 简单点可以写成这样

//http://blog.163.com/lfw2565295@126/blog/static/122005162012418964333/

//公式推导看我博客，其实挺简单的

if(val>=M) break;

total[pt]=val; h[pt]=i; type[pt]=1;

pt++;

}

for(int i=3; ;i++){

int val=i*(i+1)*(i+2)/6;

if(val>=M) break;

total[pt]=val; h[pt]=i; type[pt]=0;

pt++;

}

for(int i=0; i

sort(ind,ind+pt,cmp);

/*for(int i=0; i

printf("%d ",total[index[i]]);

}

puts("");*/

优化效果不好，基本上都能实现的，DP时间也很费

printf("pt = %d\n",pt);

for(int i=0; i<=M; i++) dp[i]=0;

dp[0]=1;

int to=0;

for(int i=0; i

for(int j=to; j>=0; j--){

if(dp[j] && j+total[index[i]]<=M){

dp[j+total[index[i]]]=1;

to=max(to, j+total[index[i]]);

}

for(int i=0; i<200; i++) if(dp[i]) printf("%d ",i);

puts("");*/

}

bool dfs(int i, int s, int sum){

//printf("sum= %d %d\n",sum,total[index[i]]);

if(flag) return true;

if(sum==n) {

step[s]=-1;

flag=true;

return true;

}

if(sum>n || i==pt || s==limit) return false;

step[s]=ind[i];

dfs(i+1, s+1, sum+total[ind[i]]); //先搜这个，因为基本上上千以上的数字都能搜的到的

if(flag) return true; //已经找到了，不要再搜了，不然会覆盖掉step的

dfs(i+1, s, sum);

}

int main(){

init();

int cas=1;

while(scanf("%d",&n)){

if(n==0) break;

printf("Case %d:",cas++);

flag=false;

for(int k=1; k<=10; k++){ //优先还要保证步数最小！！！

limit=k;

dfs(0,0,0);

if(flag) break;

}

if(flag){

for(int i=0; ; i++){

if(step[i]==-1) break;

printf(" %d%c",h[step[i]],wd[type[step[i]]]);

}

puts("");

}else{

puts(" impossible");

}

自然数平方数列和立方数列求和高次推导低次

long1 — Fri, 18 May 2012 09:06:43 +0800

1^2+2^2+3^2+……+n^2=n(n+1)(2n+1)/6

利用立方差公式

n^3-(n-1)^3=1*[n^2+(n-1)^2+n(n-1)]

=n^2+(n-1)^2+n^2-n

=2*n^2+(n-1)^2-n

2^3-1^3=2*2^2+1^2-2

3^3-2^3=2*3^2+2^2-3

4^3-3^3=2*4^2+3^2-4

......

n^3-(n-1)^3=2*n^2+(n-1)^2-n

各等式全相加

n^3-1^3=2*(2^2+3^2+...+n^2)+[1^2+2^2+...+(n-1)^2]-(2+3+4+...+n)

n^3-1=2*(1^2+2^2+3^2+...+n^2)-2+[1^2+2^2+...+(n-1)^2+n^2]-n^2-(2+3+4+...+n)

n^3-1=3*(1^2+2^2+3^2+...+n^2)-2-n^2-(1+2+3+...+n)+1

n^3-1=3(1^2+2^2+...+n^2)-1-n^2-n(n+1)/2

3(1^2+2^2+...+n^2)=n^3+n^2+n(n+1)/2=(n/2)(2n^2+2n+n+1)

=(n/2)(n+1)(2n+1)

1^2+2^2+3^2+...+n^2=n(n+1)(2n+1)/6

1^3+2^3+3^3+……+n^3=[n(n+1)/2]^2

(n+1)^4-n^4=[(n+1)^2+n^2][(n+1)^2-n^2]

=(2n^2+2n+1)(2n+1)

=4n^3+6n^2+4n+1

2^4-1^4=4*1^3+6*1^2+4*1+1

3^4-2^4=4*2^3+6*2^2+4*2+1

4^4-3^4=4*3^3+6*3^2+4*3+1

......

(n+1)^4-n^4=4*n^3+6*n^2+4*n+1

各式相加有

(n+1)^4-1=4*(1^3+2^3+3^3...+n^3)+6*(1^2+2^2+...+n^2)+4*(1+2+3+...+n)+n

4*(1^3+2^3+3^3+...+n^3)=(n+1)^4-1+6*[n(n+1)(2n+1)/6]+4*[(1+n)n/2]+n

=[n(n+1)]^2

1^3+2^3+...+n^3=[n(n+1)/2]^2

1^2+3^2+5^2+...+n^2=n(n+1)(n+2)/6 (n=2*i-1)

2^2+4^2+6^2+...+n^2=n(n+1)(n+2)/6 (n=2*i)

推导：

先要有这个公式

1^2+2^2+3^2+4^2+……+n^2=n(n+1)(2n+1)/6 然后把上面的式子变成 1^2+3^2+5^2+………+（2n-1）^2 =[1^2+2^2+3^2+4^2+……+(2n)^2]-[2^2+4^2+6^2+……+(2n)^2] =[1^2+2^2+3^2+4^2+……+(2n)^2]-4*[1^2+2^2+3^2+……+(n)^2] 再用上面的那个公式代入 有 (2n)(2n+1)(4n+1)/6-4*n(n+1)(2n+1)/6 最终得2n(2n-1)(2n+1)/6

UVALive - 5132 Coffee Central WordFinal 2011 E 旋转45度坐标转换

long1 — Thu, 17 May 2012 15:13:08 +0800

这是2011(去年)世界总决赛的E题，当时思路已经有了，坐标变化上卡住了，今天是2012世界总决赛的日子，想来解决下去年遗憾的题

http://acm.hust.edu.cn:8080/judge/problem/viewProblem.action?id=19842

Coffee Central

Time Limit: 5000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

[Submit] [Go Back] [Status]

Description

Is it just a fad or is it here to stay? You're not sure, but the steadily increasing number of coffee shops that are opening in your hometown has certainly become quite a draw. Apparently, people have become so addicted to coffee that apartments that are close to many coffee shops will actually fetch higher rents.

This has come to the attention of a local real-estate company. They are interested in identifying the most valuable locations in the city in terms of their proximity to large numbers of coffee shops. They have given you a map of the city, marked with the locations of coffee shops. Assuming that the average person is willing to walk only a fixed number of blocks for their morning coffee, you have to find the location from which one can reach the largest number of coffee shops. As you are probably aware, your hometown is built on a square grid layout, with blocks aligned on north-south and east-west axes. Since you have to walk along streets, the distance between intersections(a, b) and (c, d ) is | a - c| + | b - d|.

Input

The input contains several test cases. Each test case describes a city. The first line of each test case contains four integers dx, dy, n, and q. These are the dimensions of the city grid dx x dy (1dx, dy1000), the number of coffee shops n (0n5^.10⁵), and the number of queries q (1q20). Each of the next n lines contains two integers x_i and y_i (1x_idx, 1y_idy); these specify the location of the i-th coffee shop. There will be at most one coffee shop per intersection. Each of the next qlines contains a single integer m (0m10⁶), the maximal distance that a person is willing to walk for a cup of coffee.

The last test case is followed by a line containing four zeros.

Output

For each test case in the input, display its case number. Then display one line per query in the test case. Each line displays the maximum number of coffee shops reachable for the given query distance m followed by the optimal location. For example, the sample output shows that 3 coffee shops are within query distance 1 of the optimal location (3, 4), 4 shops are within query distance 2 of optimal location (2, 2), and 5 shops are within query distance 4 of optimal location (3, 1). If there are multiple optimal locations, pick the location that is furthest south (minimal positive integer y-coordinate). If there is still a tie, pick the location furthest west (minimal positive integer x-coordinate).

Follow the format of the sample output.

Sample Input

4 4 5 3 1 1 1 2 3 3 4 4 2 4 1 2  4 0 0 0 0

Sample Output

Case 1: 3 (3,4) 4 (2,2) 5 (3,1)

#include

using namespace std;

#define mp make_pair

const int M=2000;

int f[M][M];

int dx,dy,n,m,dxy;

//dxy表示把原来的矩形当成正方形，即空余部分当成不影响的点，dxy=max(dx,dy)

//当成正方形的话，旋转后的形状很容易识别

//坐标变化的话，有向上旋转45度，向下旋转45度，刚好x,y变化方式相反

//反过来推导就可以用二元一次方程组了，具体转换方式见下

int X,Y;

//X,Y表示原来的正方形旋转45度后，新的边长,X=Y=dxy*2-1

pair< int, pair > res;

int newx(int x,int y){ //向下45度，x坐标转化

return x+y-1;

}

int newy(int x,int y){ //向下45度，y坐标转化

return y-x+dxy;

}

int calc(int x,int y,int dis){

int minx=max(1,x-dis);

int maxx=min(X,x+dis);

int miny=max(1,y-dis);

int maxy=min(Y,y+dis);

return f[maxx][maxy]-f[maxx][miny-1]-f[minx-1][maxy]+f[minx-1][miny-1];

}

void solve(int dis){

res=mp(0, mp(1 , 1) );

for(int i=1; i<=dx; i++){

for(int j=1; j<=dy; j++){

int x=newx(i,j);

int y=newy(i,j);

int cnt=calc(x,y,dis);

if(cnt>res.first) res=mp(cnt, mp(i,j));

else if(cnt==res.first && (j

res=mp(cnt, mp(i,j));

}

int main(){

int cas=1;

while(scanf("%d%d%d%d",&dx,&dy,&n,&m)){

if(dx==0 && dy==0 && n==0 && m==0) break;

dxy=max(dx,dy);

X=Y=dxy*2-1;

for(int i=0; i<=X; i++){

for(int j=0; j<=Y; j++) f[i][j]=0;

}

for(int i=0; i

int a,b;

scanf("%d%d",&a,&b);

int x=newx(a,b);

int y=newy(a,b);

f[x][y]=1;

}

for(int i=1; i<=X; i++){

for(int j=1; j<=Y; j++){

f[i][j]+=f[i-1][j]+f[i][j-1]-f[i-1][j-1];

}

printf("Case %d:\n",cas++);

while(m--){

int dis;

scanf("%d",&dis);

solve(dis);

printf("%d (%d,%d)\n",res.first, res.second.first, res.second.second);

}

把之前的矩形，短边补长，变成正方形后，会好像的多，旋转后，可以模拟小规模数据，比如3*3的正方形，想象旋转45度后

(1,1) -> (1,3)

(1,2) -> (2,4)

(1,3) -> (3,5)

(2,1) -> (2,2)

(2,2) -> (3,3)

(2,3) -> (4,4)

(3,1) -> (3,1)

(3,2) -> (4,2)

(3,3) -> (5,3)

然后容易得出结论: newx=x+y-1 newy=y-x+dxy (dxy为正方形边长=3)

不管向上旋转45度还是向下旋转45度，对结果不影响，只要枚举一个位置坐标，然后看以这个位置坐标距离m范围内的矩形有多少个咖啡店就可以了

统计矩形内咖啡店个数就是经典的矩形统计DP了：

return f[maxx][maxy]-f[maxx][miny-1]-f[minx-1][maxy]+f[minx-1][miny-1];

所以整道题其实不是很难，转换坐标是关键部分

shell编程练习2

long1 — Wed, 16 May 2012 20:25:20 +0800

练习循环

for; while; break 2; continue;

makedir.sh:

#! /bin/bash

mkdir -p ~/桌面/dir

for i in 1 2 3 4 5

mkdir -p ~/桌面/dir/mydir${i}

if [ $? -eq 0 ] ; then #$?返回上一条命令的返回值如果是0表示成功退出

echo "创建mydir${i}成功"

continue

else

echo "串建mydir${i}失败"

done

long1lfw@ubuntu:~/桌面$ vim makedir.sh

long1lfw@ubuntu:~/桌面$ chmod +x makedir.sh

long1lfw@ubuntu:~/桌面$ ./makedir.sh

创建mydir1成功

创建mydir2成功

创建mydir3成功

创建mydir4成功

创建mydir5成功

这样，桌面上就串建了一个dir文件夹，里面有mydir{1 2 3 4 5}五个文件夹，分别在这些文件夹里随便建一些 doc; c; sh; 文件

然后写个备份功能的shell

cpdir.sh：

#! /bin/bash

mkdir -p ~/桌面/backup

i=1

while [ $i -le 5 ]

mkdir -p ~/桌面/backup/md${i}

if [ $? -eq 0 ] ; then

for j in doc c sh

cp ~/桌面/dir/mydir${i}/*.${j} ~/桌面/backup/md${i}

if [ $? -ne 0 ] ; then continue ; fi ;

done

else

echo "不能串建文件夹"

i=$(($i+1))

done

注意while里i需要$i； for里倒直接可以i;

上面如果break 2; 的话：

long1lfw@ubuntu:~/桌面$ ./cpdir.sh

cp: 无法 stat “/home/long1lfw/桌面/dir/mydir2/*.doc”: 没有那个文件或目录

一旦找不到*.${j} 类型的文件，就跳出了

break命令接受一个整型参数，大于等于1的整数，标记着退出循环的层数。

如果是continue的话，会报错，但继续复制：

long1lfw@ubuntu:~/桌面$ ./cpdir.sh

cp: 无法 stat “/home/long1lfw/桌面/dir/mydir2/*.doc”: 没有那个文件或目录

cp: 无法 stat “/home/long1lfw/桌面/dir/mydir3/*.sh”: 没有那个文件或目录

cp: 无法 stat “/home/long1lfw/桌面/dir/mydir4/*.doc”: 没有那个文件或目录

cp: 无法 stat “/home/long1lfw/桌面/dir/mydir4/*.c”: 没有那个文件或目录

cp: 无法 stat “/home/long1lfw/桌面/dir/mydir4/*.sh”: 没有那个文件或目录

cp: 无法 stat “/home/long1lfw/桌面/dir/mydir5/*.doc”: 没有那个文件或目录

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

输出数字玩玩：

digit.sh:

#! /bin/bash

x=0

while [ $x -lt 10 ]

y=0

x=$(($x+1))

while [ $y -lt $x ]

echo -e "$y \c" # echo -e 才能使得\c \n有效

y=$(($y+1))

done

echo

done

long1lfw@ubuntu:~/桌面$ vim digit.sh

long1lfw@ubuntu:~/桌面$ chmod +x digit.sh

long1lfw@ubuntu:~/桌面$ ./digit.s

0 1

0 1 2

0 1 2 3

0 1 2 3 4

0 1 2 3 4 5

0 1 2 3 4 5 6

0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7 8

0 1 2 3 4 5 6 7 8 9

注意： bash里 echo -e 才能使得\c \n 等有效

echo -e 后一般会接参数,

-e 若参数出现以下字符，则特别加以处理，而不会将它当成一般

文字输出：

\a 发出警告声；

\b 删除前一个字符；

\c 最后不加上换行符号；

\f 换行但光标仍旧停留在原来的位置；

\n 换行且光标移至行首；

\r 光标移至行首，但不换行；

\t 插入tab；

\v 与\f相同；

\\ 插入\字符；

\nnn 插入nnn（八进制）所代表的ASCII字符；

echo 语法：echo [-ne][字符串]或 echo [--help][--version]

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

SRM541 DIV2 250 500 1000的题模拟枚举最小时间 BFS java.util.Queue

long1 — Tue, 15 May 2012 10:21:14 +0800

//250

//枚举一个中间串，在后半部分也存在，并且他们前后，以及之间非空

import java.util.*;

import java.util.regex.*;

import java.text.*;

import java.math.*;

public class AkariDaisukiDiv2

{

public int countTuples(String S)

{

int res=0;

int n=S.length();

for(int i=1; i

for(int j=i+1; j

String x=S.substring(i, j); //j点不到达的

for(int k=j+1; k

int posK=S.indexOf(x,k); //存在posK为子串的第一个位置，不存在posK==0

if(posK>0 && posK+x.length()

res++;

k=posK;

}

return res;

}

//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

//500

//两两枚举可能有错，因为有些已经相遇消失了，不会再与其他相遇了

//最好是枚举步数，相遇的最小时间可能是0.5，也就是相距1的两个面对面行走

//所以一开始乘以2，最小时间就变为1了，然后枚举步数

//相遇肯定在图内相遇，遍历图最多2000*2步

import java.util.*;

import java.util.regex.*;

import java.text.*;

import java.math.*;

public class AntsMeet

{

public int countAnts(int[] x, int[] y, String direction)

{

int n=x.length;

int[] dx=new int[n];

int[] dy=new int[n];

for(int i=0; i

dx[i]=dy[i]=0;

}

for(int i=0; i

x[i]*=2;

y[i]*=2; //同时扩大两倍，相遇的最小时间单位就变成1了

switch(direction.charAt(i)){

case'N': dy[i]=1; break;

case'E': dx[i]=1; break;

case'S': dy[i]=-1; break;

case'W': dx[i]=-1; break;

}

boolean[] chk=new boolean[n];

for(int i=0; i

for(int i=0; i<=4000; i++){ //整张图最多2000*2个时刻能跑完，相遇肯定在图内

for(int j=0; j

if(chk[j]) continue;

x[j]+=dx[j];

y[j]+=dy[j];

}

for(int j=0; j

if(chk[j]) continue;

for(int k=j+1; k

if(!chk[k] && x[j]==x[k] && y[j]==y[k]){

chk[j]=true;

chk[k]=true;

}

int res=0;

for(boolean a: chk){

if(a==false) res++;

}

return res;

}

//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

//1000

//规模在4000*4000以内，直接宽搜，已经存在的点直接放入队列，然后四个方向扩展

//用数组判重，用到了java的Queue的offer和poll, 以及LinkedList动态结点

import java.util.*;

import java.util.regex.*;

import java.text.*;

import java.math.*;

public class NonXorLife

{

public class node{

int x,y,s;

node(int x,int y,int s){

this.x=x;

this.y=y;

this.s=s;

}

node(node n){

x=n.x;

y=n.y;

s=n.s;

}

public int countAliveCells(String[] field, int K)

{

Queue que=new java.util.LinkedList(); //使用动态的链表作为结点

int[] dx={1,-1,0,0};

int[] dy={0,0,1,-1};

int res=0;

int n=field.length,m=field[0].length();

boolean[][] chk=new boolean[4000][4000];

for(int i=0; i

for(int j=0; j

if(field[i].charAt(j)=='o' && !chk[i+2000][j+2000]){

chk[i+2000][j+2000]=true;

node tmp=new node(i+2000,j+2000,0);

que.offer(tmp);

res++;

}

while(!que.isEmpty()){

node tmp=new node(que.poll());

if(tmp.s>=K) break;

int x=tmp.x;

int y=tmp.y;

//System.out.println(x+" "+y+" "+tmp.s);

for(int i=0; i<4; i++){

int tx=x+dx[i];

int ty=y+dy[i];

if(!chk[tx][ty]){

chk[tx][ty]=true;

node ad=new node(tx,ty,tmp.s+1);

que.offer(ad);

res++;

}

return res;

}

//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

(zz) Java: Queue

long1 — Tue, 15 May 2012 10:18:35 +0800

学习Java: Queue队列

Java提供了Quere，相当好用，在1.5版本中又有增强。

add        增加一个元索                     如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove   移除并返回队列头部的元素    如果队列为空，则抛出一个NoSuchElementException异常
element  返回队列头部的元素             如果队列为空，则抛出一个NoSuchElementException异常
offer       添加一个元素并返回true       如果队列已满，则返回false
poll         移除并返问队列头部的元素    如果队列为空，则返回null
peek       返回队列头部的元素             如果队列为空，则返回null
put         添加一个元素                      如果队列满，则阻塞
take        移除并返回队列头部的元素     如果队列为空，则阻塞

remove、element、offer 、poll、peek 其实是属于Queue接口。

Queue：基本上，一个队列就是一个先入先出（FIFO）的数据结构

offer，add区别：
一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。
这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。

poll，remove区别：
remove() 和 poll() 方法都是从队列中删除第一个元素（head）。remove() 的行为与 Collection 接口的版本相似，
但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。

peek，element区别：
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

-----------------------------------------------------------------------------------------
Tiger中有2组Queue的实现：实现了新的BlockingQueue接口的
和没有实现的

-------------------------------------------------------------
没有实现的阻塞接口的：LinkedList：实现了java.util.Queue接口
java.util.AbstractQueue
内置的不阻塞队列： PriorityQueue 和 ConcurrentLinkedQueue

PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework 中加入两个具体集合实现。

PriorityQueue 类实质上维护了一个有序列表。加入到 Queue 中的元素根据它们的天然排序（通过其 java.util.Comparable 实现）或者根据传递给构造函数的 java.util.Comparator 实现来定位。

ConcurrentLinkedQueue 是基于链接节点的、线程安全的队列。并发访问不需要同步。因为它在队列的尾部添加元素并从头部删除它们，所以只要不需要知道队列的大小，ConcurrentLinkedQueue 对公共集合的共享访问就可以工作得很好。收集关于队列大小的信息会很慢，需要遍历队列。

------------------------------------------------------------------
实现阻塞接口的：

新的 java.util.concurrent 包在 Collection Framework 中可用的具体集合类中加入了 BlockingQueue 接口和五个阻塞队列类。

它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。

五个队列所提供的各有不同：

* ArrayBlockingQueue ：一个由数组支持的有界队列。
* LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
* PriorityBlockingQueue ：一个由优先级堆支持的无界优先级队列。
* DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
* SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

前两个类 ArrayBlockingQueue 和 LinkedBlockingQueue 几乎相同，只是在后备存储器方面有所不同， LinkedBlockingQueue 并不总是有容量界限。无大小界限的 LinkedBlockingQueue 类在添加元素时永远不会有阻塞队列的等待（至少在其中有Integer.MAX_VALUE 元素之前不会）。

PriorityBlockingQueue 是具有无界限容量的队列，它利用所包含元素的 Comparable 排序顺序来以逻辑顺序维护元素。可以将它看作 TreeSet 的可能替代物。不过对 PriorityBlockingQueue 有一个技巧。从 iterator() 返回的 Iterator 实例不需要以优先级顺序返回元素。如果必须以优先级顺序遍历所有元素，那么让它们都通过 toArray() 方法并自己对它们排序，像 Arrays.sort(pq.toArray())。

新的 DelayQueue 实现可能是其中最有意思（也是最复杂）的一个。加入到队列中的元素必须实现新的 Delayed 接口（只有一个方法 —— long getDelay(java.util.concurrent.TimeUnit unit) ）。因为队列的大小没有界限，使得添加可以立即返回，但是在延迟时间过去之前不能从队列中取出元素。如果多个元素完成了延迟，那么最早失效/失效时间最长的元素将第一个取出。实际上没有听上去这样复杂。

SynchronousQueue 类是最简单的。它没有内部容量。它就像线程之间的手递手机制。在队列中加入一个元素的生产者会等待另一个线程的消费者。当这个消费者出现时，这个元素就直接在消费者和生产者之间传递，永远不会加入到阻塞队列中。

----------------------------------------------
实验结果：

文档说BlockingQueue的队列：不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。

实验了一下，使用put、take是这样子的,线程在等待
而使用offer是立刻返回false的

srm541 div2 1000题用queue做宽搜

//1000

//规模在4000*4000以内，直接宽搜，已经存在的点直接放入队列，然后四个方向扩展

//用数组盘重，用到了java的Queue的offer和poll, 记忆LinkedList动态结点

import java.util.*;

import java.util.regex.*;

import java.text.*;

import java.math.*;

public class NonXorLife

{

public class node{

int x,y,s;

node(int x,int y,int s){

this.x=x;

this.y=y;

this.s=s;

}

node(node n){

x=n.x;

y=n.y;

s=n.s;

}

public int countAliveCells(String[] field, int K)

{

Queue que=new java.util.LinkedList(); //使用动态的链表作为结点

int[] dx={1,-1,0,0};

int[] dy={0,0,1,-1};

int res=0;

int n=field.length,m=field[0].length();

boolean[][] chk=new boolean[4000][4000];

for(int i=0; i

for(int j=0; j

if(field[i].charAt(j)=='o' && !chk[i+2000][j+2000]){

chk[i+2000][j+2000]=true;

node tmp=new node(i+2000,j+2000,0);

que.offer(tmp);

res++;

}

while(!que.isEmpty()){

node tmp=new node(que.poll());

if(tmp.s>=K) break;

int x=tmp.x;

int y=tmp.y;

//System.out.println(x+" "+y+" "+tmp.s);

for(int i=0; i<4; i++){

int tx=x+dx[i];

int ty=y+dy[i];

if(!chk[tx][ty]){

chk[tx][ty]=true;

node ad=new node(tx,ty,tmp.s+1);

que.offer(ad);

res++;

}

return res;

}

//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

JAVA的Random类(转)

long1 — Wed, 9 May 2012 21:16:00 +0800

Random类 (java.util)

Random类中实现的随机算法是伪随机，也就是有规则的随机。在进行随机时，随机算法的起源数字称为种子数(seed)，在种子数的基础上进行一定的变换，从而产生需要的随机数字。

相同种子数的Random对象，相同次数生成的随机数字是完全相同的。也就是说，两个种子数相同的Random对象，第一次生成的随机数字完全相同，第二次生成的随机数字也完全相同。这点在生成多个随机数字时需要特别注意。

下面介绍一下Random类的使用，以及如何生成指定区间的随机数组以及实现程序中要求的几率。

1、Random对象的生成

Random类包含两个构造方法，下面依次进行介绍：

a、public Random()

该构造方法使用一个和当前系统时间对应的相对时间有关的数字作为种子数，然后使用这个种子数构造Random对象。

b、public Random(long seed)

该构造方法可以通过制定一个种子数进行创建。

示例代码：

Random r = new Random();

Random r1 = new Random(10);

再次强调：种子数只是随机算法的起源数字，和生成的随机数字的区间无关。

2、Random类中的常用方法

Random类中的方法比较简单，每个方法的功能也很容易理解。需要说明的是，Random类中各方法生成的随机数字都是均匀分布的，也就是说区间内部的数字生成的几率是均等的。下面对这些方法做一下基本的介绍：

a、public boolean nextBoolean()

该方法的作用是生成一个随机的boolean值，生成true和false的值几率相等，也就是都是50%的几率。

b、public double nextDouble()

该方法的作用是生成一个随机的double值，数值介于[0,1.0)之间。

c、public int nextInt()

该方法的作用是生成一个随机的int值，该值介于int的区间，也就是-231到231-1之间。

如果需要生成指定区间的int值，则需要进行一定的数学变换，具体可以参看下面的使用示例中的代码。

d、public int nextInt(int n)

该方法的作用是生成一个随机的int值，该值介于[0,n)的区间，也就是0到n之间的随机int值，包含0而不包含n。

如果想生成指定区间的int值，也需要进行一定的数学变换，具体可以参看下面的使用示例中的代码。

e、public void setSeed(long seed)

该方法的作用是重新设置Random对象中的种子数。设置完种子数以后的Random对象和相同种子数使用new关键字创建出的Random对象相同。

3、Random类使用示例

使用Random类，一般是生成指定区间的随机数字，下面就一一介绍如何生成对应区间的随机数字。以下生成随机数的代码均使用以下Random对象r进行生成：

Random r = new Random();

a、生成[0,1.0)区间的小数

double d1 = r.nextDouble();

直接使用nextDouble方法获得。

b、生成[0,5.0)区间的小数

double d2 = r.nextDouble() * 5;

因为nextDouble方法生成的数字区间是[0,1.0)，将该区间扩大5倍即是要求的区间。

同理，生成[0,d)区间的随机小数，d为任意正的小数，则只需要将nextDouble方法的返回值乘以d即可。

c、生成[1,2.5)区间的小数

double d3 = r.nextDouble() * 1.5 + 1;

生成[1,2.5)区间的随机小数，则只需要首先生成[0,1.5)区间的随机数字，然后将生成的随机数区间加1即可。

同理，生成任意非从0开始的小数区间[d1,d2)范围的随机数字(其中d1不等于0)，则只需要首先生成[0,d2-d1)区间的随机数字，然后将生成的随机数字区间加上d1即可。

d、生成任意整数

int n1 = r.nextInt();

直接使用nextInt方法即可。

e、生成[0,10)区间的整数

int n2 = r.nextInt(10);

n2 = Math.abs(r.nextInt() % 10);

以上两行代码均可生成[0,10)区间的整数。

第一种实现使用Random类中的nextInt(int n)方法直接实现。

第二种实现中，首先调用nextInt()方法生成一个任意的int数字，该数字和10取余以后生成的数字区间为(-10,10)，然后再对该区间求绝对值，则得到的区间就是[0,10)了。

同理，生成任意[0,n)区间的随机整数，都可以使用如下代码：

int n2 = r.nextInt(n);

n2 = Math.abs(r.nextInt() % n);

f、生成[0,10]区间的整数

int n3 = r.nextInt(11);

n3 = Math.abs(r.nextInt() % 11);

相对于整数区间，[0,10]区间和[0,11)区间等价，所以即生成[0,11)区间的整数。

g、生成[-3,15)区间的整数

int n4 = r.nextInt(18) - 3;

n4 = Math.abs(r.nextInt() % 18) - 3;

生成非从0开始区间的随机整数，可以参看上面非从0开始的小数区间实现原理的说明。

h、几率实现

按照一定的几率实现程序逻辑也是随机处理可以解决的一个问题。下面以一个简单的示例演示如何使用随机数字实现几率的逻辑。

在前面的方法介绍中，nextInt(int n)方法中生成的数字是均匀的，也就是说该区间内部的每个数字生成的几率是相同的。那么如果生成一个[0,100)区间的随机整数，则每个数字生成的几率应该是相同的，而且由于该区间中总计有100个整数，所以每个数字的几率都是1%。按照这个理论，可以实现程序中的几率问题。

示例：随机生成一个整数，该整数以55%的几率生成1，以40%的几率生成2，以5%的几率生成3。实现的代码如下：

int n5 = r.nextInt(100);

int m; //结果数字

if(n5 < 55){ //55个数字的区间，55%的几率

m = 1;

}else if(n5 < 95){//[55,95)，40个数字的区间，40%的几率

m = 2;

}else{

m = 3;

}

因为每个数字的几率都是1%，则任意55个数字的区间的几率就是55%，为了代码方便书写，这里使用[0,55)区间的所有整数，后续的原理一样。

当然，这里的代码可以简化，因为几率都是5%的倍数，所以只要以5%为基础来控制几率即可，下面是简化的代码实现：

int n6 = r.nextInt(20);

int m1;

if(n6 < 11){

m1 = 1;

}else if(n6 < 19){

m1= 2;

}else{

m1 = 3;

}

在程序内部，几率的逻辑就可以按照上面的说明进行实现。

4、其它问题

a、相同种子数Random对象问题

前面介绍过，相同种子数的Random对象，相同次数生成的随机数字是完全相同的，下面是测试的代码：

Random r1 = new Random(10);

Random r2 = new Random(10);

for(int i = 0;i < 2;i++){

System.out.println(r1.nextInt());

System.out.println(r2.nextInt());

}

在该代码中，对象r1和r2使用的种子数都是10，则这两个对象相同次数生成的随机数是完全相同的。

如果想避免出现随机数字相同的情况，则需要注意，无论项目中需要生成多少个随机数字，都只使用一个Random对象即可。

b、关于Math类中的random方法

其实在Math类中也有一个random方法，该random方法的工作是生成一个[0,1.0)区间的随机小数。

通过阅读Math类的源代码可以发现，Math类中的random方法就是直接调用Random类中的nextDouble方法实现的。

只是random方法的调用比较简单，所以很多程序员都习惯使用Math类的random方法来生成随机数字。

我使用的例子：

import java.util.*;

import java.io.*;

public class Main {

private static int N=6;

private static String[] attr={"occupation","industry","workclass","education","majorocc","majorind"};

private static int[] num={47,52,10,17,15,24};

public static void main(String[] args){

try{

//FileReader inputfile=new FileReader("a.in");

//BufferedReader inputstream=new BufferedReader(inputfile);

FileWriter outputfile=new FileWriter("randonlydata.in");

BufferedWriter out=new BufferedWriter(outputfile);

for(int i=0; i

if(i>0) out.write(" # ");

out.write(attr[i]);

}

out.write("\n");

Random r = new Random(); //if double. simply use Math.random()

for(int i=0; i<10000; i++){

int[] val=new int[N];

out.write("linenum"+i+": ");

for(int j=0; j

if(j>0) out.write(" # ");

val[j]=Math.abs( r.nextInt() )%num[j]; //if I use r.nextInt(num[j]), everytime values are same

out.write(""+val[j]);

}

out.write("\n");

}

out.close(); //记得加 close

}catch(IOException e){

System.out.println("The load may be error!");

e.printStackTrace();

}

热情高涨的五月

long1 — Wed, 9 May 2012 13:21:18 +0800

4月过的真快，一下到了5月，主要4月事情也真多

回了一趟家，去了N次杭州，找实习，准备ZJNU邀请赛，一晃就到了5月

虽然组织过校赛，但组织邀请赛这样大型的赛事，比预想的麻烦多了，我是主要负责系统组，我们学校29幢机房是无盘工作站，没有硬盘，启动系统和存储文件都靠几台大服务器，方便管理，但给我们的工作，一开始造成了很多麻烦。

首先我们组想用11.10版本的ubuntu，结果公司的人说他们暂时还没刻最新的内核，所以让我们找老版本，于是我们尝试10.04，结果发现还是不行，能用的版本是9.04，9.10。无奈我们装了9.10后，发现ubuntu软件中心不支持了，很多软件需要网上手动找资源，下载安装，恶心的是软件还有依赖关系，不能用apt-get install方法真恶心，大部分搞定后，最后g++一时弄不好，旧版本也不好拿出手。于是找公司看他们能不能做个11.10内核，同时学校里做好买150个硬盘的准备。不过还好，公司及时弄好了内核，我们预装的系统和环境全部可以上传到服务器，然后发布到各个无盘电脑。

接下来是搞懂pc^2的使用，摸索了一段时间，测试了好几场练习赛，还有配置气球打印机，打印机，排名机，工程量很大，并且要多次测试，尤其打印服务总是莫名的出问题，热身赛前1小时还出问题了，幸好比赛中没出问题。

还有就是系统安全方面，周维民的儿子周智凯是个神牛，帮我们弄了服务器同传，还有发现我们没有禁掉两台机器间的通讯，较我们方法，正是赛时选手机只能访问固定几个ip了

整个比赛下来，还算顺利，A题数据发生了小错误，这个北大郭老师亲自出的，在比赛中途rejudge了，不过大部分队伍可能影响不大，这个错误也是平时我们也容易烦的，就是写了12个case，实际只有11个case，所以容易最后一个case莫名的错了，写的常规点的代码也能1A，因为这题最简单，大部分队伍都过了，所以影响还好。

赛后以为终于解放了，发现打印奖状是个大的体力活，留下10名左右的集训队员一直工作到晚上9点半才和韩老师一起吃晚饭，当时大家都累死，饿死了。

不过总算邀请赛顺利结束了。事后有些新队员不懂事，发布一些选手的代码到网上，被我们批评了，总感觉现在的新队员责任心和原则性牵强，整个比赛下来，很多老队员做了很多事，忙到最后一刻，新队员总是需要他们做点体力活时都找不到人影，同时，没有一份跟着学习的心，感觉没事就离开了，这样的态度还是很难学到很多的。

很多学校也有这样的感觉，新老交替时，下一代容易被强大的上一代带惯了，功利性强了，热情度低了，福利好了，义务活少了，所以怀念我当年06级时代的人，那个时候大部分人都还很难取得成绩，但热情度比现在高多了，把机房当作自己寝室一样，有时还在机房通宵过。所以希望新一代人不管成绩怎么样，既然加入了集训队，付出的多一点，期待的少一点，享受过程多一点，荣誉看得轻一点，当一份爱情来对待！

SRM542 DIV2 250 500 950的题模拟矩形想法组合概率

long1 — Wed, 9 May 2012 12:44:53 +0800

这次TC没注册上，但还是看了下题，做了下，感觉有难度，DIV1 零分都排名280多，能涨分，所以可见难度有点，做了下DIV2的题，挺好的题，想法考的比较多

//250

//模拟一下就可以了

import java.util.*;

import java.util.regex.*;

import java.text.*;

import java.math.*;

public class WorkingRabbits

{

public double getEfficiency(String[] profit)

{

int n=profit.length;

double sum=0;

for(int i=0; i

for(int j=i+1; j

int tmp=(int)profit[i].charAt(j)-'0';

sum+=(double)tmp;

}

double total=(double)(n*(n-1))/2;

return sum/total;

}

//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

//500

//关键在于找技巧，固定矩形，A,B,C绕一圈，就相当于矩形周长

//所以枚举小矩形长宽，计算数量

import java.util.*;

import java.util.regex.*;

import java.text.*;

import java.math.*;

public class PatrolRoute

{

public int countRoutes(int X, int Y, int minT, int maxT)

{

long res=0;

int mod=1000000007;

for(int i=3; i<=X; i++){

for(int j=3; j<=Y; j++){

int t=(i+j-2)*2;

//注意周长计算时，i个点，(i-1)边长

if(tmaxT) continue;

long tmp=(long)(X-i+1)*(Y-j+1)*(i-2)*(j-2)*6;

//(X-i+1)*(Y-j+1) 表示x*y大矩形里有多少i*j小矩形

//(i-2)*(j-2)*4表示，固定一个顶点，剩下两个点必须放在边长上，且不重叠的情况，4个定点所以乘以4

//(i-2)*(j-2)*2表示，固定对角一对顶点，剩下一个点必须在内嵌的矩形里面，2种对角所以乘以2

//这两种情况合并就是 (i-2)*(j-2)*6

res+=tmp;

res%=mod;

}

return (int)res;

}

//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

//950

//res[i]+=c[m][cnt1+cnt2]*cnt2*f[cnt1+cnt2-1] * f[m-cnt1-cnt2] / f[m];

//代表，字母一样的m-cnt1-cnt2个字母，位置随意

//不一样的字母cnt1+cnt2中，保证第一个位置是cnt2中选出来的，其余的位置随意

//f[m]总的位置安排

//任意两个words比较，看排名倒退一位的概率

import java.util.*;

import java.util.regex.*;

import java.text.*;

import java.math.*;

public class StrangeDictionary

{

public double[] getExpectedPositions(String[] words)

{

double[][] c=new double[55][55];

double[] f=new double[55];

for(int i=0; i<=50; i++){ //计算组合数

for(int j=0; j<=i; j++){

if(i==j || j==0) c[i][j]=1;

else{

c[i][j]=c[i-1][j];

if(j-1>=0) c[i][j]+=c[i-1][j-1];

}

f[0]=1;

for(int i=1; i<=50; i++) f[i]=f[i-1]*i; //计算阶层

int n=words.length;

int m=words[0].length();

double[] res=new double[n];

for(int i=0; i

res[i]=0.0;

for(int j=0; j

if(i==j) continue;

int cnt1=0,cnt2=0;

for(int k=0; k

if(words[i].charAt(k)

if(words[i].charAt(k)>words[j].charAt(k)) cnt2++;

}

res[i]+=c[m][cnt1+cnt2]*cnt2*f[cnt1+cnt2-1] * f[m-cnt1-cnt2] / f[m];

//代表，字母一样的m-cnt1-cnt2个字母，位置随意

//不一样的字母cnt1+cnt2中，保证第一个位置是cnt2中选出来的，其余的位置随意

//f[m]总的位置安排

//任意两个words比较，看排名倒退一位的概率

}

return res;

}

//Powered by KawigiEdit 2.1.4 (beta) modified by pivanof!

题目：

250：

Problem Statement

N rabbits (numbered 0 through N - 1) are going to work together at the new TopCoder office in Rabbitland.

Each pair of rabbits will make a certain profit when they work together. The efficiency of the group of rabbits is defined as follows: Let P be the sum of profits from all pairs of rabbits, and Q be the number of pairs of rabbits. Then the efficiency is the real number P / Q.

You are given a String[] profit, the j-th character of the i-th element of which represents the profit from the fact that rabbits i and j work together. The characters '0', '1', ..., '9' represent the values 0, 1, ..., 9, respectively. Compute and return the efficiency of this TopCoder office.

Definition

Class:	WorkingRabbits
Method:	getEfficiency
Parameters:	String[]
Returns:	double
Method signature:	double getEfficiency(String[] profit)
(be sure your method is public)

Notes

The returned value must have an absolute or relative error less than 1e-9.

Constraints

profit will contain between 2 and 50 elements, inclusive.

Each element of profit will contain exactly N characters, where N is the number of elements in profit.

Each character in each element of profit will be a digit ('0' - '9').

For each index i and j, the i-th character of the j-th element of profit will be equal to the j-th character of the i-th element of profit.

For each index i, the i-th character of the i-th element of profit will be '0'.

500：

Problem Statement

There are exactly X*Y places in the Planar Kingdom: For each pair of integers (x, y) such that 0 <= x < X and 0 <= y < Y there is a place with coordinates (x, y). When a citizen of the kingdom wants to move from (x1, y1) to (x2, y2), the required time is |x1 - x2| + |y1 - y2| (where |t| denotes the absolute value of t).

In order to improve stability in the kingdom, the police wants to introduce a specific patrol route. The route will contain exactly three places A, B, and C. A policeman will visit these three places and verify that everything is as it should be. The three places that determine a valid route must satisfy the following criteria::

x-coordinates of A, B and C are pairwise distinct.
y-coordinates of A, B and C are pairwise distinct.
Let T be the total time required to follow along the route: first from A to B, then from B to C and finally from C back to A. T must be between minT and maxT, inclusive.

You are given the ints X, Y, minT, and maxT. Return the number of different patrol routes that satisfy these criteria, modulo 1,000,000,007. Two routes are considered to be different if there is a place that belongs to one of them, but does not belong to the other one.

Definition

Class:	PatrolRoute
Method:	countRoutes
Parameters:	int, int, int, int
Returns:	int
Method signature:	int countRoutes(int X, int Y, int minT, int maxT)
(be sure your method is public)

Constraints

X and Y will each be between 3 and 4,000, inclusive.

minT will be between 1 and 20,000, inclusive.

maxT will be between minT and 20,000, inclusive.

950：

Problem Statement

A standard way of ordering words in a dictionary involves comparison of two words character by character, from left to right, until some two characters disagree. Jim thinks it's pretty boring, so he introduced a more complicated and less predictable scheme.

Given is a String[] words that contains N distinct words and each element is a single word. The length of each word is the same -- exactly L characters. To order words according to his scheme, Jim first generates a random permutation p[0], p[1], ..., p[L-1] of integers between 0 and L-1, inclusive. This permutation is generated only once and then considered to be fixed for the rest of the procedure. Using the permutation p, Jim can compare any two words as follows:

// returns -1, if AB function Compare(Word A, Word B):  for i = 0, 1, ..., L-1:   a := character at position p[i] (0-based) in A   b := character at position p[i] (0-based) in B   if (a < b), return -1   if (b < a), return 1   return 0

Let Sorted be the list of the given words ordered according to Compare operator defined above. In other words, Compare(Sorted[i], Sorted[j]) = -1, for any i, j, 0 <= i < j < N. Let pos[i] be the 0-based position of words[i] within Sorted.

Obviously, the value pos[i] depends on the choice of the random permutation p. Assume that p is chosen uniformly at random. Return a double[] that contains N elements. Element i of the return value must be the expected value of pos[i].

Definition

Class:	StrangeDictionary
Method:	getExpectedPositions
Parameters:	String[]
Returns:	double[]
Method signature:	double[] getExpectedPositions(String[] words)
(be sure your method is public)

Notes

Each element of the return value must have an absolute or relative error of less than 1e-9.

Constraints

words will contain between 1 and 50 elements, inclusive.

Each element of words will contain between 1 and 50 characters, inclusive.

All elements of words will contain the same number of characters.

Each character in each element of words will be a lowercase letter ('a'-'z').

All elements of words will be distinct.

g++ diff

long1 — Tue, 8 May 2012 16:24:37 +0800

g++ -o a a.cpp
time ./a < a.in >team.out
time ./a team.out
diff team.out a.out

37th ACM/ICPC 浙江师范大学邀请赛最终排名 PC^2 版本

long1 — Sun, 6 May 2012 23:51:45 +0800

Rank	Name	Solved	Time	A	B	C	D	E	F	G	H	I	J	Total att/solv
				Light_Green	Orange	Red	Light_Purple	Pink	White	Deep_Purple	Blue	Yellow	Deep_Green
1	Seraphim	8	967	2/19	1/46	1/216	2/94	2/56	1/101	3/183	0/--	1/152	0/--	13/8
2	Epic	8	1190	2/38	1/30	1/197	2/77	1/83	1/192	4/219	0/--	2/234	0/--	14/8
3	FreeJourney	6	631	1/40	2/28	1/195	2/129	1/57	2/122	1/--	0/--	9/--	0/--	19/6
4	kerokero	6	866	3/59	1/41	1/--	1/73	1/113	7/262	7/--	0/--	2/138	0/--	23/6
5	FutureGazer	6	895	2/31	1/54	13/--	1/130	2/64	2/233	0/--	0/--	5/243	0/--	26/6
6	Cutit	6	1047	1/24	2/100	25/--	1/48	6/253	3/277	0/--	0/--	1/185	0/--	39/6
7	EndlessMaze	6	1151	1/81	1/50	3/287	1/221	3/237	1/195	0/--	0/--	0/--	0/--	10/6
8	Simpler	5	610	2/75	1/43	1/97	1/160	2/195	0/--	0/--	0/--	1/--	0/--	8/5
9	YXC	5	709	2/42	1/68	1/126	2/98	4/275	1/--	1/--	0/--	0/--	0/--	12/5
10	Freshman	5	794	1/75	3/114	1/167	3/191	3/127	1/--	0/--	0/--	5/--	0/--	17/5
11	HUST_Godot	5	933	1/42	2/190	0/--	1/194	4/120	3/267	0/--	0/--	4/--	0/--	15/5
12	TimeBomb	5	1152	8/162	3/89	2/138	1/202	5/281	0/--	0/--	0/--	6/--	0/--	25/5
13	Mercury	4	359	1/29	1/61	0/--	2/97	2/132	0/--	4/--	0/--	0/--	0/--	10/4
14	HDU-Baiye	4	370	2/62	2/80	9/--	1/45	2/123	0/--	0/--	0/--	2/--	0/--	18/4
15	HDU-FinalChance	4	380	1/32	1/68	4/--	2/102	1/158	0/--	0/--	0/--	1/--	0/--	10/4
16	ZSTU_02	4	393	1/33	1/64	3/--	1/152	2/124	3/--	0/--	0/--	0/--	0/--	11/4
17	C3S	4	436	1/35	2/62	0/--	4/171	1/88	0/--	0/--	0/--	4/--	0/--	12/4
18	N.N.Update	4	502	1/30	1/97	3/--	1/176	1/199	2/--	0/--	0/--	0/--	0/--	9/4
19	UESTC_Excalibur	4	612	2/30	1/62	3/--	1/87	10/233	0/--	0/--	0/--	0/--	0/--	17/4
20	Tour_de_Force	4	635	2/101	1/96	3/--	3/200	1/178	0/--	0/--	0/--	0/--	0/--	10/4
21	GanSiDui	4	668	1/31	3/102	2/--	1/254	16/--	1/241	0/--	0/--	0/--	0/--	24/4
22	xiaoshua	4	690	1/23	1/116	0/--	2/216	4/255	0/--	0/--	0/--	0/--	0/--	8/4
23	Vector	4	698	1/39	2/154	0/--	5/229	1/176	14/--	0/--	0/--	0/--	0/--	23/4
24	Aiwell	4	719	2/53	3/149	0/--	5/245	2/112	6/--	0/--	0/--	3/--	0/--	21/4
25	primeShark	4	723	2/81	1/94	6/--	2/184	5/244	0/--	0/--	0/--	0/--	0/--	16/4
26	AxorB	4	733	4/137	3/104	4/--	2/212	1/160	1/--	0/--	0/--	0/--	0/--	15/4
27	Nyquist	4	761	1/44	3/124	0/--	3/277	2/216	0/--	0/--	0/--	0/--	0/--	9/4
28	galaxy	4	789	1/103	2/88	0/--	2/244	3/274	0/--	0/--	0/--	0/--	0/--	8/4
29	Water	4	933	1/34	10/241	0/--	2/284	2/154	1/--	0/--	0/--	0/--	0/--	16/4
30	TeammateKiller	4	938	3/91	1/102	0/--	6/259	4/286	1/--	0/--	0/--	0/--	0/--	15/4
31	NJU_Diablo	4	1037	4/226	4/142	0/--	2/297	1/232	0/--	0/--	0/--	0/--	0/--	11/4
32	ZJUT-3	4	1047	4/113	5/297	0/--	3/184	2/253	0/--	0/--	0/--	0/--	0/--	14/4
33	CSU_BMW	3	236	1/32	1/114	4/--	1/90	5/--	1/--	0/--	0/--	0/--	0/--	13/3
34	Accelerator	3	236	1/30	1/75	0/--	2/--	1/131	0/--	0/--	0/--	1/--	5/--	11/3
35	HIT_Avalon	3	279	2/71	2/51	0/--	1/117	10/--	0/--	0/--	0/--	5/--	0/--	20/3
36	Memory	3	312	1/51	2/82	0/--	1/159	4/--	1/--	0/--	0/--	0/--	0/--	9/3
37	ZJUT-1	3	347	2/79	2/90	2/--	1/138	11/--	0/--	0/--	0/--	0/--	0/--	18/3
38	ZSTU_01	3	398	2/42	2/119	0/--	2/177	13/--	0/--	0/--	0/--	0/--	0/--	19/3
39	NKU_HOT ~Encore~	3	402	1/29	1/147	3/--	0/--	2/--	3/186	0/--	0/--	0/--	0/--	10/3
40	WDM	3	407	1/52	2/105	0/--	14/--	4/170	0/--	0/--	0/--	0/--	0/--	21/3
41	ZSTU_03	3	416	1/45	1/71	0/--	2/--	4/240	0/--	0/--	0/--	0/--	0/--	8/3
42	HDU-Overflow	3	455	1/46	2/120	0/--	1/269	3/--	0/--	0/--	0/--	0/--	0/--	7/3
43	HDU-Alaligehua	3	462	1/32	3/186	1/--	3/164	11/--	0/--	0/--	0/--	0/--	0/--	19/3
44	ham	3	480	1/63	2/158	0/--	0/--	2/219	0/--	0/--	0/--	0/--	0/--	5/3
45	Yababom	3	480	2/69	2/103	6/--	3/228	10/--	0/--	0/--	0/--	0/--	0/--	23/3
46	NJU_Atom	3	482	1/51	2/197	0/--	0/--	2/194	0/--	0/--	0/--	0/--	0/--	5/3
47	Ceaseless	3	483	1/51	2/199	0/--	4/--	1/213	0/--	0/--	0/--	0/--	0/--	8/3
48	Bomb	3	484	1/27	2/146	7/--	0/--	2/271	0/--	0/--	0/--	0/--	0/--	12/3
49	NKU_COLD	3	486	1/34	1/149	2/--	2/--	4/243	0/--	0/--	0/--	0/--	0/--	10/3
50	NKU_Code Monkey	3	487	1/25	1/83	2/--	1/--	5/299	0/--	0/--	0/--	0/--	0/--	10/3
51	fly_CFE	3	509	2/74	1/216	0/--	3/159	3/--	0/--	0/--	0/--	0/--	0/--	9/3
52	Star_Light	3	515	1/117	3/139	0/--	6/--	2/199	0/--	0/--	0/--	0/--	0/--	12/3
53	ZJUT-2	3	517	2/82	1/215	0/--	2/180	4/--	0/--	0/--	0/--	0/--	0/--	9/3
54	Maze	3	531	2/61	3/183	11/--	0/--	1/227	6/--	0/--	0/--	0/--	0/--	23/3
55	ZSTU_04	3	550	1/59	1/192	0/--	1/--	2/279	0/--	0/--	0/--	0/--	0/--	5/3
56	shrimp	3	554	1/47	2/183	0/--	0/--	2/284	0/--	0/--	0/--	0/--	0/--	5/3
57	ZAFU_2	3	584	1/32	2/114	0/--	0/--	9/258	0/--	0/--	0/--	0/--	0/--	12/3
58	Burning Ice	3	592	1/62	5/246	0/--	4/--	3/164	0/--	0/--	0/--	0/--	0/--	13/3
59	Tangent	3	600	1/45	3/247	5/--	0/--	2/248	0/--	0/--	0/--	0/--	0/--	11/3
60	HDU-ACHunter	3	608	1/42	3/--	7/--	2/215	6/231	0/--	0/--	0/--	0/--	0/--	19/3
61	ZCMU-BS-Forever	3	633	3/135	3/184	0/--	0/--	1/234	1/--	0/--	0/--	0/--	0/--	8/3
62	Jxust_leap	3	666	3/90	2/142	0/--	6/274	1/--	0/--	0/--	0/--	0/--	0/--	12/3
63	XYZSOY	3	670	1/40	4/233	0/--	3/297	2/--	0/--	0/--	0/--	0/--	0/--	10/3
64	JLU3	3	681	1/108	2/56	0/--	0/--	11/297	0/--	0/--	0/--	0/--	0/--	14/3
65	HFUT_Evolution	3	691	1/83	2/171	8/277	0/--	12/--	0/--	0/--	0/--	0/--	0/--	23/3
66	GDUT_Twilight	3	734	1/58	5/247	0/--	4/289	8/--	0/--	0/--	0/--	0/--	0/--	18/3
67	UESTC_silence	3	738	1/63	9/299	0/--	1/216	0/--	0/--	0/--	0/--	0/--	0/--	11/3
68	Rookies Back	2	176	2/45	1/111	0/--	0/--	7/--	0/--	0/--	0/--	0/--	0/--	10/2
69	Ecust_ChallengeSyste	2	177	1/30	2/127	0/--	0/--	13/--	0/--	0/--	0/--	0/--	0/--	16/2
70	SmokeWine	2	284	1/75	0/--	0/--	0/--	1/209	0/--	0/--	0/--	0/--	0/--	2/2
71	Simple	2	288	1/37	2/--	4/--	0/--	1/251	0/--	0/--	0/--	0/--	0/--	8/2
72	Ldream	2	293	1/42	7/--	0/--	0/--	3/211	0/--	0/--	0/--	0/--	0/--	11/2
73	Front	2	295	1/91	2/184	5/--	0/--	10/--	0/--	0/--	0/--	0/--	0/--	18/2
74	DIGIMON	2	312	1/122	2/--	0/--	0/--	1/190	0/--	0/--	0/--	0/--	0/--	4/2
75	#____#	2	323	1/49	0/--	0/--	0/--	2/254	0/--	0/--	0/--	0/--	0/--	3/2
76	Paralines Zero	2	323	1/28	3/255	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	4/2
77	Mars	2	331	3/84	2/187	0/--	2/--	0/--	1/--	0/--	0/--	0/--	0/--	8/2
78	NKU_22DormB306	2	378	3/79	4/199	0/--	1/--	2/--	0/--	0/--	0/--	0/--	0/--	10/2
79	NKU_CHH	2	387	2/91	2/256	0/--	3/--	5/--	0/--	0/--	0/--	0/--	0/--	12/2
80	SuperBug	2	388	1/102	2/266	1/--	2/--	12/--	0/--	0/--	0/--	0/--	0/--	18/2
81	xiaocaicai	2	393	1/34	0/--	0/--	7/239	0/--	0/--	0/--	0/--	0/--	1/--	9/2
82	Badminton	2	403	2/110	0/--	0/--	0/--	1/273	0/--	0/--	0/--	0/--	0/--	3/2
83	iBeyond	2	406	3/127	1/239	0/--	3/--	0/--	1/--	0/--	0/--	0/--	0/--	8/2
84	come on baby	2	461	6/180	2/161	0/--	0/--	1/--	0/--	0/--	0/--	0/--	0/--	9/2
85	MaXon	2	499	3/249	0/--	0/--	3/--	1/210	0/--	0/--	0/--	0/--	0/--	7/2
86	Lost	2	644	8/267	2/217	0/--	0/--	2/--	0/--	0/--	0/--	0/--	0/--	12/2
87	Killers	1	51	1/51	0/--	0/--	0/--	3/--	0/--	0/--	0/--	0/--	0/--	4/1
88	Scarlet_RE	1	62	1/62	1/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	2/1
89	ZCMU-breeze（1）	1	65	1/65	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	1/1
90	Unicorn	1	76	1/76	0/--	0/--	3/--	0/--	0/--	0/--	0/--	0/--	0/--	4/1
91	hutc_C_man	1	87	1/87	1/--	0/--	0/--	0/--	0/--	0/--	1/--	0/--	0/--	3/1
92	ACDarkStar	1	90	2/70	3/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	5/1
93	JxufeAAA	1	90	1/90	0/--	0/--	3/--	0/--	0/--	0/--	0/--	0/--	0/--	4/1
94	HDU-Diligence	1	100	2/80	0/--	0/--	0/--	7/--	0/--	0/--	0/--	0/--	0/--	9/1
95	Sun_Light	1	109	2/89	4/--	0/--	1/--	7/--	0/--	0/--	0/--	0/--	0/--	14/1
96	BITelite	1	111	1/111	0/--	0/--	2/--	0/--	0/--	0/--	0/--	8/--	0/--	11/1
97	1+1+1>3	1	115	1/115	0/--	2/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	3/1
98	Bnuz_EyesOnMe_	1	124	2/104	0/--	0/--	0/--	3/--	0/--	0/--	0/--	0/--	0/--	5/1
99	Surprising	1	142	1/142	0/--	0/--	3/--	0/--	0/--	0/--	0/--	0/--	0/--	4/1
100	vampire	1	146	2/126	0/--	0/--	2/--	6/--	0/--	0/--	0/--	0/--	0/--	10/1
101	Flyhw	1	163	3/123	7/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	10/1
102	HWJ	1	168	3/128	0/--	5/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	8/1
103	Extreme	1	199	4/139	0/--	0/--	2/--	0/--	0/--	0/--	0/--	0/--	0/--	6/1
104	BJZCMU-A + B	1	207	6/107	2/--	0/--	1/--	0/--	0/--	0/--	0/--	0/--	0/--	9/1
105	ZSTU_05	1	213	1/213	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	1/1
106	Moon_Light	1	218	2/198	3/--	2/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	7/1
107	HUST_Ignotus	1	228	4/168	2/--	0/--	2/--	0/--	0/--	0/--	0/--	0/--	0/--	8/1
108	JxufeRandom	1	238	3/198	0/--	0/--	3/--	0/--	0/--	0/--	0/--	0/--	0/--	6/1
109	Here Idears Come	1	245	2/225	0/--	0/--	3/--	0/--	0/--	0/--	0/--	0/--	0/--	5/1
110	JLU1	1	247	2/227	0/--	5/--	8/--	0/--	0/--	0/--	0/--	0/--	0/--	15/1
111	Earth	1	253	1/253	2/--	0/--	3/--	0/--	0/--	0/--	0/--	0/--	0/--	6/1
112	JLU2	1	276	2/256	0/--	2/--	1/--	0/--	0/--	0/--	0/--	0/--	0/--	5/1
113	Try	1	282	6/--	4/--	0/--	1/--	1/282	0/--	0/--	0/--	0/--	0/--	12/1
114	zjicm:echo1	1	308	4/248	2/--	1/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	7/1
115	Romance	1	331	6/231	1/--	9/--	0/--	7/--	0/--	0/--	0/--	0/--	0/--	23/1
116	SuperSoy	1	339	4/279	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	4/1
117	hutc_AC^3	1	495	12/275	1/--	1/--	1/--	13/--	13/--	0/--	0/--	0/--	0/--	41/1
118	CoreCoder	0	0	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/0
118	Dream	0	0	4/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	4/0
118	JZS'fight	0	0	5/--	0/--	0/--	1/--	0/--	0/--	0/--	0/--	0/--	0/--	6/0
118	LittleGirl	0	0	0/--	6/--	0/--	1/--	0/--	0/--	0/--	0/--	0/--	0/--	7/0
118	ZAFU_1	0	0	5/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	0/--	5/0
Rank	Name	Solved	Time	A	B	C	D	E	F	G	H	I	J	Total att/solv
				Light_Green	Orange	Red	Light_Purple	Pink	White	Deep_Purple	Blue	Yellow	Deep_Green
	Submitted/1st Yes/Total Yes			248/19/116	222/28/77	182/97/9	200/45/48	369/56/58	78/101/10	20/183/2	1/--/0	60/138/5	6/--/0	1386/325

Created by CSUS PC^2 9.2.1 20120304 build 2482
http://www.ecs.csus.edu/pc2/
Last updated Sun May 06 14:11:22 CST 2012

shell编程练习题1

long1 — Thu, 3 May 2012 18:19:07 +0800

一．用Shell编程，判断一文件是不是字符设备文件，如果是将其拷贝到 /dev 目录下。

参考程序：

#!/bin/sh

FILENAME=

echo “Input file name：”

read FILENAME

if [ -c "$FILENAME" ]

then

cp $FILENAME /dev

five file type in linux: regular file, link file , directory file, device file(charater or block), pipe file

unix这类系统里面分为character device and block device,像鼠标显示器键盘这类的一个个字节读取的称为字符设备，硬盘这类最小以扇区为单位，必须一次读512字节的称为块设备

普通文件都是字符流的，可以一个字节读取，硬盘设备一次至少读512字符，所以需要缓冲

使用ls -l查看，可以看到 crw------- 这样的描述，第一c表示字符设备文件；b表示块设备文件；d表示文件夹，也就是目录；一般文件第一个是"-"。后面三个“只读“，”写“，“执行”分别是属主权限u，组权限g，其它权限o

类似操作，桌面上有a文件和dira文件夹

写个a.sh把a文件移动到dira文件夹里

a.sh:

#! /bin/bash

FILENAME= #这个貌似可有可没有

echo "input file name:"

read FILENAME

if [ -e "$FILENAME" ]

then

mv $FILENAME dira

chmod +x a.sh 让a.sh能执行

long1lfw@ubuntu:~/桌面$ ./a.sh

input file name:

运行下就能把a移动到dira里了

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

二. 写一个使用"case"的脚本，如果输入"start"能执行脚本a.sh,输入"cat"能查看a.sh

vim case.sh

#! /bin/bash

case "$1" in

'start')

cd ~/桌面; ./a.sh ;;

'view')

cd ~/桌面; cat a.sh;;

echo "no such command usage $0 start|view";;

esac

注意，一行里多个命令用";" 分隔，一行只有一个命令，可以不用“;”，$1表示第一个参数，$0表示怎么执行的

运行：

long1lfw@ubuntu:~/桌面$ ./case.sh start

input file name:

long1lfw@ubuntu:~/桌面$ ./case.sh view

#! /bin/bash

echo "input file name:"

read FILENAME

if [ -e "$FILENAME" ]

then

mv $FILENAME dira

long1lfw@ubuntu:~/桌面$ ./case.sh kao

no such command usage ./case.sh start|view

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

三．设计一个shell程序，添加一个新组为class1，然后添加属于这个组的30个用户，用户名的形式为stdxx，其中xx从01到30。

vim addclass1.sh

#!/bin/sh

i=1

groupadd class1

while [ $i -le 30 ]

if [ $i -le 9 ] ;then

USERNAME=stu0${i}

else

USERNAME=stu${i}

useradd $USERNAME

(echo $USERNAME; sleep 1; echo $USERNAME) | passwd $USERNAME

#另外一种方法貌似不行

#echo $USERNAME | passwd $USERNAME --stdin > /dev/null 2>&1

mkdir /home/$USERNAME

chown -R $USERNAME /home/$USERNAME

chgrp -R class1 /home/$USERNAME

i=$(($i+1))

done

long1lfw@ubuntu:~/桌面$ chmod +x addclass1.sh

long1lfw@ubuntu:~/桌面$ ./addclass1.sh

注意不能直接运行，权限不够，需要 sudo ./addclass1.sh

关于创建，修改，删除，查看用户和用户组：

1，创建组

groupadd test

增加一个test组

2，修改组

groupmod -n test2 test

将test组的名子改成test2

3，删除组

groupdel test2

删除组test2

4.查看组(a)查看当前登录用户所在的组 groups，查看lfw所在组 groups lfw (b)查看所有组 cat /etc/group

1.增加用户 useradd test

passwd test

增加用户test，有一点要注意的，useradd增加一个用户后，不要忘了给他设置密码，不然不能登录的。

2，修改用户

usermod -d /home/test -G test2 test

将test用户的登录目录改成/home/test，并加入test2组，注意这里是大G。

3，删除用户

userdel test

将test用户删除

4.查看用户 w 或 who 或 whoami 等

写一个相应删除组和用户的shell:

long1lfw@ubuntu:~/桌面$ vim delclass1.sh

#! /bin/bash

i=1

groupdel class1

while [ $i -le 30 ]

if [ $i -le 9 ]

then

USERNAME=stu0${i}

else

USERNAME=stu${i}

userdel $USERNAME

rm -rf /home/$USERNAME

i=$(($i+1))

done

同样，也需要chmod +x 以及 sudo运行

先执行sudo ./addclass1.sh

long1lfw@ubuntu:~/桌面$ sudo ./addclass1.sh

输入新的 UNIX 密码：重新输入新的 UNIX 密码： passwd：已成功更新密码

注销一下，尝试登录~

可以登录，OK！

然后再回到本来的用户,long1lfw,查看group组

long1lfw@ubuntu:~/桌面$ sudo cat -n /etc/group

1 root:x:0:

2 daemon:x:1:

3 bin:x:2:

4 sys:x:3:

5 adm:x:4:long1lfw

6 tty:x:5:

7 disk:x:6:

8 lp:x:7:

9 mail:x:8:

10 news:x:9:

11 uucp:x:10:

12 man:x:12:

13 proxy:x:13:

14 kmem:x:15:

15 dialout:x:20:long1lfw

16 fax:x:21:

17 voice:x:22:

18 cdrom:x:24:long1lfw

19 floppy:x:25:

20 tape:x:26:

21 sudo:x:27:

22 audio:x:29:pulse

23 dip:x:30:

24 www-data:x:33:

25 backup:x:34:

26 operator:x:37:

27 list:x:38:

28 irc:x:39:

29 src:x:40:

30 gnats:x:41:

31 shadow:x:42:

32 utmp:x:43:

33 video:x:44:

34 sasl:x:45:

35 plugdev:x:46:long1lfw

36 staff:x:50:

37 games:x:60:

38 users:x:100:

39 nogroup:x:65534:

40 libuuid:x:101:

41 crontab:x:102:

42 syslog:x:103:

43 fuse:x:104:

44 messagebus:x:105:

45 mlocate:x:106:

46 ssh:x:107:

47 avahi-autoipd:x:108:

48 avahi:x:109:

49 netdev:x:110:

50 lpadmin:x:111:long1lfw

51 ssl-cert:x:112:

52 couchdb:x:113:

53 pulse:x:114:

54 pulse-access:x:115:

55 utempter:x:116:

56 rtkit:x:117:

57 saned:x:118:

58 admin:x:119:long1lfw

59 gdm:x:120:

60 nopasswdlogin:x:121:

61 long1lfw:x:1000:

62 sambashare:x:122:long1lfw

63 jetty:x:123:

64 haldaemon:x:124:

65 class1:x:1001:

66 stu01:x:1002:

67 stu02:x:1003:

68 stu03:x:1004:

69 stu04:x:1005:

70 stu05:x:1006:

71 stu06:x:1007:

72 stu07:x:1008:

73 stu08:x:1009:

74 stu09:x:1010:

75 stu10:x:1011:

76 stu11:x:1012:

77 stu12:x:1013:

78 stu13:x:1014:

79 stu14:x:1015:

80 stu15:x:1016:

81 stu16:x:1017:

82 stu17:x:1018:

83 stu18:x:1019:

84 stu19:x:1020:

85 stu20:x:1021:

86 stu21:x:1022:

87 stu22:x:1023:

88 stu23:x:1024:

89 stu24:x:1025:

90 stu25:x:1026:

91 stu26:x:1027:

92 stu27:x:1028:

93 stu28:x:1029:

94 stu29:x:1030:

95 stu30:x:1031:

从65到95就是新添的，再运行sudo ./delclass1.sh

long1lfw@ubuntu:~/桌面$ sudo ./delclass1.sh

long1lfw@ubuntu:~/桌面$ sudo cat -n /etc/group

1 root:x:0:

2 daemon:x:1:

3 bin:x:2:

4 sys:x:3:

5 adm:x:4:long1lfw

6 tty:x:5:

7 disk:x:6:

8 lp:x:7:

9 mail:x:8:

10 news:x:9:

11 uucp:x:10:

12 man:x:12:

13 proxy:x:13:

14 kmem:x:15:

15 dialout:x:20:long1lfw

16 fax:x:21:

17 voice:x:22:

18 cdrom:x:24:long1lfw

19 floppy:x:25:

20 tape:x:26:

21 sudo:x:27:

22 audio:x:29:pulse

23 dip:x:30:

24 www-data:x:33:

25 backup:x:34:

26 operator:x:37:

27 list:x:38:

28 irc:x:39:

29 src:x:40:

30 gnats:x:41:

31 shadow:x:42:

32 utmp:x:43:

33 video:x:44:

34 sasl:x:45:

35 plugdev:x:46:long1lfw

36 staff:x:50:

37 games:x:60:

38 users:x:100:

39 nogroup:x:65534:

40 libuuid:x:101:

41 crontab:x:102:

42 syslog:x:103:

43 fuse:x:104:

44 messagebus:x:105:

45 mlocate:x:106:

46 ssh:x:107:

47 avahi-autoipd:x:108:

48 avahi:x:109:

49 netdev:x:110:

50 lpadmin:x:111:long1lfw

51 ssl-cert:x:112:

52 couchdb:x:113:

53 pulse:x:114:

54 pulse-access:x:115:

55 utempter:x:116:

56 rtkit:x:117:

57 saned:x:118:

58 admin:x:119:long1lfw

59 gdm:x:120:

60 nopasswdlogin:x:121:

61 long1lfw:x:1000:

62 sambashare:x:122:long1lfw

63 jetty:x:123:

64 haldaemon:x:124:

就但删除了，目录也用rm -rf强制删除了(r表示目录， f表示强制)

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

shell 函数

long1 — Tue, 1 May 2012 13:27:51 +0800

函数

type命令告诉正在执行的命令的来源是别名，函数，或外部命令，如：

long1lfw@ubuntu:~$ type ls

ls 已被别名为“ls --color=auto”

long1lfw@ubuntu:~$ type echo

echo 是一个 shell 内部命令

long1lfw@ubuntu:~$ type cat

cat 是 /bin/cat

ls来自alias,echo是shell内部命令,cat则是外部命令

函数需要先定义，后使用，用exit退出脚本，用return返回到调用的地方

return语句返回函数执行最后一条命令的退出状态

declare -f或-F可以看字典序的函数定义

定义函数可以用function funcname() { shell comands}

或 funcname() { shell commands}

删除可以用unset -f funcname，-f表示unset删除的是函数

写一个user_login.sh:

#! /bin/bash

function user_login()

{

if who | grep $1 >/dev/null

then echo "User $1 is on."

else echo "User $1 is off."

}

long1lfw@ubuntu:~/桌面$ source user_login.sh

long1lfw@ubuntu:~/桌面$ user_login long1lfw

User long1lfw is on.

long1lfw@ubuntu:~/桌面$ user_login longpo

User longpo is off.

通过source命令将函数从文件读入，函数就如同命令一样变得可调用。然后传入参数$1表示第一个参数，判断用户是否在线。

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

看函数怎么返回值的例子：

add.sh:

#! /bin/bash

add()

{

let "sum=$1+$2"

return $sum

}

long1lfw@ubuntu:~/桌面$ source add.sh

long1lfw@ubuntu:~/桌面$ add 3 4

long1lfw@ubuntu:~/桌面$ echo $?

$? 中保存的是上一条命令的返回值，正是如此，执行完add 3 4后，可以使用echo $?来获取执行的返回结果

if/else语句，结果：

if condition

then

statements

[elif condition

then

statements...]

[else

statement ]

退出用0表示成功，非0表示失败，$? 结果如果是0，表示正常退出，否则异常，如：

long1lfw@ubuntu:~/桌面$ cat /etc/shadow

cat: /etc/shadow: 权限不够

long1lfw@ubuntu:~/桌面$ echo $?

if语句唯一可以测试的内容是退出状态，不能用于检测表达式的值。但通过test命令可以连用

if test 2 -gt 3

then

...

等同于

if [ 2 -gt 3 ] #[,]前必须有空格

then

...

看个例子：

add.sh:

#! /bin/bash

add()

{

if [ $1 -gt $2 ]

then

let "sum=$1+$2"

else

let "sum=0"

return $sum

}

long1lfw@ubuntu:~/桌面$ vim add.sh

long1lfw@ubuntu:~/桌面$ source add.sh

long1lfw@ubuntu:~/桌面$ add 4 5

long1lfw@ubuntu:~/桌面$ echo $?

long1lfw@ubuntu:~/桌面$ add 5 4

long1lfw@ubuntu:~/桌面$ echo $?

当第一个参数大于第二个参数执行相加，数字型的比较有： -eg等于 -ne不等与 -lt小于 -le小于等于 -gt大于 -ge大于等于

字符型的比较有：-z长度为0 -n长度非0 =相等！=不等

文件测试有：-b存在并且是块文件 -c存在且是字符文件 -d路径存在且是一个目录 -e指定的文件或目录存在 -f存在且是正规文件 -g文件或目录存在且设置了SGID位 -h存在且是符号链接文件 -s文件存在且文件大小大于0 -w可写 -r可读 -x可执行

符合表达式： !假为真 -a同时为真 -o有一个为真

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

shell的变量

long1 — Fri, 27 Apr 2012 19:27:57 +0800

shell是一种动态类型语言(不使用显式数据声明)和弱类型语言(变量类型操作根据需求而不同)。shell变成中的变量是不分类型的(都是字符串类型)，但是依赖于具体的上下文，shell编程也允许比较操作和整数操作。

看下面例子：

variable.sh:

#!/bin/bash

a=2334 #整型

let "a+=1"

echo "a=$a" #a=2335

echo #还是整型

b=${a/23/BB} #将"23"替换成"BB",这将把b从整型变为字符串

echo "b=$b" #b=BB35

declare -i b #即使使用declare命令也不会对此有任何帮助

echo "b=$b" #b=BB35

let "b += 1" #BB35 + 1 =

echo "b=$b" #b = 1

echo

c=BB34

echo "c=$c" #c=BB34

d=${c/BB/23} #降"BB"替换成"23",这使得变量$d变为一个整型

echo "d=$d" #d = 2334

let "d += 1" #2334 + 1=

echo "d=$d" #d=2335

echo

#null 变量会如何

e=""

echo "e=$e" #e =

let "e += 1" #算术操作允许一个null变量？

echo "e=$e" #e=1

echo #null变量将被转换成一个整型变量

#如果没有声明变量会怎么样

echo "f=$f" #f=

let "f += 1" #算术操作能通过吗？

echo "f=$f" #f=1

echo #未声明的变量将转换成一个整型变量

#所以bash shell中的变量都是不去分类型的

exit 0

运行：

long1lfw@ubuntu:~/桌面$ vim variable.sh

long1lfw@ubuntu:~/桌面$ chmod +x variable.sh

long1lfw@ubuntu:~/桌面$ ./variable.sh

a=2335

b=BB35

b=1

c=BB34

d=2334

d=2335

e=1

f=1

结果跟注释的一样

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

shell里有三种变量：用户变量，位置变量和环境变量。

1.用户变量

有分全局和局部，默认是全局，局部的话需要使用local限定词。

定义为 varname=value，等号两边不能有空格。变量值多于一个单词，必须用引号引起来。要在命令中引用，在其名字前加符合$

例如：

str=how are you? #错误，没加引号

str = "how are you?"#错误，等号左右不能有空格

str="how are you?" #正确

echo str #错误，要引用str的值，需要用$

echo $str #正确

unset varname 可以删除变量，但一般不这样使用

默认变量返回空字符串

要打出特殊字符需要转义，使用\$, \~等，如：

long1lfw@ubuntu:~/桌面$ echo $you

long1lfw@ubuntu:~/桌面$ echo \$you

$you

弱引用""和强引用'', 强引用让引用内的变量失效，弱的让部分失效，例子：

long1lfw@ubuntu:~/桌面$ vname=lfw

long1lfw@ubuntu:~/桌面$ echo "I am $vname"

I am lfw

long1lfw@ubuntu:~/桌面$ echo 'I am $vname'

I am $vname

正式的表示方式为${vname}, 上面例子，如果要输出lfw_,不能用echo $vname_,只能用${vname}_,因为变量的命名方式和c,java类似，把vname_当成变量了

操作字符串有替换运算符，模式匹配运算符

模式匹配运算符的一个应用，如${varname//pattern/string}替换任意的pattern为string(如果一个/就替换第一个)，应用于查看环境变量 echo -e ${PATH//:/'\n'}

/usr/local/sbin

/usr/local/bin

/usr/sbin

/usr/bin

/sbin

/bin

/usr/games

-e允许将echo的\n解释为一个LINEFEED

效果同等与sed命令： long1lfw@ubuntu:~/桌面$ echo $PATH | sed 's/:/\n/g'

使用`command` (`为1左边的键)命令替换，允许使用命令的标准输出

long1lfw@ubuntu:~/桌面$ echo `pwd`

/home/long1lfw/桌面

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

2.位置变量

$# 输出变量的个数

$? 输出上条命令的结束值

$0 输出命令的名字

$* 输出命令的所有参数

$1 $2 $9 ${10} 输出1 2 9 10的参数

例子：

long1lfw@ubuntu:~/桌面$ vim process.sh

long1lfw@ubuntu:~/桌面$ chmod +x process.sh

long1lfw@ubuntu:~/桌面$ ./process.sh a b

the script name is ./process.sh

$1=a; $2=b

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

3.环境变量

常见的环境变量有：PATH HOME HISTFILE IFS LOGNAME TERM等

可以用echo查看，如：

long1lfw@ubuntu:~/桌面$ echo $LOGNAME

long1lfw

当需要保存修改的环境变量时，我们使用export命令将变量修改写进启动文件里。对于不同的启动shell，启动文件不同

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

shell编程基础

long1 — Thu, 26 Apr 2012 13:36:44 +0800

1.shell脚本的参数

long1lfw@ubuntu:~$ testfunc()

> {

> echo "$# parameters";

> echo "$@";

> }

其实$#表示传入参数个数，$@表示所有参数的内容,测试：

long1lfw@ubuntu:~$ testfunc

0 parameters

long1lfw@ubuntu:~$ testfunc a b c

3 parameters

a b c

long1lfw@ubuntu:~$ testfunc a " b c "

2 parameters

a b c

用vim建立一个文本写shell

#! /bin/bash

echo "$# parameters"

echo "$@";

注意，首行表示使用哪种shell运行，之后的 "#" 表示注释，类似C++的 "//"

写完后增加个权限，原来的权限是：

long1lfw@ubuntu:~/桌面$ ls -l testfunc.sh

-rw-r--r-- 1 long1lfw long1lfw 45 2012-04-26 12:30 testfunc.sh

通过chmod +x testfunc.sh增加权限

long1lfw@ubuntu:~/桌面$ chmod +x testfunc.sh

long1lfw@ubuntu:~/桌面$ ls -l testfunc.sh

-rwxr-xr-x 1 long1lfw long1lfw 45 2012-04-26 12:30 testfunc.sh

最后运行，类似g++编译后的运行：

long1lfw@ubuntu:~/桌面$ ./testfunc.sh a "b c"

2 parameters

a b c

用户的#HOME目录为：

long1lfw@ubuntu:~/桌面$ echo $HOME

/home/long1lfw

就像命令前的~/桌面一样，可以用~来表示$HOME

mkdir可以创建一个或多个目录，如：

long1lfw@ubuntu:~/桌面$ mkdir ma mb

创建了ma 和 mb两个文件夹，删除目录也可以用rm 只是要多加 -r:

long1lfw@ubuntu:~/桌面$ rm -r ma mb

或者使用rmdir，但文件夹必须为空

mv可以移动或重命名文件或目录，如把b.txt 改为 b.cpp:

long1lfw@ubuntu:~/桌面$ mv b.txt b.cpp

把a.cpp移动到bm文件夹：

long1lfw@ubuntu:~/桌面$ sudo mv a.cpp bm

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

2.I/O重定向

echo的行为(1)读取echo参数中的变量，将所有变量替换成值，变成字符串输出；(2)在输出的末尾追加换行符，退出程序

如：

long1lfw@ubuntu:~/桌面$ echo $PATH

/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin:/usr/games

cat的使用，运行cat命令，你输入什么，它就回复什么，用ctrl+D结束

或者查看某个文件： long1lfw@ubuntu:~/桌面$ cat bm/a.cpp

就会显示bm文件夹下a.cpp的内容到终端

">" "<" ">>"几种重定向

long1lfw@ubuntu:~/桌面$ echo "$PATH" > try

就把echo的结果输入到try文件里，但会覆盖try

long1lfw@ubuntu:~/桌面$ cat < try >try2

使用cat < try输出try的内容，然后> try2输入到try2中

long1lfw@ubuntu:~/桌面$ cat < try >> try2

使用">>" 就不是覆盖了，而是追加到未行

“|” 管道，类似"<"和">"的组合，读出前者作为输入到后者,常与文本检索命令"grep"连用

比如读取try2前5行作为输入，给grep，让它查找"try"在哪里

long1lfw@ubuntu:~/桌面$ head -n5 try2 | grep "try"

或者 long1lfw@ubuntu:~/桌面$ cat try | cat

内核(kernel)通过文件描述符(file descriptor)来访问文件，文件描述符是非负整数，打开现存文件或新建文件时，内核会返回一个文件描述符。

（1）文件描述符表（2）系统文件表（3）内存索引节点表

习惯上标准输入的文件描述符是0，标准输出是1，标准错误是2

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

Linux/UNIX下存在一些特殊的文件。例如/dev下的null和zero文件。 null文件相当与Linux系统的一个黑洞，它非常接近于一个只写文件。所有写入它的内容都会永远丢失。而如果想从它那读取内容，则什么也读不到。zero文件则可以读出一串二进制的0。 tty文件与当前的控制终端直接相连。

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

Linux下的线程控制 (C语言实现)

long1 — Sun, 22 Apr 2012 09:30:58 +0800

Linux下的线程控制

线程(thread),现在很多系统支持多线程了。与进程相比，它是一种非常“节俭”的多任务操作方式，启动一个新进程必须分配给它独立的地址空间，建立众多的数据表来维护它的代码段，堆栈段和数据段，这是一种“昂贵“的多任务工作方式。而运行于一个进程中的多个线程，他们彼此之间使用相同的地址空间，共享大部分数据，启动一个线程所花费的空间远远小于启动一个进程所花费的空间，而且，线程间彼此切换所需的时间也远远小于进程间切换所需要的时间。进程开销是线程的30倍左右。

另外线程间通信很方便。进程有独立的数据空间，要进行数据的传递只能通过数据传递，不仅费时，而且很不方便。线程因为在同一进程下共享数据空间，所以一个线程的数据可以直接为其它线程所用，快捷方便。但要注意变量为多个线程修改，也容易出错，需要同步机制。

多线程也作为多任务，并发的工作方式：

1.提高应用程序响应。对于图形界面的程序，有些操作耗时很长，此时可以其它操作。

2.使多CPU系统更加有效。操作系统保证线程数小于CPU数时，不同线程运行于不同的CPU。

3.改善程序结构。一个即长又复杂的进程可以考虑分为多个线程，成为几个独立或半独立的运行部分，这样的程序利于理解和修改。

线程是程序执行流的最小单元，由线程ID，当前指令指针(PC),寄存器集合和堆栈组成。

线程是进程中的一个实体，被系统独立调度和分配的基本单元。线程也有就绪、阻塞和运行三种基本状态。

线程是程序中一个单一的顺序控制流程，单个程序中同时运行多个线程完成不同工作，成为多线程。

各线程共享进程资源和环境。

Linux线程函数位于libpthread共享库中，编译时要加上 -lpthread 选项

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

例子：

#include

pthread_t nt;

//打印对应的进程和线程id

void printid(const char *s){

pid_t p;

pthread_t t;

p=getpid();

t=pthread_self();

printf("%s pid is %u, tid is %u\n",s,(unsigned int)p,(unsigned int)t);

}

//线程执行函数

void* f(void *arg){ //c语言里,NULL是void*，在c++中NULL就是0

printid("new thread: ");

return ((void*)0);

}

//主函数

int main(int argc, char **argv){

int result;

result=pthread_create(&nt, NULL, f, NULL);

if(result!=0){ //线程创建失败

printf("create thread error!\n");

exit(1);

}

printid("main thread: ");

sleep(1); //用sleep函数起到延迟的作用

exit(0);

}

显示：

long1lfw@ubuntu:~/桌面$ gcc a.c -o a -lpthread

long1lfw@ubuntu:~/桌面$ ./a

main thread: pid is 3059, tid is 3079514928

new thread: pid is 3059, tid is 3079506800

Linux线程的终止

1.从线程函数return. 这对主线程不适用，从main函数return相当于调用exit.

2.一个线程可以调用pthread_cancel终止同一进程中的另一个线程

3.线程可以调用pthread_exit终止自己

线程互斥，线程同步通信等问题一直是线程控制中的重点和难点，经典例子“生产者——消费者问题”。

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

ubuntu tomcat 安装(配置环境)

long1 — Sat, 21 Apr 2012 15:44:40 +0800

安装前，先要成功安装jdk;

http://tomcat.apache.org/ 下载tomcat

下载tar.gz类型文件

放到桌面(Desktop)上，命令

sudo tar zxvf filename 解压

在终端输入：

$sudo gedit /etc/profile
在profile文件后加入以下内容：

JAVA_HOME=/home/liufupanhao/jdk1.6.0_21
export JRE_HOME=/home/liufupanhao/jdk1.6.0_21/jre
export CLASSPATH=.:$JAVA_HOME/lib:$JRE_HOME/lib:$CLASSPATH
export PATH=$JAVA_HOME/bin:$JRE_HOME/bin:$PATH
export CATALINA_HOME=/home/liufupanhao/apache-tomcat-7.0.0

如图：

注前面四行为安装jdk时加入的，如最后一行是安装tomcat是加入的保存退出

在终端输入：

sudo gedit .bashrc

打开bashrc，在bashrc最后加入：

如图：

保存退出，重新启动系统

重启后打开终端输入：

sudo gedit /home/liufupanhao/apache-tomcat-7.0.0/bin/catalina.sh

打开catalina.sh，在catalina.sh的开头加入：

JAVA_HOME=/home/liufupanhao/jdk1.6.0_21

如图：

保存退出：

在终端输入：sudo /home/liufupanhao/apache-tomcat-7.0.0/bin/startup.sh

启动tomcat (windows下是.bat启动，在linux下，.sh启动，同时也要.sh关闭)

关闭tomcat

sudo /home/liufupanhao/apache-tomcat-7.0.0/bin/shutdown.sh

接下来是注意的地方：

命令 whereis java 可以找jdk位置
jre 在 jdk1.6.0_31 里面

我电脑的环境变量为：
JAVA_HOME=/usr/share/jdk1.6.0_31/
export JRE_HOME=/usr/share/jdk1.6.0_31/jre
export CLASSPATH=.:$JAVA_HOME/lib:$JRE_HOME/lib:$CLASSPATH
export PATH=$JAVA_HOME/bin:$JRE_HOME/bin:$PATH
export CATALINA_HOME=/home/coach/Desktop/apache-tomcat-7.0.27

server里修改端口号，http默认为80，所以把8080改为80，然后可以设置虚拟路径

注意，这个路径目录下要有个WEB-INF文件，里面保存web.xml，如添加首页信息：

summary.html

Linux进程间通信 (C语言实现)

long1 — Fri, 20 Apr 2012 16:45:49 +0800

几个命令：

cat filename 显示文件内容

wc -l filename 显示文件行数列数

grep word filename 搜索文件中"word"字符所在的行

date +%D 输出 mm/dd/yy

具体都可以用

man 命令

来查看，用q退出man

回到正题，Linux进程间通信，方式有很多，这里介绍信号量，管道，消息队列

1.信号量

常见的信号有：SIGINT 程序终止(interrupt)，用户键入INTR字符(通常是ctrl+c)时发出

SIGTSTP 在用户按下挂起建(一般ctrl+z)时，系统会发出此信号，会造成进程挂起

SIGKILL和SEGSTOP这两个信号是应用程序无法捕捉和忽略的

常用函数有kill 发送信号SIGKILL给进程或进程组

raise 发信号给进程或自身

例子：

#include

int main()

{

pid_t p;

int r;

p=fork();

if(p<0)

{

printf("failed\n");

exit(1);

}

//son pid

if(p==0)

{

raise(SIGSTOP);

exit(0);

}

else

{

printf("son pid is:%d\n",p);

if(waitpid(p,NULL,WNOHANG)==0) //wait for son pid over

{

if(r=kill(p,SIGKILL)==0)

{

printf("The pid sent SIGKILL is:%d\n",p);

}

else

{

printf("failed\n");

exit(1);

}

显示：

son pid is:2004

The pid sent SIGKILL is:2004

系统调用kill和raise函数，简单的向某一进程发送信号，还有其它函数，需要有空拓展

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

2.管道

一种最基本的IPC机制，由pipe函数创建，#include int pipe(int filedes[2])

内核中开辟一块缓冲区(成为管道)用于通信，一端读，一端写，通过filedes参数传给用户程序两个文件描述付，filedes[0]指向管道读端，filedes[1]指向管道写端(0读1写，类似标准输入标准输出)

read(filedes[0])或write(filedes[1])读写内核缓冲区，成功调用返回0，失败返回-1

需要同源，同一个进程产生的进程，采用半双工方式，只允许单方面传输数据，步骤：

1）父进程调用pipe开辟管道，得到两个文件描述符指向管道的两端

2）父进程调用fork创建子进程，子进程也有两个文件描述符指向同一个管道

3）父进程关闭读端，子进程关闭写端，父进程写，子进程读，环形队列实现，数据从写端流入从读端流出，实现进程间通信

例子：

//pipe

#include

#define SIZE 100

int main(int argc,char **argv)

{

int n;

int fd[2];

pid_t p;

char str[SIZE];

if(pipe(fd)<0){

printf("pipe");

exit(1);

}

p=fork();

if(p<0){

printf("fork error!\n");

exit(1);

}

if(p>0){

close(fd[0]);

write(fd[1], "hello linux", 12);

}

else {

close(fd[1]);

n=read(fd[0], str, SIZE);

printf("%s\n",str);

}

return 0;

}

显示：

hello linux

也可以父进程fork两次，把文件描述符传给两个子进程，两个子进程间通信

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

3.消息队列

两个进程发送数据快，有最大尺寸限制，例子：

//information queue

#include

#define SIZE 256

struct message{

long msg_type;

char msg_text[SIZE];

};

int main(int argc,char **argv)

{

int qid;

key_t key;

int len;

struct message msg;

if((key=ftok(".",'a'))==-1){

printf("key error!\n");

exit(1);

}

if((qid=msgget(key,IPC_CREAT|0666))==-1){

printf("create queue error!\n");

exit(1);

}

printf("create, open queue id is: %d\n",qid);

printf("input content to queue:\n");

if((fgets((&msg)->msg_text, SIZE, stdin))==NULL){

printf("no information!\n");

exit(1);

}

msg.msg_type=getpid();

len=strlen(msg.msg_text);

if((msgsnd(qid, &msg, len, 0))<0){

printf(" add message error!\n");

exit(1);

}

if((msgrcv(qid, &msg, SIZE, 0, 0))<0){

printf("read information error!\n");

exit(1);

}

printf("information is: %s\n",(&msg)->msg_text);

if((msgctl(qid, IPC_RMID, NULL))<0){

printf("delete information queue error!\n");

exit(1);

}

exit(0);

}

显示：

long1lfw@ubuntu:~/桌面$ gcc -o a a.c

long1lfw@ubuntu:~/桌面$ ./a

create, open queue id is: 0

input content to queue:

hello queue

information is: hello queue

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

(zz) ubuntu 软件源

long1 — Fri, 20 Apr 2012 11:00:08 +0800

ubuntu sources

默认的中国源速度非常不错

在终端输入并运行
sudo cp /etc/apt/sources.list /etc/apt/sources.list.backup （备份当前的源列表，以便日後需要时恢复）
sudo gedit /etc/apt/sources.list （修改sources.list文件中源的列表）

然后保存编辑好的文件，终端执行以下命令进行软件升级。
sudo apt-get update #这一步是更新你的源列表，换源後必须执行
（如果更新速度非常慢请更换源 sudo gedit /etc/apt/sources.list ）
sudo apt-get upgrade #这一步是更新软件
更新完软件后，再继续设置吧。

有时你可能需要使用:sudo apt-get -f install 来修复安装
因为经常会用到终端：所以把终端加到右键菜单：
sudo apt-get install nautilus-open-terminal
这就终端就在右键菜单了可以了！！

# 台湾的官方源速度也相当不错，有时甚至快于内地的：
deb http://tw.archive.ubuntu.com/ubuntu lucid main restricted universe multiverse
deb http://tw.archive.ubuntu.com/ubuntu lucid-security main restricted universe multiverse
deb http://tw.archive.ubuntu.com/ubuntu lucid-updates main restricted universe multiverse
deb http://tw.archive.ubuntu.com/ubuntu lucid-backports main restricted universe multiverse
deb http://tw.archive.ubuntu.com/ubuntu lucid-proposed main restricted universe multiverse
deb-src http://tw.archive.ubuntu.com/ubuntu lucid main restricted universe multiverse
deb-src http://tw.archive.ubuntu.com/ubuntu lucid-security main restricted universe multiverse
deb-src http://tw.archive.ubuntu.com/ubuntu lucid-updates main restricted universe multiverse
deb-src http://tw.archive.ubuntu.com/ubuntu lucid-backports main restricted universe multiverse
deb-src http://tw.archive.ubuntu.com/ubuntu lucid-proposed main restricted universe multiverse

# 骨头兄亲自搭建并维护这个Ubuntu源（该源位于浙江杭州百兆共享宽带的电信机房)：
deb http://ubuntu.srt.cn/ubuntu/ lucid main restricted universe multiverse
deb http://ubuntu.srt.cn/ubuntu/ lucid-security main restricted universe multiverse
deb http://ubuntu.srt.cn/ubuntu/ lucid-updates main restricted universe multiverse
deb http://ubuntu.srt.cn/ubuntu/ lucid-proposed main restricted universe multiverse
deb http://ubuntu.srt.cn/ubuntu/ lucid-backports main restricted universe multiverse
deb-src http://ubuntu.srt.cn/ubuntu/ lucid main restricted universe multiverse
deb-src http://ubuntu.srt.cn/ubuntu/ lucid-security main restricted universe multiverse
deb-src http://ubuntu.srt.cn/ubuntu/ lucid-updates main restricted universe multiverse
deb-src http://ubuntu.srt.cn/ubuntu/ lucid-proposed main restricted universe multiverse
deb-src http://ubuntu.srt.cn/ubuntu/ lucid-backports main restricted universe multiverse

# Archive.ubuntu.com更新服务器（欧洲，此为官方源，电信网通用户使用)：
deb http://archive.ubuntu.com/ubuntu/ lucid main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu/ lucid-security main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu/ lucid-updates main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu/ lucid-proposed main restricted universe multiverse
deb http://archive.ubuntu.com/ubuntu/ lucid-backports main restricted universe multiverse
deb-src http://archive.ubuntu.com/ubuntu/ lucid main restricted universe multiverse
deb-src http://archive.ubuntu.com/ubuntu/ lucid-security main restricted universe multiverse
deb-src http://archive.ubuntu.com/ubuntu/ lucid-updates main restricted universe multiverse
deb-src http://archive.ubuntu.com/ubuntu/ lucid-proposed main restricted universe multiverse
deb http://archive.canonical.com/ lucid partner
deb-src http://archive.ubuntu.com/ubuntu/ lucid-backports main restricted universe multiverse

#北京交通大学

deb http://mirror.bjtu.edu.cn/ubuntu/ karmic main multiverse restricted universe

deb http://mirror.bjtu.edu.cn/ubuntu/ karmic-backports main multiverse restricted universe

deb http://mirror.bjtu.edu.cn/ubuntu/ karmic-proposed main multiverse restricted universe

deb http://mirror.bjtu.edu.cn/ubuntu/ karmic-security main multiverse restricted universe

deb http://mirror.bjtu.edu.cn/ubuntu/ karmic-updates main multiverse restricted universe

deb-src http://mirror.bjtu.edu.cn/ubuntu/ karmic main multiverse restricted universe

deb-src http://mirror.bjtu.edu.cn/ubuntu/ karmic-backports main multiverse restricted universe

deb-src http://mirror.bjtu.edu.cn/ubuntu/ karmic-proposed main multiverse restricted universe

deb-src http://mirror.bjtu.edu.cn/ubuntu/ karmic-security main multiverse restricted universe

deb-src http://mirror.bjtu.edu.cn/ubuntu/ karmic-updates main multiverse restricted universe

#江苏双线

deb http://mirror.lupaworld.com/ubuntu karmic main restricted universe multiverse

deb http://mirror.lupaworld.com/ubuntu karmic-security main restricted universe multiverse

deb http://mirror.lupaworld.com/ubuntu karmic-updates main restricted universe multiverse

deb http://mirror.lupaworld.com/ubuntu karmic-backports main restricted universe multiverse

deb http://mirror.lupaworld.com/ubuntu/ubuntu-cn karmic main restricted universe multiverse

deb http://mirror.lupaworld.com/ubuntu/ karmic-proposed main restricted universe multiverse

deb-src http://mirror.lupaworld.com/ubuntu karmic main restricted universe multiverse

deb-src http://mirror.lupaworld.com/ubuntu karmic-security main restricted universe multiverse

deb-src http://mirror.lupaworld.com/ubuntu karmic-updates main restricted universe multiverse

deb-src http://mirror.lupaworld.com/ubuntu karmic-backports main restricted universe multiverse

deb-src http://mirror.lupaworld.com/ubuntu/ karmic-proposed main restricted universe multiverse

Linux下进程控制 (C语言实现)

long1 — Thu, 19 Apr 2012 18:13:17 +0800

Linux环境下，每个正在运行的程序都称为进程，它相当于Windows系统中的任务，可以用top查看用q退出，或ps -aux查看具体。每个进程包含进程标识符及数据，这些数据包含进程变量、外部变量和进程栈等。

进程和程序的区别：

1.程序是指令的有序集合，其本身没有任何运行的意义，是一个静态的概念。而进程是程序在处理机上的一次执行过程，它是一个动态的概念。

2.程序可以作为一种软件长期存在，而进程是有一定生命期的。程序是永久的，进程是暂时的。

3.进程更能真实地描述并发，而程序不能；进程是由程序和数据两部分组成的。

4.进程具有创建其它进程的功能，程序没有。

5.同一程序运行于若干个数据集合上，它将属于若干个不同的进程。也就是说同一程序可以对应多个进程。

6.在传统的操作系统中，程序并不能独立运行，作为资源分配和独立运行的基本单位都是进程。

每个进程在内核中都有一个进程控制块(PCB)来维护进程相关的信息，Linux内核的进程控制块是task_stuct结构体。每个进程有唯一id,C语言中用pid_t类型表示，其实就是一个非负整数。进程状态有“就绪”，“运行”，“阻塞”，“挂起(睡眠)”，“停止”，“僵尸”等状态。进程中包含的信息都保存在PCB中。

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

pid是进程号，ppid是父进程号，他们都是正整数。使用getpid,getppid获得：

vim p.c

进入vim输入"i"进入编辑模式，输入代码：

#include //别忘了这个头文件

#include

int main(int argc,char **argv){

printf("进程号:%d, 父进程号:%d\n",getpid(),getppid());

return 0;

}

"ESC"切换到命令模式， ":wq"保存退出

然后运行：

long1lfw@ubuntu:~/桌面$ vim p.c

long1lfw@ubuntu:~/桌面$ gcc p.c -o p

long1lfw@ubuntu:~/桌面$ ./p

进程号:3829, 父进程号:3138

多次运行，pid都不一样(逐渐变大),ppid一样，许多程序利用取得的pid值来建立临时文件，以避免临时文件相同带来的问题。

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

进程创建

1.exec

有六种，execve是真正的系统调用函数，其它五个是库函数，最终都会调用execve.

int execve(const char *path, char *const argv[], char *const envp[]);

path是要被执行的程序的路径， argv命令行参数（命令的集合）, envp传递环境变量

const例子：

这里是const char *p; “自以为指向常量的指针”,指针地址值可以增减(p++可以)，也可以给指针更换指向的常量，但不可以直接通过(*p)='b'来改变，例子程序：

#include

int main(int argc,char **argv){

const char *p;

char c='a';

p=&c;

printf("c=%c\n",*p);

c='b'; //(*p)='b'; 这个不可以

printf("c=%c\n",*p);

}

输出：c=a c=b

类似const int p; p的值就不能变了，p为常量,上面p变为*p,所以*p的值不能变； const char *p和char const *p一样（所以本质上就看const 和 p还是*p）；

char * const p 指向不变，内容可以用(*p)来修改，是一个“长指针”，例子程序：

#include

int main(int argc,char **argv){

char c='a';

char b='d';

char *const p=&c;

printf("c=%c ",*p);

c='b';

printf("c=%c ",*p);

(*p)='c'; //p=&b; 这个不可以

printf("c=%c\n",*p);

}

对c，(*p)操作都可以，唯一不可操作的是p=&b,也就是说，p指向的地址不能变，地址里的东西可以变

回到正题，使用execve()函数，例子：

#include

int main(int argc,char **argv){

char *str[]={"ls", NULL};

printf("当前进程的进程号为:%d\n", getpid());

if(execve("/bin/ls", str, NULL)<0) printf("execve error!");

return 0;

}

long1lfw@ubuntu:~/桌面$ vim p.c

long1lfw@ubuntu:~/桌面$ gcc p.c -o p

long1lfw@ubuntu:~/桌面$ ./p

当前进程的进程号为:5738

250 eclipse.desktop p.c

ContestAppletProd.jnlp google-chrome.desktop ?????????

codeblocks.desktop netbeans.desktop ??????????????????

com.qq.web.webtop.desktop p

这个和直接命令里输入 ls类似，文字编码不一样：

long1lfw@ubuntu:~/桌面$ ls

250 eclipse.desktop p.c

codeblocks.desktop google-chrome.desktop 未命名文件夹

com.qq.web.webtop.desktop netbeans.desktop 新文件

ContestAppletProd.jnlp p

在使用exec函数族的时候，加上错误判断语句，失败时往往因为“找不到文件路径”

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

2.system函数

函数原型include int system(cosnt char *string);

system()会调用fork()产生子进程，由子进程来调用/bin/sh -c string来执行参数string字符串所代表的命令，此命令执行完后随即返回原调用的进程。在调用system()期间SIGCHLD信号会被暂时搁置，SIGINT和SIGQUIT信号则会被忽略。

返回值： =-1: 出现错误

=0：调用成功，但没有出现子进程

>0：成功退出的子进程的id

如果system()在调用/bin/sh 时失败则返回127,其他失败原因返回-1，看个例子：

#include

int main(int argc,char **argv){

int t;

printf("当前进程号是：%d\n",getpid());

t=system("ls -l");

printf("t=%d\n",t);

return 0;

}

运行：（运行了ls -l 的命令）

long1lfw@ubuntu:~/桌面$ vim p.c

long1lfw@ubuntu:~/桌面$ gcc p.c -o p

long1lfw@ubuntu:~/桌面$ ./p

当前进程号是：2363

总计 60

-rw-r--r-- 1 long1lfw long1lfw 1894 2012-01-11 11:40 250

-rwxr-xr-x 1 long1lfw long1lfw 323 2011-11-11 11:09 codeblocks.desktop

-rwx------ 1 long1lfw long1lfw 344 2011-11-10 18:17 com.qq.web.webtop.desktop

-rw-r--r-- 1 long1lfw long1lfw 962 2011-11-11 16:55 ContestAppletProd.jnlp

-rwxr-xr-x 1 long1lfw long1lfw 195 2011-11-11 11:09 eclipse.desktop

-rwxr-xr-x 1 long1lfw long1lfw 8467 2011-11-10 18:01 google-chrome.desktop

-rw-r--r-- 1 long1lfw long1lfw 4760 2012-04-19 16:37 Linux下进程控制

-rwxr-xr-x 1 long1lfw long1lfw 283 2011-11-11 11:09 netbeans.desktop

-rwxr-xr-x 1 long1lfw long1lfw 7229 2012-04-19 16:43 p

-rw-r--r-- 1 long1lfw long1lfw 165 2012-04-19 16:43 p.c

drwxr-xr-x 3 long1lfw long1lfw 4096 2012-04-18 11:29 未命名文件夹

t=0

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

3.fork函数

作用是根据一个现有的进程复制出一个新进程，原来的进程成为父进程，新进程为子进程。shell下输入命令可以运行一个程序，是因为shell进程在读取用户输入的命令后会调用fork复制出一个新的shell进程，然后新的shell进程调用exec执行新的程序

一个程序可以多次加载到内存成为同时运行的多个进程，如打开多个终端运行/bin/bash，另一方面，一个进程在调用exec前后也可以分别执行两个不同的程序，如shell提示符下输入ls,首先fork串建子进程，这时子进程仍在执行/bin/bash程序，然后子进程调用exec执行新的程序/bin/ls

用fork创建子进程后，子进程会复制父进程的数据和堆栈空间，并继承父进程的用户代码，组代码，环境变量，已经打开的文件代码，工作目录及资源限制等，但使用的内存空间不同。

原型： #include #include pid_t fork(void);

调用失败（内存不足或用户的最大进程数已到）返回-1，否则fork返回值有很重要的作用。对于父进程fork返回子进程的ID,而对于fork子进程返回0，根据这个返回值来区分父子进程的。一旦子进程被创建，父子进程一起从fork处继续执行，相互竞争系统的资源。

例子：

#include

int main(void){

pid_t p;

char *message;

int n;

p=fork();

if(p<0) {printf("fork failed\n"); exit(1);}

if(p==0){message="This is the child\n"; n=6;}

else {message="This is the parent\n"; n=3;}

for(; n>0; n--){printf("%d %s",n,message);sleep(1);}

return 0;

}

运行：

long1lfw@ubuntu:~/桌面$ vim p.c

long1lfw@ubuntu:~/桌面$ gcc p.c -o p

long1lfw@ubuntu:~/桌面$ ./p

3 This is the parent

6 This is the child

2 This is the parent

5 This is the child

1 This is the parent

4 This is the child

3 This is the child

long1lfw@ubuntu:~/桌面$ 2 This is the child

1 This is the child

这里sleep(1)是1s(java里貌似是1ms),当父进程结束时，shell进程认为命令执行结束了，于是打印shell提示符号，而事实上子进程还没有结束，所以子进程的消息打印到了shell提示符后面，最后光标停在1 This is the child的下一行，这时用户仍可以敲命令，即使不紧跟在提示符(long1lfw@ubuntu:~/桌面$)后面，shell也能正确读取

fork函数的特点概括起来就是“调用一次，返回两次”，在父进程中调用一次，在父进程和子进程中各返回一次,就像分叉了一样，所以才用fork这个名字。

fork的另一个特性是所有的父进程打开的描述符都被复制到子进程中。父、子进程中相同编号的文件描述符在内核中指向统一个file结构体，也就是说，file结构体的引用计数要增加。

进程终止

滥用fork会占满系统进程，资源消耗殆尽，所以有终止，stdlib.h的exit和unistd.h_exit()，一般情况下，exit(0)表示正常退出，exit(1),exit(-1)为异常退出

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

僵尸进程(zombie)

指已终止运行，但尚未被清楚的进程。如果父进程终止早，子进程还在运行，就成了僵尸进程

父进程通过wait和waitpid等函数等待子进程结束，父进程挂起或阻塞。

例子：

#include

int main(int argc,int **argv){

pid_t pid;

pid=fork();

if(pid<0) {printf("fork failed\n"); exit(1);}

if(pid==0){int i; for(i=3; i>0; i--){printf("This is child\n"); sleep(1);} exit(3);}

else {

int stat_val;

waitpid(pid, &stat_val, 0);

if(WIFEXITED(stat_val)) printf("Child exited with code %d\n", WEXITSTATUS(stat_val));

else if(WIFSIGNALED(stat_val)) printf("Child terminated abnormally, signa %d\n",WTERMSIG(stat_val));

}

return 0;

}

运行：

long1lfw@ubuntu:~/桌面$ vim p.c

long1lfw@ubuntu:~/桌面$ gcc p.c -o p

long1lfw@ubuntu:~/桌面$ ./p

This is child

Child exited with code 3

如果子进程是正常终止的，WIFEXITED取出的字段值非零，就是子进程的退出状态；如果异常终止，WIFSIGNALED取出的是信号的编号。这些是宏定义，在头文件里可以查看相关运算，如何取出字段。

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

Linux 程序设计基础 gcc gdb makefile 等

long1 — Wed, 18 Apr 2012 11:28:22 +0800

pwd命令现实当前路径

long1lfw@ubuntu:~/桌面$ pwd

/home/long1lfw/桌面

建立a.c文件，内容：

#include

int main(){

printf("hello world\n");

return 0;

}

然后在终端里(ctrl+alt+t): gcc a.c -o a

编译成a

然后: ./a

输出： hello world

有三种写法：

gcc file.c -o file

gcc -o file file.c

gcc file.c

前两种生成file目标文件,第三种生成file.out文件

gcc的编译过程: 源文件(*.c)->预处理(Pre-Processing)->编译(Compiling)->汇编(Assembing)->链接(Linking)->可执行文件

然后使用rm -v a 删除a,显示:已删除“a”

rm[必要参数][选择性参数][目录或者文件]

rm指令用来删除文件或者目录，如果使用rm来删除文件，通常仍可以将文件恢复。如果想保证该文件的内容无法复原，可以考虑使用shred指令。

必要参数具体说明如下：

参数功能

-d 删除可能仍有数据的目录

-f 强制删除

-i 交互模式

-v 运行时显示详细的信息

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

gdb调试期是linux下一款GNU组织开发的程序调试工具，虽然没有友好界面，但功能强大,需要先通过gcc编译生成可执行文件后，才能用gdb调试

gcc a.c -o a -g

注意gcc编译时，最后加-g,编译好后，命令: gdb a

输出一些gdb信息，然后可以(gdb)调试了

输入: "l", 显示行号； "b 行号" 在相应行位置设置断点，可以用"info b"查看

如：

(gdb) l

1 #include

2 int main(){

3 int a,b,c;

4 printf("input a,b:\n");

5 scanf("%d",&a);

6 scanf("%d",&b);

7 a++;

8 b++;

9 c=a+b;

10 printf("%d\n",c);

(gdb) l

11 return 0;

12 }

这里每次最多显示10行

(gdb) b 5 就设置了一个断点，然后类似设置几个，用info b查看

(gdb) info b

Num Type Disp Enb Address What

1 breakpoint keep y 0x08048459 in main at a.c:5

2 breakpoint keep y 0x08048483 in main at a.c:7

3 breakpoint keep y 0x0804848e in main at a.c:8

"r"来运行程序至断点; "p 变量名"可以观察对应变量的值

如果单步调试，可输入"s"或"n"，"s"会进入函数，"n"不会

要推出gdb环境，输入"q"，选择"y"

如果有四个文件a.c:

#include

#include "file.h"

int main(){

int i;

int n=5;

int a[5]={1,2,3,4,5};

double a_sum,a_avg;

a_sum=Sum(a,n);

a_avg=Avg(a,n);

printf("sum is %f,avg is %f\n",a_sum,a_avg);

return 0;

}

b.c:

double Sum(int *a, int n){

double sum=0.0;

int i;

for(i=0; i

return sum;

}

c.c:

double Avg(int *a, int n){

double avg=0.0;

int i;

for(i=0; i

return avg/n;

}

file.h:

double Sum(int *a, int n);

double Avg(int *a, int n);

把他们编译运行可以： gcc a.c b.c c.c -o d

然后 long1lfw@ubuntu:~/桌面$ ./d

sum is 15.000000,avg is 3.000000

但很多文件，有时部分文件修改，不许要全部都编译，但编译器不知道哪些文件最近更新过的，所以都要重新编译，工作量就很大了。这事make工程管理器就排上用场了

make是一个“自动编译管理器”,这里的“自动”是指它能够根据文件时间戳自动发现更新过的文件而减少编译的工作量。同时，它通过读入makefile文件的内容来执行大量的编译工作。用户只需编写一次编写语句就可以了，从而大大提高了实际的工作效率。

一个makefile文件中通常包含以下内容：

1.目标体(target),通常是目标文件或可执行文件 2.目标所依赖的文件 3.创建目标时需要运行的命令

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

先创建一个vim makefileabc

提示：程序“vim”已包含在下列软件包中：

* vim

* vim-gnome

* vim-tiny

* vim-gtk

* vim-nox

请尝试：sudo apt-get install <选定的软件包>

我们install简单的vim

long1lfw@ubuntu:~/桌面$ sudo apt-get install vim

vim-gnome有图形界面，也比较好

然后再 vim makefileabc

1.初始进入vi是「命令行模式（command mode）」，还不能编辑，要转换到「插入模式（Insert mode）」，按一下字母「i」就能够进入「插入模式（Insert mode）」，这时候您就能够开始输入文字了。

2.现在处于「插入模式（Insert mode）」，您就只能一直输入文字，假如您发现输错了字！想用光标键往回移动，将该字删除，就要先按一下「ESC」键转到「命令行模式（command mode）」再删除文字。

3.在「命令行模式（command mode）」下，按一下「：」冒号键进入「Last line mode」，例如：

: w filename （输入「w filename」将文章以指定的文档名filename保存）

: wq (输入「wq」，存盘并退出vi)

: q! (输入q!，不存盘强制退出vi)

vim中功能增强了，可以回移

vim makefileabc输入：

abc:a.o b.o c.o

gcc a.o b.o c.o -o abc

a.o:a.c file.h

gcc a.c -c

b.o:b.c

gcc b.c -c

c.o:c.c

gcc c.c -c

[ESC] :wq 保存退出到终端

然后输入：make -f makefileabc

此时终端显示如下信息：

long1lfw@ubuntu:~/桌面$ make -f makefileabc

gcc a.c -c

gcc b.c -c

gcc c.c -c

gcc a.o b.o c.o -o abc

此时在执行abc，就可以得到之前一样的结果，代表编译和链接等过程已执行。注意的是gcc前面的空格是[Tab]形成的，不是空格建，那么makefile的书写规范：

1.目标文件：依赖文件

2.[Tab] 产生目标文件的命令

(long1 vs longpo 转载请注明出处：http://blog.163.com/lfw2565295@126)

命令： uname

-a, --all print all information, in the followiorder:

　　-s, --kernel-name print the kernel name

　　-n, --nodename print the network node hostname

　　-r, --kernel-release print the kernel release

　　-v, --kernel-version print the kernel version

　　-m, --machine print the machine hardware name

　　-p, --processor print the processor type

　　-i, --hardware-platform print the hardware platform

　　-o, --operating-system print the operating system

解释：

uname这个是用于显示系统的信息

uname -r查看内核等，

uname -a也能得到所有的信息（linux发行商，版本号，主机名，liunx版本内核信息等）

这里主要讲了pwd,cd,rm,gcc,gdb,makefile,vim,uname的相关小知识，具体还需要多实验运行

又回校了

long1 — Sun, 15 Apr 2012 16:13:49 +0800

连续三周出去回来，本来简单的感冒，似乎越来越加剧了，我还算经常打篮球锻炼身体的人，哎，杯具

想想如今肾结石，脚扭伤，感冒一些列病，我也算“病怏怏”了。。

好了，说最近干了什么，首先是清明回家，这趟还挺好的，回家见见父母，上上坟，和亲戚交流交流，算是难得的节日。

接下来杭州腾讯笔试，周五晚上通知的，周六上午就要去浙大考试。。。考虑了半天，想出了一个方案，周六凌晨过去，反正时间安排也不好，随便去打打酱油。于是第二天3点半起床，刷新了早起新记录，然后黑乎乎的，没出租车，走到火车站。。。然后买了5点半的票，8点多到杭州，然后K21路1个小时的路程到浙大，真是累死，找到大学室友京龙百行，和百行一起参加了考试，考试内容反正计算机基础知识都涉及到，还有些想法题，做的感觉一般，就当一次经历了。

接下来是西安一个朋友内推的腾讯面试，想想去西安还是太麻烦了，最主要导师给我的任务是这周，不好意思推掉。这任务就是，老师病了，不方便带队参加省赛，希望我和另外两个老师带队，我有点经验，熟悉流程。于是周五下午1点半浩浩荡荡去浙大紫金港校区了，联系京龙，充饭卡，上次百行，他们均能得到些回扣（500吃掉400多，多余的给他们了），方便以后我来杭州请我吃饭。晚上住在外面小宾馆里，隔音效果很差。。。1点多了，楼梯上上下下声音很多，屋内老师打呼，楼上“爱爱”运动。。。这尼玛让我怎么睡。。。第二天还要很早起，去报道注册，发东西什么，忙到中午吃饭。腾讯杭州面试又是周五晚上才发过来，让我上午10点去瑞豪中心酒店面试。。我想如果不能改时间我就不去了，还好后来电话打过来改到下午2点，然后午饭后就匆匆赶过去，杭州的公交真是XXX，到那里1点，让我会议室里准备，其实我累的不行了，直接趴下睡了大半个小时，然后2点叫到我面试了，去1308房间，一同去的一名女生，结果一进去让我写程序，一个字符串的程序，不是一般的写个程序，而是需要算法，这个算法我脑子中没印象（后来问集训队员，尼玛是后缀数组，而且要纸上写。。）于是先写了个一般的，然后尝试写点优化的，没怎么写好。写程序时，旁边面试官问那个女生，不知道什么方向，那女生论文能力应该很强，说有写过一级论文，那个方向说的也头头是道，然后感觉问她的问题也挺简单的，让她写的程序更简单了。。她面试完了感觉挺好。然后轮到我了，首先程序没写好，其次问我会那些语言什么的，有没有写过汇编，比如如何写游戏外挂。。（明显不会），然后问上次笔试的加分题，然后问有没有玩过网游，熟悉图像处理什么的吗（当然玩过，图像处理什么的，果断不是我的方向，不会），然后问一根绳子烧完用10分钟，粗细不均匀，如何测试5分钟（尼玛脑筋急转弯题，貌似两头点着烧就可以了，当时一愣，不会），最后问网络编程里进程线程有什么区别（网络编程，没做过）。。整个下来，基本都是我不会的，想想也就这么杯具了吧，回去等消息，意思也是没什么消息了。

面试完，然后急匆匆的赶回浙大观战，还好队员给力，名次挺好的，最后本部3金3银2铜，行知2银1铜，都创了最好成绩。最后就是回校，晚上下雨，感觉冷了，又累，头也痛了，车上迷迷糊糊的睡回来，到10点半左右回到学校，感觉快趴了，买了个鸡蛋饼，回寝室了。

最后总结，最近看似很忙，但其实也不知道忙了什么，本来有准备面试复习什么的，但现在想想，操作系统，数据结构，算法，Linux，网络，c++,java程序，汇编，计算机组成，这么多知识，我完全没那么大能力能都精通，临时看的没什么效果，我也不应该对自己有那么高要求精通这么多，所以最近还是回到本行，研究生方向的论文继续做做，工作的事，以后再说吧，其次身体最要紧了，刚刚不久学校一个老师50岁左右上课前死了，让大家都很惊讶，为之可惜，我最近还是想修养修养吧，什么目标励志现在都是浮云，最后和中科大研究生朋友温鸿交流，觉得大公司这样的实习要求，还是很有商榷的，我们也不能算很差吧，工作啊，面试啊很多机遇很重要，如今还是做好本分，那么也就不想太多实习的事了，时间还有点，慢慢来了。

zz 榜样人物数理信息学院罗方炜：笃定坚守淡定泰然

long1 — Fri, 13 Apr 2012 10:56:54 +0800

又上研究生网站了，呵呵，看看也挺好的！

http://ygb.zjnu.edu.cn/show.aspx?id=1464&cid=18

http://ygb.zjnu.edu.cn/show.aspx?id=888&cid=34

罗方炜，浙江师范大学数理信息学院2010级计算机软件与理论专业研究生。研究生期间，获得校优秀研究生干部，浙江师范大学“动感地带”奖学金等荣誉。现为所在专业班长。本科就读于浙江师范大学，期间曾获得校一等奖学金，校三好学生，校优秀研究生干部，校研究与创新奖，院优秀班干部，院科研之星等八项荣誉称号。

“只要我做了决定，就会一直走下去”

说到2007年5月份第一次参加ACM省赛，罗方炜的竞赛感触很多，“相比其他院校的优秀学子，我们感到了自身的不足。”尽管这次竞赛没有获奖，但罗方炜发现了存在的问题，回校后，他积极做好准备。他平时大部分时间都“泡”在机房里，钻心研发与设计。第一学年暑假他没有回家，而是选择留在学校参加暑期集训。所谓的集训是在电脑屏幕前，连续不间断地做五个小时的程序设计题。罗方炜说，一开始参加集训的人有20余个，真正坚持到最后的人往往只有4-5人。对于这种现象，他也表示理解。毕竟集训考验的不仅是专业知识，更是一种耐力与意志的磨砺。罗方炜每次都能坚持下来，说到个中缘由时，罗方炜说：“在不断训练中，我发现了很多瓶颈。我想突破瓶颈，提升自己。最初的确是因为兴趣选择了这个专业，而现在更多地是为了超越与挑战。在做题的最后会有排名，我每次都能衡量自己的名次。就像登山一样，既然我的目标是巅峰，只有登上顶峰，你才会发现景色尽收眼底，我是不会在半途中放弃的，只要我做了决定，就会一直走下去。”

正是坚持不懈的顽强毅力，从2007年到2011年，罗方炜共参加过14次ACM国际大学生程序设计竞赛——最具影响力的大学生计算机竞赛。令人激动的是，2010年10月，罗方炜所在团队亚洲赛杭州站喜获金奖，并出线全球总决赛！2011年，罗方炜带领小组成员参加了在美国佛罗里达州奥兰多(Orlando)举办的全球总决赛，他感受到了世界顶尖高手的实力，开阔了视野。这不仅对于罗方炜、而且对于我们浙师大也是史上的大事件。

“以平常心来看待”

随着参赛的实战经验的累积和对全局意识的把握，罗方炜成为了团队的组织者。此外，作为助理教练，他还负责组织集训，训练新队员。在得失取舍，分工定位，时间意识的操练中，他收获了很多。罗方炜说，之所以能取得这些竞技的荣誉，不完全归功于自己，团队作战尤为重要。ACM属于一种现场竞赛，对团队的依赖性很大，取得的成绩是能及时看得到的。所以，比赛时三个成员做题的方向各有分工，每个人都有主攻的方向，这样组合起来才会各尽所长。

在这个喧嚣与骚动的时代，保持一颗平常心是最重要的。罗方炜说，一个人的心态很重要。在参赛的时候，他都会以平常心来看待的，他会告诉自己，每次比赛都是一种对自己的检测，重要的是在比赛中能知道自己的哪些尚待提高的东西，这样自我暗示下来，他在比赛中会淡定自若，泰然处之，凡事尽力。而心理压力大的选手往往手忙脚乱。

罗方炜酷爱运动，尤其喜爱打篮球。只要有闲暇，他都会在篮球场上一展身手。他也是以一颗平常心来看待生活的。生活的理想是为了理想的生活，这是人人渴求的。那么究竟什么是理想的生活呢？罗方炜在大三下学期曾作为交换生远赴土耳其城市花园大学留学一学期，这次经历给他感受最深的是那里的自由与闲适的氛围，他会经常和同学一起喝茶聊天。喝茶聊天中他们谈天说地，那是一种心境，也是一份自在。“闲看庭前花开花落，漫观天外云卷云舒”。宠辱不惊，去留无意间你会淡定从容积极地去面对人生，哪怕是几许失意。

“对自己有一个正确的定位”

罗方炜是个稳重、勤勉的学生，在学习上“一步一个脚印”，走的很坚定，也很踏实。现在毕业论文正在准备的过程中，倾尽了大量心血。他喜欢动脑去思考、解决问题。除了ACM竞赛，罗方炜也参加了一些数学建模的比赛。所谓数学建模，就是在三四天之内，通过对数学、物理、计算机、生物等学科的应用，解决一个实际问题，构建几种方案并以一篇论文的形式提交上去。通过众多的参赛，罗方炜掌握的是一种思维方式，而不是满足于攻克某一具体问题。罗方炜获得了“高教杯”省三等奖、美国数模二等奖的好成绩。他也做过些校级、院级课题与项目。

说到工作的方向，罗方炜和能明确地说，未来的打算是最好能进大城市类似腾讯、阿里巴巴这样的IT公司。他说，小公司的平台有很大局限，只有大公司的机制才更健全，学到的东西与提升的空间才会更大。当然，一开始大家都会从底层编码做起，他的理想职业是当一名好的计算机工程师。罗方炜对自己有一个准确的定位，“尽管在学校的表现还不错，但是就全国而已，我的成绩还是尚待提高的。”

每个人都有属于自己的位置。一个人对自己的定位准确是很重要的。不要把自己定位太高而遮蔽双眼，也不要把自己定位太低而自暴自弃。

态度决定一切。罗方炜的坚持、平常心与正确的定位决定了他今日的所作所为。汲取他人的养料浇灌自己的土壤，罗方炜的成长案例你得到收获了吗？

插入排序，希尔排序，堆排序，桶排序，外部排序

long1 — Thu, 12 Apr 2012 16:27:07 +0800

插入排序，希尔排序，堆排序，桶排序，外部排序

输入：

23 44 16 46 7 49 20 20 26 17 32 31 34 11 4 42 26 19 1 9

输出：

1 4 7 9 11 16 17 19 20 20 23 26 26 31 32 34 42 44 46 49

插入排序，最优可达O(n),一般O(n^2);

希尔排序，需要找增量序列，有点类似插入排序，可能有更好的增量，最坏O(n^2)

不好的情况：1 9 2 10 3 11 4 12 5 13 6 14 7 15 8 16,这样前几趟就是无用功

堆排序，构建二叉堆，每次将左右2个儿子中最大（最小）值与父亲比，保证父亲比儿子大（小），这样保证跟最大（小）

从0结点开始，左右儿子为0*2+1， 0*2+2

从1结点开始，左右儿子为1*2, 1*2+1

堆排序就是先构建好二叉堆，然后每次取堆顶元素，剩下的重构，为了节省空间，堆顶元素与a[j]交换，剩下j个元素重新构建

代码：

#include

using namespace std;

int a[1000];

void insertSort(int n,int *a){ //插入排序

for(int i,p=1; p

int tmp=a[p];

for(i=p; i>0 && tmp

a[i]=tmp;

}

void shellSort(int n,int *a){ //希尔排序

for(int gap=n/2; gap>0; gap/=2){

for(int i=gap,j; i

int tmp=a[i];

for(j=i; j>=gap && tmp

a[j]=tmp;

}

inline int leftChild(int i){return i*2+1;}

void precDown(int *a,int i,int n){

int child,tmp=a[i];

for(; leftChild(i)

child=leftChild(i);

if(child!=n-1 && a[child]

if(tmp

else break;

}

a[i]=tmp;

}

void heapSort(int n,int *a){ //堆排序

for(int i=n/2; i>=0; i--) precDown(a,i,n); //buildHeap

for(int j=n-1; j>=0; j--){

swap(a[0],a[j]); //deleteMax

precDown(a,0,j);

}

int main(){

freopen("a.in","r",stdin);

freopen("a.out","w",stdout);

int n;

scanf("%d",&n);

for(int i=0; i

//insertSort(n,a);

//shellSort(n,a);

heapSort(n,a);

for(int i=0; i

}

桶排序，输入a1,a2...an,都小于m的时候，且都是正整数，则可以开大小为m的count数组，出现某个位置的数，count[a[i]]++

最后扫描count数组就可以了，用时O(n+m)，需要有预见性，知道规模 (其实就是标记法排序)

外部排序，大部分内部排序算法都用到内存可直接寻址的事实，但如果数据量大，放在磁带(磁盘),不可能直接寻址就失去了效率，磁带上是顺序访问，磁盘也有延迟

简单算法、多路合并、多相合并、替换选择

AVL树类似平衡二叉树 SB树

long1 — Wed, 11 Apr 2012 22:35:21 +0800

概述

　　在计算机科学中，AVL树是最先发明的自平衡二叉查找树。AVL树得名于它的发明者 G.M. Adelson-Velsky 和 E.M. Landis，他们在 1962 年的论文 "An algorithm for the organization of information" 中发表了它。

编辑本段 AVL 节点数计算

　　高度为 h 的 AVL 树, 节点数 N 最多2^h - 1；最少Nh= F【h+ 2】 - 1 (F【h+ 2】是 Fibonacci polynomial 的第h+2个数)。

　　最少节点数n 如以费伯纳西数列可以用数学归纳法证明：

　　即:

　　N0 = 0 (表示 AVL Tree 高度为0的节点总数)

　　N1 = 1 (表示 AVL Tree 高度为1的节点总数)

　　N2 = 2 (表示 AVL Tree 高度为2的节点总数)

　　Nh= N【h- 1】 + N【h- 2】 + 1 (表示 AVL Tree 高度为h的节点总数)

　　换句话说，当节点数为N 时，高度h 最多为logN + 2。

　　节点的平衡因子是它的右子树的高度减去它的左子树的高度。带有平衡因子 1、0 或 -1 的节点被认为是平衡的。带有平衡因子 -2 或 2 的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

编辑本段 操作

　　AVL树的基本操作一般涉及运做同在不平衡的二叉查找树所运做的同样的算法。但是要进行预先或随后做一次或多次所谓的"AVL 旋转"。

　　假设由于在二叉排序树上插入结点而失去平衡的最小子树根结点的指针为a(即a是离插入点最近，且平衡因子绝对值超过1的祖先结点)，则失去平衡后进行进行的规律可归纳为下列四种情况：

　　单向右旋平衡处理RR：由于在*a的右子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行一次右旋转操作；

　　单向左旋平衡处理LL：由于在*a的左子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行一次左旋转操作；

一字型旋转

　　双向旋转（先左后右）平衡处理LR：由于在*a的左子树根结点的右子树上插入结点，*a的平衡因子由1增至2，致使以*a为根的子树失去平衡，则需进行两次旋转（先左旋后右旋）操作。

　　双向旋转（先右后左）平衡处理RL：由于在*a的右子树根结点的左子树上插入结点，*a的平衡因子由-1变为-2，致使以*a为根的子树失去平衡，则需进行两次旋转（先右旋后左旋）操作。

之字型旋转

插入

　　向AVL树插入可以通过如同它是未平衡的二叉查找树一样把给定的值插入树中，接着自底向上向根节点折回，于在插入期间成为不平衡的所有节点上进行旋转来完成。因为折回到根节点的路途上最多有 1.5 乘 log n 个节点，而每次 AVL 旋转都耗费恒定的时间，插入处理在整体上耗费 O(log n) 时间。　在平衡的的二叉排序树Balanced BST上插入一个新的数据元素e的递归算法可描述如下：　若BBST为空树，则插入一个数据元素为e的新结点作为BBST的根结点，树的深度增1；若e的关键字和BBST的根结点的关键字相等，则不进行；若e的关键字小于BBST的根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e插入在BBST的左子树上，并且当插入之后的左子树深度增加(+1)时，分别就下列不同情况处理之： BBST的根结点的平衡因子为-1(右子树的深度大于左子树的深度，则将根结点的平衡因子更改为0，BBST的深度不变； BBST的根结点的平衡因子为0（左、右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1； BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：则若BBST的左子树根结点的平衡因子为1：则需进行单向右旋平衡处理，并且在右旋处理之后，将根结点和其右子树根结点的平衡因子更改为0，树的深度不变；若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同关键字的结点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加(+1)时，分别就不同情况处理之。

删除

　　从AVL树中删除可以通过把要删除的节点向下旋转成一个叶子节点，接着直接剪除这个叶子节点来完成。因为在旋转成叶子节点期间最多有 log n个节点被旋转，而每次 AVL 旋转耗费恒定的时间，删除处理在整体上耗费 O(log n) 时间。

查找

　　在AVL树中查找同在一般BST完全一样的进行，所以耗费 O(log n) 时间，因为AVL树总是保持平衡的。不需要特殊的准备，树的结构不会由于查询而改变。(这是与伸展树查找相对立的，它会因为查找而变更树结构。)

编辑本段 参考实现

　　给出一个操作AVLTREE的完整程序大部分由Peter Brass编写　#include 　#include 　#include 　//建立一个整数类型　typedef struct obj_n_t　{　int obj_key;　} obj_node_t;　//建立树结点的基本机构　typedef struct tree_n_t {　int key;　struct tree_n_t *left,*right;　int height;　} tree_node_t;　//建立堆栈　#define MAXSIZE 512　tree_node_t *stack[MAXSIZE]; //warning!the tree can contain 256 leaves at most!　int i=0; //堆栈计数器　//堆栈清空　void stack_clear()　{　while(i!=0)

　　{

　　stack[i-1]=NULL;

　　i--;

　　}

　　//堆栈为空

　　int stack_empty()

　　{

　　return(i==0);

　　}

　　//入栈函数

　　int push(tree_node_t *node)

　　{

　　if(i

　　{

　　stack[i++]=node;

　　return(0);

　　}

　　else

　　return(-1);

　　}

　　//出栈函数

　　tree_node_t *pop()

　　{

　　if(i>0)

　　return(stack[--i]);

　　else

　　return(0);

　　}

　　//建立get_node函数，用于动态分配内存空间

　　tree_node_t *get_node()

　　{

　　tree_node_t *tmp;

　　tmp=(tree_node_t *)malloc(sizeof(tree_node_t));

　　return(tmp);

　　}

　　//建立return_node函数，用于释放内存

　　void return_node(tree_node_t *free_node)

　　{

　　free(free_node);

　　}

　　//建立左旋转函数

　　void left_rotation(tree_node_t *node)

　　{

　　tree_node_t *tmp;

　　int tmp_key;

　　tmp=node->left;

　　tmp_key=node->key;

　　node->left=node->right;

　　node->key=node->right->key;

　　node->right=node->left->right;

　　node->left->right=node->left->left;

　　node->left->left=tmp;

　　node->left->key=tmp_key;

　　}

　　//建立右旋转函数

　　void right_rotation(tree_node_t *node)

　　{

　　tree_node_t *tmp;

　　int tmp_key;

　　tmp=node->right;

　　tmp_key=node->key;

　　node->right=node->left;

　　node->key=node->left->key;

　　node->left=node->right->left;

　　node->right->left=node->right->right;

　　node->right->right=tmp;

　　node->right->key=tmp_key;

　　}

　　int rebalance(tree_node_t *node)

　　{

　　int finished=0;

　　while(!stack_empty()&&!finished)

　　{

　　int tmp_height,old_height;

　　node=pop(); //back to the root along the search path

　　old_height=node->height;

　　if(node->left->height-node->right->height==2)

　　{

　　if(node->left->left->height-node->right->height==1)

　　{

　　right_rotation(node);

　　node->right->height=node->right->left->height+1;

　　node->height=node->right->height+1;

　　}

　　else

　　{

　　left_rotation(node->left);

　　right_rotation(node);

　　tmp_height=node->left->left->height;

　　node->left->height=tmp_height+1;

　　node->right->height=tmp_height+1;

　　node->height=tmp_height+2;

　　}

　　else if(node->left->height-node->right->height==-2)

　　{

　　if(node->right->right->height-node->left->height==1)

　　{

　　left_rotation(node);

　　node->left->height=node->left->right->height+1;

　　node->height=node->left->height+1;

　　}

　　else

　　{

　　right_rotation(node->right);

　　left_rotation(node);

　　tmp_height=node->right->right->height;

　　node->left->height=tmp_height+1;

　　node->right->height=tmp_height+1;

　　node->height=tmp_height+2;

　　}

　　else

　　{

　　if(node->left->height>node->right->height)

　　node->height=node->left->height+1;

　　else

　　node->height=node->right->height+1;

　　}

　　if(node->height==old_height)

　　finished=1;

　　}

　　stack_clear();

　　return(0);

　　}

　　//建立creat_tree函数，用于建立一颗空树

　　tree_node_t *creat_tree()

　　{

　　tree_node_t *root;

　　root=get_node();

　　root->left=root->right=NULL;

　　root->height=0;

　　return(root); //build up an empty tree.the first insert bases on the empty tree.

　　}

　　//建立find函数，用于查找一个对象

　　obj_node_t *find(tree_node_t *tree,int query_key)

　　{

　　tree_node_t *tmp;

　　if(tree->left==NULL)

　　return(NULL);

　　else

　　{

　　tmp=tree;

　　while(tmp->right!=NULL)

　　{

　　if(query_keykey)

　　tmp=tmp->left;

　　else

　　tmp=tmp->right;

　　}

　　if(tmp->key==query_key)

　　return((obj_node_t*)tmp->left);

　　else

　　return(NULL);

　　}

　　//建立插入函数

　　int insert(tree_node_t *tree,obj_node_t *new_obj)

　　{

　　tree_node_t *tmp;

　　int query_key,new_key;

　　query_key=new_key=new_obj->obj_key;

　　if(tree->left==NULL)

　　{

　　tree->left=(tree_node_t *)new_obj;

　　tree->key=new_key;

　　tree->height=0;

　　tree->right=NULL;

　　}

　　else

　　{

　　stack_clear();

　　tmp=tree;

　　while(tmp->right!=NULL)

　　{

　　//use stack to remember the path from root to the position at which the new object should be inserted.

　　//then after inserting,we can rebalance from the parrent node of the leaf which pointing to new object to the root node.

　　push(tmp);

　　if(query_keykey)

　　tmp=tmp->left;

　　else

　　tmp=tmp->right;

　　}

　　if(tmp->key==query_key)

　　return(-1);

　　else

　　{

　　tree_node_t *old_leaf,*new_leaf;

　　//It must allocate 2 node space in memory.

　　//One for the new one,another for the old one.

　　//the previous node becomes the parrent of the new node.

　　//when we delete a leaf,it will free two node memory spaces as well.

　　old_leaf=get_node();

　　old_leaf->left=tmp->left;

　　old_leaf->key=tmp->key;

　　old_leaf->right=NULL;

　　old_leaf->height=0;

　　new_leaf=get_node();

　　new_leaf->left=(tree_node_t *)new_obj;

　　new_leaf->key=new_key;

　　new_leaf->right=NULL;

　　new_leaf->height=0;

　　if(tmp->key

　　{

　　tmp->left=old_leaf;

　　tmp->right=new_leaf;

　　tmp->key=new_key;

　　}

　　else

　　{

　　tmp->left=new_leaf;

　　tmp->right=old_leaf;

　　}

　　tmp->height=1;

　　}

　　rebalance(tmp);

　　return(0);

　　}

　　//建立删除函数

　　int del(tree_node_t *tree,int key)

　　{

　　tree_node_t *tmp,*upper,*other;

　　if(tree->left==NULL)

　　return(-1);

　　else if(tree->right==NULL)

　　{

　　if(tree->key==key)

　　{

　　tree->left=NULL;

　　return(0);

　　}

　　else

　　return(-1);

　　}

　　else

　　{

　　tmp=tree;

　　stack_clear();

　　while(tmp->right!=NULL)

　　{

　　upper=tmp;

　　push(upper);

　　if(keykey)

　　{

　　tmp=upper->left;

　　other=upper->right;

　　}

　　else

　　{

　　tmp=upper->right;

　　other=upper->left;

　　}

　　if(tmp->key!=key)

　　return(-1);

　　else

　　{

　　upper->key=other->key;

　　upper->left=other->left;

　　upper->right=other->right;

　　upper->height=upper->height-1;

　　return_node(tmp);

　　return_node(other);

　　rebalance(pop());

　　//here must pop,then rebalance can run from the parrent of upper,because upper has become a leaf.

　　return(0);

　　}

　　//建立测试遍历函数

　　int travel(tree_node_t *tree)

　　{

　　stack_clear();

　　if(tree->left==NULL)

　　push(tree);

　　else if(tree->left!=NULL)

　　{

　　int m=0;

　　push(tree);

　　while(i!=m)

　　{

　　if(stack[m]->left!=NULL && stack[m]->right!=NULL)

　　{

　　push(stack[m]->left);

　　push(stack[m]->right);

　　}

　　m++;

　　}

　　return(0);

　　}

　　//建立测试函数

　　int test_structure(tree_node_t *tree)

　　{

　　travel(tree);

　　int state=-1;

　　while(!stack_empty())

　　{

　　--i;

　　if(stack->right==NULL && stack->height==0) //this statement is leaf,but also contains an empty tree

　　state=0;

　　else if(stack->left!=NULL && stack->right!=NULL)

　　{

　　if(abs(stack->height-stack->height)<=1)

　　state=0;

　　else

　　{

　　state=-1;

　　stack_clear();

　　}

　　stack_clear();

　　return(state);

　　}

　　//建立remove_tree函数

　　int remove_tree(tree_node_t *tree)

　　{

　　travel(tree);

　　if(stack_empty())

　　return(-1);

　　else

　　{

　　while(!stack_empty())

　　{

　　return_node(pop());

　　}

　　return(0);

　　}

　　void main()

　　{

　　tree_node_t *atree=NULL;

　　obj_node_t obj[256],*f; //MAXSIZE=n(number of leaf)+(n-1) number of node

　　int n,j=0;

　　cout<<"Now Let's start this program! There is no tree in memory.\n";

　　int item;

　　while(item!=0)

　　{

　　cout<<"\nRoot address = "<

　　cout<<"\n1.Create a tree\n";

　　cout<<"\n2.Insert a int type object\n";

　　cout<<"\n3.Test the structure of the tree\n";

　　cout<<"\n4.Find a object\n";

　　cout<<"\n6.Delete a object\n";

　　cout<<"\n7.Remove the Tree\n";

　　cout<<"\n0.Exit\n";

　　cout<<"\nPlease select:";

　　cin>>item;

　　cout<<"\n\n\n";

　　switch(item)

　　{

　　case 1:

　　{

　　atree=creat_tree();

　　cout<<"\nA new empty tree has been built up!\n";

　　break;

　　}

　　case 2:

　　{

　　if(atree!=NULL)

　　while(n!=3458)

　　{

　　cout<<"Please insert a new object.\nOnly one object every time(3458 is an end code) : ";

　　cin>>n;

　　if(n!=3458)

　　{

　　obj[j].obj_key=n;

　　if(insert(atree,&obj[j])==0)

　　{

　　j++;

　　cout<<"Integer "<

　　}

　　else

　　cout<<"\n\nInsert failed!\n\n";

　　}

　　else

　　cout<<"\n\nNo tree in memory,insert Fail!\n\n";

　　break;

　　}

　　case 3:

　　{

　　if(atree!=NULL)

　　{

　　n=test_structure(atree);

　　if(n==-1)

　　cout<<"\n\nIt's not a correct AVL tree.\n\n";

　　if(n==0)

　　cout<<"\n\nIt's a AVL tree\n\n";

　　}

　　else

　　cout<<"\n\nNo tree in memory,Test Fail!\n\n";

　　break;

　　}

　　case 4:

　　{

　　if(atree!=NULL)

　　{

　　cout<<"\n\nWhat do you want to find? : ";

　　cin>>n;

　　f=find(atree,n);

　　if(f==NULL)

　　{

　　cout<<"\n\nSorry,"<

　　}

　　else

　　{

　　cout<<"\n\nObject "<obj_key<<" has been found!\n\n";

　　}

　　else

　　cout<<"\n\nNo tree in memory,Find Fail!\n\n";

　　break;

　　}

　　case 5:

　　{

　　if(atree!=NULL)

　　{

　　travel(atree);

　　for(int count=0;count

　　{

　　cout<<" "<key<<",";

　　}

　　else

　　cout<<"\n\nNo tree in memory,Travel Fail!\n\n";

　　break;

　　}

　　case 6:

　　{

　　if(atree!=NULL)

　　{

　　cout<<"\n\nWhich object do you want to delete?\n\n";

　　cin>>n;

　　if(del(atree,n)==0)

　　{

　　cout<<"\n\n"<

　　}

　　else

　　cout<<"\n\nNo this object\n\n";

　　}

　　else

　　cout<<"\n\nNo tree in memory,Delete Fail!\n\n";

　　break;

　　}

　　case 7:

　　{

　　if(atree!=NULL)

　　{

　　remove_tree(atree);

　　cout<<"\n\nThe Tree has been removed!\n\n";

　　atree=NULL;

　　}

　　else

　　cout<<"\n\nNo tree in memory,Removing Fail!\n\n";

　　}

　　default:

　　cout<<"\n\nNo this operation!\n\n";

　　}

　　n=0;

　　}

SQL查询前10条记录（SqlServer/mysql/oracle）[语法分析] （转)

long1 — Tue, 10 Apr 2012 13:06:17 +0800

SQL查询前10条记录（SqlServer/mysql/oracle）[语法分析] （转)

Sql Server :

Sql代码

select top X * from table_name --查询前X条记录，可以改成需要的数字。
select top n * from (select top m * from table_name order by column_name ) a order by column_namedesc --查询第N到M条记录。常用的分页也是这种方式。
例如常用的分页方式：
declare @page int
declare @row int
set @page=2 --页数
set @row=3 --每页展示行数
select top (@row) * from (select top (@row*@page) * from table_name order by id ) a order by iddesc --最基本的分页方式，改变@row和@page达到分页效果

MYSQL查询前10条的方法(limit参数的第一个参数n（如下面的0或1）表示前n条记录是不在选择范围内，相当于hibernate的setFirstResult的参数加一；第二个参数表示要选择的记录条数，相当于hibernate的setMaxResult的参数)：

Sql代码

select * from table_name limit 0,10 --通常0是可以省略的，直接写成 limit 10。0代表从第0条记录后面开始，也就是从第一条开始
select * from table_name limit 1,10 --则为从第一条后面的记录开始展示，也就是说从第二条开始。

MySQL查询前5条方法(假设一个表为users表，这里作为子查询时要加入别名不然会出错，还有一点要注意的是order by在limit前面，不然还没出结果前就说要前几条，怎么搞嘛，所以limit要放最后。)：

Sql代码

select * from (select * from users order by id limit 0 , 10) partOfUsers order by id desc limit 0 , 5;

ORACLE查询前十条的方法：

Sql代码

select * from table_name where rownum--X为前多少条记录
select * from (select a.*,a.rownum rn from （select *　from table_name） a where a.rownumwhere rn>n --这句就是从n到m也的数据，分为三层结构

哈希表百科 md5 sha1

long1 — Mon, 9 Apr 2012 22:12:43 +0800

哈希表

散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

基本概念

　　* 若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。

　　* 对不同的关键字可能得到同一散列地址，即key1≠key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象” 作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。这个现象也叫散列桶，在散列桶，只能通过顺序的方式来查找，一般只需要查找三次就可以找到。科学家计算过，当重载因子不超过75%，查找效率最高。

　　* 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。

编辑本段 常用的构造散列函数的方法

　　散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位：

　　1. 直接寻址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = a·key + b，其中a和b为常数（这种散列函数叫做自身函数）。若其中H(key)中已经有值了，就往下一个找，直到H(key)中没有值了，就放进去。

　　2. 数字分析法：分析一组数据，比如一组员工的出生年月日，这时我们发现出生年月日的前几位数字大体相同，这样的话，出现冲突的几率就会很大，但是我们发现年月日的后几位表示月份和具体日期的数字差别很大，如果用后面的数字来构成散列地址，则冲突的几率会明显降低。因此数字分析法就是找出数字的规律，尽可能利用这些数据来构造冲突几率较低的散列地址。

　　3. 平方取中法：取关键字平方后的中间几位作为散列地址。

　　4. 折叠法：将关键字分割成位数相同的几部分，最后一部分位数可以不同，然后取这几部分的叠加和（去除进位）作为散列地址。

　　5. 随机数法：选择一随机函数，取关键字的随机值作为散列地址，通常用于关键字长度不同的场合。

　　6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p<=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。

编辑本段 处理冲突的方法

　　1. 开放寻址法：Hi=(H(key) + di) MOD m, i=1,2,…, k(k<=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法：

　　1.1. di=1,2,3,…, m-1，称线性探测再散列；

　　1.2. di=1^2, -1^2, 2^2,-2^2, (3)^2, …, ±(k)^2,(k<=m/2)称二次探测再散列;

　　1.3. di=伪随机数序列，称伪随机探测再散列。 ==

　　2. 再散列法：Hi=RHi(key), i=1,2,…,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。

　　3. 链地址法(拉链法)

　　4. 建立一个公共溢出区

编辑本段 查找的性能分析

　　散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。

　　查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：

　　1. 散列函数是否均匀；

　　2. 处理冲突的方法；

　　3. 散列表的装填因子。

　　散列表的装填因子定义为：α= 填入表中的元素个数 / 散列表的长度

　　α是散列表装满程度的标志因子。由于表长是定值，α与“填入表中的元素个数”成正比，所以，α越大，填入表中的元素较多，产生冲突的可能性就越大；α越小，填入表中的元素较少，产生冲突的可能性就越小。

　　实际上，散列表的平均查找长度是装填因子α的函数，只是不同处理冲突的方法有不同的函数。

　　了解了hash基本定义，就不能不提到一些著名的hash算法，MD5 和 SHA-1 可以说是目前应用最广泛的Hash算法，而它们都是以 MD4 为基础设计的。那么他们都是什么意思呢?

　　这里简单说一下：

　　（1) MD4

　　MD4(RFC 1320)是 MIT 的 Ronald L. Rivest 在 1990 年设计的，MD 是 Message Digest 的缩写。它适用在32位字长的处理器上用高速软件实现--它是基于 32 位操作数的位操作来实现的。

　　（2) MD5

　　MD5(RFC 1321)是 Rivest 于1991年对MD4的改进版本。它对输入仍以512位分组，其输出是4个32位字的级联，与 MD4 相同。MD5比MD4来得复杂，并且速度较之要慢一点，但更安全，在抗分析和抗差分方面表现更好

　　（3) SHA-1 及其他

　　SHA1是由NIST NSA设计为同DSA一起使用的，它对长度小于264的输入，产生长度为160bit的散列值，因此抗穷举(brute-force)性更好。SHA-1 设计时基于和MD4相同原理,并且模仿了该算法。

　　那么这些Hash算法到底有什么用呢?

　　Hash算法在信息安全方面的应用主要体现在以下的3个方面：

　　（1) 文件校验

　　我们比较熟悉的校验算法有奇偶校验和CRC校验，这2种校验并没有抗数据篡改的能力，它们一定程度上能检测并纠正数据传输中的信道误码，但却不能防止对数据的恶意破坏。

　　MD5 Hash算法的"数字指纹"特性，使它成为目前应用最广泛的一种文件完整性校验和(Checksum)算法，不少Unix系统有提供计算md5 checksum的命令。

　　（2) 数字签名

　　Hash 算法也是现代密码体系中的一个重要组成部分。由于非对称算法的运算速度较慢，所以在数字签名协议中，单向散列函数扮演了一个重要的角色。对 Hash 值，又称"数字摘要"进行数字签名，在统计上可以认为与对文件本身进行数字签名是等效的。而且这样的协议还有其他的优点。

　　（3) 鉴权协议

　　如下的鉴权协议又被称作挑战--认证模式：在传输信道是可被侦听，但不可被篡改的情况下，这是一种简单而安全的方法。

　　MD5、SHA1的破解

　　2004年8月17日，在美国加州圣芭芭拉召开的国际密码大会上，山东大学王小云教授在国际会议上首次宣布了她及她的研究小组近年来的研究成果——对MD5、HAVAL－128、MD4和RIPEMD等四个著名密码算法的破译结果。次年二月宣布破解SHA-1密码。

编辑本段 实际应用

　　以上就是一些关于hash以及其相关的一些基本预备知识。那么在emule里面他具体起到什么作用呢?

　　大家都知道emule是基于P2P （Peer-to-peer的缩写，指的是点对点的意思的软件），它采用了"多源文件传输协议”(MFTP，the Multisource FileTransfer Protocol)。在协议中，定义了一系列传输、压缩和打包还有积分的标准，emule 对于每个文件都有md5-hash的算法设置，这使得该文件独一无二，并且在整个网络上都可以追踪得到。

　　什么是文件的hash值呢?

　　MD5-Hash-文件的数字文摘通过Hash函数计算得到。不管文件长度如何，它的Hash函数计算结果是一个固定长度的数字。与加密算法不同，这一个Hash算法是一个不可逆的单向函数。采用安全性高的Hash算法，如MD5、SHA时，两个不同的文件几乎不可能得到相同的Hash结果。因此，一旦文件被修改，就可检测出来。

　　当我们的文件放到emule里面进行共享发布的时候，emule会根据hash算法自动生成这个文件的hash值，他就是这个文件唯一的身份标志，它包含了这个文件的基本信息,然后把它提交到所连接的服务器。当有他人想对这个文件提出下载请求的时候，这个hash值可以让他人知道他正在下载的文件是不是就是他所想要的。尤其是在文件的其他属性被更改之后（如名称等）这个值就更显得重要。而且服务器还提供了,这个文件当前所在的用户的地址,端口等信息,这样emule就知道到哪里去下载了。

　　一般来讲我们要搜索一个文件，emule在得到了这个信息后，会向被添加的服务器发出请求，要求得到有相同hash值的文件。而服务器则返回持有这个文件的用户信息。这样我们的客户端就可以直接的和拥有那个文件的用户沟通，看看是不是可以从他那里下载所需的文件。

　　对于emule中文件的hash值是固定的，也是唯一的，它就相当于这个文件的信息摘要，无论这个文件在谁的机器上，他的hash值都是不变的，无论过了多长时间，这个值始终如一，当我们在进行文件的下载上传过程中，emule都是通过这个值来确定文件。

　　那么什么是userhash呢?

　　道理同上，当我们在第一次使用emule的时候，emule会自动生成一个值，这个值也是唯一的，它是我们在emule世界里面的标志，只要你不卸载，不删除config，你的userhash值也就永远不变，积分制度就是通过这个值在起作用，emule里面的积分保存，身份识别，都是使用这个值，而和你的id和你的用户名无关，你随便怎么改这些东西，你的userhash值都是不变的，这也充分保证了公平性。其实他也是一个信息摘要，只不过保存的不是文件信息，而是我们每个人的信息。

　　那么什么是hash文件呢?

　　我们经常在emule日志里面看到，emule正在hash文件，这里就是利用了hash算法的文件校验性这个功能了，文章前面已经说了一些这些功能，其实这部分是一个非常复杂的过程，目前在ftp,bt等软件里面都是用的这个基本原理，emule里面是采用文件分块传输，这样传输的每一块都要进行对比校验，如果错误则要进行重新下载，这期间这些相关信息写入met文件，直到整个任务完成，这个时候part文件进行重新命名，然后使用move命令，把它传送到incoming文件里面，然后met文件自动删除，所以我们有的时候会遇到hash文件失败，就是指的是met里面的信息出了错误不能够和part文件匹配，另外有的时候开机也要疯狂hash，有两种情况一种是你在第一次使用，这个时候要hash提取所有文件信息，还有一种情况就是上一次你非法关机，那么这个时候就是要进行排错校验了。

　　关于hash的算法研究，一直是信息科学里面的一个前沿，尤其在网络技术普及的今天，他的重要性越来越突出，其实我们每天在网上进行的信息交流安全验证，我们在使用的操作系统密钥原理，里面都有它的身影，特别对于那些研究信息安全有兴趣的朋友，这更是一个打开信息世界的钥匙，他在hack世界里面也是一个研究的焦点。

　　一般的线性表、树中，记录在结构中的相对位置是随机的即和记录的关键字之间不存在确定的关系，在结构中查找记录时需进行一系列和关键字的比较。这一类查找方法建立在“比较”的基础上，查找的效率与比较次数密切相关。理想的情况是能直接找到需要的记录，因此必须在记录的存储位置和它的关键字之间建立一确定的对应关系f，使每个关键字和结构中一个唯一的存储位置相对应。因而查找时，只需根据这个对应关系f找到给定值K的像f(K)。若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上，由此不需要进行比较便可直接取得所查记录。在此，称这个对应关系f为哈希函数，按这个思想建立的表为哈希表（又称为杂凑法或散列表）。

　　哈希表不可避免冲突(collision)现象：对不同的关键字可能得到同一哈希地址即key1≠key2，而hash(key1)=hash(key2)。具有相同函数值的关键字对该哈希函数来说称为同义词(synonym)。因此，在建造哈希表时不仅要设定一个好的哈希函数，而且要设定一种处理冲突的方法。可如下描述哈希表：根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上并以关键字在地址集中的“象”作为相应记录在表中的存储位置，这种表被称为哈希表。

　　对于动态查找表而言，1) 表长不确定；2)在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。因此，一般情况需建立一个函数关系，以f(key)作为关键字为key的录在表中的位置，通常称这个函数f(key)为哈希函数。(注意：这个函数并不一定是数学函数)

　　哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可。

　　现实中哈希函数是需要构造的，并且构造的好才能使用的好。

　　用途：加密，解决冲突问题。。。。

　　用途很广，比特精灵中就使用了哈希函数，你可以自己看看。

　　具体可以学习一下数据结构和算法的书。

编辑本段 字符串哈希函数

　　（著名的ELFhash算法）

　　int ELFhash(char *key)

　　{

　　unsigned long h=0;

　　while(*key)

　　{

　　h=(h<<4)+*key++;

　　unsigned long g=h&0Xf0000000L;

　　if(g)

　　h^=g>>24;

　　h&=~g;

　　}

　　return h%MOD;

　　}

子串问题和模式匹配(kmp)

long1 — Mon, 9 Apr 2012 11:19:19 +0800

子串：对于一个字符串变量，例如"adereegfbw",它的子串就是像"ader"这样可以从中找到的连续的字符串。字符串"adereegfbw"本身也属于它本身最长的子串。

子串计算方法：

ab的子串：a、b、ab共3个即（2+1）个，abc的子串：a、 b、 c、 ab、 bc 、abc 共（3+2+1）个，所以若字符串的长度为n,则子串的个数就是[n+(n-1)+.......+1]个，"software"中非空子串的个数就是8+7+....+1=36个，如果包括空串,则应为37个。

串的模式匹配(kmp)：

KMP, s主串，t模式串 (存储方式由1开始到n,1..m)

i不回溯，j回溯到某个位置k,si与tk比较

当si!=sj时："s[i-k+1]s[s-k+2]..s[i-1]" == "t[1]t[2]..t[k-1]" 前k-1个字符一样 k

同时 "s[i-k+1]s[s-k+2]..s[i-1]" == "t[j-k+1]t[j-k+2]..t[j-1]";

则： "t[1]t[2]..t[k-1]" == "t[j-k+1]t[j-k+2]..t[j-1]"

依赖本模式t本身字符序列的构成

next[j] 是一个整数 -1<=next[j]取最大的可能k
可以理解为这点之前，有多少个点，与初始的多少个点一致。
接下来编号改为0~len-1，方便编程

则next[j]= (1) -1 (j==0)

           (2) max{k| 0

           (3) 0

但对next值，还需要递归调整t[next[]],用递归的方法求next函数值初始：next[1]=0;

因为对于本身的t串，也是模式匹配的问题，采用压缩路径的方式，复杂度O(n+m)

char a[10001],b[1000001];

int next[10001],la,lb;

void getNext(){

      int i=0,j=-1; next[0]=-1;

    while(i<la){

        if(j==-1 || a[i]==a[j]){

            i++,j++;

            //next[i]=j; 这里可以改进

            if(a[i]==a[j]) next[i]=next[j];

            else next[i]=j;

        }else j=next[j];

    }

}

int kmp(){

      int i=0,j=0,cnt=0;

    while(i<lb){

        if(j==-1 || b[i]==a[j]){

            i++,j++;

            if(j==la) return 1;

        }else j=next[j];

    }return 0;

}

特殊矩阵数据结构里的特殊矩阵及其存储

long1 — Sun, 8 Apr 2012 16:33:27 +0800

特殊矩阵

    　所谓特殊矩阵是指非零元素或零元素的分布有一定规律的矩阵。常见的有对称矩阵、三角矩阵和对角矩阵等。
1．对称矩阵
（1）对称矩阵
    　在一个n阶方阵A中，若元素满足下述性质：
       a_ij=a_ji 0≤i，j≤n-1
则称A为对称矩阵。
【例】下图便是一个5阶对称矩阵。

（2）对称矩阵的压缩存储
    对称矩阵中的元素关于主对角线对称，故只要存储矩阵中上三角或下三角中的元素，让每两个对称的元素共享一个存储空间。这样，能节约近一半的存储空间。
①按"行优先顺序"存储主对角线(包括对角线)以下的元素

    即按a₀₀,a₁₀,a₁₁,……，a_n-1,0,a_n-1,1…，a_n-1,n-1次序存放在一个向量sa[0．．n(n+1)／2-1]中（下三角矩阵中，元素总数为n(n+1)／2）。
    其中：
         sa[0]= a₀₀ ,
         sa[1] = a₁₀ ,
         ……，
         sa[n(n+1)／2-1]= a_n-1,n-1
②元素a_ij的存放位置
    a_ij元素前有i行(从第0行到第i-1行)，一共有：
         1+2+…+i=i×(i+1)／2个元素；
    在第i行上，aij之前恰有j个元素(即a_i0，a_il，…，a_i,j-1)，因此有：
           sa[i×(i+1)／2+j]= a_ij
③a_ij和sa[k]之间的对应关系：
    若i≥j，k=i×(i+1)／2+j   0≤k    若i＜j，k=j×(j+1)／2+i   0≤k    令I=max(i，j)，J=min(i，j)，则k和i，j的对应关系可统一为：
         k=I×(I+1)／2+J 0≤k
（3）对称矩阵的地址计算公式
LOC(a_ij)=LOC(sa[k])
          =LOC(sa[0])+k×d=LOC(sa[0])+[I×(I+1)／2+J]×d
    通过下标变换公式，能立即找到矩阵元素a_ij在其压缩存储表示sa中的对应位置k。因此是随机存取结构。
【例】a₂₁和a₁₂均存储在sa[4]中，这是因为
           k=I×(I+1)／2+J=2×(2+1)／2+1=4

2、三角矩阵
（1）三角矩阵的划分
    　以主对角线划分，三角矩阵有上三角矩阵和下三角矩阵两种。
①上三角矩阵
    　如下图(a)所示，它的下三角(不包括主角线)中的元素均为常数c。
②下三角矩阵
    　与上三角矩阵相反，它的主对角线上方均为常数c，如下图(b)所示。
  注意：
　    在多数情况下，三角矩阵的常数c为零。

　　　

（2）三角矩阵的压缩存储
    三角矩阵中的重复元素c可共享一个存储空间，其余的元素正好有n×(n+1)／2个，因此，三角矩阵可压缩存储到向量sa[0．．n(n+1)／2]中，其中c存放在向量的最后一个分量中。

① 上三角矩阵中a_ij和sa[k]之间的对应关系
    　上三角矩阵中，主对角线之上的第p行(0≤pij时：
     a_ij元素前有i行(从第0行到第i-1行)，一共有：
        (n-0)+(n-1)+(n-2)+…+(n-i)=i×(2n-i+1)／2个元素；
    　在第i行上，a_ij之前恰有j-i个元素(即a_ij，a_i,j+l，…，a_i,j-1)，因此有：
          sa[i×(2n-i+1)／2+j-i]= a_ij
所以：
　 ┌i×(2n-i+1)／2+j-i 当i≤j
  　k=│
      └n×(n+1)/2 当i＞j

②下三角矩阵中a_ij和sa[k]之间的对应关系
  　 ┌i×(i+1)／2+j 当i≥j
　   k=│
    　 └n×(n+1)/2 当i＜j

注意：
    　三角矩阵的压缩存储结构是随机存取结构。

3．对角矩阵
    　所有的非零元素集中在以主对角线为中心的带状区域中，即除了主对角线和主对角线相邻两侧的若干条对角线上的元素之外，其余元素皆为零的矩阵为对角矩阵。
　　【例】下图给出了一个三对角矩阵。

     其中：
    非零元素仅出现在主对角上(a_ii，0≤i≤n-1)，紧邻主对角线上面的那条对角线上(a_i_，_i+1 ，0≤i≤n-2)和紧邻主对角线下面的那条对角线上(a _i+1_，_i，0≤i≤n-2)。当|i-j|>1时，元素a_ij=0。
    　由此可知，一个k对角线矩阵(k为奇数)A是满足下述条件的矩阵：
            若|i-j|>(k-1)／2，则元素a_ij=0。
    　对角矩阵可按行优先顺序或对角线的顺序，将其压缩存储到一个向量中，并且也能找到每个非零元素和向量下标的对应关系。

转自：http://linjianren.ycool.com/post.1123606.html

实现b[i]=a[0]a[1]…a[N-1]/a[i] 不使用除法操作

long1 — Sun, 8 Apr 2012 14:22:19 +0800

实现b[i]=a[0]*a[1]*…a[N-1]/a[i]

不使用除法操作，复杂度O(n),除了循环控制的i,数组a,b,不能使用其他变量

方法：

初始b[i]记录a[i+1~n-1]的积,a[i]记录a[0~i-1]的积

再一趟循环，计算b[i]=a[i-1]*b[i+1]

复杂度：O(n)，额外数据空间：无

#include

using namespace std;

#define N 5

int main(){

int a[N]={1,2,3,4,5};

int b[N];

for(int i=N-1; i>0; i--) {

b[i]=a[i];

if(i

}

for(int i=1; i

a[i]*=a[i-1];

}

for(int i=0; i

if(i==0) b[i]=b[i+1];

else if(i==N-1 && i-1>=0) b[i]=a[i-1];

else b[i]=a[i-1]*b[i+1];

}

for(int i=0; i

printf("%d ",b[i]);

}

puts("");

system("pause");

}

清明回家归来

long1 — Thu, 5 Apr 2012 17:52:05 +0800

简述一下回家2天的经历

其实没什么经历，首先想有机会多见见爸爸妈妈，姐姐去厦门旅游了，没见到

其次自大学5年多来，我还真没主动回家，尤其清明，有两次清明去杭州玩了

4.4清明的日子很神奇，上一天，后一天的天气都是阳光明媚，就是清明的日子有点小雨，应验清明时节雨纷纷的情景

各个坟都去上了下，摆水果，点蜡烛，放烟火，捧一把泥到坟头

然后和亲戚们聊聊马上快毕业了，就业方向什么的，有说找稳定点的事业单位，教师，公务员，也有推荐去大城市闯的，但这些都是意见

身体依旧不是很好，貌似类似感冒，喉咙痛这些病我都得持续一个月左右

不过重要的是，回家和爸爸妈妈聊聊，问问他们的近况，一起吃吃饭，这样就挺好了

常回家看看！

我今年二十七八岁

long1 — Mon, 2 Apr 2012 20:06:42 +0800

我今年二十七八岁，

　　每天起床的时间从中午12点变成了早上7点，睡觉的时间从凌晨变成了晚上11点。

　　我今年二十七八岁，

　　工作中开始接触形形色色的人，

　　我今年二十七八岁，

　　见到亲戚朋友，他们不再问你考试考了几分，更多的是问现在一个月工资是多少，结婚没有哇...

　　我今年二十七八岁，

　　聊天的话题从各种网络游戏变成汽车，房子…

　　吃饭的时候，讨论的往往是他准备结婚，她哪年结婚了…

　　我今年二十七八岁，

　　每天不再感叹学校作业有多少作业做不完，开始感叹油价，房价涨得有多快，股票是涨还是跌…

　　我今年二十七八岁，

　　不再乱买东西，月底开始算计，这个月还了信用卡，开销多少，还剩下多少，该开始攒钱买房子了…

　　我今年二十七八岁，

　　渐渐的讨厌酒吧、KTV，喜欢亲近自然，喜欢健康的生活方式…

　　我今年二十七八岁，

　　偶尔会有寂寞，偶尔会怀念一个人；

　　我今年二十七八岁，

　　我们开始追逐梦想，不会再轻易流泪，不会再为了一点挫折而放弃…

　　我今年二十七八岁，

　　没有了年少的轻狂，把遇到的挫折困难都当作一种人生的阅历，试着去包容试着去忍耐…

　　我今年二十七八岁，

　　回想起曾经，我们做了太多的错事，走了太多的弯路，我们总在后悔，可是我们回不去了，回不去那个曾经纯真的年代了。

　　当我们被社会上无形的压力压得喘不过气的时候，我们渴望曾经的那份爱，渴望每天下班能有一个人一起吃饭，一起看电影，我们需要有一个人，来为我们分担一些东西。

　　我们在一条伟大的航路上，我们需要有人为我们鼓劲，也许我们偶尔累倒想放弃，可是当我们想到身边还有个让我们挂念的一个人，深吸一口气，继续向前走，我相信，总有一个能够停靠的彼岸。

　　我今年二十七八岁，

　　孤单时我们没有去网吧，我们用手机隐身上QQ，看看谁在线呢，看见熟悉的人，想说点什么，究竟又什么也没说，就这样纠结着…

　　我们把空间刷新了一遍又一遍，看看谁更新了心情，谁更新了日志，回复了符号，却没有回复句子…

　　我今年二十七八岁，

　　烦恼的时候不再发牢骚，我们静静的，静静的看着、听着，这很现实又很虚伪的世界…

　　我今年二十七八岁，

　　明明很想哭，却还在笑；

　　明明很在乎，却装作无所谓；

　　明明很想留下，却坚定地说要离开；

　　明明很痛苦，却偏偏说自己很幸福；

　　明明忘不掉，却说已经忘了；

　　明明放不下，却说她是她，我是我；

　　明明舍不得，却说我已经受够了；

　　明明说的是违心的假话，却说那是自己的真心话；

　　明明眼泪都快溢出眼眶，却高昂着头；

　　明明已经无法挽回，却依旧执着；

　　明明知道自己很受伤，却说你不必觉得欠我的；

　　明明这样『伪装』得很累，却还得依旧…

　　为得只是隐藏自己的脆弱，即使很难过，也会装的无所谓…

　　只是不愿别人看见自己的伤口，不让自己周围的人担心，不想别人同情自己…

　　只想在心底独自承受，虽然心疼的难以呼吸，却笑着告诉所有人“我没事的！”然后静下来时，自己便笑话自己，何必把自己伪装得这么坚强？好像自己可以承受所有的苦难…

　　呵…这好累，好累！！！

http://www.tudou.com/programs/view/nAFa6ESjDHg/?fr=rec1&FR=LIAN

CSS 初步 http://www.w3school.com.cn/

long1 — Mon, 2 Apr 2012 16:13:11 +0800

http://www.w3school.com.cn/

jsp页面里增加

连接到css文件夹下的style.css文件，然后样式就会按照里面的内容变化了

看看例子：

http://www.w3school.com.cn/tiy/t.asp?f=csse_background-color

代码：

这是标题 1

这是标题 2

这是段落

这个段落设置了内边距。

看看class的效果

显示：

关于背景的例子： (也可以一个声明中

background: #ff0000 url(/i/eg_bg_03.gif) no-repeat fixed center; )

body

{

background-image:url('/i/eg_bg_03.gif');

background-repeat:no-repeat;

background-attachment:fixed;

background-position:center;

}

提示：您需要把 background-attachment 属性设置为 "fixed"，才能保证该属性在 Firefox 和 Opera 中正常工作。

显示：

设置表单的样式：

显示：

超链接，鼠标放上去的样子,a:hover例子：

a:hover {

font-size: 9pt; color:#FF0000;

text-decoration: underline;

cursor:url("images/back/0081.ani");

}

a {

font-size: 9pt; text-decoration: none; color:#000000;

text-decoration: underline;

cursor:url("images/back/0081.ani");

}

id 选择器

id 选择器可以为标有特定 id 的 HTML 元素指定特定的样式。

id 选择器以 "#" 来定义。

下面的两个 id 选择器，第一个可以定义元素的颜色为红色，第二个定义元素的颜色为绿色：

#red {color:red;}

#green {color:green;}

下面的 HTML 代码中，id 属性为 red 的 p 元素显示为红色，而 id 属性为 green 的 p 元素显示为绿色。

id="red">这个段落是红色。

id="green">这个段落是绿色。

注意：id 属性只能在每个 HTML 文档中出现一次

CSS 背景属性

属性	描述
background	简写属性，作用是将背景属性设置在一个声明中。
background-attachment	背景图像是否固定或者随着页面的其余部分滚动。
background-color	设置元素的背景颜色。
background-image	把图像设置为背景。
background-position	设置背景图像的起始位置。
background-repeat	设置背景图像是否及如何重复。

CSS 文本属性

属性	描述
color	设置文本颜色
direction	设置文本方向。
line-height	设置行高。
letter-spacing	设置字符间距。
text-align	对齐元素中的文本。
text-decoration	向文本添加修饰。
text-indent	缩进元素中文本的首行。
text-shadow	设置文本阴影。CSS2 包含该属性，但是 CSS2.1 没有保留该属性。
text-transform	控制元素中的字母。
unicode-bidi	设置文本方向。
white-space	设置元素中空白的处理方式。
word-spacing	设置字间距。

CSS 字体属性

属性	描述
font	简写属性。作用是把所有针对字体的属性设置在一个声明中。
font-family	设置字体系列。
font-size	设置字体的尺寸。
font-size-adjust	当首选字体不可用时，对替换字体进行智能缩放。（CSS2.1 已删除该属性。）
font-stretch	对字体进行水平拉伸。（CSS2.1 已删除该属性。）
font-style	设置字体风格。
font-variant	以小型大写字体或者正常字体显示文本。
font-weight	设置字体的粗细。

CSS 列表属性(list)

属性	描述
list-style	简写属性。用于把所有用于列表的属性设置于一个声明中。
list-style-image	将图象设置为列表项标志。
list-style-position	设置列表中列表项标志的位置。
list-style-type	设置列表项标志的类型。
marker-offset

CSS Table 属性

属性	描述
border-collapse	设置是否把表格边框合并为单一的边框。
border-spacing	设置分隔单元格边框的距离。
caption-side	设置表格标题的位置。
empty-cells	设置是否显示表格中的空单元格。
table-layout	设置显示单元、行和列的算法。

CSS 边框属性

"CSS" 列中的数字指示哪个 CSS 版本定义了该属性。

属性	描述	CSS
outline	在一个声明中设置所有的轮廓属性。	2
outline-color	设置轮廓的颜色。	2
outline-style	设置轮廓的样式。	2
outline-width	设置轮廓的宽度。	2

开发部署一个简单的Servlet

long1 — Sun, 1 Apr 2012 22:03:37 +0800

开发部署一个简单的Servlet

Servlet程序必须通过servlet引擎来启动运行，并且存储目录有特殊要求，通常需要存储在应用程序目录>\WEB-INF\classed\目录中。Servlet程序必须在web应用程序的web.xml文件中经行注册和映射其访问路径，才可以被servlet引擎加载和被外界访问。

MyEclispe中，新建一个servlet，在新建，others中的MyEclipse中的web中的Servlet中选中(servlet wizard意思：向导程序(Wizard) )，package可以写成com,名字自己定。下一步，就会自动生成Generate/Map web.xml file了，包括servlet/jsp name，mapping url, file path of web.xml，display name和description.

自动产生的TestServlet.java:

package com;

import java.io.IOException;

import java.io.PrintWriter;

import javax.servlet.ServletException;

import javax.servlet.http.HttpServlet;

import javax.servlet.http.HttpServletRequest;

import javax.servlet.http.HttpServletResponse;

public class TestServlet extends HttpServlet {

/**

* Constructor of the object.

public TestServlet() {

super();

}

/**

* Destruction of the servlet.

public void destroy() {

super.destroy(); // Just puts "destroy" string in log

// Put your code here

}

/**

* The doGet method of the servlet.

* This method is called when a form has its tag value method equals to get.

* @param request the request send by the client to the server

* @param response the response send by the server to the client

* @throws ServletException if an error occurred

* @throws IOException if an error occurred

public void doGet(HttpServletRequest request, HttpServletResponse response)

throws ServletException, IOException {

response.setContentType("text/html");

PrintWriter out = response.getWriter();

out

.println("");

out.println("");

out.println(" A Servlet");

out.println(" ");

out.print(" This is ");

out.print(this.getClass());

out.println(", using the GET method");

out.println(" ");

out.println("");

out.flush();

out.close();

}

/**

* The doPost method of the servlet.

* This method is called when a form has its tag value method equals to post.

* @param request the request send by the client to the server

* @param response the response send by the server to the client

* @throws ServletException if an error occurred

* @throws IOException if an error occurred

public void doPost(HttpServletRequest request, HttpServletResponse response)

throws ServletException, IOException {

response.setContentType("text/html");

PrintWriter out = response.getWriter();

out

.println("");

out.println("");

out.println(" A Servlet");

out.println(" ");

out.print(" This is ");

out.print(this.getClass());

out.println(", using the POST method");

out.println(" ");

out.println("");

out.flush();

out.close();

}

/**

* Initialization of the servlet.

* @throws ServletException if an error occurs

public void init() throws ServletException {

// Put your code here

}

自动产生的web.xml:

xmlns="http://java.sun.com/xml/ns/j2ee"

xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"

xsi:schemaLocation="http://java.sun.com/xml/ns/j2ee

http://java.sun.com/xml/ns/j2ee/web-app_2_4.xsd">

This is the description of my J2EE component

This is the display name of my J2EE component

TestServlet

com.TestServlet

TestServlet

/servlet/TestServlet

index.jsp

我tomcat的虚拟路径需要添加\web，则浏览器中输入：

http://10.7.16.4/web/servlet/TestServlet

后者的/servlet/TestServlet是映射路径，用来访问servlet

显示:This is class com.TestServlet, using the GET method

是调用了doGet函数

下面的例子展示应用实例，采用JSP+JavaBean+Servlet实现留言板

新建一个sql数据库：

create database liuyan;

use liuyan;

create table message(title varchar(100),name varchar(20),time varchar(50),content varchar(2000),mail varchar(50));

2个JSP页面，index.jsp:

viewMessages.jsp:

3个message包里的java文件, AddMessageServlet.java

MessageVO.java

ViewMessageServlet.java

web.xml:

xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://java.sun.com/xml/ns/j2ee http://java.sun.com/xml/ns/j2ee/web-app_2_4.xsd">

Add

AddMessageServlet

message.AddMessageServlet

View

ViewMessageServlet

message.ViewMessageServlet

AddMessageServlet

/AddMessageServlet

ViewMessageServlet

/ViewMessageServlet

index.jsp

BASIC

注意的地方：时间格式，我自己手动调节了一下，然后viewMessages.jsp里：

<td><%out.println("+ms.getEmail()+">"+ms.getEmail()+""); %>td>

一开始写成

<td><%=out.println("+ms.getEmail()+">"+ms.getEmail()+"") %>td>

很难查错！！！

(zz) ASP、JSP、PHP三种技术比较

long1 — Sun, 1 Apr 2012 18:36:38 +0800

目前，最常用的三种动态网页语言有ASP(Active Server Pages),JSP(JavaServer Pages),PHP (Hypertext Preprocessor)。

简介

ASP全名Active Server Pages，是一个WEB服务器端的开发环境，利用它可以产生和执行动态的、互动的、高性能的WEB服务应用程序。ASP采用脚本语言(VBScript,JavaScript)作为自己的开发语言。

PHP是一种跨平台的服务器端的嵌入式脚本语言。它大量地借用C,Java和Perl语言的语法, 并耦合PHP自己的特性,使WEB开发者能够快速地写出动态产生页面。它支持目前绝大多数数据库。还有一点，PHP是完全免费的，不用花钱，你可以从PHP官方站点(http: //www.php.net)自由下载。而且你可以不受限制地获得源码，甚至可以从中加进你自己需要的特色。

JSP是Sun公司推出的新一代网站开发语言，Sun公司借助自己在Java上的不凡造诣，将Java从Java应用程序和Java Applet之外，又有新的硕果，就是JSP，Java Server Page。JSP可以在Serverlet和JavaBean的支持下，完成功能强大的站点程序。

三者都提供在 HTML代码中混合某种程序代码、由语言引擎解释执行程序代码的能力。但JSP代码被编译成 Servlet并由Java虚拟机解释执行，这种编译操作仅在对JSP页面的第一次请求时发生。在ASP 、PHP、JSP环境下，HTML代码主要负责描述信息的显示样式，而程序代码则用来描述处理逻辑。普通的 HTML页面只依赖于Web服务器，而ASP 、PHP、JSP页面需要附加的语言引擎分析和执行程序代码。程序代码的执行结果被重新嵌入到HTML代码中，然后一起发送给浏览器。ASP 、PHP、JSP三者都是面向Web服务器的技术，客户端浏览器不需要任何附加的软件支持。

　　技术特点:

ASP:

1. 使用VBScript 、 JScript等简单易懂的脚本语言，结合HTML代码，即可快速地完成网站的应用程序。

2. 无须compile编译，容易编写，可在服务器端直接执行。

3. 使用普通的文本编辑器，如Windows的记事本，即可进行编辑设计。

4. 与浏览器无关(Browser Independence), 客户端只要使用可执行HTML码的浏览器，即可浏览Active Server Pages所设计的网页内容。Active ServerPages 所使用的脚本语言(VBScript 、 Jscript)均在WEB服务器端执行，客户端的浏览器不需要能够执行这些脚本语言。

5.Active Server Pages能与任何ActiveX scripting语言兼容。除了可使用VB Script或JScript语言来设计外，还通过plug－in的方式，使用由第三方所提供的其它脚本语言，譬如REXX 、Perl 、Tcl等。脚本引擎是处理脚本程序的COM(Component Object Model) 对象。

6. 可使用服务器端的脚本来产生客户端的脚本。

7. ActiveX Server Components(ActiveX 服务器组件 )具有无限可扩充性。可以使用Visual Basic 、Java 、Visual C＋＋、COBOL等程序设计语言来编写你所需要的ActiveX Server Component 。

PHP:

1 数据库连接

PHP可以编译成具有与许多数据库相连接的函数。PHP与MySQL是现在绝佳的群组合。你还可以自己编写外围的函数去间接存取数据库。通过这样的途径当你更换使用的数据库时，可以轻松地修改编码以适应这样的变化。PHPLIB就是最常用的可以提供一般事务需要的一系列基库。但PHP提供的数据库接口支持彼此不统一，比如对Oracle, MySQL，Sybase的接口，彼此都不一样。这也是PHP的一个弱点。

JSP:

1.将内容的产生和显示进行分离

使用JSP技术，Web页面开发人员可以使用HTML或者XML标识来设计和格式化最终页面。使用JSP标识或者小脚本来产生页面上的动态内容。产生内容的逻辑被封装在标识和JavaBeans群组件中，并且捆绑在小脚本中，所有的脚本在服务器端执行。如果核心逻辑被封装在标识和Beans中，那么其它人，如Web管理人员和页面设计者，能够编辑和使用JSP页面，而不影响内容的产生。在服务器端，JSP引擎解释JSP标识，产生所请求的内容（例如，通过存取JavaBeans群组件，使用JDBC技术存取数据库），并且将结果以HTML（或者XML）页面的形式发送回浏览器。这有助于作者保护自己的代码，而又保证任何基于HTML的Web浏览器的完全可用性。

2.强调可重用的群组件

绝大多数JSP页面依赖于可重用且跨平台的组件（如：JavaBeans或者Enterprise JavaBeans）来执行应用程序所要求的更为复杂的处理。开发人员能够共享和交换执行普通操作的组件，或者使得这些组件为更多的使用者或者用户团体所使用。基于组件的方法加速了总体开发过程，并且使得各种群组织在他们现有的技能和优化结果的开发努力中得到平衡。

3.采用标识简化页面开发

Web页面开发人员不会都是熟悉脚本语言的程序设计人员。JavaServer Page技术封装了许多功能，这些功能是在易用的、与JSP相关的XML标识中进行动态内容产生所需要的。标准的JSP标识能够存取和实例化JavaBeans组件，设定或者检索群组件属性，下载Applet，以及执行用其它方法更难于编码和耗时的功能。通过开发定制化标识库，JSP技术是可以扩展的。今后，第三方开发人员和其它人员可以为常用功能建立自己的标识库。这使得Web页面开发人员能够使用熟悉的工具和如同标识一样的执行特定功能的构件来工作。 JSP技术很容易整合到多种应用体系结构中，以利用现存的工具和技巧，并且扩展到能够支持企业级的分布式应用。作为采用Java技术家族的一部分，以及Java 2EE的一个成员，JSP技术能够支持高度复杂的基于Web的应用。由于JSP页面的内置脚本语言是基于Java程序设计语言的，而且所有的JSP页面都被编译成为Java Servlet，JSP页面就具有Java技术的所有好处，包括健壮的存储管理和安全性。作为Java平台的一部分，JSP拥有Java程序设计语言“一次编写，各处执行”的特点。随着越来越多的供货商将JSP支持加入到他们的产品中，您可以使用自己所选择的服务器和工具，修改工具或服务器并不影响目前的应用。

应用范围：

ASP是Microsoft开发的动态网页语言，也继承了微软产品的一贯传统，只能执行于微软的服务器产品,IIS(Internet Information Server) (windows NT)和PWS(Personal Web Server)(windows 98)上。Unix下也有ChiliSoft的组件来支持ASP，但是ASP本身的功能有限，必须通过ASP＋COM的群组合来扩充，Unix下的COM实现起来非常困难。

PHP3可在Windows,Unix,Linux的Web服务器上正常执行,还支持IIS,Apache等一般的Web服务器,用户更换平台时,无需变换PHP3代码,可即拿即用。

JSP同PHP3类似，几乎可以执行于所有平台。如Win NT,Linux,Unix。在NT下IIS通过一个外加服务器，例如JRUN或者ServletExec，就能支持JSP。知名的Web服务器Apache已经能够支持JSP。由于Apache广泛应用在NT、Unix和Linux上，因此JSP有更广泛的执行平台。虽然现在NT操作系统占了很大的市场份额，但是在服务器方面Unix的优势仍然很大，而新崛起的Linux更是来势不小。从一个平台移植到另外一个平台，JSP和JavaBean甚至不用重新编译，因为Java字节码都是标准的与平台无关的。

性能比较：

有人做过试验，对这三种语言分别做回圈性能测试及存取Oracle数据库测试。在循环性能测试中，JSP只用了令人吃惊的四秒钟就结束了20000＊20000的回圈。而ASP、PHP测试的是2000＊2000循环（少一个数量级），却分别用了63秒和84秒。（参考PHPLIB）。数据库测试中，三者分别对 Oracle 8 进行 1000 次 Insert,Update,Select和Delete： JSP 需要 13 秒，PHP 需要 69 秒，ASP则需要 73 秒。

　　前景分析：

目前在国内PHP与ASP应用最为广泛。而JSP由于是一种较新的技术，国内采用的较少。但在国外，JSP已经是比较流行的一种技术，尤其是电子商务类的网站，多采用JSP。采用PHP的网站如新浪网（sina）、中国人（Chinaren）等，但由于PHP本身存在的一些缺点，使得它不适合应用于大型电子商务站点，而更适合一些小型的商业站点。首先，PHP缺乏规模支持。其次，缺乏多层结构支持。对于大负荷站点，解决方法只有一个：分布计算。数据库、应用逻辑层、表示逻辑层彼此分开，而且同层也可以根据流量分开，群组成二维数组。而PHP则缺乏这种支持。还有上面提到过的一点，PHP提供的数据库接口支持不统一，这就使得它不适合运用在电子商务中。

ASP和JSP则没有以上缺陷，ASP可以通过Microsoft Windowsd的COM/DCOM获得ActiveX规模支持，通过DCOM和Transcation Server获得结构支持；JSP可以通过SUN Java的Java Class和EJB获得规模支持，通过EJB/CORBA以及众多厂商的Application Server获得结构支持。三者中，JSP应该是未来发展的趋势。世界上一些大的电子商务解决方案提供商都采用JSP/Servlet。比较出名的如IBM的E－business，它的核心是采用JSP/Servlet的Web Sphere。它们都是通过CGI来提供支持的。但去年10月后它推出了Enfinity，一个采用JSP/Servlet的电子商务Application Server，而且声言不再开发传统软件。

总之，ASP，PHP,JSP三者都有相当数量的支持者，由此也可以看出三者各有所长。正在学习或使用动态页面的朋友可根据三者的特点选择一种适合自己的语言。

http://news.xinhuanet.com/internet/2007-04/29/content_6044292.htm

new String(getBytes(ISO-8859-1),GBK) 解决中文乱码问题分析

long1 — Thu, 29 Mar 2012 10:59:46 +0800

转自

http://blog.renren.com/blog/280808345/730757661

用了好几种编码全是乱码，request.setCharacterEncoding("UTF-8");尝试了好几种

String newdefrayItem = new String(request.getParameter("newdefrayItem").getBytes("iso-8859-1"),"GBK");也换了几次编码方式，最后是String newdefrayItem = new String(request.getParameter("newdefrayItem").getBytes("iso-8859-1"),"GBK");这样可以。在网上查了下原理，转了过来

tomcat默认全部都是用ISO-8859-1编码,不管你页面用什么显示,Tomcat最终还是会替你将所有字符转做ISO-8859-1.那么,当在另目标页面再用GBK翻译时就会将本来错的编码翻译成GBK的编码,这时的文字会乱码.

所以需要先将得到"字符"(不管是什么)都先用字节数组表示,且使用ISO-8859-1进行翻译,得到一个在ISO-8859-1编码环境下的字节数组.例如:AB表示成[64,65].然后再用GBK编码这个数组,并翻译成一个字符串.

那么我们可以得到一个编码转换的过程
假设:GBK码("你")->URLencode后变成->(%3F%2F)->Tomcat自动替你转一次ISO-8859-1->得到( 23 43 68 23 42 68 每一个符号表示为ISO-8859-1中的一个编码)->接收页面--->再转一次为ISO-8859-1的Byte数组[23,43,68,23,42,68]--->用GBK再转为可读的文字--->(%3F%2F"---->转为("你")

除了UTF-16，其它字符集定义时都重复。

比如汉字“我”，假设它的值是22530（只是假设，具体多少我没查）
而日文的“マ”的值也可能是22530(也是假设)或韩文的“?”

在网络上传输是不能以高字节传输，因为网络底层最后只认无符号char,相当于java中的byte,所以
22530这个int要转换为字节数组，

byte[0] = (22530 >> 8)&0xFF;
byte[1] = 22530 &0xFF;
具体多少我没算，假设是byte[125，231]

这样的字节传到服务端到是表示汉字“我”还是日文的“マ”还是其它狗屁？
一般通讯协议中会告诉对字符集，比如HTTP在请求时告诉服务端：
ContentType="xxxxxxxxxx";charset="GKB";
这时服务端就知道现在接收到的［125，231］是GKB的“我”而不是其它文字。

上面是标准的通信过程。但如果有些水平很差的程序员在提交请求时没有通知服务端字符集，那服务端就没办法了。
只好按最常用的字符集来猜一个默认的。

这还不错，最要命的是写服务器的程序员水平和见识很差时，就要命了。就象写老版本的TOMCAT的程序员，他自己生在西方，以为全世界所有人都用的是26个字母加一些符号，所以他不管客户端提交什么都按ISO-8859-1来算，结果可想而知。

没办法，谁让我们用GBK的人不会写tomcat呢，只好先把让那个差劲的程序员错误生成的String用ISO-8859-1还原成
［125，231］，再重新用GKB生成String.

用于得到服务器传来的字符重新生成GBK编码

MyEclipse 打包和发布

long1 — Wed, 28 Mar 2012 22:36:33 +0800

MyEclipse 打包和发布

开发环境

Myeclipse8.5

jdk1.6

Tomcat 7.*

实验方法一：简单的内部测试的发布方法，不用打包步骤

使用myeclipse时，在本机自动编译且运行正常后，找到Tomcat目录的相关位置，如C:/Tomcat6.0/work/Catalina/localhost/_/org/apache/jsp，下一级目录就是server.xml中配置的子目录了，复制内容该子目录的全部内容到测试服务器的同样目录下，启动测试服务器的tomcat，就能看到对应的网页了。

说明：

1、此方法，用户可以看到源文件，只能用于内部测试。

2、本人清空work目录，在myesclipse启动Tomcat时，会自动生成各下级目录和对应的内容，证明是自动生成的。

实验方法二：MyEclipse生成WAR包并在Tomcat下部署发布

首先是使用MyEclipse将web项目打包，右键选中项目，选择export。
弹出Export的select窗体，选择Java EE 的WAR file(myeclipse)选项，然后选择工程名称和路径，单击完成就可以了。

打包完成以后我们将war放到tomcat的webapps目录下，并设置server.xml文件；设置方法，在本人的其它文章中有介绍。
然后运行tomcat，并输入项目的url就可以了。

说明，对外此方法可用，即使包括了外部JAR包

补充，个人习惯是将war包用rar解压到webapps目录下的指定目录中(如abc)，然后在server.xml文件中，设置docBase项为该目录(如abc)，再启动tomcat。

说明，server.xml调整后，tomcat必须重新启动，配置文件才起作用。

实验方法三：指定目录生成jar包

在工程内的指定目录（CS或者BS结构)上单击右键，选择Export选项，弹出Export的select窗体，选择Java 的Jar file选项，然后选择工程名称和路径等，单击完成就可以了。

实验方法四：用MyEclipse视图生成并自动布署

菜单window--show view，选择package exlorer视图，在此视图中，在要生成的项目上右键，选择add and remove project deployments，弹出窗体中，单击add按钮，弹出创建新部署对话框，在server下拉框中选择tomcat 6.x服务器；选项是生成开发过程的部署(wlp)，还是最终发版的部署(war)；系统会自动部署在tomcat的webapps目录，系统允许删除此部署，允许重新部署。

说明，此方法最简单，且满足了内部测试和发版的要求。

注意事项

发布后与开发版不一样，直接用http://localhost:8080访问时，显示的是tomcat的root下的index.jsp，即使你的目录下有此文件也是显示tomcat的，解决方法，用不同的端口号，且地址改为访问IP地址，即使本机，也用http://127.0.0.1:8080，就正常了。

自动获取IP时，检查本机的IP地址的方法，运行cmd，输入ipconfig，本地连接中会显示现在的IP地址。

long1 vs longpo

屌丝们！ 别看片别强撸别搬砖了！！！！ 看看你们应该怎样逆袭！

520晚安！

1020 AOE网络 拓扑排序

UVALive - 5137 Pyramids WordFinal 2011 J 搜索DP

自然数平方数列和立方数列求和 高次推导低次

UVALive - 5132 Coffee Central WordFinal 2011 E 旋转45度坐标转换

shell编程练习2

SRM541 DIV2 250 500 1000的题 模拟 枚举最小时间 BFS java.util.Queue

(zz) Java: Queue

JAVA的Random类(转)

热情高涨的五月

SRM542 DIV2 250 500 950的题 模拟 矩形想法 组合概率

Problem Statement

Definition

Notes

Constraints

Problem Statement

Definition

Constraints

Problem Statement

Definition

Notes

Constraints

g++ diff

37th ACM/ICPC 浙江师范大学邀请赛最终排名 PC^2 版本

shell编程练习题1

shell 函数

shell的变量

shell编程基础

Linux下的线程控制 (C语言实现)

ubuntu tomcat 安装(配置环境)

Linux进程间通信 (C语言实现)

(zz) ubuntu 软件源

Linux下进程控制 (C语言实现)

Linux 程序设计基础 gcc gdb makefile 等

又回校了

zz 榜样人物数理信息学院罗方炜：笃定坚守 淡定泰然

插入排序，希尔排序，堆排序，桶排序，外部排序

AVL树 类似平衡二叉树 SB树

概述

编辑本段AVL 节点数计算

编辑本段操作

插入

删除

查找

编辑本段参考实现

SQL查询前10条记录（SqlServer/mysql/oracle）[语法分析] （转)

SQL查询前10条记录（SqlServer/mysql/oracle）[语法分析] （转)

哈希表 百科 md5 sha1

哈希表

哈希表

基本概念

编辑本段常用的构造散列函数的方法

编辑本段处理冲突的方法

编辑本段查找的性能分析

编辑本段实际应用

编辑本段字符串哈希函数

子串问题 和 模式匹配(kmp)

特殊矩阵 数据结构里的特殊矩阵及其存储

实现b[i]=a[0]*a[1]*…a[N-1]/a[i] 不使用除法操作

清明回家归来

我今年二十七八岁

CSS 初步 http://www.w3school.com.cn/

这是标题 1

这是标题 2

开发部署一个简单的Servlet

(zz) ASP、JSP、PHP三种技术比较

new String(getBytes(ISO-8859-1),GBK) 解决中文乱码问题分析

MyEclipse 打包和发布

屌丝们！别看片别强撸别搬砖了！！！！看看你们应该怎样逆袭！

1020 AOE网络拓扑排序

自然数平方数列和立方数列求和高次推导低次

SRM541 DIV2 250 500 1000的题模拟枚举最小时间 BFS java.util.Queue

SRM542 DIV2 250 500 950的题模拟矩形想法组合概率

zz 榜样人物数理信息学院罗方炜：笃定坚守淡定泰然

AVL树类似平衡二叉树 SB树

编辑本段 AVL 节点数计算

哈希表百科 md5 sha1

子串问题和模式匹配(kmp)

特殊矩阵数据结构里的特殊矩阵及其存储

实现b[i]=a[0]a[1]…a[N-1]/a[i] 不使用除法操作