「2019纪中集训Day15」解题报告

T1、投票

(n (n leq 2000)) 个事件，第 (i) 件事发生的概率为 (p_i)，选出 (k (k leq 2000, 2 | k)) 件事，求使得发生与不发生的事件数量相同的最大概率；
精度误差需保证在 (10^{-6}) 以内。

(Sol)：

一定是选按概率排好序的一段前缀和一段后缀比较优秀，这一点并不显然。
(prf)：
假定现在已经确定了 (k - 1) 个事件，未确定的事件设为 (x)；
那么概率为：

[sum_{for all situation} Big[ p_x cdot prod_{i = 1} ^ {frac{k}{2} - 1} p_{a_i} cdot prod_{j = 1} ^ {frac{k}{2}}(1 - p_{b_j}) + (1 - p_x) cdot prod_{i = 1} ^ {frac{k}{2}} p_{b_i} cdot prod_{j = 1} ^ {frac{k}{2} - 1}(1 - p_{a_j})Big] , { a_i } igcap { b_i } = varnothing ]

这是一个关于 (p_x) 的一次幂函数，所以一定是取能取到的最大或最小值比较优。
(Q.E.D.)

先将概率从小到大排序；
记 (f_{i,j}) 表示前 (i) 件事恰好发生 (j) 件的概率，转移是显然的；
记一个前缀和一个后缀的 (dp)，再枚举一边选择了多少人，求出概率取最大即可。

(Source)：

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <algorithm>
typedef double db;
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }

const int N = 2e3 + 5;
int n, m;
db pre[N][N], suf[N][N], p[N], res;

int main() {
    //freopen("in", "r", stdin);
    freopen("vote.in", "r", stdin);
    freopen("vote.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; ++i)
        scanf("%lf", &p[i]);
    std::sort(p + 1, p + 1 + n);
    pre[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
        pre[i][0] = pre[i - 1][0] * (1 - p[i]);
        for (int j = 1; j <= i; ++j)
            pre[i][j] = pre[i - 1][j - 1] * p[i] + pre[i - 1][j] * (1 - p[i]);
    }
    std::reverse(p + 1, p + 1 + n);
    suf[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
        suf[i][0] = suf[i - 1][0] * (1 - p[i]);
        for (int j = 1; j <= i; ++j)
            suf[i][j] = suf[i - 1][j - 1] * p[i] + suf[i - 1][j] * (1 - p[i]);
    }
    for (int i = 0; i <= m; ++i) {
        db tmp = 0;
        for (int j = std::max(0, m / 2 - (m - i)); j <= i && j <= m / 2; ++j)
            tmp += pre[i][j] * suf[m - i][m / 2 - j];
        chk_max(res, tmp);
    }
    printf("%.7lf
", res);
    return 0;
}

T2、动态数点

给定一个长度为 (n (n leq 5 imes 10 ^ 5)) 的序列 ({ a_i } (a_i leq 2 ^ {32} - 1))，如果对于一个区间 ([l, r])，存在 (k in [l, r]) 使得 (forall i in [l,r] a_k | a_i)，那么它有 (r - l) 的价值，求最大价值。

(Sol)：

(gcd) 的 (log) 比较小，直接 (st) 表可过。
时间复杂度 (O(n log_2 n log_2a_i))。

对于两个区间里可以作为除数的数 (a_x, a_y (x e y))；
若 (a_x = a_y)，他们一定会被包含在同一个区间；
否则包含其中一个点的区间不会包含另一个点，很容易证明这两点。

所以从左到右枚举除数 (a_i)，向左右扩展，找到包含它的极大区间 ([l, r])，更新答案，并把除数设为 (a_{r + 1}) 即可；
根据上述引理，(l) 一定在上一个除数的位置的右边，所以每个点只会被算到两次。

时间复杂度 (O(n))。

(Source)：

#include <cstdio>
#include <cstring>
#include <algorithm>
unsigned in() {
    unsigned x = 0; char c = getchar();
    while (c < '0' || c > '9')
        c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }

const int N = 5e5 + 5;

unsigned n, a[N], res[N];

int main() {
    //freopen("in", "r", stdin);
    freopen("point.in", "r", stdin);
    freopen("point.out", "w", stdout);
    n = in();
    for (unsigned i = 1; i <= n; ++i)
        a[i] = in();

    unsigned max = 0, num = 0, tmp;
    for (unsigned i = 1, l, r; i <= n; i = r + 1) {
        l = r = i;
        while (r < n && a[r + 1] % a[i] == 0)
            ++r;
        while (l > 1 && a[l - 1] % a[i] == 0)
            --l;
        tmp = r - l;
        if (tmp == max)
            res[++num] = l;
        if (tmp > max)
            max = tmp, res[num = 1] = l;
    }

    printf("%u %u
", num, max);
    for (unsigned i = 1; i <= num; ++i)
        printf("%u ", res[i]);
    puts("");
    return 0;
}

T3、演员

一道让我咕博客的题，然而理解后也咕了很久十分简单。
老虎蒜头神仙题。
给 (m (m leq 300)) 个演员排 (n (n leq 10 ^ 6)) 天班；
每次选择一个演员，并选择区间 ([l, r])，给他安排 ([l,r]) 里没有还被分配给其他演员的天；
每天都要被分配，演员可以不被安排，求分配方案数，对 (10 ^ 9 + 7) 取模。

(Sol)：

显然可以发现，两个演员被安排的天一定不存在相交但不包含的情况；
那么按时间顺序来看正在工作的演员，可以把它看成一个栈，工作的演员在栈顶；
可以 (dp)，记 (f_{i,j,k}) 表示前 (i) 天，已经有 (j) 个演员入过栈，栈里还有 (k) 个人的方案数，转移是显然的，不再赘述。

由于 (n) 很大，这样显然不行，但是注意到时间被不同演员分成了最多 (2m - 1) 段；
可以把第一维状态改为上述时间段，对每个状态组合数计算贡献即可。

时间复杂度 (O(m ^ 3))。

(Source)：

//#pragma GCC optimize(3,"Ofast","inline")
#include <cstdio>
#include <cstring>
#include <algorithm>
int in() {
    int x = 0; char c = getchar(); bool f = 0;
    while (c < '0' || c > '9')
        f |= c == '-', c = getchar();
    while (c >= '0' && c <= '9')
        x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return f ? -x : x;
}
template<typename T>inline void chk_min(T &_, T __) { _ = _ < __ ? _ : __; }
template<typename T>inline void chk_max(T &_, T __) { _ = _ > __ ? _ : __; }

const int M = 305, mod = 1e9 + 7;

int n, m, res;
int fac[N], inv[N], f[M + M][M][M];

inline void add(int &_, int __) {
    _ += __;
    if (_ >= mod)
        _ -= mod;
}

int qpow(int base, int b, int ret = 1) {
    for (; b; b >>= 1, base = 1ll * base * base % mod)
        if (b & 1)
            ret = 1ll * ret * base % mod;
    return ret;
}

void prep() {
    int nn = std::max(n, m);
    fac[0] = inv[0] = 1;
    for (int i = 1; i <= nn; ++i)
        fac[i] = 1ll * fac[i - 1] * i % mod;
    inv[nn] = qpow(fac[nn], mod - 2);
    for (int i = nn - 1; i; --i)
        inv[i] = 1ll * inv[i + 1] * (i + 1) % mod;
}

inline int C(const int n, const int m) {
    return 1ll * fac[n] * inv[m] % mod * inv[n - m] % mod;
}
inline int A(const int n, const int m) {
    return 1ll * fac[n] * inv[n - m] % mod;
}

int main() {
    //freopen("in", "r", stdin);
    freopen("actor.in", "r", stdin);
    freopen("actor.out", "w", stdout);
    n = in(), m = in();
    prep();
    f[0][0][0] = 1;
    for (int i = 1; i <= n && i <= m + m; ++i) {
        for (int j = 1; j <= m; ++j)
            for (int k = j, sum = 0, tmp; k; --k) {
                tmp = f[i - 1][j - 1][k - 1]; add(tmp, sum);
                add(f[i][j][k], tmp);
                add(sum, f[i - 1][j][k]);
                add(res, 1ll * A(m, j) * C(n - 1, i - 1) % mod * f[i][j][k] % mod);
            }
    }
    printf("%d
", res);
    return 0;
}