刷刷刷——蒟蒻的刷水题计划(1)

hoj 1684 Symmetric Order

In your job at Albatross Circus Management (yes, it’s run by a bunch of clowns), you have just finished writing a program whose output is a list of names in nondescending order by length (so that each name is at least as long as the one preceding it). However, your boss does not like the way the output looks, and instead wants the output to appear more symmetric, with the shorter strings at the top and bottom and the longer strings in the middle. His rule is that each pair of names belongs on opposite ends of the list, and the first name in the pair is always in the top part of the list. In the first example set below, Bo and Pat are the first pair, Jean and Kevin the second pair, etc.

Input

The input consists of one or more sets of strings, followed by a final line containing only the value 0. Each set starts with a line containing an integer, n, which is the number of strings in the set, followed by n strings, one per line, sorted in nondescending order by length. None of the strings contain spaces. There is at least one and no more than 15 strings per set.  Each string is at most 25 characters long.

Output

For each input set print “SET n on a line, where n starts at 1, followed by the output set as shown in the sample output.

Sample Input

Sample Output

[cpp]
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
using namespace std;

int main()
{
int n,T=1;
while(cin>>n&&n){
printf("SET %dn",T++);
string s[n];
for(int i=0;i<n/2;i++){
cin>>s[i];
cin>>s[n-i-1];
}
if(n%2==1) cin>>s[n/2];
for(int i=0;i<n;i++){
cout<<s[i]<<endl;
}
}
}
[/cpp]

poj 1852 Ants

Description

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

Sample Output

[cpp]
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
int temp[1000010];
int main()
{
int Case;
while(scanf("%d",&Case)!=EOF){
while(Case–){
memset(temp,0,sizeof(temp));
int l,n;
scanf("%d %d",&l,&n);
int minT=0,maxT=0;
for(int i=0;i<n;i++)
scanf("%d",&temp[i]);
/*蚂蚁相遇时可以看成并没有返回而是继续向前走直到端点*/
for(int i=0;i<n;i++)
{
minT=max(minT,min(temp[i],l-temp[i]));
maxT=max(maxT,max(temp[i],l-temp[i]));
}
printf("%d %dn",minT,maxT);
}
}
return 0;
}
[/cpp]

poj 2386 Lake Counting

Description

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

Sample Output

Hint

OUTPUT DETAILS:

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

第一次写dfs,从任意的W开始dfs,并且通过递归把与它连通的W也转化为’.’。读取数据的时候有些要注意的地方。。

[cpp]
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>
#define MAXN 110
#define MAXM 110
using namespace std;
int N,M;
char field [MAXN][MAXM];
void dfs(int x,int y) //深度搜索
{
field[x][y]=’.’;
for(int dx=-1;dx<=1;dx++) //循环遍历八个方向
for(int dy=-1;dy<=1;dy++){
int nx=x+dx,ny=y+dy;
if(0<=nx&&nx<N&&ny>=0&&ny<M&&field[nx][ny]==’W’) dfs(nx,ny);
}
}
int main()
{

while(scanf("%d %d",&N,&M)==2){
getchar(); //读走回车
memset(field,0,sizeof(field));
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
scanf("%c",&field[i][j]); //储存
}
getchar();
}
int ans=0;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++)
{
if(field[i][j]==’W’){ //有积水后开始dfs
dfs(i,j);
ans++;
}
}
}
printf("%dn",ans);
}
}
[/cpp]

hdu 1016 prime ring problme

Problem Description

A ring is compose of n circles as shown in diagram. Put natural number 1, 2, …, n into each circle separately, and the sum of numbers in two adjacent circles should be a prime.

Note: the number of first circle should always be 1.

Input
n (0 < n < 20).
Output

The output format is shown as sample below. Each row represents a series of circle numbers in the ring beginning from 1 clockwisely and anticlockwisely. The order of numbers must satisfy the above requirements. Print solutions in lexicographical order.

You are to write a program that completes above process.

Print a blank line after each case.

Sample Input
6 8
Sample Output
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2

分析:dfs练习,加上了一些剪枝,还是不够熟练。

[cpp]
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;
int vis[22]; //数组下标代表对应的数字
int num[22]; //环
int n,Case=1;
bool isPrime(int n)
{
bool flag = true;
if(n==2) return true;
for(int i=2;i<=sqrt(n);i++){
if(n%i==0)
{
flag=false;
break;
}
}
return flag;
}
void Print()
{
for(int i=1;i<n;i++) printf("%d ",num[i]);
printf("%dn",num[n]);
}
void dfs(int c) //c代表圆环上的位置
{
if(c>n){
if(isPrime(num[1]+num[n]))
Print();
}
else{
for(int i=2;i<=n;i++){
if(vis[i]) continue; //使用过了的数跳过
if(isPrime(i+num[c-1])){
vis[i]=1;
num[c]=i;
dfs(c+1);
vis[i]=0;
num[c]=0; //恢复至原来情况,该情况已经遍历完
}

}
}
}

int main()
{

while(scanf("%d",&n)!=EOF){
memset(num,0,sizeof(num));
memset(vis,0,sizeof(vis));
vis[1]=1;
num[1]=1;
printf("Case %d:n",Case++);
dfs(2);
printf("n");
}
return 0;
}
[/cpp]

 Poj 3617 best cow line

思路,字典序最小,就是要开头部分的字母尽可能的小,贪心选择左边第一个字母和右边第一个字母中最小的那个,如果二者相同就继续往后面进行选择,直到可以判断…..

[cpp]
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#define maxn 2010
using namespace std;
int n;
char s[maxn+1];
void solve()
{
int left=0,right=n-1,cnt=0;
for(int i=1;i<=n;i++){
bool flag=false;
for(int j=0;left+j<=right;j++){
if(s[left+j]<s[right-j]){ flag=true; break; //找到左边字符比右边字符小 }
else if(s[left+j]>s[right-j]){
flag=false;
break;
}
}
if(flag) {printf("%c",s[left++]);cnt++;}
else {printf("%c",s[right–]);cnt++;}
if(cnt%80==0||i==n) printf("n");
}
}
int main()
{
while(scanf("%d",&n)!=EOF){
getchar();
for(int i=0;i<n;i++) {scanf("%c",&s[i]);getchar();}
solve();
}
}
[/cpp]

发表评论

电子邮件地址不会被公开。 必填项已用*标注