无界
If the only tool you have is a hammer, you tend to see every problem as a nail.
BlogJava | 首页 | 发新随笔 | 发新文章 | 联系 | 聚合 | 管理

2009年4月22日

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 杨磊 阅读(353) | 评论 (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 杨磊 阅读(262) | 评论 (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 杨磊 阅读(175) | 评论 (0) | 编辑 收藏
 
Starry Night (USACO)
     摘要: 绝对，非常考耐心，细心的一道题目，这道题目充分的说明我是考虑问题不全面的人 所以现在看来TopCoder的测试数据还都算是比较弱的，真的没有极其变态的，而且TopCoder的题目其实没有超级复杂的，或许是因为我从来没做过第三题吧。 回正题。 这道题目其实一看就知道怎么做，但是就一个字烦 首先你要用FloodFill把所有的Cluster标注出来，这个不难，而且速度很快，时间...  阅读全文
posted @ 2009-04-28 21:53 杨磊 阅读(475) | 评论 (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
  1. First, The choice of what models to create has a profound influence on how a problem is attacked and how a solution is shaped.
  2. Second, Every model may be expressed at different levels of precision.
  3. Third, The best models are connected to reality.
  4. 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:
  1. the UML's basic building blocks
  2. the rules that dictate how those building blocks may be put together
  3. some common mechanisms that apply throughout the UML
The vocabulary of the UML encompasses three kinds of building blocks:
  1. Things
  2. Relationships
  3. Diagrams
Three kinds of relationships that are most important: dependencies, generalizations, and associations.
  1. Dependencies are using relationships. For example, pipes depend on the water heater to heat the water they carry.
  2. 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.
  3. 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 杨磊 阅读(159) | 评论 (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) | 编辑 收藏
 
随笔：99 文章：-1 评论：17 引用：0
<2009年4月>
日一二三四五六
2930311234
567891011
12131415161718
19202122232425
262728293012
3456789

留言簿(1)

  • 给我留言
  • 查看公开留言
  • 查看私人留言

随笔分类

  • ACM(43) (rss)
  • Boost(5) (rss)
  • 开发感言(2) (rss)
  • 心情日记(3) (rss)

随笔档案

  • 2009年5月 (12)
  • 2009年4月 (26)
  • 2009年3月 (5)
  • 2009年2月 (7)
  • 2009年1月 (1)
  • 2008年12月 (1)
  • 2008年11月 (4)
  • 2008年10月 (1)
  • 2008年8月 (10)
  • 2008年7月 (1)
  • 2008年6月 (7)
  • 2008年5月 (16)
  • 2008年4月 (3)
  • 2008年3月 (2)
  • 2008年2月 (1)
  • 2007年12月 (1)

相册

  • BlogPicture

搜索

  •  

最新评论

  • 1. re: Boost Thread学习笔记三
  • Mediator的构造函数也许缺少一句如下：
    for ( int i = 0; i < _slotCount; i++ ) _pSlot[i] = NULL;
  • --Harly
  • 2. re: SGU 102
  • 博主这个代码的原理是什么啊？看不大懂欸
  • --lph
  • 3. re: Boost Thread学习笔记五
  • 确实厉害
  • --12
  • 4. re: USACO 终于做完了
  • TOPCODER的数据更坑爹。各种challenge会导致各种刁钻数据都被选手钻研出来了
  • --cot
  • 5. re: 各种话题
  • 评论内容较长,点击标题查看
  • --zvin

Powered by: 博客园
模板提供：沪江博客
Copyright ©2024 杨磊