2020.3 月赛题解

oxx1108 edited 4 年，7 月前

致歉

Xiejiadong ：由于出题人和验题人的疏忽。导致 $A$ 的 std 和数据是假的。

花絮

疫情即将过去，愿大家一切安好。

等待着,一个可以肆无忌惮赏樱的日子。

#	Tag	Idea	Developer	Tester
A	-	-	-	-
B	网络流	cs2017 Xiejiadong	cubercsl Kilo_5723	Xiejiadong Weaver_zhu
C	位运算贪心	Xiejiadong	Xiejiadong	cubercsl Weaver_zhu
D	图论树形 dp	oxx1108	cubercsl	Kilo_5723
E	组合数学	Xiejiadong	Xiejiadong	cubercsl Weaver_zhu

Problem A 传播模型

准确的说，std 假了。

应该还是能做的，就是没有这么简单了。可能在不久的将来，会再与大家见面。

Xiejiadong ：没想到吧。这是个假题。我也没想到。

Problem B 迷宫

解法 $1$

考虑二分答案。

我们现在要判断，所有人能否在 $mid$ 天内走出去。

因为道路限制了每天通过的流量，我们不妨拆点，分层建图，把每一个点拆成 $($ 标号，天数 $)$ ，在相邻节点相邻的天数之间连边，然后跑最大流就好了。

解法 $2$

考虑二分答案，即考虑在限定时间内能跑多少人单位流量对答案的贡献为 $T - dis$ 其中 $T$ 是二分的答案，$dis$ 是距离。

我们用费用流的方法逐步增加流量同时使得费用（路程）最短。费用流可以让单位流量总费用最短，而我们也可以表示能走的人为 $T \times f - totcost$，其中 $f$ 是流量，$totcost$ 是总费用，所以逐步增加流量检测每一个可能的流量是否能让所有人都跑掉。

Comments

Weaver_zhu ：我想出了解法 $2$ 觉得挺真，就写了，然后就过了。

Xiejiadong ：想不出来为什么是对的，但是也过了压力测试，就是无法证明正确性，不知道大家有没有证明方法或者能 hack 掉它的数据。

Problem C 与矩阵

肯定要按位考虑。对于一个位置 $(i,j)$ 考虑二进制下的其中一位，如果它所在的行和列中的数在这一位上出现了 $1$ ，那么必然这个数这一位上一定是 $1$ 。

题目要求字典序最小的，那么我们必然会把所有可以为 $0$ 的位置全部设为 $0$ ，也就是它所在的行和列中的数在这一位上没有出现了 $1$ 。

很容易证明，这样的到的一定是最小的。

Problem D 排序树

解法 $1$

首先可以确定的是题目要求是在添加完若干条边后，整个图是 DAG（有向无环图），且拓扑排序唯一确定。

拓扑排序唯一确定的充要条件是对于拓扑排序相邻的两个结点一定有边，或者说存在一条长度为 $n$ 的链（可以用反证法证明），不然的话交互这两个相邻的结点，拓扑序依然成立。

那么问题就转化成了加最少的边保证是 DAG 的前提下，使得存在一条长度为 $n$ 的链。

先看至少需要多少条边。假设加的边都在这条链上，那么就相当于将一些链接起来，而这些链恰好能够 cover 所有点。因此至少需要加的边数就是最小链覆盖的数量。

然后看构造，将树分割成若干条链后可以将每条链缩成一个 supernode ，那么任意两个 supernode 至多只会有一条边（因为缩完之后依然是一棵树）。

那么将 supernode 拓扑排序一下，然后前一个 supernode 的尾接后一个 supernode 的头，那么就可以把所有链串起来了并且保证没有环。（因为加的边都是前指向后，不会出现环）。

最后，就是如何求最小链覆盖了。在 dag 下是个很经典的问题，可以用二分图匹配解决；在树上如果是无向图也是一个很经典的问题。但是这里边是有向的，所以要树形 dp，对于每个顶点考虑两种情况，一种是它的父边切掉，那么它可以连一个向上的儿子和一个向下的儿子。如果不切掉，那么它至多只能连一个与它父边方向相同的儿子。

具体的转移方程自己思考，这边注意还要找到链的起点和终点，所以不是很好写。

解法 $2$

将相邻结点的大小关系看作一条有向边，则我们需要尽可能利用树中已经存在的边，每多利用一条边就意味着可以少添加一条边。在理想情况下，把树分割成最小的单向路径集，使得单向路径既覆盖到每个结点又不共享结点，那么把这些单向路首尾相连就是答案，需要添加最少的单向路径数量 $-1$ 条边。

可以证明，只要能把树分割成单向路径集，就一定能通过将单项路径首尾相连形成链。因为如果将单向路径缩成一个节点，新的图依旧是一棵树，也就一定是有向无环图，只要根据图的拓扑序给前后的结点加边就保证正确。

考虑用 dfs 求出最小的路径集。对于每一条在答案中的路径，我们在其中深度最浅的结点处理它。对于每个结点 $u$，令其父亲是 $f$，考虑 $u$ 属于哪条路径。对于 $u$ 的所有子节点，如果存在 $v,w$ 使得 $v$ 提供 $\cdots \to v \to u$ 的路径，$w$ 提供 $u \to w \to \cdots$ 的路径，那么使用这两条路径， $u$ 在最优解下一定属于 $\cdots \to v \to u \to w \to \cdots$ 的路径。在这种情况下，不需要尝试向父亲提供边。否则如果存在 $v$，使得 $v$ 提供和 $u$ 与 $f$ 之间的边相同方向的路径，则使用这条路径，将 $u$ 与 $f$ 的边加入这条路径并尝提供给 $f$。否则向 $f$ 提供只由 $u$ 到 $f$ 的边构成的路径。所有被提供而未被使用的路径都直接加入路径集。

接下来的问题是如何将路径集的路径拓扑排序。有一个巧妙的方法，在每个节点被加入路径集的时候，根据每条路径深度最浅的节点 $u$ 与其父亲 $f$ 的连边方向，如果是 $f \to u$ 则加到队列 $A$ 的右边，否则加到队列 $B$ 的左边。如果深度最浅的节点是根节点，加到哪边都可以。将 $A$ 的末尾与 $B$ 的开头相连之后会发现，队列中路径的顺序恰好形成树上的拓扑序。

另外，对于每条路径，我们只需要存储它的起始节点和终止节点。

Comments

oxx1108 ：

原来想的是没有树这一限制，后来发现构造那一步会出环。比如这个数据:

答案应该是 $2$ ，但是链的话答案就是 $1$ 了。

对于按拓扑排序的层级顺序排序，然后添加相邻的边的方法，给一个反例：

答案应该是 $1$ ，层级拓扑序的话会加 $1$ $2$ 和 $2$ $3$ 。 * 这题原来准备放校赛的，但是这一场没啥难题就搬过来了。

Problem E 钢琴演奏家

考虑每一个数作为最大数的时候的情况。

如果将给定的值排序以后，每一个数产生贡献的时候，所选取的其他值一定都在他的一侧，可以直接通过组合公式计算出当前值作为最大值时候的贡献。

于是可以得到答案为 $$\sum_{i = m} ^ n a_i {{m - 1} \choose {i - 1}}$$ 。

而对于可能出现相同值的情况，我们可以在排序以后默认左边的数要大于右边（即当我们按下的琴键中有多个最大值的时候，我们认为位置最左边的最小，显然这样处理可以不重不漏）。

20 1

sdibtlly

4 年，7 月前

有没有大佬分享一下e题的ac代码

回复 5 0

SmallY

4 年，7 月前

PyPy3代码

p = 1000000007

def fastExpMod(b, e):
    result = 1
    while e != 0:
        if (e&1) == 1:
            result = (result * b) % p
        e >>= 1
        b = (b*b) % p
    return result

for _ in range(int(input())):
    n, m = map(int, input().split())
    com = [0]*(n+1)
    com[m] = 1
    for i in range(m+1, n+1):
        com[i] = ((i*com[i-1]%p)*fastExpMod(i-m, p-2))%p
    L = [int(i) for i in input().split()]
    L.sort()
    L = [0]+L
    res = 0
    for i in range(n, m-1, -1):
        res = (res+(((com[i]-com[i-1])*L[i])%p))%p
    print(res)

回复 1 0

shwei

4 年，5 月前

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 1e6 + 7, mod = 1e9 + 7;

int a[N];
LL fact[N], infact[N]; // 阶乘数组最好用 long long 来存

// 快速幂
int qmi(int a, int k, int p) {
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % p;
        a = (LL)a * a % p;
        k >>= 1;
    }
    return res;
}

// 预处理阶乘
void init() {
    fact[0] = infact[0] = 1;
    for (int i = 1; i <= N; i++) {
        fact[i] = fact[i - 1] * i % mod;
        infact[i] = infact[i - 1] * qmi(i, mod - 2, mod) % mod;
    }
}

int main() {
    int T;
    cin >> T;

    init();

    while (T --) {
        int n, m;
        cin >> n >> m;

        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }

        sort(a + 1, a + n + 1);

        // 计算组合公式
        int res = 0;
        for (int i = m; i <= n; i ++) {
            int x = i - 1, y = m - 1;
            res = (res % mod + a[i] * 1ll * fact[x] % mod * infact[x - y] % mod * infact[y] % mod) % mod;
        }
        cout << res << endl;
    }

    return 0;
}

回复 1 0

Cascol

4 年，7 月前

求分享+1

回复 0 0

weiyangs

4 年，7 月前

俺也想看看，e题一直卡测试点

回复 0 0

hehaoming

4 年，7 月前

include

using namespace std;
typedef long long LL;
const LL N = 1000000007;
const int maxn = 1000000 + 10;
LL a[maxn];
LL fac[maxn];//乘阶表
LL FAC_K;
LL power(LL a, LL b) {//快速幂
a %= N;
LL ans = 1;
while (b) {
if (b & 1)ans = (ans * a) % N;
b >>= 1;
a = (a * a) % N;
}
return ans;
}
LL inv(LL a) {//返回逆元（费马小定理）
return power(a, N - 2L) % N;
}
void solve(int n) {//计算乘阶表
fac[0] = 1;
for (int i = 1; i <= n; i++) {
fac[i] = (fac[i - 1] * i) % N;
}
}
LL comb(int n, int k) {//返回组合数（组合数公式）
if (k > n)return 0;
return ((fac[n] * FAC_K)% N * (inv(fac[n - k]) % N)) % N;
}

int main() {
int t;
scanf(“%d”, &t);
for (int i = 0; i < t; i++) {
int n, m;
scanf(“%d %d”, &n, &m);
for (int j = 0; j < n; j++) {
scanf(“%lld”, &a[j]);

    }
    sort(a, a + n);
    solve(n);
    int require = m - 1;
    FAC_K = inv(fac[require]);
    long sum = 0;
    for (int p = require; p < n; p++) {
        sum = (sum % N + ((a[p] * comb(p, require)) % N)) % N;
    }
    sum %= N;
    cout << sum << endl;
}
return 0;