百度 秋招 2023.10.10 编程题目与题解

1、小红的精灵

小红有 $n$ 个精灵，精灵分布在 $m$ 个房间中，第 $i$ 个精灵可以施展 $a_i$ 次魔法，现在有 $k$ 个敌人要攻击，每次攻击需要一个房间的精灵都消耗一次魔法，该次攻击可以击杀一个敌人。问小红最多可以消灭多少敌人。

输入

一行三个整数 $n,m,k$，分别表示精灵数量，房间数量，敌人数量。

接下来 $n$ 行，每行两个整数，第 $i$ 行表示第 $i$ 个精灵的所在房间编号 $b_i$ 和可以施展的魔法次数 $a_i$。

• $1\le n,m\le {10}^5$
• $1\le b_i\le m$
• $1\le a_i,k\le {10}^6$

输出

输出一个整数，表示最多可以消灭的敌人数量。

样例

输入：
4 5 12
2 4
5 2
3 6
2 3

输出：
11

提示：
有12个敌人，第二个房间可以消灭3个敌人，第三个房间可以消灭6个敌人，第五个房间可以消灭2个敌人。总共可以消灭11个敌人。

解答

如果第 $i$ 个房间没有精灵，那么第 $i$ 个房间并没有用处。如果第 $i$ 个房间有精灵，那么这个房间可以击败的敌人数为 $c_i={\displaystyle \underset{1\le j\le n,b_j=i}{min}\{a_j\}}$。

最终把 $c_i$ 的值进行求和即可，并和 $k$ 取较小值。如果第 $i$ 个房间没有精灵，那么令 $c_i=0$。

代码

n, m, k = map(int, input().split())
mp = {}
INF = 10 ** 9
for _ in range(n):
    b, a = map(int, input().split())
    mp[b] = min(mp.get(b, INF), a)
ans = min(sum(mp.values()), k)
print(ans)

2、小红分糖果

小红有 $n$ 个糖果，要分给小朋友，每个小朋友必须分到 $[l,r]$ 个，如果可以分完，输出最少可以分给多少小朋友，最多可以分给多少小朋友，如果不能分完，输出 $-1$。

输入

一行三个整数 $n,l,r$，表示糖果数量和每个小朋友的要求。

• $1\le n\le {10}^9$
• $1\le l\le r\le {10}^9$

输出

如果可以分完，输出最少可以分给多少小朋友，最多可以分给多少小朋友，如果不能分完，输出 $-1$。

样例

输入：
10 2 3

输出：
4 5

提示：
最少可以分给4个小朋友，[2,2,3,3]; 最多可以分给5个小朋友，每个小朋友分到2个糖果。

解答

假设现在需要求最大值，基本思想是每个小朋友都分的最少。也就是说，分得 $d=\lfloor n/l\rfloor$ 个小朋友，还剩下 $q=n-ld$ 个糖果。容易知道 $d$ 是答案的一个上界，$d$ 不能够再大了。可见 $q<l$，那么这些多出来的 $q$ 个糖果需要分配回去，但是为了确保满足题意，哪怕分回去每个小朋友也不能分超过 $r$ 个糖果，他们现在最多只能再得到 $r-l$ 个糖果。因此，剩下的糖果数 $q$ 必须满足 $q\le d(r-l)$。如果不满足 $q\le d(r-l)$，

那么如果分给 $d$ 个小朋友不可行，有没有可能通过减少小朋友从而获得一个分配方案呢？答案是不可能的，因为减少了小朋友后，就要承担原本分给他的 $l$ 个糖果，之前的小朋友反而还需要多承受一些糖果（总共剩余不止 $q$ 糖果了）。因此减少小朋友并不能获得一个合法的分配方案，上面给出的答案就是最佳答案。

假设现在需要求最小值，思想和上面的类似，每个小朋友都分的最多。也就是说，分得 $d=\lfloor n/r\rfloor$ 个小朋友，还剩下 $q=n-rd$ 个糖果。容易知道 $d$ 是答案的一个下界，$d$ 不能够再小了。类似的，可见 $q<r$。如果 $q=0$，那么这些糖果恰好分完，不需要再判断其它情况。如果 $q>0$，那么还需要多一个小朋友来承受这些糖果。如果 $q\ge l$，那么说明这时新的小朋友已经满足了条件，此时答案为 $d+1$，如果 $q<l$，那么前面的小朋友只能都拿出 $r-l$ 个糖果给他。因此，如果 $q+d(r-l)\ge l$ 仍然成立，那么这个小朋友也是符合条件的，否则他无法取到 $l$ 个糖果，并不可行。

同样的问题，如果分给 $d$ 个小朋友不可行，有没有可能通过增加小朋友从而获得一个分配方案呢？答案同样也是不可行的，因为增加了小朋友后，其余的小朋友就要拿出更多的糖果分出来，原来已经不够分配给持有 $q$ 个糖果的小朋友的数量，现在更加不可行。因此增加小朋友并不能获得一个合法的分配方案，上面给出的答案就是最佳答案。

代码

n, l, r = map(int, input().split())
rp, rr = divmod(n, l)
if rp * (r - l) < rr:
    rp = -1
lp, lr = divmod(n, r)
if lr > 0:
    if lp * (r - l) + lr < l:
        lp = -1
    else:
        lp += 1
if rp == -1:
    print(-1)
else:
    print(lp, rp)

3、小红的树上游走

小红有一棵 $n$ 个节点的树，节点编号为 $1$ 到 $n$。每条边有一个权值，权值是 $1$ 或者 $0$。

对于一个长度为 $k$ 的节点序列 $[a_1,a_2,\dots ,a_k]$，按照顺序依次访问这些节点，从 $a_i$ 走到 $a_{i+1}$，会按照最短路径走。

小红想知道，对于所有长度为 $k$ 的节点序列中（一共有 $n^k$ 个长度为 $k$ 的序列），有多少个序列满足：小红走完这个序列后，经过的所有边的权值之和不为 0。

由于答案可能很大，你只需要输出答案对 ${10}^9+7$ 取模的结果。

注意，小红可以从一个节点走到它自己，也可以重复经过一条边。

输入

一行两个整数 $n$ 和 $k$，表示树的节点数和序列长度。

接下来 $n-1$ 行，每行三个整数 $u,v,w$，表示节点 $u$ 和节点 $v$ 之间有一条边，权值为 $w$。

• $1\le k\le n\le {10}^5$
• $1\le u,v\le n,0\le w\le 1$

输出

输出一个整数，表示满足条件的序列个数对 ${10}^9+7$ 取模的结果。

样例

输入：
3 2
1 2 1
2 3 0

输出：
4

提示：
四个序列分别为[1,2],[2,1],[1,3],[3,1]

解答

这道题的对立问题是：有多少序列，经过的所有边的权值之和等于 $0$。最终用总方案数 $n^k$ 减去对立问题的答案数，就能过得到原问题的答案。

可以发现，求解对立问题的解比求解原问题要简单的多，只要序列 $a$ 相邻的两个节点之间的路径都为 $0$ 即可。原问题与此的区别在于，$a$ 中至少存在一对相邻节点，其路径权值和不等于 $0$，由于还要考虑其它相邻对节点是否满足这个情况，因此直接求解原问题比较困难。

接下来求解这个对立问题。可见，只需要每一对相邻对节点的路径和为 $0$ 即可，这时不需要考虑其它相邻节点对的问题，比较简单，我们使用并查集进行解决。将所有权值为 $0$ 的所有边的相邻节点合并在一起，那么节点 $u$ 和节点 $v$ 的路径之和为 $0$ 当且仅当它们在同一个集合中。因此，一个满足对立问题的序列，要求它的所有结点都在同一个集合中。假设所有合并操作完成后，一共有 $m$ 个集合，第 $i$ 个集合一共有 $c_i$ 个节点，那么这个集合中，满足的节点序列答案为 $c_i^k$。因此本题的最终答案为 ${\displaystyle n^k-\sum _{i=1}^{m}c{i}^k}$。

代码

n, k = map(int, input().split())
fa = [i for i in range(n)]
sz = [1 for _ in range(n)]
mod = 10 ** 9 + 7


def find(x):
    if fa[x] == x:
        return x
    fa[x] = find(fa[x])
    return fa[x]


def merge(x, y):
    u, v = find(x), find(y)
    if u != v:
        fa[v] = u
        sz[u] += sz[v]


for _ in range(n - 1):
    x, y, w = map(int, input().split())
    x, y = x - 1, y - 1
    if w == 0:
        merge(x, y)

ans = (pow(n, k, mod) - sum(pow(sz[i], k, mod) for i in range(n) if i == find(i))) % mod
print(ans)