H 戏团演出 思路 听说这题是原题？ 虽然效率更低但还是介绍一个现场口胡的树剖+区间差分做法： 先考虑解决一维区间上的覆盖问题：对于一个起点为 lll，终点为 rrr，颜色为 www 的区间，我们可以在 lll 处打上让 www 加一的标记，同时在 r+1r+1r+1 处打上让 www 减一的标记，最后从 111 到 nnn 按顺序扫一遍，每次操作后在优先队列里更新最优答案。 接下来解决树上问题：考虑树剖后每条链最多被分解成 O(log)O(log)O(log) 条重链，而每条重链对应一个连续区间，于是我们可以把每个询问拆分成 O(log)O(log)O(log) 个连续区间，然后搬到平面上处...

Lndjy and the mex 题意 给定多重集 SSS，满足元素是 [0,n][0,n][0,n] 内的整数，且 ∣S∣=n|S| = n∣S∣=n。 一个序列的权值定义为所有区间的 mexmexmex 之和。 计算所有长度为 nnn 且元素与 SSS 完全相同的序列的权值之和。 取模 998244353。 1≤n≤1051 ≤ n ≤ 10^51≤n≤105。 思路 对于一个长度为 lenlenlen 的区间而言，它的 mexmexmex 小于 www，当且仅当 000 到 w−1w-1w−1 中的某些数不在这个区间内出现。 于是考虑容斥。对于 {0,1,...,w−1}\...

RT，应该是 F 的 std 对只剩一个人时的溅射伤害的判断有问题，导致这部分没被统计进去比如 3 1 1 3 8 10这个样例，std 跑出来是 2，但是正解应该是在第一轮中 {3,8,10} → {2,7,9} → {0,5,7} → {0,2,4} → {0,0,1} → {0,0,0}，答案为 1

E.游戏人生 贪心。考虑从第 111 回合到第 nnn 回合依次构造最优状态。 首先定义 BOSS 的生命值 hphphp 为击败 BOSS 所需攻击次数，即 ⌈HPx⌉\lceil \frac{HP}{x} \rceil⌈xHP​⌉，若这个值超过 2n2n2n 直接输出 -1。 在第 iii 回合开始时，我们首先令前 i−1i-1i−1 回合全部防御，然后考虑每次进行一步令 BOSS 生命值减 111 的操作。 操作方法有 2 种： 放弃第 xxx 次防御进行输出，受到 a[x]−a[x]/2a[x]-a[x]/2a[x]−a[x]/2 伤害。 在某次放弃防御的基础上狂暴，受到 yyy 伤...

C.数字匹配 如果一个数对 (x(x(x , y)y)y) 存在重合位数大于 kkk 的子串，那么在所有 (x>>a(x>>a(x>>a , y>>b)y>>b)y>>b) 中，一定存在从第 111 位到第 kkk 位相互匹配的数对。 令 maskmaskmask 为拥有恰好 kkk 个 111 的二进制串，那么 (x(x(x , y)y)y) 从第 111 位到第 kkk 位相互匹配即可视作 (x&mask)==(y&mask)(x \& mask)==(y \& mask)(x&amp...

K.atzlein Cocktail 不难发现最少的交换次数就是人数 减去排列形成的环的数量。 先解决 个数完全随机的情况。考虑到排列环中每个点只和两个点相连的特性，我们可以把问题等价于 条相同的绳每次选择两头相连，不生成环的次数的期望。对于一条绳而言，当且仅当他不与自己两头相连时不生成环，而每次合并后可选的绳子必然会减少一条，因此有：。 再来考虑部分数被钦定的情况：如果合并后不形成新环，那么答案增加；而无论是否形成新环，可选的绳子都会减少一条。因此钦定 个数且形成 条新链后的答案为 。 是否形成新环可用并查集解决。 #include <bits/stdc++.h> us...

Problem F 合并石子一共有 堆石子，故合并时产生 种情况;第 次合并时共有 堆石子，故选取两堆的期望和为 ;故消耗体力总和为 。 #include <bits/stdc++.h> using namespace std; typedef long long ll; #define M 1000000007 ll ksm(ll a,ll p){ ll res=1; while(p){if(p&1){res=res*a%M;}a=a*a%M;p>>=1;}return res; } int i; ll n,res,tmp; in...