2.14 晚上的比赛, 现在改好了四题, 还差提答. 在这补个题解
新年的xor
Description
给你 (n) , 然后要你构造 ([L, R], L<R) 使得区间异或和为 (n)
Solution
做法多的是
我的方法是特判 (nle 4) 的, 然后对于奇数用 ([n-3,n-1]) , 偶数用 ([n-4, n])
新年的叶子
Description
一棵 (nle 5e5) 的树, 每次会随机将一个原树的叶子染黑, 问白点最远距离什么时候变小
Solution
直径的性质 : 所有直径的中点的距离 (le 1) (反证易证)
我们随便找一条直径的终点为根建树.
当直径长度 (d) 为偶数时 :
有若干关键子树(即包含关键叶子的子树)
这里关键叶子定义为 (dep=frac d 2) 的叶子
当只剩一棵关键子树内关键叶子不全黑时, 最长链变小
当直径长度 (d) 为奇数时 :
所有长度为 (dep = lceilfrac d 2 ceil) 的叶子必定都在同一棵子树, 把这些叶子称为该子树的关键叶子
把其他子树中的关键叶子为 (dep = lfloorfrac d 2 floor) 的
当上面那种关键叶子全黑或下面那种全黑时, 最长链变小.
把深度不是最大的哪些子树合并起来, 就可以用直经长度为偶数的方法来处理
做法1 :
枚举哪棵关键子树最后剩下, 设那棵有 (s) 个关键叶子, 染色结束时剩余 (i) 个关键叶子
设关键叶子总数为 (n), 叶子总数为 (tot)
在剩余 (k) 个关键叶子未黑时, 要想再染多一个关键节点需要期望 (frac {tot} k) 步.
做法2 :
枚举哪颗关键子树最后剩下, 然后不管那颗子树, 算把剩余子树染黑的期望时间
显然会算多.
注意到对于算多的部分, 必然时所有关键叶子全都被染黑了, 但是最后染黑的不在当前子树
令 (E(x)) 为把所有关键叶子全部染黑, 最后染黑的在 (x) 子树的期望时间
总共算多的部分是 : (设有 (L) 个关键子树)
新年的五维几何
Description
(n=5) 个实数变量, 第 (i) 个变量的取值范围为 ([l_i, r_i])
给定矩阵 (a).
问每个变量都在取值范围内随机时, 有多大概率使得 (x_i-x_jge a_{i, j}) 全部成立
(-10le l_i, r_i, a_{i, j} le 10), 且 都是整数
Partial Score
讲一个比较有意义的部分分 : (若 j eq i+1, a_{i,j}=-10)
因为 (x_i-x_j) 一定 (ge -10), 所以这个部分分相当于我们只需要考虑相邻变量的限制
设 (f_i(x)) 为 (x_i le x), 且 (x_i,cdots,x_n) 满足限制的概率 ((f_{n+1}(x) = 1))
我们有
注意到 (f_i(x)) 是 (O(n)) 段的多项式, 我们可以每段积分, 然后平移
对于定积分的处理方法 : 因为 (l_i) 是常数, 我们算出不定积分, 然后整体减去一个常数即可
最后截出 ([l, r]), 补上旁边两段即可
(没有实现, 有错指出)
Solution
注意到特殊性质 : 取值范围, 限制 都是整数.
(l_i=r_i) 的变量不讨论 (特判一些东西就好了)
考虑对于 (l_ilt r_i) 的变量, 我们设 (x_i = p_i+q_i), (p_iin[l_i, r_i)in Z, q_iin[0, 1)in R)
那么我们 (O(10^n)) 枚举 (p), 算出对应概率, 取平均值即为答案所求
考虑限制 (p_i+q_i-p_j-q_jge a_{i,j})
移项有 (q_i-q_jge p_j-p_i+a_{i,j}) , 可知右边 (ge 1) 时无解, (le -1) 时限制无效
右边为 (0) 时相当于 (q_jle q_i) 的变量. 在随机撒点的情况下可视为 (q_jlt q_i)
由于随机撒点时 (n!) 种相对大小顺序的概率是相同的, 我们可以转为统计有多少种相对大小顺序满足条件. 状压或暴搜即可
总复杂度 (O(10^n2^nn))
新年的代码
Description
给你长度 (5e5) 的 (RGB) 串 (S, T), 问从 (S) 至少操作多少次才能到 (T)
操作(1) : 选择两个不同颜色的相邻位, 将它们都变成除了它们的第三种颜色 (RG -> BB)
操作(2) : 选择两个相同颜色的相邻位, 将它们变成不同的新颜色 (BB -> RG / GR)
Solution
给 (R, G, B) 随便进行一个 (012) 标号 (标号后 (S o a, T o b))
然后发现每次操作相当于在 (mod 3) 意义下把相邻位一个 +1, 另一个 -1
反之, 把相邻位+-1不一定是一个操作
考虑在(mod 3) 意义下求个前缀和 (sa, sb)
原操作等价于对前缀和序列的单点 (pm 1), 原目标等价于经过一波操作让两个前缀和序列相等
考虑按照 (saequiv sbpmod 3) 的位置分段. (每段包含最右边 (sa=sb) 的那个位置)
那么显然对于一个长度 (n) 的段, 至少要操作 (n-1) 次.
然后根据后面的构造, 操作至多 (n) 次, 因此每段需要操作 ([n-1, n]) 次
目前为止只考虑了段与段独立的情况. 考虑归纳 :
归纳基础 : 若某一次在段交界处操作了一下使两段合并, 之后不再合并段, 那么设合并了长度为 (a, b) 的段, 原来要 ([a+b-2, a+b]) 次, 合并的话要 (1 + [a+b-1, a+b]) 次. 不优
归纳 : 每次合并段后进入归纳子状态, 不优.
然后我们按照下面的构造中用到的操作方法, 进行 (dp)
(dp[i][u][v]) 表示第 (i+1) 这个位置要从 (u) 变 (v) , 前 (i) 个位置需要代价是什么
然后有两种可能的操作 : (操作从上到下依次执行, 每次操作把上一行变成下一行)
case 1:
a[i+1]
u w
v b[i+1]
case 2:
u a[i+1]
v w
b[i+1]
构造
若 (a) 中段头为相同颜色, 不妨设为 (00)
那么若 (b) 中段头为 (1/2), 一步操作把段头改对, 递归. 否则, 不用改段头, 直接递归进入
若 (a) 中段头为不同颜色, 不妨设为 (01)
若 (b) 中段头为 (2) , 一步操作递归. 若为 (0), 直接递归
若为 (10) , 则 (01 o 22 o 10) 两步完成两个位置, 递归两层
若为 (11) , 先递归操作后面, 把 (a) 中第二个位置变成 (2), 再 (02 o 11)
若为 (12) , 同理先操作后面, 把 (a) 中第二个位置变成 (0), 再 (00 o 12)
构造完成.
问题来了 : 会不会一直借位到段位还要往后借呢?
从前缀和的角度, 借位相当于先fix后面, 再fix自己. 然后段尾不需要fix自己.
(我记得我之前不是这样证的. 现在写题解时不知道我当时怎么证的了. 不知道这样理解有没有错, 有错请指出)
新年的投票
还不会啊... 挖个坑