Category Archives: POJ

POJ 2251-Dungeon Master

1 Reply

POJ 2251-Dungeon Master Dungeon Master Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 16959 Accepted: 6603 Description You are trapped in a 3D dungeon and need to find the quickest way out! The dungeon is composed of unit cubes which may or may not be filled with rock. It takes one minute to move one unit north, south, east, west, up or down. You cannot move diagonally and the maze is surrounded by solid rock on all sides. Is an escape possible? If yes, how long will it take? Input The input consists of a number of dungeons. Each dungeon description starts with a line containing three integers L, R and C (all limited to 30 in size). L is the number of levels making up the dungeon. R and C are the number of rows and columns making up the plan of each level. Then there will follow L blocks of R lines each containing C characters. Each character describes one cell of the dungeon. A cell full of rock is indicated by a ‘#’ and empty cells are represented by a ‘.’. Your starting position is indicated by ‘S’ and the exit by the letter ‘E’. There’s a single blank line after each level. Input is terminated by three zeroes for L, R and C. Output Each maze generates one line of output. If it is possible to reach the exit, print a line of the form Escaped in x minute(s). where x is replaced by the shortest time it takes to escape. If it is not possible to escape, print the line Trapped! Sample Input 3 4 5 S…. .###. .##.. ###.# ##### ##### ##.## ##… ##### ##### #.### ####E 1 3 3 S## #E# ### 0 0 0 Sample Output Escaped in 11 minute(s). Trapped! Source Ulm Local 1997

经典广度优先搜索题，网上居然把这题分到深度优先搜索了，害的我写好DFS提交后得到个TLE。 首先分析题意，给出一个立体的迷宫，要求从S走到E，求最短距离，其中迷宫中#不能走，.这个能走。我们可以用三维数组char dungeon[MAX_SIZE][MAX_SIZE][MAX_SIZE];来存储迷宫，对于某一个点dungeon[i][j][k]，可以试探下面六个点：dungeon[i-1][j][k]、dungeon[i+1][j][k]、dungeon[i][j-1][k]、dungeon[i][j+1][k]、dungeon[i][j][k-1]、dungeon[i][j][k+1]，想象你站在空间某一点，你可以往上、下、前、后、左、右走。 如果是深度搜索，试探到某点可行之后，访问它，并以该点为基点继续试探下去，直到到达E点或者无路可走，然后清除访问，每次到达E点，就比较一下这次走过的距离和上次的距离哪个小，当所有点都试探完毕时，就能得到最小值。 如果是广度搜索，以S点为起点，找到所有可行的下一个点，访问他们，并把他们插入到一个队列，然后在队列不为空的情况下循环：取出队首元素，以该元素为基点，找到所有可行的下一个点，访问他们，并把他们加入到队列中。如果广度搜索的过程中遇到E点，则此时走过的距离就是最小值，因为是广度搜索，最先访问到的肯定是最小值，不需要像深度搜索那样再进行比较。 下面是完整代码： [cpp] #include<iostream> #include<queue> using namespace std; const int MAX_SIZE=60; const int MAX_DISTANCE=1024; int L,R,C; char dungeon[MAX_SIZE][MAX_SIZE][MAX_SIZE];//迷宫 //int visited[MAX_SIZE][MAX_SIZE][MAX_SIZE]; int ans; int s_l,s_r,s_c,e_l,e_r,e_c; typedef struct P//点 { int x,y,z;//坐标 int dist;//从S到该点走过的距离 }; //深度搜索，结果正确，但是TLE /*void dfs(int l,int r,int c,int steps) { int visited[MAX_SIZE][MAX_SIZE][MAX_SIZE]={0};//每次初始化 if(l==e_l&&r==e_r&&c==e_c)//搜索成功 { if(steps<ans)//求最小值 ans=steps; return; } //深度搜索的六种情况 if((l-1)>=0&&visited[l-1][r][c]==0&&dungeon[l-1][r][c]==’.’) { visited[l-1][r][c]=1; dfs(l-1,r,c,steps+1);//继续深度搜索 visited[l-1][r][c]=0;//回溯 } if((l+1)<L&&visited[l+1][r][c]==0&&dungeon[l+1][r][c]==’.’) { visited[l+1][r][c]=1; dfs(l+1,r,c,steps+1); visited[l+1][r][c]=0; } if((r-1)>=0&&visited[l][r-1][c]==0&&dungeon[l][r-1][c]==’.’) { visited[l][r-1][c]=1; dfs(l,r-1,c,steps+1); visited[l][r-1][c]=0; } if((r+1)<R&&visited[l][r+1][c]==0&&dungeon[l][r+1][c]==’.’) { visited[l][r+1][c]=1; dfs(l,r+1,c,steps+1); visited[l][r+1][c]=0; } if((c-1)>=0&&visited[l][r][c-1]==0&&dungeon[l][r][c-1]==’.’) { visited[l][r][c-1]=1; dfs(l,r,c-1,steps+1); visited[l][r][c-1]=0; } if((c+1)<C&&visited[l][r][c+1]==0&&dungeon[l][r][c+1]==’.’) { visited[l][r][c+1]=1; dfs(l,r,c+1,steps+1); visited[l][r][c+1]=0; } }*/ //广度搜索 bool bfs(int s_l,int s_r,int s_c) { int visited[MAX_SIZE][MAX_SIZE][MAX_SIZE]={0};//记得每次都要初始化为0，否则会影响下一个case queue<P> P_Q;//队列 P p,next_p; p.x=s_l,p.y=s_r,p.z=s_c,p.dist=0; visited[s_l][s_r][s_c]=1; P_Q.push(p); int l,r,c; while(!P_Q.empty()) { p=P_Q.front(); P_Q.pop(); if(p.x==e_l&&p.y==e_r&&p.z==e_c) { ans=p.dist;//因为是广度搜索，最先到达E，肯定就是最小值 return true; } l=p.x,r=p.y,c=p.z; //广度搜索的六种情况 if((l-1)>=0&&visited[l-1][r][c]==0&&dungeon[l-1][r][c]==’.’) { visited[l-1][r][c]=1; next_p.x=l-1; next_p.y=r; next_p.z=c; next_p.dist=p.dist+1; P_Q.push(next_p); } if((l+1)<L&&visited[l+1][r][c]==0&&dungeon[l+1][r][c]==’.’) { visited[l+1][r][c]=1; next_p.x=l+1; next_p.y=r; next_p.z=c; next_p.dist=p.dist+1; P_Q.push(next_p); } if((r-1)>=0&&visited[l][r-1][c]==0&&dungeon[l][r-1][c]==’.’) { visited[l][r-1][c]=1; next_p.x=l; next_p.y=r-1; next_p.z=c; next_p.dist=p.dist+1; P_Q.push(next_p); } if((r+1)<R&&visited[l][r+1][c]==0&&dungeon[l][r+1][c]==’.’) { visited[l][r+1][c]=1; next_p.x=l; next_p.y=r+1; next_p.z=c; next_p.dist=p.dist+1; P_Q.push(next_p); } if((c-1)>=0&&visited[l][r][c-1]==0&&dungeon[l][r][c-1]==’.’) { visited[l][r][c-1]=1; next_p.x=l; next_p.y=r; next_p.z=c-1; next_p.dist=p.dist+1; P_Q.push(next_p); } if((c+1)<C&&visited[l][r][c+1]==0&&dungeon[l][r][c+1]==’.’) { visited[l][r][c+1]=1; next_p.x=l; next_p.y=r; next_p.z=c+1; next_p.dist=p.dist+1; P_Q.push(next_p); } } return false; } int main() { //freopen("input.txt","r",stdin); while(cin>>L>>R>>C&&L&&R&&C) { ans=MAX_DISTANCE; for(int i=0;i<L;i++) for(int j=0;j<R;j++) for(int k=0;k<C;k++) { cin>>dungeon[i][j][k]; if(dungeon[i][j][k]==’S’) { s_l=i; s_r=j; s_c=k; } else if(dungeon[i][j][k]==’E’) { dungeon[i][j][k]=’.’;//注意这里改成了’.’，便于BFS里搜索判断 e_l=i; e_r=j; e_c=k; } } //dfs(s_l,s_r,s_c,0); if(bfs(s_l,s_r,s_c)) cout<<"Escaped in "<<ans<<" minute(s)."<<endl; else cout<<"Trapped!"<<endl; } return 0; } [/cpp] 本代码提交AC，用时63MS，内存1248K。]]>

POJ 1125-Stockbroker Grapevine

Leave a reply

POJ 1125-Stockbroker Grapevine Stockbroker Grapevine Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 27559 Accepted: 15273 Description Stockbrokers are known to overreact to rumours. You have been contracted to develop a method of spreading disinformation amongst the stockbrokers to give your employer the tactical edge in the stock market. For maximum effect, you have to spread the rumours in the fastest possible way. Unfortunately for you, stockbrokers only trust information coming from their “Trusted sources” This means you have to take into account the structure of their contacts when starting a rumour. It takes a certain amount of time for a specific stockbroker to pass the rumour on to each of his colleagues. Your task will be to write a program that tells you which stockbroker to choose as your starting point for the rumour, as well as the time it will take for the rumour to spread throughout the stockbroker community. This duration is measured as the time needed for the last person to receive the information. Input Your program will input data for different sets of stockbrokers. Each set starts with a line with the number of stockbrokers. Following this is a line for each stockbroker which contains the number of people who they have contact with, who these people are, and the time taken for them to pass the message to each person. The format of each stockbroker line is as follows: The line starts with the number of contacts (n), followed by n pairs of integers, one pair for each contact. Each pair lists first a number referring to the contact (e.g. a ‘1’ means person number one in the set), followed by the time in minutes taken to pass a message to that person. There are no special punctuation symbols or spacing rules. Each person is numbered 1 through to the number of stockbrokers. The time taken to pass the message on will be between 1 and 10 minutes (inclusive), and the number of contacts will range between 0 and one less than the number of stockbrokers. The number of stockbrokers will range from 1 to 100. The input is terminated by a set of stockbrokers containing 0 (zero) people. Output For each set of data, your program must output a single line containing the person who results in the fastest message transmission, and how long before the last person will receive any given message after you give it to this person, measured in integer minutes. It is possible that your program will receive a network of connections that excludes some persons, i.e. some people may be unreachable. If your program detects such a broken network, simply output the message “disjoint”. Note that the time taken to pass the message from person A to person B is not necessarily the same as the time taken to pass it from B to A, if such transmission is possible at all. Sample Input 3 2 2 4 3 5 2 1 2 3 6 2 1 2 2 2 5 3 4 4 2 8 5 3 1 5 8 4 1 6 4 10 2 7 5 2 2 2 5 1 5 Sample Output 3 2 3 10 Source Southern African 2001

首先读懂题意。Stockbroker想要给每一个人传播谣言，问从哪一个人开始传播，可以使谣言传播得最快，并求最快的传播时间是多少。转换成数据结构的语言就是：给你一张图，问从哪一点到其他所有点的最短距离中的最长者最短。表述起来有点绕，下面用图示来说明。 假设分别从A点和B点开始的单源最短距离如上两张图所示，那么Stockbroker从A点开始传播谣言总共需要多长时间呢？因为传播是可以同时进行的，所以传播结束时间就是A点到其他点中的最长距离，也就是上图中的AC。同理，如果从B点开始，则|BD|是传播时间。 综上所述，本题的求解过程可以归纳为以下几步： 1. 测试图中的每一个点$$i$$，求从该点出发，到其他所有点的单源最短距离集合$$S_i$$ 2. 求出该单源最短距离$$S_i$$内部的最大值$$M_i$$ 3. 对于图中的所有点，求其$$M_i$$ 4. 最后求所有$$M_i$$中的最小值$$MIN$$，即为最终结果 所以根据上面的步骤，我们可以用n次Dijkstra算法求每个点的单源最短距离内部的最大值$$M_i$$，然后求$$MIN$$。其实也可以不用这么麻烦，因为我们还有另外一个更简单的算法Floyd算法。使用Floyd算法求得所有点对的最短距离，自然就知道某个点的单源最短距离了。 在写代码的时候还有一些小问题需要注意，对于数据输入，请仔细多读几遍Input说明，如果还是有困难，请看这里，题目还要求如果是非连通图，输出disjoint，那么怎么来判断是否是非连通图呢？我使用的方法是：把图中不相连的两条边的距离设置为MAX_DISTANCE=1024，因为本题的距离取值范围是[1，10]，所以如果最终求出来的最小值大于MAX_DISTANCE，说明在求解的时候通过了不相连的边，也就说明这个图是非连通图。（后来我仔细想了一下，这个方法好像不对，但是代码还是AC，据说数据比较弱。） 完整代码如下： [cpp] #include<iostream> using namespace std; const int MAX_DISTANCE=1024;//距离取值范围[1,10]，所以用1024代表无穷大 const int MAX_PEOPLE_NUM=101;//最多传播者 int path[MAX_PEOPLE_NUM][MAX_PEOPLE_NUM];//路径 int n;//实际人数 //初始化路径都为0 void init_path() { for(int i=0;i<n;i++) for(int j=0;j<n;j++) path[i][j]=0; } //floyd算法求所有点对的最短距离 void floyd() { for(int k=0;k<n;k++) { for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(path[i][j]>path[i][k]+path[k][j]) path[i][j]=path[i][k]+path[k][j]; } } } } int main() { int connected_num,person_index; while(cin>>n&&n) { init_path(); //输入数据 for(int i=0;i<n;i++) { cin>>connected_num; for(int j=0;j<connected_num;j++) { cin>>person_index; cin>>path[i][person_index-1]; } } //给不相连的两者的距离赋为最大值无穷 for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(i!=j&&path[i][j]==0) path[i][j]=MAX_DISTANCE; } } floyd();//调用floyd算法，求得所有点对的最短距离，还是保存在path[][]中 int longest_path,global_shorest=MAX_DISTANCE,start_person; for(int i=0;i<n;i++)//对于以i为起点的单源最短距离 { longest_path=0;//求出这个单源最短距离中的最大值 for(int j=0;j<n;j++) if(path[i][j]>longest_path) longest_path=path[i][j]; if(longest_path<global_shorest)//再求其最小值 { start_person=i; global_shorest=longest_path; } } if(global_shorest<MAX_DISTANCE) cout<<start_person+1<<" "<<global_shorest<<endl; else cout<<"disjoint"<<endl;//非连通图 } return 0; } [/cpp] 本代码提交AC，用时0MS，内存256K。网上有人讨论还可以用SPFA算法，改天学习了重新提交一个版本。 ]]>

POJ 2503-Babelfish

Leave a reply

POJ 2503-Babelfish Babelfish Time Limit: 3000MS Memory Limit: 65536K Total Submissions: 33433 Accepted: 14347 Description You have just moved from Waterloo to a big city. The people here speak an incomprehensible dialect of a foreign language. Fortunately, you have a dictionary to help you understand them. Input Input consists of up to 100,000 dictionary entries, followed by a blank line, followed by a message of up to 100,000 words. Each dictionary entry is a line containing an English word, followed by a space and a foreign language word. No foreign word appears more than once in the dictionary. The message is a sequence of words in the foreign language, one word on each line. Each word in the input is a sequence of at most 10 lowercase letters. Output Output is the message translated to English, one word per line. Foreign words not in the dictionary should be translated as “eh”. Sample Input dog ogday cat atcay pig igpay froot ootfray loops oopslay atcay ittenkay oopslay Sample Output cat eh loops Hint Huge input and output,scanf and printf are recommended. Source Waterloo local 2001.09.22

水题。题目说明了“No foreign word appears more than once in the dictionary”，又要快速查找，马上想到用MAP来当字典，然后查找。这题稍微有点麻烦是的输入输出，因为题目没有给出具体的输入结束标志，需要自己判断，输入的又是字符串，且含有空格空行等，虽然题目hint建议用printf或scanf，但是我选择了用C++的getline，看起来更加优雅。 getline的优点是一次读入一行，不管有没有空格，而且它还能读入空行，所以我们可以使用下面的代码来读取一行并判断跳出循环条件： [cpp] while(getline(cin,s)) { if(s=="") break; } [/cpp] 其他的就是常规的字符串处理，map查找输出。具体代码如下： [cpp] #include<iostream> #include<string> #include<map> #include<vector> using namespace std; int main() { string s; map<string,string> mss; vector<string> vs; while(getline(cin,s)) { if(s=="") break; int blankPos=s.find(" ");//找到空格位置 mss[s.substr(blankPos+1)]=s.substr(0,blankPos);//插入map } while(getline(cin,s)) { if(s=="") break; if(mss.find(s)!=mss.end()) { vs.push_back(mss[s]); //cout<<mss[s]<<endl; } else //cout<<"eh"<<endl; vs.push_back("eh"); } int v_size=vs.size(); for(int i=0;i<v_size;i++) { cout<<vs[i]; if(i!=v_size-1) cout<<endl; } return 0; } [/cpp] 本代码提交AC，用时1000MS，内存14648K，效率比较低，如果使用scanf和printf估计会好些。]]>

POJ 2151-Check the difficulty of problems

Leave a reply

POJ 2151-Check the difficulty of problems Check the difficulty of problems Time Limit: 2000MS Memory Limit: 65536K Total Submissions: 5066 Accepted: 2238 Description Organizing a programming contest is not an easy job. To avoid making the problems too difficult, the organizer usually expect the contest result satisfy the following two terms: 1. All of the teams solve at least one problem. 2. The champion (One of those teams that solve the most problems) solves at least a certain number of problems. Now the organizer has studied out the contest problems, and through the result of preliminary contest, the organizer can estimate the probability that a certain team can successfully solve a certain problem. Given the number of contest problems M, the number of teams T, and the number of problems N that the organizer expect the champion solve at least. We also assume that team i solves problem j with the probability Pij (1 <= i <= T, 1<= j <= M). Well, can you calculate the probability that all of the teams solve at least one problem, and at the same time the champion team solves at least N problems? Input The input consists of several test cases. The first line of each test case contains three integers M (0 < M <= 30), T (1 < T <= 1000) and N (0 < N <= M). Each of the following T lines contains M floating-point numbers in the range of [0,1]. In these T lines, the j-th number in the i-th line is just Pij. A test case of M = T = N = 0 indicates the end of input, and should not be processed. Output For each test case, please output the answer in a separate line. The result should be rounded to three digits after the decimal point. Sample Input 2 2 2 0.9 0.9 1 0.9 0 0 0 Sample Output 0.972 Source POJ Monthly,鲁小石

这题纯粹的数学概率题，不太好做。题目大意是：有m个问题，t个队，要求冠军至少解决n个问题，所有队至少解决1个问题，问这样的概率是多少。对于题目中给的样例，我们可以手算得出，分3种情况：a.第一个队是冠军，第二个队只解出一题0.9*0.9*1*0.1=0.081；b.第二个队是冠军，第一个队只解出一题(0.9*0.1+0.1*0.9)*1*0.9=0.162；c.两个队都是冠军，也就是并列冠军0.9*0.9*1*0.9=0.729；把这三种情况加起来就是0.972。 但是如果m,t的数字很大，问题就没那么简单了，解题思路比较难想到，可以参考以下两篇博客： 比较难理解的是概率的转化：
要求：每队至少解出一题且冠军队至少解出N道题的概率。
由于冠军队可以不止一队，即允许存在并列冠军。 则原来的所求的概率可以转化为：每队均至少做一题的概率P1 减去 每队做题数均在1到N-1之间的概率P2。 如果理解了上面那句话，使用概率DP就很容易写出代码： [cpp] #include<iostream> #include<cstdio> using namespace std; int m,t,n; double p[1001][31];//p[i][j]第i个队解出第j题的概率 double dp[1001][31][31];//dp[i][j][k]第i个队在前j个题中解出k个题的概率dp[i][j][k]=dp[i][j-1][k-1]*p[j][k]+dp[i][j-1][k]*(1-p[j][k])分第j个题能和不能解出来 double s[1001][31];//s[i][k]第i个队最多解出k个题的概率s[i][k]=dp[i][M][0]+dp[i][M][1]+…+dp[i][M][k] void solve() { for(int i=1;i<=t;i++) { dp[i][0][0]=1.0;//初始化，第i支队伍前0道题做对0道的概率为1 for(int j=1;j<=m;j++) { for(int k=0;k<=j;k++) { dp[i][j][k]=dp[i][j-1][k]*(1-p[i][j]); if(k!=0) dp[i][j][k]+=dp[i][j-1][k-1]*p[i][j]; } } s[i][0]=dp[i][m][0]; for(int j=1;j<=m;j++) s[i][j]=s[i][j-1]+dp[i][m][j]; } double p1=1.0,p2=1.0; for(int i=1;i<=t;i++) { p1*=(1-s[i][0]); p2*=(s[i][n-1]-s[i][0]); } printf("%.3f\n",p1-p2); } int main() { while(cin>>m>>t>>n&&m&&t&&n) { for(int i=1;i<=t;i++) for(int j=1;j<=m;j++) cin>>p[i][j]; solve(); } return 0; } [/cpp] 本代码提交AC，用时94MS，内存8228K。]]>

POJ 1321-棋盘问题

Leave a reply

POJ 1321-棋盘问题 棋盘问题 Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 23209 Accepted: 11512 Description 在一个给定形状的棋盘（形状可能是不规则的）上面摆放棋子，棋子没有区别。要求摆放时任意的两个棋子不能放在棋盘中的同一行或者同一列，请编程求解对于给定形状和大小的棋盘，摆放k个棋子的所有可行的摆放方案C。 Input 输入含有多组测试数据。 每组数据的第一行是两个正整数，n k，用一个空格隔开，表示了将在一个n*n的矩阵内描述棋盘，以及摆放棋子的数目。 n <= 8 , k <= n 当为-1 -1时表示输入结束。 随后的n行描述了棋盘的形状：每行有n个字符，其中 # 表示棋盘区域， . 表示空白区域（数据保证不出现多余的空白行或者空白列）。 Output 对于每一组数据，给出一行输出，输出摆放的方案数目C （数据保证C< 2^31）。 Sample Input 2 1 #. .# 4 4 …# ..#. .#.. #… -1 -1 Sample Output 2 1 Source 蔡错@pku

这题可以看成是深度搜索的样题或者经典题。有点类似八皇后问题，题目要求在棋盘上能放棋子的区域放上规定数目的棋子，且保证同行和同列最多放一个棋子，问一共有多少种解法。 本题的限制条件就是同行和同列最多放一个棋子，那么我们在搜索的时候就可以以行为单位搜索，每次测试一行，这样就保证同一行最多放了一个棋子，那么怎样保证同列最多放一个棋子呢？我们可以设置一个数组`int col[]`数组，`col[i]=0`表示该行还没有放棋子；`col[i]=1`表示该行已经放了棋子了。这样我们在搜索的时候就可以这样： [cpp] if(board[i][j]==’#’&&col[j]==0)//如果可以放棋子，且这一列上还没有放过棋子 { col[j]=1;//则在该处放棋子 dfs(i,placed_num+1);//继续往下搜索 col[j]=0;//回溯 } [/cpp] 本题的思路和代码都不难，对于深度搜索的题目，还是要多做，做多了自然会摸索出其中的固定模式。下面是完整代码： [cpp] #include<iostream> using namespace std; int n,k,ans; char board[9][9];//棋盘 int col[9];//每一列是否放置了棋子，0没放；1放了。 //深度搜索，row表示上一次搜索的行号，placed_num表示已经放了几个棋子了 void dfs(int row,int placed_num) { if(placed_num==k)//如果所有棋子都放好了，则找到一个解 { ans++; return; } for(int i=row+1;i<n;i++)//否则的话，从下一行开始搜索每一行 { for(int j=0;j<n;j++)//对该行的所有位置（列） { if(board[i][j]==’#’&&col[j]==0)//如果可以放棋子，且这一列上还没有放过棋子 { col[j]=1;//则在该处放棋子 dfs(i,placed_num+1);//继续往下搜索 col[j]=0;//回溯 } } } } //初始的时候，每一列都没有放棋子 void init_col() { for(int i=0;i<9;i++) col[i]=0; } int main() { while(cin>>n>>k&&n!=-1&&k!=-1) { ans=0; init_col(); for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>board[i][j]; dfs(-1,0);//row=-1；placed_num=0 cout<<ans<<endl; } return 0; } [/cpp] 本代码AC，用时32MS，内存216K。]]>

POJ 1258-Agri-Net

Leave a reply

POJ 1258-Agri-Net Agri-Net Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 40975 Accepted: 16713 Description Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course. Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms. Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm. The distance between any two farms will not exceed 100,000. Input The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem. Output For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms. Sample Input 4 0 4 9 21 4 0 8 17 9 8 0 16 21 17 16 0 Sample Output 28 Source USACO 102

这一题相对第2485来说就更是彻头彻尾的最小生成树了。它要求的是最小生成树的总长度，所以对2485稍微修改即可。需要注意的是题目中有这么一句话：
The input includes several cases.
也就是说有多个测试用例，而不是直接告诉你有几个用例或者结束标志是0 0 0之类的，我一开始写成了 [cpp] while(1) { scanf("%d",&n); … } [/cpp] 这样就变成了有无穷个测试用例了，根本停不下来，所以Time Limit Exceeded好几次，后来改成这样就好了： [cpp] while(scanf("%d",&n)!=EOF) { … } [/cpp] 完整的代码如下： [cpp] #include<stdio.h> int a[101][101]; int lowcost[101]; //int closet[101]; const static int MAX_DIS=100001; //最长距离 //prim算法求最小生成树 int prim(int n) { for(int i=0;i<n;i++) { lowcost[i]=a[0][i]; //closet[i]=0;//这个数组可以不要 } int total_min_len=0; int k,curr_min_len; for(int t=0;t<n-1;t++) { k=0; curr_min_len=MAX_DIS; for(int i=0;i<n;i++) { if(lowcost[i]!=0&&lowcost[i]<curr_min_len) { curr_min_len=lowcost[i]; k=i; } } total_min_len+=curr_min_len;//这题才是求和 //if(curr_min_len>total_min_len)//注意看题，求最小生成树中的最长路径 // total_min_len=curr_min_len; lowcost[k]=0; for(int i=0;i<n;i++) { if(a[i][k]!=0&&a[i][k]<lowcost[i]) { lowcost[i]=a[i][k]; //closet[i]=k; } } } return total_min_len; } int main() { int n; //while(1)//The input includes several cases.并不代表case无穷 while(scanf("%d",&n)!=EOF) { //scanf("%d",&n); for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&a[i][j]); printf("%d\n",prim(n)); } return 0; } [/cpp] 本代码提交AC，用时16MS，内存172K。可以看到内存明显比2485题少了，那是因为我把closet数组删了，因为常规的最小生成树不需要这个变量。]]>

POJ 2485-Highways

1 Reply

POJ 2485-Highways Highways Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 22907 Accepted: 10553 Description The island nation of Flatopia is perfectly flat. Unfortunately, Flatopia has no public highways. So the traffic is difficult in Flatopia. The Flatopian government is aware of this problem. They’re planning to build some highways so that it will be possible to drive between any pair of towns without leaving the highway system. Flatopian towns are numbered from 1 to N. Each highway connects exactly two towns. All highways follow straight lines. All highways can be used in both directions. Highways can freely cross each other, but a driver can only switch between highways at a town that is located at the end of both highways. The Flatopian government wants to minimize the length of the longest highway to be built. However, they want to guarantee that every town is highway-reachable from every other town. Input The first line of input is an integer T, which tells how many test cases followed. The first line of each case is an integer N (3 <= N <= 500), which is the number of villages. Then come N lines, the i-th of which contains N integers, and the j-th of these N integers is the distance (the distance should be an integer within [1, 65536]) between village i and village j. There is an empty line after each test case. Output For each test case, you should output a line contains an integer, which is the length of the longest road to be built such that all the villages are connected, and this value is minimum. Sample Input 1 3 0 990 692 990 0 179 692 179 0 Sample Output 692 Hint Huge input,scanf is recommended. Source POJ Contest,Author:Mathematica@ZSU

原始的最小生成树算法，但是要注意题目要我们求解的是什么：
which is the length of the longest road to be built such that all the villages are connected, and this value is minimum.
最小生成树中的最长路径，而不是最小生成树！读题一定要仔细。 代码如下： [cpp] #include<stdio.h> int a[501][501]; int lowcost[501]; int closet[501]; //prim算法求最小生成树 int prim(int n) { for(int i=0;i<n;i++) { lowcost[i]=a[0][i]; closet[i]=0;//这个数组可以不要 } int total_min_len=0; int k,curr_min_len; for(int t=0;t<n-1;t++) { k=0; curr_min_len=65537; for(int i=0;i<n;i++) { if(lowcost[i]!=0&&lowcost[i]<curr_min_len) { curr_min_len=lowcost[i]; k=i; } } //total_min_len+=curr_min_len; if(curr_min_len>total_min_len)//注意看题，求最小生成树中的最长路径 total_min_len=curr_min_len; lowcost[k]=0; for(int i=0;i<n;i++) { if(a[i][k]!=0&&a[i][k]<lowcost[i]) { lowcost[i]=a[i][k]; closet[i]=k; } } } return total_min_len; } int main() { int t,n; scanf("%d",&t); while(t–) { scanf("%d",&n); for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%d",&a[i][j]); printf("%d\n",prim(n)); } return 0; } [/cpp] 本代码提交AC，用时157MS，内存528K。]]>

POJ 1019-Number Sequence

Leave a reply

POJ 1019-Number Sequence Number Sequence Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 34278 Accepted: 9835 Description A single positive integer i is given. Write a program to find the digit located in the position i in the sequence of number groups S1S2…Sk. Each group Sk consists of a sequence of positive integer numbers ranging from 1 to k, written one after another. For example, the first 80 digits of the sequence are as follows: 11212312341234512345612345671234567812345678912345678910123456789101112345678910 Input The first line of the input file contains a single integer t (1 ≤ t ≤ 10), the number of test cases, followed by one line for each test case. The line for a test case contains the single integer i (1 ≤ i ≤ 2147483647) Output There should be one output line per test case containing the digit located in the position i. Sample Input 2 8 3 Sample Output 2 2 Source Tehran 2002, First Iran Nationwide Internet Programming Contest

做这一题需要细心，我们先分析一下题意。给出一串数字，问你这个数字串中第i个位置的数字是什么。其中数字串是形如112123123412345123456123456712345678123456789123456789101234567891011123456789101112这样的。 仔细分析一下就是1、12、123、1234，…，123456789、12345678910、1234567891011，… 串联起来的。我们定义单个数字串1234…i的长度为single_len[i]，总的数字串1,12,123,…,123…i.的长度为total_len[i]。因为1,12,123,…,123…i.=1,12,123,…,123…(i-1).+123…i.所以我们可以得出一个等式：total_len[i]=total_len[i-1]+single_len[i]。那么怎么来求解single_len[i]呢？ single_len[0]=0; single_len[1]=1; single_len[2]=2; single_len[10]=11. 因为single_len[i]为123…(i-1)i的长度，single_len[i-1]为123…(i-1)的长度。很显然，single_len[i]=single_len[i-1]+数字i的长度。这有点类似动态规划的状态转移方程。求数字i的长度可以用下面的函数求解： [cpp] //求数字i的位数 int get_digits_num(int i) { int rs=1; while(i>=10) { rs++; i/=10; } return rs; } [/cpp] 当然也可以用stringstream先将int转换为string再求string.size()，但是这种方法更慢。 当我们求到了single_len和total_len，就可以分两步求解总的数字串中第i个位置的数字了。首先在total_len中找到位置i在哪一个内部串中，然后再在内部串中找到位置i的确切位置。这就有点像信号调节中的粗调和微调，首先找到大致的位置，然后在某个局部找细节的位置。 比如给定数字串112123123412345123456123456712345678123456789123456789101234567891011123456789101112。问i=18位置处的数字是什么。我们已经求到total_len[0]=0; total_len[1]=1; total_len[2]=3; total_len[3]=6; total_len[4]=10; total_len[5]=15; total_len[6]=21; 。18正好在total_len[5]和total_len[6]之间。因为total_len[5]=15表示以5结束的总的数字串的长度为15<18，所以我们取total_len[6]，也就是i=18必定在以6结尾的总的数字串中，即在112123123412345123456中，且在以6结尾的单个数字串中的第i-total_len[6-1]=18-15=3个位置，也就是在123456的第3个位置即3，所以最终结果就是3。 所以总结一下求解的步骤就是： 1. 计算single_len和total_len。 2. 在total_len中二分查找位置i在以last_num为末尾数字的总的串中。 3. 计算出在以last_num为末尾数字的单个内部串中位置i所在的相对位置inner_index。 4. 在以last_num为末尾数字的单个内部串中二分查找出相对位置为inner_index的数字。 其中要数第4步最难，其二分搜索函数如下： [cpp] //（单组数字串）内部二分搜索 char bin_search_inner(int i) { int s=1,t=MAX_N,mid; while(s<t) { mid=(s+t)/2; if(single_len[mid]<i) s=mid+1; else if(single_len[mid]==i) { string s=int2string(mid); return s[s.size()-1]; } else t=mid-1; } if(single_len[t]<i) t++; string rs=int2string(t); return rs[rs.size()-(single_len[t]-i)-1]; } [/cpp] 其中的single_len[mid]==i分支：比如single_len[12]=15; single_len[13]=17;如果mid==12; i==15.结果是多少呢？single_len[12]=15表示以12结尾的数字串的长度为15，而i正好为15，所以结果应该为123456789101112的最后一个数字2。 假设single_len[1234]=9843; i=9841; 这时t=1234，结果又是多少呢？假设我们到了rs[rs.size()-(single_len[t]-i)-1];这一步。通过直观观察，i=9841的位置是2，因为single_len[1234]=9843表示1234末尾的数字4的i=9843，往前推自然得到i=9841时数字为2；怎样写成一个公式呢？single_len[t]-i=2表示位置i离末尾数字的距离为2，那么它离开头的距离为多少呢？很显然用t（也就是rs=int2string(t)）的总长度减去离末尾的距离再减1就行了。也就是rs[rs.size()-(single_len[t]-i)-1];，所以我们是从这个数字的末尾往前推的。 还要注意一下i最大为2147483647，2147483647刚好是int的正整数最大极限值，所以total_len要用unsigned int。其他的就没有太多要解释的了。具体看代码： [cpp] #include<iostream> #include<string> #include<sstream> #include<cstdlib> using namespace std; const static int MAX_N=31269;//数字串中最大的数 int single_len[MAX_N]={0};//single_len[i]表示1,2,3,…,i.这个数字串中总的数字位数 unsigned int total_len[MAX_N]={0};//total_len[i]表示1,12,123,…,123…i.这个数字串中总的数字位数 //将int转换为string string int2string(int i) { stringstream ss; string s; ss<<i; ss>>s; return s; } //求数字i的位数 int get_digits_num(int i) { int rs=1; while(i>=10) { rs++; i/=10; } return rs; } //初始化单组数字串 void init_single_len() { for(int i=1;i<MAX_N;i++) { single_len[i]=single_len[i-1]+get_digits_num(i); } } //初始化总体数字串 void init_total_len() { for(int i=1;i<MAX_N;i++) { total_len[i]=total_len[i-1]+single_len[i]; } } //外部（总体）二分搜索 int bin_search_outer(int i) { int s=1,t=MAX_N-1,mid; while(s<t) { mid=(s+t)/2; if(total_len[mid]<i) s=mid+1; else if(total_len[mid]==i) return mid; else t=mid-1; } if(total_len[t]<i) return t+1; else return t; } //（单组数字串）内部二分搜索 char bin_search_inner(int i) { int s=1,t=MAX_N,mid; while(s<t) { mid=(s+t)/2; if(single_len[mid]<i) s=mid+1; else if(single_len[mid]==i) { string s=int2string(mid); return s[s.size()-1]; } else t=mid-1; } if(single_len[t]<i) t++; string rs=int2string(t); return rs[rs.size()-(single_len[t]-i)-1]; } int main() { int t,i; cin>>t; init_single_len(); init_total_len(); //cout<<total_len[31268]<<endl; while(t–) { cin>>i; int last_num=bin_search_outer(i); int inner_index=i-total_len[last_num-1]; cout<<bin_search_inner(inner_index)<<endl; } return 0; } [/cpp] 本代码提交AC，用时16MS，内存464K。]]>

POJ 2586-Y2K Accounting Bug

Leave a reply

POJ 2586-Y2K Accounting Bug Y2K Accounting Bug Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 10647 Accepted: 5328 Description Accounting for Computer Machinists (ACM) has sufferred from the Y2K bug and lost some vital data for preparing annual report for MS Inc. All what they remember is that MS Inc. posted a surplus or a deficit each month of 1999 and each month when MS Inc. posted surplus, the amount of surplus was s and each month when MS Inc. posted deficit, the deficit was d. They do not remember which or how many months posted surplus or deficit. MS Inc., unlike other companies, posts their earnings for each consecutive 5 months during a year. ACM knows that each of these 8 postings reported a deficit but they do not know how much. The chief accountant is almost sure that MS Inc. was about to post surplus for the entire year of 1999. Almost but not quite. Write a program, which decides whether MS Inc. suffered a deficit during 1999, or if a surplus for 1999 was possible, what is the maximum amount of surplus that they can post. Input Input is a sequence of lines, each containing two positive integers s and d. Output For each line of input, output one line containing either a single integer giving the amount of surplus for the entire year, or output Deficit if it is impossible. Sample Input 59 237 375 743 200000 849694 2500000 8000000 Sample Output 116 28 300612 Deficit Source Waterloo local 2000.01.29

这个题首先要读懂题意，其中的
ACM knows that each of these 8 postings reported a deficit
我一开始看不懂，不知道这个8代表什么意思，是怎么来的，看过别人的解释才知道，原来前面说每连续5个月会发布一次盈亏报告，而一年又12个月，总共可以发布8次，即：1-5,2-6,3-7,4-8,5-9,6-10,7-11,8-12。注意每次报告的月份和前后的报告的月份是有重叠的。 题目告诉我们这8次报告都是亏损，但是求这一年是否可以盈利，总的盈利最多是多少。这道题有点最优化的感觉，已知约束是8次报告都是亏损，求最优化总的盈利。 这道题可以有两种解法。 贪心 因为要求盈利最大化，所以可以先设12个月都是盈利的，然后再慢慢调整满足8次报告都是亏损的。一次报告是连续的5个月的总和，要保证一次报告是亏损，5个月里至少一个月是亏损的，亏损的月份放在5个月里的最后月份是最好的，因为这样可以和下一个报告重叠，使总的盈利最大。比如1-5使第5月份亏损，就能保证这个报告亏损，则2-6已经包含5月份了，当然这个报告肯定也亏损。这样1-5和2-6实际只有5月份是亏损的。但是如果1-5使第1月份亏损，虽然第一个报告是亏损的，但是2-6还是盈利的，又使第2月份亏损，则1-5和2-6实际有1月份和2月份是亏损的，这就亏损了两个月。 所以每次我们要亏损时，都从该报告的最后月份开始试探，一直往前试探，直到这个报告亏损。一直循环8个报告。最后求这一年总的盈亏。代码如下： [cpp] #include<iostream> #include<vector> using namespace std; int main() { int s,d; while(cin>>s>>d) { int surplus_num;//盈余的月份数 vector<int> month(12,1);//初始的时候每个月都是surplus，1为surplus，0为deficit for(int i=0;i<8;i++)//8个‘连续5个月’ { surplus_num=0; for(int j=0;j<5;j++) surplus_num+=month[i+j]; int k=0; while(surplus_num*s>=(5-surplus_num)*d) { month[i+4-k]=0;//亏损的月份尽量放到后面，因为可以和下一个周期重叠，这样总的surplus会大一些 surplus_num=0; for(int j=0;j<5;j++) surplus_num+=month[i+j]; k++; } } surplus_num=0; for(int i=0;i<12;i++) surplus_num+=month[i]; int rs=surplus_num*s-(12-surplus_num)*d;//这一年总的盈亏 if(rs<0) cout<<"Deficit"<<endl; else cout<<rs<<endl; } return 0; } [/cpp] 这个版本提交AC，用时32MS，内存216K。 枚举 因为这题只有12月份，每个报告只是连续5个月，要是每个报告都亏损，则可以在5个月里有1个月份亏损、2个月份亏损、3个月份亏损、4个月份亏损、5个月份亏损。前4种情况依次求解，直到既满足每个报告亏损，又使12个月总的是盈利。如果前4种都不行，那总的肯定是亏损。 这4种情况可以这样来表示，由于每5个月的报账都为亏损，所有连续的5个月里至少有1个月为亏损，则可能产生最优解的情况为如下4种
1 2 3 4 5 6 7 8 9 10 11 12 s s s s d s s s s d s s //每5个月里只有1个月亏损 s s s d d s s s d d s s //每5个月里只有2个月亏损 s s d d d s s d d d s s //每5个月里只有3个月亏损 s d d d d s d d d d s d //每5个月里只有4个月亏损
从上到下一次枚举四种情况，如果满足条件（每次报账都为亏损），则算出ans = (盈利的月数)*s – (亏损的月数)*d,若ans>0 则输出 否则输出Deficit；若上述4种情况都不满足，则直接输出Deficit. 代码如下： [cpp] #include<iostream> using namespace std; int main() { int a,b; while(cin>>a>>b) { int ans = 0; if(4*a-b<0) { ans = 10*a-2*b; } else if(3*a-2*b<0) { ans = 8*a-4*b; } else if(2*a-3*b<0) { ans = 6*a-6*b; } else if(a-4*b<0) { ans = 3*a-9*b; } else { ans = -1; } if(ans>0) cout<<ans<<endl; else cout<<"Deficit"<<endl; } return 0; } [/cpp] 这个版本提交AC，用时0MS，内存216K。 很显然，枚举速度更快，但是如果总共有1000个月份，每个报告20个月，共50个报告，或者数字更大时，枚举就很麻烦了，所以掌握第一种贪心的方法还是很有必要的。]]>

POJ 1012-Joseph

Leave a reply

POJ 1012-Joseph Joseph Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 48397 Accepted: 18267 Description The Joseph’s problem is notoriously known. For those who are not familiar with the original problem: from among n people, numbered 1, 2, . . ., n, standing in circle every mth is going to be executed and only the life of the last remaining person will be saved. Joseph was smart enough to choose the position of the last remaining person, thus saving his life to give us the message about the incident. For example when n = 6 and m = 5 then the people will be executed in the order 5, 4, 6, 2, 3 and 1 will be saved. Suppose that there are k good guys and k bad guys. In the circle the first k are good guys and the last k bad guys. You have to determine such minimal m that all the bad guys will be executed before the first good guy. Input The input file consists of separate lines containing k. The last line in the input file contains 0. You can suppose that 0 < k < 14. Output The output file will consist of separate lines containing m corresponding to k in the input file. Sample Input 3 4 Sample Output 5 30 Source Central Europe 1995

这个题目挺有趣的。有k个好人和k个坏人，依次编号为1~k~2k，其中前k个为好人，后k个为坏人。然后从1开始循环报数，报到m的被杀掉，杀掉之后，从被杀掉的下一个人开始又从1开始循环报数。求最小的m使得在杀好人之前，所有的坏人都已经被杀掉了。 看到这个题很快能得出两个约束条件： 1. 因为坏人的编号大于k，所以m的取值肯定要大于k，要不然第一个杀的肯定是好人。 2. 对于某个m，最多只需要循环杀k个人，我们就能判断这个m是不是所求，杀人的过程中杀到某个人的编号小于等于k，则肯定杀到好人了，但此时还没有杀完所有坏人，所以这个m不是所求，跳出，m++；如果这k个人都成功杀完，则所有坏人都杀完，m是所求。 以上思路都很简单，但是有一个关键问题没有解决：已知第i次杀人的编号是a[i]，那么杀完a[i]后，下一个杀的人的编号是多少呢？如果是环形不杀人，只是报数的话，易知是(a[i]+m-1)%n，但是杀完某个人后下一轮报数时这个人已经不在了，要跳过他，所以编号是(a[i]+m-1)%(n-i)，这就是著名的Joseph环。 有了Joseph环这个结论就很好办了，加上之前的两点结论，我们可以很快的写出代码，如下： [cpp] #include <stdio.h> int main() { int people[28] = {0}, k, Joseph[14] = {0};//k最多是13，people所有人的编号，Joseph用于打表，不然超时 while(scanf("%d", &k) != EOF && k != 0) { if (Joseph[k] != 0)//如果是之前求过的 { printf("%d\n", Joseph[k]);//则直接输出 continue; } int n = 2 * k; int m = k+1;//m从k+1开始测试 people[0] = 0;//people[0] = 0表示编号从0开始 for (int i = 1; i <= k; i++)//最多连续杀k个人 { //每次枚举完毕将剩下的人按从0到n – i编号，只要好人没有杀掉，则前面k – 1个编号是不变的 people[i] = (people[i – 1] + m – 1) % (n – i + 1); if (people[i] < k)//第k个人的编号为k – 1,所以这里是<而不是<= //杀到好人了 { i = 0 ;//重新开始 //有点continue的意思 m++; //测试下一个m } } Joseph[k] = m; printf("%d\n", m); } return 0; } [/cpp] 以上代码参考这个博客，做了微小的调整。代码AC，用时250MS，内存136K。 其实在我不知道Joseph环公式的时候，我用双向链表（其实就是STL里的list）写了一个版本，这个版本很朴实，就是杀一个人之后，把这个节点去掉，然后再循环报数，这样就不需要琢磨下一个被杀的编号到底是多少啊，但是这个版本超时严重。我也把代码贴上来，以供参考。 [cpp] #include<iostream> #include<list> #include<map> using namespace std; //测试m是否是所求 bool check_m(int k,int m) { list<int> li; for(int i=1;i<=2*k;i++) li.push_back(i);//首先初始化链表，人的编号从1开始 int pos=1,executed_num=0;//pos当前报数，executed_num被杀的人数 list<int>::iterator it=li.begin(),tmp; while(executed_num<k)//最多杀k个人就可以判断m { if(pos==m)//如果报数到m了。 { //cout<<*it<<endl; if(*it<=k)//但是编号小于等于k，则杀到好人了。 return false; tmp=it; tmp++; li.erase(it);//否则把这个坏人杀掉并去除这个节点 it=tmp; pos=1;//重新从1开始报数 executed_num++; } else//如果还没报到m，则一直报下去，这个地方可能会消耗比较多的时间 { pos++; it++; } if(it==li.end())//如果到链表尾了，则循环到头 it=li.begin(); } return true; } int main() { int k,m; map<int,int> mii; //用于打表 while(cin>>k&&k) { if(mii.find(k)!=mii.end())//如果之前计算过这个k，则直接输出 { cout<<mii[k]<<endl; continue; } for(m=k+1;;m++) { if(check_m(k,m)) { cout<<m<<endl; mii[k]=m; break; } } } return 0; } [/cpp]]]>