Posts Tagged ‘方程’

POJ 3028 Shoot-out

Posted in PKU OJ on 四月 27th, 2010 by 纳米 – 1 Comment

2010-04-24，阅读题目、解题报告
2010-04-26，与老师讨论，阅读标程，Code，Debug
2010-04-27，提交，AC。本地搞到数据测用600ms，记得比POJ快的，于是想能进1000ms就不错了（因为另一份用解方程方法解决环的程序说用了2000ms），结果提交，250ms。我记得我阅读题目的时候最快的是3xxms，莫非……一看，果然刷了个第一。为了庆祝一下，写一份详细的解题报告。

（用文档写，稍后上传PDF）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

#include <stdio.h>
#include <string.h>
 
const int pow[] = {1<<0, 1<<1, 1<<2, 1<<3, 1<<4, 1<<5, 1<<6, 1<<7, 1<<8, 1<<9, 1<<10, 1<<11, 1<<12, 1<<13};
const int maxn = 13;
int Statu[maxn + 1][1 << maxn][maxn], StatuSize[maxn][1 << maxn], Next[maxn+1][1 << maxn][maxn];
int n;
double p[maxn], dp[maxn][1 << maxn][maxn];
 
int init() {
	memset(StatuSize, 0, sizeof(StatuSize));
	for (int i = 1; i <= maxn; ++i)
		for (int s = 1; s < pow[i]; ++s)
			for (int j = 0; j < i; ++j)
				if (s & pow[j])
					Statu[i][s][StatuSize[i][s]++] = j;
	for (int i = 1; i <= maxn; ++i)
		for (int s = 1, jj, j; s < pow[i]; ++s) {
			for (jj = 0, j = Statu[i][s][0]; jj < StatuSize[i][s]-1; j = Statu[i][s][++jj])
				Next[i][s][j] = Statu[i][s][jj+1];
			Next[i][s][j] = Statu[i][s][0];
		}
	return 0;
}
 
int input() {
	scanf("%d", &n);
	for (int i = 0; i < n; ++i) {
		scanf("%lf", &p[i]);
		p[i] /= 100;
	}
	return 0;
}
 
void calc_root(double *root[], double cf1[], double cf2[], int n) {
	double cf1x = cf1[0], cf2x = cf2[0];
	for (int i = 1; i < n; ++i) {
		cf2x += cf1x * cf2[i];
		cf1x *= cf1[i];
	}
	if (1-1e-12 < cf1x && cf1x < 1+1e-12)
		*root[0] = 1;
	else
		*root[0] = cf2x / (1 - cf1x);
	for (int i = n-1; i > 0; --i)
		*root[i] = cf2[i] + cf1[i] * *root[i+1 < n ? i+1 : 0];
}
 
int work() {
	for (int s = 1; s < pow[n]; ++s) {
		double hit[maxn][maxn];
		for (int ii = 0, i = Statu[n][s][0]; ii < StatuSize[n][s]; i = Statu[n][s][++ii]) {
			double px = 0, px0;
			int t[maxn], ts[maxn], ps = 0, ns;
			for (int jj = 0, j = Statu[n][s][0]; jj < StatuSize[n][s]; j = Statu[n][s][++jj]) {
				ns = s - pow[j];
				px0 = i != j ? dp[i][ns][Next[n][ns][i]] : -1;
				if (px - 1e-12 < px0 && px0 < px + 1e-12) {
					t[++ps] = j;
					ts[ps] = ns;
				} else if (px0 > px + 1e-12) {
					px = px0;
					t[ps=1] = j;
					ts[ps] = ns;
				}
			}
			for (int jj = 0, j = Statu[n][s][0]; jj < StatuSize[n][s]; j = Statu[n][s][++jj]) {
				hit[i][j] = 0;
				for (int k = 1; k <= ps; ++k)
					hit[i][j] += pow[j] & ts[k] ? dp[j][ts[k]][Next[n][ts[k]][i]] : 0;
				if (ps)
					hit[i][j] *= p[i] / ps;
				else
					hit[i][j] = p[i];
			}
		}
		for (int ii = 0, i = Statu[n][s][0]; ii < StatuSize[n][s]; i = Statu[n][s][++ii]) {
			double * root[maxn], cf1[maxn], cf2[maxn];
			int k = 0;
			for (int jj = 0, j = Statu[n][s][0]; jj < StatuSize[n][s]; j = Statu[n][s][++jj]) {
				root[k] = &dp[i][s][j];
				cf1[k] = 1 - p[j];
				cf2[k++] = hit[j][i];
			}
			calc_root(root, cf1, cf2, k);
		}
	}
	return 0;
}
 
int output() {
	for (int i = 0; i < n-1; ++i)
		printf("%.2f ", dp[i][pow[n]-1][0] * 100);
	printf("%.2f\n", dp[n-1][pow[n]-1][0] * 100);
	return 0;
}
 
int main() {
	init();
	int Cases;
	scanf("%d", &Cases);
	while (Cases--) {
		input();
		work();
		output();
	}
	return 0;
}