### 第8届浙江省程序设计竞赛点评beta » ZOJ3493

ZOJ3493.cpp

```#include <cmath>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <algorithm>

using namespace std;

struct People {
string name;
double u, d;
double r, p, s;

static int t;
assert(scanf("%d", &t) == 1);
assert(0 <= t && t <= 100);
return t;
}

static char buf[80];
assert(scanf("%s", buf) == 1);
name = buf;
assert(name.length() <= 20);
for (string::const_iterator c = name.begin(); c != name.end(); ++c) {
assert(isalpha(*c));
}

static double t;
t = u + d;
assert(t > 0);
u /= t;
d /= t;

t = r + p + s;
assert(t > 0);
r /= t;
p /= t;
s /= t;
}
} info[32];

const int MAXN = 13;
const double EPS = 1e-8;

double lose[MAXN][MAXN];
double u[1 << MAXN], d[1 << MAXN], dp[1 << MAXN];
double popcnt[1 << MAXN], ctz[1 << MAXN];

void init() {
for (int i = 0; i < (1 << MAXN); ++i) {
popcnt[i] = __builtin_popcount(i);
ctz[i] = __builtin_ctz(i);
}
}

int main() {
int re, n;
double ans;

init();
scanf("%d", &re);
for (int ri = 1; ri <= re; ++ri) {
scanf("%d", &n);
assert(1 <= n && n <= 13);
for (int i = 0; i < n; ++i) {
}

u[0] = d[0] = 1;
for (int i = 1; i < (1 << n); ++i) {
int z = ctz[i];
u[i] = u[i ^ (1 << z)] * info[z].u;
d[i] = d[i ^ (1 << z)] * info[z].d;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
lose[i][j] = info[i].r * info[j].p + info[i].p * info[j].s + info[i].s * info[j].r;
}
}

//
for (int i = 1; i < (1 << n); ++i) {
if (popcnt[i] == 1) {
dp[i] = 0;
} else if (popcnt[i] == 2) {
int x = ctz[i];
int y = ctz[i ^ (1 << x)];
dp[i] = 1 / (lose[x][y] + lose[y][x]);
} else {
double x = 0;
double y = 1;
for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
int k = i ^ j;
if (popcnt[j] != popcnt[k] && u[j] > 0 && d[k] > 0) {
x += u[j] * d[k];
y += u[j] * d[k] * dp[popcnt[j] < popcnt[k] ? j : k];
}
}
dp[i] = y / x;
}
//	printf("%d = %lf\n", i, dp[i]);
assert(!isnan(dp[i]));
}
if (isinf(dp[(1 << n) - 1])) {
printf("Infinity ");
} else {
printf("%.3lf ", dp[(1 << n) - 1]);
}

//
ans = 0;
fill(dp, dp + (1 << n), 0);
dp[(1 << n) - 1] = 1;
for (int i = (1 << n) - 1; i > 0; --i) {
if (dp[i] == 0) {
continue;
}
if (popcnt[i] == 1) {
ans = max(ans, dp[i]);
} else if (popcnt[i] == 2) {
int x = ctz[i];
int y = ctz[i ^ (1 << x)];
if (lose[x][y] + lose[y][x] > 0) {
dp[1 << x] += lose[x][y] / (lose[x][y] + lose[y][x]) * dp[i];
dp[1 << y] += lose[y][x] / (lose[x][y] + lose[y][x]) * dp[i];
}
} else {
double x = 0;
for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
int k = i ^ j;
if (popcnt[j] != popcnt[k] && u[j] > 0 && d[k] > 0) {
x += u[j] * d[k];
}
}
if (x == 0) {
continue;
}
for (int j = (i - 1) & i; j > 0; j = (j - 1) & i) {
int k = i ^ j;
if (popcnt[j] != popcnt[k] && u[j] > 0 && d[k] > 0) {
dp[popcnt[j] < popcnt[k] ? j : k] += u[j] * d[k] / x * dp[i];
}
}
}
//	printf("%d = %lf\n", i, dp[i]);
assert(isfinite(dp[i]));
}
printf("%.3lf%%\n", 100 * ans);

vector<string> lst;
for (int i = 0; i < n; ++i) {
if (fabs(dp[1 << i] - ans) < EPS) {
lst.push_back(info[i].name);
}
}
sort(lst.begin(), lst.end());
for (int i = 0; i < (int)lst.size(); ++i) {
printf("%s%c", lst[i].c_str(), i == (int)lst.size() - 1 ? '\n' : ' ');
}
}
assert(scanf("%d", &re) == EOF);

return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//472 	2011-04-15 01:47:37 	Accepted 	G 	C++ 	980 	500 	watashi 	Source

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//2 	2011-04-15 23:03:51 	Accepted 	G 	C++ 	740 	504 	watashi@ArcOfDream 	Source
```
2 Responses to “ZOJ3493”
1. suchen says:

Palm Up and Palm Down这道题目我一直在WA，不知道哪里出现问题。能不能把这题目数据给我让我本地测试。我是BJTU现役队员，如果你来我们OJ做题遇到问题，我愿意给你提供测试数据。实在是WA得不行了，感激不尽。

• watashi says:

很抱歉，我们对内对外都不提供测试数据
你可以拿上面的程序去对拍，可以自己造一些n=5/7的数据，然后程序里assert一下没有inf/nan，最后还有n=1的数据……

2.