比赛 组合计数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;
}