GHIJ待补...

A.HUD5702:Solving Order

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 3550    Accepted Submission(s): 2149

Problem Description Welcome to HDU to take part in the first CCPC girls' competition!



As a pretty special competition, many volunteers are preparing for it with high enthusiasm.
One thing they need to do is blowing the balloons.

Before sitting down and starting the competition, you have just passed by the room where the boys are blowing the balloons. And you have found that the number of balloons of different colors are strictly different.

After thinking about the volunteer boys' sincere facial expressions, you noticed that, the problem with more balloon numbers are sure to be easier to solve.

Now, you have recalled how many balloons are there of each color.
Please output the solving order you need to choose in order to finish the problems from easy to hard.
You should print the colors to represent the problems.  

 

Input The first line is an integer T which indicates the case number.
And as for each case, the first line is an integer n, which is the number of problems.
Then there are n lines followed, with a string and an integer in each line, in the i-th line, the string means the color of ballon for the i-th problem, and the integer means the ballon numbers.

It is guaranteed that:
T is about 100.
1≤n≤10.
1≤ string length ≤10.
1≤ bolloon numbers ≤83.(there are 83 teams :p)
For any two problems, their corresponding colors are different.
For any two kinds of balloons, their numbers are different.
 

 

Output For each case, you need to output a single line.
There should be n strings in the line representing the solving order you choose.
Please make sure that there is only a blank between every two strings, and there is no extra blank.
  Sample Input 3 3 red 1 green 2 yellow 3 1 blue 83 2 red 2 white 1   Sample Output yellow green red blue red white

题意：

　　将气球按数量排序从大到小输出

题解：

　　排序输出

#include <stdio.h>
#include <string>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
#define ll long long
#define exp 1e-8
using namespace std;
const int N = 20+5;
const int INF = 0x3f3f3f3f;
struct node{
    string s;
    int num;
}a[N];
bool cmp(node x,node y){
    return x.num>y.num;
}
int main(){
    int T,n;
    for (scanf("%d",&T);T;T--){
        scanf("%d",&n);
        for(int i=0;i<n;i++){
            cin>>a[i].s>>a[i].num;
        }
        sort(a,a+n,cmp);
        for (int i=0;i<n;i++) {
            cout<<a[i].s<< ((i==n-1)?"\n":" ");
        }
    }
    return 0;
}

View Code

 

 

B.HUD5703Desert

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 2586    Accepted Submission(s): 1660

Problem Description A tourist gets lost in the desert with n liters of water. He drinks positive integer units of water each day.

Write a program to calculate how many different ways the tourist can drink up the water.  

 

Input The first line contains the number of test cases T(T≤10).
Next T lines contain the number n(1≤n≤1000000) for each test case.
 

 

Output Output consists of T lines.
Each line contains the binary number which represents number of different ways to finish up the water specified in the test case.
 

 

Sample Input 1 3  

 

Sample Output 100   Hint 3 liters of water can be comsumed in four different ways show in the following. 1. 1 1 1 2. 1 2 3. 2 1 4. 3 If we write 4 in binary, it's 100.

题意：

　　一共有n升水，每天必须喝正整数升，问有几种不同的方法。

　　既，用正整数组成n有多少种组成方法。

　　用二进制方式输出。

题解：

　　这题是打表找的规律，列出前几项之后发现f(n)=2^n-1。

 

#include <stdio.h>
#include <string>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
#define ll long long
#define exp 1e-8
using namespace std;
int main(){
    int T,n;
    for (scanf("%d",&T);T;T--){
        scanf("%d",&n);
        printf("1");
        for (int i=1;i<n;i++){
            printf("0");
        }
        printf("\n");
    }
    return 0;
}

View Code

 

 

 

C.HDU5704Luck Competition

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)
Total Submission(s): 1775    Accepted Submission(s): 1087

Problem Description Participants of the Luck Competition choose a non-negative integer no more than 100 in their mind. After choosing their number, let K be the average of all numbers, and M be the result of K×23. Then the lucky person is the one who choose the highest number no more than M. If there are several such people, the lucky person is chosen randomly.

If you are given a chance to know how many people are participating the competition and what their numbers are, calculate the highest number with the highest probability to win assuming that you're joining the competition.
 

 

Input There are several test cases and the first line contains the number of test cases T(T≤10).

Each test case begins with an integer N(1<N≤100), denoting the number of participants. And next line contains N−1 numbers representing the numbers chosen by other participants.

  Output For each test case, output an integer which you have chosen and the probability of winning (round to two digits after the decimal point), seperated by space.

  Sample Input 3 4 1 2 3 4 1 1 2 4 20 30 40    Sample Output 1 0.50 0 1.00 18 1.00  

题意：

 　　n个人参加比赛，每个人选择一个非负整数，谁选的数小于且最接近 这些数的平均数的2/3 ，谁就可能成为幸运者，现在已知有n个人，给出n-1个人选的数，第n个人是你，你要成为幸运者应该选择哪个数，以及你选择了这个数之后能成为幸运者的概率是多少。

题解：

　　根据题目我们可以推出幸运数x满足：

　　x≤ (x+sum)/n  * 2/3            =>          x≤ (2*sum)/(3*n-2)            其中sum为n-1个数的和，n为n个人。

#include <stdio.h>
#include <string>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
#define ll long long
#define exp 1e-8
using namespace std;
int main(){
    int T,n,x;
    for (scanf("%d",&T);T;T--){
        scanf("%d",&n);
        int sum = 0,a[110]={0};
        for (int i=1;i<n;i++){
            scanf("%d",&x);
            a[x]++;
            sum+=x;
        }
        int ans = (int)(2.0*sum/(3.0*n-2));
        a[ans]++;
        printf("%d %.2f\n", ans,1.0/a[ans]);
    }
    return 0;
}

View Code

 

 

D.HDU5705Clock

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 1707    Accepted Submission(s): 625

Problem Description Given a time HH:MM:SS and one parameter a, you need to calculate next time satisfying following conditions:

1. The angle formed by the hour hand and the minute hand is a.
2. The time may not be a integer(e.g. 12:34:56.78), rounded down(the previous example 12:34:56).

  Input The input contains multiple test cases.

Each test case contains two lines.
The first line is the time HH:MM:SS(0≤HH<12,0≤MM<60,0≤SS<60).
The second line contains one integer a(0≤a≤180).
  Output For each test case, output a single line contains test case number and the answer HH:MM:SS.   Sample Input 0:59:59 30 01:00:00 30   Sample Output Case #1: 01:00:00 Case #2: 01:10:54

 

题意：

　　给出时间t和角度a，求时间t之后 时针和分针呈a°角的时刻。如果不是整数则向下取整。

题解：

　　我们知道时针每120秒走1°，分针每10秒走1°，既每隔120秒时针分针差11°，我们可以把a扩大11倍  a*=11。

　　所以我们可以从120秒开始枚举。当枚举的时间恰好时针分针差a°且大于时间t的时候得到结果，因为之前乘了11所以结果要除以11。

　　这里我们要注意0≤a≤180，所以当我们算的过程中的度数 b 大于180×11 时，时针和分针的实际度数为360*11-b。

#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
#define ll long long
#define exp 1e-8
using namespace std;
const int N = 2000 +5;
const int INF = 2e9+5;
int dp[N][N]={1,0};
char a[N],b[N],c[N];
int main() {
    int h,m,s,a,cnt=1;
    while (~scanf("%d:%d:%d %d",&h,&m,&s,&a)){
        int t = (h*3600+m*60+s)*11;
        a*=11;
        int b = 0,b1,tt;
        for (tt=120;;tt+=120){
            b+=11;
            b1=b%(360*11);
            if (b1>180*11) {
                b1 = (360*11)-b1;
            }
            if(b1 == a&&tt>t){
                break;
            }
        }
        tt = tt%(3600*12*11); // 避免时间大于12小时
        h = tt / (3600*11);
        m = (tt - h * 3600*11) / (60*11);
        s = (tt - h * 3600*11 - m * 60*11) / 11;
        printf("Case #%d: %02d:%02d:%02d\n",cnt++,h,m,s);
    }
    return 0;
}

View Code

 

 

E.HDU5706GirlCat

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1955    Accepted Submission(s): 1155

Problem Description As a cute girl, Kotori likes playing ``Hide and Seek'' with cats particularly.
Under the influence of Kotori, many girls and cats are playing ``Hide and Seek'' together.
Koroti shots a photo. The size of this photo is n×m, each pixel of the photo is a character of the lowercase(from `a' to `z').
Kotori wants to know how many girls and how many cats are there in the photo.

We define a girl as -- we choose a point as the start, passing by 4 different connected points continuously, and the four characters are exactly ``girl'' in the order.
We define two girls are different if there is at least a point of the two girls are different.
We define a cat as -- we choose a point as the start, passing by 3 different connected points continuously, and the three characters are exactly ``cat'' in the order.
We define two cats are different if there is at least a point of the two cats are different.

Two points are regarded to be connected if and only if they share a common edge.
 

 

Input The first line is an integer T which represents the case number.

As for each case, the first line are two integers n and m, which are the height and the width of the photo.
Then there are n lines followed, and there are m characters of each line, which are the the details of the photo.

It is guaranteed that:
T is about 50.
1≤n≤1000.
1≤m≤1000.
∑(n×m)≤2×106.
  Output As for each case, you need to output a single line.
There should be 2 integers in the line with a blank between them representing the number of girls and cats respectively.

Please make sure that there is no extra blank.

  Sample Input 3 1 4 girl 2 3 oto cat 3 4 girl hrlt hlca   Sample Output 1 0 0 2 4 1

 

题意：

　　找图中有多少个girl和cat。如果连着走4步，是"girl"就是一个girl；如果连着走3步，是"cat"就是一只cat。字符可重复使用，只要有一个字符位置不同就是不同的。

题解：

　　可以用搜索来写，遇到g或c就搜它和它周围的字符能否组成girl或cat。

#include <stdio.h>
#include <string>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
#define ll long long
#define exp 1e-8
using namespace std;
const int N = 1000+5;
const int INF = 0x3f3f3f3f;
int n,m,ans1,ans2;
char s[N][N];
int d[][2]={0,1,1,0,0,-1,-1,0};
char s1[2][5]={"girl","cat"};
bool in(int x,int y){
    return x<n&&x>=0&&y<m&&y>=0;
}
void dfs(int x,int y,int type,int k){
    if (type==0 && k==4){
        ans1++;
        return;
    }else if (type==1 && k==3){
        ans2++;
        return;
    }
    for (int i=0;i<4;i++){
        int xx = x+d[i][0];
        int yy = y+d[i][1];
        if (in(xx,yy)&&s[xx][yy]==s1[type][k]){
            dfs(xx,yy,type,k+1);
        }
    }
}
int main(){
    int T;
    for (scanf("%d",&T);T;T--){
        ans1=ans2=0;
        scanf("%d%d",&n,&m);
        for (int i=0;i<n;i++)
            scanf("%s",s[i]);
        for (int i=0;i<n;i++){
            for (int j = 0;j<m;j++){
                if (s[i][j] == 'g'){
                    dfs(i,j,0,1);
                }else if (s[i][j] == 'c'){
                    dfs(i,j,1,1);
                }
            }
        }
        printf("%d %d\n", ans1,ans2);
    }
    return 0;
}

View Code

 

 

F.HDU5707Combine String

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)
Total Submission(s): 3853    Accepted Submission(s): 1048

Problem Description Given three strings a, b and c, your mission is to check whether c is the combine string of a and b.
A string c is said to be the combine string of a and b if and only if c can be broken into two subsequences, when you read them as a string, one equals to a, and the other equals to b.
For example, ``adebcf'' is a combine string of ``abc'' and ``def''.
 

 

Input Input file contains several test cases (no more than 20). Process to the end of file.
Each test case contains three strings a, b and c (the length of each string is between 1 and 2000).
 

 

Output For each test case, print ``Yes'', if c is a combine string of a and b, otherwise print ``No''.
 

 

Sample Input abc def adebcf abc def abecdf  

 

Sample Output Yes No

 

题意：

　　给你三个串a,b,c。将c拆成两个子序列，问能否正好拆成a,b。

题解：

　　这题贪心显然是不行的。我们可以用DP来写：

　　dp[i][j] 表示 c串前i+j个字符是否和a串的前i项以及b串的前j项匹配。

　　状态转移方程为：

　　　　　　if (i>0) {
  　　　　　　  dp[i][j] |= dp[i-1][j]&(a[i-1]==c[i+j-1]);
　　　　　　}
　　　　　　if (j>0) {
　　　　　　    dp[i][j] |= dp[i][j-1]&(b[j-1]==c[i+j-1]);
　　　　　　}

　　

#include <stdio.h>
#include <string.h>
#include <string>
#include <map>
#include <queue>
#include <iostream>
#include <algorithm>
#define ll long long
#define exp 1e-8
using namespace std;
const int N = 2000 +5;
const int INF = 2e9+5;
int dp[N][N]={1,0};
char a[N],b[N],c[N];
int main() {
    while (~scanf("%s%s%s",a,b,c)){
        int la=strlen(a),lb=strlen(b),lc=strlen(c);
        if (la + lb != lc) {
            printf("No\n");
            continue;
        }
        memset(dp,0,sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0; i <= la; i++) {
            for (int j = 0;j <= lb; j++) {
                if (i) {
                    dp[i][j] |= dp[i-1][j]&(a[i-1]==c[i+j-1]);
                }
                if (j) {
                    dp[i][j] |= dp[i][j-1]&(b[j-1]==c[i+j-1]);
                }
            }
        }
        printf("%s\n",dp[la][lb]?"Yes":"No");
    }
    return 0;
}

View Code

 

待补...