# 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 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，又包含并查集，对初学者来说有一定的难度，而且这个题给出的数据是字符串形式的，数据量又很大，有很多细节需要注意。 我先把完整的代码贴出来，然后讲一下主要过程。 [cpp] #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; } [/cpp] 摆在我们面前的第一个问题就是数据的输入问题，题目给的每个人名都是字符串，当然我们可以直接用字符串构建一个树结构，然后进行查找、比较、赋值等操作，但是这样的时空效率都比较低，所以我们可以先用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)的时间，大大提高了时间效率。 因为题目中说明了

# 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

# 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

# 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

# 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

# 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

# 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

# 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

# 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