Category Archives: POJ

POJ 2240-Arbitrage

1 Reply

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算法实施。 完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时94MS，内存236K。]]>

POJ 3253-Fence Repair

Leave a reply

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的完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时188MS，内存1064K。 需要注意的是，因为1 ≤ N ≤ 20,000且1 ≤ Li ≤ 50,000，最终结果可能超过int的取值范围，需要改为long long才能AC，原因请看这里。 本来到这里本题应该结束了，但是总是用STL里的东西还是有点虚，打算自己实现求2个最小值然后求和插入的过程。基本思路就是将原始数组排序，然后把他们转换为链表，便于后面的插入删除操作；然后取链表的头两个指针求和，然后删除这连个节点，再用插入排序的方式把和插入到链表中。 完整代码如下： [cpp] #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; } [/cpp] 本代码提交AC，用时1000MS，内存1000K。看来链表的效率还是没有红黑树高啊。 需要注意的是，在对链表插入排序的时候，使用的是如下的代码： [cpp] min_it=sorted_planks.begin(); while(min_it!=sorted_planks.end()&&curr_sum>*min_it)//相当于插入排序 { min_it++; } sorted_planks.insert(min_it,curr_sum); [/cpp] list.insert(it,v)是将v插入到it的前面。需要特别注意的是while循环的条件，因为如果要将6插入到1,2,3,4里面，则如果任由min_it++的话，会超出链表的范围，所以还需要加上min_it!=sorted_planks.end()这个条件，但是把while写成这样： [cpp] while(curr_sum>*min_it&&min_it!=sorted_planks.end())//相当于插入排序 { min_it++; } [/cpp] 也不行，因为如果min_it==sorted_planks.end()，则先执行的是curr_sum>*min_it出错，所以我们需要先判断是否超出了链表的范围，再判断有没有找到正确的位置，利用第一种的while循环条件就可以借助短路原则，即如果min_it!=sorted_planks.end()不满足，则不会执行后面的curr_sum>*min_it，而是while直接跳出。]]>

POJ 1068-Parencodings

Leave a reply

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序列的每一个数字也是对应右括号的，它表示从“和该右括号匹配的左括号”的位置到“该右括号”的位置一共有多少个右括号。这就要求我们知道每一个右括号匹配的左括号的位置，用一个堆栈可以简单求出。 求除了右括号及其匹配的左括号的位置后，就可以遍历括号字符串计算出期间共有多少个右括号了。 求解思路清晰之后，可以快速写出完整代码： [cpp] #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; } [/cpp] 本代码提交AC，用时0MS，内存764K。]]>

POJ 2965-The Pilots Brothers' refrigerator

Leave a reply

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)点同行同列的所有点，我们还是通过异或来完成。比如我们要对 [cpp] -+– —- —- -+– [/cpp] 的(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);。这个问题用笔在纸上演算一下就会很明白了。 还有一个问题是怎样来记录搜索的路径，我的办法是开辟两个数组： [cpp] typedef struct P//翻转时的格子坐标 { int x,y; }; P trace[MAX_STATUS];//trace[i]到达i状态值时翻转的某个格子坐标 int pre[MAX_STATUS];//pre[i]记录i状态的前一个状态值 [/cpp] pre[i]数组用来记录到达i状态时的前一个状态，而trace[i]则用来记录到达该状态时翻转的格子坐标。这样通过成功状态回溯到开始状态就可以找到所有路径了，具体实现请看下面的代码。 完整代码如下： [cpp] #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; } [/cpp] 这个版本的代码如果以C++提交，则TLE，如果用G++提交则AC，用时625MS，内存1788K，不知道是什么原因。]]>

POJ 1753-Flip Game

1 Reply

POJ 1753-Flip Game Flip Game Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 31655 Accepted: 13776 Description Flip game is played on a rectangular 4×4 field with two-sided pieces placed on each of its 16 squares. One side of each piece is white and the other one is black and each piece is lying either it’s black or white side up. Each round you flip 3 to 5 pieces, thus changing the color of their upper side from black to white and vice versa. The pieces to be flipped are chosen every round according to the following rules: Choose any one of the 16 pieces. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any). Consider the following position as an example: bwbw wwww bbwb bwwb Here “b” denotes pieces lying their black side up and “w” denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become: bwbw bwww wwwb wwwb The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal. Input The input consists of 4 lines with 4 characters “w” or “b” each that denote game field position. Output Write to the output file a single integer number – the minimum number of rounds needed to achieve the goal of the game from the given position. If the goal is initially achieved, then write 0. If it’s impossible to achieve the goal, then write the word “Impossible” (without quotes). Sample Input bwwb bbwb bwwb bwww Sample Output 4 Source Northeastern Europe 2000

题意：翻动格子使得整个棋盘为全黑或者全白，求最少的翻动次数，翻动某一个格子，也会同时翻动其周围的四个格子（如果有的话）。因为某一个格子翻动2次的结果和不翻是一样的；翻动3次的结果和翻动1次的结果是一样的；多个也是一样，所以一个格子最多翻动1次，这样总的翻动次数最多为16次。每个格子有翻和不翻两种情况，所以总共有$$2^{16}$$种情况，可以暴力枚举。 但是一直没有想好用哪种方法，深度搜索还是广度搜索。后来想了想，这是求最优解（最少翻动次数）的题，所以用广度优先搜索的效率应该会高一些，但是在BFS的过程中曾有一个问题困扰了，后面再说。又因为棋盘正好是4*4=16的，可以用int的位运算来表示，b表示1，w表示0，这样棋盘的一个状态就可以用一个int数来表示，翻动格子也可以用位运算来表示，总共的状态数是$$2^{16}$$，取值范围是[0,65535]，当棋盘状态是0或者65535时，表示全白或者全黑，这时找到结果。 了解了这些，就可以写出BFS+位运算的代码了，这题我是参考了网上的题解： [cpp] #include<iostream> #include<queue> using namespace std; const int MAX_STATUS=65536;//2^16=65536种，所以[0,65535] const int ALL_0=0;//全0 const int ALL_1=65535;//全1 int ans; int visited[MAX_STATUS]={0};//访问标记 typedef struct POS//position翻转位置 { int val;//当前翻转状态的值 int step;//到当前状态共翻转了多少次 }; //广搜 void BFS(int init_id) { queue<POS> Q_P; POS s,next_p; //初始位置 s.val=init_id; s.step=0; visited[s.val]=1; Q_P.push(s); while(!Q_P.empty()) { s=Q_P.front(); Q_P.pop(); if(s.val==ALL_0||s.val==ALL_1)//找到结果 { ans=s.step; return; } //尝试翻16个位置 for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { next_p.val=s.val; //测试i，翻转[i,j]上下位置的格子 if(i==0) next_p.val^=1<<(11-4*i-j); else if(i==3) next_p.val^=1<<(19-4*i-j); else { next_p.val^=1<<(11-4*i-j); next_p.val^=1<<(19-4*i-j); } //测试j，翻转[i,j]左右位置的格子 if(j==0) next_p.val^=3<<(14-4*i-j); else if(j==3) next_p.val^=3<<(15-4*i-j); else next_p.val^=7<<(14-4*i-j); if(visited[next_p.val]==0)//如果没有访问 { visited[next_p.val]=1;//访问 next_p.step=s.step+1;//翻转次数加1 Q_P.push(next_p);//并加入队列 } } } } ans=-1;//到这里还没有return,说明impossible } int main() { //freopen("input.txt","r",stdin); char c; int id=0; //输入转换 /*bwbw wwww bbwb bwwb 排列成bwbw wwww bbwb bwwb，然后把b换成1，w换成0*/ for(int i=0;i<4;i++) { for(int j=0;j<4;j++) { cin>>c; id<<=1; if(c==’b’)//b=1;w=0 id+=1; } } BFS(id); if(ans==-1) cout<<"Impossible"; else cout<<ans; return 0; } [/cpp] 本代码提交AC，用时79MS，内存508K。 在每一次BFS的时候，我们都要尝试去翻所有16个格子，如果翻动之后达到了一个新的状态（也就是之前没有访问过），说明这个翻动是有效的，把它加入到队列中。在翻动的时候，怎样进行位运算大家可以把i=0,j=0代入到for循环里手算一遍，程序会根据i和j的不同，和不同的数进行异或运算。 之前我说有一个地方让我困惑，就是我之前：第一次BFS的时候肯定把所有格子都翻了一遍，也就是把(0,0)(0,1)…(3,3)翻动的结果都加入到队列中了，那么在第二次BFS的时候，把(0,0)出队，这个时候再来翻所有16个格子，这样不就相当于把所有格子又翻回到初始状态了吗？其实这种想法是不对的，说到底还是对BFS理解不够透彻。**我们在每次BFS的时候都是在队首元素的基础上翻转的，因为我们在while开头执行了s=Q_P.front();Q_P.pop();这么两句**，那么当我们把(0,0)翻转状态出队在去翻转的时候，是在(0,0)翻转状态的基础是再进行翻转的，而这个时候是只有(0,0)这一个格子翻了，其他15个格子都没有翻；同理当把(0,1)出队的时候，也是只有(0,1)翻了，其他15个都没有翻。所以这样BFS下去是能够搜索到所有状态的。 纵观所有BFS题目，套路都是一样的。]]>

POJ 1045-Bode Plot

Leave a reply

POJ 1045-Bode Plot Bode Plot Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 12888 Accepted: 8184 Description Consider the AC circuit below. We will assume that the circuit is in steady-state. Thus, the voltage at nodes 1 and 2 are given by v1 = VS coswt and v2 = VRcos (wt + q ) where VS is the voltage of the source, w is the frequency (in radians per second), and t is time. VR is the magnitude of the voltage drop across the resistor, and q is its phase. ![](http://poj.org/images/1045/bode.jpg) You are to write a program to determine VR for different values of w. You will need two laws of electricity to solve this problem. The first is Ohm’s Law, which states v2 = iR where i is the current in the circuit, oriented clockwise. The second is i = C d/dt (v1-v2) which relates the current to the voltage on either side of the capacitor. “d/dt”indicates the derivative with respect to t. Input The input will consist of one or more lines. The first line contains three real numbers and a non-negative integer. The real numbers are VS, R, and C, in that order. The integer, n, is the number of test cases. The following n lines of the input will have one real number per line. Each of these numbers is the angular frequency, w. Output For each angular frequency in the input you are to output its corresponding VR on a single line. Each VR value output should be rounded to three digits after the decimal point. Sample Input 1.0 1.0 1.0 9 0.01 0.031623 0.1 0.31623 1.0 3.1623 10.0 31.623 100.0 Sample Output 0.010 0.032 0.100 0.302 0.707 0.953 0.995 1.000 1.000 Source Greater New York 2001

这是一道数学+物理题，计算$$V_R$$的过程如下： 已知： ①$$v_1 = V_Scoswt$$ ②$$v_2 = V_R cos (wt+\theta )$$ ③$$v_2 = iR$$ ④$$i = C d/dt (v_1-v_2)$$ 把④代入③得⑤：$$v_2 =CR d/dt (v_1-v_2)$$ 再把①和②代入⑤得⑥：$$v_2=CR d/dt (V_Scoswt-V_R cos (wt+\theta ))$$ $$d/dt$$为对$$t$$求导，所以把⑥中的$$coswt$$和$$cos(wt+\theta )$$对$$t$$求导得到⑦：$$v_2=CRw(V_Rsin(wt+\theta )-V_Ssinwt)$$ 又因为②式，所以得到⑧：$$V_R cos (wt+\theta )=CRw(V_Rsin(wt+\theta )-V_Ssinwt)$$ 令$$wt+\theta =0$$，⑧式变为⑨：$$V_R=CRw(V_Ssin\theta)$$ 令$$t=0$$，⑧式变为⑩：$$tan\theta=1/CRw$$ 简单画一个三角形： 快速得到$$sin\theta=1/\sqrt{1+(CRw)^2}$$，代入⑨式得到最终结果：$$V_R=CRwV_S/\sqrt{1+(CRw)^2}$$ 得到了公式，快速写出代码： [cpp] #include<iostream> #include<cmath> #include<cstdio> using namespace std; int main() { //freopen("input.txt","r",stdin); double vs,r,c,w,vr; int n; cin>>vs>>r>>c>>n; while(n–) { cin>>w; vr=c*r*w*vs/sqrt(1+c*r*w*c*r*w); printf("%.3lf\n",vr); } return 0; } [/cpp] 本代码提交AC，用时0MS，内存208K。 ]]>

POJ 1837-Balance

1 Reply

POJ 1837-Balance Balance Time Limit: 1000MS Memory Limit: 30000K Total Submissions: 10845 Accepted: 6742 Description Gigel has a strange “balance” and he wants to poise it. Actually, the device is different from any other ordinary balance. It orders two arms of negligible weight and each arm’s length is 15. Some hooks are attached to these arms and Gigel wants to hang up some weights from his collection of G weights (1 <= G <= 20) knowing that these weights have distinct values in the range 1..25. Gigel may droop any weight of any hook but he is forced to use all the weights. Finally, Gigel managed to balance the device using the experience he gained at the National Olympiad in Informatics. Now he would like to know in how many ways the device can be balanced. Knowing the repartition of the hooks and the set of the weights write a program that calculates the number of possibilities to balance the device. It is guaranteed that will exist at least one solution for each test case at the evaluation. Input The input has the following structure: • the first line contains the number C (2 <= C <= 20) and the number G (2 <= G <= 20); • the next line contains C integer numbers (these numbers are also distinct and sorted in ascending order) in the range -15..15 representing the repartition of the hooks; each number represents the position relative to the center of the balance on the X axis (when no weights are attached the device is balanced and lined up to the X axis; the absolute value of the distances represents the distance between the hook and the balance center and the sign of the numbers determines the arm of the balance to which the hook is attached: ‘-‘ for the left arm and ‘+’ for the right arm); • on the next line there are G natural, distinct and sorted in ascending order numbers in the range 1..25 representing the weights’ values. Output The output contains the number M representing the number of possibilities to poise the balance. Sample Input 2 4 -2 3 3 4 5 8 Sample Output 2 Source Romania OI 2002

这一题题意为：给定一个天平，在天平两个臂上有若干个挂钩，给定若干砝码，问将所有砝码都挂上挂钩并使天平平衡的方法数有多少种？这一题有一定的难度，如果只有两个挂钩，问题比较好解决，可以看我的另一篇博客从一个数字序列中取若干个数字使得和为某个数，问共有多少种取数方案；但是这一题的挂钩有若干个，情况比较多，想过用动态规划、背包问题，但是一直想不出状态转换方程。 后来看了某前辈的解题报告，他提出了一个平衡度的概念，并推导出如下的状态转换方程：①dp[i][ j+ w[i]*c[k] ]= ∑(dp[i-1][j])。dp[i][j]表示前i个砝码使平衡度为j共有多少种方案数。 按照常理，我们得到的状态转换方程为：②dp[i][j] =∑(dp[i – 1][j – c[i] * w[i]])，表示dp[i][j]等于前i-1个砝码使平衡度为j-x的方案数之和，这个x就是第i个砝码挂在c个挂钩中的某一个产生的力臂。稍加推导就能得出①等价于②。 有了状态转换方程，我们可以很快的写出代码： [cpp] #include<iostream> using namespace std; int c[21]; int w[21]; int dp[21][15001]; int main() { int n,g; cin>>n>>g; for(int i=1;i<=n;i++) cin>>c[i]; for(int i=1;i<=g;i++) cin>>w[i]; dp[0][7500]=1;//不挂任何砝码的时候它本身就平衡了，所以是一种“挂法” for(int i=1;i<=g;i++)//对于每一个砝码 { for(int j=0;j<=15000;j++)//挂上去之后可能使天平出现0-15000中的任意一种状态 { if(dp[i-1][j])//如果这个状态之前出现过，则直接用 { for(int k=1;k<=n;k++) { dp[i][j+w[i]*c[k]]+=dp[i-1][j]; } } } } cout<<dp[g][7500]<<endl; return 0; } [/cpp] 代码提交AC，用时0MS，内存1060K。]]>

POJ 2676-Sudoku

Leave a reply

POJ 2676-Sudoku Sudoku Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 14104 Accepted: 6963 Special Judge Description Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3×3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3×3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task. Input The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0. Output For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them. Sample Input 1 103000509 002109400 000704000 300502006 060000050 700803004 000401000 009205800 804000107 Sample Output 143628579 572139468 986754231 391542786 468917352 725863914 237481695 619275843 854396127 Source Southeastern Europe 2005

这一题是练习深度搜索和剪枝的好题目。题意很简答，数独游戏，在每一行、每一列和每一个小正方形填入1-9这9个数字，数字不能重复，求一种可以的方案。 因为只需要求一种可行解，根据POJ Problem 3278: Catch That Cow后面的总结，很快有了深度搜索的思路：从上到下，从左到右依次扫描每一个格子，如果这个格子上的数字不是0，说明原来就有数字了，不用填，测试下一个格子；如果这个格子为0，则求出可填入该格子的候选数字，再依次测试每一个候选数字是否可行，一直这样深度搜索下去，直到将所有格子测试完毕。这个思路相信很多人都能很快想到，完整的代码如下： [cpp] #include<iostream> #include<vector> using namespace std; const int N=9; int board[N][N];//棋盘 int candidates[N];//对于某一个坐标ij，可以填入的候选数字 //给定坐标(row,column),求它所在的小方格的左上角坐标 void get_subquare_start(int row,int column,int& x0,int& y0) { if(row<3&&column<3) { x0=0; y0=0; } else if(row<3&&column<6) { x0=0; y0=3; } else if(row<3&&column<9) { x0=0; y0=6; } else if(row<6&&column<3) { x0=3; y0=0; } else if(row<6&&column<6) { x0=3; y0=3; } else if(row<6&&column<9) { x0=3; y0=6; } else if(row<9&&column<3) { x0=6; y0=0; } else if(row<9&&column<6) { x0=6; y0=3; } else if(row<9&&column<9) { x0=6; y0=6; } } //给定坐标(row,column),将可以填入该坐标的候选数字放入vi //思路就是先把candidates[N]填满1-9，然后将给定坐标的 //横轴、纵轴、小方格出现过的数字去掉，剩下的数字就是 //候选数字 void get_candidates(int row,int column,vector<int>& vi) { for(int i=0;i<N;i++) candidates[i]=i+1; for(int i=0;i<N;i++)//横轴 { if(board[row][i]!=0) candidates[board[row][i]-1]=0; } for(int i=0;i<N;i++)//纵轴 { if(board[i][column]!=0) candidates[board[i][column]-1]=0; } int x0,y0; get_subquare_start(row,column,x0,y0); for(int i=x0;i<x0+3;i++)//小方格 { for(int j=y0;j<y0+3;j++) { if(board[i][j]!=0) candidates[board[i][j]-1]=0; } } for(int i=0;i<N;i++)//重复工作，可优化 if(candidates[i]!=0) vi.push_back(candidates[i]); } //深度搜索 bool dfs(int pos) { if(pos==N*N) { return true; } int row=pos/N; int column=pos%N; if(board[row][column]!=0)//如果有数字 return dfs(pos+1);//则搜下一个格子 else { vector<int> local_candidates;//要使用局部的candidates，因为如果是全局的，那么回溯的时候candidates已经修改了 get_candidates(row,column,local_candidates);//获取可填入该格子的候选数字 int cand_num=local_candidates.size(); for(int i=0;i<cand_num;i++) { board[row][column]=local_candidates[i];//填入 if(dfs(pos+1))//继续搜下一个格子 return true; } board[row][column]=0;//回溯 return false;//回溯 } } int main() { freopen("input.txt","r",stdin); int t; char c; cin>>t; while(t–) { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { cin>>c; board[i][j]=c-‘0’; } } if(dfs(0)) { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) cout<<board[i][j]; cout<<endl; } } } return 0; } [/cpp] 满心欢喜的提交后发现TLE超时了，此时泪流满面，后来又琢磨了一下，师兄给的分类是简单搜索技巧和剪枝，我上面的代码压根就没有剪枝，TLE也就不足为奇了。 那么怎样剪枝？想一想我们手算解数独的过程，正常情况下，如果A这个格子有5个候选数字可以填入，而B这个格子只有2个候选数字可以填入，我们肯定会先填好B这个格子，再填A，因为B的情况少一些，而填完B之后，A的情况可能又会减少，这样比先填A再填B会快得多。根据这样的思路，我们在每次深度搜索的时候，把每个空格的候选数字求出来，并求候选数字个数最少的那个格子C，填格子C，继续深度搜索，直到所有空格填满为止。 可能有的同学会问，每次深度搜索的时候都要求一遍所有空格的候选数字，这样会不会耗时太多了，这个我也担心过，但是总体来说，剪枝比第一个版本的代码高效多了。下面是剪枝版本的完整代码： [cpp] #include<iostream> #include<vector> using namespace std; const int N=9; int board[N][N];//棋盘 int candidates[N];//对于某一个坐标ij，可以填入的候选数字 //给定坐标(row,column),求它所在的小方格的左上角坐标 void get_subquare_start(int row,int column,int& x0,int& y0) { if(row<3&&column<3) { x0=0; y0=0; } else if(row<3&&column<6) { x0=0; y0=3; } else if(row<3&&column<9) { x0=0; y0=6; } else if(row<6&&column<3) { x0=3; y0=0; } else if(row<6&&column<6) { x0=3; y0=3; } else if(row<6&&column<9) { x0=3; y0=6; } else if(row<9&&column<3) { x0=6; y0=0; } else if(row<9&&column<6) { x0=6; y0=3; } else if(row<9&&column<9) { x0=6; y0=6; } } //给定坐标(row,column),将可以填入该坐标的候选数字放入vi //思路就是先把candidates[N]填满1-9，然后将给定坐标的 //横轴、纵轴、小方格出现过的数字去掉，剩下的数字就是 //候选数字 void get_candidates(int row,int column,vector<int>& vi) { for(int i=0;i<N;i++) candidates[i]=i+1; for(int i=0;i<N;i++)//横轴 { if(board[row][i]!=0) candidates[board[row][i]-1]=0; } for(int i=0;i<N;i++)//纵轴 { if(board[i][column]!=0) candidates[board[i][column]-1]=0; } int x0,y0; get_subquare_start(row,column,x0,y0); for(int i=x0;i<x0+3;i++)//小方格 { for(int j=y0;j<y0+3;j++) { if(board[i][j]!=0) candidates[board[i][j]-1]=0; } } for(int i=0;i<N;i++)//重复工作，可优化 if(candidates[i]!=0) vi.push_back(candidates[i]); } //深度搜索 bool dfs(vector<int>& blank_pos) { int blank_num=blank_pos.size(); if(blank_num==0)//如果空格都填完了，返回true { return true; } int row,column,pos; int min_candidates=N+1; vector<int> global_candidates; for(int i=0;i<blank_num;i++) { row=blank_pos[i]/N; column=blank_pos[i]%N; vector<int> local_candidates; get_candidates(row,column,local_candidates);//对于每一个空格求可填入的候选数字 if(local_candidates.size()<min_candidates)//求到最小值 { pos=blank_pos[i];//记录位置 min_candidates=local_candidates.size(); global_candidates.clear(); global_candidates=local_candidates;//vector可以直接赋值 } } row=pos/N; column=pos%N; vector<int> next_blank_pos; for(int j=0;j<blank_num;j++) if(blank_pos[j]!=pos) next_blank_pos.push_back(blank_pos[j]);//剩余的空格 for(int i=0;i<min_candidates;i++) { board[row][column]=global_candidates[i];//填入 if(dfs(next_blank_pos))//继续搜下一个格子 return true; } board[row][column]=0;//回溯 return false;//回溯 } //剪枝版本，AC，用时282MS，内存240K int main() { //freopen("input.txt","r",stdin); int t; char c; cin>>t; vector<int> blank_pos; while(t–) { blank_pos.clear();//因为可能有多个case，所以每次都要clear！！！ for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { cin>>c; board[i][j]=c-‘0’; if(board[i][j]==0) blank_pos.push_back(i*N+j); } } if(dfs(blank_pos)) { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) cout<<board[i][j]; cout<<endl; } } } return 0; } [/cpp] 这个版本的代码需要注意一个小细节，我在每次输入的时候都将空格的位置记录在了blank_pos的vector中，因为题目说有多个case，所以每次输入的时候都要记得blank_pos.clear()，要不然会影响下一个case。这个版本的代码AC，用时282MS，内存240K。 AC之后，又看了一下discuss，发现很多同学谈到如果倒搜，会比顺搜快得多，倒搜就是从最后一个格子开始搜索。闲来无事，我就把第一个版本的代码改成了倒搜索，只需要修改两三个地方，代码如下： [cpp] #include<iostream> #include<vector> using namespace std; const int N=9; int board[N][N];//棋盘 int candidates[N];//对于某一个坐标ij，可以填入的候选数字 //给定坐标(row,column),求它所在的小方格的左上角坐标 void get_subquare_start(int row,int column,int& x0,int& y0) { if(row<3&&column<3) { x0=0; y0=0; } else if(row<3&&column<6) { x0=0; y0=3; } else if(row<3&&column<9) { x0=0; y0=6; } else if(row<6&&column<3) { x0=3; y0=0; } else if(row<6&&column<6) { x0=3; y0=3; } else if(row<6&&column<9) { x0=3; y0=6; } else if(row<9&&column<3) { x0=6; y0=0; } else if(row<9&&column<6) { x0=6; y0=3; } else if(row<9&&column<9) { x0=6; y0=6; } } //给定坐标(row,column),将可以填入该坐标的候选数字放入vi //思路就是先把candidates[N]填满1-9，然后将给定坐标的 //横轴、纵轴、小方格出现过的数字去掉，剩下的数字就是 //候选数字 void get_candidates(int row,int column,vector<int>& vi) { for(int i=0;i<N;i++) candidates[i]=i+1; for(int i=0;i<N;i++)//横轴 { if(board[row][i]!=0) candidates[board[row][i]-1]=0; } for(int i=0;i<N;i++)//纵轴 { if(board[i][column]!=0) candidates[board[i][column]-1]=0; } int x0,y0; get_subquare_start(row,column,x0,y0); for(int i=x0;i<x0+3;i++)//小方格 { for(int j=y0;j<y0+3;j++) { if(board[i][j]!=0) candidates[board[i][j]-1]=0; } } for(int i=0;i<N;i++)//重复工作，可优化 if(candidates[i]!=0) vi.push_back(candidates[i]); } //深度搜索 bool dfs(int pos) { if(pos==-1)//倒搜到-1结束 { return true; } int row=pos/N; int column=pos%N; if(board[row][column]!=0)//如果有数字 return dfs(pos-1);//则搜下一个格子 else { vector<int> local_candidates;//要使用局部的candidates，因为如果是全局的，那么回溯的时候candidates已经修改了 get_candidates(row,column,local_candidates);//获取可填入该格子的候选数字 int cand_num=local_candidates.size(); for(int i=0;i<cand_num;i++) { board[row][column]=local_candidates[i];//填入 if(dfs(pos-1))//继续搜下一个格子 return true; } board[row][column]=0;//回溯 return false;//回溯 } } //倒搜版本，AC，用时125MS，内存224K int main() { //freopen("input.txt","r",stdin); int t; char c; cin>>t; while(t–) { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { cin>>c; board[i][j]=c-‘0’; } } if(dfs(N*N-1))//倒搜 { for(int i=0;i<N;i++) { for(int j=0;j<N;j++) cout<<board[i][j]; cout<<endl; } } } return 0; } [/cpp] 令我吃惊的是，倒搜这个版本的代码AC了，而且用时125MS，内存224K，居然比剪枝还要快，内存占用也更少。到现在我还没有搞清楚更快的原因。]]>

POJ 1028-Web Navigation

Leave a reply

POJ 1028-Web Navigation Web Navigation Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 29660 Accepted: 13249 Description Standard web browsers contain features to move backward and forward among the pages recently visited. One way to implement these features is to use two stacks to keep track of the pages that can be reached by moving backward and forward. In this problem, you are asked to implement this. The following commands need to be supported: BACK: Push the current page on the top of the forward stack. Pop the page from the top of the backward stack, making it the new current page. If the backward stack is empty, the command is ignored. FORWARD: Push the current page on the top of the backward stack. Pop the page from the top of the forward stack, making it the new current page. If the forward stack is empty, the command is ignored. VISIT : Push the current page on the top of the backward stack, and make the URL specified the new current page. The forward stack is emptied. QUIT: Quit the browser. Assume that the browser initially loads the web page at the URL http://www.acm.org/ Input Input is a sequence of commands. The command keywords BACK, FORWARD, VISIT, and QUIT are all in uppercase. URLs have no whitespace and have at most 70 characters. You may assume that no problem instance requires more than 100 elements in each stack at any time. The end of input is indicated by the QUIT command. Output For each command other than QUIT, print the URL of the current page after the command is executed if the command is not ignored. Otherwise, print “Ignored”. The output for each command should be printed on its own line. No output is produced for the QUIT command. Sample Input VISIT http://acm.ashland.edu/ VISIT http://acm.baylor.edu/acmicpc/ BACK BACK BACK FORWARD VISIT http://www.ibm.com/ BACK BACK FORWARD FORWARD FORWARD QUIT Sample Output http://acm.ashland.edu/ http://acm.baylor.edu/acmicpc/ http://acm.ashland.edu/ http://www.acm.org/ Ignored http://acm.ashland.edu/ http://www.ibm.com/ http://acm.ashland.edu/ http://www.acm.org/ http://acm.ashland.edu/ http://www.ibm.com/ Ignored Source East Central North America 2001

水题一个。使用STL自带stack快速解决。有一个小细节需要注意：
BACK: Push the current page on the top of the forward stack. Pop the page from the top of the backward stack, making it the new current page. If the backward stack is empty, the command is ignored. FORWARD: Push the current page on the top of the backward stack. Pop the page from the top of the forward stack, making it the new current page. If the forward stack is empty, the command is ignored.
如果栈为空，则这个命令被忽略。被忽略的意思是就当没出现这个命令，自然也就不需要执行前半部分的操作了。
BACK: Push the current page on the top of the forward stack. FORWARD: Push the current page on the top of the backward stack.
完整代码如下： [cpp] #include<iostream> #include<stack> #include<string> using namespace std; int main() { //freopen("input.txt","r",stdin); string current_url="http://www.acm.org/"; stack<string> forward_url,backward_url; string command; while(cin>>command&&command!="QUIT") { if(command=="VISIT") { backward_url.push(current_url); cin>>current_url; cout<<current_url<<endl; while(!forward_url.empty()) { forward_url.pop(); } } else if(command=="BACK") { //forward_url.push(current_url);//If the backward stack is empty, the command is ignored忽略的话，这一句也不能执行 if(!backward_url.empty()) { forward_url.push(current_url); current_url=backward_url.top(); backward_url.pop(); cout<<current_url<<endl; } else { cout<<"Ignored"<<endl; } } else if(command=="FORWARD") { //backward_url.push(current_url); if(!forward_url.empty()) { backward_url.push(current_url); current_url=forward_url.top(); forward_url.pop(); cout<<current_url<<endl; } else { cout<<"Ignored"<<endl; } } } return 0; } [/cpp] 代码提交AC，用时0MS，内存200K。]]>

POJ 3278-Catch That Cow

1 Reply

POJ 3278-Catch That Cow Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 48323 Accepted: 15139 Description Farmer John has been informed of the location of a fugitive cow and wants to catch her immediately. He starts at a point N (0 ≤ N ≤ 100,000) on a number line and the cow is at a point K (0 ≤ K ≤ 100,000) on the same number line. Farmer John has two modes of transportation: walking and teleporting. Walking: FJ can move from any point X to the points X – 1 or X + 1 in a single minute Teleporting: FJ can move from any point X to the point 2 × X in a single minute. If the cow, unaware of its pursuit, does not move at all, how long does it take for Farmer John to retrieve it? Input Line 1: Two space-separated integers: N and K Output Line 1: The least amount of time, in minutes, it takes for Farmer John to catch the fugitive cow. Sample Input 5 17 Sample Output 4 Hint The fastest way for Farmer John to reach the fugitive cow is to move along the following path: 5-10-9-18-17, which takes 4 minutes. Source USACO 2007 Open Silver

又是一题广度搜索题，经过了上一题的锻炼，基本摸清了做广度优先搜索的套路，而且这一题比上一题还更简单一些。上一题是在三维空间里，而这一题只在一维直线上，只有三种情况：x-1、x+1、2*x。所以可以很快的写出代码： [cpp] #include<iostream> #include<queue> using namespace std; int n,k; int ans; int visited[100002]; const int MAX_DISTANCE=100000;//最大点位置 typedef struct P { int x;//坐标 int curr_min;//从n点到该点走过的时间 }; //广度优先搜索 void bfs() { queue<P> Q_P; P p,next_p; p.x=n; p.curr_min=0; visited[n]=1; Q_P.push(p); while(!Q_P.empty()) { p=Q_P.front(); Q_P.pop(); if(p.x==k) { ans=p.curr_min; return; } if(p.x-1>=0&&visited[p.x-1]==0) { visited[p.x-1]=1; next_p.x=p.x-1; next_p.curr_min=p.curr_min+1; Q_P.push(next_p); } if(p.x+1<=MAX_DISTANCE&&visited[p.x+1]==0) { visited[p.x+1]=1; next_p.x=p.x+1; next_p.curr_min=p.curr_min+1; Q_P.push(next_p); } if(2*p.x<=MAX_DISTANCE&&visited[2*p.x]==0) { visited[2*p.x]=1; next_p.x=2*p.x; next_p.curr_min=p.curr_min+1; Q_P.push(next_p); } } } int main() { cin>>n>>k; bfs(); cout<<ans; return 0; } [/cpp] 本代码提交AC，用时141MS，内存1304K。 仔细琢磨一下做过的深度搜索和广度搜索的题，你会发现，一般要求最短距离、最优化问题的，都是用广度优先搜索BFS，比如这一题和上一题；如果只是求某一个可行方案，那么可以用深度搜索，比如POJ Problem 1321: 棋盘问题和POJ Problem 1011: Sticks。当然广度搜索题其实也可以用深度搜索题解决，比如用深度搜索找出所有可行解，再求其中的最优解，但是这样的效率明显比只用广度搜索低。]]>