首页 > ACM题库 > HDU-杭电 > HDU 4437-swap[解题报告]HOJ
2015
07-16

HDU 4437-swap[解题报告]HOJ

swap

问题描述 :

There’s a matrix of n rows and m columns whose elements are either 0 or 1.
If an element is 0, it is located at the i-th row and j-th column, there is at least one 1 is located at the i-th row and k-th (k < j) column, and at least one 1 is located at the i-th row and r-th(r > j) column, this element is called Cup.
You can swap any two rows and any two columns of the matrix. You can do this infinite times, to minimize the number of Cups.

输入:

Multiple test cases (no more than 50), ended with EOF.
The 1st line of each test case contains two integers n and m (3 ≤ n ≤ 10, 3 ≤ m ≤ 25), the number of rows and the number of columns of the matrix.
Then following n lines, each line has m space-separated 0 or 1, indicating the original configuration of the matrix.

输出:

Multiple test cases (no more than 50), ended with EOF.
The 1st line of each test case contains two integers n and m (3 ≤ n ≤ 10, 3 ≤ m ≤ 25), the number of rows and the number of columns of the matrix.
Then following n lines, each line has m space-separated 0 or 1, indicating the original configuration of the matrix.

样例输入:

3 3
1 1 0
1 0 1
0 1 1

样例输出:

1

H. Hunters

1000ms
1000ms
32768KB
64-bit integer IO format: %I64d      Java class name: Main
Font Size:
Alice and Bob are the topmost hunters in the forest, so no preys can escape from them. However, they both think that its hunting skill is better than the other. So they need a match.
In their match, the
targets are two animals, a tiger and a wolf. They both know that the
tiger is living in the south of the forest and the wolf is living in the
north of the forest. They decide that the one who kills the tiger
scores X points and who kills the wolf scores Y points. If the one who
kills both tiger and wolf scores X+Y points.
Before the match starts,
Alice is in the east of the forest and Bob is in the west of the
forest. When the match starts, Alice and Bob will choose one of the
preys as targets. Because they haven’t known the other’s choice, maybe
they choose the same target. There will be two situations:
(1) If they choose different targets, they both are sure of killing their respective targets.
(2)
If they choose the same target, the probability of Alice killing the
target is P, and the probability of Bob killing it is 1-P. Then they
will hunt for the other prey, also the probability of Alice killing it
is P and the probability of Bob killing it is 1-P.
But Alice knows
about Bob. She knows that the probability of Bob choosing tiger as his
first target is Q, and the probability of choosing wolf is 1-Q. So that
Alice can decide her first target to make her expected score as high as
possible.

Input

The first line of input contains an integer T (1≤T≤10000), the number of test cases.
Then
T test cases follow. Each test case contains X, Y, P, Q in one line. X
and Y are integers and 1≤X, Y≤1000000000. P and Q are decimals and 0≤P,
Q≤1, and there are at most two digits after decimal point.

Output

For each test case, output the target Alice should choose and the
highest expected score she can get, in one line, separated by a space.
The expected score should be rounded to the fourth digit after decimal
point. It is guaranteed that Alice will have different expected score
between choosing tiger and wolf.

Sample Input

3
2 1 0.5 0.5
2 1 0 1
7 7 0.32 0.16

Sample Output

tiger 1.7500
wolf 1.0000
tiger 6.5968
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<vector>
#include<cstdlib>
#include<algorithm>

using namespace std;

#define LL long long
#define ULL unsigned long long
#define UINT unsigned int
#define MAX_INT 0x7fffffff
#define MAX_LL 0x7fffffffffffffff
#define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
#define MIN(X,Y) ((X) < (Y) ? (X) : (Y))

double p,q;
int x,y;

int main(){
//  freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);

    int t;
    scanf(" %d",&t);
    while(t--){
        scanf(" %d %d %lf %lf",&x,&y,&p,&q);
        double ma1=q*(p*x + p*y)+(1-q)*x;

        double ma2=(1-q)*(p*y+p*x)+q*y;
        if(ma1>ma2){
            printf("tiger %.4f\n",ma1);
        }
        else printf("wolf %.4f\n",ma2);
    }

    return 0;
}

 

参考:http://www.cnblogs.com/ramanujan/archive/2013/11/07/3412888.html