&1&import&java.io.*;
&2&import&java.util.*;
&4&ID:&yanglei4
&5&LANG:&JAVA
&6&TASK:picture
&8&public&class&picture&{
&9&&&&&public&int[]&
10&&&&&public&int&N;
11&&&&&public&int&ans&=&0;
13&&&&&public&class&Line&implements&Comparable&Line&&{
14&&&&&&&&&int&s,t,p;
15&&&&&&&&&boolean&
16&&&&&&&&&public&Line(int&a,&int&b,&int&c,&boolean&d)&{
17&&&&&&&&&&&&&s&=&a;
18&&&&&&&&&&&&&t&=&b;
19&&&&&&&&&&&&&p&=&c;
20&&&&&&&&&&&&&start&=&d;
21&&&&&&&&&}
22&&&&&&&&&public&int&compareTo(Line&o)&{
23&&&&&&&&&&&&&if&(this.p&==&o.p)&{
24&&&&&&&&&&&&&&&&&if&(this.start)
25&&&&&&&&&&&&&&&&&&&&&return&-1;
26&&&&&&&&&&&&&&&&&else
27&&&&&&&&&&&&&&&&&&&&&return&1;
28&&&&&&&&&&&&&}
29&&&&&&&&&&&&&return&this.p&&&o.p&?&-1&:&1;
30&&&&&&&&&}
32&&&&&public&void&Scan(Line[]&L)&{
33&&&&&&&&&for&(int&i&=&0;i&&=&20000;i++)
34&&&&&&&&&&&&&level[i]&=&0;
35&&&&&&&&&for&(int&i&=&0;&i&&&2&*&N;i++)&{
36&&&&&&&&&&&&&if&(L[i].start)&{
37&&&&&&&&&&&&&&&&&for&(int&j&=&L[i].s;j&&&L[i].t;j++)&{
38&&&&&&&&&&&&&&&&&&&&&level[j]++;
39&&&&&&&&&&&&&&&&&&&&&if&(level[j]==1)
40&&&&&&&&&&&&&&&&&&&&&&&&&ans++;
41&&&&&&&&&&&&&&&&&}
42&&&&&&&&&&&&&}
43&&&&&&&&&&&&&else&{
44&&&&&&&&&&&&&&&&&for&(int&j&=&L[i].s;j&&&L[i].t;j++)&{
45&&&&&&&&&&&&&&&&&&&&&level[j]--;
46&&&&&&&&&&&&&&&&&&&&&if&(level[j]==0)
47&&&&&&&&&&&&&&&&&&&&&&&&&ans++;
48&&&&&&&&&&&&&&&&&}
49&&&&&&&&&&&&&}
50&&&&&&&&&}
52&&&&&public&void&done()&throws&IOException&{
53&&&&&&&&&BufferedReader&f&=&new&BufferedReader(new&FileReader("picture.in"));
54&&&&&&&&&PrintWriter&out&=&new&PrintWriter(new&BufferedWriter(new&FileWriter("picture.out")));
55&&&&&&&&&N&=&Integer.parseInt(f.readLine());
56&&&&&&&&&Line[]&Lx&=&new&Line[2&*&N];
57&&&&&&&&&Line[]&Ly&=&new&Line[2&*&N];
58&&&&&&&&&
59&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)&{
60&&&&&&&&&&&&&StringTokenizer&st&=&new&StringTokenizer(f.readLine());
61&&&&&&&&&&&&&int&x1&=&Integer.parseInt(st.nextToken());//left&x
62&&&&&&&&&&&&&int&y1&=&Integer.parseInt(st.nextToken());//left&y
63&&&&&&&&&&&&&int&x2&=&Integer.parseInt(st.nextToken());//right&x
64&&&&&&&&&&&&&int&y2&=&Integer.parseInt(st.nextToken());//right&y
65&&&&&&&&&&&&&x1&+=&10000;
66&&&&&&&&&&&&&y1&+=&10000;
67&&&&&&&&&&&&&x2&+=&10000;
68&&&&&&&&&&&&&y2&+=&10000;
69&&&&&&&&&&&&&Lx[2&*&i]&=&new&Line(x1,x2,y1,true);
70&&&&&&&&&&&&&Lx[2&*&i&+&1]&=&new&Line(x1,x2,y2,false);
71&&&&&&&&&&&&&Ly[2&*&i]&=&new&Line(y1,y2,x1,true);
72&&&&&&&&&&&&&Ly[2&*&i&+&1]&=&new&Line(y1,y2,x2,false);
73&&&&&&&&&}
74&&&&&&&&&Arrays.sort(Lx);
75&&&&&&&&&Arrays.sort(Ly);
76&&&&&&&&&level&=&new&int[20001];
77&&&&&&&&&Scan(Lx);
78&&&&&&&&&Scan(Ly);
79&&&&&&&&&out.println(ans);
80&&&&&&&&&
81&&&&&&&&&out.close();&&&&
83&&&&&public&static&void&main(String[]&args)&throws&IOException&{
84&&&&&&&&&picture&t&=&new&picture();
85&&&&&&&&&t.done();
86&&&&&&&&&System.exit(0);
这道题用了离散化的方法
其实最朴素的方法就是在一个的矩阵上面把所有的点描出来，然后把这些点的周长算出来，不过算周长这一步也是很麻烦的。
因为毕竟还有可能出现“空心”的情况
用离散化的方法就是想办法只数每条线段，而不去管其他空白的地方是怎么样的。
由于我们是需要算周长的，所以只需要看矩形的四条边就可以了。
然后，我们就是先看所有的横边，再看竖边。
先把横边全部选出来，放在一个数组里面，然后排序，从下到上。
一个矩形的两条边要分成始边和终边，排序的时候，如果纵坐标相同，那么应该把始边放在终边。
如果遇到始边，那么就把这条边上面的所有点level[j]加一。
如果遇到终边，就把那条边上所有的点的level[j]减一
于是，当一条边上的点的leve是1的时候，那么就说明这条边肯定是始边边缘，所以要ans++
另一种情况，当一条边上的点的level是0的时候，那么说明这个点是终边边缘，所以ans++
这样扫完横边再扫竖边。
最后的ans就是周长了。
不过这个算法的时间效率并不是非常的好，因为数据比较弱（可能是这样）
如果真的是有5000个矩形，没个矩形都是2000的，那么可能会超时
杨磊 阅读(182) |
虽然从5.1开始，大部分题目都要借助于NoCow和网上的解题报告，但是还是学到了不少的东西。
原来认为只要熟练的掌握各种算法，那就可以随便去切题，现在发现其实不是这样。
有很多题目，都需要进行一些转化，也可以说是建模，才能套用现成的算法
而有一些题目，根本就没有现成的算法，只能你自己去想
这种算法基本上是不属于任何一类的
还有一些比如说剪枝，虽然搜索谁都会，Brute Force谁都会写，但是剪枝却不是谁都能写的出来的
这就需要一些数学功底
现在发现这个东西必须要长年累月的积累才能够达到驾轻就熟的境界。
但是就算那样，也不能保证所有的题目都会做。
杨磊 阅读(161) |
&&1&import&java.io.*;
&&2&import&java.util.*;
&&5&LANG:&JAVA
&&6&TASK:telecow
&&8&public&class&telecow&{
&10&&&&&public&static&final&int&WHITE&=&0,&GRAY&=&1,&BLACK&=&2;
&11&&&&&private&int[][]&flow,&capacity,&res_
&12&&&&&private&int[]&parent,&color,&
&13&&&&&private&int[]&min_
&14&&&&&private&int&size,&source,&sink,&first,&
&15&&&&&private&static&int&MAXN&=&200;
&16&&&&&int&N,M;
&18&&&&&private&int&maxFlow()&&//&Edmonds-Karp&algorithm&with&O(V3E)&complexity
&20&&&&&&&&&flow&=&new&int[MAXN][MAXN];
&21&&&&&&&&&res_capacity&=&new&int[MAXN][MAXN];
&22&&&&&&&&&parent&=&new&int[MAXN];
&23&&&&&&&&&min_capacity&=&new&int[MAXN];
&24&&&&&&&&&color&=&new&int[MAXN];
&25&&&&&&&&&queue&=&new&int[MAXN];
&26&&&&&&&&&int&max_flow&=&0;
&27&&&&&&&&&for&(int&i&=&0;&i&&&&i++)
&28&&&&&&&&&&&&&for&(int&j&=&0;&j&&&&j++)
&29&&&&&&&&&&&&&&&&&res_capacity[i][j]&=&capacity[i][j];
&31&&&&&&&&&while&(BFS(source))
&32&&&&&&&&&{
&33&&&&&&&&&&&&&max_flow&+=&min_capacity[sink];
&34&&&&&&&&&&&&&int&v&=&sink,&u;
&35&&&&&&&&&&&&&while&(v&!=&source)
&36&&&&&&&&&&&&&{
&37&&&&&&&&&&&&&&&&&u&=&parent[v];
&38&&&&&&&&&&&&&&&&&flow[u][v]&+=&min_capacity[sink];
&39&&&&&&&&&&&&&&&&&flow[v][u]&-=&min_capacity[sink];
&40&&&&&&&&&&&&&&&&&res_capacity[u][v]&-=&min_capacity[sink];
&41&&&&&&&&&&&&&&&&&res_capacity[v][u]&+=&min_capacity[sink];
&42&&&&&&&&&&&&&&&&&v&=&u;
&43&&&&&&&&&&&&&}
&44&&&&&&&&&}
&45&&&&&&&&&return&max_
&48&&&&&private&boolean&BFS(int&source)&&//&Breadth&First&Search&in&O(V2)
&50&&&&&&&&&for&(int&i&=&0;&i&&&&i++)&{
&51&&&&&&&&&&&&&color[i]&=&WHITE;
&52&&&&&&&&&&&&&min_capacity[i]&=&Integer.MAX_VALUE;
&53&&&&&&&&&}
&55&&&&&&&&&first&=&last&=&0;
&56&&&&&&&&&queue[last++]&=&
&57&&&&&&&&&color[source]&=&GRAY;
&59&&&&&&&&&while&(first&!=&last)&&//&While&"queue"&not&empty..
&60&&&&&&&&&{
&61&&&&&&&&&&&&&int&v&=&queue[first++];
&62&&&&&&&&&&&&&for&(int&u&=&0;&u&&&&u++)
&63&&&&&&&&&&&&&&&&&if&(color[u]&==&WHITE&&&&res_capacity[v][u]&&&0)
&64&&&&&&&&&&&&&&&&&{
&65&&&&&&&&&&&&&&&&&&&&&min_capacity[u]&=&Math.min(min_capacity[v],&res_capacity[v][u]);
&66&&&&&&&&&&&&&&&&&&&&&parent[u]&=&v;
&67&&&&&&&&&&&&&&&&&&&&&color[u]&=&GRAY;
&68&&&&&&&&&&&&&&&&&&&&&if&(u&==&sink)&return&true;
&69&&&&&&&&&&&&&&&&&&&&&queue[last++]&=&u;
&70&&&&&&&&&&&&&&&&&}
&71&&&&&&&&&}
&72&&&&&&&&&return&false;
&75&&&&&public&void&done()&throws&IOException&{
&76&&&&&&&&&BufferedReader&f&=&new&BufferedReader(new&FileReader("telecow.in"));
&77&&&&&&&&&PrintWriter&out&=&new&PrintWriter(new&BufferedWriter(new&FileWriter("telecow.out")));
&78&&&&&&&&&StringTokenizer&st&=&new&StringTokenizer(f.readLine());
&79&&&&&&&&&N&=&Integer.parseInt(st.nextToken());
&80&&&&&&&&&M&=&Integer.parseInt(st.nextToken());
&81&&&&&&&&&source&=&Integer.parseInt(st.nextToken());
&82&&&&&&&&&sink&=&Integer.parseInt(st.nextToken());
&83&&&&&&&&&source--;
&84&&&&&&&&&sink--;
&85&&&&&&&&&int&osource&=&
&86&&&&&&&&&int&osink&=&
&87&&&&&&&&&capacity&=&new&int[N&*&2][N&*&2];
&88&&&&&&&&&
&89&&&&&&&&&//init
&90&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)
&91&&&&&&&&&&&&&capacity[i&*&2][i&*&2&+&1]&=&1;
&92&&&&&&&&&
&93&&&&&&&&&for&(int&i&=&0;&i&&&M;&i++)&{
&94&&&&&&&&&&&&&st&=&new&StringTokenizer(f.readLine());
&95&&&&&&&&&&&&&int&x&=&Integer.parseInt(st.nextToken());
&96&&&&&&&&&&&&&int&y&=&Integer.parseInt(st.nextToken());
&97&&&&&&&&&&&&&x--;
&98&&&&&&&&&&&&&y--;
&99&&&&&&&&&&&&&capacity[x&*&2&+&1][y&*&2]&=&Integer.MAX_VALUE;
100&&&&&&&&&&&&&capacity[y&*&2&+&1][x&*&2]&=&Integer.MAX_VALUE;
101&&&&&&&&&}
102&&&&&&&&&
103&&&&&&&&&for&(int&i&=&0;&i&&&2&*&N;&i++)&{
104&&&&&&&&&&&&&capacity[i][source&*&2]&=&0;
105&&&&&&&&&&&&&capacity[sink&*&2&+&1][i]&=&0;
106&&&&&&&&&}
107&&&&&&&&&
108&&&&&&&&&int[]&ans&=&new&int[N&+&1];
109&&&&&&&&&
110&&&&&&&&&size&=&2&*&N;
111&&&&&&&&&source&=&source&*&2&+&1;
112&&&&&&&&&sink&=&sink&*&2;
113&&&&&&&&&
114&&&&&&&&&int&max&=&maxFlow();
115&&&&&&&&&
116&&&&&&&&&int&count&=&0;
117&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)
118&&&&&&&&&&&&&if&(i&!=&osource&&&&i&!=&osink)&{
119&&&&&&&&&&&&&&&&&capacity[i&*&2][i&*&2&+&1]&=&0;
120&&&&&&&&&&&&&&&&&int&nowFlow&=&maxFlow();
121&&&&&&&&&&&&&&&&&
122&&&&&&&&&&&&&&&&&if&(max&-&nowFlow&==&count&+&1)&
123&&&&&&&&&&&&&&&&&&&&&ans[count++]&=&i;&&&&&&&&&&&&
124&&&&&&&&&&&&&&&&&else&
125&&&&&&&&&&&&&&&&&&&&&capacity[i&*&2][i&*&2&+&1]&=&1;
126&&&&&&&&&&&&&}
127&&&&&&&&&
128&&&&&&&&&out.println(max);
129&&&&&&&&&
130&&&&&&&&&for&(int&i&=&0;&i&&&count&-&1;&i++)
131&&&&&&&&&&&&&out.print(ans[i]&+&1&+&"&");
132&&&&&&&&&out.println(ans[count&-&1]&+&1);
133&&&&&&&&&out.close();
134&&&&&&&&&
137&&&&&public&static&void&main(String[]&args)&throws&IOException&{
138&&&&&&&&&telecow&t&=&new&telecow();
139&&&&&&&&&t.done();
140&&&&&&&&&System.exit(0);
这道题目我自己看出来是最小割的问题，而之前的题目有一道是最小割的
但是有一个不同，这道题是点的最小割，而不是常规的边的最小割
所以这就比较麻烦，需要我们把点转化成边
这就让我想起了之前的那个Fence Loops
我就是把所有的边表示的图转化成了点表示的图，我实在是不想再写那么恶心的算法了。
然后我就去NoCow上面看了一下，果然是有很赞的方法。
具体方法就是，把一个点变成两个点，然后在两个点之间加一条边，并且这条边的权值是1
这样的话，如果割这条边，就相当于去掉了这个点。
剩下的事情就是跟前面的那个Pollute Control差不多了
每次去掉一条边，然后用MaxFlow求一下最大流，如果得出的最大流==最大流-边的权值
那么就证明这条边是最小割。
就这样把所有的最小割找出来，然后就可以了
貌似数据很弱，不像上次的那个Pollute那道题目，还要考虑边的编号的问题的。
杨磊 阅读(139) |
一个搜索的题目，不过肯定是要剪枝的
最简单的两个剪枝我想到了
首先，第一行已经确定了，那么我们可以把第一列也确定，就按照升序，2，3，4，5……，这样的话，没生成这么一个square，我们就可以随便的去交换除了第一行后面的几行。
他们的一个全排列就对应着一种组合，所以最后的答案乘以N-1的阶乘就可以
这个其实是看来的，就是每次只要所搜完N-1行就可以了。因为剩下的一行必然存在一个解。其实这个不难理解的，最后一行的排列顺序只跟前面的每一列缺少的那个数有关。
而且也只能取缺少的那个数，所以也就是唯一的。
要用到置换群，我没看懂
尽管之前N次看组合数学里面都说到置换群，但是我还是似懂非懂，问了数学小王子，他也不是非常懂。然后以为这个东西没用，就忽略了。没想到还真的有用。
杨磊 阅读(253) |
今天终于第一次写了强连通分量的题目
虽然以前老早就知道有这么个东西，对这个东西也有概念，但是确实从来没有写过判别的算法
原来如此简单，但是确实也很巧妙。
在算法导论上面看到的K算法，方法就是做两遍DFS，因为强连通分量有一个性质，就是如果把所有的边反向，那么它仍然是一个强连通分量。
但是今天我用的是Tarjan算法，据说效率比K算法高很多，事实上也应该是这样，因为Tarjan算法只做了一次DFS
其实思想也很简单，就是一直DFS（u），向下向下向下，如果突然发现有一个点可以回到u了，那么这个肯定是一个强连通分量。
哈哈，是不是很通俗。
严格的定义过程大家可以看这里/blog/scc-tarjan/
我也是参考了这个才做出来的Tarjan算法，Wiki上的那个过于庞大了，虽然封装的非常好
说说本题，其实就是找强连通分量，然后把每个强连通分量当成一个“超点”来考虑
如果这个“超点”的入度为零，那么它就必然是一个源头，统计这样的“超点”的个数，就是第一问的答案。
第二问，如果有一个“超点”入度不是0，但是出度是0，那就说明这个“超点”可以给其他“超点”作贡献。
我们就找这样的点对，把入度是0和出度是0的点连起来。
这样匹配过后，剩下的要么全是入度是0的，要么全是出度是0的，这些就没办法了，随便从一个连通分量连接过来一条边就可以了。
所以第二问的答案就是所有的“超点”中，入度是0和出度是0的点大的那个数。
&&1&import&java.io.*;
&&2&import&java.util.*;
&&4&ID:&yanglei4
&&5&LANG:&JAVA
&&6&TASK:schlnet
&&8&public&class&schlnet&{
&&9&&&&&boolean[]&inS
&10&&&&&int[]&DFN;
&11&&&&&int[]&LOW;
&12&&&&&int&index&=&0;
&13&&&&&int[]&S
&14&&&&&int&top&=&0;
&15&&&&&int[][]&
&16&&&&&int&BelongCount&=&0;
&17&&&&&int[]&
&19&&&&&public&void&Tarjan(int&i)&{
&20&&&&&&&&&DFN[i]&=&LOW[i]&=&++
&21&&&&&&&&&inStack[i]&=&true;
&22&&&&&&&&&Stack[top++]&=&i;
&23&&&&&&&&&for&(int&j&=&1;&j&&=&map[i][0];&j++)&{
&24&&&&&&&&&&&&&if&(DFN[map[i][j]]&==&0)&{
&25&&&&&&&&&&&&&&&&&Tarjan(map[i][j]);
&26&&&&&&&&&&&&&&&&&if&(LOW[map[i][j]]&&&LOW[i])
&27&&&&&&&&&&&&&&&&&&&&&LOW[i]&=&LOW[map[i][j]];
&28&&&&&&&&&&&&&}
&29&&&&&&&&&&&&&else&if&(inStack[map[i][j]]&&&&DFN[map[i][j]]&&&LOW[i])
&30&&&&&&&&&&&&&&&&&LOW[i]&=&DFN[map[i][j]];
&31&&&&&&&&&}
&32&&&&&&&&&if&(DFN[i]&==&LOW[i])&{
&33&&&&&&&&&&&&&int&j&=&0;
&34&&&&&&&&&&&&&do&{
&35&&&&&&&&&&&&&&&&&j&=&Stack[--top];
&36&&&&&&&&&&&&&&&&&inStack[j]&=&false;
&37&&&&&&&&&&&&&&&&&belong[j]&=&BelongC
&38&&&&&&&&&&&&&}&while&(j&!=&i);
&39&&&&&&&&&&&&&BelongCount++;
&40&&&&&&&&&}
&41&&&&&&&&&
&44&&&&&public&void&done()&throws&IOException&{
&45&&&&&&&&&BufferedReader&f&=&new&BufferedReader(new&FileReader("schlnet.in"));
&46&&&&&&&&&PrintWriter&out&=&new&PrintWriter(new&BufferedWriter(new&FileWriter("schlnet.out")));
&47&&&&&&&&&int&N&=&Integer.parseInt(f.readLine());
&48&&&&&&&&&map&=&new&int[N&+&1][N&+&1];
&49&&&&&&&&&DFN&=&new&int[N&+&1];
&50&&&&&&&&&LOW&=&new&int[N&+&1];
&51&&&&&&&&&inStack&=&new&boolean[N&+&1];
&52&&&&&&&&&Stack&=&new&int[N&+&1];
&53&&&&&&&&&belong&=&new&int[N&+&1];
&54&&&&&&&&&
&55&&&&&&&&&Arrays.fill(belong,-1);
&56&&&&&&&&&for&(int&i&=&1;&i&&=&N;&i++)&{
&57&&&&&&&&&&&&&StringTokenizer&st&=&new&StringTokenizer(f.readLine());
&58&&&&&&&&&&&&&int&len&=&st.countTokens();
&59&&&&&&&&&&&&&map[i][0]&=&len&-&1;
&60&&&&&&&&&&&&&for&(int&j&=&1;&j&&=&len&-&1;&j++)
&61&&&&&&&&&&&&&&&&&map[i][j]&=&Integer.parseInt(st.nextToken());&&&&
&62&&&&&&&&&}
&63&&&&&&&&&
&64&&&&&&&&&for&(int&i&=&1;&i&&=&N;&i++)&{
&65&&&&&&&&&&&&&if&(DFN[i]&==&0)
&66&&&&&&&&&&&&&&&&&Tarjan(i);
&67&&&&&&&&&}&&&&
&68&&&&&&&&&boolean[][]&dis&=&new&boolean[BelongCount&+&1][BelongCount&+&1];
&69&&&&&&&&&for&(int&i&=&1;i&&=&N;i++)&{
&70&&&&&&&&&&&&&for&(int&k&=&1;k&&=&map[i][0];k++)
&71&&&&&&&&&&&&&&&&&dis[belong[i]&+&1][belong[map[i][k]]&+&1]&=&true;
&72&&&&&&&&&}
&73&&&&&&&&&int[]&oud&=&new&int[BelongCount&+&1];
&74&&&&&&&&&int[]&ind&=&new&int[BelongCount&+&1];
&75&&&&&&&&&
&76&&&&&&&&&for&(int&i&=&1;i&&=&BelongCi++)&{
&77&&&&&&&&&&&&&for&(int&j&=&1;&j&=&BelongCj++)&{
&78&&&&&&&&&&&&&&&&&if&(i!=j&&&&dis[i][j])&{
&79&&&&&&&&&&&&&&&&&&&&&oud[i]++;
&80&&&&&&&&&&&&&&&&&&&&&ind[j]++;
&81&&&&&&&&&&&&&&&&&}
&82&&&&&&&&&&&&&}
&83&&&&&&&&&}
&84&&&&&&&&&
&85&&&&&&&&&int&i0&=&0;
&86&&&&&&&&&int&o0&=&0;
&87&&&&&&&&&for&(int&i&=&1;i&&=&BelongCi++)&{
&88&&&&&&&&&&&&&if&(ind[i]&==&0)
&89&&&&&&&&&&&&&&&&&i0++;
&90&&&&&&&&&&&&&if&(oud[i]&==&0)
&91&&&&&&&&&&&&&&&&&o0++;
&92&&&&&&&&&}
&93&&&&&&&&&
&94&&&&&&&&&if&(BelongCount&==&1)&{
&95&&&&&&&&&&&&&out.println("1");
&96&&&&&&&&&&&&&out.println("0");
&97&&&&&&&&&}
&98&&&&&&&&&else&{
&99&&&&&&&&&&&&&out.println(i0);
100&&&&&&&&&&&&&out.println(i0&o0?i0:o0);
101&&&&&&&&&}&&&&
102&&&&&&&&&out.close();&&&&
105&&&&&public&static&void&main(String[]&args)&throws&IOException&{
106&&&&&&&&&schlnet&t&=&new&schlnet();
107&&&&&&&&&t.done();
108&&&&&&&&&System.exit(0);
杨磊 阅读(135) |
&1&import&java.io.*;
&2&import&java.util.*;
&5&ID:&yanglei4
&6&LANG:&JAVA
&7&TASK:bigbrn
&9&public&class&bigbrn&{
10&&&&&public&static&int&min(int&a,&int&b)&{
11&&&&&&&&&if&(a&&&b)&return&a;
12&&&&&&&&&else&return&b;
14&&&&&public&static&int&min3(int&a,&int&b,&int&c)&{
15&&&&&&&&&return&min(a,&min(b,&c));&&&&
17&&&&&public&static&void&main(String[]&args)&throws&IOException&{
18&&&&&&&&&BufferedReader&f&=&new&BufferedReader(new&FileReader("bigbrn.in"));
19&&&&&&&&&PrintWriter&out&=&new&PrintWriter(new&BufferedWriter(new&FileWriter("bigbrn.out")));
20&&&&&&&&&StringTokenizer&st&=&new&StringTokenizer(f.readLine());
21&&&&&&&&&int&N&=&Integer.parseInt(st.nextToken());
22&&&&&&&&&int&T&=&Integer.parseInt(st.nextToken());
23&&&&&&&&&int[][]&map&=&new&int[N][N];
24&&&&&&&&&for&(int&i&=&0;&i&&&T;&i++)&{
25&&&&&&&&&&&&&st&=&new&StringTokenizer(f.readLine());
26&&&&&&&&&&&&&int&x&=&Integer.parseInt(st.nextToken());
27&&&&&&&&&&&&&int&y&=&Integer.parseInt(st.nextToken());
28&&&&&&&&&&&&&map[x&-&1][y&-&1]&=&-1;
29&&&&&&&&&}
30&&&&&&&&&
31&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)&{
32&&&&&&&&&&&&&if&(map[0][i]!=&-1)
33&&&&&&&&&&&&&&&&&map[0][i]&=&1;
34&&&&&&&&&&&&&if&(map[i][0]!=&-1)
35&&&&&&&&&&&&&&&&&map[i][0]&=&1;
36&&&&&&&&&}
37&&&&&&&&&
38&&&&&&&&&
39&&&&&&&&&for&(int&i&=&1;&i&&&N;&i++)
40&&&&&&&&&&&&&for&(int&j&=&1;&j&&&N;&j++)&{
41&&&&&&&&&&&&&&&&&if&(map[i][j]&!=&-1)&{
42&&&&&&&&&&&&&&&&&&&&&int&temp&=&min3(map[i&-&1][j],&map[i][j&-&1],&map[i&-&1][j&-&1]);
43&&&&&&&&&&&&&&&&&&&&&if&(temp&!=&-1)&map[i][j]&=&temp&+&1;
44&&&&&&&&&&&&&&&&&&&&&else&map[i][j]&=&1;
45&&&&&&&&&&&&&&&&&}
46&&&&&&&&&&&&&}
47&&&&&&&&&
48&&&&&&&&&int&max&=&0;
49&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)
50&&&&&&&&&&&&&for&(int&j&=&0;&j&&&N;&j++)
51&&&&&&&&&&&&&&&&&if&(map[i][j]&!=&0&&&&map[i][j]&&&max)
52&&&&&&&&&&&&&&&&&&&&&max&=&map[i][j];
53&&&&&&&&&&&&&&&&&
54&&&&&&&&&out.println(max);
55&&&&&&&&&out.close();
56&&&&&&&&&System.exit(0);
应该算是一个比较基本的DP吧，状态转移方程也不难想，但是我最开始写成了N^3的了
首先就是用Map[i][j]来表示以i，j为右下角的最大的square的大小
初始化就是第一行，第一列，如果不是#，那么肯定是1
然后对于i，j，我们需要观察i - 1，j - 1，因为是square，所以只跟这个有关
如果在第i行，第j列上面，从当前位置开始，连续map[i-1][j-1]个位置，没有#的话，那么map[i][j] = map[i-1][j-1]+1
我就是在判断连续map[i-1][j-1]这个地方出了问题，我又加了一层循环，所以就变成了N^3的了，然后果然TLE了
这个地方完全没必要用循环一个一个去判断，因为其实你已经有结果了，这个结果就是map[i-1][j]和map[i][j-1]里面小的那个
map[i-1][j]肯定就是从当前位置开始，在第j列上，向上最多可以走多少步不碰到#
因为这时候实际上你已经确定了，#只有可能出现在第i行，第j列上，因为map[i-1][j-1]不是#就保证了这一点
于是，找到两个方向上走的比较近的那个数，如果这个数是小于map[i-1][j-1]的，那么map[i][j]就等于这个数
否则，map[i][j] = map[i-1][j-1]+1
这个地方的重点就是，如果map[i-1][j-1]不是#，那么就保证了#只能在第i行，第j列上面。
只需要检查这两个就可以
然后我们就可以来看map[i-1][j],map[i][j-1]，这两个东西其实跟map[i-1][j-1]共享了上面的一块。
如果在第i行，第j列上面出现了#，那么map[i-1][j],map[i][j-1]肯定比map[i-1][j-1]小
否则，我们的square最大也就只能是map[i-1][j-1]+1，因为map[i-1][j-1]已经是以i-1,j-1为右下角最大的square了
于是状态转移方程就是
map[i][j] = min (map[i-1][j],map[i][j-1],map[i-1][j-1]) + 1, map[i][j] != '#'
杨磊 阅读(90) |
&&&& 摘要: 绝对，非常考耐心，细心的一道题目，这道题目充分的说明我是考虑问题不全面的人
所以现在看来TopCoder的测试数据还都算是比较弱的，真的没有极其变态的，而且TopCoder的题目其实没有超级复杂的，或许是因为我从来没做过第三题吧。
这道题目其实一看就知道怎么做，但是就一个字烦
首先你要用FloodFill把所有的Cluster标注出来，这个不难，而且速度很快，时间...&&
杨磊 阅读(254) |
发个网络流的标准代码，用的是BFS
外面自己套一个类就行了
capacity自己初始化放进去就可以了
返回值在max_flow里面，有需要的话可以自己改成返回类型的
&1&&&&&public&static&final&int&WHITE&=&0,&GRAY&=&1,&BLACK&=&2;
&2&&&&&private&int[][]&flow,&capacity,&res_
&3&&&&&private&int[]&parent,&color,&
&4&&&&&private&int[]&min_
&5&&&&&private&int&size,&source,&sink,&first,&
&6&&&&&private&int&max_
&8&&&&&private&void&maxFlow()&&//&Edmonds-Karp&algorithm&with&O(V3E)&complexity
10&&&&&&&&&flow&=&new&int[size][size];
11&&&&&&&&&res_capacity&=&new&int[size][size];
12&&&&&&&&&parent&=&new&int[size];
13&&&&&&&&&min_capacity&=&new&int[size];
14&&&&&&&&&color&=&new&int[size];
15&&&&&&&&&queue&=&new&int[size];
17&&&&&&&&&for&(int&i&=&0;&i&&&&i++)
18&&&&&&&&&&&&&for&(int&j&=&0;&j&&&&j++)
19&&&&&&&&&&&&&&&&&res_capacity[i][j]&=&capacity[i][j];
21&&&&&&&&&while&(BFS(source))
22&&&&&&&&&{
23&&&&&&&&&&&&&max_flow&+=&min_capacity[sink];
24&&&&&&&&&&&&&int&v&=&sink,&u;
25&&&&&&&&&&&&&while&(v&!=&source)
26&&&&&&&&&&&&&{
27&&&&&&&&&&&&&&&&&u&=&parent[v];
28&&&&&&&&&&&&&&&&&flow[u][v]&+=&min_capacity[sink];
29&&&&&&&&&&&&&&&&&flow[v][u]&-=&min_capacity[sink];
30&&&&&&&&&&&&&&&&&res_capacity[u][v]&-=&min_capacity[sink];
31&&&&&&&&&&&&&&&&&res_capacity[v][u]&+=&min_capacity[sink];
32&&&&&&&&&&&&&&&&&v&=&u;
33&&&&&&&&&&&&&}
34&&&&&&&&&}
37&&&&&private&boolean&BFS(int&source)&&//&Breadth&First&Search&in&O(V2)
39&&&&&&&&&for&(int&i&=&0;&i&&&&i++)
40&&&&&&&&&{
41&&&&&&&&&&&&&color[i]&=&WHITE;
42&&&&&&&&&&&&&min_capacity[i]&=&Integer.MAX_VALUE;
43&&&&&&&&&}
45&&&&&&&&&first&=&last&=&0;
46&&&&&&&&&queue[last++]&=&
47&&&&&&&&&color[source]&=&GRAY;
49&&&&&&&&&while&(first&!=&last)&&//&While&"queue"&not&empty..
50&&&&&&&&&{
51&&&&&&&&&&&&&int&v&=&queue[first++];
52&&&&&&&&&&&&&for&(int&u&=&0;&u&&&&u++)
53&&&&&&&&&&&&&&&&&if&(color[u]&==&WHITE&&&&res_capacity[v][u]&&&0)
54&&&&&&&&&&&&&&&&&{
55&&&&&&&&&&&&&&&&&&&&&min_capacity[u]&=&Math.min(min_capacity[v],&res_capacity[v][u]);
56&&&&&&&&&&&&&&&&&&&&&parent[u]&=&v;
57&&&&&&&&&&&&&&&&&&&&&color[u]&=&GRAY;
58&&&&&&&&&&&&&&&&&&&&&if&(u&==&sink)&return&true;
59&&&&&&&&&&&&&&&&&&&&&queue[last++]&=&u;
60&&&&&&&&&&&&&&&&&}
61&&&&&&&&&}
62&&&&&&&&&return&false;
杨磊 阅读(109) |
原来这道题目这么简单，记得当年高中的时候做USACO的时候，好像最后就是卡在这道题目上面，然后就是NOIP了
然后我就伤心的告别了NOIP投向了好好学习的怀抱。
今天拿过来看还是没什么思路，然后就去搜了一下解题报告。
其实这个题目无论如何也是要DFS的，因为人家要你输出全部的答案。这样就不用怕了，最多就是剪剪枝。
但是最开始没有想到这一点。
问题就在这个剪枝上，和怎么判断合理的解上面。
方法就是，首先找到每一个Frame的四个角。
然后沿着这个Frame的每条边走一下，如果有其他的字符，就是跟当前Frame不同的字符，那么这个字符肯定是在当前这个字符上层的。
这样就能用一张表来确定上下关系，Above[i][j]，表示第i个字符在第j个字符上层
然后就是根据这张表来做一个DFS，这样就可以了。
看了leokan的解题报告，说还要floyd一下。
这样做的目的无非也就是想确定两两之间的上下层关系罢了。
但是似乎没这个必要，直接DFS就可以了。
&&1&import&java.io.*;
&&2&import&java.util.*;
&&4&ID:&yanglei4
&&5&LANG:&JAVA
&&6&TASK:frameup
&&8&public&class&frameup{
&&9&&&&&static&char[][]&
&10&&&&&static&int[][]&
&11&&&&&static&int[]&
&12&&&&&static&int&
&13&&&&&static&int[][]&
&14&&&&&static&char[]&
&15&&&&&static&PrintWriter&
&16&&&&&public&static&void&findAnswer(int&step)&{
&17&&&&&&&&&int&i,j;
&18&&&&&&&&&if&(step&&=&cnt)&{
&19&&&&&&&&&&&&&for&(int&k&=&0;&k&&&&k++)
&20&&&&&&&&&&&&&&&&&out.print(answer[k]);
&21&&&&&&&&&&&&&out.println();
&22&&&&&&&&&}
&23&&&&&&&&&for&(i&=&0;&i&&&26;&i++)&
&24&&&&&&&&&if&(in[i]&&0)&{
&25&&&&&&&&&&&&&for&(j&=&0;&j&&&26;&j++)&
&26&&&&&&&&&&&&&if&(in[j]&&&0&&&&above[i][j]&==&1)&break;
&27&&&&&&&&&&&&&&&&&
&28&&&&&&&&&&&&&&&if&(j&&=&26)&{&/*&no&such&frame,&so&this&COULD&be&the&next&one&*/
&29&&&&&&&&&&&&&&&&&answer[step]&=&(char)&('A'&+&i);
&30&&&&&&&&&&&&&&&&&in[i]&=&0;&/*&mark&as&in&answer&*/
&31&&&&&&&&&&&&&&&&&findAnswer(step&+&1);
&32&&&&&&&&&&&&&&&&&in[i]&=&1;&/*&clear&mark&*/
&33&&&&&&&&&&&&&&&}
&35&&&&&&&&&}
&37&&&&&public&static&void&main(String[]&args)&throws&IOException&{
&38&&&&&&&&&BufferedReader&f&=&new&BufferedReader(new&FileReader("frameup.in"));
&39&&&&&&&&&out&=&new&PrintWriter(new&BufferedWriter(new&FileWriter("frameup.out")));
&40&&&&&&&&&StringTokenizer&st&=&new&StringTokenizer(f.readLine());
&41&&&&&&&&&int&H&=&Integer.parseInt(st.nextToken());
&42&&&&&&&&&int&W&=&Integer.parseInt(st.nextToken());
&43&&&&&&&&&
&44&&&&&&&&&board&=&new&char[30][32];
&45&&&&&&&&&pos&=&new&int[26][4];
&46&&&&&&&&&in&=&new&int[26];
&47&&&&&&&&&cnt&=&0;
&48&&&&&&&&&
&49&&&&&&&&&above&=&new&int[26][26];
&50&&&&&&&&&answer&=&new&char[27];
&51&&&&&&&&&
&52&&&&&&&&&for&(int&i&=&0;&i&&&H;&i++)&{
&53&&&&&&&&&&&&&String&temp&=&f.readLine();
&54&&&&&&&&&&&&&board[i]&=&temp.toCharArray();
&55&&&&&&&&&&&&&for&(int&j&=&0;&j&&&W;&j++)&{
&56&&&&&&&&&&&&&&&&&if&(board[i][j]&!=&'.')&{
&57&&&&&&&&&&&&&&&&&&&&&int&loc&=&board[i][j]&-&'A';
&58&&&&&&&&&&&&&&&&&&&&&
&59&&&&&&&&&&&&&&&&&&&&&if&(in[loc]&==&0)&{//First&time&met
&60&&&&&&&&&&&&&&&&&&&&&&&&&in[loc]&=&1;
&61&&&&&&&&&&&&&&&&&&&&&&&&&cnt++;
&62&&&&&&&&&&&&&&&&&&&&&&&&&pos[loc][0]&=&pos[loc][2]&=&i;
&63&&&&&&&&&&&&&&&&&&&&&&&&&pos[loc][1]&=&pos[loc][3]&=&j;
&64&&&&&&&&&&&&&&&&&&&&&}
&65&&&&&&&&&&&&&&&&&&&&&else&{
&66&&&&&&&&&&&&&&&&&&&&&&&&&if&(i&&&pos[loc][0])&pos[loc][0]&=&i;
&67&&&&&&&&&&&&&&&&&&&&&&&&&if&(i&&&pos[loc][2])&pos[loc][2]&=&i;
&68&&&&&&&&&&&&&&&&&&&&&&&&&if&(j&&&pos[loc][1])&pos[loc][1]&=&j;
&69&&&&&&&&&&&&&&&&&&&&&&&&&if&(j&&&pos[loc][3])&pos[loc][3]&=&j;
&70&&&&&&&&&&&&&&&&&&&&&}
&71&&&&&&&&&&&&&&&&&&&&&&&&&
&72&&&&&&&&&&&&&&&&&}
&73&&&&&&&&&&&&&}
&74&&&&&&&&&}
&75&&&&&&&&&
&76&&&&&&&&&for&(int&i&=&0;&i&&&26;&i++)
&77&&&&&&&&&&&&&if&(in[i]&&&0)&{&/*&for&each&frame&*/
&78&&&&&&&&&&&&&&&&&&for&(int&j&=&pos[i][0];&j&&=&pos[i][2];&j++)&{&/*&check&left&and&right&borders&*/
&80&&&&&&&&&&&&&&&&&&&&/*&left&*/
&81&&&&&&&&&&&&&&&&&&&&int&loc&=&board[j][pos[i][1]]&-&'A';
&82&&&&&&&&&&&&&&&&&&&&if&(loc&!=&i)&/*&there's&a&different&frame&where&this&one&should&be&*/
&83&&&&&&&&&&&&&&&&&&&&&&above[loc][i]&=&1;&/*&that&different&frame&must&be&above&this&one&*/
&85&&&&&&&&&&&&&&&&&&&&/*&right&*/
&86&&&&&&&&&&&&&&&&&&&&loc&=&board[j][pos[i][3]]&-&'A';
&87&&&&&&&&&&&&&&&&&&&&if&(loc&!=&i)&/*&same&as&left&*/
&88&&&&&&&&&&&&&&&&&&&&&&above[loc][i]&=&1;
&89&&&&&&&&&&&&&&&&&&}
&90&&&&&&&&&&&&&&&&&&for&(int&j&=&pos[i][1];&j&&=&pos[i][3];&j++)&{&/*&check&top&and&bottom&*/
&92&&&&&&&&&&&&&&&&&&&&/*&top&*/
&93&&&&&&&&&&&&&&&&&&&&int&loc&=&board[pos[i][0]][j]&-&'A';
&94&&&&&&&&&&&&&&&&&&&&if&(loc&!=&i)
&95&&&&&&&&&&&&&&&&&&&&&&above[loc][i]&=&1;
&97&&&&&&&&&&&&&&&&&&&&/*&bottom&*/
&98&&&&&&&&&&&&&&&&&&&&loc&=&board[pos[i][2]][j]&-&'A';
&99&&&&&&&&&&&&&&&&&&&&if&(loc&!=&i)
100&&&&&&&&&&&&&&&&&&&&&&above[loc][i]&=&1;
101&&&&&&&&&&&&&&&&&&}
102&&&&&&&&&&&&&}
103&&&&&&&&&
104&&&&&&&&&findAnswer(0);
105&&&&&&&&&out.close();
106&&&&&&&&&System.exit(0);
杨磊 阅读(74) |
Principles of Modeling
First, The choice of what models to create has
a profound influence on how a problem is attacked and how a solution is
Second, Every model may be expressed at
different levels of precision.
Third, The best models are connected to
Fourth,No single model or view is sufficient.
Every nontrivial system is best approached through a small set of nearly
independent models with multiple viewpoints.
Three major elements:
the UML's basic building blocks
the rules that dictate
how those building blocks may be put together
some common mechanisms that
apply throughout the UML
The vocabulary of the UML encompasses three kinds of building blocks:
Relationships
Three kinds of relationships that are most important: dependencies, generalizations, and associations.
Dependencies are using relationships. For example, pipes depend on the water heater to heat the water they carry.
Associations are structural relationships among instances. For example, rooms consist of wa walls themselves may have embedd pipes may pass through walls.
Generalizations connect generalized classes to more-specialized ones in what is known as subclass/superclass or child/parent relationships. For example, a picture window is a kind of window with very large, a patio window is a kind of window with panes that open side to side.
杨磊 阅读(88) |
先自动下载了新的控件
然后去用这个文件去注册掉那个什么什么CAB
然后再去下载 xenroll.dll
去 cmd 运行 regsvr32 xenroll.dll
然后就可以了，就可以导入数字证书了。
杨磊 阅读(86) |
&&&& 摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)
/
-->&&1&import&java.io.*;
&&2&import&java.util.*;
&&n...&&
杨磊 阅读(115) |
速度提高了一倍啊，看来底层的东西还是有必要了解的，不过Java写东西是真方便啊
本来这道题是要高精度的，YD啊，但是Java有BigDecimal，哈哈，不过这玩意好用是好用，但是确实是非常的慢
我估计我自己用一个数组实现的话，速度应该还会快的
不过最后被我瞎猫碰死耗子碰到了，终于过了。
&1&import&java.io.*;
&2&import&java.math.BigI
&3&import&java.util.*;
&5&ID:&yanglei4
&6&LANG:&JAVA
&7&TASK:buylow
&9&public&class&buylow{
10&&&&&public&static&void&main(String[]&args)&throws&IOException&{
11&&&&&&&&&BufferedReader&f&=&new&BufferedReader(new&FileReader("buylow.in"));
12&&&&&&&&&PrintWriter&out&=&new&PrintWriter(new&BufferedWriter(new&FileWriter("buylow.out")));
13&&&&&&&&&int&N&=&Integer.parseInt(f.readLine());
14&&&&&&&&&int[]&D&=&new&int[N];
15&&&&&&&&&int&count&=&0;
16&&&&&&&&&String&temp&=&f.readLine();
17&&&&&&&&&while&(temp&!=&null)&{
18&&&&&&&&&&&&&StringTokenizer&st&=&new&StringTokenizer(temp);
19&&&&&&&&&&&&&int&len&=&st.countTokens();
20&&&&&&&&&&&&&for&(int&i&=&0;&i&&&&i++)
21&&&&&&&&&&&&&&&&&D[count++]&=&Integer.parseInt(st.nextToken());
22&&&&&&&&&&&&&temp&=&f.readLine();
23&&&&&&&&&}
24&&&&&&&&&long[]&lds&=&new&long[N];
25&&&&&&&&&BigInteger[]&cnt&=&new&BigInteger[N];
26&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)&{
27&&&&&&&&&&&&&&&&&lds[i]&=&1;
28&&&&&&&&&&&&&&&&&cnt[i]&=&new&BigInteger("1");
29&&&&&&&&&}
30&&&&&&&&&ArrayList&Integer&&exist&=&new&ArrayList&Integer&();
31&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)&{
32&&&&&&&&&&&&&
33&&&&&&&&&&&&&for&(int&j&=&i&-&1;&j&&=&0;&j--)&{
34&&&&&&&&&&&&&&&&&if&(D[i]&&&D[j])&{
35&&&&&&&&&&&&&&&&&&&&&if&(lds[j]&+&1&&&lds[i])&{
36&&&&&&&&&&&&&&&&&&&&&&&&&lds[i]&=&lds[j]&+&1;
37&&&&&&&&&&&&&&&&&&&&&&&&&exist.clear();
38&&&&&&&&&&&&&&&&&&&&&&&&&exist.add(D[j]);
39&&&&&&&&&&&&&&&&&&&&&&&&&cnt[i]&=&new&BigInteger(cnt[j].toByteArray());
40&&&&&&&&&&&&&&&&&&&&&}
41&&&&&&&&&&&&&&&&&&&&&else&if&(lds[j]&+&1&==&lds[i])&{
42&&&&&&&&&&&&&&&&&&&&&&&&&if&(!exist.contains(D[j]))&{
43&&&&&&&&&&&&&&&&&&&&&&&&&&&&&exist.add(D[j]);
44&&&&&&&&&&&&&&&&&&&&&&&&&&&&&cnt[i]&=&cnt[i].add(cnt[j]);
45&&&&&&&&&&&&&&&&&&&&&&&&&}
46&&&&&&&&&&&&&&&&&&&&&}
47&&&&&&&&&&&&&&&&&
48&&&&&&&&&&&&&&&&&}
49&&&&&&&&&&&&&}
50&&&&&&&&&}
51&&&&&&&&&
52&/*&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)
53&&&&&&&&&&&&&System.out.println(lds[i][0]&+&"&"&+&lds[i][1]&+&"&"&+&cnt[i]);*/
54&&&&&&&&&
55&&&&&&&&&long&maxleng&=&0;
56&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)&{
57&&&&&&&&&&&&&if&(maxleng&&&lds[i])
58&&&&&&&&&&&&&&&&&&&&&maxleng&=&lds[i];
59&&&&&&&&&}
60&&&&&&&&&BigInteger&sum&=&new&BigInteger("0");
61&&&&&&&&&exist&=&new&ArrayList&Integer&();&&&&&&&&
62&&&&&&&&&for&(int&i&=&N&-&1;&i&&=&0;&i--)&{
63&&&&&&&&&&&&&if&(lds[i]&==&maxleng)
64&&&&&&&&&&&&&&&&&if&(!exist.contains(D[i]))&{
65&&&&&&&&&&&&&&&&&&&&&sum&=&sum.add(cnt[i]);
66&&&&&&&&&&&&&&&&&&&&&exist.add(D[i]);
67&&&&&&&&&&&&&&&&&}
68&&&&&&&&&}
69&&&&&&&&&
70&&&&&&&&&out.println(maxleng&+&"&"&+&sum);
71&&&&&&&&&out.close();
72&&&&&&&&&System.exit(0);
就是红色的那个地方，用toString的话，最后一个点过不了，换成了这个就过了。
杨磊 阅读(2135) |
&1&&&if&(source&=&sink)
&2&&&&&totalflow&=&Infinity
&3&&&&&DONE&
&4&&&totalflow&=&0&
&5&&&while&(True)
&6&#&find&path&with&highest&capacity&from
&&&#&source&to&sink&
&7&#&uses&a&modified&djikstra's&algorithm
&8&&&&&for&all&nodes&i
&9&&&&&&&prevnode(i)&=&nil
10&&&&&&&flow(i)&=&0
11&&&&&&&visited(i)&=&False
12&&&&&flow(source)&=&infinity&
13&&&&&while&(True)
14&&&&&&&maxflow&=&0
15&&&&&&&maxloc&=&nil&
16&&&&&&&#&find&the&unvisited&node&with
&&&&&&&&&#&the&highest&capacity&to&it
17&&&&&&&for&all&nodes&i
18&&&&&&&&&if&(flow(i)&&&maxflow&AND
&&&&&&&&&&&&&&&&&&&&&&&&&&not&visited(i))
19&&&&&&&&&&&maxflow&=&flow(i)
20&&&&&&&&&&&maxloc&=&i
21&&&&&&&if&(maxloc&=&nil)
22&&&&&&&&&break&inner&while&loop
23&&&&&&&if&(maxloc&=&sink)
24&&&&&&&&&break&inner&while&loop
24a&&&&&&visited(maxloc)&=&true
25&&&&&&&#&update&its&neighbors
26&&&&&&&for&all&neighbors&i&of&maxloc
27&&&&&&&&&if&(flow(i)&&&min(maxflow,
&&&&&&&&&&&&&&&&&&&&&&capacity(maxloc,i)))
28&&&&&&&&&&&prevnode(i)&=&maxloc
29&&&&&&&&&&&flow(i)&=&min(maxflow,
&&&&&&&&&&&&&&&&&&&&capacity(maxloc,i))&
30&&&&&if&(maxloc&=&nil)&&&&&&&&&#&no&path
31&&&&&&&break&outer&while&loop&
32&&&&&pathcapacity&=&flow(sink)
33&&&&&totalflow&=&totalflow&+&pathcapacity&
&&&#&add&that&flow&to&the&network,
&&&#&update&capacity&appropriately
35&&&&&curnode&=&sink
&&&&&&&&&#&for&each&arc,&prevnode(curnode),
&&&&&&&&&#&curnode&on&path:
36&&&&&while&(curnode&!=&source)&&&&&&&
38&&&&&&&nextnode&=&prevnode(curnode)
39&&&&&&&capacity(nextnode,curnode)&=
&&&&&&&&&&&capacity(nextnode,curnode)&-&
40&&&&&&&&&&&&&&&&&&&&&&&&&&&pathcapacity
41&&&&&&&capacity(curnode,nextnode)&=
&&&&&&&&&&&capacity(curnode,nextnode)&+&
42&&&&&&&&&&&&&&&&&&&&&&&&&&&pathcapacity
43&&&&&&&curnode&=&nextnode
杨磊 阅读(87) |
喜欢的可以拿去用，欢迎提意见
之所以用黑色，就是因为foreground可以用更多的颜色，对比度高一点
而且经常看白色的背景色，好像对眼睛也是一种折磨。
杨磊 阅读(1689) |
第一次用Java代码过搜索+剪枝的题目啊，不容易啊……，而且还是参考了后面的Analysis，-_-!
不过里面的那个Hash的剪枝还是很强大的，再一次说明了学好数学的重要
同时，再一次证明了Java有多慢，C++肯定不用加最后的剪枝就过了，但是Java就不行
而且有一个点居然要1.5秒，真是不可思议。
待会儿我再试试Analysis里面的代码，看看有多快，是不是Static的要比正常的写快。
算法没啥好说的，就是生成，把F+R个数生成出来，然后用那个最大ratio是最小ratio的三倍做一个剪枝
我之前还打了一个表，所有的数的ratio的表，然后后面直接访问这个表，而不是去现去除
但是发现好像左右不大。
剩下的就是那个Hash的优化了，很强大，就好象题目里说的那样，就是看F生成好之后的比率
比如1 3 5 7，前两个是F的，后两个是R的，那么它的variance和2 6 10 14是一样的，这个不用我解释吧
这样的话呢，同一个比率的就不用再做第二次了。
自己没有去严格的证明这个剪枝的正确性，但是想想证明应该不太难。
同一个ratio的话肯定取前面那组，如果是不同的ratio呢？
现在的问题就是，如果是不同的ratio，后面的正确的组会不会被前面的不小心剪掉。或者后面的这组根本没必要。
如果是根本没必要的话，那么这个剪枝肯定就是正确的了。
其实这个剪枝是正确的，因为在你用比如1，3的时候，你就试过了后面所有的不同组合了。
那么当你扩大1，3到2，6时，我们可以看看USACO后面的解释的那个例子来。
39/16 = 2.
40/16 = 2.
39/15 = 2.
40/15 = 2.
39/14 = 2.
40/14 = 2.
39/13 = 3.
40/13 = 3.
39/12 = 3.
40/12 = 3.
就相当于这些ratio全都翻了一倍，那样的话，variance当然不会变
所以个剪枝是正确的。
贴一下代码：
&&1&import&java.io.*;
&&2&import&java.util.*;
&&4&ID:&yanglei4
&&5&LANG:&JAVA
&&6&TASK:cowcycle
&&8&public&class&cowcycle{
&&9&&&&&public&double[][]&ratio&=&new&double[81][41];
&10&&&&&int&F,R,F1,F2,R1,R2;
&11&&&&&public&int[]&s1;
&12&&&&&public&int[]&s2;
&13&&&&&double&min&=&1000000;
&14&&&&&static&String[]&
&15&&&&&public&int[]&ans1;
&16&&&&&public&int[]&ans2;
&18&&&&&public&static&boolean&contains(String&str)&{
&19&&&&&&&&&int&num&=&str.hashCode();
&20&&&&&&&&&if(num&0)&num&=&-
&21&&&&&&&&&int&p&=&num&%&hash.
&22&&&&&&&&&while(hash[p]!=null)
&23&&&&&&&&&&&&&if(str.equals(hash[p]))&&&return&true;
&24&&&&&&&&&&&&&else&if(p==hash.length-1)&p=0;
&25&&&&&&&&&&&&&else&p++;
&26&&&&&&&&&hash[p]=
&27&&&&&&&&&return&false;
&30&&&&&public&void&DFS_F(int&step,int&start)&{
&31&&&&&&&&&if&(step&==&F&+&1)&{
&32&&&&&&&&&&&&&StringBuffer&str&=&new&StringBuffer();
&33&&&&&&&&&&&&&for(int&i&=&2;i&&=&F;i++)
&34&&&&&&&&&&&&&&&&&str.append((int)(100*(double)s1[i]/s1[1]));
&35&&&&&&&&&&&&&if(contains(str.toString()))&return;
&36&&&&&&&&&&&&&
&37&&&&&&&&&&&&&DFS_R(1,R1);
&38&&&&&&&&&&&&&return;
&39&&&&&&&&&}
&40&&&&&&&&&for&(int&i&=&&i&&=&F2&-&(F&-&step);&i++)&{
&41&&&&&&&&&&&&&s1[step]&=&i;
&42&&&&&&&&&&&&&DFS_F(step&+&1,&i&+&1);
&43&&&&&&&&&}
&46&&&&&public&void&DFS_R(int&step,int&start)&{
&47&&&&&&&&&if&(step&==&R&+&1)&{
&48&&&&&&&&&&&&&if&(s1[F]&*&s2[R]&&&3&*&s1[1]&*&s2[1])
&49&&&&&&&&&&&&&&&&&return;
&50&&&&&&&&&&&&&count();
&51&&&&&&&&&&&&&return;
&52&&&&&&&&&}
&53&&&&&&&&&for&(int&i&=&&i&&=&R2&-&(R&-&step);&i++)&{
&54&&&&&&&&&&&&&s2[step]&=&i;
&55&&&&&&&&&&&&&DFS_R(step&+&1,&i&+&1);
&56&&&&&&&&&}&&&&&&&&
&59&&&&&public&double&count()&{
&60&&&&&&&&&double[]&rate&=&new&double[R&*&F&+&1];
&61&&&&&&&&&double[]&diff&=&new&double[R&*&F&+&1];
&62&&&&&&&&&double&sum&=&0;
&63&&&&&&&&&double&sumf&=&0;
&64&&&&&&&&&int&l&=&1;
&65&&&&&&&&&for&(int&i&=&1;&i&&=&F;&i++)
&66&&&&&&&&&&&&&for&(int&j&=&1;&j&&=&R;&j++)&
&67&&&&&&&&&&&&&&&&&rate[l++]&=&ratio[s1[i]][s2[j]];
&69&&&&&&&&&Arrays.sort(rate);
&70&&&&&&&&&
&71&&&&&&&&&for&(int&i&=&1;&i&&=&F&*&R&-&1;&i++)&{
&72&&&&&&&&&&&&&diff[i]&=&rate[i&+&1]&-&rate[i];
&73&&&&&&&&&&&&&sum&+=&diff[i];
&74&&&&&&&&&&&&&sumf&+=&diff[i]&*&diff[i];
&75&&&&&&&&&}
&76&&&&&&&&&double&avg&=&sum&/&(F&*&R&-&1);
&77&&&&&&&&&double&vf&=&sumf&-&sum&*&
&78&&&&&&&&&if&(vf&&&min)&{
&79&&&&&&&&&&&&&min&=&
&80&&&&&&&&&&&&&for&(int&i&=&1;&i&&=&F;&i++)&ans1[i]&=&s1[i];
&81&&&&&&&&&&&&&for&(int&i&=&1;&i&&=&R;&i++)&ans2[i]&=&s2[i];
&82&&&&&&&&&}
&83&&&&&&&&&return&0.0;
&86&&&&&public&void&done()&throws&IOException&{
&87&&&&&&&&&for&(int&i&=&25;&i&&=&80;&i++)
&88&&&&&&&&&&&&&for&(int&j&=&5;&j&&=&40;&j++)&
&89&&&&&&&&&&&&&&&&&ratio[i][j]&=&(double)i&/&j;
&91&&&&&&&&&BufferedReader&f&=&new&BufferedReader(new&FileReader("cowcycle.in"));
&92&&&&&&&&&PrintWriter&out&=&new&PrintWriter(new&BufferedWriter(new&FileWriter("cowcycle.out")));
&93&&&&&&&&&StringTokenizer&st&=&new&StringTokenizer(f.readLine());
&94&&&&&&&&&F&=&Integer.parseInt(st.nextToken());
&95&&&&&&&&&R&=&Integer.parseInt(st.nextToken());
&96&&&&&&&&&st&=&new&StringTokenizer(f.readLine());
&97&&&&&&&&&F1&=&Integer.parseInt(st.nextToken());
&98&&&&&&&&&F2&=&Integer.parseInt(st.nextToken());
&99&&&&&&&&&R1&=&Integer.parseInt(st.nextToken());
100&&&&&&&&&R2&=&Integer.parseInt(st.nextToken());
101&&&&&&&&&s1&=&new&int[F&+&1];
102&&&&&&&&&s2&=&new&int[R&+&1];
103&&&&&&&&&ans1&=&new&int[F&+&1];
104&&&&&&&&&ans2&=&new&int[R&+&1];
105&&&&&&&&&hash&=&new&String[50003];
106&&&&&&&&&
107&&&&&&&&&DFS_F(1,F1);
108&&&&&&&&&
109&&&&&&&&&for&(int&i&=&1;&i&&=&F&-&1;&i++)
110&&&&&&&&&&&&&out.print(ans1[i]&+&"&");
111&&&&&&&&&out.println(ans1[F]);
113&&&&&&&&&for&(int&i&=&1;&i&&=&R&-&1;&i++)
114&&&&&&&&&&&&&out.print(ans2[i]&+&"&");
115&&&&&&&&&out.println(ans2[R]);
116&&&&&&&&&&&&&&&&&
117&&&&&&&&&out.close();
120&&&&&public&static&void&main(String[]&args)&throws&IOException&{
121&&&&&&&&&cowcycle&t&=&new&cowcycle();
122&&&&&&&&&t.done();
123&&&&&&&&&System.exit(0);
杨磊 阅读(59) |
不明白为什么一模一样的算法，Java的结果就是不对呢，很奇怪
又是一个剪枝的题目，我发现剪枝这东西真是需要灵感的
那个不会改变的字符串的剪枝比较容易想，不过Hash的那个剪枝确实是让我爱莫能及啊，然后就参考了Leokan的代码
很神奇的代码，Hash Size只有3W+，然后居然就AC了，我最后就是用他的代码试了一下 -_-!，然后AC的
可是为什么我的Java代码就是过不了呢？很神奇
在第七个点的时候，Hash Size要开到50W才可以出正确的结果，但是这样的话时间会超长，估计有4，5秒的样子
而且我把能加的剪枝全加上了，还是不行……
真是不明白所以啊，不知道自己问题处在哪里了。
太TM诡异了……
杨磊 阅读(80) |
/blog/string-hash-compare/
常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。
常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。
其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与
1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与(更大素数)求模后存储到线性表中冲突的个数。
经过比较，得出以上平均得分。平均数为平方平均数。可以发现，BKDRHash无论是在实际效果还是编码实现中，效果都是最突出的。APHash也
是较为优秀的算法。DJBHash,JSHash,RSHash与SDBMHash各有千秋。PJWHash与ELFHash效果最差，但得分相似，其算
法本质是相似的。
在信息修竞赛中，要本着易于编码调试的原则，个人认为BKDRHash是最适合记忆和使用的。。
附：各种哈希函数的C语言程序代码
unsigned&int&SDBMHash(char&*str)
unsigned&int&hash&=&0;
while&(*str)
//&equivalent&to:&hash&=&65599*hash&+&(*str++);
hash&=&(*str++)&+&(hash&&&&6)&+&(hash&&&&16)&-&
return&(hash&&&0x7FFFFFFF);
//&RS&Hash&Function
unsigned&int&RSHash(char&*str)
unsigned&int&b&=&378551;
unsigned&int&a&=&63689;
unsigned&int&hash&=&0;
while&(*str)
hash&=&hash&*&a&+&(*str++);
return&(hash&&&0x7FFFFFFF);
//&JS&Hash&Function
unsigned&int&JSHash(char&*str)
unsigned&int&hash&=&;
while&(*str)
hash&^=&((hash&&&&5)&+&(*str++)&+&(hash&&&&2));
return&(hash&&&0x7FFFFFFF);
//&P.&J.&Weinberger&Hash&Function
unsigned&int&PJWHash(char&*str)
unsigned&int&BitsInUnignedInt&=&(unsigned&int)(sizeof(unsigned&int)&*&8);
unsigned&int&ThreeQuarters&&&&=&(unsigned&int)((BitsInUnignedInt&&*&3)&/&4);
unsigned&int&OneEighth&&&&&&&&=&(unsigned&int)(BitsInUnignedInt&/&8);
unsigned&int&HighBits&&&&&&&&&=&(unsigned&int)(0xFFFFFFFF)&&&&(BitsInUnignedInt&-&OneEighth);
unsigned&int&hash&&&&&&&&&&&&&=&0;
unsigned&int&test&&&&&&&&&&&&&=&0;
while&(*str)
hash&=&(hash&&&&OneEighth)&+&(*str++);
if&((test&=&hash&&&HighBits)&!=&0)
hash&=&((hash&^&(test&&&&ThreeQuarters))&&&(~HighBits));
return&(hash&&&0x7FFFFFFF);
//&ELF&Hash&Function
unsigned&int&ELFHash(char&*str)
unsigned&int&hash&=&0;
unsigned&int&x&&&&=&0;
while&(*str)
hash&=&(hash&&&&4)&+&(*str++);
if&((x&=&hash&&&0xF0000000L)&!=&0)
hash&^=&(x&&&&24);
hash&&=&~x;
return&(hash&&&0x7FFFFFFF);
//&BKDR&Hash&Function
unsigned&int&BKDRHash(char&*str)
unsigned&int&seed&=&131;&//&31&131&&131313&etc..
unsigned&int&hash&=&0;
while&(*str)
hash&=&hash&*&seed&+&(*str++);
return&(hash&&&0x7FFFFFFF);
//&DJB&Hash&Function
unsigned&int&DJBHash(char&*str)
unsigned&int&hash&=&5381;
while&(*str)
hash&+=&(hash&&&&5)&+&(*str++);
return&(hash&&&0x7FFFFFFF);
//&AP&Hash&Function
unsigned&int&APHash(char&*str)
unsigned&int&hash&=&0;
for&(i=0;&*&i++)
if&((i&&&1)&==&0)
hash&^=&((hash&&&&7)&^&(*str++)&^&(hash&&&&3));
hash&^=&(~((hash&&&&11)&^&(*str++)&^&(hash&&&&5)));
return&(hash&&&0x7FFFFFFF);
杨磊 阅读(457) |
今天在Lab想连一下MySQL的数据库，因为电脑不知道什么时候被人关掉了
今天又被我开起来了，之前连的都好好的，我也没做过什么特殊的处理
大概就是刚刚装好的时候，security的那个check一直过不了，然后我就搞来搞去弄了什么权限的东西
我自己都记不得是什么指令了，但是其实还是我对数据库这东西不熟悉，只懂一点点的简单的SQL
然后今天就发现连不上了，Error Number 1130，于是我去Google一下，发现这个是远程root用户没有权限的问题
原来root用户只有本地的权限，需要手动将远程的权限打开，尝试了好几种方法，最后还是下面这种方法管用
&在安装mysql的机器上运行：
1、d:"mysql"bin"&mysql -h localhost -u root
//这样应该可以进入MySQL服务器
2、mysql&GRANT ALL PRIVILEGES ON *.* TO 'root'@'%' WITH GRANT OPTION
//赋予任何主机访问数据的权限
3、mysql&FLUSH PRIVILEGES
//修改生效
4、mysql&EXIT
//退出MySQL服务器
想懂很多东西。
杨磊 阅读(1312) |
Fence Rails
一道感觉很不错的搜索+剪枝的题目，当然剪枝策略我是参考来的，我自己想到的都是小剪枝
然后我自己用Java实现了，结果发现……，这速度啊，真让我郁闷，居然在第四个点就超时了
但是同样的算法用C++实现的代码，快了100+倍。
难怪现在还有这么多人在搞C++，也难怪有人批评说Java速度慢，还有些人在反驳
事实却是如此啊。
代码贴一下吧，TLE的，如果有人愿意的话，可以转成C++用就行了
其实我是想能不能再改进改进，让它用Java也能过，但是感觉很难，我已经想不出更好的剪枝的办法了
或者另外一个方法就是空间换时间，但是感觉已经没什么好换的了，该开的数组都开了。
&1&import&java.io.*;
&2&import&java.util.*;
&4&ID:&yanglei4
&5&LANG:&JAVA
&6&TASK:fence8
&8&public&class&fence8{
&9&&&&&int&wastemax&=&0;
10&&&&&int&
11&&&&&int&N,R;
12&&&&&int[]&
13&&&&&int[]&
14&&&&&int[]&from&=&new&int[1100];
15&&&&&PrintWriter&
17&&&&&public&void&dfs(int&k,&int&waste)&{
18&&&&&&&&&if&(k&&&0)&{
19&&&&&&&&&&&&&out.println(ans&+&1);
20&&&&&&&&&&&&&out.close();
21&&&&&&&&&&&&&System.exit(0);&&&&&&&&&&&&
22&&&&&&&&&}
23&&&&&&&&&int&i;
24&&&&&&&&&if(k&!=&ans&&&&rails[k]&==&rails[k&+&1])&i&=&from[k&+&1];&
25&&&&&&&&&else&i&=&0;
26&&&&&&&&&
27&&&&&&&&&for&(i&=&0;&i&&&N;&i++)&{
28&&&&&&&&&&&&&if&(remain[i]&&=&rails[k])&{
29&&&&&&&&&&&&&&&&&
30&&&&&&&&&&&&&&&&&from[k]&=&i;
31&&&&&&&&&&&&&&&&&remain[i]&-=&rails[k];
32&&&&&&&&&&&&&&&&&if&(remain[i]&&&rails[0])&waste&+=&remain[i];
33&&&&&&&&&&&&&&&&&if&(waste&&&wastemax)&{
34&&&&&&&&&&&&&&&&&&&&&waste&-=&remain[i];
35&&&&&&&&&&&&&&&&&&&&&remain[i]&+=&rails[k];
36&&&&&&&&&&&&&&&&&&&&&continue;
37&&&&&&&&&&&&&&&&&}
38&&&&&&&&&&&&&&&&&dfs(k&-&1,&waste);
39&&&&&&&&&&&&&&&&&remain[i]&+=&rails[k];
40&&&&&&&&&&&&&}
41&&&&&&&&&}
44&&&&&public&void&done()&throws&IOException&{
45&&&&&&&&&BufferedReader&f&=&new&BufferedReader(new&FileReader("fence8.in"));
46&&&&&&&&&out&=&new&PrintWriter(new&BufferedWriter(new&FileWriter("fence8.out")));
47&&&&&&&&&//Read&the&boards
48&&&&&&&&&N&=&Integer.parseInt(f.readLine());
49&&&&&&&&&int[]&boards&=&new&int[N];
50&&&&&&&&&int&boardSum&=&0;
51&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)&
52&&&&&&&&&&&&&{
53&&&&&&&&&&&&&&&&&boards[i]&=&Integer.parseInt(f.readLine());
54&&&&&&&&&&&&&&&&&boardSum&+=&boards[i];
55&&&&&&&&&&&&&}
56&&&&&&&&&Arrays.sort(boards);
57&&&&&&&&&
58&&&&&&&&&remain&=&new&int[N];
59&&&&&&&&&for&(int&i&=&N&-&1;&i&&=&0;&i--)&remain[i]&=&boards[i];
60&&&&&&&&&
61&&&&&&&&&//&Read&the&rails
62&&&&&&&&&R&=&Integer.parseInt(f.readLine());
63&&&&&&&&&rails&=&new&int[R];
64&&&&&&&&&int&railSum&=&0;
65&&&&&&&&&for&(int&i&=&0;&i&&&R;&i++)
66&&&&&&&&&&&&&rails[i]&=&Integer.parseInt(f.readLine());&&&&&&&&
67&&&&&&&&&Arrays.sort(rails);
68&&&&&&&&&
69&&&&&&&&&int&i;
70&&&&&&&&&for&(i&=&0;&i&&&R;&i++)&{
71&&&&&&&&&&&&&if&(railSum&+&rails[i]&&&boardSum)&
72&&&&&&&&&&&&&&&&&break;
73&&&&&&&&&&&&&railSum&+=&rails[i];
74&&&&&&&&&}
75&&&&&&&&&int&k&=&i&-&1;
76&&&&&&&&&//Try&every&possible&number
77&&&&&&&&&for&(i&=&k;&k&&=&0;&i--)&{
78&&&&&&&&&&&&&ans&=&i;
79&&&&&&&&&&&&&wastemax&=&boardSum&-&railS
80&&&&&&&&&&&&&railSum&-=&rails[i];
81&&&&&&&&&&&&&dfs(i,0);
82&&&&&&&&&}
83&&&&&&&&&out.println(0);
84&&&&&&&&&out.close();&&&&
86&&&&&public&static&void&main(String[]&args)&throws&IOException&{
87&&&&&&&&&fence8&t&=&new&fence8();
88&&&&&&&&&t.done();
89&&&&&&&&&System.exit(0);
杨磊 阅读(83) |
杨磊 阅读(69) |
&&&& 摘要: Code highlighting produced by Actipro CodeHighlighter (freeware)
/
-->&&1&import&java.io.*;
&&2&import&java.util.*;
&&n...&&
杨磊 阅读(66) |
妈了个头！！
杨磊 阅读(115) |
等老子学好了J2EE，俺也要自己写一个blog程序
杨磊 阅读(48) |
真的可以用天差地别来形容啊，基本上差一个数量级
所以现在对C++还是有点留恋的，不舍得完全放弃掉
其实能把C++这么灵活的语言运用的灵活的程序员才是真正有水平的
而且C++在组织很多数据结构上确实比Java要舒服一点
可能是因为C++毕竟是从面向过程的C扩展而来的吧
不知道我这种说话会不会被人喷……
有空还是捡一下C++吧
杨磊 阅读(206) |
&1&#&circuit&is&a&global&array
&2&&&&find_euler_circuit
&3&&&&&&circuitpos&=&0
&4&&&&&&find_circuit(node&1)
&6&#&nextnode&and&visited&is&a&local&array
&7&#&the&path&will&be&found&in&reverse&order
&8&&&find_circuit(node&i)
10&&&&&if&node&i&has&no&neighbors&then
11&&&&&&&circuit(circuitpos)&=&node&i
12&&&&&&&circuitpos&=&circuitpos&+&1
13&&&&&else
14&&&&&&&while&(node&i&has&neighbors)
15&&&&&&&&&&&pick&a&random&neighbor&node&j&of&node&i
16&&&&&&&&&&&delete_edges&(node&j,&node&i)
17&&&&&&&&&&&find_circuit&(node&j)
18&&&&&&&circuit(circuitpos)&=&node&i
19&&&&&&&circuitpos&=&circuitpos&+&1
杨磊 阅读(73) |
&1&unsigned&long&cantor(unsigned&long&S)
&3&&&&&long&x=0,i,p,k,j;
&4&&&&&bool&hash[8]={false};
&5&&&&&for&(i=8;i&=2;i--)
&7&&&&&&&&&k=S&&&3*(i-1);
&8&&&&&&&&&S-=k&&3*(i-1);
&9&&&&&&&&&hash[k]=true;
10&&&&&&&&&p=k;
11&&&&&&&&&for&(j=0;j&=k-1;j++)
12&&&&&&&&&&&&&if&(hash[j])
13&&&&&&&&&&&&&&&&&p--;
14&&&&&&&&&x+=fac[i-1]*p;&//fac存的是阶乘&fac[1]&=&1,&fac[2]&=&2,&fac[3]&=&6
16&&&&&return&x;
其实就是求全排列中，某一个排列的序号
比如321，对应1，2，3的全排列的第6号
上面这个是8禁止存储的，有利于位操作
杨磊 阅读(79) |
/animation.php?t=Bellman-Ford_algorithm
&1&procedure&BellmanFord(list&vertices,&list&edges,&vertex&source)
&2&&&&//&This&implementation&takes&in&a&graph,&represented&as&lists&of&vertices
&3&&&&//&and&edges,&and&modifies&the&vertices&so&that&their&distance&and
&4&&&&//&predecessor&attributes&store&the&shortest&paths.
&6&&&&//&Step&1:&Initialize&graph
&7&&&&for&each&vertex&v&in&vertices:
&8&&&&&&&&if&v&is&source&then&v.distance&:=&0
&9&&&&&&&&else&v.distance&:=&infinity
10&&&&&&&&v.predecessor&:=&null
12&&&&//&Step&2:&relax&edges&repeatedly
13&&&&for&i&from&1&to&size(vertices)-1:&&&&&&&
14&&&&&&&&for&each&edge&uv&in&edges:&//&uv&is&the&edge&from&u&to&v
15&&&&&&&&&&&&u&:=&uv.source
16&&&&&&&&&&&&v&:=&uv.destination&&&&&&&&&&&&&
17&&&&&&&&&&&&if&v.distance&&&u.distance&+&uv.weight:
18&&&&&&&&&&&&&&&&v.distance&:=&u.distance&+&uv.weight
19&&&&&&&&&&&&&&&&v.predecessor&:=&u
21&&&&//&Step&3:&check&for&negative-weight&cycles
22&&&&for&each&edge&uv&in&edges:
23&&&&&&&&u&:=&uv.source
24&&&&&&&&v&:=&uv.destination
25&&&&&&&&if&v.distance&&&u.distance&+&uv.weight:
26&&&&&&&&&&&&error&"Graph&contains&a&negative-weight&cycle"
An implementation from wiki
&1&#include&&limits.h&
&2&#include&&stdio.h&
&3&#include&&stdlib.h&
&5&/*&Let&INFINITY&be&an&integer&value&not&likely&to&be
&6&&&&confused&with&a&real&weight,&even&a&negative&one.&*/
&7&#define&INFINITY&((1&&&&14)-1)
&9&typedef&struct&{
10&&&&&int&
11&&&&&int&
12&&&&&int&
15&void&BellmanFord(Edge&edges[],&int&edgecount,&int&nodecount,&int&source)
17&&&&&int&*distance&=&malloc(nodecount&*&sizeof&*distance);
18&&&&&int&i,&j;
20&&&&&for&(i=0;&i&&&&++i)
21&&&&&&&distance[i]&=&INFINITY;
22&&&&&distance[source]&=&0;
24&&&&&for&(i=0;&i&&&&++i)&{
25&&&&&&&&int&somethingchanged&=&0;&
26&&&&&&&&for&(j=0;&j&&&&++j)&{
27&&&&&&&&&&&&&if&(distance[edges[j].source]&!=&INFINITY)&{
28&&&&&&&&&&&&&&&&&int&new_distance&=&distance[edges[j].source]&+&edges[j].
29&&&&&&&&&&&&&&&&&if&(new_distance&&&distance[edges[j].dest])&{
30&&&&&&&&&&&&&&&&&&&distance[edges[j].dest]&=&new_
31&&&&&&&&&&&&&&&&&&&somethingchanged&=&1;
32&&&&&&&&&&&&&&&&&}&
33&&&&&&&&&&&&&}
34&&&&&&&&&}
35&&&&&&&&&/*&if&one&iteration&had&no&effect,&further&iterations&will&have&no&effect&either&*/
36&&&&&&&&&if&(!somethingchanged)&break;
39&&&&&for&(i=0;&i&&&&++i)&{
40&&&&&&&&&if&(distance[edges[i].dest]&&&distance[edges[i].source]&+&edges[i].weight)&{
41&&&&&&&&&&&&&puts("Negative&edge&weight&cycles&detected!");
42&&&&&&&&&&&&&free(distance);
43&&&&&&&&&&&&&return;
44&&&&&&&&&}
47&&&&&for&(i=0;&i&&&&++i)&{
48&&&&&&&&&printf("The&shortest&distance&between&nodes&%d&and&%d&is&%d\n",
49&&&&&&&&&&&&&source,&i,&distance[i]);
52&&&&&free(distance);
53&&&&&return;
56&int&main(void)
58&&&&&/*&This&test&case&should&produce&the&distances&2,&4,&7,&-2,&and&0.&*/
59&&&&&Edge&edges[10]&=&{{0,1,&5},&{0,2,&8},&{0,3,&-4},&{1,0,&-2},
60&&&&&&&&&&&&&&&&&&&&&&&{2,1,&-3},&{2,3,&9},&{3,1,&7},&{3,4,&2},
61&&&&&&&&&&&&&&&&&&&&&&&{4,0,&6},&{4,2,&7}};
62&&&&&BellmanFord(edges,&10,&5,&4);
63&&&&&return&0;
杨磊 阅读(152) |
&&1&/*************************************************************************
&&2&&*&&Compilation:&&javac&QuickSort.java
&&3&&*&&Execution:&&&&java&QuickSort&N
&&5&&*&&Generate&N&random&real&numbers&between&0&and&1&and&quicksort&them.
&&7&&*&&On&average,&this&quicksort&algorithm&runs&in&time&proportional&to
&&8&&*&&N&log&N,&independent&of&the&input&distribution.&The&algorithm
&&9&&*&&guards&against&the&worst-case&by&randomly&shuffling&the&elements
&10&&*&&before&sorting.&In&addition,&it&uses&Sedgewick's&partitioning
&11&&*&&method&which&stops&on&equal&keys.&This&protects&against&cases
&12&&*&&that&make&many&textbook&implementations,&even&randomized&ones,
&13&&*&&go&quadratic&(e.g.,&all&keys&are&the&same).
&15&&*************************************************************************/
&17&public&class&QuickSort&{
&18&&&&&private&static&long&comparisons&=&0;
&19&&&&&private&static&long&exchanges&&&=&0;
&21&&&&/***********************************************************************
&22&&&&&*&&Quicksort&code&from&Sedgewick&7.1,&7.2.
&23&&&&&***********************************************************************/
&24&&&&&public&static&void&quicksort(double[]&a)&{
&25&&&&&&&&&shuffle(a);&&&&&&&&&&&&&&&&&&&&&&&&//&to&guard&against&worst-case
&26&&&&&&&&&quicksort(a,&0,&a.length&-&1);
&29&&&&&//&quicksort&a[left]&to&a[right]
&30&&&&&public&static&void&quicksort(double[]&a,&int&left,&int&right)&{
&31&&&&&&&&&if&(right&&=&left)&return;
&32&&&&&&&&&int&i&=&partition(a,&left,&right);
&33&&&&&&&&&quicksort(a,&left,&i-1);
&34&&&&&&&&&quicksort(a,&i+1,&right);
&37&&&&&//&partition&a[left]&to&a[right],&assumes&left&&&right
&38&&&&&private&static&int&partition(double[]&a,&int&left,&int&right)&{
&39&&&&&&&&&int&i&=&left&-&1;
&40&&&&&&&&&int&j&=&
&41&&&&&&&&&while&(true)&{
&42&&&&&&&&&&&&&while&(less(a[++i],&a[right]))&&&&&&//&find&item&on&left&to&swap
&43&&&&&&&&&&&&&&&&&;&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&//&a[right]&acts&as&sentinel
&44&&&&&&&&&&&&&while&(less(a[right],&a[--j]))&&&&&&//&find&item&on&right&to&swap
&45&&&&&&&&&&&&&&&&&if&(j&==&left)&break;&&&&&&&&&&&//&don't&go&out-of-bounds
&46&&&&&&&&&&&&&if&(i&&=&j)&break;&&&&&&&&&&&&&&&&&&//&check&if&pointers&cross
&47&&&&&&&&&&&&&exch(a,&i,&j);&&&&&&&&&&&&&&&&&&&&&&//&swap&two&elements&into&place
&48&&&&&&&&&}
&49&&&&&&&&&exch(a,&i,&right);&&&&&&&&&&&&&&&&&&&&&&//&swap&with&partition&element
&50&&&&&&&&&return&i;
&53&&&&&//&is&x&&&y&?
&54&&&&&private&static&boolean&less(double&x,&double&y)&{
&55&&&&&&&&&comparisons++;
&56&&&&&&&&&return&(x&&&y);
&59&&&&&//&exchange&a[i]&and&a[j]
&60&&&&&private&static&void&exch(double[]&a,&int&i,&int&j)&{
&61&&&&&&&&&exchanges++;
&62&&&&&&&&&double&swap&=&a[i];
&63&&&&&&&&&a[i]&=&a[j];
&64&&&&&&&&&a[j]&=&
&67&&&&&//&shuffle&the&array&a[]
&68&&&&&private&static&void&shuffle(double[]&a)&{
&69&&&&&&&&&int&N&=&a.
&70&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)&{
&71&&&&&&&&&&&&&int&r&=&i&+&(int)&(Math.random()&*&(N-i));&&&//&between&i&and&N-1
&72&&&&&&&&&&&&&exch(a,&i,&r);
&73&&&&&&&&&}
&78&&&&&//&test&client
&79&&&&&public&static&void&main(String[]&args)&{
&80&&&&&&&&&int&N&=&Integer.parseInt(args[0]);
&82&&&&&&&&&//&generate&N&random&real&numbers&between&0&and&1
&83&&&&&&&&&long&start&=&System.currentTimeMillis();
&84&&&&&&&&&double[]&a&=&new&double[N];
&85&&&&&&&&&for&(int&i&=&0;&i&&&N;&i++)
&86&&&&&&&&&&&&&a[i]&=&Math.random();
&87&&&&&&&&&long&stop&=&System.currentTimeMillis();
&88&&&&&&&&&double&elapsed&=&(stop&-&start)&/&1000.0;
&89&&&&&&&&&System.out.println("Generating&input:&&"&+&elapsed&+&"&seconds");
&91&&&&&&&&&//&sort&them
&92&&&&&&&&&start&=&System.currentTimeMillis();
&93&&&&&&&&&quicksort(a);
&94&&&&&&&&&stop&=&System.currentTimeMillis();
&95&&&&&&&&&elapsed&=&(stop&-&start)&/&1000.0;
&96&&&&&&&&&System.out.println("Quicksort:&&&"&+&elapsed&+&"&seconds");
&98&&&&&&&&&//&print&statistics
&99&&&&&&&&&System.out.println("Comparisons:&"&+&comparisons);
100&&&&&&&&&System.out.println("Exchanges:&&&"&+&exchanges);
杨磊 阅读(75) |
&&#&distance(j)&is&distance&from&tree&to&node&j
&&#&source(j)&is&which&node&of&so-far&connected&MST
&&#&&&&&&&&&&&&&&&&&&&&&&is&closest&to&node&j
&1&&&For&all&nodes&i
&2&&&&&distance(i)&=&infinity&&&&&&&&#&no&connections
&3&&&&&intree(i)&=&False&&&&&&&&&&&&&#&no&nodes&in&tree
&4&&&&&source(i)&=&nil&
&5&&&treesize&=&1&&&&&&&&&&&&&&&&&&&&#&add&node&1&to&tree
&6&&&treecost&=&0&&&&&&&&&&&&&&&&&&&
&7&&&intree(1)&=&True
&8&&&For&all&neighbors&j&of&node&1&&&#&update&distances
&9&&&&&&distance(j)&=&weight(1,j)
10&&&&&source(j)&=&1&
11&&&while&(treesize&&&graphsize)
12&&&&&find&node&with&minimum&distance&to&&call&it&node&i
13&&&&&assert&(distance(i)&!=&infinity,&"Graph&Is&Not&Connected")&
&&&&#&add&edge&source(i),i&to&MST
14&&&&&treesize&=&treesize&+&1
15&&&&&treecost&=&treecost&+&distance(i)
16&&&&&intree(i)&=&True&&&&&&&&&&&&&&#&mark&node&i&as&in&tree&
&&&&#&update&distance&after&node&i&added
17&&&&&for&all&neighbors&j&of&node&i
18&&&&&&&if&(distance(j)&&&weight(i,j))
19&&&&&&&&&distance(j)&=&weight(i,j)
20&&&&&&&&&source(j)&=&i
杨磊 阅读(63) |
&&&& 摘要: 留个纪念吧
Code highlighting produced by Actipro CodeHighlighter (freeware)
/
-->&&1&import&java.io.*;
&&2&import&java.util...&&
杨磊 阅读(106) |
#&distance(j)&is&distance&from&source&vertex&to&vertex&j
#&parent(j)&is&the&vertex&that&precedes&vertex&j&in&any&shortest&path
#&&&&&&&&&&&&&&&&&&(to&reconstruct&the&path&subsequently)&
&1&For&all&nodes&i
&2&&&&&distance(i)&=&infinity&&&&&&&&&&#&not&reachable&yet
&3&&&&&visited(i)&=&False
&4&&&&&parent(i)&=&nil&#&no&path&to&vertex&yet&
&5&distance(source)&=&0&#&source&-&&source&is&start&of&all&paths
&6&parent(source)&=&nil
&7&&&8&while&(nodesvisited&&&graphsize)
&9&&&&&find&unvisited&vertex&with&min&distance&to&&call&it&vertex&i
10&&&&&assert&(distance(i)&!=&infinity,&"Graph&is&not&connected")&
11&&&&&visited(i)&=&True&#&mark&vertex&i&as&visited&
&&&&#&update&distances&of&neighbors&of&i
12&&&&&For&all&neighbors&j&of&vertex&i
13&&&&&&&&&if&distance(i)&+&weight(i,j)&&&distance(j)&then
14&&&&&&&&&&&&&distance(j)&=&distance(i)&+&weight(i,j)
15&&&&&&&&&&&&&parent(j)&=&i
#&dist(i,j)&is&"best"&distance&so&far&from&vertex&i&to&vertex&j&
#&Start&with&all&single&edge&paths.
For&i&=&1&to&n&do
&&&&For&j&=&1&to&n&do
&&&&&&&&dist(i,j)&=&weight(i,j)&
For&k&=&1&to&n&do&#&k&is&the&`intermediate'&vertex
&&&&For&i&=&1&to&n&do
&&&&&&&&For&j&=&1&to&n&do
&&&&&&&&&&&&if&(dist(i,k)&+&dist(k,j)&&&dist(i,j))&then&#&shorter&path?
&&&&&&&&&&&&&&&&dist(i,j)&=&dist(i,k)&+&dist(k,j)
杨磊 阅读(174) |
高中的时候对DP就没有感觉，到现在还是不行，尽管对于递推这种东西已经比原来有感觉的多了
但是还是没办法弄出来状态划分啊什么的，难道真的需要多做题积累经验么
一直觉得DP是很神奇的东西，因为感觉很玄乎，不像其他的算法那样，基本都有固定套路的
DP相对来说很灵活，也正是如此所以难以掌握吧
没办法啦，还是多多努力吧，多做题，多见识一下，大概就能掌握了
熟能生巧么，谁让我天生没长懂DP的脑袋呢
Dev+Algo两不误，我的追求
杨磊 阅读(48) |
ALWAYS implement a tested version of the demonstration from the component
specification.
ALWAYS provide a meaningful message in assert and fail calls.
ALWAYS document your test code as well as you document your component code.
Break up your tests into discrete TestCase classes. If one TestCase becomes
unmanageable, don't hesitate to break it into two or more classes.
Break up your tests within those classes into the smalles
this way, it is clear which areas of the component are failing.
then use the number of tests passing and failing as a completion metric, as
Reduce code duplication and increase robustness with setUp() and tearDown().
Test every public function for as much valid and invalid input as time allows.
Test expected component processes: loading, processing data, and saving data,
for instance.
Don't forget to clean up your environment! Unit tests should leave the system
in the same st there should be no persistent changes. This
is checked during development review.
Test classes are normal classes in every respect, except that they have special
significance to the testing framework. These classes can inherit from a class
intermediate between themselves and the final test. They may contain methods
other than test methods. They may have state.
Because they are in the same package or namespace as the component classes they
test, the unit tests can access package-private and protected classes and their
Interfaces cannot be tested directly, but methods that accept interface
arguments can be presented with alternative implementations. This technique has
great potential for verifying that the component does the expected things with
and to its interface-typed fields and method arguments, and that it reacts
correctly to exceptions thrown by methods invoked on such arguments.
杨磊 阅读(86) |
对一块3行7列的长方形阵列中的小方格的每一格任意染成黑色或白色，求证：在这个长方形中，一定有一个由小方格组成的长方形，它的四个角上的小方格同色。
证法1：每一列的三个格用黑、白两种颜色染色.所有可能的染法只有如下图中的八种
如果在所染色的3行7列阵列中某一列是第（1）种方式，即三格均为白色，则其余6列中只要再有第（1）（2）（3）（4）种方式之一（即该列中至少有两个白格），那么显然存在一个四角格都是白色的长方形.若第（1）、（2）、（3）、（4）种方式均未出现，那么其余6列就只能是（5）、（6）、（7）、（8）这四种方式，根据抽屉原理，其中至少有两列染色方式完全一样.又（5）～（8）中每一列至少有两格染黑色，所以一定存在一个长方形，它的四角格颜色都是黑色。
同理可知，如果有一列是第（8）种方式，即三格均为黑色，那么也存在四角同色的长方形。
如果在7列中（1）、（8）两种方式都未出现，则只有（2）、（3）、（4）、（5）、（6）、（7）这六种方式染这7列，根据抽屉原理，至少有两列染色方式完全一样，所以仍然存在四角同色的长方形。
证法2：第一行有7个小方格，用黑白两种颜色去染，根据抽屉原理，至少有四个方格所染颜色相同，不妨设第一行有4个黑方格.再看第二行，如果在第一行的四个黑方格下面的四格中有两格是黑色，则结论显然成立.否则第二行这四个格中至少有3个白色方格。
再看第三行.根据抽屉原理，在第三行的位于第二行的3个白格下面的3个格中必至少有两格同色.如果有两格为白色，则与第二行构成四角白色的长方形；如果没有两格白色，那么必有两格为黑色，则与第一行构成四角黑色的长方形。
杨磊 阅读(138) |
杨磊 阅读(112) |
bool&find(int&a)
&&&&&&&&for(int&i=1;i&=m;i++)
&&&&&&&&&&&&&&&&if(g[a][&i&]==1&&!b[&i&])
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&&b[&i&]=true;
&&&&&&&&&&&&&&&&&&&&&&&&if(link[&i&]==0||find(link[&i&]))
&&&&&&&&&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&link[&i&]=a;
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&return&true;
&&&&&&&&&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&}
&&&&&&&&return&false;
int&main()
&&&&&&&&while(init())
&&&&&&&&&&&&&&&&for(int&i=1;i&=n;i++)
&&&&&&&&&&&&&&&&{
&&&&&&&&&&&&&&&&&&&&&&&&memset(b,0,sizeof(b));
&&&&&&&&&&&&&&&&&&&&&&&&if(find(i))ans++;
&&&&&&&&&&&&&&&&}
&&&&&&&&&&&&&&&&printf("%d\n",ans);
杨磊 阅读(51) |
&SRM144&DIV1&1100
杨磊 阅读(39) |
&Titan Quest
&Warhammer 40,000 Dawn of War II
&StarCraft II
&Diablo III
Titan Quest 实在是没心思玩，这个ARPG的游戏，居然没有大范围杀伤的技能，或者是我没找到
而且就算有，比如战斗专精的战风，也是伤害低的可怜，根本不想Diablo里面法师的魔法那么强大
差不多是完全靠剧情来打的游戏，屏幕上的怪，无论大的小的，我都只能一个一个的打，太费神了，还是算了
Warhammer 40,000 Dawn of War II，真是好游戏啊！可惜电脑不行，否则效果全开的话，一定是非常非常震撼的
也许等过个几年，我换电脑了，到时候再来尝试一下效果全开是什么感觉
To Be Continued....
有朝一日希望我有机会能玩上这些游戏，但我估计是梦想了
“游戏你的游戏，不要被游戏所游戏”
杨磊 阅读(37) |
http://en.wikipedia.org/wiki/Endianness
杨磊 阅读(102) |
Big and Little Endian
Basic Memory Concepts
In order to understand the concept of big and little endian, you
need to understand memory.
Fortunately, we only need a very high
level abstraction for memory.
You don't need to know all the little
details of how memory works.
All you need to know about memory is that it's one large array.
But one large array containing what?
The array contains bytes.
In computer organization, people don't use the term "index" to
refer to the array locations.
Instead, we use the term "address".
"address" and "index" mean the same, so if you're getting confused,
just think of "address" as "index".
Each address stores one element of the memory "array".
element is typically one byte.
There are some memory configurations
where each address stores something besides a byte.
For example, you
might store a nybble or a bit.
However, those are exceedingly
rare, so for now, we make the broad assumption that all memory addresses
store bytes.
I will sometimes say that memory is byte-addresseable.
This is just a fancy way of saying that each address stores one
If I say memory is nybble-addressable, that means
each memory address stores one nybble.
Storing Words in Memory
We've defined a word to mean 32 bits.
This is the same as 4 bytes.
Integers, single-precision floating point numbers, and MIPS instructions
are all 32 bits long.
How can we store these values into memory?
After all, each memory address can store a single byte, not 4 bytes.
The answer is simple.
We split the 32 bit quantity into 4 bytes.
For example, suppose we have a 32 bit quantity, written as
90AB12CD16, which is hexadecimal.
Since each hex digit
is 4 bits, we need 8 hex digits to represent the 32 bit value.
So, the 4 bytes are: 90, AB, 12, CD where each byte requires
2 hex digits.
It turns out there are two ways to store this in memory.
Big Endian
In big endian, you store the most significant byte in the smallest
Here's how it would look:
Little Endian
In little endian, you store the least significant byte in
the smallest address.
Here's how it would look:
Notice that this is in the reverse order compared to big endian.
To remember which is which, recall whether the least significant
byte is stored first (thus, little endian) or the most significant
byte is stored first (thus, big endian).
Notice I used "byte" instead of "bit" in least significant bit.
I sometimes abbreciated this as LSB and MSB, with the 'B' capitalized
to refer to byte and use the lowercase 'b' to represent bit.
refer to most and least significant byte when it comes to endianness.
Which Way Makes Sense?
Different ISAs use different endianness.
While one way may seem
more natural to you (most people think big-endian is more natural),
there is justification for either one.
For example, DEC and IBMs(?) are little endian, while Motorolas
and Suns are big endian.
MIPS processors allowed you to select
a configuration where it would be big or little endian.
Why is endianness so important?
Suppose you are storing int
values to a file, then you send the file to a machine which uses the
opposite endianness and read in the value.
You'll run into problems
because of endianness.
You'll read in reversed values that won't
make sense.
Endianness is also a big issue when sending numbers over
the network.
Again, if you send a value from a machine of one
endianness to a machine of the opposite endianness, you'll have
This is even worse over the network, because you might
not be able to determine the endianness of the machine that sent you
The solution is to send 4 byte quantities using network byte order
which is arbitrarily picked to be one of the endianness (not sure if it's
big or little, but it's one of them).
If your machine has the same
endianness as network byte order, then great, no change is needed.
If not, then you must reverse the bytes.
History of Endian-ness
Where does this term "endian" come from?
Jonathan Swift was a satirist
(he poked fun at society through his writings).
His most famous book
is "Gulliver's Travels", and he talks about how certain people prefer
to eat their hard boiled eggs from the little end first (thus, lit