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

发表于 2023-10-11 分类于笔试阅读次数：本文字数： 2.6k 阅读时长 ≈ 2 分钟

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{\min_{1\le j\le n,b_j=i}\{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}^mci^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)