生活随笔
收集整理的這篇文章主要介紹了
201612-5 卡牌游戏
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
**根據(jù)題目樣例解釋得到每種卡牌擁有狀態(tài)之間的關(guān)系，然后轉(zhuǎn)換成等式，高斯消元是2^(3n) **
80分超時(shí)代碼：
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <queue>
#define ls (u<<1)
#define rs (u<<1|1)
#define mid (l+r>>1)
using namespace std
;
typedef long long LL
;
typedef pair
<int,int> PII
;
const int N
= 13, mod
= 1e9 + 7;double p
[20][20];
double s
[1<<N
][1<<N
];
int n
, m
;
int gauss(double a
[][1<<N
], int n
) {
const double eps
= 1e-6; int c
, r
;for (c
= 0, r
= 0; c
< n
; ++c
) { int t
= r
;for (int i
= r
; i
< n
; ++i
) if (fabs(a
[i
][c
]) > fabs(a
[t
][c
]))t
= i
;if (fabs(a
[t
][c
]) < eps
) continue; for (int i
= c
; i
< n
+ 1; ++i
) swap(a
[t
][i
], a
[r
][i
]);for (int i
= n
; i
>= c
; --i
) a
[r
][i
] /= a
[r
][c
];for (int i
= r
+ 1; i
< n
; ++i
)if (fabs(a
[i
][c
]) > eps
)for (int j
= n
; j
>= c
; --j
)a
[i
][j
] -= a
[r
][j
] * a
[i
][c
];++r
;}if (r
< n
) {for (int i
= r
; i
< n
; ++i
)if (fabs(a
[i
][n
]) > eps
) return 2;return 1; }for (int i
= n
- 1; i
>= 0; --i
)for (int j
= i
+ 1; j
< n
; ++j
)a
[i
][n
] -= a
[j
][n
] * a
[i
][j
];return 0;
}void calc(int x
)
{vector
<pair
<int,double> >a
, b
;a
.clear(); b
.clear();;for(int i
= 0;i
< n
;i
++)if(x
>>i
&1)a
.push_back({i
, 0});else b
.push_back({i
, 0});double l
= 0, r
= 0;for(int i
= 0;i
< a
.size();i
++)for(int j
= 0;j
< b
.size();j
++){int x
= a
[i
].first
, y
= b
[j
].first
;l
+= p
[x
][y
]; r
+= p
[y
][x
]; a
[i
].second
+= p
[x
][y
];b
[j
].second
+= p
[y
][x
];}for(int i
= 0;i
< a
.size();i
++)for(int j
= 0;j
< b
.size();j
++){int z
= a
[i
].first
, y
= b
[j
].first
;s
[x
][x
^1<<z
] -= p
[y
][z
]*a
[i
].second
*b
[j
].second
/l
/r
;s
[x
][x
|1<<y
] -= p
[z
][y
]*a
[i
].second
*b
[j
].second
/l
/r
;}s
[x
][x
] = 1;
}int main()
{scanf("%d%d", &n
, &m
);for(int i
= 0;i
< n
;i
++)for(int j
= i
+1;j
< n
;j
++)scanf("%lf", p
[i
]+j
), p
[j
][i
] = 1-p
[i
][j
];s
[(1<<n
)-1][1<<n
] = 1;for(int i
= 0;i
< 1<<n
;i
++)calc(i
);gauss(s
, 1<<n
);while(m
--){int x
= 0;for(int i
= 0, j
;i
< n
;i
++)scanf("%d", &j
) ,j
?x
|= 1<<i
:0;printf("%.5lf\n", s
[x
][1<<n
]);}return 0;
}
總結(jié)
以上是生活随笔為你收集整理的201612-5 卡牌游戏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。
