跳至主要內容

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

Wallbreaker5th大约 3 分钟OI×ICPCOI×ICPCOI×ICPC - 题解OI×ICPC - 贪心OI×ICPC - 优先队列OI×ICPC - 珂朵莉树OI×ICPC - min-max容斥

注意

题解写得可能非常抽象。

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

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

A. Undercover

题意

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

题解

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

F. Competition

题意

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

题解

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

I. TianHe-IIA

题意

给定序列,有四种操作:

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

随机数据。n105,V107n\leq 10^5,V\leq 10^7

题解

珂朵莉树板子题。

K. Cards

题意

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

题解

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

E[S 中第一次出现重复的卡的时刻]=k=0P(时刻 k 时,S 中仍未有重复的卡)=k=0j=0S(kk)fS,jj!(1pS)(kj)=j=0SfS,ji=0(1pS)i(i+j)!i!=j=0SfS,j1pS(j+1) \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}

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