Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

有点像线段树?(雾)因为没清空变量wa了两次。。

Posted by chrono_chasm at 2022-02-17 16:24:10 on Problem 3071
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int lim = 1 << 8;
double p[lim][lim];
double wins[lim][8];  // wins[i][k] 第i+1队在倒数第k次比赛中存活概率
void dfs(int l, int r, int dep) {  // 有点像线段树?
    if (l + 1 == r) return (void)(wins[l][dep] = 1);
    int mid = (l + r) >> 1;
    dfs(l, mid, dep + 1);
    dfs(mid, r, dep + 1);
    for (int i = l; i < mid; ++i) {
        wins[i][dep] = 0;
        for (int j = mid; j < r; ++j)
            wins[i][dep] += wins[i][dep + 1] * p[i][j] * wins[j][dep + 1];
    }
    for (int i = mid; i < r; ++i) {
        wins[i][dep] = 0;
        for (int j = l; j < mid; ++j)
            wins[i][dep] += wins[i][dep + 1] * p[i][j] * wins[j][dep + 1];
    }
}
int main() {
    int n;
    while (scanf("%d", &n), ~n) {
        for (int i = 0; i < (1 << n); ++i)
            for (int j = 0; j < (1 << n); ++j) scanf("%lf", p[i] + j);
        dfs(0, (1 << n), 0);
        int pos = 0;
        for (int i = 1; i < (1 << n); ++i)
            if (wins[i][0] > wins[pos][0]) pos = i;
        printf("%d\n", pos + 1);
    }
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator