2025 华为数据通信高校程序设计竞赛训练营 Day 3

注意

题解写得可能非常抽象。

「如果一个题解你看不懂，那是题解垃圾而不是你垃圾。」

不清楚原题是哪里的，听讲题时讲题人的说法，好像提到什么校赛。/yun

A. Undercover

题意

主持人选了一个未知的数 $1\leq x\leq n$。$n$ 个人分别描述「这个数是 $a_i$」或「这个数不是 $a_i$」。已知这 $n$ 句话里面恰有 $m$ 句是正确的，问每个人说的是对还是错还是无法确定。保证有解。$n\leq 10^5$。

题解

记录每个数的「是」和「不是」的数量，可以验证 $x$ 是不是可能是每个数。随后对于每个人，看其提到的数/这个数以外的数是否可能是 $x$，从而判断其是否可能是对的。

F. Competition

题意

有 $n$ 个队伍，每个队有能力值 $a_i$；$m$ 道题，每道题难度值 $d_i$；一个队伍能做难度值不超过自己能力值的题目。$k$ 条无向边，如果一道题被队伍 $a$ 做出来了，与之相邻的队伍的「针对这道题的能力值」会增加边权。求每道题能被多少队做出来。$n,m,k\leq 10^5$。

题解

从难到简单考虑题目。用优先队列维护队伍的能力值，每次取最强队伍做题，更新其他队伍的能力值；如果做不出来就考虑更简单的一道题。

I. TianHe-IIA

题意

给定序列，有四种操作：

• 区间变为欧拉函数
• 区间覆盖为指定值
• 查询区间 $x$ 次方和模 $y$
• 区间覆盖为上面那个查询的结果

随机数据。$n\leq 10^5,V\leq 10^7$。

题解

珂朵莉树板子题。

K. Cards

题意

有 $n$ 种卡，你一次会从这 $n$ 种卡中以给定概率分布 $p_i$ 抽到一张。求期望每种卡都得到至少两张的时间。$n\leq 20$，10 组数据。

题解

先 min-max 容斥，这时我们要考虑每个集合 $S$ 中第一次出现重复的卡的时刻。记 $p_S$ 为 $S$ 内元素的 $p_i$ 之和。记 $f_{S,i}$ 为所有【$S$ 的大小为 $i$ 的子集】的【$p_j$ 之积】的和，即 $[x^i] \prod_{j\in S} (1+p_j x)$。则

$$\begin{aligned} & E[\text{$S$ 中第一次出现重复的卡的时刻}]\\ =& \sum_{k=0}^{\infty} P(\text{时刻 $k$ 时，$S$ 中仍未有重复的卡})\\ =& \sum_{k=0}^{\infty} \sum_{j=0}^{|S|} \binom{k}{k} f_{S,j} j! (1-p_S)^(k-j)\\ =& \sum_{j=0}^{|S|} f_{S,j} \sum_{i=0}^{\infty} (1-p_S)^i \frac{(i+j)!}{i!}\\ =& \sum_{j=0}^{|S|} f_{S,j} \frac{1}{p_S^(j+1)} \end{aligned}$$

$f_{S,j}, \frac{1}{p_S^(j+1)}$ 都可以 $O(n 2^n)$ 求出。