Monthly Archives: November 2014

POJ 1330-Nearest Common Ancestors

POJ 1330-Nearest Common Ancestors
Nearest Common Ancestors
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 19432 Accepted: 10292
Description
A rooted tree is a well-known data structure in computer science and engineering. An example is shown below:
In the figure, each node is labeled with an integer from {1, 2,...,16}. Node 8 is the root of the tree. Node x is an ancestor of node y if node x is in the path between the root and node y. For example, node 4 is an ancestor of node 16. Node 10 is also an ancestor of node 16. As a matter of fact, nodes 8, 4, 10, and 16 are the ancestors of node 16. Remember that a node is an ancestor of itself. Nodes 8, 4, 6, and 7 are the ancestors of node 7. A node x is called a common ancestor of two different nodes y and z if node x is an ancestor of node y and an ancestor of node z. Thus, nodes 8 and 4 are the common ancestors of nodes 16 and 7. A node x is called the nearest common ancestor of nodes y and z if x is a common ancestor of y and z and nearest to y and z among their common ancestors. Hence, the nearest common ancestor of nodes 16 and 7 is node 4. Node 4 is nearer to nodes 16 and 7 than node 8 is.
For other examples, the nearest common ancestor of nodes 2 and 3 is node 10, the nearest common ancestor of nodes 6 and 13 is node 8, and the nearest common ancestor of nodes 4 and 12 is node 4. In the last example, if y is an ancestor of z, then the nearest common ancestor of y and z is y.
Write a program that finds the nearest common ancestor of two distinct nodes in a tree.
Input
The input consists of T test cases. The number of test cases (T) is given in the first line of the input file. Each test case starts with a line containing an integer N , the number of nodes in a tree, 2<=N<=10,000. The nodes are labeled with integers 1, 2,..., N. Each of the next N -1 lines contains a pair of integers that represent an edge --the first integer is the parent node of the second integer. Note that a tree with N nodes has exactly N - 1 edges. The last line of each test case contains two distinct integers whose nearest common ancestor is to be computed.
Output
Print exactly one line for each test case. The line should contain the integer that is the nearest common ancestor.
Sample Input
2
16
1 14
8 5
10 16
5 9
4 6
8 4
4 10
1 13
6 15
10 11
6 7
10 2
16 3
8 1
16 12
16 7
5
2 3
3 4
3 1
1 5
3 5
Sample Output
4
3
Source
Taejon 2002


昨天被hihoCoder Problem 1067: 最近公共祖先·二的离线算法虐了之后,今天在POJ上找了一个水题来重塑信心,这个题也是最近公共祖先问题,只不过它是目前为止最简单的,和hihoCoder Problem 1062: 最近公共祖先·一类似,甚至更简单,因为这个题每个case只询问一次,所以没必要用离线算法,而且给的就是数字,不是字符串,连转换都不要。直接记录一个节点node1的所有祖先,然后从下往上查找另一个节点node2的所有祖先,每找到一个祖先,则判断这个祖先是否是node1的祖先,如果是,则这就是他们的公共祖先。
这一次我甚至连set和map都没有用,因为给定的是连续的整数,直接用数组当hash即可,而且查找效率比set和map还快。
完整代码如下:

#include<iostream>
#include<vector>
using namespace std;
int main()
{
     //freopen("input.txt","r",stdin);
     int t,n;
     int node1,node2;
     cin>>t;
     while(t--)
     {
          cin>>n;
          vector<int> s_f(n+1,0);//s_f[i]为第i个节点的父亲,开始时所有节点的父亲为0
          for(int i=0;i<n-1;i++)
          {
               cin>>node1>>node2;
               s_f[node2]=node1;//保存输入关系
          }
          cin>>node1>>node2;
          vector<int> node1_father(n+1,0);//node1的父亲
          node1_father[node1]=1;//自己是自己的祖先
          while(s_f[node1]!=0)
          {
               node1_father[s_f[node1]]=1;//记录哪些点是node1的父亲
               node1=s_f[node1];
          }
          if(node1_father[node2]!=0)//node2也是自己的祖先
          {
               cout<<node2<<endl;
               continue;
          }
          while(s_f[node2]!=0)
          {
               if(node1_father[s_f[node2]]!=0)//从下网上找node2的祖先是否出现在node1的祖先里
               {
                    cout<<s_f[node2]<<endl;
                    break;
               }
               else
                    node2=s_f[node2];
          }
     }
     return 0;
}

本代码提交AC,用时125MS,内存336K。
关于最近公共祖先问题,还有一种牛逼的在线算法RMQ,在hihoCoder上也有提到,下回再战!

hihoCoder 1067-最近公共祖先·二

hihoCoder 1067-最近公共祖先·二
#1067 : 最近公共祖先·二
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
上上回说到,小Hi和小Ho用非常拙劣——或者说粗糙的手段山寨出了一个神奇的网站,这个网站可以计算出某两个人的所有共同祖先中辈分最低的一个是谁。远在美国的他们利用了一些奇妙的技术获得了国内许多人的相关信息,并且搭建了一个小小的网站来应付来自四面八方的请求。
但正如我们所能想象到的……这样一个简单的算法并不能支撑住非常大的访问量,所以摆在小Hi和小Ho面前的无非两种选择:
其一是购买更为昂贵的服务器,通过提高计算机性能的方式来满足需求——但小Hi和小Ho并没有那么多的钱;其二则是改进他们的算法,通过提高计算机性能的利用率来满足需求——这个主意似乎听起来更加靠谱。
于是为了他们第一个在线产品的顺利运作,小Hi决定对小Ho进行紧急训练——好好的修改一番他们的算法。
而为了更好的向小Ho讲述这个问题,小Hi将这个问题抽象成了这个样子:假设现小Ho现在知道了N对父子关系——父亲和儿子的名字,并且这N对父子关系中涉及的所有人都拥有一个共同的祖先(这个祖先出现在这N对父子关系中),他需要对于小Hi的若干次提问——每次提问为两个人的名字(这两个人的名字在之前的父子关系中出现过),告诉小Hi这两个人的所有共同祖先中辈分最低的一个是谁?
提示一:老老实实分情况讨论就不会出错的啦!
提示二:并查集其实长得很像一棵树你们不觉得么?
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,意义如前文所述。
每组测试数据的第2~N+1行,每行分别描述一对父子关系,其中第i+1行为两个由大小写字母组成的字符串Father_i, Son_i,分别表示父亲的名字和儿子的名字。
每组测试数据的第N+2行为一个整数M,表示小Hi总共询问的次数。
每组测试数据的第N+3~N+M+2行,每行分别描述一个询问,其中第N+i+2行为两个由大小写字母组成的字符串Name1_i, Name2_i,分别表示小Hi询问中的两个名字。
对于100%的数据,满足N<=10^5,M<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),所有询问中出现过的名字均在之前所描述的N对父子关系中出现过,第一个出现的名字所确定的人是其他所有人的公共祖先。
输出
对于每组测试数据,对于每个小Hi的询问,按照在输入中出现的顺序,各输出一行,表示查询的结果:他们的所有共同祖先中辈分最低的一个人的名字。
样例输入
4
Adam Sam
Sam Joey
Sam Micheal
Adam Kevin
3
Sam Sam
Adam Sam
Micheal Kevin
样例输出
Sam
Adam
Adam


hihoCoder确实是个练习算法的好网站,之前我们写过朴素的最近公共祖先问题:hihoCoder Problem 1062: 最近公共祖先·一,但那是一个效率比较低的方法,这一次,hihoCoder详细给我们介绍了最近公共祖先的离线算法,而且讲解非常详细。
网站上的讲解详细,易于理解,我这里简单概括一下。所谓离线算法就是先把询问搜集起来,如果某个询问能先回答,则记录答案,直到把所有询问都解答了;与之相对的是在线算法,也就是每提出一个询问,我都要实时的马上回答。
离线算法综合了DFS和并查集。给定一个族谱(树形结构),我们先把每一个节点染成白色,并且在初始并查集中,每个点都是一个独立的集合,然后从树根开始深度优先遍历,当第一次经过某个节点a的时候,把它由白色改为灰色;如果第二次访问该节点的时候(也就是离开该点的时候),则把它由灰色改为黑色。
当a每次由白变灰之后,查看询问中是否出现过该节点,如果出现了,则查看询问中另一个节点b的颜色,如果b是灰色,则<a,b>的最近公共祖先就是b,因为b是灰色的,所以访问a之前肯定访问了b,所以它们的最近公共祖先是b;如果b是黑色,此时已经离开b了,并不能直接说明a和b的关系,但是<a,b>的最近公共祖先肯定在灰色链上,所以我们只要找出b向上的第一个灰色节点,就是<a,b>的最近公共祖先;如果b是白色,则说明b还没有访问,没有关于b的信息,所以我们暂时不管这个询问,等到访问到b时,a肯定不是白色,这是可以依据前两条规则得出它们的最近公共祖先。
当a每次由灰变黑之后,我们需要在并查集中将a和a的直接父节点合并UNION,因为当a由灰变黑时,a及其子树都访问结束了,但是a的直接父节点还没有访问结束,也就是说a的直接父节点还是灰色的,这样我们就记录了a向上的第一个灰色节点,这为上面的第二种情况判断做准备。
最近公共祖先的离线算法概括起来就是上面的内容,简单易懂也很强大。但是因为算法既包含DFS,又包含并查集,对初学者来说有一定的难度,而且这个题给出的数据是字符串形式的,数据量又很大,有很多细节需要注意。
我先把完整的代码贴出来,然后讲一下主要过程。

#include<iostream>
#include<string>
#include<map>
#include<vector>
using namespace std;
const int MAX_N=100010;//最大人数
map<string,int> name_index;//名字转换为数字
vector<string> index_name(MAX_N);//数字转换为名字
int color[MAX_N]={0};//0:白;1:灰;2:黑,初始颜色都是白色
int s_f[MAX_N];//son_father。s_f[i]表示第i个儿子的直接父亲
vector<vector<int> > f_s(MAX_N);//f_s[i]表示第i个父亲的所有孩子
vector<vector<int> > show_at(MAX_N);//show_at[i]表示第i个人在哪些询问里出现过
int q_l[MAX_N];//第i个询问的左边
int q_r[MAX_N];//第i个询问的右边
int father[MAX_N];//用于并查集,和s_f不一样
vector<string> ans;//最终结果
//保存某个人的信息,并返回其下标
int store_name(string name)
{
     map<string,int>::iterator it=name_index.find(name);
     if(it==name_index.end())//还不存在
     {
          int curr_index=name_index.size();//用当前已有人数作为其下标,正好是递增的。
          name_index.insert(make_pair(name,curr_index));
          index_name[curr_index]=name;//记录
          father[curr_index]=curr_index;//初始的时候,并查集中每个元素都是一个独立的集合
          return curr_index;//返回下标
     }
     else
          return it->second;//已经存在,直接返回
}
//并查集FIND操作
int find_father(int name)
{
     return name==father[name]?name:(father[name]=find_father(father[name]));
}
//并查集UNION操作
void union_father(int name1,int name2)
{
     father[find_father(name1)]=find_father(name2);
}
//深度遍历族谱树
void DFS(int root)
{
     color[root]=1;//首先修改颜色为灰色
     int show_time=show_at[root].size();//查看该元素是否在询问里出现
     if(show_time!=0)
     {
          for(int i=0;i<show_time;i++)//判断所有询问
          {
               int column=show_at[root][i];
               int left=q_l[column];//找到该询问的左右元素
               int right=q_r[column];
               if(left==right)//如果是左右相同,则该自身即是其最近公共祖先
                    ans[column]=index_name[left];
               else
               {
                    if(left==root)//判断当前访问的是左边的还是右边的
                    {
                         if(color[right]==1)//另一个点为灰色
                              ans[column]=index_name[right];//结果即为该灰色点
                         else if(color[right]=2)//另一个点为黑色
                              ans[column]=index_name[find_father(right)];//找其向上最近的灰色节点
                    }
                    else
                    {
                         if(color[left]==1)//另一个点为灰色
                              ans[column]=index_name[left];
                         else if(color[left]=2)//另一个点为黑色
                              ans[column]=index_name[find_father(left)];
                    }
               }
          }
     }
     int sons=f_s[root].size();//查看是否有孩子节点
     if(sons!=0)
     {
          for(int i=0;i<sons;i++)
               DFS(f_s[root][i]);//深度遍历其所有孩子
     }
     color[root]=2;//改颜色为黑色
     union_father(root,s_f[root]);//和直接父节点UNION
}
int main()
{
     ios_base::sync_with_stdio(false);//取消同步,加速
     cin.tie(0);
     //freopen("input.txt","r",stdin);
     int n,m;
     string name1,name2;
     int index1,index2;
     cin>>n;
     while(n--)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          f_s[index1].push_back(index2);
          s_f[index2]=index1;
     }
     cin>>m;
     ans.resize(m);
     for(int i=0;i<m;i++)
     {
          cin>>name1>>name2;
          index1=store_name(name1);
          index2=store_name(name2);
          q_l[i]=index1;
          q_r[i]=index2;
          show_at[index1].push_back(i);
          show_at[index2].push_back(i);
     }
     DFS(0);
     for(int i=0;i<m;i++)
          cout<<ans[i]<<endl;
     return 0;
}

摆在我们面前的第一个问题就是数据的输入问题,题目给的每个人名都是字符串,当然我们可以直接用字符串构建一个树结构,然后进行查找、比较、赋值等操作,但是这样的时空效率都比较低,所以我们可以先用map<string,int> name_index和vector<string> index_name来记录人名字符串和人名数字下标,这样我们在DFS+并查集的时候可以只使用数字下标,到最后输出的时候再转换为字符串,提高效率。记录并返回人名数字下标的操作在函数int store_name(string name);中。
我们还需要记录父子关系,因为一个父亲可以有多个孩子,所以父亲-孩子关系需要用二维数组vector<vector<int> > f_s(MAX_N);来表示;而一个孩子只可能有一个父亲,所以孩子-父亲关系可以用一维数组int s_f[MAX_N];来表示。
还有两个数组需要初始化,每个节点的颜色初始化为白色,在并查集中每个节点单独为一个集合。
然后就是存储询问了。正如前面对LCA离线算法的描述,每当一个节点从白色变为灰色时,我们都要查看询问中是否出现过该节点。输入的询问中有很多节点,怎样来快速判断所有询问中是否有某个节点以及该询问中的另一个节点呢?如果这个问题处理不好,很可能就是TLE,反正我前两个版本都是因为这个原因TLE的。
这个问题可以通过两个步骤来解决,都是用空间来换时间。因为每一个询问都是由左右两个人名组成的,那么我们先把每次询问的左右两个人名记录在int q_l[MAX_N];和int q_r[MAX_N];中。然后还用一个二维数组vector<vector<int> > show_at(MAX_N);来记录某一个节点在哪些询问里出现过。这样当我们DFS到某个节点a时,首先查看show_at[a]这个数组是否为空,如果为空,说明a没有出现在任何一次询问中;如果不为空,则show_at[a]记录了a出现的所有询问的序号,根据这个序号,我们再去查q_l和q_r,这样就可以取出a出现时的那个询问的左右两个人名是什么了。所以整个过程只需要O(1)的时间,大大提高了时间效率。
因为题目中说明了

第一个出现的名字所确定的人是其他所有人的公共祖先。

所以我们以第一个人名下标0来DFS树结构。DFS的过程和上面的算法描述一致,我这里就不多说了,代码中都有详细的注释。
还有一个小问题需要注意,因为编译器不一样,在用vector声明二维数组的时候,我在VS2010下可以这样:

vector<vector<int>> a; //sth

但是提交之后会报Compile Error的错误:error: ‘>>’ should be ‘> >’ within a nested template argument list,也就是说这个编译器把>>看成了移位操作符,所以我们在两个箭头之间加一个空格> >这样就没问题了。
我上面的代码版本提交后AC,用时711MS,内存30MB。这是我迄今为止内存消耗最大的一次AC。
总的来说,这个题是好题,很考验选手的综合能力,特别是本题用到的各种数据结构较多,需要全盘考虑,不断优化。

POJ 1080-Human Gene Functions

POJ 1080-Human Gene Functions
Human Gene Functions
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 17334 Accepted: 9637
Description
It is well known that a human gene can be considered as a sequence, consisting of four nucleotides, which are simply denoted by four letters, A, C, G, and T. Biologists have been interested in identifying human genes and determining their functions, because these can be used to diagnose human diseases and to design new drugs for them.
A human gene can be identified through a series of time-consuming biological experiments, often with the help of computer programs. Once a sequence of a gene is obtained, the next job is to determine its function.
One of the methods for biologists to use in determining the function of a new gene sequence that they have just identified is to search a database with the new gene as a query. The database to be searched stores many gene sequences and their functions – many researchers have been submitting their genes and functions to the database and the database is freely accessible through the Internet.
A database search will return a list of gene sequences from the database that are similar to the query gene.
Biologists assume that sequence similarity often implies functional similarity. So, the function of the new gene might be one of the functions that the genes from the list have. To exactly determine which one is the right one another series of biological experiments will be needed.
Your job is to make a program that compares two genes and determines their similarity as explained below. Your program may be used as a part of the database search if you can provide an efficient one.
Given two genes AGTGATG and GTTAG, how similar are they? One of the methods to measure the similarity
of two genes is called alignment. In an alignment, spaces are inserted, if necessary, in appropriate positions of
the genes to make them equally long and score the resulting genes according to a scoring matrix.
For example, one space is inserted into AGTGATG to result in AGTGAT-G, and three spaces are inserted into GTTAG to result in –GT--TAG. A space is denoted by a minus sign (-). The two genes are now of equal
length. These two strings are aligned:
AGTGAT-G
-GT--TAG
In this alignment, there are four matches, namely, G in the second position, T in the third, T in the sixth, and G in the eighth. Each pair of aligned characters is assigned a score according to the following scoring matrix.
![](http://poj.org/images/1080/1080_1.gif)
denotes that a space-space match is not allowed. The score of the alignment above is (-3)+5+5+(-2)+(-3)+5+(-3)+5=9.
Of course, many other alignments are possible. One is shown below (a different number of spaces are inserted into different positions):
AGTGATG
-GTTA-G
This alignment gives a score of (-3)+5+5+(-2)+5+(-1) +5=14. So, this one is better than the previous one. As a matter of fact, this one is optimal since no other alignment can have a higher score. So, it is said that the
similarity of the two genes is 14.
Input
The input consists of T test cases. The number of test cases ) (T is given in the first line of the input file. Each test case consists of two lines: each line contains an integer, the length of a gene, followed by a gene sequence. The length of each gene sequence is at least one and does not exceed 100.
Output
The output should print the similarity of each test case, one per line.
Sample Input
2
7 AGTGATG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA
Sample Output
14
21
Source
Taejon 2001


这一题是LCS(最长公共子序列)的变种,但是还是用DP来解决。
题目问给两个基因序列s1,s2插入'-',使得两个序列的`相似度`最大,求最大的相似度。假设f[i-1,j-1]为s1[1,...,i-1]和s2[1,...,j-1]的最大相似度,怎么通过f[i-1,j-1]来求f[i,j]呢?分如下三种情况:(这里假设f下标从0开始,s1,s2下标从1开始)
1. s1取第i个基因,s2取'-',则f[i,j]=f[i-1,j]+score[s1[i]],'-'];
2. s1取'-',s2取第j个基因,则f[i,j]=f[i,j-1]+score['-',s2[j]];
3. s1取第i个基因,s2取第j个基因,则f[i,j]=f[i-1,j-1]+score[s1[i],s2[j]];
所以f[i,j]即为上述三者的最大值。
对于初始值,自然有f[0,0]=0; f[0,j]=f[0,j-1]+score['-',s2[j]]; f[i,0]=f[i-1,0]+score[s1[i],'-']。
有了上述状态转换方程及初始值,便可以写出DP代码:

#include<iostream>
#include<string>
using namespace std;
int score['T'+1]['T'+1];
int inf=-5;//负无穷
const int MAX_N=101;//基因最大长度
int f[MAX_N][MAX_N];//f[i][j]表示s1[0...i-1]和s2[0...j-1]的相识度
//初始化分数表
void init_score()
{
     score['A']['A']=score['C']['C']=score['G']['G']=score['T']['T']=5;//可以连续赋值
     score['-']['-']=inf;//负无穷
     score['A']['C']=score['C']['A']=-1;
     score['A']['G']=score['G']['A']=-2;
     score['A']['T']=score['T']['A']=-1;
     score['A']['-']=score['-']['A']=-3;//'-'的ASCII小于'T'
     score['C']['G']=score['G']['C']=-3;
     score['C']['T']=score['T']['C']=-2;
     score['C']['-']=score['-']['C']=-4;
     score['G']['T']=score['T']['G']=-2;
     score['G']['-']=score['-']['G']=-2;
     score['T']['-']=score['-']['T']=-1;
}
//动态规划求值
int DP(string s1,int n1,string s2,int n2)
{
     f[0][0]=0;
     for(int i=1;i<=n1;i++)
          //f[0][i]=f[0][i-1]+score['-'][s1[i-1]];//注意顺序不要弄错了,这里表示i,s1为纵轴;j,s2为横轴
          f[i][0]=f[i-1][0]+score[s1[i-1]]['-'];
     for(int j=1;j<=n2;j++)
          //f[j][0]=f[j-1][0]+score[s2[j-1]]['-'];
          f[0][j]=f[0][j-1]+score['-'][s2[j-1]];
     for(int i=1;i<=n1;i++)
     {
          for(int j=1;j<=n2;j++)
          {
               int a=f[i-1][j]+score[s1[i-1]]['-'];
               int b=f[i][j-1]+score['-'][s2[j-1]];
               int c=f[i-1][j-1]+score[s1[i-1]][s2[j-1]];
               int rs=a>b?a:b;
               f[i][j]=rs>c?rs:c;//三者最大值
          }
     }
     return f[n1][n2];
}
int main()
{
     //freopen("input.txt","r",stdin);
     int t;
     cin>>t;
     init_score();
     while(t--)
     {
          int n1,n2;
          string s1,s2;
          cin>>n1>>s1>>n2>>s2;
          cout<<DP(s1,n1,s2,n2)<<endl;
     }
     return 0;
}

本代码提交AC,用时0MS,内存272K。

POJ 1094-Sorting It All Out

POJ 1094-Sorting It All Out
Sorting It All Out
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 28397 Accepted: 9814
Description
An ascending sorted sequence of distinct values is one in which some form of a less-than operator is used to order the elements from smallest to largest. For example, the sorted sequence A, B, C, D implies that A < B, B < C and C < D. in this problem, we will give you a set of relations of the form A < B and ask you to determine whether a sorted order has been specified or not.
Input
Input consists of multiple problem instances. Each instance starts with a line containing two positive integers n and m. the first value indicated the number of objects to sort, where 2 <= n <= 26. The objects to be sorted will be the first n characters of the uppercase alphabet. The second value m indicates the number of relations of the form A < B which will be given in this problem instance. Next will be m lines, each containing one such relation consisting of three characters: an uppercase letter, the character "<" and a second uppercase letter. No letter will be outside the range of the first n letters of the alphabet. Values of n = m = 0 indicate end of input.
Output
For each problem instance, output consists of one line. This line should be one of the following three:
Sorted sequence determined after xxx relations: yyy...y.
Sorted sequence cannot be determined.
Inconsistency found after xxx relations.
where xxx is the number of relations processed at the time either a sorted sequence is determined or an inconsistency is found, whichever comes first, and yyy...y is the sorted, ascending sequence.
Sample Input
4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0
Sample Output
Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.
Source
East Central North America 2001


这一题有一定的难度,有很多细节需要兼顾。题目的意思为:给定一系列小于关系,问能否从中得出一个严格有序的序列。需要明确的是,题目所指的严格有序的序列需要满足如下几个条件:1.包含n个所有字母;2.每个字母都有明确的大小关系。
另外根据测试样例我们可以知道:每输入一个关系都要判断一次,如果可以得到严格有序序列,则输出结果,但这个测试用例后续的输入还是要输入的;如果出现相互依赖(环),也输出结果,同样的,这个测试用例后面的数据还是要输入;如果所有关系都输入了还不能得出一个严格有序的序列,则输入无法判断。
这一题很自然的想到用拓扑排序来做。下面我们先来回顾一下拓扑排序。

如上图是《算法导论》中关于拓扑排序的一个例子,这是某位教授起床后需要穿戴衣物的顺序,比如只有先穿了袜子才能穿鞋、但是穿鞋和戴手表并没有严格的先后顺序。拓扑排序的功能就是根据图(a)的拓扑图,得到图(b)中节点的先后顺序。
常见的拓扑排序算法有两种:Kahn算法和基于DFS的算法,这两种算法都很好理解,详细的解释请看维基百科Topological sorting,下面简要介绍一下这两个算法。
Kahn算法
拓扑排序强调先后顺序,先做的事情排在前面,那么反应到有向图上,最先做的事情就是没有入度的节点(可能 有/没有 出度)。所以Kahn算法很朴素,他就是把所有没有入度的点加入到集合S中,在S不为空的情况下循环:从S中取出一个节点a,把a加入到L链表的尾部,对于每一条a的出度边,如< a,b>,删除它,并把b的入度减一,如果b的入度也为0了,则又把b加入到集合S中。如果S为空了,但是图中还有边未删除,说明图中至少有一个,拓扑排序失败;否则拓扑排序成功,且链表L保存了一条拓扑排序链。(链表L的生成使用尾插法)
维基百科上关于Kahn算法的伪代码描述如下:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else
    return L (a topologically sorted order)

基于DFS的算法
这个算法类似于深度优先搜索,它不断的递归访问下一个节点,直到不能再递归时,把最后一个节点插入到链表的头部,然后返回。
拿上面穿衣物的例子来说,如果我们首先选择了内裤,则可以递归访问裤子->腰带->夹克。到夹克时,无法递归了,则把夹克插入到L的头部,返回到腰带,腰带也无法递归了,则把腰带插入到L的头部,这个时候就形成了L:腰带->夹克的中间结果,也就是腰带要在夹克前面穿。这个算法不太好表述,还请大家看伪代码领会。(链表L的生成使用头插法)

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n)
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

那么问题来了,只使用拓扑排序并不能满足本题的要求。因为本题问的是能否生成一个严格有序的序列,一个拓扑序列并不一定是严格有序的序列,比如上图中的穿衣物生成的拓扑序列中,先穿袜子和先穿衬衫都是可以的,也就是说袜子和衬衫是没有明确的先后顺序的,所以这不是一个严格有序的序列。再比如下图的拓扑序列,也不是一个严格有序的序列,因为C和A,D,E,F无法比较大小。

那么怎么判断生产的拓扑序列是否是严格的有序序列呢?基本原则就是就是任意取序列中的两个点,看能不能比较大小,如果能则是严格有序,否则不是。
我起初想到的是对拓扑序列的第一个节点进行深度遍历,遍历之后如果所有的节点都访问了,那么这是一个严格有序的序列,否则不是。后来证明这是不正确的,比如上图从B点开始DFS,遍历完F之后回溯到B点再访问C点,这样即使它不是严格有序的,但DFS还是访问了所有节点。
后来想到了Floyd算法。对拓扑图进行Floyd算法之后,会得到任意两点之间的最短距离。如果拓扑序列中前面的节点都可以到达后面的节点(最短距离不为无穷),则是严格有序的;否则不是。比如上图的一个拓扑序列为BCADEF(不唯一,还可以是BADEFC),但是C到ADEF的最短距离都是无穷,所以这个序列不是严格有序的。
把这些大的问题搞清楚之后就可以写代码了,一些小细节可以看我代码里的注释。

#include<iostream>
//#include<set>
#include<list>
#include<string>
#include<vector>
using namespace std;
int n,m;
const int MAX_N=26;
const int MAX_DIS=10000;
//*******这些都是维基百科关于拓扑排序(DFS版)里的变量含义
int temporary[MAX_N];
int permanent[MAX_N];
int marked[MAX_N];
//*******************************
int path[MAX_N][MAX_N];
//int dfs_visited[MAX_N];
list<int> L;//拓扑排序生产的顺序链
bool isDAG;//DAG=directed acyclic graph,无回路有向图
//每一个测试用例都要初始化路径
void init_path()
{
     for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
               path[i][j]=0;
}
//每一次拓扑排序都要初始化temporary,permanent,marked
void init_tpm()
{
     isDAG=true;
     L.clear();
     for(int i=0;i<n;i++)
     {
          temporary[i]=0;
          permanent[i]=0;
          marked[i]=0;
     }
}
//递归访问。具体看维基百科
void visit(int i)
{
     if(temporary[i]==1)
     {
          isDAG=false;
          return;
     }
     else
     {
          if(marked[i]==0)
          {
               marked[i]=1;
               temporary[i]=1;
               for(int j=0;j<n;j++)
               {
                    if(path[i][j]==1)
                    {
                         visit(j);
                    }
               }
               permanent[i]=1;
               temporary[i]=0;
               L.push_front(i);
          }
     }
}
/*
void init_dfs()
{
     for(int i=0;i<n;i++)
          dfs_visited[i]=0;
}*/
/*
//DFS有缺陷
void DFS(int v)
{
     if(dfs_visited[v]==0)
     {
          dfs_visited[v]=1;
          for(int i=0;i<n;i++)
          {
               if(dfs_visited[i]==0&&path[v][i]==1)
               {
                    DFS(i);
               }
          }
     }
}*/
//使用Floyd算法来判断生产的拓扑排序是否是严格有序的
bool Floyd()
{
     int copy_path[MAX_N][MAX_N];
     for(int i=0;i<n;i++)//首先复制一份路径图
          for(int j=0;j<n;j++)
          {
               copy_path[i][j]=path[i][j];
               if(i!=j&&copy_path[i][j]==0)//如果原来两点距离为0,说明他们是不直接连通的
                    copy_path[i][j]=MAX_DIS;//置为无穷
          }
     //floyd算法
     for(int k=0;k<n;k++)
          for(int i=0;i<n;i++)
               for(int j=0;j<n;j++) if(copy_path[i][j]>copy_path[i][k]+copy_path[k][j])
                         copy_path[i][j]=copy_path[i][k]+copy_path[k][j];
     vector<int> seq;//把原来用链表的拓扑序列转换成数组,方便后面的操作
     list<int>::iterator it=L.begin();
     while(it!=L.end())
     {
          seq.push_back(*it);
          it++;
     }
     //如果这个拓扑链是严格有序的话,则前面的元素到后面的元素一定是可达的。
     for(int i=0;i<n-1;i++)
     {
          for(int j=i+1;j<n;j++) { if(copy_path[seq[i]][seq[j]]>=MAX_DIS)//如果不可达,则不是严格有序的。
                    return false;
          }
     }
     return true;
}
//拓扑排序DFS版本。返回0:有回路;1:虽然是拓扑排序,但非连通(不是严格有序);2:是拓扑排序且连通(严格有序)(即任意两个元素都可以比较大小)
int topological_sorting()
{
     for(int i=0;i<n;i++)
     {
          if(marked[i]==0)
          {
               visit(i);
          }
     }
     if(!isDAG)
          return 0;
     else
     {
          /*init_dfs();
          DFS(*L.begin());
          for(int i=0;i<n;i++) { if(dfs_visited[i]==0) { return 1; } }*/ if(Floyd()) return 2; else return 1; } } int main() { //freopen("input.txt","r",stdin); string tmp; while(cin>>n>>m&&n&&m)
     {
          init_path();
          vector<string> relations(m);
          int i;
          for(i=0;i<m;i++)//一次性把所有输入都存起来,免得后续麻烦 { cin>>relations[i];
          }
          int rs=-1;
          for(i=0;i<m;i++)//每增加一个关系,都要重新拓扑排序一次
          {
               init_tpm();//每次都要初始化
               tmp=relations[i];
               path[tmp[0]-'A'][tmp[2]-'A']=1;
               rs=topological_sorting();
               if(rs==0)
               {
                    cout<<"Inconsistency found after "<<i+1<<" relations."<<endl;
                    break;//如果是回路的话,后续的输入可以跳过
               }
               else if(rs==2)//成功
               {
                    cout<<"Sorted sequence determined after "<<i+1<<" relations: ";
                    list<int>::iterator it=L.begin();
                    while(it!=L.end())
                    {
                         char c='A'+*it;
                         cout<<c;
                         it++;
                    }
                    cout<<"."<<endl;
                    break;//后续输入跳过
               }
          }
          if(i==m&&rs==1)//如果处理完所有输入都没有形成严格有序的拓扑序列
               cout<<"Sorted sequence cannot be determined."<<endl;
     }
     return 0;
}

我原本以为又是DFS,又是Floyd,算法时空效率会很低,但是提交后AC,用时125MS,内存244K,也不是很差。
代码中的拓扑排序算法使用的是基于DFS的版本,大家也可以改成Kahn算法。
如果觉得自己的代码是对的,但是提交WA的,可以使用这两个测试数据:数据1数据2

POJ 2263-Heavy Cargo

POJ 2263-Heavy Cargo
Heavy Cargo
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 3549 Accepted: 1894
Description
Big Johnsson Trucks Inc. is a company specialized in manufacturing big trucks. Their latest model, the Godzilla V12, is so big that the amount of cargo you can transport with it is never limited by the truck itself. It is only limited by the weight restrictions that apply for the roads along the path you want to drive.
Given start and destination city, your job is to determine the maximum load of the Godzilla V12 so that there still exists a path between the two specified cities.
Input
The input will contain one or more test cases. The first line of each test case will contain two integers: the number of cities n (2<=n<=200) and the number of road segments r (1<=r<=19900) making up the street network.
Then r lines will follow, each one describing one road segment by naming the two cities connected by the segment and giving the weight limit for trucks that use this segment. Names are not longer than 30 characters and do not contain white-space characters. Weight limits are integers in the range 0 - 10000. Roads can always be travelled in both directions.
The last line of the test case contains two city names: start and destination.
Input will be terminated by two values of 0 for n and r.
Output
For each test case, print three lines:
a line saying "Scenario #x" where x is the number of the test case
a line saying "y tons" where y is the maximum possible load
a blank line
Sample Input
4 3
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Muenchen
5 5
Karlsruhe Stuttgart 100
Stuttgart Ulm 80
Ulm Muenchen 120
Karlsruhe Hamburg 220
Hamburg Muenchen 170
Muenchen Karlsruhe
0 0
Sample Output
Scenario #1
80 tons
Scenario #2
170 tons
Source
Ulm Local 1998


题意:给定一个公路核载图,图上标明了每一段公路载重限额,问从A地到B地最多能装载多少吨货物。这一题和POJ Problem 2240: Arbitrage有点相似,也是使用Floyd算法,稍作修改即可。

如上图所示,假设要从A到B,在用Floyd算法时,判断要不要借助C点,如果不借助,则load_ton[A][B]=80;如果借助C点,则路径变为A->C->B,A->C最多能载100吨,C->B最多能载90吨,所以总的来说,A->C->B最多能载min{100,90}=90吨;而90>80,所以借助C点后的载重大于不借助C点的载重,所以修改load_ton[A][B]=90。
知道这一点,我们可以很快的写出代码:

#include<iostream>
#include<map>
#include<string>
using namespace std;
const int MAX_N=202;
int load_ton[MAX_N][MAX_N];
//初始化数据
void init_load(int n)
{
     for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
               load_ton[i][j]=0;
}
//改造Floyd算法
void Floyd(int n)
{
     for(int k=0;k<n;k++)
     {
          for(int i=0;i<n;i++)
          {
               for(int j=0;j<n;j++)
               {
                    int min_ton=load_ton[i][k]<load_ton[k][j]?load_ton[i][k]:load_ton[k][j];//这条路上的最小值即为能通过的最大值
                    if(load_ton[i][j]<min_ton)
                    {
                         load_ton[i][j]=min_ton;//对称矩阵
                         load_ton[j][i]=min_ton;//对称矩阵
                    }
               }
          }
     }
}
int main()
{
     //freopen("input.txt","r",stdin);
     int n,r;
     int case_num=1;
     while(cin>>n>>r&&n&&r)
     {
          init_load(n);
          map<string,int> city_index;//保存城市和下标的对应关系
          string city1,city2;
          int w;
          int i=0;
          while(r--)
          {
               cin>>city1>>city2>>w;
               if(city_index.find(city1)==city_index.end())
                    city_index[city1]=i++;
               if(city_index.find(city2)==city_index.end())
                    city_index[city2]=i++;
               //load_ton[i-2][i-1]=w;//错,因为有可能cityi在之前已经加入了,这个时候i-1,i-2就不是cityi的下标了
               //load_ton[i-1][i-2]=w;
               load_ton[city_index[city1]][city_index[city2]]=w;//还是要从map里找对应下标
               load_ton[city_index[city2]][city_index[city1]]=w;//因为路是两边通的,所以a[i][j]和a[j][i]相等
          }
          cin>>city1>>city2;
          Floyd(n);
          cout<<"Scenario #"<<case_num++<<endl;//
          cout<<load_ton[city_index[city1]][city_index[city2]]<<" tons"<<endl<<endl;
     }
     return 0;
}

本代码提交AC,用时79MS,内存316K。
在写代码的时候有几个小细节需要注意。在输入数据的时候,用MAP来保存城市和下标的关系,方便后面Floyd算法的操作;因为道路是双向通行的,所以保存数据时要保存成对称矩阵。

POJ 2240-Arbitrage

POJ 2240-Arbitrage
Arbitrage
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 16195 Accepted: 6814
Description
Arbitrage is the use of discrepancies in currency exchange rates to transform one unit of a currency into more than one unit of the same currency. For example, suppose that 1 US Dollar buys 0.5 British pound, 1 British pound buys 10.0 French francs, and 1 French franc buys 0.21 US dollar. Then, by converting currencies, a clever trader can start with 1 US dollar and buy 0.5 * 10.0 * 0.21 = 1.05 US dollars, making a profit of 5 percent.
Your job is to write a program that takes a list of currency exchange rates as input and then determines whether arbitrage is possible or not.
Input
The input will contain one or more test cases. Om the first line of each test case there is an integer n (1<=n<=30), representing the number of different currencies. The next n lines each contain the name of one currency. Within a name no spaces will appear. The next line contains one integer m, representing the length of the table to follow. The last m lines each contain the name ci of a source currency, a real number rij which represents the exchange rate from ci to cj and a name cj of the destination currency. Exchanges which do not appear in the table are impossible.
Test cases are separated from each other by a blank line. Input is terminated by a value of zero (0) for n.
Output
For each test case, print one line telling whether arbitrage is possible or not in the format "Case case: Yes" respectively "Case case: No".
Sample Input
3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar
Sample Output
Case 1: Yes
Case 2: No
Source
Ulm Local 1996


本题的题意是“通过汇率的转换,有没有可能获利”。题目给出了不同货币之间的汇率,这其实就给出了一张图,我们需要从图中找出一条回路,回路上所有汇率的乘积大于1,则可以获利;如果所有回路的乘积都小于等于1,则不可能获利。
仔细想想,这有点像求所有点对的最短距离!只是这题的最短距离实际上是最大乘积值,以往我们求最短距离的时候,图中点A到自身的距离是0;但是本题A到A自身的距离(汇率)应该是1。利用Floyd算法求解之后,如果存在path[A][A]>1则可获利,否则不可获利。
所以总的来说,这题还是不难的。需要注意的是,输入的时候给出的是字符串,我们需要把它转换成整型对应关系,可以利用map<string,int>来保存string和int的对应关系,方便后面的Floyd算法实施。
完整代码如下:

#include<iostream>
#include<string>
#include<map>
using namespace std;
const int MAX_N=31;
double path[MAX_N][MAX_N];
//初始化,A到A的路径(汇率)为1;其他为0
void init_path(int n)
{
     for(int i=0;i<n;i++)
     {
          for(int j=0;j<n;j++)
          {
               if(i==j)
                    path[i][j]=1.0;
               else
                    path[i][j]=0.0;
          }
     }
}
//Floyd算法求所有点对的“最短距离”(最大乘积值)
void Floyd(int n)
{
     for(int k=0;k<n;k++)
     {
          for(int i=0;i<n;i++)
          {
               for(int j=0;j<n;j++)
               {
                    path[i][j]=(path[i][j]>path[i][k]*path[k][j])?path[i][j]:(path[i][k]*path[k][j]);
               }
          }
     }
}
int main()
{
     //freopen("input.txt","r",stdin);
     int n,m;
     int case_num=1;
     while(cin>>n&&n)
     {
          init_path(n);
          map<string,int> currency_index;//保存string和int的对应关系
          int i=0;
          string tmp;
          for(int j=0;j<n;j++)
          {
               cin>>tmp;
               currency_index[tmp]=i++;
          }
          cin>>m;
          string ci,cj;
          double rij;
          while(m--)
          {
               cin>>ci>>rij>>cj;
               path[currency_index[ci]][currency_index[cj]]=rij;
          }
          Floyd(n);
          bool yes=false;
          for(i=0;i<n;i++)
          {
               if(path[i][i]>1)
               {
                    yes=true;
                    break;
               }
          }
          if(yes)
               cout<<"Case "<<case_num<<": Yes"<<endl;
          else
               cout<<"Case "<<case_num<<": No"<<endl;
          case_num++;
     }
     return 0;
}

本代码提交AC,用时94MS,内存236K。

POJ 3253-Fence Repair

POJ 3253-Fence Repair
Fence Repair
Time Limit: 2000MS Memory Limit: 65536K
Total Submissions: 27581 Accepted: 8976
Description
Farmer John wants to repair a small length of the fence around the pasture. He measures the fence and finds that he needs N (1 ≤ N ≤ 20,000) planks of wood, each having some integer length Li (1 ≤ Li ≤ 50,000) units. He then purchases a single long board just long enough to saw into the N planks (i.e., whose length is the sum of the lengths Li). FJ is ignoring the "kerf", the extra length lost to sawdust when a sawcut is made; you should ignore it, too.
FJ sadly realizes that he doesn't own a saw with which to cut the wood, so he mosies over to Farmer Don's Farm with this long board and politely asks if he may borrow a saw.
Farmer Don, a closet capitalist, doesn't lend FJ a saw but instead offers to charge Farmer John for each of the N-1 cuts in the plank. The charge to cut a piece of wood is exactly equal to its length. Cutting a plank of length 21 costs 21 cents.
Farmer Don then lets Farmer John decide the order and locations to cut the plank. Help Farmer John determine the minimum amount of money he can spend to create the N planks. FJ knows that he can cut the board in various different orders which will result in different charges since the resulting intermediate planks are of different lengths.
Input
Line 1: One integer N, the number of planks
Lines 2..N+1: Each line contains a single integer describing the length of a needed plank
Output
Line 1: One integer: the minimum amount of money he must spend to make N-1 cuts
Sample Input
3
8
5
8
Sample Output
34
Hint
He wants to cut a board of length 21 into pieces of lengths 8, 5, and 8.
The original board measures 8+5+8=21. The first cut will cost 21, and should be used to cut the board into pieces measuring 13 and 8. The second cut will cost 13, and should be used to cut the 13 into 8 and 5. This would cost 21+13=34. If the 21 was cut into 16 and 5 instead, the second cut would cost 16 for a total of 37 (which is more than 34).
Source
USACO 2006 November Gold


题目大意是要把一根木棍锯成若干根小棍子,问每锯一次剩余木棍的长度之和最少是多少。
这其实就是哈弗曼树的问题。我们可以想象所有小棍子都锯好了,我们要把他们拼接成原来的长木棍,则每拼接一次的长度就是上一次锯的时候剩余的木棍长度,要使剩余长度之和最小,我们可以每次取最短的两根木棍拼接,这样得到的剩余木棍长度之和自然是最小的。而这就是哈弗曼树。
每次取剩余元素中最小的两个求和,把这两个元素删除,然后插入这个和,如此循环直到最后只剩下一个元素。每次都要取最小的两个元素,本能的想到排序,但是每次都排序效率肯定不高,所以我偷懒的使用了STL中的multiset来解决,multiset的内部实现是红黑树,其插入、查找、删除的效率都是lgn,插入的元素自动排好序了,很不错。所以我们只要不停的插入元素,取头两个元素,求和,删除这两个元素,再插入新元素...直到只剩一个元素。
使用multiset的完整代码如下:

#include<iostream>
#include<set>
using namespace std;
int main()
{
     int n,tmp;
     multiset<int> planks;
     cin>>n;
     while(n--)
     {
          cin>>tmp;
          planks.insert(tmp);
     }
     //int rs=0;//超出最大值
     long long rs=0;
     int curr_sum;//当前两个元素之和
     multiset<int>::iterator min_it;
     while(planks.size()>1)
     {
          curr_sum=0;
          min_it=planks.begin();//最小元素
          rs+=*min_it;
          curr_sum+=*min_it;
          planks.erase(min_it);
          min_it=planks.begin();//第二小元素
          rs+=*min_it;
          curr_sum+=*min_it;
          planks.erase(min_it);
          planks.insert(curr_sum);//插入新元素
     }
     cout<<rs;
     return 0;
}

本代码提交AC,用时188MS,内存1064K。
需要注意的是,因为1 ≤ N ≤ 20,000且1 ≤ Li ≤ 50,000,最终结果可能超过int的取值范围,需要改为long long才能AC,原因请看这里
本来到这里本题应该结束了,但是总是用STL里的东西还是有点虚,打算自己实现求2个最小值然后求和插入的过程。基本思路就是将原始数组排序,然后把他们转换为链表,便于后面的插入删除操作;然后取链表的头两个指针求和,然后删除这连个节点,再用插入排序的方式把和插入到链表中。
完整代码如下:

#include<iostream>
#include<vector>
#include<list>
#include<algorithm>
using namespace std;
int main()
{
     int n,tmp;
     vector<int> planks;
     cin>>n;
     while(n--)
     {
          cin>>tmp;
          planks.push_back(tmp);
     }
     sort(planks.begin(),planks.end());//首先排序
     list<int> sorted_planks;
     vector<int>::iterator it=planks.begin();
     while(it!=planks.end())//把数组转换为链表,便于后面的插入删除操作
     {
          sorted_planks.push_back(*it);
          it++;
     }
     long long rs=0;
     int curr_sum;
     list<int>::iterator min_it;
     while(sorted_planks.size()>1)
     {
          curr_sum=0;
          min_it=sorted_planks.begin();//最小元素
          rs+=*min_it;
          curr_sum+=*min_it;
          sorted_planks.erase(min_it);
          min_it=sorted_planks.begin();//第二小元素
          rs+=*min_it;
          curr_sum+=*min_it;
          sorted_planks.erase(min_it);
          min_it=sorted_planks.begin();
          while(min_it!=sorted_planks.end()&&curr_sum>*min_it)//相当于插入排序
          {
               min_it++;
          }
          sorted_planks.insert(min_it,curr_sum);
     }
     cout<<rs;
     return 0;
}

本代码提交AC,用时1000MS,内存1000K。看来链表的效率还是没有红黑树高啊。
需要注意的是,在对链表插入排序的时候,使用的是如下的代码:

min_it=sorted_planks.begin();
while(min_it!=sorted_planks.end()&&curr_sum>*min_it)//相当于插入排序
{
        min_it++;
}
sorted_planks.insert(min_it,curr_sum);

list.insert(it,v)是将v插入到it的前面。需要特别注意的是while循环的条件,因为如果要将6插入到1,2,3,4里面,则如果任由min_it++的话,会超出链表的范围,所以还需要加上min_it!=sorted_planks.end()这个条件,但是把while写成这样:

while(curr_sum>*min_it&&min_it!=sorted_planks.end())//相当于插入排序
{
        min_it++;
}

也不行,因为如果min_it==sorted_planks.end(),则先执行的是curr_sum>*min_it出错,所以我们需要先判断是否超出了链表的范围,再判断有没有找到正确的位置,利用第一种的while循环条件就可以借助短路原则,即如果min_it!=sorted_planks.end()不满足,则不会执行后面的curr_sum>*min_it,而是while直接跳出。

POJ 1068-Parencodings

POJ 1068-Parencodings
Parencodings
Time Limit: 1000MS Memory Limit: 10000K
Total Submissions: 20210 Accepted: 12196
Description
Let S = s1 s2...s2n be a well-formed string of parentheses. S can be encoded in two different ways:
q By an integer sequence P = p1 p2...pn where pi is the number of left parentheses before the ith right parenthesis in S (P-sequence).
q By an integer sequence W = w1 w2...wn where for each right parenthesis, say a in S, we associate an integer which is the number of right parentheses counting from the matched left parenthesis of a up to a. (W-sequence).
Following is an example of the above encodings:
S (((()()())))
P-sequence 4 5 6666
W-sequence 1 1 1456
Write a program to convert P-sequence of a well-formed string to the W-sequence of the same string.
Input
The first line of the input contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case is an integer n (1 <= n <= 20), and the second line is the P-sequence of a well-formed string. It contains n positive integers, separated with blanks, representing the P-sequence.
Output
The output file consists of exactly t lines corresponding to test cases. For each test case, the output line should contain n integers describing the W-sequence of the string corresponding to its given P-sequence.
Sample Input
2
6
4 5 6 6 6 6
9
4 6 6 6 6 8 9 9 9
Sample Output
1 1 1 4 5 6
1 1 2 4 5 1 1 3 9
Source
Tehran 2001


简单题。给一个括号字符串的P序列,要求算出其W序列。
直接计算即可,首先根据P序列还原出该括号字符串,因为P序列的每一个数字是对应右括号的,所以这个数字就表示这个右括号左边有多少个左括号,通过一个while循环就可以还原出原始括号字符串。
得到原始括号字符串之后,就可以计算W序列了。W序列的每一个数字也是对应右括号的,它表示从“和该右括号匹配的左括号”的位置到“该右括号”的位置一共有多少个右括号。这就要求我们知道每一个右括号匹配的左括号的位置,用一个堆栈可以简单求出。
求除了右括号及其匹配的左括号的位置后,就可以遍历括号字符串计算出期间共有多少个右括号了。
求解思路清晰之后,可以快速写出完整代码:

#include<iostream>
#include<string>
#include<vector>
#include<stack>
using namespace std;
typedef struct PAR//括号结构
{
     char c;//左括号或右括号
     int pos;//该字符的下标
};
//根据P-sequence还原出括号字符串
string get_parentheses(vector<int>& p)
{
     string rs="";
     vector<int>::iterator it=p.begin();
     int i=0;
     while(it!=p.end())
     {
          while(i!=(*it))
          {
               rs+='(';
               i++;
          }
          rs+=')';
          it++;
     }
     return rs;
}
//根据括号字符串paren得到W-sequence
void get_w(vector<int>& w,string paren)
{
     int len=paren.size();
     stack<PAR> s_p;
     PAR par;
     vector<int> right_pos,left_pos;//分别记录某个右括号对应左括号的位置
     for(int i=0;i<len;i++)
     {
          if(paren[i]=='(')//如果是左括号,入栈
          {
               par.c=paren[i];
               par.pos=i;
               s_p.push(par);
          }
          else//右括号,出栈,配对
          {
               par=s_p.top();
               s_p.pop();
               right_pos.push_back(i);
               left_pos.push_back(par.pos);
          }
     }
     vector<int>::iterator it_r=right_pos.begin();
     vector<int>::iterator it_l=left_pos.begin();
     while(it_r!=right_pos.end())//计算W-sequence
     {
          int num=0;
          for(int i=*it_l;i<=*it_r;i++)
          {
               if(paren[i]==')')
                    num++;
          }
          w.push_back(num);
          it_r++;
          it_l++;
     }
}
int main()
{
     int t,n;
     cin>>t;
     while(t--)
     {
          cin>>n;
          vector<int> p;//P-sequence
          int tmp;
          string parentheses;
          while(n--)
          {
               cin>>tmp;
               p.push_back(tmp);
          }
          parentheses=get_parentheses(p);
          vector<int> w;//W-sequence
          get_w(w,parentheses);
          vector<int>::iterator it=w.begin();
          while(it!=w.end())
          {
               cout<<*it<<" ";
               it++;
          }
          cout<<endl;
     }
     return 0;
}

本代码提交AC,用时0MS,内存764K。

hihoCoder 1066-无间道之并查集

hihoCoder 1066-无间道之并查集
#1066 : 无间道之并查集
时间限制:20000ms
单点时限:1000ms
内存限制:256MB
描述
这天天气晴朗、阳光明媚、鸟语花香,空气中弥漫着春天的气息……额,说远了,总之,小Hi和小Ho决定趁着这朗朗春光出去玩。
但是刚刚离开居住的宾馆不久,抄近道不小心走入了一条偏僻小道的小Hi和小Ho就发现自己的前方走来了几个彪形大汉,定睛一看还都是地地道道的黑人兄弟!小Hi和小Ho这下就慌了神,捡肥皂事小,这一身百把来斤别一不小心葬身他乡可就没处说去了。
就在两人正举足无措之时,为首的黑叔叔从怀里掏出了一件东西——两张花花绿绿的纸,分别递给了小Hi和小Ho。
小Hi和小Ho接过来,只见上面写道(译为中文):“本地最大的帮派——青龙帮,诚邀您的加入!”下面还详细的列出了加入青龙帮的种种好处。
于是两人略感心安,在同黑叔叔们交谈一番之后,已是均感相见恨晚。同时,在小Hi和小Ho表示自己不日便将回国之后,黑叔叔们也没有再提加入帮派之事,但是那为首的黑叔叔思索一会,开口道(译为中文):“我现在有一个难题,思索了很久也没法子解决,既然你们俩都是高材生,不如来帮我看看。”
小Hi和小Ho点了点头表示没问题,于是黑叔叔继续说道:“这个问题是这样的,我们帮派最近混进了许多警察的卧底,但是在我们的调查过程中只能够知道诸如‘某人和另一个人是同阵营的’这样的信息,虽然没有办法知道他们具体是哪个阵营的,但是这样的信息也是很重要的,因为我们经常会想要知道某两个人究竟是不是同一阵营的。”
小Hi和小Ho赞同的点了点头,毕竟无间道也都是他们看过的。
黑叔叔接着说道:“于是现在问题就来了,我希望你们能写出这样一个程序,我会有两种操作,一种是告诉它哪两个人是同一阵营的,而另一种是询问某两个人是不是同一阵营的……既然你们就要回国了,不如现在就去我们帮派的总部写好这个程序再走把。”
为了生命安全与……小Hi和小Ho都不得不解决这个问题!那么他们究竟从何下手呢?
提示:说起来其实就是不断的合并集合嘛~
输入
每个测试点(输入文件)有且仅有一组测试数据。
每组测试数据的第1行为一个整数N,表示黑叔叔总共进行的操作次数。
每组测试数据的第2~N+1行,每行分别描述黑叔叔的一次操作,其中第i+1行为一个整数op_i和两个由大小写字母组成的字符串Name1_i, Name2_i,其中op_i只可能为0或1,当op_i=0时,表示黑叔叔判定Name1_i和Name2_i是同一阵营的,当op_i=1时,表示黑叔叔希望知道Name1_i和Name2_i是否为同一阵营的。
对于100%的数据,满足N<=10^5, 且数据中所有涉及的人物中不存在两个名字相同的人(即姓名唯一的确定了一个人),对于所有的i,满足Name1_i和Name2_i是不同的两个人。
输出
对于每组测试数据,对于黑叔叔每次op_i=1的操作,输出一行,表示查询的结果:如果根据已知信息(即这次操作之前的所有op_i=0的操作),可以判定询问中的两个人是同一阵营的,则输出yes,否则输出no。
样例输入
10
0 Steven David
0 Lcch Dzx
1 Lcch Dzx
1 David Dzx
0 Lcch David
0 Frank Dzx
1 Steven Dzx
1 Frank David
0 Steven Dzx
0 Dzx Frank
样例输出
yes
no
yes
yes


这是一道考察并查集的好题目。并查集也叫做不相交集。它主要有两个操作:FIND和UNION。
假设有两个不相交集分别为A,B,用各自集合内的元素a和b分别代表A和B,也就是说A中所有元素(包括a自己)的祖先都是a,B中所有元素(包括b自己)的祖先都是b。FIND操作就是给定一个元素c,要找到它的祖先。常规思路就是递归的顺着族谱往上找,但是为了后续查找的高效,可以路径压缩一下,也就是把查找过程中的节点的祖先都赋为c的祖先,这样下次查找其他元素的祖先时就快得多。
UNION操作就是已知元素c和d,要把这两个元素所在的集合合并起来,自然就是先用FIND找到c和d的祖先,然后把其中一个祖先当做另一个祖先的祖先,这样就把两个集合合并起来了。
至于这道题,题目中的提示已经把并查集的FIND函数写出来了。

如果op_i=0,说明这两个人是同一个集合的,即他们有共同的祖先,则首先判断这两个人在不在map中,如果不在,则以自身为祖先加入到map中,然后执行UNION操作把他们合并为一个集合。
如果op_i=1,要判断两个人是否在一个集合中,想当然的FIND他们的祖先,如果祖先相同,说明他们是一个集合的。
理清了上述关系,马上写出代码:

#include<iostream>
#include<string>
#include<map>
using namespace std;
map<string,string> represent;
//并查集FIND操作
string find_represent(string name)
{
     if(name==represent[name])
          return name;
     else
     {
          represent[name]=find_represent(represent[name]);//把经过的节点全部链接到根节点
          return represent[name];
     }
}
int main()
{
      //freopen("input.txt","r",stdin);
     int n;
     int op;
     string name1,name2;
     cin>>n;
     while(n--)
     {
          cin>>op>>name1>>name2;
          if(op==0)
          {
               if(represent.find(name1)==represent.end())
                    represent[name1]=name1;
               if(represent.find(name2)==represent.end())
                    represent[name2]=name2;
               represent[find_represent(name1)]=find_represent(name2);//UNION操作
          }
          else
          {
               //**********也需要先判断是否在map里*********
               if(represent.find(name1)==represent.end())
                    represent[name1]=name1;
               if(represent.find(name2)==represent.end())
                    represent[name2]=name2;
               //******************************************
               if(find_represent(name1)==find_represent(name2))
                    cout<<"yes"<<endl;
               else
                    cout<<"no"<<endl;
          }
     }
     return 0;
}

本代码提交AC,用时243MS,内存1MB。
需要注意的是,由于本题使用MAP实现,在执行FIND操作时有这么一句:

if(name==represent[name])

对于STL的map,如果本来map中不存在a这个元素,执行了if(map[a]=="sth")之后,也会自动把a加入map,最后就是map[a]="",为空。虽然就某一次来说,这样判断的结果和下面修正的结果是一样的,但是如果下一次op_i=0需要加入a时发现map中已经有a了,就直接执行UNION操作了,但是这个时候a的祖先却是空"",而本来a的祖先应该是它自己a的。所以这就会对后面的结果产生影响。所以当我们op_i=1时,如果某个人不在map中,我们也要把它加入map并使其祖先为自身。
关于这道题,这篇题解写得还可以,它把并查集的UNION和FIND分开来写,条理清晰,值得参考,不过它没有路径压缩。
之前一直对并查集心存恐惧,刷过这道题之后,发现并查集也就这么回事,代码简洁,也不难理解。继续坚持!

POJ 2965-The Pilots Brothers' refrigerator

POJ 2965-The Pilots Brothers' refrigerator
The Pilots Brothers' refrigerator
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 19188 Accepted: 7358 Special Judge
Description
The game “The Pilots Brothers: following the stripy elephant” has a quest where a player needs to open a refrigerator.
There are 16 handles on the refrigerator door. Every handle can be in one of two states: open or closed. The refrigerator is open only when all handles are open. The handles are represented as a matrix 4х4. You can change the state of a handle in any location [i, j] (1 ≤ i, j ≤ 4). However, this also changes states of all handles in row i and all handles in column j.
The task is to determine the minimum number of handle switching necessary to open the refrigerator.
Input
The input contains four lines. Each of the four lines contains four characters describing the initial state of appropriate handles. A symbol “+” means that the handle is in closed state, whereas the symbol “−” means “open”. At least one of the handles is initially closed.
Output
The first line of the input contains N – the minimum number of switching. The rest N lines describe switching sequence. Each of the lines contains a row number and a column number of the matrix separated by one or more spaces. If there are several solutions, you may give any one of them.
Sample Input
-+--
----
----
-+--
Sample Output
6
1 1
1 3
1 4
4 1
4 3
4 4
Source
Northeastern Europe 2004, Western Subregion


这一题和之前做的POJ Problem 1753: Flip Game大同小异,只是这题要求记录搜索路径,并且翻转的时候是同行同列的所有格子都翻转,对之前那题的代码稍作修改即可。
这一题要求翻转的时候是翻转和(i,j)点同行同列的所有点,我们还是通过异或来完成。比如我们要对

-+--
----
----
-+--

的(0,0)(坐标从0开始)及其行列翻转,应该怎么办呢?
因为1^1=0,1^0=1,所以如果我们要改变某一位,只需要将该位异或1即可。又因为我们输入的时候是从左到右,从上到下的顺序,所以当我们要翻转第0行的时候,只需要异或0xf<<12,0xf<<12相当于把4个二进制1移到最左边(因为第0行在最左边),如果是翻转第i行,则异或0xf<<(4*(3-i));当我们要翻转某一列时,因为同一列的二进制位相差3个位置,所以异或值的形式为二进制0001000100010001,又因为(i,j)这个位置在行翻转的时候已经翻转过了,所以在列翻转时不能再翻转了,否则回到原状态了,所以根据行号的不同,我们可以得到不同的列异或值,分别是curr_xor=0x111,0x1011,0x1101,0x1110,列翻转的公式是next_p.val^=curr_xor<<(3-j);。这个问题用笔在纸上演算一下就会很明白了。
还有一个问题是怎样来记录搜索的路径,我的办法是开辟两个数组:

typedef struct P//翻转时的格子坐标
{
     int x,y;
};
P trace[MAX_STATUS];//trace[i]到达i状态值时翻转的某个格子坐标
int pre[MAX_STATUS];//pre[i]记录i状态的前一个状态值

pre[i]数组用来记录到达i状态时的前一个状态,而trace[i]则用来记录到达该状态时翻转的格子坐标。这样通过成功状态回溯到开始状态就可以找到所有路径了,具体实现请看下面的代码。
完整代码如下:

#include<iostream>
#include<queue>
#include<vector>
using namespace std;
const int MAX_STATUS=65536;//2^16=65536种,所以[0,65535]
const int ALL_1=65535;//全1
int visited[MAX_STATUS]={0};//访问标记
int XOR[4]={0x111,0x1011,0x1101,0x1110};//列异或值
typedef struct POS//position翻转位置
{
     int val;//当前翻转状态的值
     int step;//到当前状态共翻转了多少次
};
typedef struct P//翻转时的格子坐标
{
     int x,y;
};
P trace[MAX_STATUS];//trace[i]到达i状态值时翻转的某个格子坐标
int pre[MAX_STATUS];//pre[i]记录i状态的前一个状态值
//通过反向索引打印结果
void print_result(POS pos,int init_id)
{
     cout<<pos.step<<endl;
     vector<P> points;
     points.push_back(trace[pos.val]);
     int pre_val=pre[pos.val];
     while(pre_val!=init_id)//当没有追溯到初始状态时,一直循环
     {
          points.push_back(trace[pre_val]);
          pre_val=pre[pre_val];//追溯
     }
     int p_num=points.size();//顺着打印出来
     for(int i=p_num-1;i>=0;i--)
          cout<<points[i].x<<" "<<points[i].y<<endl;
}
//广度优先搜索
void BFS(int init_id)
{
     POS p,next_p;
     p.val=init_id;
     p.step=0;
     visited[p.val]=1;
     pre[p.val]=-1;//没有前一个状态
     queue<POS> Q_P;
     Q_P.push(p);
     while(!Q_P.empty())
     {
          p=Q_P.front();
          Q_P.pop();
          if(p.val==ALL_1)
          {
               print_result(p,init_id);
               return;
          }
          for(int i=0;i<4;i++)
          {
               int curr_xor=XOR[i];//i不同时,翻转异或的值也不同
               for(int j=0;j<4;j++)
               {
                    next_p.val=p.val;
                    next_p.val^=0xf<<(4*(3-i));//横向翻转
                    next_p.val^=curr_xor<<(3-j);//纵向翻转
                    if(visited[next_p.val]==0)
                    {
                         visited[next_p.val]=1;
                         next_p.step=p.step+1;
                         pre[next_p.val]=p.val;//记录前一个状态值
                         trace[next_p.val].x=i+1;//注意输出的坐标是从1开始到4
                         trace[next_p.val].y=j+1;//所以这里加1
                         Q_P.push(next_p);
                    }
               }
          }
     }
}
int main()
{
     //freopen("input.txt","r",stdin);
     char c;
     int id=0;
     for(int i=0;i<4;i++)
     {
          for(int j=0;j<4;j++)
          {
               cin>>c;
               id<<=1;//id=id<<1;
               if(c=='-')//-:1;+:0
                    id+=1;
          }
     }
     BFS(id);
     return 0;
}

这个版本的代码如果以C++提交,则TLE,如果用G++提交则AC,用时625MS,内存1788K,不知道是什么原因。