湖北中医药大学2019暑期练习赛题解（三）

落日映苍穹つ 2021-11-05 13:16 220阅读 0赞

# A - Ants POJ - 1852 #

An army of ants walk on a horizontal pole of length l cm, each with a constant speed of 1 cm/s. When a walking ant reaches an end of the pole, it immediatelly falls off it. When two ants meet they turn back and start walking in opposite directions. We know the original positions of ants on the pole, unfortunately, we do not know the directions in which the ants are walking. Your task is to compute the earliest and the latest possible times needed for all ants to fall off the pole.  
**Input**  
The first line of input contains one integer giving the number of cases that follow. The data for each case start with two integer numbers: the length of the pole (in cm) and n, the number of ants residing on the pole. These two numbers are followed by n integers giving the position of each ant on the pole as the distance measured from the left end of the pole, in no particular order. All input integers are not bigger than 1000000 and they are separated by whitespace.  
**Output**  
For each case of input, output two numbers separated by a single space. The first number is the earliest possible time when all ants fall off the pole (if the directions of their walks are chosen appropriately) and the second number is the latest possible such time.  
**Sample Input**  
2  
10 3  
2 6 7  
214 7  
11 12 7 13 176 23 191  
**Sample Output**  
4 8  
38 207

### 题目大意 ###

在长为len的绳子上有n只蚂蚁，蚂蚁可以左右爬，两只蚂蚁碰到之后都会掉头，朝反方向爬，当爬到左右两端就会落下去。若所有蚂蚁掉下去，所需的最长时间和最短时间分别是多少。

### 解题思路 ###

两只蚂蚁相碰可以理解为两只蚂蚁相互穿过去，因为两只蚂蚁本质上没有区别，两只蚂蚁共同的状态并没有改变。所以最后掉下去的那只蚂蚁，不管有没有阻拦，都可以看成无阻拦。所以所有蚂蚁掉下去的时间最小值就是每只蚂蚁掉下去的时间最小值（这个值就是向左和向右中取出的最小值）中取出时间最大的（时间最长的掉下去说明其他的已经掉下去了）。当所有蚂蚁掉下去的时间最大值就是每只蚂蚁掉下去的时间最大值中取出最大的。

**注意点：**  
1.数组比较大，应该开在mian函数之外  
2.输入的量比较大，应该用scanf，用cin会报错。  
3.这里用万能头文件会报错。

### 源代码 ###

#include <stdio.h>
    #include <iostream>
    #include<algorithm>
    using namespace std;
    int a[1000005];
    int main()
    { 
        int i,t;
        cin>>t;
        while(t--)
        { 
            int len,n;
            cin>>len>>n;
            int mi,ma;
            int min=-1,max=-1;
            for(i=0;i<n;i++)
            { 
                scanf("%d",&a[i]);
                mi=a[i]<(len-a[i])?a[i]:(len-a[i]);
                min=mi>min?mi:min;
                ma=a[i]>(len-a[i])?a[i]:(len-a[i]);
                max=ma>max?ma:max;
            }
    
            cout<<min<<" "<<max<<endl;
    
        }
    
        return 0;
    }

# B - Lake Counting POJ - 2386 #

Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (’.’). Farmer John would like to figure out how many ponds have formed in his field. A pond is a connected set of squares with water in them, where a square is considered adjacent to all eight of its neighbors.

Given a diagram of Farmer John’s field, determine how many ponds he has.  
**Input**  
\* Line 1: Two space-separated integers: N and M

\* Lines 2…N+1: M characters per line representing one row of Farmer John’s field. Each character is either ‘W’ or ‘.’. The characters do not have spaces between them.  
**Output**  
\* Line 1: The number of ponds in Farmer John’s field.  
**Sample Input**  
10 12  
W．．．．．．．．WW．  
．WWW．．．．．WWW  
．．．．WW．．．WW．  
．．．．．．．．．WW．  
．．．．．．．．．W．．  
．．W．．．．．．W．．  
．W．W．．．．．WW．  
W．W．W．．．．．W．  
．W．W．．．．．．W．  
．．W．．．．．．．W．  
**Sample Output**  
3  
**Hint**  
OUTPUT DETAILS:

There are three ponds: one in the upper left, one in the lower left,and one along the right side.

### 题目大意 ###

‘’w‘’表示有水，‘’．‘’代表旱地，一个或者多个w构成一个池塘，多个“w”相连，则认为他们是一个池塘，相连指的是一个池塘的八个方向之一有另一个池塘，问有多少池塘。

### 解题思路 ###

这题是一个深搜。以某个w为起点搜索他的周围所有的w，当搜过的w置为已经搜索过，搜索过的不重复搜索。当某个点搜索结束，池塘的数量加1，遍历所有点，即可得出所有池塘的数量。

### 源代码 ###

#include <stdio.h>
    #include <iostream>
    #include<algorithm>
    #include<string.h>
    //#include <bits/stdc++.h>
    using namespace std;
    bool found[105][105];
    int n,m;
    char a[105][105];
    void dfs(int x,int y)
    { 
        int i,j,k;
        if(found[x][y]==false&&x>=0&&x<n&&y>=0&&y<m)
        { 
            found[x][y]=true;
    
            for(i=-1;i<=1;i++)
            { 
                for(j=-1;j<=1;j++)
                { 
    
                    if((i+x)>=0&&(i+x)<n&&(j+y)>=0&&(j+y)<m&&a[i+x][j+y]=='W')
                    { 
                        dfs(i+x,j+y);
                    }
                }
            }
        }
    }
    int main()
    { 
        int i,j;
        cin>>n>>m;
        for(i=0;i<n;i++)
        { 
            for(j=0;j<m;j++)
            { 
                cin>>a[i][j];
            }
        }
        memset(found,false,sizeof(found));
        int count=0;
        for(i=0;i<n;i++)
        { 
            for(j=0;j<m;j++)
            { 
                if(found[i][j]==false&&a[i][j]=='W')
                { 
                    count++;
                    dfs(i,j);
                }
            }
        }
        cout<<count<<endl;
    
        return 0;
    }

# C - Best Cow Line #

FJ is about to take his N (1 ≤ N ≤ 2,000) cows to the annual"Farmer of the Year" competition. In this contest every farmer arranges his cows in a line and herds them past the judges.

The contest organizers adopted a new registration scheme this year: simply register the initial letter of every cow in the order they will appear (i.e., If FJ takes Bessie, Sylvia, and Dora in that order he just registers BSD). After the registration phase ends, every group is judged in increasing lexicographic order according to the string of the initials of the cows’ names.

FJ is very busy this year and has to hurry back to his farm, so he wants to be judged as early as possible. He decides to rearrange his cows, who have already lined up, before registering them.

FJ marks a location for a new line of the competing cows. He then proceeds to marshal the cows from the old line to the new one by repeatedly sending either the first or last cow in the (remainder of the) original line to the end of the new line. When he’s finished, FJ takes his cows for registration in this new order.

Given the initial order of his cows, determine the least lexicographic string of initials he can make this way.

**Input**

*  Line 1: A single integer: N
 *  Lines 2…N+1: Line i+1 contains a single initial (‘A’…‘Z’) of the cow in the ith position in the original line

**Output**  
The least lexicographic string he can make. Every line (except perhaps the last one) contains the initials of 80 cows (‘A’…‘Z’) in the new line.

**Sample Input**  
6  
A  
C  
D  
B  
C  
B  
**Sample Output**  
ABCBCD

### 题目大意 ###

从队列的首尾中取值，得出字典序最小的串。

### 解题思路 ###

这题用到的是贪心  
将队首和队尾的值取出来，进行比较，若队首小就拿出队首的值，并且输出，若队尾小就拿出队尾的值，并且输出。  
若队尾与队首相同，则比较里面一层字符，若还是相同，继续向内比较，直到比较出大小。若一直相同，前面的值的位置>=后面的值的位置之后就直接取队首的值。当队首的的值的位置>队尾的值的位置时，说明所有值都已经输出，循环结束。

### 源代码 ###

#include <iostream>
    using namespace std;
    int main()
    { 
    	int n,i;
    	cin>>n;
    	char a[2005];
    	for(i=0;i<n;i++)
    	cin>>a[i];
    	int start=0,end=n-1;
    	int count=0;
    	while(start<=end)
    	{ 
    		
    		for(i=0;start+i<i+end;i++)
    		{ 
    			if(a[i+start]>a[end-i])
    			{ 
    				cout<<a[end];
    				end--;
    				count++;
    				if(count%80==0)
    					cout<<endl;
    				break;
    			}	
    			else if(a[i+start]<a[end-i])
    			{ 
    				cout<<a[start];
    				start++;
    				count++;
    				if(count%80==0)
    					cout<<endl;
    				break;
    			}
    			
    		}
    		if(start+i>=i+end)
    		{ 
    			cout<<a[end];
    			end--;
    			count++;
    			if(count%80==0)
    				cout<<endl;
    		}
    		
    	}
    	return 0;
    }

# D - A - Crazy Rows SPOJ - HAROWS #

Crazy Rows

You are given an N x N matrix with 0 and 1 values. You can swap any two adjacent rows of the matrix.

Your goal is to have all the 1 values in the matrix below or on the main diagonal. That is, for each X where 1 ≤ X ≤ N, there must be no 1 values in row X that are to the right of column X.

Return the minimum number of row swaps you need to achieve the goal.

**Input**

The first line of input gives the number of cases, T. T test cases follow.  
The first line of each test case has one integer, N. Each of the next N lines contains N characters. Each character is either 0 or 1.

**Output**

For each test case, output

Case \#X: K  
where X is the test case number, starting from 1, and K is the minimum number of row swaps needed to have all the 1 values in the matrix below or on the main diagonal.

You are guaranteed that there is a solution for each test case.

Limits

1 ≤ T ≤ 60

1 ≤ N ≤ 8

**Input**

3  
2  
10  
11  
3  
001  
100  
010  
4  
1110  
1100  
1100  
1000  
**Output**  
Case \#1: 0  
Case \#2: 2  
Case \#3: 4

### 题目大意 ###

只能交换相邻行，问最少多少次，可以把所有的1移动到主对角线上，或者主对角线下方。

### 解题思路 ###

放在第一行的数到放在最后一行，限制越来越小，第一行就只能是00000…，或者10000…，最后一行可以随意放，。所以应该先从哪一行放在第一行开始考虑，有多行满足条件的时候就取最近的行，放在第一行的条件满足之后就继续往下看第二行，直到最后一行。每行的0和1的位置不重要，重要的是每行最右边的1的位置，最右边1的位置可以推出每行可以放的行的范围。

### 源代码 ###

#include <iostream>
    #include <algorithm>
    using namespace std;
    char a[10][10];
    int main()
    { 
    	int t;
    	cin>>t;
    	int kase=0;
    	while(t--)
    	{ 
    		int n;
    		int i,j;
    		int aend[10];
    		int ans=0;
    	
    		cin>>n;
    		for(i=0;i<n;i++)
    		{ 
    			for(j=0;j<n;j++)
    			{ 
    				cin>>a[i][j];
    			}
    		}
    		for(i=0;i<n;i++)//找到最右边的1的位置
    		{ 
    			aend[i]=-1;
    			for(j=n-1;j>=0;j--)
    			{ 
    				if(a[i][j]=='1')
    				{ 
    					aend[i]=j;	
    					break;		
    				}
    			}
    		}
    		for(i=0;i<n;i++)
    		{ 
    	 		int pos=-1;//要移动到第i行的行
     		 	for(j=i;j<n;j++)
            	{ 
    	            if(aend[j]<=i)
    	            { 
    	                pos=j;
    	                break;
    	            }
            	}
    
            	for(j=pos;j>i;j--)//交换相邻的行
            	{ 
            		 
    	            swap(aend[j],aend[j-1]);
    	            ans++;
           	 	}
    
    		}
    		printf("Case #%d: %d\n",++kase,ans);
    	}
    	return 0;
    }

# E - Bribe the Prisoners SPOJ - GCJ1C09C #

**Problem**

In a kingdom there are prison cells (numbered 1 to P) built to form a straight line segment. Cells number i and i+1 are adjacent, and prisoners in adjacent cells are called “neighbours.” A wall with a window separates adjacent cells, and neighbours can communicate through that window.

All prisoners live in peace until a prisoner is released. When that happens, the released prisoner’s neighbours find out, and each communicates this to his other neighbour. That prisoner passes it on to his other neighbour, and so on until they reach a prisoner with no other neighbour (because he is in cell 1, or in cell P, or the other adjacent cell is empty). A prisoner who discovers that another prisoner has been released will angrily break everything in his cell, unless he is bribed with a gold coin. So, after releasing a prisoner in cell A, all prisoners housed on either side of cell A - until cell 1, cell P or an empty cell - need to be bribed.

Assume that each prison cell is initially occupied by exactly one prisoner, and that only one prisoner can be released per day. Given the list of Q prisoners to be released in Q days, find the minimum total number of gold coins needed as bribes if the prisoners may be released in any order.

Note that each bribe only has an effect for one day. If a prisoner who was bribed yesterday hears about another released prisoner today, then he needs to be bribed again.

**Input**

The first line of input gives the number of cases, N. N test cases follow. Each case consists of 2 lines. The first line is formatted as

P Q

where P is the number of prison cells and Q is the number of prisoners to be released.  
This will be followed by a line with Q distinct cell numbers (of the prisoners to be released), space separated, sorted in ascending order.  
**Output**

For each test case, output one line in the format

Case \#X: C  
where X is the case number, starting from 1, and C is the minimum number of gold coins needed as bribes.  
Limits

1 ≤ N ≤ 100  
Q ≤ P  
Each cell number is between 1 and P, inclusive.

Large dataset

1 ≤ P ≤ 10000  
1 ≤ Q ≤ 100

**Sample**

**Input**  
2  
8 1  
3  
20 3  
3 6 14  
**Output**

Case \#1: 7  
Case \#2: 35  
Note

In the second sample case, you first release the person in cell 14, then cell 6, then cell 3. The number of gold coins needed is 19 + 12 + 4 = 35. If you instead release the person in cell 6 first, the cost will be 19 + 4 + 13 = 36.

### 题意 ###

有p个犯人，编号从1到p，现有q个犯人可以被释放，但是他两旁的所有犯人看到了觉得很不爽，所以要给1元钱来贿赂他们（请问他在监狱里到哪去花钱），一直到q个人都被释放，要求安排q个犯人释放的顺序，使得总代价最小。

### 解题思路 ###

这题是一个DP算法，dp\[i\]\[j\]表示的是，将从a\[i\]号囚犯到a\[j\]号囚犯（不含两端的囚犯）的连续部分里的所有囚犯都释放时，所需的最少金币总数。  
为了更方便的处理两端的情况，我们把左端当成0号囚犯，右端当成Q+1号囚犯。这样，dp\[0\]\[Q+1\]就是答案。

### 源代码 ###

#include <cstdio>
    #include <algorithm>
    using namespace std;
    
    int P, Q, a[10005];
    int dp[10005][10005];
    int main()
    { 
        int T,i,j,k;
        int q,w,t;
        int count=1;
        scanf("%d", &T);
    	while(T--)
        { 
            scanf("%d%d",&P,&Q);
    
            for(i=1;i<=Q;i++)
            { 
                scanf("%d",&a[i]);
            }
    
            a[0]=0;
            a[Q+1]=P+1;
    
            for(q=0;q<Q;q++)
            { 
                dp[q][q+1]=0;
            }
    
            for(w=2;w<=Q+1;w++)
            { 
                for(i=0;i+w<=Q+1;i++)
                { 
                    j=i+w;
                    t=100005;
    
                    for(k=i+1;k<j;k++)
                    { 
                        t= min(t,dp[i][k]+dp[k][j]);
                    }
                     dp[i][j]=t+a[j]-a[i]-2;
                }
            }
            printf("Case #%d: %d\n",count++,dp[0][Q+1]);
        }
        return 0;
    }