跳转至

Frozen Standing

题意

赛场上有 n 名选手，其中第 i 名在封榜前做出了 x_i 道题。在封榜期间一名选手最多再多做出一题，也就是说选手最终做出了 x_i 或 x_i+1 道题。

所有选手按做出的题数排名；如果题数相同则编号小的排在前面。求选手最终一共可能有多少种不同的排名？

解析

原题可以转化为：有 n 个区间 [l_i,l_i+L]，且 l_i 互不相同，每个区间的权值在 l_i 和 l_i+L 中选择，求最终一共有多少种不同的排名。

我们规定一个合法的选择是：不存在一个区间的权值为 l_i+L 且将这个区间的权值改为 l_i 时排名不变。这样，所有合法的选择和所有可能的不同排名都一一对应了。

证明

显然每个可能出现的排名都对应至少一种合法选择，而每种合法选择都对应恰好一个排名。因此我们只需要证明任意两个不同的合法选择都对应不同的排名。

设排名为 i 的区间的编号为 p_i。若有两个不同的合法选择对应同一种排名，则取最小的满足编号为 p_j 的区间在两种选择中的权值不同的 j。对于选择 l_{p_j}+L 的那个选择，将 p_j 的权值改为 l_{p_j} 也仍然对应相同的排名，故其不是一个合法的选择。故不存在两个合法选择对应同样的排名。

因此，我们在合法的选择和排名之间建立了双射关系。合法的选择的数量就是可能出现的排名的数量。

考虑怎样的选择不是合法的。我们把所有区间从左到右编号为 1 至 n，则第 i 个区间从选 l_i+L 变为选 l_i 时排名不变，当且仅当所有比 i 小且与 i 相交的区间 j 都选择 l_j，所有比 i 大且与 i 相交的区间 k 都选择 l_k+L。这一点很好理解，因为所有区间长度相等，如果存在一个在 i 左边且与 i 相交的区间 j 选了 l_i+L，则有 l_i<l_j+L<l_i+L，l_i 和 l_i+L 会导向不同的排名。

那么，设 A_i 表示最左的与 i 相交的区间的编号，B_i 表示最右的与 i 相交的区间的编号，则 A_i\sim i-1 都选择 l，i\sim B_i 都选择 l+L 的情况是不合法的。我们利用补集转化，去除这些限制情况即可。

设 dp_i 表示所有满足 B_j\le i 的 [A_j,B_j] 限制的合法选择数。则

dp_i=2dp_{i-1}-\sum_{j\le i\land B_j=i}dp_{A_j-1}

其中，2dp_{i-1} 表示第 i 个区间既可以选 l，也可以选 l+L；dp_{A_j-1} 表示去除掉 j 区间不合法的情况。由于 2dp_{i-1} 代表的所有情况中 [A_j,B_j=i] 都恰好不满足限制一次，且这些不满足限制的情况相互不交，所以这样计数是不重不漏的。

这个 DP 可以 O(n) 转移。

实现

#include <bits/stdc++.h>

typedef long long int ll;
const int mod = 1e9 + 7, maxn = 5e5 + 19;

struct Edge{
    int to, next;
}edge[maxn];

int head[maxn];

inline void add(int from, int to){
    edge[++head[0]] = (Edge){to, head[from]};
    head[from] = head[0];
}

struct range{
    ll l, r;
    bool operator<(const range &b)const{return l < b.l; }
}p[maxn];

int X[maxn], dp[maxn];

class FrozenStandings{
public:
    int countStandings(int N, int A, int seed){
        ll x = seed;
        for(int i = 1; i <= N; ++i){
            x = x * 20142014 % mod;
            X[i] = x % A;
        }
        for(int i = 1; i <= N; ++i)
            p[i].l = (ll)X[i] * N + (N - i), p[i].r = (ll)X[i] * N + (N - i) + N;
        std::sort(p + 1, p + 1 + N);
        for(int i = 1, a = 1, b = 1; i <= N; ++i){
            while(b + 1 <= N && p[b + 1].l < p[i].r) ++b;
            while(p[a].r < p[i].l) ++a;
            add(b, a);
        }
        dp[0] = 1;
        for(int i = 1; i <= N; ++i){
            dp[i] = 2ll * dp[i - 1] % mod;
            for(int j = head[i]; j; j = edge[j].next)
                dp[i] = (dp[i] - dp[edge[j].to - 1]) % mod;
        }
        return (dp[N] + mod) % mod;
    }
};

来源

2014 TCO Algorithm Finals - Division I, Level Three

评论