注意
题解写得可能非常抽象。
「如果一个题解你看不懂,那是题解垃圾而不是你垃圾。」
不清楚原题是哪里的,听讲题时讲题人的说法,好像提到什么校赛。/yun
主持人选了一个未知的数 1≤x≤n。n 个人分别描述「这个数是 ai」或「这个数不是 ai」。已知这 n 句话里面恰有 m 句是正确的,问每个人说的是对还是错还是无法确定。保证有解。n≤105。
记录每个数的「是」和「不是」的数量,可以验证 x 是不是可能是每个数。随后对于每个人,看其提到的数/这个数以外的数是否可能是 x,从而判断其是否可能是对的。
有 n 个队伍,每个队有能力值 ai;m 道题,每道题难度值 di;一个队伍能做难度值不超过自己能力值的题目。k 条无向边,如果一道题被队伍 a 做出来了,与之相邻的队伍的「针对这道题的能力值」会增加边权。求每道题能被多少队做出来。n,m,k≤105。
从难到简单考虑题目。用优先队列维护队伍的能力值,每次取最强队伍做题,更新其他队伍的能力值;如果做不出来就考虑更简单的一道题。
给定序列,有四种操作:
- 区间变为欧拉函数
- 区间覆盖为指定值
- 查询区间 x 次方和模 y
- 区间覆盖为上面那个查询的结果
随机数据。n≤105,V≤107。
珂朵莉树板子题。
有 n 种卡,你一次会从这 n 种卡中以给定概率分布 pi 抽到一张。求期望每种卡都得到至少两张的时间。n≤20,10 组数据。
先 min-max 容斥,这时我们要考虑每个集合 S 中第一次出现重复的卡的时刻。记 pS 为 S 内元素的 pi 之和。记 fS,i 为所有【S 的大小为 i 的子集】的【pj 之积】的和,即 [xi]∏j∈S(1+pjx)。则
====E[S 中第一次出现重复的卡的时刻]k=0∑∞P(时刻 k 时,S 中仍未有重复的卡)k=0∑∞j=0∑∣S∣(kk)fS,jj!(1−pS)(k−j)j=0∑∣S∣fS,ji=0∑∞(1−pS)ii!(i+j)!j=0∑∣S∣fS,jpS(j+1)1
fS,j,pS(j+1)1 都可以 O(n2n) 求出。