USACO 终于做完了

用了大概一个半月的时间吧，当然中间有大概一个礼拜空着来着

这是第二次做USACO了，第一次是高中的时候，那个时候的题目跟现在的都不太一样，主要是顺序，而且那个时候是用PASCAL写的

但是高中的时候没有做完，卡在了Section 5之前，其实是因为很多东西不会，数学其实也不够好，至于理解的能力，不知道现在是不是也有所提高了

其实这次做的并不是非常顺利，我不是牛人，不可能一天扫10几道题目那种，然后每到题目半个小时就搞定

前面3个Section的题目还都不算是很难，都是训练型的，都是教你算法怎么用，从Section 4开始就有比较难的题目了，尤其是DP

DP从高中开始我就没有感觉，那时候就有人跟我说，只能多做题目，也许我现在做的还不够多吧，总感觉DP是很有用很有用的东西，所以一直想学好

不管怎么样，USACO总算是磕磕碰碰的做完了，应该在NoCow和Google的帮助下终于做完了

后面大部分题目我都看了解题报告，有些算法想得出，但是不知道该怎么应用到题目之上

现在发现这点才是最重要的，算法模块谁不会写啊，都可以提前写好一个放在那里，但是问题是怎么把这个算法应用到题目上

可能这就是所谓的建模吧，把题目变形一下，然后跟我们已知的算法联系起来

还有另外一种情况，这个题目的算法不是已知的任何算法，要自己去想的，这才是真正考验一个人算法素养的时候

就像TCO里面的题目，其实很多都是这样的，很少会给你一道题目让你直接去套一个算法的

可能原来我在这方面的理解就有偏差，我总认为，你把所有的常见算法都练熟了，所有的题目都可以横扫

但是问题就是，你能不能看得出来哪道题目用哪种算法

而且，就像DP这种题目，就算你看出来了，状态转移方程你也未必写的出来

总之还是学到了很多，虽然磕磕碰碰，但是做完了100道题还是会有收获的

不知道下一个目标是什么SGU呢，还是TCO

其实之所以喜欢USACO的一个原因就是他会告诉你测试数据，你可以很方便的Debug

像OJ这种，不告诉你测试数据的，如果遇到了WA，你就要想破脑袋去想你的程序哪里错了

而往往一个人自己看自己的程序的时候，是很难发现错误的，这就会让人很郁闷，真的是非常郁闷

更何况，有些OJ真的是很贱的，用一些超级恶心的数据来钻你的空子。

不知道这样对不对，也许是考验你的细心程度吧

SGU or TCO 呢？

posted @ 2009-05-11 09:27 杨磊阅读(1220) | 评论 (1) | 编辑收藏

USACO Section 5回顾

TEXT Convex Hulls	突包
PROB Fencing the Cows	突包问题，直接忽略，差不多所有的计算几何我都跳过了
PROB Starry Night	超级麻烦题，用Flood Fill把所有的pattern全认出来，然后判断重复，不重复就添加新的
PROB Musical Themes	DP题，技巧在于如果两个序列是theme，那么相邻的两个number差相等
PROB Snail Trail	DFS，没啥技巧
PROB Electric Fences	刚开始以为是Divide&Conquer，后来发现跟那道题不一样，直接搜索就可以
PROB Wisconsin Squares	搜索题，Testcase只有sample那一组
TEXT Heuristics & Approximate Searches	启发式搜索，没看
PROB Milk Measuring	一道我看Analysis看了两天的DP，其实还是没有深刻理解
PROB Window Area	可以用矩形切割过
PROB Network of Schools	强连通分量题
PROB Big Barn	最大子正方形，简单的DP
PROB All Latin Squares	搜索+剪枝
PROB Canada Tour	诡异的DP算法，Analysis的那个DP倒是还可以接受，不过Nocow上的似乎需要证明，但是又没有
PROB Character Recognition	这道题目都能用DP，不得不感叹DP的伟大
PROB Betsy's Tour	又是搜索+剪枝
PROB TeleCowmunication	先把点转化成边，然后求最小割
PROB Picture	离散化
PROB Hidden Passwords	搜索+KMP优化
PROB Two Five	算是道难题吧，Analysis都看了好久，DP真是无所不能

第六个Section的就不写了，两个DP+一个牛叉的位运算

那个Cow XOR我估计我这辈子都不会忘记了。

posted @ 2009-05-11 09:16 杨磊阅读(572) | 评论 (1) | 编辑收藏

USACO Section 4回顾

TEXT Optimization Techniques	讲怎么剪枝的
PROB Beef McNuggets	初看上去像是一道背包问题，但是用背包肯定超时，后来看了解题报告，发现原来是数学题
PROB Fence Rails	高维背包问题，只能搜索
PROB Fence Loops	其实是很简单的一道最短路问题，恶心就恶心在图的转化
PROB Cryptcowgraphy	非常恶心的搜索+剪枝
TEXT "Network Flow" Algorithms	网络流，我第一次会写网络流就是看了这个算法
PROB Drainage Ditches	网络流练习题
PROB The Perfect Stall	最大匹配，匈牙利算法
PROB Job Processing	第一问是贪心，第二问应该也还是贪心，就是把第一问最快做完的给第二问最慢做完的
PROB Cowcycles	直接枚举的好像
TEXT Big Numbers	高精度
PROB Buy Low, Buy Lower	经典DP，最长下降序列，可是问题是要求出现了多少次，于是我看了解题报告
PROB The Primes	搜索+剪枝，要注意搜索的顺序，先是第五行第五列，然后对角线，然后其他
PROB Street Race	关键路径，去掉每一个节点，然后看看起点与终点是否连通，不联通总说明是关键节点
PROB Letter Game	枚举，分两块，先找完整的单词，然后找pair
PROB Shuttle Puzzle	刚开始以为搜索，后来看了解题报告，发现原来有规律的，寒啊
PROB Pollutant Control	最小割问题
PROB Frame Up	搜索题，用一张表来维护每个pattern的上下关系，可以大量剪枝

posted @ 2009-05-11 08:52 杨磊阅读(355) | 评论 (0) | 编辑收藏

USACO Section3回顾

TEXT Minimal Spanning Trees	最小生成树，经典的算法
PROB Agri-Net	最小生成树，USACO这点比较好，一般讲完了一个算法，都会出一道练习题
PROB Score Inflation	背包问题
PROB Humble Numbers	经典题目，算法是用已有的丑数乘上集合里面的素数去生成新的丑数
PROB Shaping Regions	记得高中的时候做过这道题目，当初用的离散化的方法，不过现在USACO时限改成1秒了，那个方法可能不行了
PROB Contact	枚举，输出有点烦
PROB Stamps	一个背包问题的变形
TEXT Knapsack Problems	怎么到现在才介绍背包问题啊，前面都有好几道了
PROB Factorials	高精度可以做，但是我是去接保留了最后的6位数，一直到最后。注意只保留一位数是不行的
PROB Stringsobits	直接生成的
PROB Spinning Wheels	又是一个我没看懂题的题目，然后看了标程，原来直接枚举就行了，如此简单
PROB Feed Ratios	线性代数题目，直接把方程解出来就好了
PROB Magic Squares	比较恶心的DFS，主要是转换那个状态起来比较麻烦
PROB Sweet Butter	最短路的题目，枚举每一个点作为集合点，然后求最短路
TEXT Eulerian Tours	欧拉回路，又是一个经典的算法
PROB Riding The Fences	欧拉回路的题目
PROB Shopping Offers	DP问题，状态方程又不是我自己想的，555～
PROB Camelot	著名的亚瑟王问题，我是看了解题报告才做出来的
PROB Home on the Range	DP问题，找最大子正方形，后面还有一道是找最大子矩形的，难度大了很多
PROB A Game	动态规划，好不容易自己推出来的状态转移方程
TEXT Computational Geometry	计算几何，没看：（
PROB Closed Fences	计算几何的题目，跳过了
PROB American Heritage	二叉树遍历顺序题目，已知前序中序求后序
PROB Electric Fence	一个迭代求最优值的题目，其实就是不断缩小范围的枚举
PROB Raucous Rockers	DP，状态方程又是看来的，似乎这才是比较有难度的DP，不像前面有些题，状态方程简直显而易见

posted @ 2009-05-10 21:25 杨磊阅读(480) | 评论 (0) | 编辑收藏

USACO Section 2回顾

TEXT Graph Theory	很有用的东西，建议仔细看看
TEXT Flood Fill Algorithms	其实就是DFS
PROB The Castle	Flood Fill，直接用上面那篇文章的算法就可以过
PROB Ordered Fractions	2次循环，求出所有的分数，约分，去掉重复的，排序
PROB Sorting A Three-Valued Sequence	这题我是看的结题报告，其实就是分块来交换，首先把所有的能一次交换完成的处理掉，然后处理需要两次交换的
PROB Healthy Holsteins	忘记是贪心还是背包了……-_-!
PROB Hamming Codes	直接枚举的
TEXT Data Structures	跳过
TEXT Dynamic Programming	动态规划啦，非常有必要好好看，不过这篇文章也只是对于初学者很有用
PROB Preface Numbering	罗马数字问题，把所有可能的组合先生成出来，4，9这种，然后就是求最小表示方法
PROB Subset Sums	背包问题，这题我最开始居然没看出来……，以为是要深搜的，汗啊
PROB Runaround Numbers	直接模拟的，注意判断是否是round number的条件
PROB Party Lamps	我当初只注意到了每个操作做两次就跟没做一样，所以一共也就有8种操作，后来看了解题报告，发现其实只要处理前6个灯就可以了
PROB The Longest Prefix	DP，我看得别人的解题报告，没办法DP是我的弱项
PROB Cow Pedigrees	DP，自己推了一个差不多的状态方程，可惜错了……
PROB Zero Sum	直接模拟，把表达式生成出来，然后计算结果就行
PROB Money Systems	背包问题
PROB Controlling Companies	看了别人的解题报告，这道题目用了一个变形的Floyd算法，很巧妙
TEXT Shortest Paths	经典算法啦
PROB The Tamworth Two	模拟吧
PROB Overfencing	其实是比较恶心的一题，因为要转化那个图，剩下的就简单了，从两个exit开始BFS，然后找最大值
PROB Cow Tours	先Floyd，把图划分成两块，然后枚举
PROB Bessie Come Home	直接Floyd就行
PROB Fractions to Decimals	判断时候循环的条件就是看余数是否重复出现，当然，在我看了Analysis之后，发现了更巧妙的办法

posted @ 2009-05-10 17:43 杨磊阅读(382) | 评论 (0) | 编辑收藏

Cow XOR (USACO)

这个题目是USACO最后的一道题目，我在网上找了N多的题解，不是完全一样的，就是说的不知道是什么东西的

不知道为啥，是不是所有搞OI的人在写题解的时候都喜欢用“提示”的办法，不直接把问题说清楚，而是隐隐约约的公诉你该怎么做，然后你让你自己去想。

于是导致我到现在都没有弄明白这道题目是怎么回事，尽管他们的做法有N多种，但是归根到底都是在搞一个叫做前缀的东西。

下面这个是我在TopCoder上面找到的一个牛人的解释，算是英语写的比较好的，很通俗易懂的
上面这篇文章我想我就不用再翻译了，说的比较清楚，但是他也没有给出具体的算法，不过思路已经很清楚了

其实有了第一条性质之后，最朴素的办法就是枚举i和j，所以个2次循环，但是这样显然是要TLE的

在没有更好的算法的前提下，这道题目的算法就是空间换时间，在我看来就是这样的。

在看了N多代码之后，我觉得还是USACO的Analysis的代码看上去比较美，不知道为啥，那些用Hash和Trie的我都没看懂，可能是我比较菜吧

下面我尝试着把USACO的代码解释一下，看看能不能说清楚，很遗憾，由于这道题目的巨型的输入数据，java肯定是没办法过的

1 int main() {
2     freopen("cowxor.in", "r", stdin);
3     freopen("cowxor.out", "w", stdout);
4     scanf("%i", &n);
5     xr[0] = 0;
6     for (a = 0; a < n; a++ ) {
7         scanf("%d", &x);
8         xr[a+1] = xr[a] ^ x;
9     }
10     for (a = 0; a <= n; a++ ) {
11         prev[a][0] = a-1;
12         prev[a][1] = -1;
13         best[a] = a-1;
14     }
15     wyk = 22;
16     res = 0;
17     while (wyk--) {
18         for (a = 1; a <= n; a++ )
19             if (prev[a][0] == -1)
20                 prev[a][1] = -1;
21             else {
22                 if (xr[a] >> wyk != xr[prev[a][0]] >> wyk) {
23                     tmp[0] = prev[prev[a][0]][1];
24                     tmp[1] = prev[a][0];
25                 } else {
26                     tmp[0] = prev[a][0];
27                     tmp[1] = prev[prev[a][0]][1];
28                 }
29                 prev[a][0] = tmp[0];
30                 prev[a][1] = tmp[1];
31             }
32         fnd = false;
33         for (a = 1; a <= n; a++ )
34             if (0 <= best[a])
35                 if ((xr[a] >> wyk) % 2 != (xr[best[a]] >> wyk) % 2 ||
36                                       0 <= prev[best[a]][1])
37                     fnd = true;
38         if (fnd) {
39             res |= 1 << wyk;
40             for (a = 1; a <= n; a++ )
41                 if (0 <= best[a] &&
42                               (xr[a] >> wyk) % 2 == (xr[best[a]] >> wyk) % 2)
43                     best[a] = prev[best[a]][1];
44         }
45     }
46     for (a = 0; best[a] == -1; a++ );
47     printf("%d %d %d"n", res, best[a]+1, a);
48     return 0;
49 }

首先，6～9行，程序把从1开始到i位结束的所有的xor都求出来保存在了数组xor里面，我想这个就是为了方便后面用到xor的那个性质。

10～14行是一个初始化的过程，这个prev的定义应该可以从USACO的Analysis上面看到：

xr[pop[q][0]]'s and xr[q]'s binary representations are the same on positions e, e+1, etc., and pop[q][0] is biggest possible with 0 ≤ pop[q][0] < q. If there's no such pop[q][0] possible, then pop[q][0] = -1.

xr[pop[q][1]]'s and xr[q]'s binary representations are the same on positions e+2, e+2, etc., different on position e, and pop[q][1] is biggest possible with 0 ≤ pop[q][1] < q. If there's no such pop[q][1] possible, then pop[q][1] = -1.

我们要根据后面的循环来看这个prev数组的含义

外侧的循环的作用是每次处理一位，由于题目中已经说明了，最多只有21位，所以循环21次就可以了。

我们来看内侧的循环

18～31行，对所有的奶牛编号循环一遍，得到的结果就是：
对于当前的xor number，对于这个xor number的前21 - wyk位，与他相同的那个xor number的位置，并且，这个位置要尽量的靠后。

如果没有相同的，那么这个位置就是-1

这样，经过每次循环之后，prev里面就是与当前的xor number前k位相同的那个数的位置，一次一次循环，直到最后。

prev[i][0]存的是当current bit也相同的时候的位置，prev[i][1]存的是currnet bit不相同时候的位置，为什么要这样呢？

这可能就需要解释一下
     if (xr[a] >> wyk != xr[prev[a][0]] >> wyk) {
                     tmp[0] = prev[prev[a][0]][1];
                     tmp[1] = prev[a][0];
     } else {
                     tmp[0] = prev[a][0];
                     tmp[1] = prev[prev[a][0]][1];
    }
如果当前比较的这一位相等，那么也就意味着prev[a][0]不用变，但是prev[i][1]却必须变化，因为当前的这一位，已经不是刚才比较的那一位了，prev[a][1]应该等于此时的prev[a][0]的prev[a][1]，我想这个应该不难理解。

另一方面，如果当前比较的这一位不相等的时候，那么prev[a][1]就应该等于prev[a][0]了，因为之前的所有位都相等，之后当前这一位不相等，这就是prev[a][1]的定义。那么prev[a][0]的值呢？我们需要注意的时候，当我们处理到a的时候，prev[a][0]位置的值肯定是已经处理过的了。那么prev[a][prev[a][0]][1]里面存的就是与prev[a][0]在当前位不相等的那个xor number的位置，注意，bit只有0和1，prev[a][0]与当前的不相等，而prev[a][prev[a][0]][1]又与prev[a] [0]不相等，所以当前的prev[a][1]肯定与prev[a][prev[a][0]][1]是相等的。这就是 tmp[0] = prev[prev[a][0]][1];的含义。

我再来看32～37行，首先要知道best[q]的定义：

if X would be equal biggest possible xor, then xr[best[q]] xor xr[q]'s in equal X's binary representation on positions e, e+1, etc., and best[q] is biggest possible with 0 ≤ best[q] < q. If there's no such best[q] possible, then best[q] = -1.

想要得到尽量大的xor，那么就要尽量让每一位都不相同（xr[a] >> wyk) % 2就是取当前的二进制的最后一位

这段代码的作用就是找，到当前位为止，是否有两个xor number，他们的每一位都不相同，这样就能保证异或结果是最大的。

接下来看38～45的这段代码，因为我们是从高位到低位来处理的，这样的话，如果能保证高位是1，那么比你所有的低位都是1都管用：）

于是，既然我们找到了高位是1的情况，那么我们就要记录下结果 res

然后，剩下的那个循环就是更新best[a]

在所有的xor number中，如果当前位跟best[a]的当前位是相等的，那么就更新best[a]，将其更新为prev[best[a]][1]，就是除了当前位不相等，其余位不变的那个xor number，这样就保证了从高位开始，每一位都能够尽量取到1，因为只要高位尽量是1，我们的结果就能尽量的大。

其实prev这个数组里面真正有用的是prev[q][1]

不知道我解释清楚了没，其实解释了一遍，自己也清楚了很多。

posted @ 2009-05-10 17:20 杨磊阅读(680) | 评论 (0) | 编辑收藏

USACO Section 1回顾

Section 1.0	TEXT Introduction	介绍啦，我是没看
Section 1.1	TEXT Submitting Solutions	交你怎么提交程序的，可以看看
	PROB Your Ride Is Here	最直接的方法是直接乘，然后mod 47,不过可以利用余数定理，边乘边mod
	TEXT Contest Problem Types	跳过
	TEXT Ad Hoc Problems	跳过
	PROB Greedy Gift Givers	简单的模拟题，就是处理名字的时候有点烦
	PROB Friday the Thirteenth	数日期的题，我不知道一天天的模拟能不能过，我是只算了周五这一天的。
	PROB Broken Necklace	也是模拟题，不过很要细心，有很多特殊情况，比如全是w。
Section 1.2	TEXT Complete Search	跳过
	PROB Milking Cows	直接模拟应该是过不了的，
	PROB Transformations	模拟题，直接把所有可能的pattern生成出来，然后比较就行
	PROB Name That Number	正确方法是把字典里面的所有word转化成数字，然后比较就行。
	PROB Palindromic Squares	直接枚举
	PROB Dual Palindromes	DFS，注意搜索的时候，只要搜索回文数前一半就行，后面的直接反向复制一下就好
Section 1.3	TEXT Greedy Algorithm	跳过
	PROB Mixing Milk	简单的贪心
	PROB Barn Repair	也是贪心法，把最大的缝隙就出来，然后去覆盖
	TEXT Winning Solutions	跳过
	PROB Calf Flac	枚举，从没一点向两边枚举
	PROB Prime Cryptarithm	直接枚举，反正只有5个数
Section 1.4	TEXT More Search Techniques	跳过
	PROB Packing Rectangles	恶心题，我没做：P
	PROB The Clocks	看了一个牛人的结题报告后过的，那位牛人总结了一个数组，就是如何让表针转一圈回到原来位置的操作组合
	PROB Arithmetic Progressions	搜索，硬搜的
	PROB Mother's Milk	BFS，把所有的情况都弄出来
Section 1.5	TEXT Introduction to Binary Numbers	跳过
	PROB Number Triangles	经典DP
	PROB Prime Palindromes	搜索，生成回文数，检查是否是素数。需要一点点剪枝（长度是偶数的回文数，除了11之外必然是合数，因它肯定是11的倍数）
	PROB SuperPrime Rib	直接枚举
	PROB Checker Challenge	八皇后啊，用最经典的算法就能过，不过如果想优化的非常快，可能需要其他的办法，也有很复杂的。

posted @ 2009-05-09 15:05 杨磊阅读(1364) | 评论 (0) | 编辑收藏

终于把USACO做完了

感想及题解待会儿再发：）

posted @ 2009-05-09 13:50 杨磊阅读(336) | 评论 (0) | 编辑收藏

Picture （USACO）

1 import java.io.*;
2 import java.util.*;
3 /*
4 ID: yanglei4
5 LANG: JAVA
6 TASK:picture
7 */
8 public class picture {
9     public int[] level;
10     public int N;
11     public int ans = 0;
12
13     public class Line implements Comparable<Line> {
14         int s,t,p;
15         boolean start;
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         }
31     }
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         }
51     }
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();
82     }
83     public static void main(String[] args) throws IOException {
84         picture t = new picture();
85         t.done();
86         System.exit(0);
87     }
88 }
89

这道题用了离散化的方法

其实最朴素的方法就是在一个20000*20000的矩阵上面把所有的点描出来，然后把这些点的周长算出来，不过算周长这一步也是很麻烦的。

因为毕竟还有可能出现“空心”的情况

用离散化的方法就是想办法只数每条线段，而不去管其他空白的地方是怎么样的。

由于我们是需要算周长的，所以只需要看矩形的四条边就可以了。

然后，我们就是先看所有的横边，再看竖边。

先把横边全部选出来，放在一个数组里面，然后排序，从下到上。

一个矩形的两条边要分成始边和终边，排序的时候，如果纵坐标相同，那么应该把始边放在终边。

如果遇到始边，那么就把这条边上面的所有点level[j]加一。

如果遇到终边，就把那条边上所有的点的level[j]减一

于是，当一条边上的点的leve是1的时候，那么就说明这条边肯定是始边边缘，所以要ans++

另一种情况，当一条边上的点的level是0的时候，那么说明这个点是终边边缘，所以ans++

这样扫完横边再扫竖边。

最后的ans就是周长了。

不过这个算法的时间效率并不是非常的好，因为数据比较弱（可能是这样）

如果真的是有5000个矩形，没个矩形都是20000×20000的，那么可能会超时

posted @ 2009-05-07 10:33 杨磊阅读(294) | 评论 (0) | 编辑收藏

USACO终于到5.5了

虽然从5.1开始，大部分题目都要借助于NoCow和网上的解题报告，但是还是学到了不少的东西。

原来认为只要熟练的掌握各种算法，那就可以随便去切题，现在发现其实不是这样。

有很多题目，都需要进行一些转化，也可以说是建模，才能套用现成的算法

而有一些题目，根本就没有现成的算法，只能你自己去想

这种算法基本上是不属于任何一类的

还有一些比如说剪枝，虽然搜索谁都会，Brute Force谁都会写，但是剪枝却不是谁都能写的出来的

这就需要一些数学功底

现在发现这个东西必须要长年累月的积累才能够达到驾轻就熟的境界。

但是就算那样，也不能保证所有的题目都会做。

posted @ 2009-05-06 23:57 杨磊阅读(285) | 评论 (0) | 编辑收藏

Telecowmunication （USACO）

  1 import java.io.*;
  2 import java.util.*;
  3 /*
  4 ID:
  5 LANG: JAVA
  6 TASK:telecow
  7 */
  8 public class telecow {
  9
10     public static final int WHITE = 0, GRAY = 1, BLACK = 2;
11     private int[][] flow, capacity, res_capacity;
12     private int[] parent, color, queue;
13     private int[] min_capacity;
14     private int size, source, sink, first, last;
15     private static int MAXN = 200;
16     int N,M;
17
18     private int maxFlow()  // Edmonds-Karp algorithm with O(V3E) complexity
19     {
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 < size; i++)
28             for (int j = 0; j < size; j++)
29                 res_capacity[i][j] = capacity[i][j];
30
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_flow;
46     }
47
48     private boolean BFS(int source)  // Breadth First Search in O(V2)
49     {
50         for (int i = 0; i < size; i++) {
51             color[i] = WHITE;
52             min_capacity[i] = Integer.MAX_VALUE;
53         }
54
55         first = last = 0;
56         queue[last++] = source;
57         color[source] = GRAY;
58
59         while (first != last)  // While "queue" not empty..
60         {
61             int v = queue[first++];
62             for (int u = 0; u < size; 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;
73     }
74
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 = source;
86         int osink = sink;
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
135     }
136
137     public static void main(String[] args) throws IOException {
138         telecow t = new telecow();
139         t.done();
140         System.exit(0);
141     }
142 }
143

这道题目我自己看出来是最小割的问题，而之前的题目有一道是最小割的

但是有一个不同，这道题是点的最小割，而不是常规的边的最小割

所以这就比较麻烦，需要我们把点转化成边

这就让我想起了之前的那个Fence Loops

我就是把所有的边表示的图转化成了点表示的图，我实在是不想再写那么恶心的算法了。

然后我就去NoCow上面看了一下，果然是有很赞的方法。

具体方法就是，把一个点变成两个点，然后在两个点之间加一条边，并且这条边的权值是1

这样的话，如果割这条边，就相当于去掉了这个点。

剩下的事情就是跟前面的那个Pollute Control差不多了

每次去掉一条边，然后用MaxFlow求一下最大流，如果得出的最大流==最大流-边的权值

那么就证明这条边是最小割。

就这样把所有的最小割找出来，然后就可以了

貌似数据很弱，不像上次的那个Pollute那道题目，还要考虑边的编号的问题的。

posted @ 2009-05-06 14:01 杨磊阅读(264) | 评论 (0) | 编辑收藏

All Latin Squares (USACO)

一个搜索的题目，不过肯定是要剪枝的

最简单的两个剪枝我想到了

第一个：
首先，第一行已经确定了，那么我们可以把第一列也确定，就按照升序，2，3，4，5……，这样的话，没生成这么一个square，我们就可以随便的去交换除了第一行后面的几行。

他们的一个全排列就对应着一种组合，所以最后的答案乘以N-1的阶乘就可以

第二个：
这个其实是看来的，就是每次只要所搜完N-1行就可以了。因为剩下的一行必然存在一个解。其实这个不难理解的，最后一行的排列顺序只跟前面的每一列缺少的那个数有关。

而且也只能取缺少的那个数，所以也就是唯一的。

第三个：
要用到置换群，我没看懂

尽管之前N次看组合数学里面都说到置换群，但是我还是似懂非懂，问了数学小王子，他也不是非常懂。然后以为这个东西没用，就忽略了。没想到还真的有用。

posted @ 2009-05-02 15:22 杨磊阅读(388) | 评论 (0) | 编辑收藏

Network of Schools （USACO)

今天终于第一次写了强连通分量的题目

虽然以前老早就知道有这么个东西，对这个东西也有概念，但是确实从来没有写过判别的算法

原来如此简单，但是确实也很巧妙。

在算法导论上面看到的K算法，方法就是做两遍DFS，因为强连通分量有一个性质，就是如果把所有的边反向，那么它仍然是一个强连通分量。

但是今天我用的是Tarjan算法，据说效率比K算法高很多，事实上也应该是这样，因为Tarjan算法只做了一次DFS

其实思想也很简单，就是一直DFS（u），向下向下向下，如果突然发现有一个点可以回到u了，那么这个肯定是一个强连通分量。

哈哈，是不是很通俗。

严格的定义过程大家可以看这里http://www.cmykrgb123.cn/blog/scc-tarjan/

我也是参考了这个才做出来的Tarjan算法，Wiki上的那个过于庞大了，虽然封装的非常好

说说本题，其实就是找强连通分量，然后把每个强连通分量当成一个“超点”来考虑

如果这个“超点”的入度为零，那么它就必然是一个源头，统计这样的“超点”的个数，就是第一问的答案。

第二问，如果有一个“超点”入度不是0，但是出度是0，那就说明这个“超点”可以给其他“超点”作贡献。

我们就找这样的点对，把入度是0和出度是0的点连起来。

这样匹配过后，剩下的要么全是入度是0的，要么全是出度是0的，这些就没办法了，随便从一个连通分量连接过来一条边就可以了。

所以第二问的答案就是所有的“超点”中，入度是0和出度是0的点大的那个数。

  1 import java.io.*;
  2 import java.util.*;
  3 /*
  4 ID: yanglei4
  5 LANG: JAVA
  6 TASK:schlnet
  7 */
  8 public class schlnet {
  9     boolean[] inStack;
10     int[] DFN;
11     int[] LOW;
12     int index = 0;
13     int[] Stack;
14     int top = 0;
15     int[][] map;
16     int BelongCount = 0;
17     int[] belong;
18
19     public void Tarjan(int i) {
20         DFN[i] = LOW[i] = ++index;
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] = BelongCount;
38             } while (j != i);
39             BelongCount++;
40         }
41
42     }
43
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 <= BelongCount;i++) {
77             for (int j = 1; j<= BelongCount;j++) {
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 <= BelongCount;i++) {
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();
103     }
104
105     public static void main(String[] args) throws IOException {
106         schlnet t = new schlnet();
107         t.done();
108         System.exit(0);
109     }
110 }
111

posted @ 2009-04-30 20:23 杨磊阅读(274) | 评论 (0) | 编辑收藏

Big Barn （USACO）

1 import java.io.*;
2 import java.util.*;
3
4 /*
5 ID: yanglei4
6 LANG: JAVA
7 TASK:bigbrn
8 */
9 public class bigbrn {
10     public static int min(int a, int b) {
11         if (a < b) return a;
12         else return b;
13     }
14     public static int min3(int a, int b, int c) {
15         return min(a, min(b, c));
16     }
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);
57     }
58 }
59

应该算是一个比较基本的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] != '#'

posted @ 2009-04-30 10:40 杨磊阅读(176) | 评论 (0) | 编辑收藏

Starry Night (USACO)

摘要: 绝对，非常考耐心，细心的一道题目，这道题目充分的说明我是考虑问题不全面的人所以现在看来TopCoder的测试数据还都算是比较弱的，真的没有极其变态的，而且TopCoder的题目其实没有超级复杂的，或许是因为我从来没做过第三题吧。回正题。这道题目其实一看就知道怎么做，但是就一个字烦首先你要用FloodFill把所有的Cluster标注出来，这个不难，而且速度很快，时间... 阅读全文

posted @ 2009-04-28 21:53 杨磊阅读(476) | 评论 (2) | 编辑收藏

终于到了5.1了，希望能早日做完USACO

发个网络流的标准代码，用的是BFS

外面自己套一个类就行了

capacity自己初始化放进去就可以了

返回值在max_flow里面，有需要的话可以自己改成返回类型的

1     public static final int WHITE = 0, GRAY = 1, BLACK = 2;
2     private int[][] flow, capacity, res_capacity;
3     private int[] parent, color, queue;
4     private int[] min_capacity;
5     private int size, source, sink, first, last;
6     private int max_flow;
7
8     private void maxFlow()  // Edmonds-Karp algorithm with O(V3E) complexity
9     {
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];
16
17         for (int i = 0; i < size; i++)
18             for (int j = 0; j < size; j++)
19                 res_capacity[i][j] = capacity[i][j];
20
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         }
35     }
36
37     private boolean BFS(int source)  // Breadth First Search in O(V2)
38     {
39         for (int i = 0; i < size; i++)
40         {
41             color[i] = WHITE;
42             min_capacity[i] = Integer.MAX_VALUE;
43         }
44
45         first = last = 0;
46         queue[last++] = source;
47         color[source] = GRAY;
48
49         while (first != last)  // While "queue" not empty..
50         {
51             int v = queue[first++];
52             for (int u = 0; u < size; 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;
63     }

posted @ 2009-04-28 10:39 杨磊阅读(182) | 评论 (0) | 编辑收藏

Frame Up

原来这道题目这么简单，记得当年高中的时候做USACO的时候，好像最后就是卡在这道题目上面，然后就是NOIP了

然后我就伤心的告别了NOIP投向了好好学习的怀抱。

今天拿过来看还是没什么思路，然后就去搜了一下解题报告。

其实这个题目无论如何也是要DFS的，因为人家要你输出全部的答案。这样就不用怕了，最多就是剪剪枝。

但是最开始没有想到这一点。

问题就在这个剪枝上，和怎么判断合理的解上面。

方法就是，首先找到每一个Frame的四个角。

然后沿着这个Frame的每条边走一下，如果有其他的字符，就是跟当前Frame不同的字符，那么这个字符肯定是在当前这个字符上层的。

这样就能用一张表来确定上下关系，Above[i][j]，表示第i个字符在第j个字符上层

然后就是根据这张表来做一个DFS，这样就可以了。

看了leokan的解题报告，说还要floyd一下。

这样做的目的无非也就是想确定两两之间的上下层关系罢了。

但是似乎没这个必要，直接DFS就可以了。

  1 import java.io.*;
  2 import java.util.*;
  3 /*
  4 ID: yanglei4
  5 LANG: JAVA
  6 TASK:frameup
  7 */
  8 public class frameup{
  9     static char[][] board;
10     static int[][] pos;
11     static int[] in;
12     static int cnt;
13     static int[][] above;
14     static char[] answer;
15     static PrintWriter out;
16     public static void findAnswer(int step) {
17         int i,j;
18         if (step >= cnt) {
19             for (int k = 0; k < cnt; 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               }
34
35         }
36     }
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 */
79
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 */
84
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 */
91
92                    /* top */
93                    int loc = board[pos[i][0]][j] - 'A';
94                    if (loc != i)
95                      above[loc][i] = 1;
96
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);
107     }
108 }
109

posted @ 2009-04-27 17:07 杨磊阅读(154) | 评论 (0) | 编辑收藏

UML读书笔记

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 shaped.
Second, Every model may be expressed at different levels of precision.
Third, The best models are connected to reality.
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:

Things
Relationships
Diagrams

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 walls and other things; walls themselves may have embedded doors and windows; 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, fixed panes; a patio window is a kind of window with panes that open side to side.

posted @ 2009-04-26 18:37 杨磊阅读(170) | 评论 (0) | 编辑收藏

解决Windows 7支付宝问题

先自动下载了新的控件

然后去用这个文件去注册掉那个什么什么CAB

http://www.blogjava.net/Files/LittleDS/800A138F.rar

然后再去下载 xenroll.dll
去 cmd 运行 regsvr32 xenroll.dll

然后就可以了，就可以导入数字证书了。

posted @ 2009-04-25 14:16 杨磊阅读(162) | 评论 (0) | 编辑收藏

The Primes （USACO）

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ --> 1 import java.io.*; 2 import java.util.*; &n... 阅读全文

posted @ 2009-04-24 12:01 杨磊阅读(208) | 评论 (0) | 编辑收藏

就一个toString和toByteArray的差别

速度提高了一倍啊，看来底层的东西还是有必要了解的，不过Java写东西是真方便啊

本来这道题是要高精度的，YD啊，但是Java有BigDecimal，哈哈，不过这玩意好用是好用，但是确实是非常的慢

我估计我自己用一个数组实现的话，速度应该还会快的

不过最后被我瞎猫碰死耗子碰到了，终于过了。

1 import java.io.*;
2 import java.math.BigInteger;
3 import java.util.*;
4 /*
5 ID: yanglei4
6 LANG: JAVA
7 TASK:buylow
8 */
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 < len; 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);
73     }
74 }
75

就是红色的那个地方，用toString的话，最后一个点过不了，换成了这个就过了。

posted @ 2009-04-23 23:27 杨磊阅读(2367) | 评论 (0) | 编辑收藏

Network Flow

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

posted @ 2009-04-22 14:05 杨磊阅读(155) | 评论 (0) | 编辑收藏

我的Eclipse配色

http://www.blogjava.net/Files/LittleDS/eclipse.rar 喜欢的可以拿去用，欢迎提意见

之所以用黑色，就是因为foreground可以用更多的颜色，对比度高一点

而且经常看白色的背景色，好像对眼睛也是一种折磨。

http://www.blogjava.net/Files/LittleDS/eclipse.rar

posted @ 2009-04-17 22:38 杨磊阅读(1785) | 评论 (0) | 编辑收藏

Hash很强大

第一次用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.43750000000000000000

40/16 = 2.50000000000000000000

39/15 = 2.60000000000000000000

40/15 = 2.66666666666666666666

39/14 = 2.78571428571428571428

40/14 = 2.85714285714285714285

39/13 = 3.00000000000000000000

40/13 = 3.07692307692307692307

39/12 = 3.25000000000000000000

40/12 = 3.33333333333333333333

就相当于这些ratio全都翻了一倍，那样的话，variance当然不会变

所以个剪枝是正确的。

贴一下代码：

  1 import java.io.*;
  2 import java.util.*;
  3 /*
  4 ID: yanglei4
  5 LANG: JAVA
  6 TASK:cowcycle
  7 */
  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[] hash;
15     public int[] ans1;
16     public int[] ans2;
17
18     public static boolean contains(String str) {
19         int num = str.hashCode();
20         if(num<0) num = -num;
21         int p = num % hash.length;
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]=str;
27         return false;
28    }
29
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 = start; i <= F2 - (F - step); i++) {
41             s1[step] = i;
42             DFS_F(step + 1, i + 1);
43         }
44     }
45
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 = start; i <= R2 - (R - step); i++) {
54             s2[step] = i;
55             DFS_R(step + 1, i + 1);
56         }
57     }
58
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]];
68
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 * avg;
78         if (vf < min) {
79             min = vf;
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;
84     }
85
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;
90
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]);
112
113         for (int i = 1; i <= R - 1; i++)
114             out.print(ans2[i] + " ");
115         out.println(ans2[R]);
116
117         out.close();
118     }
119
120     public static void main(String[] args) throws IOException {
121         cowcycle t = new cowcycle();
122         t.done();
123         System.exit(0);
124     }
125 }
126

posted @ 2009-04-17 22:32 杨磊阅读(130) | 评论 (0) | 编辑收藏

Cryptcowgraphy

不明白为什么一模一样的算法，Java的结果就是不对呢，很奇怪

又是一个剪枝的题目，我发现剪枝这东西真是需要灵感的

那个不会改变的字符串的剪枝比较容易想，不过Hash的那个剪枝确实是让我爱莫能及啊，然后就参考了Leokan的代码

很神奇的代码，Hash Size只有3W+，然后居然就AC了，我最后就是用他的代码试了一下 -_-!，然后AC的

可是为什么我的Java代码就是过不了呢？很神奇

在第七个点的时候，Hash Size要开到50W才可以出正确的结果，但是这样的话时间会超长，估计有4，5秒的样子

而且我把能加的剪枝全加上了，还是不行……

真是不明白所以啊，不知道自己问题处在哪里了。

太TM诡异了……

posted @ 2009-04-16 23:56 杨磊阅读(150) | 评论 (0) | 编辑收藏

转一篇字符串Hash函数的文章

http://www.cmykrgb123.cn/blog/string-hash-compare/

常用的字符串Hash函数还有ELFHash，APHash等等，都是十分简单有效的方法。这些函数使用位运算使得每一个字符都对最后的函数值产生影响。另外还有以MD5和SHA1为代表的杂凑函数，这些函数几乎不可能找到碰撞。

常用字符串哈希函数有BKDRHash，APHash，DJBHash，JSHash，RSHash，SDBMHash，PJWHash，ELFHash等等。对于以上几种哈希函数，我对其进行了一个小小的评测。

Hash函数	数据1	数据2	数据3	数据4	数据1得分	数据2得分	数据3得分	数据4得分	平均分
BKDRHash	2	0	4774	481	96.55	100	90.95	82.05	92.64
APHash	2	3	4754	493	96.55	88.46	100	51.28	86.28
DJBHash	2	2	4975	474	96.55	92.31	0	100	83.43
JSHash	1	4	4761	506	100	84.62	96.83	17.95	81.94
RSHash	1	0	4861	505	100	100	51.58	20.51	75.96
SDBMHash	3	2	4849	504	93.1	92.31	57.01	23.08	72.41
PJWHash	30	26	4878	513	0	0	43.89	0	21.95
ELFHash	30	26	4878	513	0	0	43.89	0	21.95

其中数据1为100000个字母和数字组成的随机串哈希冲突个数。数据2为100000个有意义的英文句子哈希冲突个数。数据3为数据1的哈希值与 1000003(大素数)求模后存储到线性表中冲突的个数。数据4为数据1的哈希值与10000019(更大素数)求模后存储到线性表中冲突的个数。

经过比较，得出以上平均得分。平均数为平方平均数。可以发现，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) - hash;
}
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++);
a *= b;
}
return (hash & 0x7FFFFFFF);
}

// JS Hash Function
unsigned int JSHash(char *str)
{
unsigned int hash = 1315423911;
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 1313 13131 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;
int i;
for (i=0; *str; i++)
{
if ((i & 1) == 0)
{
hash ^= ((hash << 7) ^ (*str++) ^ (hash >> 3));
}
else
{
hash ^= (~((hash << 11) ^ (*str++) ^ (hash >> 5)));
}
}
return (hash & 0x7FFFFFFF);
}

posted @ 2009-04-16 22:12 杨磊阅读(554) | 评论 (0) | 编辑收藏

MySQL无法远程连接问题

今天在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服务器

想懂很多东西。

posted @ 2009-04-16 19:28 杨磊阅读(1397) | 评论 (0) | 编辑收藏

再一次见识了Java的慢……

Fence Rails

一道感觉很不错的搜索+剪枝的题目，当然剪枝策略我是参考来的，我自己想到的都是小剪枝

然后我自己用Java实现了，结果发现……，这速度啊，真让我郁闷，居然在第四个点就超时了

但是同样的算法用C++实现的代码，快了100+倍。

难怪现在还有这么多人在搞C++，也难怪有人批评说Java速度慢，还有些人在反驳

事实却是如此啊。

代码贴一下吧，TLE的，如果有人愿意的话，可以转成C++用就行了

其实我是想能不能再改进改进，让它用Java也能过，但是感觉很难，我已经想不出更好的剪枝的办法了

或者另外一个方法就是空间换时间，但是感觉已经没什么好换的了，该开的数组都开了。

1 import java.io.*;
2 import java.util.*;
3 /*
4 ID: yanglei4
5 LANG: JAVA
6 TASK:fence8
7 */
8 public class fence8{
9     int wastemax = 0;
10     int ans;
11     int N,R;
12     int[] remain;
13     int[] rails;
14     int[] from = new int[1100];
15     PrintWriter out;
16
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         }
42     }
43
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 - railSum;
80             railSum -= rails[i];
81             dfs(i,0);
82         }
83         out.println(0);
84         out.close();
85     }
86     public static void main(String[] args) throws IOException {
87         fence8 t = new fence8();
88         t.done();
89         System.exit(0);
90     }
91 }
92

posted @ 2009-04-16 16:50 杨磊阅读(181) | 评论 (0) | 编辑收藏

UML Structure zz from Wiki

posted @ 2009-04-15 00:10 杨磊阅读(142) | 评论 (0) | 编辑收藏

不容易啊，做了好几个小时

摘要: Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ --> 1 import java.io.*; 2 import java.util.*; &n... 阅读全文

posted @ 2009-04-14 00:53 杨磊阅读(133) | 评论 (0) | 编辑收藏

DP啊，55555～

妈了个头！！

posted @ 2009-04-12 00:42 杨磊阅读(233) | 评论 (0) | 编辑收藏

Blogjava的代码字体真丑……

等老子学好了J2EE，俺也要自己写一个blog程序

posted @ 2009-04-10 18:04 杨磊阅读(109) | 评论 (0) | 编辑收藏

感叹一下C++和Java的速度对比

真的可以用天差地别来形容啊，基本上差一个数量级

所以现在对C++还是有点留恋的，不舍得完全放弃掉

其实能把C++这么灵活的语言运用的灵活的程序员才是真正有水平的

而且C++在组织很多数据结构上确实比Java要舒服一点

可能是因为C++毕竟是从面向过程的C扩展而来的吧

不知道我这种说话会不会被人喷……

有空还是捡一下C++吧

posted @ 2009-04-09 16:51 杨磊阅读(420) | 评论 (0) | 编辑收藏

Eulerian Tour

1 # circuit is a global array
2    find_euler_circuit
3      circuitpos = 0
4      find_circuit(node 1)
5
6 # nextnode and visited is a local array
7 # the path will be found in reverse order
8   find_circuit(node i)
9
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
20

posted @ 2009-04-04 10:21 杨磊阅读(134) | 评论 (0) | 编辑收藏

康托展开

1 unsigned long cantor(unsigned long S)
2 {
3     long x=0,i,p,k,j;
4     bool hash[8]={false};
5     for (i=8;i>=2;i--)
6     {
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

15 }
16 return x;
17 }

其实就是求全排列中，某一个排列的序号

比如321，对应1，2，3的全排列的第6号

上面这个是8禁止存储的，有利于位操作

posted @ 2009-04-03 14:52 杨磊阅读(161) | 评论 (0) | 编辑收藏

Bellman-Ford Algo.

http://www.csanimated.com/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.
5
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
11
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
20
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"
27

An implementation from wiki

1 #include <limits.h>
2 #include <stdio.h>
3 #include <stdlib.h>
4
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)
8
9 typedef struct {
10     int source;
11     int dest;
12     int weight;
13 } Edge;
14
15 void BellmanFord(Edge edges[], int edgecount, int nodecount, int source)
16 {
17     int *distance = malloc(nodecount * sizeof *distance);
18     int i, j;
19
20     for (i=0; i < nodecount; ++i)
21       distance[i] = INFINITY;
22     distance[source] = 0;
23
24     for (i=0; i < nodecount; ++i) {
25        int somethingchanged = 0;
26        for (j=0; j < edgecount; ++j) {
27             if (distance[edges[j].source] != INFINITY) {
28                 int new_distance = distance[edges[j].source] + edges[j].weight;
29                 if (new_distance < distance[edges[j].dest]) {
30                   distance[edges[j].dest] = new_distance;
31                   somethingchanged = 1;
32                 }
33             }
34         }
35         /* if one iteration had no effect, further iterations will have no effect either */
36         if (!somethingchanged) break;
37     }
38
39     for (i=0; i < edgecount; ++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         }
45     }
46
47     for (i=0; i < nodecount; ++i) {
48         printf("The shortest distance between nodes %d and %d is %d\n",
49             source, i, distance[i]);
50     }
51
52     free(distance);
53     return;
54 }
55
56 int main(void)
57 {
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;
64 }

posted @ 2009-04-03 14:09 杨磊阅读(245) | 评论 (0) | 编辑收藏

QSort Algo.

  1 /*************************************************************************
  2  *  Compilation:  javac QuickSort.java
  3  *  Execution:    java QuickSort N
  4  *
  5  *  Generate N random real numbers between 0 and 1 and quicksort them.
  6  *
  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).
14  *
15  *************************************************************************/
16
17 public class QuickSort {
18     private static long comparisons = 0;
19     private static long exchanges   = 0;
20
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);
27     }
28
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);
35     }
36
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 = right;
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;
51     }
52
53     // is x < y ?
54     private static boolean less(double x, double y) {
55         comparisons++;
56         return (x < y);
57     }
58
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] = swap;
65     }
66
67     // shuffle the array a[]
68     private static void shuffle(double[] a) {
69         int N = a.length;
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         }
74     }
75
76
77
78     // test client
79     public static void main(String[] args) {
80         int N = Integer.parseInt(args[0]);
81
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");
90
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");
97
98         // print statistics
99         System.out.println("Comparisons: " + comparisons);
100         System.out.println("Exchanges:   " + exchanges);
101     }
102 }
103

posted @ 2009-04-01 15:49 杨磊阅读(149) | 评论 (0) | 编辑收藏

Prim Algo.

  # 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 tree; 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

posted @ 2009-04-01 13:16 杨磊阅读(121) | 评论 (0) | 编辑收藏

人生悲凉莫过于写了200行代码最后发现TLE

摘要: 留个纪念吧 Code highlighting produced by Actipro CodeHighlighter (freeware) http://www.CodeHighlighter.com/ --> 1 import java.io.*; 2 import java.util... 阅读全文

posted @ 2009-03-31 18:08 杨磊阅读(179) | 评论 (0) | 编辑收藏

Dijkstra's algorithm & The Floyd-Warshall Algorithm

# 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 source; 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)

posted @ 2009-03-30 20:44 杨磊阅读(243) | 评论 (0) | 编辑收藏

DP啊，为啥我还是不会呢……

高中的时候对DP就没有感觉，到现在还是不行，尽管对于递推这种东西已经比原来有感觉的多了

但是还是没办法弄出来状态划分啊什么的，难道真的需要多做题积累经验么

一直觉得DP是很神奇的东西，因为感觉很玄乎，不像其他的算法那样，基本都有固定套路的

DP相对来说很灵活，也正是如此所以难以掌握吧

没办法啦，还是多多努力吧，多做题，多见识一下，大概就能掌握了

熟能生巧么，谁让我天生没长懂DP的脑袋呢

Dev+Algo两不误，我的追求

posted @ 2009-03-29 22:55 杨磊阅读(122) | 评论 (0) | 编辑收藏

Unit Testing Tips from TopCoder

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 smallest functions possible; this way, it is clear which areas of the component are failing. You can then use the number of tests passing and failing as a completion metric, as well.
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 state they found it in; 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 members.
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.

posted @ 2009-03-28 21:38 杨磊阅读(145) | 评论 (0) | 编辑收藏

抽屉原理

对一块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个格中必至少有两格同色.如果有两格为白色，则与第二行构成四角白色的长方形；如果没有两格白色，那么必有两格为黑色，则与第一行构成四角黑色的长方形。

posted @ 2009-03-03 14:34 杨磊阅读(287) | 评论 (0) | 编辑收藏

今天开始看The Art of Computer Programming

att

posted @ 2009-02-28 00:08 杨磊阅读(164) | 评论 (0) | 编辑收藏

二维图最大匹配--匈牙利算法

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);
        }
}

posted @ 2009-02-25 14:42 杨磊阅读(162) | 评论 (0) | 编辑收藏

Problems Left To Do

SRM144 DIV1 1100	图形学

posted @ 2009-02-20 23:50 杨磊阅读(102) | 评论 (0) | 编辑收藏

Games Wanted To Play

X	Titan Quest
V	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....

有朝一日希望我有机会能玩上这些游戏，但我估计是梦想了

“游戏你的游戏，不要被游戏所游戏”

posted @ 2009-02-16 18:41 杨磊阅读(100) | 评论 (0) | 编辑收藏

Endianness from wikipedia

http://en.wikipedia.org/wiki/Endianness

posted @ 2009-02-14 00:27 杨磊阅读(166) | 评论 (0) | 编辑收藏

Big and Little Endian zz from UMD

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". Each 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 byte. 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 90AB12CD₁₆, 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 address. Here's how it would look:

Address	Value
1000	90
1001	AB
1002	12
1003	CD

Little Endian

In little endian, you store the least significant byte in the smallest address. Here's how it would look:

Address	Value
1000	CD
1001	12
1002	AB
1003	90

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. I only 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 problems. This is even worse over the network, because you might not be able to determine the endianness of the machine that sent you the data.

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, little endian), while others prefer to eat from the big end (thus, big endians) and how this lead to various wars.

Of course, the point was to say that it was a silly thing to debate over, and yet, people argue over such trivialities all the time (for example, should braces line in parallel or not? vi or emacs? UNIX or Windows).

Misconceptions

Endianness only makes sense when you want to break a large value (such as a word) into several small ones. You must decide on an order to place it in memory.

However, if you have a 32 bit register storing a 32 bit value, it makes no sense to talk about endianness. The register is neither big endian nor little endian. It's just a register holding a 32 bit value. The rightmost bit is the least significant bit, and the leftmost bit is the most significant bit.

There's no reason to rearrange the bytes in a register in some other way.

Endianness only makes sense when you are breaking up a multi-byte quantity, and attempting to store the bytes at consecutive memory locations. In a register, it doesn't make sense. A register is simply a 32 bit quantity, b₃₁....b₀, and endianness does not apply to it.

With regard to endianness, You may argue there's a very natural way to store 4 bytes in 4 consecutive addresses, and that the other way looks strange. In particular, it looks "backwards". However, what's natural to you may not be natural to someone else. The fact of the matter is that the word is split in 4 bytes, and most people would agree that you need some order to place it in memory.

C-style strings

Once you start thinking about endianness, you begin to think it applies to everything. Before you see big or little endian, you may have had no idea it even existed. That's because it's reasonably well-hidden from you.

If you do bitwise/bitshift operations on an int, you don't notice the endianness. The machine arranges the multiple bytes so the least significant byte is still the least significant byte (e.g., b_7-0) and the most significant byte is still the most significant byte (e.g., b_31-24).

So, it's natural to think whether strings might be saved in some sort of strange order, depending on the machine.

This is where it's useful to think about all the facts you know about arrays. A C-style string, after all, is still an array of characters.

Here are some facts you should know about C-style strings and arrays.

C-style strings are stored in arrays of characters.
Each character requires one byte of memory, since characters are represented in ASCII (in the future, this could change, as Unicode becomes more popular).
In an array, the address of consecutive array elements increases. Thus, & arr[ i ] is less than & arr[ i + 1 ].
What's not as obvious is that if something is stored in increasing addresses in memory, it's going to be stored in increasing "addresses" in a file. When you write to a file, you usually specify an address in memory, and the number of bytes you wish to write to the file starting at that address.

So, let's imagine some C-style string in memory. You have the word "cat". Let's pretend 'c' is stored at address 1000. Then 'a' is stored at 1001. 't' is at 1002. The null character '"0' is at 1003.

Since C-style strings are arrays of characters, they follow the rules of characters. Unlike int or long, you can easily see the individual bytes of a C-style string, one byte at a time. You use array indexing to access the bytes (i.e., characters) of a string. You can't easily index the bytes of an int or long, without playing some pointer tricks (using reinterpret cast, for example, in C++). The individual bytes of an int are more or less hidden from you.

Now imagine writing out this string to a file using some sort of write() method. You specify a pointer to 'c', and the number of bytes you wish to print (in this case 4). The write() method proceeds byte by byte in the character string and writes it to the file, starting with 'c' and working to the null character.

Given that explanation, is it clear whether endianness matters with C-style strings? Hopefully, it is clear.

As an aside, since C++ strings are objects, it may have complicated inner structures, and so it's less obvious what a C++ string would look like when print out to a file. It's well-known what a C-style string looks like (a sequence of characters ending in a null character), which is why I've been careful to call them C-style strings.

posted @ 2009-02-14 00:25 杨磊阅读(226) | 评论 (0) | 编辑收藏

Space Ranger 2 Reboot Text Quest

摘要: Feeding the xenomorphs

While landing a local caretaker tells you that a little mischievous xenomorph
mixed up the tablets showing the animals name in 5 cages around the zoo .
Read the books about their shape and feeding habits - a couple of hints in a
water of nonsense - and check the tubes with food. If you don`t like to wait 阅读全文

posted @ 2009-02-13 10:18 杨磊阅读(2866) | 评论 (0) | 编辑收藏

Point Quadtree

摘要: 高级数据库的大作业，水过，代码写的不是很好，主要是处理I/O这块，没有找到更好的办法，时间问题，所以只能妥协了可能我做的这个Quadtree比较奇怪，具体的可以参考UMD的那个Spatial Demo 网址如下：http://donar.umiacs.umd.edu/quadtree/ 贴一下代码好了，有需要的人可以跟我一起讨论，以后如果有机会会改进这个代码的 IO操作类... 阅读全文

posted @ 2009-01-15 09:59 杨磊阅读(341) | 评论 (0) | 编辑收藏

Theory of Computation

set of all finite subsets of N is countably infinite.

To be proved....

posted @ 2008-12-28 21:29 杨磊阅读(106) | 评论 (0) | 编辑收藏

Smack Jabber Client

摘要: 阅读全文

posted @ 2008-11-15 15:37 杨磊阅读(1097) | 评论 (0) | 编辑收藏

CMOS CCD

有鉴于许多网友询问 CCD 与 CMOS 的主要差别。我们暂时撇开复杂的技术文字，透过简单的比较来看这两种不同类型，作用相同的影像感光元件。
不管，CCD 或 CMOS，基本上两者都是利用矽感光二极体（photodiode）进行光与电的转换。这种转换的原理与各位手上具备“太阳电能”电子计算机的“太阳能电池”效应相近，光线越强、电力越强；反之，光线越弱、电力也越弱的道理，将光影像转换为电子数字信号。

比较 CCD 和 CMOS 的结构，ADC的位置和数量是最大的不同。简单的说，按我们在上一讲“CCD 感光元件的工作原理（上）”中所提之内容。CCD每曝光一次，在快门关闭后进行像素转移处理，将每一行中每一个像素（pixel）的电荷信号依序传入“缓冲器”中，由底端的线路引导输出至 CCD 旁的放大器进行放大，再串联 ADC 输出；相对地，CMOS 的设计中每个像素旁就直接连着 ADC（放大兼类比数字信号转换器），讯号直接放大并转换成数字信号。

两者优缺点的比较

CCD CMOS
设计单一感光器感光器连接放大器
灵敏度同样面积下高感光开口小，灵敏度低
成本线路品质影响程度高，成本高 CMOS整合集成，成本低
解析度连接复杂度低，解析度高低，新技术高
噪点比单一放大，噪点低百万放大，噪点高
功耗比需外加电压，功耗高直接放大，功耗低

由于构造上的基本差异，我们可以表列出两者在性能上的表现之不同。CCD的特色在于充分保持信号在传输时不失真（专属通道设计），透过每一个像素集合至单一放大器上再做统一处理，可以保持资料的完整性；CMOS的制程较简单，没有专属通道的设计，因此必须先行放大再整合各个像素的资料。

整体来说，CCD 与 CMOS 两种设计的应用，反应在成像效果上，形成包括 ISO 感光度、制造成本、解析度、噪点与耗电量等，不同类型的差异：

ISO 感光度差异：由于 CMOS 每个像素包含了放大器与A/D转换电路，过多的额外设备压缩单一像素的感光区域的表面积，因此相同像素下，同样大小之感光器尺寸，CMOS的感光度会低于CCD。

成本差异：CMOS 应用半导体工业常用的 MOS制程，可以一次整合全部周边设施于单晶片中，节省加工晶片所需负担的成本和良率的损失；相对地 CCD 采用电荷传递的方式输出资讯，必须另辟传输通道，如果通道中有一个像素故障（Fail），就会导致一整排的讯号壅塞，无法传递，因此CCD的良率比CMOS低，加上另辟传输通道和外加 ADC 等周边，CCD的制造成本相对高于CMOS。

解析度差异：在第一点“感光度差异”中，由于 CMOS 每个像素的结构比 CCD 复杂，其感光开口不及CCD大，相对比较相同尺寸的CCD与CMOS感光器时，CCD感光器的解析度通常会优于CMOS。不过，如果跳脱尺寸限制，目前业界的CMOS 感光原件已经可达到1400万像素 / 全片幅的设计，CMOS 技术在量率上的优势可以克服大尺寸感光原件制造上的困难，特别是全片幅 24mm-by-36mm 这样的大小。

噪点差异：由于CMOS每个感光二极体旁都搭配一个 ADC 放大器，如果以百万像素计，那么就需要百万个以上的 ADC 放大器，虽然是统一制造下的产品，但是每个放大器或多或少都有些微的差异存在，很难达到放大同步的效果，对比单一个放大器的CCD，CMOS最终计算出的噪点就比较多。

耗电量差异：CMOS的影像电荷驱动方式为主动式，感光二极体所产生的电荷会直接由旁边的电晶体做放大输出；但CCD 却为被动式，必须外加电压让每个像素中的电荷移动至传输通道。而这外加电压通常需要12伏特（V）以上的水平，因此 CCD 还必须要有更精密的电源线路设计和耐压强度，高驱动电压使 CCD 的电量远高于CMOS。

尽管 CCD 在影像品质等各方面均优于CMOS，但不可否认的CMOS具有低成本、低耗电以及高整合度的特性。由于数码影像的需求热烈，CMOS的低成本和稳定供货，成为厂商的最爱，也因此其制造技术不断地改良更新，使得 CCD 与 CMOS 两者的差异逐渐缩小。新一代的CCD朝向耗电量减少作为改进目标，以期进入照相手机的行动通讯市场；CMOS系列，则开始朝向大尺寸面积与高速影像处理晶片统合，藉由后续的影像处理修正噪点以及画质表现，特别是 Canon 系列的 EOS D30 、EOS 300D 的成功，足见高速影像处理晶片已经可以胜任高像素 CMOS 所产生的影像处理时间与能力的缩短；另外，大尺寸全片幅则以 Kodak DCS Pro14n、DCS Pro/n、DCS Pro/c 这一系列的数码机身为号召，CMOS未来跨足高阶的影像市场产品，前景可期。

posted @ 2008-11-14 16:28 杨磊阅读(118) | 评论 (0) | 编辑收藏

Introduction:

The introduction is the most important part of the essay, especially the first sentence. The first sentence introduces your essay and a bad introduction, in person or in writing, is detrimental to your admissions chances.
Keep the reader interested by making them continue to read your essay after reading the first paragraph.
The first sentence should be unique and compelling, possibly thought provoking or attention-grabbing.
First sentences may explain your desire to study the subject of interest or discuss the motivation that influenced your desire to study the subject of interest. State it in a creative manner.
The sentences following the first sentence should provide a brief explanation that supports the claim stated in the first sentence.

The Body:

The body should include several paragraphs (usually about 3) that provide detailed evidence to support the statement made in the introductory paragraph. The paragraphs should flow by using transitions and resolutions.
Each paragraph should have a transition, which starts each paragraph with a topic statement that will be the theme of that paragraph (See more on transitions and resolutions below).
Each paragraph should have a resolution, which ends each paragraph with a meaningful sentence that provides a transition to the next paragraph (See more on transitions and resolutions below).
Experiences, accomplishments, or any other evidence that can support your claims should be included in the body. Future goals should also be mentioned in the body.
A short summary of your educational background can be discussed in the 1st paragraph.
Personal experiences and the reasons for wanting to attend the school can be discussed in the 2nd paragraph.
Do not repeat what was stated in the application.
The last paragraph should explain why you should be accepted.[/li

Conclusion:

The conclusion is the last paragraph of the personal statement.
State why you are interested in studying the subject of interest.
State the key points mentioned in the body, such as your experiences or accomplishments, that explain your interest in the subject. State it in a conclusive and brief manner.
End on a positive note with one or two attention-grabbing sentences.

Do:

Prepare an outline and create a draft.
Answer all the questions being asked.
Make sure your essay has a theme or a thesis.
Provide evidence to support your claims.
Make your introduction unique.
Write clearly and make sure it is easy to read.
Be honest, confident, and be yourself.
Be interesting and positive.
Make sure your essay is organized, coherent, and concise.
Write about yourself and use examples from your own life experiences.
Use a mixture of long and short sentences.
Discuss your future goals.
Mention any hobbies, past jobs, community service, or research experience.
Speak in the first person (I…).
Mention weaknesses without making excuses.
Discuss why you're interested in the school and/or program.
Show, don’t tell (Use examples to demonstrate your abilities).
Ask for help.
Proofread and revise your statement at least 3 times.
Have others proofread your essay.

Don’t:

Have any grammar or spelling errors. (Proofread!)
Be wordy or use jargon (don’t try to impress the readers by using big words).
Swear or use slang.
Digress or be repetitive.
Be boring.
Generalize.
Include cliches.
Use gimmicks.
Be comical (a little humor is okay but remember it can be misconstrued).
Be defensive or arrogant.
Complain.
Preach.
Have your essay focus too much on other individuals.
Discuss politics or religion.
Give excuses for a low GPA.
Make lists of accomplishments, awards, skills, or personal qualities (Show, don’t tell).
Write a term paper or an autobiography.
Summarize your resume.
Include information already cited on the application.
Forget to proofread.

posted @ 2008-11-07 15:07 杨磊阅读(203) | 评论 (0) | 编辑收藏

Java XML 读写

用的是DOM，代码丑了一点，将就着看吧，不过还是能用的

  1 import java.io.File;
  2 import java.io.FileOutputStream;
  3 import java.io.IOException;
  4 import java.io.PrintWriter;
  5 import javax.xml.parsers.DocumentBuilder;
  6 import javax.xml.parsers.DocumentBuilderFactory;
  7 import javax.xml.parsers.ParserConfigurationException;
  8 import javax.xml.transform.OutputKeys;
  9 import javax.xml.transform.Transformer;
10 import javax.xml.transform.TransformerException;
11 import javax.xml.transform.TransformerFactory;
12 import javax.xml.transform.dom.DOMSource;
13 import javax.xml.transform.stream.StreamResult;
14 import org.w3c.dom.Document;
15 import org.w3c.dom.Element;
16 import org.w3c.dom.Node;
17 import org.w3c.dom.NodeList;
18 import org.xml.sax.SAXException;
19
20 public class ChatRecord {
21
22     private Document document;
23     private String filename;
24     Element root;
25
26     public ChatRecord (String name)
27     {
28         filename = name;
29     }
30
31     /*
32      * If there is no chat record, we should start a new one
33      * But make sure that this method will only be executed ONCE!!!
34      */
35     public void startNewRecord() throws ParserConfigurationException
36     {
37         DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
38         DocumentBuilder builder = factory.newDocumentBuilder();
39         document = builder.newDocument();
40         root = document.createElement("ChatRecord");
41         document.appendChild(root);
42         toSave();
43     }
44
45     /*
46      * Save the XML to disk
47      */
48     public void toSave(){
49         try{
50           TransformerFactory tf = TransformerFactory.newInstance();
51           Transformer transformer = tf.newTransformer();
52           DOMSource source = new DOMSource(document);
53           transformer.setOutputProperty(OutputKeys.ENCODING,"GB2312");
54           //transformer.setOutputProperty(OutputKeys.INDENT,"yes");
55           PrintWriter pw = new PrintWriter(new FileOutputStream(filename));
56           StreamResult result = new StreamResult(pw);
57           transformer.transform(source,result);
58           pw.close();
59           }
60         catch(TransformerException mye){
61           mye.printStackTrace();
62         }
63         catch(IOException exp){
64           exp.printStackTrace();
65         }
66     }
67
68
69     /*
70      * Read the chat record from a XML
71      */
72     public void print()
73     {
74          try {
75
76              // create DocumentBuilderFactory
77              DocumentBuilderFactory factory =
78                 DocumentBuilderFactory.newInstance();
79
80              // create DocumentBuilder
81              DocumentBuilder builder = factory.newDocumentBuilder();
82
83              // obtain document object from XML document
84              Document document = builder.parse(
85                 new File( filename) );
86
87              // get root node
88              Node root = document.getDocumentElement();
89
90              NodeList childNodes = root.getChildNodes();
91              Node currentNode;
92
93              for ( int i = 0; i < childNodes.getLength(); i++ ) {
94
95                 currentNode = childNodes.item( i );
96
97                 // print node name of each child element
98                 System.out.println( currentNode.getNodeName() + " " + currentNode.getFirstChild().getNodeValue());
99              }
100
101           }
102
103           // handle exception creating DocumentBuilder
104           catch ( ParserConfigurationException parserError ) {
105              System.err.println( "Parser Configuration Error" );
106              parserError.printStackTrace();
107           }
108
109           // handle exception reading data from file
110           catch ( IOException fileException ) {
111              System.err.println( "File IO Error" );
112              fileException.printStackTrace();
113           }
114
115           // handle exception parsing XML document
116           catch ( SAXException parseException ) {
117              System.err.println( "Error Parsing Document" );
118              parseException.printStackTrace();
119           }
120     }
121
122
123     /*
124      * If there is already a chat record
125      * use this method to update it
126      */
127     public void update(String time, String sender, String receiver, String textcontent)
128     {
129         try {
130
131          // create DocumentBuilderFactory
132          DocumentBuilderFactory factory = DocumentBuilderFactory.newInstance();
133
134          // create DocumentBuilder
135          DocumentBuilder builder = factory.newDocumentBuilder();
136
137          // obtain document object from XML document
138          document = builder.parse(
139             new File( filename ) );
140
141         Node thisroot = document.getFirstChild();
142          Element mytime = document.createElement("Time");
143         mytime.appendChild(document.createTextNode(time));
144         thisroot.appendChild(mytime);
145
146         Element Sender = document.createElement("Sender");
147         Sender.appendChild(document.createTextNode(sender));
148         thisroot.appendChild(Sender);
149
150         Element Receiver = document.createElement("Receiver");
151         Receiver.appendChild(document.createTextNode(receiver));
152         thisroot.appendChild(Receiver);
153
154         Element content = document.createElement("Content");
155         content.appendChild(document.createTextNode(textcontent));
156         thisroot.appendChild(content);
157
158         }
159      // handle exception creating DocumentBuilder
160      catch ( ParserConfigurationException parserError ) {
161         System.err.println( "Parser Configuration Error" );
162         parserError.printStackTrace();
163      }
164
165      // handle exception reading data from file
166      catch ( IOException fileException ) {
167         System.err.println( "File IO Error" );
168         fileException.printStackTrace();
169      }
170
171      // handle exception parsing XML document
172      catch ( SAXException parseException ) {
173         System.err.println( "Error Parsing Document" );
174         parseException.printStackTrace();
175      }
176     }
177 }
178

说说问题吧，因为要写一个聊天记录的XML，就好象MSN的那个聊天记录一样，于是当然要不断的续写

但是我没找到DOM的API来完成这个功能，找了很久很久，想了很多办法

最后还是用了最SB的办法，parseXML文件，append新的Element，然后重新写出去

但是这样当XML文件打了一会，为了写一条聊天记录就要进行大量的IO操作，这样现在是不合理的

其实可以直接在文件里面println，这样就不用进行那么多无用的读写了

但是我想DOM应该不至于连这么有用的API都没有吧？

其实我看DOM的API也就一个晚上，而且对DOM整体的架构还不是很了解

不知道里面的parse是怎么实现的，或许人家已经想到了我这个问题……

不知道，反正现在只能暂时这样实现了，如果真的是为了性能的考虑，那倒是可以自己写一个println的方法，直接把新的元素追加上去

有空去好好学学XML吧

JAVA还是基本功不够好啊，很多诸如I/O Stream之类的东西，里面的类都还不是很清楚

当初看得Design Pattern现在全忘光了……，真是对不起我的媳妇儿啊

Anyway，有时间再说吧……

posted @ 2008-11-05 15:53 杨磊阅读(1852) | 评论 (1) | 编辑收藏

Schedule

成绩单	Done
GT	Done
推荐信	Done
PS	Done
网申	Done

posted @ 2008-10-07 17:46 杨磊阅读(91) | 评论 (0) | 编辑收藏

GRE Argue 证明调查不可靠的句型

The author provides no evidence that the study's results are statistically reliable. In order to establish a strong correlation between..., the study's sample must be sufficient in size and representative of ... Lack evidence of a sufficiently representative sample, the author cannot justifiably rely on the study to draw any conclusion whatsoever.

posted @ 2008-08-20 16:19 杨磊阅读(178) | 评论 (0) | 编辑收藏

Digital Micromirror Device

A Digital Micromirror Device, or DMD is an optical semiconductor that is the core of DLP projection technology, and was invented by Dr. Larry Hornbeck and Dr. William E. "Ed" Nelson of Texas Instruments (TI) in 1987.

The DMD project began as the Deformable Mirror Device in 1977, using micromechanical, analog light modulators. The first analog DMD product was the TI DMD2000 airline ticket printer that used a DMD instead of a laser scanner.

A DMD chip has on its surface several hundred thousand microscopic mirrors arranged in a rectangular array which correspond to the pixels in the image to be displayed. The mirrors can be individually rotated ±10-12°, to an on or off state. In the on state, light from the projector bulb is reflected into the lens making the pixel appear bright on the screen. In the off state, the light is directed elsewhere (usually onto a heatsink), making the pixel appear dark.

To produce greyscales, the mirror is toggled on and off very quickly, and the ratio of on time to off time determines the shade produced (binary pulse-width modulation). Contemporary DMD chips can produce up to 1024 shades of gray. See DLP for discussion of how color images are produced in DMD-based systems.

The mirrors themselves are made out of aluminium and are around 16 micrometres across. Each one is mounted on a yoke which in turn is connected to two support posts by compliant torsion hinges. In this type of hinge, the axle is fixed at both ends and literally twists in the middle. Because of the small scale, hinge fatigue is not a problem and tests have shown that even 1 trillion (10¹²) operations do not cause noticeable damage. Tests have also shown that the hinges cannot be damaged by normal shock and vibration, since it is absorbed by the DMD superstructure.

Two pairs of electrodes control the position of the mirror by electrostatic attraction. Each pair has one electrode on each side of the hinge, with one of the pairs positioned to act on the yoke and the other acting directly on the mirror. The majority of the time, equal bias charges are applied to both sides simultaneously. Instead of flipping to a central position as one might expect, this actually holds the mirror in its current position. This is because attraction force on the side the mirror is already tilted towards is greater, since that side is closer to the electrodes.

To move the mirrors, the required state is first loaded into an SRAM cell located beneath each pixel, which is also connected to the electrodes. Once all the SRAM cells have been loaded, the bias voltage is removed, allowing the charges from the SRAM cell to prevail, moving the mirror. When the bias is restored, the mirror is once again held in position, and the next required movement can be loaded into the memory cell.

The bias system is used because it reduces the voltage levels required to address the pixels such that they can be driven directly from the SRAM cell, and also because the bias voltage can be removed at the same time for the whole chip, so every mirror moves at the same instant. The advantages of the latter are more accurate timing and a more filmic moving image.

posted @ 2008-08-17 14:33 杨磊阅读(245) | 评论 (0) | 编辑收藏

LCD原理

（一）液晶的物理特性

液晶的物理特性是：当通电时导通，排列变的有秩序，使光线容易通过；不通电时排列混乱，阻止光线通过。让液晶如闸门般地阻隔或让光线穿透。从技术上简单地说，液晶面板包含了两片相当精致的无钠玻璃素材，称为 Substrates，中间夹著一层液晶。当光束通过这层液晶时，液晶本身会排排站立或扭转呈不规则状，因而阻隔或使光束顺利通过。大多数液晶都属于有机复合物，由长棒状的分子构成。在自然状态下，这些棒状分子的长轴大致平行。将液晶倒入一个经精良加工的开槽平面，液晶分子会顺着槽排列，所以假如那些槽非常平行，则各分子也是完全平行的。

（二）单色液晶显示器的原理

LCD技术是把液晶灌入两个列有细槽的平面之间。这两个平面上的槽互相垂直(相交成90度)。也就是说，若一个平面上的分子南北向排列，则另一平面上的分子东西向排列，而位于两个平面之间的分子被强迫进入一种90度扭转的状态。由于光线顺着分子的排列方向传播，所以光线经过液晶时也被扭转90度。但当液晶上加一个电压时，分子便会重新垂直排列，使光线能直射出去，而不发生任何扭转。

LCD是依赖极化滤光器(片)和光线本身。自然光线是朝四面八方随机发散的。极化滤光器实际是一系列越来越细的平行线。这些线形成一张网，阻断不与这些线平行的所有光线。极化滤光器的线正好与第一个垂直，所以能完全阻断那些已经极化的光线。只有两个滤光器的线完全平行，或者光线本身已扭转到与第二个极化滤光器相匹配，光线才得以穿透。（如图1）

图1 光线穿透示意图

LCD正是由这样两个相互垂直的极化滤光器构成，所以在正常情况下应该阻断所有试图穿透的光线。但是，由于两个滤光器之间充满了扭曲液晶，所以在光线穿出第一个滤光器后，会被液晶分子扭转90度，最后从第二个滤光器中穿出。另一方面，若为液晶加一个电压，分子又会重新排列并完全平行，使光线不再扭转，所以正好被第二个滤光器挡住。总之，加电将光线阻断，不加电则使光线射出。（如图2）

图2 光线阻断示意图

然而，可以改变LCD中的液晶排列，使光线在加电时射出，而不加电时被阻断。但由于计算机屏幕几乎总是亮着的，所以只有“加电将光线阻断”的方案才能达到最省电的目的。

从液晶显示器的结构来看，无论是笔记本电脑还是桌面系统，采用的LCD显示屏都是由不同部分组成的分层结构。LCD由两块玻璃板构成，厚约1mm，其间由包含有液晶(LC)材料的5μm均匀间隔隔开。因为液晶材料本身并不发光，所以在显示屏两边都设有作为光源的灯管，而在液晶显示屏背面有一块背光板（或称匀光板）和反光膜，背光板是由荧光物质组成的可以发射光线，其作用主要是提供均匀的背景光源。背光板发出的光线在穿过第一层偏振过滤层之后进入包含成千上万水晶液滴的液晶层。液晶层中的水晶液滴都被包含在细小的单元格结构中，一个或多个单元格构成屏幕上的一个像素。在玻璃板与液晶材料之间是透明的电极，电极分为行和列，在行与列的交叉点上，通过改变电压而改变液晶的旋光状态，液晶材料的作用类似于一个个小的光阀。在液晶材料周边是控制电路部分和驱动电路部分。当LCD中的电极产生电场时，液晶分子就会产生扭曲，从而将穿越其中的光线进行有规则的折射，然后经过第二层过滤层的过滤在屏幕上显示出来。
（三）彩色LCD显示器的工作原理

对于笔记本电脑或者桌面型的LCD显示器需要采用的更加复杂的彩色显示器而言，还要具备专门处理彩色显示的色彩过滤层。通常，在彩色LCD面板中，每一个像素都是由三个液晶单元格构成，其中每一个单元格前面都分别有红色，绿色，或蓝色的过滤器。这样，通过不同单元格的光线就可以在屏幕上显示出不同的颜色。

LCD克服了CRT体积庞大、耗电和闪烁的缺点，但也同时带来了造价过高、视角不广以及彩色显示不理想等问题。CRT显示可选择一系列分辨率，而且能按屏幕要求加以调整，但LCD屏只含有固定数量的液晶单元，只能在全屏幕使用一种分辨率显示(每个单元就是一个像素)。

CRT通常有三个电子枪，射出的电子流必须精确聚集，否则就得不到清晰的图像显示。但LCD不存在聚焦问题，因为每个液晶单元都是单独开关的。这正是同样一幅图在LCD屏幕上为什么如此清晰的原因。LCD也不必关心刷新频率和闪烁，液晶单元要么开，要么关，所以在40～60Hz这样的低刷新频率下显示的图像不会比75Hz下显示的图像更闪烁。不过，LCD屏的液晶单元会很容易出现暇疵。对1024×768的屏幕来说，每个像素都由三个单元构成，分别负责红、绿和蓝色的显示一所以总共约需240万个单元(1024×768×3＝2359296)。很难保证所有这些单元都完好无损。最有可能的是，其中一部分己经短路(出现“亮点”)，或者断路(出现“黑点”)。所以说，并不是如此高昂的显示产品并不会出现瑕疵。

LCD显示屏包含了在 CRT技术中未曾用到的一些东西。为屏幕提供光源的是盘绕在其背后的荧光管。有些时候，会发现屏幕的某一部分出现异常亮的线条。也可能出现一些不雅的条纹，一幅特殊的浅色或深色图像会对相邻的显示区域造成影响。此外，一些相当精密的图案(比如经抖动处理的图像)可能在液晶显示屏上出现难看的波纹或者干扰纹。

现在，几乎所有的应用于笔记本或桌面系统的LCD都使用薄膜晶体管（TFT）激活液晶层中的单元格。TFT LCD技术能够显示更加清晰，明亮的图象。早期的LCD由于是非主动发光器件，速度低，效率差，对比度小，虽然能够显示清晰的文字，但是在快速显示图象时往往会产生阴影，影响视频的显示效果，因此，如今只被应用于需要黑白显示的掌上电脑，呼机或手机中。

随着技术的日新月异，LCD技术也在不断发展进步。目前各大LCD显示器生产商纷纷加大对LCD的研发费用，力求突破LCD的技术瓶颈，进一步加快LCD显示器的产业化进程、降低生产成本，实现用户可以接受的价格水平。
（四）应用与液晶显示器的新技术

（1）采用TFT型Active素子进行驱动

为了创造更优质画面构造，新技术采用了用独有TFT型Active素子进行驱动。大家都知道，异常复杂的液晶显示屏幕中最重要的组成部分除了液晶之外，就要算直接关系到液晶显示亮度的背光屏以及负责产生颜色的色滤光镜。在每一个液晶像素上加装上了Active素子来进行点对点控制，使得显示屏幕与全统的 CRT显示屏相比有天壤之别，这种控制模式在显示的精度上，会比以往的控制方式高得多，所以就在CRT显示屏会上出现图像的品质不良，色渗以及抖动非常厉害的现象，但在加入了新技术的LCD显示屏上观看时其画面品质却是相当赏心悦目的。

（2）利用色滤光镜制作工艺创造色彩斑澜的画面

在色滤光镜本体还没被制作成型以前，就先把构成其主体的材料加以染色，之后再加以灌膜制造。这种工艺要求有非常高的制造水准。但与同其他普通的LCD显示屏相比，用这种类型的制造出来的LCD，无论在解析度，色彩特性还是使用的寿命来说，都有着非常优异的表现。从而使LCD能在高分辨率环境下创造色彩斑澜的画面。

（3）低反射液晶显示技术

众所周知，外界光线对液晶显示屏幕具有非常大的干扰，一些LCD显示屏，在外界光线比较强的时候，因为它表面的玻璃板产生反射，而干扰到它的正常显示。因此在室外一些明亮的公共场所使用时其性能和可观性会大大降低。目前很多LCD 显示器即使分辨率再高，其反射技术没处理好，由此对实际工作中的应用都是不实用的。单凭一些纯粹的数据，其实是一种有偏差的去引导用户的行为。而新款的 LCD显示器就采用的“低反射液晶显示屏幕”技术就是在液晶显示屏的最外层施以反射防止涂装技术（AR coat），有了这一层涂料，液晶显示屏幕所发出的光泽感、液晶显示屏幕本身的透光率、液晶显示屏幕的分辨率、防止反射等这四个方面都但到了更好的改善。

（4）先进的“连续料界结晶矽”液晶显示方式

在一些LCD产品中，在观看动态影片的时候会出现画面的延迟现象，这是由于整个液晶显示屏幕的像素反应速度显得不足所造成的。为了提高像素反应速度，新技术的LCD采用目前最先进的Si TFT液晶显示方式，具有比旧式LCD屏快600倍的像素反应速度，效果真是不可同日而语。先进的“连续料界结晶矽”技术是利用特殊的制造方式，把原有的非结晶型透明矽电极，在以平常速率600倍的速度下进行移动，从而大大加快了液晶屏幕的像素反应速度，减少画面出现的延缓现象。

现在，低温多晶硅技术、反射式液晶材料的研究已经进入应用阶段，也会使LCD的发展进入一个崭新的时代。而在液晶显示器不断发展的同时，其它平面显示器也在进步中，等离子体显示器（PDP）、场致发光阵列显示器（FED）和发光聚合体显示器（LEP）的技术将在未来掀起平板显示器的新浪潮。其中，最值得关注和看好的就是场致显示器，它具有许多比液晶显示器更出色的性能……不过可以断定，LCD显示技术进入新纪元，作为另一支显示产品的生力军，它们将可能取代 CRT显示器。

posted @ 2008-08-17 13:37 杨磊阅读(1374) | 评论 (0) | 编辑收藏

DLP投影机原理

1987年，德州仪器公司的工程师拉里•霍恩贝克发明了数字微镜器件（Digital Micromirror Device，DMD），以这种器件为核心的DLP（Digital Light Processing，数字光学处理）投影机和DLP电视机早在1996年就被TI公司开发出来了，微软即将推出的Surface电脑就使用了这种投影机。

Larry J. Hornbeck

拉里•霍恩贝克目前为德州仪器数码影像院士，在1974年取得美国凯斯西储大学（Case Western Reserve大学）的固态物理学博士学位。由于发明与研发DMD技术，因此于1998年得到美国电视艺术及科学学会所颁发的艾美奖。霍恩贝克目前拥有电荷耦合元件（CCD）、红外线影像传感器（IR image sensor）以及DMD技术等30多个专利，其中包含DMD的基础专利。

DMD单元的内部结构

DMD芯片上有数百万个微小的反射镜片，数字信号会激活镜片下面的微型电极，推动镜面迎向或避开光源，从而将光线从两个方向反射出去。

反光镜的倾斜角度可以调整

实际的反射方向则视底层记忆晶胞的状态而定，当记忆晶胞处于“ON”状态时，反射镜会旋转至+10度，若记忆晶胞处于“OFF”状态，反射镜会旋转至-10度。

反射角度的改变导致了光的选择性，使得屏幕出现不同灰度的像素

只要结合DMD以及适当光源和投影光学系统，反射镜就会把入射光反射进入或是离开投影镜头的透光孔，使得“ON”状态的反射镜看起来非常明亮，“OFF”状态的反射镜看起来就很黑暗。

彩色DLP投影机的组成

利用二位脉冲宽度调变可以得到灰阶效果，如果使用固定式或旋转式彩色滤镜，再搭配一颗或三颗DMD芯片，即可得到彩色显示效果。

高亮、高清的DLP放映机

想要深入了解DLP技术，推荐你（1）阅读BenQ测试实验室的文章深入DLP™技术；（2）如果你的英文阅读能力还行，可以读Howstuffworks网站上的文章How DLP Sets Work，这篇文章附有十多幅非常漂亮的插图；（3）你还可以去DLP官方网站上观看介绍DLP技术原理的视频，中文配音，图文并茂。

posted @ 2008-08-17 13:10 杨磊阅读(1762) | 评论 (0) | 编辑收藏

GRE Argument 模板一

In this memo the chairperson of the Saluda school board recommends hiring Schade, Steel City High's music director for the past five years, to plan and direct the school district's general music-education programs. To support this recommendation the chairperson points out that over the past five years Steel's band has won three regional awards and that the school's facilities and instruments have improved markedly. However, close scrutiny of this evidence reveals that it lends little support for the recommendation.
In this memo, the superintendent of the Mylar school district concludes that by providing breakfast to all its students the district would reduce tardiness and absenteeism as well as improve the overall academic performance of its students. To support this conclusion the superintendent points out that during a 6-month trial program involving 100 students ranging in age from 5 to 12, theses students were less likesly to be taardy or absent than other students. The superintendent also cites the well-known fact that eating healthful breakfasts on a regular basic improves academic performance. The superintendent's argument is problematic in several respects, rendering the argument unconvincing as it stands.

看上去还算是比较有用的模板，好多范文都在用这个模板开头，暂且留下备用

posted @ 2008-08-16 15:42 杨磊阅读(1268) | 评论 (0) | 编辑收藏

GRE ARGUMENT 25 范文一篇

In this memo, Hopewell's mayor recommends that in order to stimulate the town's economy and boost tax revenues Hopewell should build a new golf course and resort hotel, just as the town of Ocean view did two years ago. To support this recommendation the mayor points out that in Ocean View during the last two years tourism has increased, new businesses have opened, and tax revenues have increased by 30%. I find the mayor's argument unconvincing in several important respects.

First of all, it is possible that mayor have confused cause with effect respecting the recent developments in Ocean View. Perhaps Ocean View's construction of a new golf course and hotel was a response to previous increases in tourism and business development--increases that have simply continued during the most recent two years. Since the mayor has failed to account for this possibility, the claim that Hopewell would boost its economy by also constructing a golf course and hotel is completely unwarranted.

Secondly, the mayor fails to account for other possible causes of the trends in Ocean View during the last two years. The increase in tourism might have been due to improving economic conditions nationwide, or to unusually pleasant weather in the region. The new businesses that have opened in Ocean View might have opened there irrespective of the new golf course and hotel. And, the 30% increase in tax revenues might have been the result of an increase in tax rates, or the addition of a new type of municipal tax. Without ruling out theses and other alternative explanations for the three recent trends in Ocean view, the mayor cannot reasonably infer based on those trends that Hopewell's economy would benefit by following Ocean view's example.

Thirdly, even if the recent trends in Ocean View are attributable to the construction of the new golf course and hotel there, the mayor assumes too hastily that the golf course and hotel will continue to benefit that town's overall economy. The mayor has not accounted for the possibility that increased tourism will begin to drive residents away during tourist season, or that new business development will result in the town's losing its appeal as a place to visit or to live. Unless the mayor can convince me that these scenarios are unlikely I cannot accept the mayor's recommendation that Hopewell follow Ocean View's example.

Finally, the mayor's argument rests on the unsubstantiated assumption that Hopewell and Ocean View are sufficiently alike in ways that might affect the economic impact of a new golf course and hotel. Hopewell might lack the sort of natural environment that would attract more tourists and new business of the town--regardless of its new golf course and hotel. For that matter, perhaps Hopewell already contains several resort hotels and golf courses that are not utilized to their capacity. If so, building yet another golf course and hotel might amount to a misallocation of the town's resources--and actually harm the town's overall economy.

In sum, the mayor's recommendation is not well supported. To bolster it the mayor must provide better evidence that Ocean View's new golf course and hotel--and not some other phenomenon--has been responsible for boosting Ocean View's economy during the last two years. To better assess the recommendation I would need to know why Ocean View decided to construct its new golf course and hotel in the first place--specifically, what events prior to construction might have prompted that decision. I would also need to thoroughly compare Hopewell with Ocean View--especially in terms of their appeal to tourists and businesses-- to determine whether the same course of action that appears to have boosted Ocean View's economy would also boost Hopewell's economy.

posted @ 2008-08-16 15:04 杨磊阅读(350) | 评论 (0) | 编辑收藏

功夫熊猫

这个翻译真是把我雷到了，哈哈～

posted @ 2008-08-16 14:30 杨磊阅读(90) | 评论 (0) | 编辑收藏

zz 让MyEclipse具有Visual Studio一样强大的代码提示

一般默认情况下，Eclipse ，MyEclipse 的代码提示功能是比Microsoft Visual Studio的差很多的，主要是Eclipse，MyEclipse本身有很多选项是默认关闭的，要开发者自己去手动配置。如果开发者不清楚的话，就不知道Eclipse ，MyEclipse的代码提示功能一样能像Microsoft Visual Studio的代码提示功能一样强大。

先举个简单的例子说明问题所在，例如在Eclipse ，MyEclipse代码里面，打个foreach，switch等这些，是无法得到代码提示的（不信自己试试），其他的就更不用说了，而在 Microsoft Visual Studio 里面是得到非常友好的代码提示的。实际上，Eclipse ，MyEclipse代码里面的代码提示功能默认的一般是点“.”，一般是有了点“.”，才会有代码提示。

原理：“Auto Activation triggers for java”这个选项就是指触发代码提示的的选项，把“.”改成“.abcdefghijklmnopqrstuvwxyz(,”的意思，就是指遇到26个字母和.，（这些符号就触发代码提示功能了。（具体后面有说，放心）

增强Eclipse ，MyEclipse 的代码提示功能，具体怎么样来配置？下面开始说步骤：PS：在6.0 和6.5测试通过

1. 打开MyEclipse 6.0.1，然后“window”→“Preferences”

2. 选择“java”，展开，“Editor”，选择“Content Assist”。

3. 选择“Content Assist”，然后看到右边，右边的“Auto-Activation”下面的“Auto Activation triggers for java”这个选项。其实就是指触发代码提示的就是“.”这个符号。

“Auto activation delay”这个是延时，可以根据自己的需要进行设置。我设置的是10

4. “Auto Activation triggers for java”这个选项，在“.”后加abc字母，方便后面的查找
修改。然后“apply”，点击“OK”。

5. 然后，“File”→“Export”，在弹出的窗口中选择“Perferences”，点击“下一步”。

6. 选择导出文件路径，本人导出到桌面，输入“test”作为文件名，点击“保存”。

7. 在桌面找到刚在保存的文件“test.epf”,右键选择“用记事本打开”。

8. 可以看到很多配置MyEclipse 6.0.1的信息

9. 按“ctrl + F”快捷键，输入“.abc”，点击“查找下一个”。

10. 查找到“.abc”的配置信息如下：

如下：

/instance/org.eclipse.jdt.ui/content_assist_autoactivation_triggers_java=.abc

11. 把“.abc”改成“.abcdefghijklmnopqrstuvwxyz”，保存，关闭“test.epf”。

12. 回到MyEclipse 6.0.1界面，“File”→“Import”，在弹出的窗口中选择“Perferences”，点击“下一步”，选择刚在已经修改的“test.epf”文件，点击“打开”，点击“Finish”。该步骤和上面的导出步骤类似。

13. 最后当然是进行代码测试了。随便新建一个工程，新建一个类。在代码输入switch，foreach等进行测试。你立即会发现，果然出了提示，而且无论是敲哪个字母都会有很多相关的提示了，很流畅，很方便。

总结：

“Auto Activation triggers for java”这个选项就是指触发代码提示的的选项，把“.”改成“.abcdefghijklmnopqrstuvwxyz(,”的意思，就是指遇到26个字母和.，（这些符号就触发代码提示功能了。

顺便说一下，修改类名，接口名等以不同颜色高亮的，可以这样配置在“java”→“enditor”→ “syntac”，右边展开“java”→“classes”，勾上“Enable”这个选项，选择自己喜欢的颜色即可。当然还有其他相关的颜色配置。具体就不说啦。其实，在“Preferences”这个东西，有很多可以配置的东西，使得MyEclipse 优化的，具体的就要各个人根据自己个人喜好去配置了。谢谢。

PS:这个设置的只是对于Java代码提示的加强，可以使用同样的方法修改对于html和JavaScript的代码提示的增强

posted @ 2008-08-14 15:18 杨磊阅读(240) | 评论 (0) | 编辑收藏

云计算

云计算机

云计算是IBM提出的新技术。是IBM采用单个性能一般的计算机群体，完成超级计算机才能提供的计算性能。IBM给出的定义：云计算是一种通过虚拟化的方式共享资源的计算，计算资源可以动态部署、动态调度、动态回收。在云计算的设施中，各种计算机被连接在一起，形成统一的资源池，这些资源会被动态地分配给不同的应用和服务，满足它们在不同时刻的需求。

云计算有几个显著的特点：

分布式：计算机可以部署在不同的网络点上，可以虚拟统一管理，也可以单独使用。分布方式方便了可重用的构架实现，可以把计算机资源分成更细的重用单元，可重用的组合越精细，复杂度也会增加。

虚拟化：应用与计算机硬件不绑定，根据应用的需要虚拟出应用需求的计算机使用，实际上就是增加了虚拟管理层。

动态可扩展：虚拟的计算机比非虚拟的好处，就是动态扩展的方便，因为业务的发展，对计算机、存储等资源的需求会动态增大，而也不希望业务因系统升级而中断，动态扩展也是虚拟计算的天生亮点。

灵活：云计算的虚拟可以支持不同应用的环境需求，包括CPU、存储的硬件需求，也包括操作系统、数据库、中间件等软件环境。

云计算可以说是虚拟计算机的高级阶段，它与网格计算的差异是网格计算允许计算资源的不同构，当然也牺牲了管理性能的代价。云计算机采用同构计算资源，对于效率的提高是有好处的，适合企业的计算中心整合。

这东西在我看来就好象是人多好办事，大家一起上，如果能够分工明确，配合的好，那么工作效率肯定是1+1>2的

感觉SOA和云计算相同的地方就是两者都是“虚拟”的，一个是软件虚拟，另外一个是硬件虚拟

不知道“虚拟”这个概念是先从软件来的还是先从硬件来的

总之殊途同归

看cnbeta一个新闻有感～

posted @ 2008-08-14 14:36 杨磊阅读(174) | 评论 (0) | 编辑收藏

Watergate Scandal

又是扫盲，原来我竟然不知道著名的水门事件是什么
现在总算知道，为什么什么事情都叫“XX门”了，原来是这么来的
以下内容为转载

水门事件指美国共和党政府在1972年总统竞选运动中的非法活动暴露后的政治丑闻。

水门是华盛顿的一座综合大厦。1972年6月17日有5个人因闯入大厦内的民主党全国总部被捕。随后的调查表明，尼克松政府为破坏选举的进程采取了一系列的行动，闯入水门只是其中之一。结果导致政府的几个官员锒铛入狱以及美国历史上破天荒第一遭出现的总统辞职。

在5个人被捕后几天，前白宫助理小亨特和争取总统连任委员会总顾问利迪即被指控犯有盗窃罪和窃听罪。1973年1月美国哥伦比亚特区地方法院首席法官赛里卡主持审讯7名被告。在7名被告中有5人认罪，另外2人由陪审团定罪。1973年3月23日宣判时赛里卡法官宣读了被告之一麦科德的来信。信中指控白宫至今仍在掩盖它与闯入水门的关系。麦科德还说白宫曾对7名被告施加压力，要他们认罪并保持缄默。在白宫显然有牵连的情况下，尼克松总统于1973年4月17日宣布他已开始一次新的调查。4月30日尼克松公开声明他对卷入此案的白宫工作人员的行动负有责任。他接受了顾问霍尔德曼和埃利希曼以及司法部长克兰丁斯特的辞职，并宣布解除迪安的职务。然而尼克公一口咬定他对政治谍报活动以及掩盖错误的努力毫不知情。他选择哈佛大学法学教授考克斯为水门事件的特别检查官。后来调查中心转向参议院，开始由该院总统竞选活动特别委员会（由参议员小欧文领导）举行由电视播放的公众听证会。欧文委员会根据证词判定白宫和竞选委员会成员有罪。然而只有迪安一个人证明尼克松总统有直接卷入掩盖活动。1973年7月16日前白宫工作人员巴特菲尔德揭露：在总统办公室的谈话都录了音。考克斯和欧文委员会立即（7月23日）票传录音带。尼克松以行政特权和国家安全为由拒绝交出。当赛里卡法官命令尼克松交出录音带的时候，尼克松表示可以提供有问题的录音带的文字提要，但以不再索取总统文件的协定作为交换条件。考克斯拒不接受这个建议。10月20日总统命令司法部长理查森解除特别检查官的职务。理查森和副部长拉克尔肖斯宁肯辞职也不执行这个命令。最后考克斯的职务是由副总检察长解除的。群众抗议的怒涛迫使尼克松于10月24日交出了录音带。但赛里卡要的是9盘，他只交出了7盘。白宫声称另外两盘根本就不存在。5月20日赛里卡法官命令尼克松向特别检查官贾瓦斯基提交其他的录音带。7月27日—30日期间众议院司法委员会通过弹劾案。8月5日总统提交三盘录音带的文字本，这些文字本清楚表明总统与掩盖活动有关。因此尼克松在国会里失去了最后的支持者。他于8月8日宣布辞职，次日上午11时35分离开白宫。1974年9月8日继任总统福特给予尼克松以无条件的赦免，不受进一步惩处。

1972年6月18日，星期日。温暖的阳光，清新的海风，茂密的树林，松软的沙滩，构成了一幅美妙的初夏海滨风景画。画里还有错落有致的几幅别墅，那是美国总统在佛罗里达的比斯凯恩湾的寓所。正在这里度假的尼克松总统，心情和这天气、景色一样的好。 4个月前的2月21日至27日，尼克松总统在他的对外政策首席顾问基辛格博士的陪同下，对中华人民共和国进行了历史性的访问，从而结束了两国之间20多年的敌对状态。此举赢得了世界舆论的广泛赞扬和美国人民的普遍欢迎，尼克松的声望大振。 1个月前的5月22日至28日，尼克松又赴莫斯科同苏联领导人会谈，达成了关于限定美苏双方各自拥有 2个反弹道导弹发射场的协议，让世界在日益升级的军备竞赛中看到了一丝有所克制的曙光。有一系列令人瞩目政绩的尼克松总统，今年任期已满，他正踌躇满志地开始了竞选连任的准备工作。这次度假，他的公文包里还放着一份竞选备忘录。在他的案头，放着英国前首相丘吉尔回忆二次大战的书著《胜利与悲剧》，这本书他已读了几遍，他想进一步从中得到有益的启示。尼克松并没有意识到，正当他向胜利的高峰攀登时，悲剧也在悄悄地向他袭来。此刻，尼克松正端坐在沙发上，漫不经心地浏览当天的报纸。他有早读的习惯，看报就像吃早餐一样必不可少。《迈阿密先驱报》第一版左侧的一段小新闻引起了他的注意，其标题是：“ 企图在民主党总部装窃听器的迈阿密人在华盛顿被拘留”。到自己的竞争对手民主党总部去实施窃听，真有意思，尼克松不由自主地看了下去。报道说，昨天 (6月17日)夜里有5个人在华盛顿的水门大厦被捕，民主党全国委员会总部就设在该处。这5个人中，有4个是从迈阿密去的，其中一个自称是中央情报局的职员，另 3个是古巴人。他们随身携有照相机和电子侦察设备，是戴着橡胶手套安装窃听装置时被发现，当场被捕的。据尼克松自己在回忆录中说，他的第一个感觉是这段新闻荒谬得很，古巴人到美国民主党总部来装窃听器，真会开玩笑。所以，他把报纸放一旁，便自由自在地投入大海畅游了好久。后来他甚至觉得，这是有利于他竞选连任的消息，因为它可以声明，由于有“左派”之称的竞选对手、民主党总统候选人麦戈文一向对古巴卡斯特罗政权采取谦让政策，在美国国内的古巴侨民都害怕这一点，故在民主党总部实施盗窃。这样的消息传播开来，可以狠狠打击民主党。然而，事情并非像尼克松想象的那么简单，那么如意。被捕的 5个人中，那个自称是中央情报局职员的麦科德，实际上是尼克松的“争取总统连任委员会”的安全顾问，其余 4人也不是什么古巴人，很可能是受雇于“争取总统连任委员会”的特工人员。一石激起千层浪。有如此前景的麦科德等人的被捕，使水门事件很快变成了新闻界热炒、全国关注的爆炸性新闻。专门辞去司法部长职务、充任尼克松的竞选连任委员会主席的米切尔，不得不向新闻界声明，在水门大厦被捕的那 5个人的行为，纯属他们的个人行为，与本委员会毫无关系。民主党展开了攻势。它们对争取总统连任委员会和这伙窃贼提出民事诉讼，要求赔偿100万美元，后来又增至640万美元。当时它们并没有想到，它们本来可以得到的更多——当然，并非是指金钱的数额。两天后，即 6月20日上午，《华盛顿邮报》的一则消息使尼克松不安起来。报道说，从被捕的人员随身携带的通讯录中，发现了曾在白宫任职的前中央情报局特工人员，他叫霍华德·亨特，在尼克松的高级顾问科尔森手下任职。闻此消息的白宫，像挨了地震。昨天刚从度假地返回华盛顿的尼克松，见报后马上召来其心腹、白宫办公厅主任霍尔德曼商谈此事。一个多小时很快过去了，似乎还没有找到万全的对策。下午继续探讨同一个问题。情况不明而又怕牵连的尼克松，首先要求霍尔德曼如实告诉他，在我们“自己人”中，不管属于哪一层次的官员，是否已经使我们卷入这个尴尬的局面。然后一起研究，目前的一切调查与口供，如果进行深查细究，会不会让民主党抓住把柄，对我们竞选不利。据尼克松日记记载，米切尔曾在电话里神秘地告诉霍尔德曼别卷入此案。但此时霍尔德曼很肯定地向尼克松保证，白宫的官员不会被牵涉到此案中，米切尔也与此事无关，尽可以放心。听到这一保证，尼克松担心被信心所取代，他决定采取以攻为守的策略。然而，霍尔德曼还告诉他，查究水门行动的主使人已经查到竞选连任委员会财政组的法律顾问戈登·利迪身上，联邦调查局正在追查因水门事件被捕的麦科德身上携带的款项，该款项很可能出自竞选连任委员会。“必须阻止联邦调查局追查那笔钱的来源！”尼克松不容置疑地说。后来，中央情报局的一位高级官员授权向联邦调查局代理局长打电话，请他“别管这件事”，因为在这两个局之间，早有互不干涉对方秘密行动的协议。尽管白宫利用其执政的权力进行掩盖和阻挠，检察机关对水门事件的调查仍在进行。9月15日，在取得必要的证据之后，在这一事件中当场被捕的麦科德等5人被依法起诉，同时被起诉的还有中央情报局的特工人员霍华德·亨特和争取总统连任委员会的法律顾问戈登· 利迪。尽管有水门事件的阴影缠绕，尼克松争取连任的竞选依然搞得有声有色。大选前夕的10月26日，从巴黎回国的基辛格特使，向美国人民公布他与北越代表黎德寿进行一系列秘密会谈的成果，宣称：“和平即将到来。”这给尼克松政府的政绩本上又增添了浓重的一笔。尼克松毫不留情地嘲笑他的竞争对手民主党总统候选人麦戈文之流，是“嘲笑我们国家的过去和将会妨碍它的未来的激进集团”。他针对麦戈文借口水门事件攻击他的政府是“最腐败的政府”一说进行抨击道：“这些年来批评美国的制度已变得很时髦。批评者们坚持认为，它是如此偏颇，如此腐败，如此不义，以致我们应该摧毁它，用别的什么东西取代它。我完全不同意，我相信美国的制度。” 麦戈文显然不是尼克松的对手。在中学时代就以擅长演讲和辩论著称的尼克松，巧妙地将对手指责他和他的政府的腐败，变成了攻击美国制度的腐败。尽管水门事件的许多事实已经揭露，但美国选民们似乎对此并不太在意，他们更看重尼克松政府的政绩，所以，11月7日公布的大选结果，尼克松就得了61%的选民票和520张选举人票，而麦戈文只获得 34%的选民票和17张选举人票。这是在美国总统选举的历史上少有的以如此悬殊的票数决出胜负的一次。以米切尔为首的总统连任竞选委员会成员个个喜形于色，他们似乎忘记了还有 7 个“难兄难弟”因水门事件正在失去自由的监狱里接受审讯。尼克松满面春风，走马上任，开始了新的一届总统任期。在1973年 1月20日的连任就职演说中，他还没有忘记抨击他的对手：“在每一个关键时刻，我们总是受到那些认为美国一无是处、绝少正确的人们的困扰。但是，我深信，这不是历史对我们有幸经历这些非凡的年代的评判。”他在演说中自豪地用了一连串“让我们感到自豪的是……”的字句，宣称“本世纪美国的经历在世界历史上是无与伦比的”。然而，水门事件的阴影并不因为尼克松满面春风而消散，相反却一步步向他逼来。当尼克松在台上发表连任就职演说时，对水门事件被告的审讯也在抓紧进行。这场审讯从1月8日开始，被告在巨大的压力下开始交代其犯罪事实，有的公开表示对各种指控服罪。他们究竟做了哪些交代，会不会将白宫里更大的人物牵扯进去？还有，为掩饰真相而做出的种种努力，会不会弄巧成拙，欲盖弥彰，反而增添新的罪证？这一切，都使白宫弥漫着一种焦虑的气氛，尼克松及其心腹官员更是坐立不安，失眠频频。本来应该沉浸在竞选连任胜利的喜悦之中，如今却被水门事件的阴影所笼罩，尼克松未免感到沮丧。他这时似乎已经意识到，从一开始阻止调查就是个错误，而且是比到水门大厦民主党总部安装窃听装置本身更大的错误。但是，为了维护自己的身份和形象，这条路哪怕是错了也要坚定不移地走下去。风雨飘摇的白宫，仿佛在经受地震后日益增强的余震的煎熬，谁能保证这不是又一次更大的“地震”到来的前兆呢?

丢卒保车，大总统挥泪斩马谡

一波未平，一波又起。曾想以攻为守的尼克松总统，渐渐地处于防不胜防的境地。尼克松在1973年 2月14日的日记中，忧心忡忡地写道：“我可以料想得到，假如法官把亨特叫到面前，拿35年的刑期来恫吓他，他很可能为了免受刑罚而就把自己所知道的一切，全盘吐露。” 亨特，这个中央情报局的特工人员，不仅与潜入水门大厦民主党总部的 5名案犯有牵连，而且他曾和总统竞选连任委员会的法律顾问利迪一起，在白宫的纵容下，私闯心理治疗专家埃尔斯伯格的办公室，企图窃取加害埃尔斯伯格的材料。这个埃尔斯伯格曾经把五角大楼关于越南战争的秘密材料交报社发表，对尼克松政府不利，政府起诉他盗用文件罪，正在受审。白宫显然想置他于死地。一旦这一事件抖露出来，岂不是又一次“地震”。如何使亨特保持沉默，或者绝不供出幕后的纵容者，是一件棘手的事情。 3月21 日上午，在尼克松的椭圆形办公室，总统和他的法律顾问约翰·迪安商谈着。 “亨特给竞选连任委员会的一名律师写信，索取12.2万美元，作为个人和请律师的费用。他甚至规定了交款期限。”迪安向尼克松通报了这一情况。 “他们到底想要多少钱？”尼克松知道，有第一笔，就会有第二、第三笔钱；有第一人，就会有第二、第三人要。 “在整个诉讼期间，至少要付 100万给各个被告。”迪安报出了一个不少的数目，虽说这一数目对美国总统来说是不难办到的，但在风声很紧的情况下，毕竟要冒不少风险。从迪安的口气中，似乎不想再去冒险。骑虎难下的尼克松总统，却只有按照既定方针走下去这一条路。他曾两次向公众信誓旦旦地保证，他和他领导的白宫在水门事件一案中是清白的，经得起调查的。如果退缩的话，他和他的政府岂不成了信誉扫地的说谎者和骗子。 “也许我们这样做是错的”，尼克松缓缓而又坚定地说，“但此时此刻，你难道不同意最好的出路是把亨特的问题妥为应付吗?我想，此时此刻，这是值得一为的。” 他显然把赌注押在了让被告守口如瓶上。他是在位的总统，拥有至高无上的权力，这样押宝也许有他的道理。因为，如果这些被告拿了钱，还想获得自由，即使法院判他重刑，作为总统还有特赦罪犯的权力。有总统作强大的后盾，聪明的被告是不会吐露对总统及其领导下的白宫不利的事实的，尼克松相信这一点。迪安嘴上答应了总统的要求，心里却像挂了15个吊桶，七上八下，惶惶不安。尼克松在回忆录中承认：“从事后看，这一天是我任期内一个悲惨的转折点。” 事实正是这样。不久便“反戈一击”的迪安，使尼克松和白宫狼狈不堪。迪安不仅说出了白宫几名重要人物与5名窃贼潜入水门大厦民主党总部一案有关，而且坦白了案发后的一系列掩饰真相的企图。他公开表示，白宫的办公厅主任霍尔德曼、总统的内务顾问埃利希曼以及他自己，都卷进了此案，有“阻挠司法的举动”。他还透露，总统的私人律师坎姆巴克曾受命筹款给水门事件一案的被告。而关在狱中受审的麦科德，也指控争取总统连行委员会主席，前司法部长米切尔应对他们潜入水门大厦民主党总部行窃一案负责，并且供出在受审期间，有人表示可予以宽赦，交换条件是他缄口不语。负责审理水门事件一案的联邦地方法院法官也似乎打定主意要与白宫过不去。在 3 月底进行的宣判中，对第一位将政界要人牵进这一事件的被告麦科德从宽处理，予以保释，而对其余 4名潜入水门大厦行窃的被告则予以重判，暂定为40年徒刑；与此案有关、又犯有私闯埃尔斯伯格医生办公室行窃之罪的亨特和利迪，前者被暂判为入狱 35年，后者曾因不肯开口而犯了蔑视法庭罪，就此暂判为6年零8个月徒刑，另处罚款4万元。轻重悬殊的宣判，给至今抱有侥幸心理、不愿吐露全部事实的被告形成了巨大的威慑力。尼克松明知这样的判决过重，甚至实属蛮横，因为对一些杀人犯的判决也不至于如此；但也不得不承认，这是地方法院法官所采取的一种文明的策略，就是要促使被告说真话，因为他们的宣判并非最后的判决，如果坦白交代，检举揭发有功，麦科德就是他们的榜样。随着水门事件真相的不断抖露，群情激愤，舆论大哗。尼克松的防线是如此脆弱，已经到了不找几个替罪羊就难以过关的程度。 4 月中旬一个星期天的下午，接替米切尔担任司法部长的理查德·克兰丁斯特，急匆匆地求见总统尼克松，说有要事相告。无心度假、正在白宫举行午后宗教礼拜仪式的尼克松，在仪式结束后马上同他进办公室密谈。克兰丁斯特省去了拐弯抹角的客套话，直截了当地告诉总统：“迪安把我们告了。霍尔德曼和埃利希曼被认为是授权闯入水门大厦行窃的主谋人。”“不，这不可能。”尼克松惊讶得差点叫了起来，紧接着又半信半疑地问他的司法部长：“真有其事？”克兰丁斯特没有正面回答，说： “让刑事厅长来谈，您看如何?”尼克松点了点头。不一会儿，身穿一件赃兮兮的 T恤衫和一条湿漉漉的牛仔裤，脚蹬一双网球鞋的司法部刑事厅厅长亨利·派德逊，在克兰丁斯特的带领下，走进了尼克松的办公室。他是在洗刷游艇时被召来的，连衣服也没来得及换。下属官员如此打扮到白宫来，实属不敬，要是在平时非被轰出去不可，但这次尼克松只是皱了一下眉头，便让他将掌握的迪安指控的情况一一道来。这位厅长迟疑了一会，瞥了身旁的部长一眼，在得到 “照实说”的眼神暗示后，便将迪安如何指控总统的办公室主任霍尔德曼、内务顾问埃利希曼卷入水门刑事案的情况做了汇报，末了还斗胆建议：“应该让他们两个辞职，不然会有麻烦的，会使您和您的总统职位处境难堪。” 尼克松默默地听着，思索着，眼睛直愣愣地望着天花板，半晌没说一句话。克兰丁斯特部长和派德逊厅长面面相觑，不知所措。 “你们走吧。”尼克松有气无力地说。宽大的办公室只剩下沉思的尼克松一人。“好一个吃里扒外的迪安！”尼克松想对他施加压力，让他明白作为总统可以阻止他获得行政豁免权，到头来一样受刑，可是又担心把他逼急了眼，说不定会把指控的矛头直接转向他。 “我没有什么把柄掌握在迪安手里。”尼克松的心里暗暗地为自己打气。虽说他事先确实没有授权任何人去干闯入水门大厦民主党总部安装窃听装置这样的蠢事，但事后的掩盖行动他能逃脱罪责吗？一想到这里，他的心又有点发虚。虽说他和年轻的法律顾问迪安商谈掩盖对策时，没有第三者可以出来证明，但谁又能保证没有留下任何可以作为证据的话柄呢? 苦思冥想，绞尽脑汁，还是没有找到自己满意的对策。想找几个心腹顾问来集思广益，可是不少人已经涉嫌水门一案，要是再冒出一个像迪安那样“反戈一击”的顾问，那不就更惨了。看来，只有变以攻为守为以退为进了，“丢卒保车”不失为一种明智的选择，尼克松终于拿定了主意。几天后，霍尔德曼和埃利希曼被召到总统办公室。尼克松把上次司法部长及该部刑事厅厅长谈的情况一五一十地讲给他们听，然后，婉转地请他们拿个主意。这两个人是尼克松的得力助手和多年的忠实朋友，为他谋取总统职位立下过汗马功劳，如今，要尼克松开口让他们辞职，实际上是把他们开除出白宫，尼克松真是有点开不出口。霍尔德曼和埃利希曼显然被总统介绍的不利于他们的事实惊呆了。虽说这些事实都是他们经历过的，但一旦作为罪证指控则是他们万万没有想到的。非常敏感而又特别能领会总统意图的办公厅主任和内务顾问，此刻，只有吞下辞职这杯苦酒，以便保全总统和白宫的面子。“我们会现实地面对这一切的。”霍尔德曼和埃利希曼说这话时，眼睛有点发红，鼻子开始发酸。三人相对无语。谁也没有说出“辞职”这两个令人难堪的字眼，但谁的心里都非常明白。还是彼此心照不宣吧，各自的心情当然有所不同。尼克松后来在回忆录中这样描述他当时的心境： “我为了自己的生存而要他们离职，真是自私得可以了；不过我还不至于狠心到能够心安理得地伤害自己所深切关怀的人。我忧虑他们被迫辞职时所受的打击，但我更忧虑他们留任不去会使我遭受的打击。” “我现在的问题，是必须把做过一些我亦有份之事的几个朋友开除。” 4月 30日晚上，尼克松向全国发表讲话。他重申自己与水门事件没有牵连，但接着又说，他将为那些“在一件他们原来深信是正确的事情中可能犯了错误”的下属承担应负的责任。尼克松借此机会宣布：“今天，我做出了任期内最难的一项决定，我接受了白宫两位最亲信僚属的辞呈。他们是霍尔德曼和埃利希曼，称得上是我有幸遇到的最优秀公务人员中的两位。”他用如此赞美的语句，送给被迫辞职的朋友，与其说是对朋友的抚慰，倒不如说是为了使自己的心里也好受些。同时宣布已经辞职的还有那个“反戈一击”的顾问迪安，以及司法部长克兰丁斯特；前者如果不从白宫清除出去，怎解尼克松的心头之恨，后者辞职是因为他的一些亲密同事可能“与违反美国法律的某些行为有牵连”。尼克松演出了一幕现代“挥泪斩马谡”的话剧。然而，就像马谡被斩并不能夺回失去的街亭一样，丢了“卒”的尼克松能保住自己这个“车”吗?

    美国《名利场》杂志2005年6月31日报道，前联邦调查局官员马克·费尔特自称是“水门事件”中的神秘线人“深喉”。

    1972年，美国《华盛顿邮报》记者鲍勃·伍德沃德和卡尔·伯恩斯依据内线“深喉”的消息，捅开“水门事件”的内幕，导致当时的美国总统尼克松辞职下台。两名记者一直拒绝透露当时线人的身份，但是总编辑西蒙斯引用了当时一部知名色情电影《深喉》的片名，作为告密者的化名。

   “深喉”到底是谁？30多年来猜测纷纷，从未有定论。接触过“深喉”的《华盛顿邮报》记者曾发誓，除非获得“深喉”同意或者“深喉”死亡，否则他绝不会说出这个天大的秘密。

    费尔特的律师康纳日前在《名利场》撰文，70年代初曾任联邦调查局“二把手”的费尔特于2002年亲口告诉他，“我就是《华盛顿邮报》记者伍德沃德的线人－－人们常说的‘深喉’”。

    此前，费尔特对于对“深喉”的身份一直是保守秘密，家人也不例外。费尔特认为，公开自己过去的所为有损名誉。有些媒体，如《华盛顿人》，曾刊文称有人怀疑过费尔特就是“深喉”。1999年，费尔特否认自己是“深喉”。

    康纳的文章写道，费尔特有一次曾暗示过他的儿子，“我认为，（作为‘深喉’）并不是一件光彩的事情，你不要把这件事情告诉任何人。”

    退休后的费尔特住在加州的圣罗莎。在如何看待“深喉”一事上，家人的立场与他不同，他们认为，费尔特在有生之年应该受到奖励，以表彰他在“水门事件”中所起到的作用。

    法新社报道称，费尔特的孙子31日代表家人就费尔特“深喉”身份一事发表一份声明，“家人认为我的祖父是一个英雄，我们真诚地希望国家也这样认为。”

   《华盛顿邮报》对此事暂无评论。

　　这是一件有一段历史的事件了，是美国历史上最不光彩的政治丑闻之一。其对美国本国历史以及整个国际新闻界都有着长远的影响。水门事件之后，每当国家领导人遭遇执政危机或执政丑闻，便通常会被国际新闻界冠之以“门”（gate）的名称，如“伊朗门”、“情报门”、“虐囚门”等。
我想，大家看了，一定深有所思，思有所感，我想，这就是政治的残酷斗争，以及那些“胜利”总是会有的！唉￣￣

posted @ 2008-08-04 16:03 杨磊阅读(544) | 评论 (0) | 编辑收藏

扫盲贴，啥是TD

每天在cnbeta上面看到TD，就是不知道是啥东西
于是今天google了一下
但是还是发现百度好-，-
http://baike.baidu.com/view/9800.htm

posted @ 2008-07-21 16:46 杨磊阅读(120) | 评论 (0) | 编辑收藏

ZJU Online Judge 1508

差分约束，第一次听说这个东西，看来以前知道的还是太少了，惭愧

代码是别人的，看了几遍看懂了，贴过来，转载一下

利用Bellaman Ford最短路算法，这个算法也是第一次听说……

要学的东西好多～

http://acm.oopos.cn/sutu.htm

一个牛人的解题报告，没太看懂，写的有点乱

1 #include<string>
2 #include<iostream>
3 using namespace std;
4 const int M = 100001;
5 int n, mx, my, d[M];
6
7 struct edge
8 {
9           int u, v, w;
10
11 }e[M];
12
13
14 // d[v] <= d[u] - w           [1]
15 // d[i] <= d[i - 1] + 1        [2]
16 // d[i - 1] <= d[i]              [3]
17
18 int bellman( )
19 {
20           int i, k;
21           bool flag = true;
22           while( flag )
23           {
24                   flag = false;
25                   for ( i = 0; i < n; i++ )
26                   {
27                            k = d[e[i].u] + e[i].w;
28                            if ( k < d[e[i].v] )
29                                    d[e[i].v] = k, flag = 1;
30                   }
31
32                  for ( i = mx; i <= my; i++ )
33                         if ( d[i-1] + 1 < d[i] )
34                                d[i] = d[i-1] + 1, flag = 1;
35
36                 for ( i = my; i >= mx; i-- )
37                        if ( d[i-1] > d[i] )
38                                d[i-1] = d[i], flag = 1;
39
40           }
41           return d[my] - d[mx - 1];
42 }
43
44 int main ()
45 {
46            int i, j, k, l;
47            while ( scanf("%d", &n) != EOF )
48            {
49                    memset(d, 0, sizeof(d));
50                    mx = M, my = 0;
51                    for ( i = 0; i < n; i++ )
52                    {
53                             scanf("%d%d%d", &j, &k, &l);
54                             e[i].u = k;
55                             e[i].v = j - 1;
56                             e[i].w = -l;
57                             if ( mx > j ) mx = j;//
58                             if ( my < k ) my = k;//
59                     }
60                     printf("%d\n", bellman() );
61            }
62            return 0;
63 }

posted @ 2008-06-10 02:29 杨磊阅读(335) | 评论 (0) | 编辑收藏

ZJU Online Judge 1457

注意n为奇数时无解

因为无论怎么排列，必然有两个奇数相邻，所以肯定和是偶数，比可能是素数（因为一定比2大）

1 #include <iostream>
2 #include <cmath>
3 using namespace std;
4
5 bool prime[100];
6 bool used[20];
7 int sequence[20];
8
9 void output(int n)
10 {
11     for (int i = 0; i < n; i++)
12         if (i!=n-1)
13             cout << sequence[i] << " ";
14         else
15             cout << sequence[i] << endl;
16 }
17 void solve(int step,int n)
18 {
19     if (step==n)
20     {
21         if (prime[(sequence[step-1]+sequence[0])])
22             output(n);
23     }
24     else
25     {
26         for (int i = 2; i <= n; i++)
27             {
28                 if (!used[i])
29                 {
30                     if (prime[(sequence[step-1] + i)])
31                     {
32                         sequence[step] = i;
33                         used[i] = true;
34                         solve(step+1,n);
35                         sequence[step] = 0;
36                         used[i] = false;
37                     }
38                 }
39             }
40     }
41 }
42 int main()
43 {
44     for (int i = 0; i < 100; i++)
45         prime[i] = false;
46     prime[2] = true;
47     for (int i = 3; i < 100; i++)
48     {
49         bool is = true;
50         for (int j = 2; j <= sqrt(i+0.0); j++)
51             if (i%j==0)
52             {
53                 is = false;
54                 break;
55             }
56         if (is) prime[i] = true;
57     }
58
59     int n;
60     int css = 1;
61     while (cin >> n)
62     {
63         cout << "Case " << css++ << ":" << endl;
64         for (int i = 0; i < 20; i++)
65         {
66             used[i] = false;
67             sequence[i] = 0;
68         }
69         sequence[0] = 1;
70         if (n%2==0) solve(1,n);
71         cout << endl;
72     }
73
74 //system("pause");
75 return 0;
76 }
77
78

posted @ 2008-06-09 18:58 杨磊阅读(325) | 评论 (2) | 编辑收藏

IME中促音输入

重复小っ后面单字的首字母就可以了，或者可以直接打ltu，也可以出现小型的つ、其他的小型字母可以仿照此法。

posted @ 2008-06-07 20:20 杨磊阅读(190) | 评论 (0) | 编辑收藏

ZJU Online Judge 2133

很巧妙的算法，自愧不如啊

当初就想着二分啊二分，结果还是没有分出来，而且情况很复杂

下面的代码的算法很巧妙，充分利用了有一个数出现的次数大于总数的一半这一条性质

1 #include<stdio.h>
2 int main()
3 {
4     int i,counter,answer,n,data;
5     while(scanf("%d",&n)!=EOF)
6     {
7         counter=0;
8         for(i=1;i<=n;i++)
9         {
10             scanf("%d",&data);
11             if (counter == 0)
12             {
13                 answer=data;
14                 counter=1;
15             }
16             else if (answer == data)
17             {
18                 counter++;
19             }
20             else
21                 counter--;
22         }
23         printf("%d\n",answer);
24     }
25     return 0;
26 }

posted @ 2008-06-05 17:12 杨磊阅读(168) | 评论 (0) | 编辑收藏

原来拒信是这个样子的

Hi Lei Yang,

It was a pleasure meeting you and we want to thank you for taking the time to interview with us for the Software Engineering Intern - Beijing position. The interview team was impressed with your background and accomplishments, and enjoyed getting to know you. We carefully reviewed your background and experience, and though we do not have a position that is a strong match with your qualifications at this time, we will be keeping your resume active in our system. We will continue to use our database to match your profile with new opportunities and will reach out to you if we find an opening for which you may be qualified.

Thanks again for your interest in Google's careers and unique culture; we hope you will remain enthusiastic about our company. If you have any questions, please feel free to contact me at libin@google.com.

Kind Regards,

Bin Li

Google People Operations

posted @ 2008-06-04 23:38 杨磊阅读(221) | 评论 (0) | 编辑收藏

ZJU Online Judge 1204

剪枝是王道！！！

if (sum+number[j]<=Max)

就这么一个简单的剪枝，时间从10+秒变成了0.85

  1 #include <iostream>
  2 #include <algorithm>
  3 using namespace std;
  4
  5 int number[31];
  6
  7 bool used[31];
  8
  9 int get[31];
10
11 int Max;
12
13 bool foundone = false;
14
15 bool compare(int a, int b)
16 {
17     return a < b;
18 }
19
20 bool binarysearch(int beg, int end,int value)
21 {
22     bool found = false;
23     int mid = 0;
24
25     while ( beg <= end )
26     {
27         mid = ( beg + end ) / 2 ;
28             if ( number[mid] > value )
29                 end = mid-1 ;
30             else if ( number[mid] < value )
31                 beg = mid+1 ;
32             else
33             {
34                 found = true;
35                 break;
36             }
37     }
38     return found;
39 }
40 void solve(int total,int start,int deep,int target,long sum)
41 {
42     if (deep==target)
43     {
44         if (binarysearch(0,total-1,sum)==true)
45         {
46             foundone = true;
47             for (int i = 0; i < target; i++)
48             {
49                 if (i!=target-1)
50                     printf("%d+",get[i]);
51                 else
52                     printf("%d=",get[i]);
53             }
54             printf("%d\n",sum);
55         }
56     }
57     else
58     for (int j = start; j < total; j++)
59         if (used[j]==false)
60         {
61                 if (sum+number[j]<=Max)
62                 {
63                     sum+=number[j];
64                     used[j] = true;
65                     get[deep] = number[j];
66                     solve(total,j+1,deep+1,target,sum);
67                     get[deep] = 0;
68                     sum-=number[j];
69                     used[j] = false;
70                 }
71         }
72 }
73 int main()
74 {
75     int N;
76     cin >> N;
77     for (int i = 0; i < N; i++)
78     {
79         int M;
80         cin >> M;
81         foundone = false;
82
83         for (int j = 0; j < M; j++)
84             scanf("%d",&number[j]);
85
86         sort(number,number+M,compare);
87
88         for (int j = 0; j < M; j++)
89             used[j] = false;
90
91         Max = number[M-1];
92
93         for (int j = 2; j < M; j++)
94             solve(M,0,0,j,0);
95
96         if (!foundone)
97             cout << "Can't find any equations." << endl;
98
99         cout << endl;
100     }
101     //system("pause");
102     return 0;
103 }

posted @ 2008-06-03 19:57 杨磊阅读(480) | 评论 (0) | 编辑收藏

ZJU Online Judge 1163

一看就是一个递推的题目，自己推了一会儿，推出来一个递推公式，有点搓
F[i][j]，表示的是第一个的楼梯高度是i的情况下，用j块积木的堆积方案
结果发现好像要用O(n^3)的时间复杂度才能解决，不过好在这个递推公式对了
但是怎么都WA，自己验证了几组比较小的数据，都对了
然后只能去Google一下，后来发现有个人说，这道题目有大数陷阱，用double就过了
一试，没过-_-!!!，怀疑自己的地推公式对不对……
后来想了想，是不是我的输出有问题，原来是cout << sum <<ｅｎｄｌ；
改成了ｐｒｉｎｔｆ（＂％０．０ｌｆ＼ｎ＂，ｓｕｍ）；
ＡＣ了，很神奇……
为什么在我自己的电脑上面，运算出来的结果显示的都是整数呢……，非得用个０．０ｌｆ这种东西才能过
看来还是对ｇｃｃ不了解……

1 #include <iostream>
2
3 using namespace std;
4
5 double F[505][505];
6
7 int main()
8 {
9
10     for (int i = 1; i < 505; i++)
11         for (int j = 1; j < 505; j++)
12         {
13             if (i!=j)
14                 F[i][j] = 0;
15             else
16                 F[i][j] = 1;
17         }
18
19     for (int i = 3; i < 505; i++)
20         for (int j = 1; j <= (i-1)/2; j++)
21             for (int k = j + 1; k <= i - 1; k++)
22                     F[j][i] += F[k][i-j];
23
24     int N;
25     while (cin >> N && N!=0)
26     {
27         double sum = 0.0;
28         for (int i = 1; i <= (N-1)/2;i++)
29             sum+=F[i][N];
30         printf("%0.0lf\n",sum);
31     }
32
33     return 0;
34 }
35

posted @ 2008-06-02 01:40 杨磊阅读(263) | 评论 (0) | 编辑收藏

ZJU Online Judge 1101

一道很普通的搜索题目，但是必须剪枝，否则会超时

if(value!=w[i] && value!=w[j] && value!=w[k])

如果没有这句剪枝就会超时……

剪枝很强大～

1 #include <iostream>
2 #include <algorithm>
3
4 using namespace std;
5
6 long w[1000];
7
8 int compare (const void * a, const void * b)
9 {
10   return ( *(int*)a - *(int*)b );
11 }
12
13 int main()
14 {
15     int N;
16     while (cin >> N && N!=0)
17     {
18         int found = false;
19
20         if (N<4)
21         {
22             cout << "no solution" << endl ;
23             continue ;
24         }
25         for (int i = 0; i < N; i++)
26             cin >> w[i];
27
28         qsort(w,(size_t)N,sizeof(long),compare);
29
30         for (int i = N - 1; i >=0; i--)
31         {
32             for (int k = N - 1; k >=0; k--)
33             {
34                 if (i == k) continue;
35                 for (int j = k - 1; j >=0; j--)
36                 {
37                     if (j == i) continue;
38                     long value = w[i] - w[j] - w[k];
39                     if(value!=w[i] && value!=w[j] && value!=w[k])
40                     {
41                         int mid ;
42                         int beg = 0;
43                         int end = N - 1;
44                         bool searchfound = false;
45                         while ( beg <= end )
46                         {
47                             mid = ( beg + end ) / 2 ;
48                                 if ( w[mid] > value )
49                                     end = mid-1 ;
50                                 else if ( w[mid] < value )
51                                     beg = mid+1 ;
52                                 else
53                                 {
54                                     searchfound = true;
55                                     break;
56                                 }
57                         }
58                         if (searchfound==true)
59                         {
60                             cout << w[i] << endl;
61                             found = true;
62                             goto out;
63                         }
64                     }
65                 }
66             }
67         }
68     out:if (!found)
69             cout << "no solution" << endl;
70     }
71     return 0;
72 }

posted @ 2008-05-29 20:53 杨磊阅读(189) | 评论 (0) | 编辑收藏

ZJU Online Judge 1024

参考了别人的算法，数学果然是王道！

2001.11.4的月+日= 11 + 4 = 奇数。。

由于无论是月加一还是日加一月日和的奇偶性都会发生变化, 除了2.28、9.30和11.30.

2.28、9.30、11.30明显有必胜的策略:

2.28->3.28,

9.30->10.1,

11.30->12.1

所以除了剩余的两个特殊的情况以外，其余只要满足月+日等于偶数就有必胜的策略。

1 #include <iostream>
2
3 using namespace std;
4
5 int main()
6 {
7     int N;
8     cin >> N;
9     for (int i = 0;i < N; i++)
10     {
11         int yy,mm,dd;
12         cin >> yy >> mm >> dd;
13         bool flag = false;
14         if (mm==2 && dd==28)
15             flag = true;
16         else if (mm==9 && dd==30)
17             flag = true;
18         else if (mm==11 && dd==30)
19             flag = true;
20         else
21         {
22             if ((mm+dd)%2==0)
23                 flag = true;
24         }
25     if (flag)
26         cout << "YES" << endl;
27     else
28         cout << "NO" << endl;
29     }
30 }

posted @ 2008-05-29 12:36 杨磊阅读(296) | 评论 (0) | 编辑收藏

ZJU Onlie Judge 1012

这就是传说中的蘑菇题

题目的大意我就不说了，大家自己去google一下吧，有人说过了

就算锻炼了一下用vector,algorithm吧

算法很简单，先按照来的时间和报酬排序

然后在一个一个的处理，未处理的就加入到suspend里面，等到下一轮处理

有个地方比较特殊，就是为处理的任务，如果他的截止时间在F之前，那么会算惩罚，如果超出了，就不算了

刚开始这个地方没注意，所以贡献了几次WA

  1 #include <iostream>
  2 #include <algorithm>
  3 #include <vector>
  4 using namespace std;
  5
  6 struct rect
  7 {
  8 public:
  9     rect(int a,int b,int c,int d,int e,int f,int g):m_a(a),m_b(b),m_c(c),m_d(d),m_e(e),m_f(f),m_g(g){}
10     int m_a,m_b,m_c,m_d,m_e,m_f,m_g;
11 };
12
13 vector<rect> job,suspend;
14 vector<rect>::iterator it;
15
16 bool compare(rect a,rect b)
17 {
18     if (a.m_c<b.m_c)
19         return 1;
20     else if (a.m_c>b.m_c)
21         return 0;
22     else
23     {
24         if (a.m_e>b.m_e)
25             return 1;
26         else
27             return 0;
28     }
29 }
30
31 int main()
32 {
33     int F;
34     int Case = 1;
35
36     cin >> F;
37     while (F!=0)
38     {
39         int M,N,L;
40         cin >> M >> N >> L;
41
42         //count the number of job
43         int totaljob = 0;
44
45         //initialize
46         job.clear();
47         suspend.clear();
48
49         //input
50         for (int i = 0; i < L; i++)
51         {
52
53             int a,b,c,d,e,f,g;
54
55             cin >> a >> b >> c >> d >> e >> f >> g;
56
57             //Arraive before timeline
58             if (c<F)
59             {
60                 rect *temp = new rect(a,b,c,d,e,f,g);
61                 job.push_back(*temp);
62                 totaljob++;
63             }
64         }
65
66         //sort the jobs according to the arriving time
67         sort(job.begin(),job.end(),compare);
68
69         it = job.begin();
70         long totalvalue = 0;
71
72         for (int time = 0; time < F; time++)
73         {
74             int mm = M;
75             int nn = N;
76
77             while (it != job.end() && time >= it->m_c)
78             {
79                 suspend.push_back(*it);
80                 it++;
81             }
82
83             vector<rect>::iterator temp;
84             temp = suspend.begin();
85
86             while (temp!=suspend.end())
87             {
88                 if (mm>=temp->m_a && nn>=temp->m_b)
89                 {
90                     mm-=temp->m_a;
91                     nn-=temp->m_b;
92                     totalvalue+=temp->m_e;
93                     if (time + 1< temp->m_d)
94                         totalvalue+=temp->m_f*(temp->m_d - time - 1 );
95                     else if (time + 1 > temp->m_d)
96                         totalvalue-=temp->m_g*(time + 1  - temp->m_d);
97                     suspend.erase(temp);
98                     temp = suspend.begin();
99                 }
100                 else
101                     temp++;
102
103             }
104         }
105
106         vector<rect>::iterator temp;
107
108         if (!suspend.empty())
109         {
110             for (temp = suspend.begin();temp!=suspend.end();temp++)
111             {
112                 if (temp->m_d<=F)
113                     totalvalue-=(F - temp->m_d)*temp->m_g;
114             }
115         }
116         //for (it = job.begin(); it!=job.end(); it++)
117         //    cout << it->m_a << " " << it->m_b << " " << it->m_c << " " << it->m_d << " " << it->m_e
118         //    << " " << it->m_f << " " << it->m_g << endl;
119
120
121
122     cout << "Case " << Case++ << ": " << totalvalue << endl << endl;
123     cin >> F;
124     }
125     return 0;
126 }

posted @ 2008-05-27 14:06 杨磊阅读(321) | 评论 (0) | 编辑收藏

囧 To Death

http://www.fitzrovian.com/hello.html

这个Hello World过于牛逼了！

posted @ 2008-05-22 16:59 杨磊阅读(147) | 评论 (0) | 编辑收藏

ZJU Online Judge 2351

让人崩溃的输入格式

另外，数据量很大，用cin会超时

1 #include <iostream>
2 #include <cmath>
3
4 using namespace std;
5
6 int main()
7 {
8     int N;
9     cin >> N;
10     getchar();
11     for (int i = 0; i < N; i++)
12     {
13         double ka,b;
14         int m,n;
15         scanf("%lf %lf %d %d",&ka,&b,&m,&n);
16         //cin >> ka >> b >> m >> n;
17         while (ka!=0.0 && b!=0.0 && m!=0 && n!=0)
18         {
19             double x = ((-1)*ka+sqrt(ka*ka+4*m*n*ka*b))/(2*m*n);
20             double pH = -log10(m*x);
21             printf("%.3f\n",pH);
22             scanf("%lf %lf %d %d",&ka,&b,&m,&n);
23             //cin >> ka >> b >> m >> n;
24         }
25
26         if (i!=N-1) {
27             printf("\n");
28             getchar();
29         }
30     }
31     //system("pause");
32     return 0;
33 }

posted @ 2008-05-22 10:23 杨磊阅读(200) | 评论 (0) | 编辑收藏

Boost Thread学习笔记五

多线程编程中还有一个重要的概念：Thread Local Store（TLS，线程局部存储），在boost中，TLS也被称作TSS，Thread Specific Storage。
boost::thread库为我们提供了一个接口简单的TLS的面向对象的封装，以下是tss类的接口定义：

class tss
{
public:
    tss(boost::function1<void, void*>* pcleanup);
    void* get() const;
    void set(void* value);
    void cleanup(void* p);
};

分别用于获取、设置、清除线程局部存储变量，这些函数在内部封装了TlsAlloc、TlsGetValue、TlsSetValue等API操作，将它们封装成了OO的形式。
但boost将该类信息封装在detail名字空间内，即不推荐我们使用，当需要使用tss时，我们应该使用另一个使用更加方便的类：thread_specific_ptr，这是一个智能指针类，该类的接口如下：

1 class thread_specific_ptr : private boost::noncopyable   // Exposition only
2 {
3 public:
4   // construct/copy/destruct
5   thread_specific_ptr();
6   thread_specific_ptr(void (*cleanup)(void*));
7   ~thread_specific_ptr();
8
9   // modifier functions
10   T* release();
11   void reset(T* = 0);
12
13   // observer functions
14   T* get() const;
15   T* operator->() const;
16   T& operator*()() const;
17 };

即可支持get、reset、release等操作。
thread_specific_ptr类的实现十分简单，仅仅为了将tss类“改装”成智能指针的样子，该类在其构造函数中会自动创建一个tss对象，而在其析构函数中会调用默认参数的reset函数，从而引起内部被封装的tss对象被析构，达到“自动”管理内存分配释放的目的。

以下是一个运用thread_specific_ptr实现TSS的例子：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <boost/thread/tss.hpp>
4 #include <iostream>
5
6 boost::mutex io_mutex;
7 boost::thread_specific_ptr<int> ptr;    // use this method to tell that this member will not shared by all threads
8
9 struct count
10 {
11     count(int id) : id(id) { }
12
13     void operator()()
14     {
15         if (ptr.get() == 0)    // if ptr is not initialized, initialize it
16             ptr.reset(new int(0));    // Attention, we pass a pointer to reset (actually set ptr)
17
18         for (int i = 0; i < 10; ++i)
19         {
20             (*ptr)++;
21             boost::mutex::scoped_lock lock(io_mutex);
22             std::cout << id << ": " << *ptr << std::endl;
23         }
24     }
25
26     int id;
27 };
28
29 int main(int argc, char* argv[])
30 {
31     boost::thread thrd1(count(1));
32     boost::thread thrd2(count(2));
33     thrd1.join();
34     thrd2.join();
35
36     return 0;
37 }

此外，thread库还提供了一个很有趣的函数，call_once，在tss::init的实现中就用到了该函数。
该函数的声明如下：
void call_once(void (*func)(), once_flag& flag);
该函数的Windows实现通过创建一个Mutex使所有的线程在尝试执行该函数时处于等待状态，直到有一个线程执行完了func函数，该函数的第二个参数表示函数func是否已被执行，该参数往往被初始化成BOOST_ONCE_INIT（即0），如果你将该参数初始化成1，则函数func将不被调用，此时call_once相当于什么也没干，这在有时候可能是需要的，比如，根据程序处理的结果决定是否需要call_once某函数func。
call_once在执行完函数func后，会将flag修改为1，这样会导致以后执行call_once的线程（包括等待在Mutex处的线程和刚刚进入call_once的线程）都会跳过执行func的代码。

需要注意的是，该函数不是一个模板函数，而是一个普通函数，它的第一个参数1是一个函数指针，其类型为void (*)()，而不是跟boost库的很多其它地方一样用的是function模板，不过这样也没有关系，有了boost::bind这个超级武器，想怎么绑定参数就随你的便了，根据boost的文档，要求传入的函数不能抛出异常，但从实现代码中好像不是这样。

以下是一个典型的运用call_once实现一次初始化的例子：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/once.hpp>
3 #include <iostream>
4
5 int i = 0;
6 int j = 0;
7 boost::once_flag flag = BOOST_ONCE_INIT;
8
9 void init()
10 {
11     ++i;
12 }
13
14 void thread()
15 {
16     boost::call_once(&init, flag);
17     ++j;
18 }
19
20 int main(int argc, char* argv[])
21 {
22     boost::thread thrd1(&thread);
23     boost::thread thrd2(&thread);
24     thrd1.join();
25     thrd2.join();
26
27     std::cout << i << std::endl;
28     std::cout << j << std::endl;
29
30     return 0;
31 }

结果显示，全局变量i仅被执行了一次++操作，而变量j则在两个线程中均执行了++操作。

posted @ 2008-05-18 18:32 杨磊阅读(1804) | 评论 (1) | 编辑收藏

Boost Thread学习笔记四

barrier
barrier类的接口定义如下：

1 class barrier : private boost::noncopyable   // Exposition only
2 {
3 public:
4   // construct/copy/destruct
5   barrier(size_t n);
6   ~barrier();
7
8   // waiting
9   bool wait();
10 };

barrier类为我们提供了这样一种控制线程同步的机制：
前n - 1次调用wait函数将被阻塞，直到第n次调用wait函数，而此后第n + 1次到第2n - 1次调用wait也会被阻塞，直到第2n次调用，依次类推。
barrier::wait的实现十分简单：

1 barrier::barrier(unsigned int count)
2     : m_threshold(count), m_count(count), m_generation(0)
3 {
4     if (count == 0)
5         throw std::invalid_argument("count cannot be zero.");
6 }
7
8 bool barrier::wait()
9 {
10     boost::mutex::scoped_lock lock(m_mutex);    // m_mutex is the base of barrier and is initilized by it's default constructor.
11     unsigned int gen = m_generation;    // m_generation will be 0 for call 1~n-1, and 1 for n~2n - 1, and so on

12
13     if (--m_count == 0)
14     {
15         m_generation++;    // cause m_generation to be changed in call n/2n/

16         m_count = m_threshold;    // reset count
17         m_cond.notify_all();    // wake up all thread waiting here
18         return true;
19     }
20
21     while (gen == m_generation)    // if m_generation is not changed, lock current thread.
22         m_cond.wait(lock);
23     return false;
24 }

因此，说白了也不过是mutex的一个简单应用。
以下是一个使用barrier的例子：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/barrier.hpp>
3
4 int i = 0;
5 boost::barrier barr(3);    // call barr.wait 3 * n times will release all threads in waiting
6
7 void thread()
8 {
9     ++i;
10     barr.wait();
11 }
12
13 int main()
14 {
15     boost::thread thrd1(&thread);
16     boost::thread thrd2(&thread);
17     boost::thread thrd3(&thread);
18
19     thrd1.join();
20     thrd2.join();
21     thrd3.join();
22
23     return 0;
24 }

如果去掉其中thrd3相关的代码，将使得线程1、2一直处于wait状态，进而使得主线程无法退出。

xtime
xtime是boost::thread中用来表示时间的一个辅助类，它是一个仅包含两个成员变量的结构体：

1 struct xtime
2 {
3 //

4 xtime_sec_t sec;
5 xtime_nsec_t nsec;
6 };

condition::timed_wait、thread::sleep等涉及超时的函数需要用到xtime。
需要注意的是，xtime表示的不是一个时间间隔，而是一个时间点，因此使用起来很不方便。为了方便使用xtime，boost提供了一些辅助的xtime操作函数，如xtime_get、xtime_cmp等。
以下是一个使用xtime来执行sleep的例子（跟简单的一句Sleep比起来，实在是太复杂了），其中用到了xtime初始化函数xtime_get：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/xtime.hpp>
3 #include <iostream>
4
5 int main()
6 {
7     boost::xtime xt;
8     boost::xtime_get(&xt, boost::TIME_UTC);    // initialize xt with current time
9     xt.sec += 1;    // change xt to next second
10     boost::thread::sleep(xt);    // do sleep
11
12     std::cout << "1 second sleep over." << std::endl;
13
14     return 0;
15 }

posted @ 2008-05-18 16:48 杨磊阅读(2099) | 评论 (0) | 编辑收藏

Boost Thread学习笔记三

摘要: 下面先对condition_impl进行简要分析。 condition_impl在其构造函数中会创建两个Semaphore（信号量）：m_gate、m_queue，及一个Mutex（互斥体，跟boost::mutex类似，但boost::mutex是基于CriticalSection<临界区>的）：m_mutex，其中： m_queue 相当于当前所有等待线程的等待队列，构造函数... 阅读全文

posted @ 2008-05-18 16:45 杨磊阅读(1969) | 评论 (1) | 编辑收藏

Boost Thread学习笔记二

除了thread，boost::thread另一个重要组成部分是mutex，以及工作在mutex上的boost::mutex::scoped_lock、condition和barrier，这些都是为实现线程同步提供的。

mutex
boost提供的mutex有6种：
boost::mutex
boost::try_mutex
boost::timed_mutex
boost::recursive_mutex
boost::recursive_try_mutex
boost::recursive_timed_mutex
下面仅对boost::mutex进行分析。
mutex类是一个CriticalSection（临界区）封装类，它在构造函数中新建一个临界区并InitializeCriticalSection，然后用一个成员变量
void* m_mutex;
来保存该临界区结构。
除此之外，mutex还提供了do_lock、do_unlock等方法，这些方法分别调用EnterCriticalSection、 LeaveCriticalSection来修改成员变量m_mutex（CRITICAL_SECTION结构指针）的状态，但这些方法都是private的，以防止我们直接对mutex进行锁操作，所有的锁操作都必须通过mutex的友元类detail::thread::lock_ops<mutex>来完成，比较有意思的是，lock_ops的所有方法：lock、unlock、trylock等都是static的，如lock_ops<Mutex>::lock的实现：

1 template <typename Mutex>
2 class lock_ops : private noncopyable
3 {
4

5 public:
6     static void lock(Mutex& m)
7     {
8         m.do_lock();
9     }
10

11 }

boost::thread的设计者为什么会这么设计呢？我想大概是：
1、boost::thread的设计者不希望被我们直接操作mutex，改变其状态，所以mutex的所有方法都是private的（除了构造函数，析构函数）。
2、虽然我们可以通过lock_ops来修改mutex的状态，如：

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <boost/thread/detail/lock.hpp>
4
5 int main()
6 {
7     boost::mutex mt;
8     //mt.do_lock();        // Error! Can not access private member!
9
10     boost::detail::thread::lock_ops<boost::mutex>::lock(mt);
11
12     return 0;
13 }

但是，这是不推荐的，因为mutex、scoped_lock、condition、barrier是一套完整的类系，它们是相互协同工作的，像上面这么操作没有办法与后面的几个类协同工作。
scoped_lock
上面说过，不应该直接用lock_ops来操作mutex对象，那么，应该用什么呢？答案就是scoped_lock。与存在多种mutex一样，存在多种与mutex对应的scoped_lock：

scoped_lock
scoped_try_lock
scoped_timed_lock

这里我们只讨论scoped_lock。
scoped_lock是定义在namespace boost::detail::thread下的，为了方便我们使用（也为了方便设计者），mutex使用了下面的typedef：
typedef detail::thread::scoped_lock<mutex> scoped_lock;
这样我们就可以通过：
boost::mutex::scoped_lock
来使用scoped_lock类模板了。
由于scoped_lock的作用仅在于对mutex加锁/解锁（即使mutex EnterCriticalSection/LeaveCriticalSection），因此，它的接口也很简单，除了构造函数外，仅有lock/unlock/locked（判断是否已加锁），及类型转换操作符void*，一般我们不需要显式调用这些方法，因为scoped_lock的构造函数是这样定义的：

1 explicit scoped_lock(Mutex& mx, bool initially_locked=true)
2 : m_mutex(mx), m_locked(false)
3 {
4 if (initially_locked) lock();
5 }

注：m_mutex是一个mutex的引用。
因此，当我们不指定initially_locked参数构造一个scoped_lock对象时，scoped_lock会自动对所绑定的mutex加锁，而析构函数会检查是否加锁，若已加锁，则解锁；当然，有些情况下，我们可能不需要构造时自动加锁，这样就需要自己调用lock方法。后面的condition、barrier也会调用scoped_lock的lock、unlock方法来实现部分方法。
正因为scoped_lock具有可在构造时加锁，析构时解锁的特性，我们经常会使用局部变量来实现对mutex的独占访问。

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <iostream>
4
5 boost::mutex io_mutex;
6
7 void count()    // worker function
8 {
9     for (int i = 0; i < 10; ++i)
10     {
11         boost::mutex::scoped_lock lock(io_mutex);
12         std::cout << i << std::endl;
13     }
14 }
15
16 int main(int argc, char* argv[])
17 {
18     boost::thread thrd1(&count);
19     boost::thread thrd2(&count);
20     thrd1.join();
21     thrd2.join();
22
23     return 0;
24 }

在每次输出信息时，为了防止整个输出过程被其它线程打乱，通过对io_mutex加锁（进入临界区），从而保证了输出的正确性。
在使用 scoped_lock时，我们有时候需要使用全局锁（定义一个全局mutex，当需要独占访问全局资源时，以该全局mutex为参数构造一个 scoped_lock对象即可。全局mutex可以是全局变量，也可以是类的静态方法等），有时候则需要使用对象锁（将mutex定义成类的成员变量），应该根据需要进行合理选择。
Java的synchronized可用于对方法加锁，对代码段加锁，对对象加锁，对类加锁（仍然是对象级的），这几种加锁方式都可以通过上面讲的对象锁来模拟；相反，在Java中实现全局锁好像有点麻烦，必须将请求封装到类中，以转换成上面的四种 synchronized形式之一。

condition
condition的接口如下：

1 class condition : private boost::noncopyable   // Exposition only
2 {
3 public:
4   // construct/copy/destruct
5   condition();
6   ~condition();
7
8   // notification
9   void notify_one();
10   void notify_all();
11
12   // waiting
13   template<typename ScopedLock> void wait(ScopedLock&);
14   template<typename ScopedLock, typename Pred> void wait(ScopedLock&, Pred);
15   template<typename ScopedLock>
16     bool timed_wait(ScopedLock&, const boost::xtime&);
17   template<typename ScopedLock, typename Pred>
18     bool timed_wait(ScopedLock&, Pred);
19 };

其中wait用于等待某个condition的发生，而timed_wait则提供具有超时的wait功能，notify_one用于唤醒一个等待该condition发生的线程，notify_all则用于唤醒所有等待该condition发生的线程。

由于condition的语义相对较为复杂，它的实现也是整个boost::thread库中最复杂的（对Windows版本而言，对支持pthread的版本而言，由于pthread已经提供了pthread_cond_t，使得condition实现起来也十分简单），下面对wait和notify_one进行简要分析。
condition内部包含了一个condition_impl对象，由该对象执行来处理实际的wait、notify_one...等操作。

posted @ 2008-05-18 16:20 杨磊阅读(5104) | 评论 (1) | 编辑收藏

Boost Thread学习笔记

thread自然是boost::thread库的主角，但thread类的实现总体上是比较简单的，前面已经说过，thread只是一个跨平台的线程封装库，其中按照所使用的编译选项的不同，分别决定使用 Windows线程API还是pthread，或者Macintosh Carbon平台的thread实现。以下只讨论Windows，即使用 BOOST_HAS_WINTHREADS的情况。
thread类提供了两种构造函数：
thread::thread()
thread::thread(const function0<void>& threadfunc)
第一种构造函数用于调用GetCurrentThread构造一个当前线程的thread对象，第二种则通过传入一个函数或者一个functor来创建一个新的线程。第二种情况下，thread类在其构造函数中间接调用CreateThread来创建线程，并将线程句柄保存到成员变量m_thread中，并执行传入的函数，或执行functor的operator ()方法来启动工作线程。

我们可以用以下三种方式启动一个新线程：
1、传递一个工作函数来构造一个工作线程

2、传递一个functor对象来构造一个工作线程

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <iostream>
4
5 boost::mutex io_mutex;
6
7 struct count
8 {
9     count(int id) : id(id) { }
10
11     void operator()()
12     {
13         for (int i = 0; i < 10; ++i)
14         {
15             boost::mutex::scoped_lock lock(io_mutex);        // lock io, will be explained soon.
16             std::cout << id << ": " << i << std::endl;
17         }
18     }
19
20     int id;
21 };
22
23 int main(int argc, char* argv[])
24 {
25     boost::thread thrd1(count(1));
26     boost::thread thrd2(count(2));
27     thrd1.join();
28     thrd2.join();
29     return 0;
30 }
31

3、无需将类设计成一个functor，借助bind来构造functor对象以创建工作线程

1 #include <boost/thread/thread.hpp>
2 #include <boost/thread/mutex.hpp>
3 #include <boost/bind.hpp>
4 #include <iostream>
5
6 boost::mutex io_mutex;
7
8 struct count
9 {
10     static int num;
11     int id;
12
13     count() : id(num++) {}
14
15     int do_count(int n)
16     {
17         for (int i = 0; i < n; ++i)
18         {
19             boost::mutex::scoped_lock lock(io_mutex);
20             std::cout << id << ": " << i << std::endl;
21         }
22         return id;
23     }
24 };
25
26 int count::num = 1;
27
28 int main(int argc, char* argv[])
29 {
30     count c1;
31     boost::thread thrd1(boost::bind(&count::do_count, &c1, 10));
32     thrd1.join();
33     return 0;
34 }

其中bind是一个函数模板，它可以根据后面的实例化参数构造出一个functor来，上面的boost::bind(&count::do_count, &c1, 10)其实等价于返回了一个functor：
struct countFunctor
{
    int operator() ()
    {
        (&c1)->do_count(10);    // just a hint, not actual code
    }
};
因此，以后就跟2中是一样的了。

posted @ 2008-05-18 14:49 杨磊阅读(5224) | 评论 (0) | 编辑收藏

ZJU Online Judge 1338

这道题有够无聊……

看了半天都没看懂题目是什么，于是直接找了一个能过的代码

后来发现原来就是找连续的上升，下降的序列的长度的平均数

1 #include <stdio.h>
2
3 int upCount, downCount, pendingCount;
4 int numberOfUpSequences, numberOfDownSequences;
5
6 char state;
7
8 int thisValue, lastValue;
9
10 int main()
11 {
12  float avgUp, avgDown;
13  int done = 0;
14  int count;
15  while ( ! done )
16  {
17   state = 'S';
18   upCount = 0; downCount = 0; pendingCount = 0;
19   count = 0;
20   numberOfUpSequences = 0; numberOfDownSequences = 0;
21   while ( 1 )
22   {
23    scanf("%d", & thisValue);
24    if ( (state == 'S') && (thisValue == 0 ) )
25    {
26     done = 1;
27     break;
28    }
29    else if (thisValue == 0)
30     break;
31    switch ( state )
32     {
33      case 'S':
34      state = 'N';
35       break;
36      case 'N':
37     if ( thisValue == lastValue )
38       pendingCount++;
39     else if ( thisValue < lastValue )
40     {
41      state = 'D';
42      downCount = pendingCount + 1;
43      numberOfDownSequences++;
44     }
45     else if ( thisValue > lastValue )
46     {
47      state = 'U';
48      upCount = pendingCount + 1;
49      numberOfUpSequences++;
50     }
51      break;
52     case 'D':
53     if ( thisValue <= lastValue )
54      downCount++;
55     else if ( thisValue > lastValue )
56     {
57      state = 'U';
58      upCount++;
59      numberOfUpSequences++;
60     }
61      break;
62     case 'U':
63     if( thisValue >= lastValue )
64      upCount++;
65     else if ( thisValue < lastValue )
66     {
67      state = 'D';
68      downCount++;
69      numberOfDownSequences++;
70     }
71      break;
72     }
73    lastValue = thisValue;
74    count++;
75   }
76   if ( state != 'S' )
77   {
78    if ( numberOfUpSequences )
79      avgUp = (float)upCount/numberOfUpSequences;
80    else
81      avgUp = 0.0;
82    if ( numberOfDownSequences )
83      avgDown = (float)downCount/numberOfDownSequences;
84    else
85      avgDown = 0.0;
86    printf("Nr values = %d:  ", count);
87    printf("%f %f\n", avgUp, avgDown );
88   }
89  }
90 }
91
92

posted @ 2008-05-11 17:29 杨磊阅读(268) | 评论 (0) | 编辑收藏

ZJU Online Judge 1889

又是一个数学问题

一个同余的问题

(a * b + c) % n=[ (a % n) * b + c] % n

呃，看起来都有点像常识了，可是还是不会，大概高中的时候就没学好

1 #include <iostream>
2
3 using namespace std;
4
5 int main(){
6    int n,rem,digs;
7    while (cin >> n) {
8       for (rem=digs=1;rem%n!=0;digs++) rem = (rem*10+1) % n;
9       printf("%d\n",digs);
10    }
11    return 0;
12 }
13

posted @ 2008-05-10 01:04 杨磊阅读(221) | 评论 (0) | 编辑收藏

ZJU题型分类

初学者题：
1001 1037 1048 1049 1051 1067 1115 1151 1201 1205 1216 1240 1241 1242 1251 1292 1331 1334 1337 1338 1350 1365 1382 1383 1394 1402 1405 1414 1494 1514 1622 1715 1730 1755 1760 1763 1796 1813 1879 1889 1904 1915 1949 2001 2022 2099 2104 2108 2172 2176 2201 2208 2321 2345 2351 2376 2388 2405 2417 2433

模拟问题：

1006 1009 1012 1016 1019 1023 1026 1028 1038 1042 1045 1051 1056 1057 1058 1061 1065 1066 1068 1072 1073 1078 1087 1088 1097 1098 1099 1103 1111 1121 1124 1126 1128 1133 1138 1146 1152 1154 1160 1175 1178 1187 1194 1207 1222 1224 1244 1259 1267 1274 1275 1277 1278 1279 1281 1282 1294 1295 1300 1308 1317 1324 1339 1351 1362 1392 1393 1397 1398 1399 1400 1402 1432 1434 1444 1452 1475 1487 1493 1497 1517 1526 1527 1530 1531 1552 1569 1573 1592 1601 1610 1623 1631 1641 1652 1657 1659 1682 1692 1700 1702 1707 1708 1712 1728 1732 1737 1746 1747 1750 1752 1754 1758 1764 1768 1774 1797 1799 1804 1807 1811 1822 1824 1831 1834 1837 1838 1842 1844 1845 1854 1858 1862 1870 1881 1884 1889 1896 1906 1921 1951 1969 1978 2000 2022 2040 2046 2047 2051 2072 2084 2101 2112 2131 2133 2138 2148 2153 2156 2160 2164 2172 2178 2184 2185 2187 2189 2193 2196 2201 2204 2208 2211 2212 2220 2229 2233 2239 2240 2261 2262 2269 2277 2288 2301 2309 2311 2312 2316 2320 2321 2322 2328 2330 2350 2389 2405 2410 2414 2420 2421 2483 2508 2560 2569 2572 2593 2613 2617 2680 2681 2731 2732 2743

动态规划：

1013 1022 1025 1027 1074 1076 1093 1094 1100 1107 1108 1136 1149 1183 1196 1200 1206 1227 1234 1245 1249 1250 1276 1303 1346 1353 1366 1368 1387 1424 1425 1428 1446 1448 1449 1454 1459 1462 1463 1470 1474 1475 1483 1484 1490 1499 1503 1512 1515 1520 1524 1539 1540 1554 1563 1567 1579 1602 1607 1611 1629 1638 1642 1651 1666 1695 1713 1717 1731 1733 1736 1738 1743 1756 1757 1787 1792 1800 1819 1853 1864 1877 1880 1893 1913 1918 1925 1953 1985 1986 1988 1991 1995 2002 2014 2025 2042 2058 2059 2067 2068 2069 2081 2096 2127 2136 2142 2144 2156 2180 2189 2202 2206 2213 2224 2227 2242 2244 2254 2255 2264 2271 2278 2280 2281 2283 2284 2297 2319 2337 2338 2341 2349 2353 2354 2366 2372 2374 2397 2401 2402 2414 2422 2424 2432 2498 2501 2521 2522 2527 2536 2547 2561 2563 2565 2568 2581 2591 2598 2604 2621 2624 2625 2626 2641 2642 2667 2673 2683 2685 2692 2702 2710 2711 2734 2739 2744 2745

字符串处理问题：

1002 1004 1005 1008 1016 1019 1046 1048 1049 1050 1051 1052 1053 1054 1055 1056 1061 1063 1086 1089 1091 1094 1099 1101 1103 1111 1115 1117 1118 1120 1123 1125 1126 1129 1130 1136 1139 1143 1150 1151 1152 1154 1159 1160 1168 1170 1177 1178 1179 1180 1181 1184 1188 1189 1190 1191 1192 1195 1197 1243 1295 1315 1325 1392 1582 1698 1707 1720 1729 1808 1831 1854 1858 1905 1963 1969 1970 1984

搜索问题：

1002 1003 1008 1031 1038 1039 1041 1060 1063 1069 1080 1083 1088 1089 1103 1144 1155 1190 1204 1217 1229 1249 1297 1301 1344 1355 1361 1412 1415 1435 1443 1457 1479 1505 1518 1530 1593 1649 1671 1675 1686 1709 1711 1719 1742 1832 1909 1935 1940 1977 1984 2031 2033 2043 2053 2093 2103 2110 2128 2165 2233 2241 2252 2276 2288 2355 2372 2374 2412 2416 2418 2437 2440 2442 2466 2471 2475 2477 2509 2515 2531 2534 2580 2588 2594 2631 2633 2688

数论问题：

1007 1028 1088 1113 1133 1160 1222 1278 1284 1312 1314 1385 1489 1526 1530 1569 1577 1596 1601 1652 1657 1712 1797 1842 1889 1906 1951 2000 2022 2028 2060 2095 2105 2156 2189 2212 2233 2277 2288 2305 2316 2320 2330 2360 2371 2400 2410 2414

几何问题：

1010 1032 1037 1041 1081 1090 1104 1123 1139 1165 1199 1426 1439 1460 1472 1597 1608 1648 1683 1910 2015 2102 2107 2157 2228 2234 2318 2335 2347 2352 2361 2370 2375 2394 2403

树型结构问题：

1011 1038 1043 1062 1141 1159 1167 1203 1319 1335 1387 1406 1481 1511 1542 1586 1610 1635 1674 1700 1752 1788 1805 1809 1900 1944 1955 1959 1965 1990 2243 2425

图表问题：

1015 1030 1082 1084 1085 1105 1119 1127 1130 1140 1203 1311 1377 1420 1453 1465 1492 1589 1798 1802 1919 1935 2016 2236 2238 2281 2326

匹配问题：

1002 1059 1077 1137 1140 1157 1197 1231 1364 1516 1525 1576 1626 1654 1882 2067 2192 2221 2223 2333 2362 2404

贪心问题：

1025 1029 1076 1117 1161 1239 1360 1543 2049 2091 2109 2315 2343 2425

最短路问题：

1298 1333 1456 1589 1721 1942 1952

博弈问题：1024 1134 1893 1913

最大流问题：1734 1992 2314

其他问题：

1021 1046 1069 1070 1073 1177 1245 1262 1292 1294 1309 1334 1354 1389 1391 1423 1440 1475 1551 1584 1610 1636 1716 1717 1926 1929 1948 1954 1958 1962 1985 1986 1990 2132 2313 2320

posted @ 2008-05-09 16:31 杨磊阅读(584) | 评论 (0) | 编辑收藏

ZJU Online Judge 1730

呃，数学竟然成了我的弱项，还是我小学奥数没学明白呢……

很简单的题目，题意我就不说了

为了完成反向交换，最少的办法就是从一点把所有人分成两组

然后每个组进行反向交换，最后加起来就是

如果某一点需要交换到距离自己的距离超过n/2时，那就可以放到另外一组，得到的交换步骤肯定比较少

不知道说清楚了没有……

代码在别人那里看到的，最开始自己做的递推公式错了……

1 #include<iostream>
2 using namespace std;
3
4 int d(int n)//懂得原理,就是一个算数
5 {
6  int i,t=0;
7  for(i=1;i<n;i++)
8     t+=i;
9  return t;
10 }
11
12 int main()
13 {
14  int n,i,a,p;
15  while(cin>>n)
16  {
17   for(i=0;i<n;i++)
18   {
19    cin>>a;
20    p=d(a/2)+d(a-a/2);//算式
21    cout<<p<<endl;
22   }
23  }
24  return 0;
25 }

posted @ 2008-05-09 16:23 杨磊阅读(219) | 评论 (0) | 编辑收藏

背包问题

怕忘了，贴上来吧

递推公式：

f(n,m)=max{f(n-1,m), f(n-1,m-w[n])+P(n,m)}

Sample Code

1 #include<stdio.h>
2 int c[10][100];/*对应每种情况的最大价值*/
3 int knapsack(int m,int n)
4 {
5  int i,j,w[10],p[10];
6  for(i=1;i<n+1;i++)
7         scanf("\n%d,%d",&w[i],&p[i]);
8  for(i=0;i<10;i++)
9       for(j=0;j<100;j++)
10            c[i][j]=0;/*初始化数组*/
11  for(i=1;i<n+1;i++)
12       for(j=1;j<m+1;j++)
13            {
14             if(w[i]<=j) /*如果当前物品的容量小于背包容量*/
15                      {
16                       if(p[i]+c[i-1][j-w[i]]>c[i-1][j])
17
18                            /*如果本物品的价值加上背包剩下的空间能放的物品的价值*/
19
20                          /*大于上一次选择的最佳方案则更新c[i][j]*/
21                             c[i][j]=p[i]+c[i-1][j-w[i]];
22                             else
23                             c[i][j]=c[i-1][j];
24                      }
25               else c[i][j]=c[i-1][j];
26             }
27  return(c[n][m]);
28
29 }
30 int main()
31 {
32     int m,n;int i,j;
33     scanf("%d,%d",&m,&n);
34     printf("Input each one:\n");
35     printf("%d",knapsack(m,n));
36     printf("\n");/*下面是测试这个数组,可删除*/
37      for(i=0;i<10;i++)
38       for(j=0;j<15;j++)
39          {
40           printf("%d ",c[i][j]);
41              if(j==14)printf("\n");
42          }
43     system("pause");
44 }
45

posted @ 2008-05-09 15:38 杨磊阅读(302) | 评论 (0) | 编辑收藏

埃拉托斯特尼法(筛素数)

1 #include<stdio.h>
2 #include<iostream>
3 #include<cmath>
4 #include<iomanip>
5 #include<set>
6 using namespace std;
7 void sieve(set<int>& s,int n)
8 {
9     int m,i;
10     s.erase(s.begin (),s.end ());//一定要清空
11     for(i=2;i<n;i++)
12         s.insert (i);
13     int t=sqrt(n);
14     for(m=2;m<=t;m++)
15     {
16         if(s.find (m)!=s.end())
17         {
18             i=2*m;
19             while(i<=n)
20             {
21                 s.erase (i);
22                 i+=m;
23             }
24         }
25     }
26 }
27 int main()
28 {
29     set<int> primeSet;
30     int n;
31     int ccount=0;
32     while(1)
33     {
34     cin>>n;
35     ccount=0;
36     sieve(primeSet,n);
37     set<int>::iterator iter;
38     iter=primeSet.begin ();
39         while(iter!=primeSet.end ())
40         {
41             ccount++;
42
43             cout<<*iter<<" ";
44             iter++;
45             if(ccount%10==0)
46             cout<<endl;
47         }
48         cout<<endl<<ccount <<endl;
49     }
50     return 0;
51 }

素数筛法是这样的：
    1.开一个大的bool型数组prime[]，大小就是n+1就可以了.先把所有的下标为奇数的标为true,下标为偶数的标为false.
    2.然后：
      for( i=3; i<=sqrt(n); i+=2 )
      {   if(prime[i])
          for( j=i+i; j<=n; j+=i ) prime[j]=false;
      }
    3.最后输出bool数组中的值为true的单元的下标，就是所求的n以内的素数了。
    原理很简单，就是当i是质(素)数的时候，i的所有的倍数必然是合数。如果i已经被判断不是质数了，那么再找到i后面的质数来把这个质
数的倍数筛掉。
    一个简单的筛素数的过程：n=30。
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

    第 1 步过后2 4 ... 28 30这15个单元被标成false,其余为true。
    第 2 步开始：
     i=3; 由于prime[3]=true, 把prime[6], [9], [12], [15], [18], [21], [24], [27], [30]标为false.
     i=4; 由于prime[4]=false,不在继续筛法步骤。
     i=5; 由于prime[5]=true, 把prime[10],[15],[20],[25],[30]标为false.
     i=6>sqrt(30)算法结束。
    第 3 步把prime[]值为true的下标输出来：
     for(i=2; i<=30; i++)
     if(prime[i]) printf("%d ",i);
    结果是 2 3 5 7 11 13 17 19 23 29

posted @ 2008-05-08 01:16 杨磊阅读(773) | 评论 (2) | 编辑收藏

to be written

frustum culling,多重纹理,....

posted @ 2008-04-16 13:27 杨磊阅读(99) | 评论 (0) | 编辑收藏

做到这80条，我们就结婚

摘要: 做到这80条，我们就结婚阅读全文

posted @ 2008-04-07 12:11 杨磊阅读(152) | 评论 (0) | 编辑收藏

词汇量测试

http://www.test-your-english-now.net/

今天在这个网站上面做了一下词汇量测试

果然是不行啊，只有56/80的成绩

等我把GT考完了再过来测一次，看看我能有多少

posted @ 2008-04-01 16:21 杨磊阅读(640) | 评论 (3) | 编辑收藏

Things To Do During This Summer Vacation

拍照片
去旅行
小败给我做饭吃
陪小败去烫头发
教小败JAVA
买小甘薯
研究一下网站的东西
做gym
跟小败回北京看爸妈
去跟小败做陶艺
跟小败去印带有我们照片的T-Shirt

posted @ 2008-03-21 22:52 杨磊阅读(150) | 评论 (0) | 编辑收藏

SGU 102

本来想直接用GCD解决的，后来找了一下，发现了更好的办法

欧拉函数：
欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数 n ，小于 n 且和 n 互质的正整数（包括 1）的个数，记作 φ(n) 。

完全余数集合：
定义小于 n 且和 n 互质的数构成的集合为 Zn ，称呼这个集合为 n 的完全余数集合。显然 |Zn| ＝φ(n) 。

有关性质：
对于素数 p ，φ(p) = p -1 。
对于两个不同素数 p， q ，它们的乘积 n = p * q 满足 φ(n) = (p -1) * (q -1) 。
这是因为 Zn = {1, 2, 3, ... , n - 1} - {p, 2p, ... , (q - 1) * p} - {q, 2q, ... , (p - 1) * q} ，则 φ(n) = (n - 1) - (q - 1) - (p - 1) = (p -1) * (q -1) ＝φ(p) * φ(q) 。

欧拉定理：
对于互质的正整数 a 和 n ，有 a^φ(n) ≡ 1 mod n 。

证明：
( 1 ) 令 Zn = {x₁, x₂, ..., x_φ(n)} ， S = {a * x₁ mod n, a * x₂ mod n, ... , a * x_φ(n) mod n} ，
        则 Zn = S 。
        ① 因为 a 与 n 互质， x_i (1 ≤ i ≤ φ(n)) 与 n 互质，所以 a * x_i 与 n 互质，所以 a * x_i mod n ∈ Zn 。
        ② 若 i ≠ j ，那么 x_i ≠ x_j，且由 a, n互质可得 a * x_i mod n ≠ a * x_j mod n （消去律）。

( 2 )     a^φ(n)* x₁* x₂ *... * x_φ(n) mod n
      ≡ (a * x₁) * (a * x₂) * ... * (a * x_φ(n)) mod n
      ≡ (a * x₁ mod n) * (a * x₂mod n) * ... * (a * x_φ(n) mod n) mod n
      ≡ x₁* x₂* ... * x_φ(n)mod n
      对比等式的左右两端，因为 x_i (1 ≤ i ≤ φ(n)) 与 n 互质，所以 a^φ(n) ≡ 1 mod n （消去律）。
注：
消去律：如果 gcd(c,p) = 1 ，则 ac ≡ bc mod p ⇒ a ≡ b mod p 。

代码如下：

import java.util.*;

import java.io.*;

public class Solution

{

public static void main (String[] argv) throws IOException

{

BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

StringTokenizer st = new StringTokenizer(in.readLine());

int n = Integer.parseInt(st.nextToken());

double j = n;

for (int i = 2; i <= n;i++)

if (n%i==0)

{

j = j * (1 - 1/(double)i);

while (n%i==0)

n = n / i;

}

System.out.println((int)j);

}

posted @ 2008-03-14 23:11 杨磊阅读(462) | 评论 (1) | 编辑收藏

2008年3月14日

Big and Little Endian

Basic Memory Concepts

Storing Words in Memory

Big Endian

Little Endian

Which Way Makes Sense?

History of Endian-ness

Misconceptions

C-style strings

留言簿(1)

随笔分类

随笔档案

相册

搜索

最新评论