| 比赛 |
组合计数1 |
评测结果 |
AWWTTTTTTT |
| 题目名称 |
按位或 |
最终得分 |
10 |
| 用户昵称 |
对立猫猫对立 |
运行时间 |
9.560 s |
| 代码语言 |
C++ |
内存使用 |
18.91 MiB |
| 提交时间 |
2026-02-26 09:41:06 |
显示代码纯文本
#include <bits/stdc++.h>
#define lowbit(x) (x & (-x))
using namespace std;
int n, limit = 0;
double ansp, res;
time_t start;
double p[1 << 20];
bool exist[50], temp[50];
bool near(int x) {
int diff = 0;
while(x) {
temp[(int)log2(lowbit(x))] = 1;
x -= lowbit(x);
}
for(int i = 1; i < 50; i++) if(exist[i] != temp[i]) diff++;
return diff;
}
struct number {
int x;
double hs = 1.0;
int idx;
bool operator<(const number t) const {
return near(x) < near(t.x);
}
};
void astar(int s) {
priority_queue<number> pq;
pq.push({s, 1.0, 0});
while(!pq.empty()) {
number t = pq.top();
pq.pop();
if(t.idx > limit) continue;
if(t.x == (1 << n) - 1) ansp += t.hs;
if(double(clock() - start) / CLOCKS_PER_SEC > 0.9) return;
for(int i = 0; i < (1 << n); i++) {
number nxt;
nxt.x = t.x | i;
nxt.hs = t.hs * p[i];
nxt.idx = t.idx + 1;
if(nxt.x == t.x && nxt.hs < 0.000001) continue;
pq.push(nxt);
}
}
}
int main() {
freopen("haoi2015_set.in", "r", stdin);
freopen("haoi2015_set.out", "w", stdout);
cin >> n;
int ans = (1 << n) - 1;
while(ans) {
exist[(int)log2(lowbit(ans))] = 1;
ans -= lowbit(ans);
}
for(int i = 0; i < (1 << n); i++) cin >> p[i];
start = clock();
for(limit = 1; limit <= n; limit++) {
astar(0);
res += limit * ansp;
if(double(clock() - start) / CLOCKS_PER_SEC > 0.9) break;
}
if(res < 0.00000001) cout << "INF" << endl;
else cout << res << endl;
}