2023年 7月做题记录-JZTXT

乐，7.9 才开始写．

LOJ #6507. 「雅礼集训 2018 Day7」A

考场做法

按位考虑．
对于 \(＆\) 操作，为 \(1\) 的位不需要考虑．对于为 \(0\) 的位，则是 \([l,r]\) 的这一位覆盖为 \(0\)．\(|\) 操作同理．
因为是某一位的覆盖，不能方便地维护全局的最小值．

考虑将覆盖操作换成加减操作．
对于任意一位：遍历 \([l,r]\)，若干极长的 \(0/1\) 段可以一起操作（加，减或不变），操作之后区间被统一成 \(1\) 或 \(0\)．我们发现复杂度是颜色段覆盖．

正解

不用按位考虑了．
考虑维护区间的 \(|\) 和 \(S_{or}\) 和 \(\&\) 和 \(S_{and}\)．

对于一个区间，只有 \(S_{or}\) 和 \(S_{and}\) 进行操作后相等，才能保证区间中的每个数进行操作后相等．
对于一个区间 \(|d\)，若 \(s_{and}|d=s_{or}|d\)，则区间 \(|d\) 无效．
对于一个区间 \(\&d\)，若 \(s_{and}\&d=s_{or}\&d\)，则区间 \(\&d\) 无效．

根据势能分析可以知道算法复杂度正确．

但我不会势能分析．

LOJ #6508. 「雅礼集训 2018 Day7」B

奇妙的转化．

考虑枚举 \(T_i\)，然后看它能贡献到以哪些地方为起点的询问上．

考虑起点是 \(p\)．

若 \(T_i=1\)：

\[\overline {S_{i+p}} \equiv [0,c)\\ \overline {S_p} \equiv [0-ia,c-ia) \]

若 \(T_i=0\)：

\[\overline {S_{i+p}} \equiv [c,n)\\ \overline {S_p} \equiv [c-ia, n-ia) \]

\(T_i\) 有贡献的起点 \(p\)，\(S_p\) 是剩余类上一个连续区间．

整一个动态开点值域线段数即可．

LOJ #6509. 「雅礼集训 2018 Day7」C

很强的随机性伴随的对称性．

考虑转化贡献．
发现一个点被选择后，若没有到终止局面，肯定会进行下一次选择：产生的移动距离期望是

\[\frac{\sum_{v\in[1,n]}dis(u,v)}{n} \]

那么我们只需要求出每个点不导致终止局面的期望被选择次数即可．
由于纯随机，发现树的形态不会对选择次数产生影响．

考虑设计状态 \(F_{i,0/1}\) 表示存在 \(i\) 个黑点，其中任意一个黑/白点不导致终止局面的期望被选择次数．

有转移方程

\[F_{i,1}=\frac{i-1}{n}F_{i-1,1}+\frac{n-i}{n}F_{i+1,1}+\frac{1}{n}(F_{i-1,0}+1) \]

\[F_{i,0}=\frac{i}{n}F_{i-1,0}+\frac{n-i-1}{n}F_{i+1, 0}+\frac{1}{n}{(F_{i+1,1}+1)} \]

笔者尝试实现暴力高斯消元．但答案一直不对．
这里附上一篇不错的题解 20200525 hz T3（#6509. 「雅礼集训 2018 Day7」C）【期望】

P7831 [CCO2021] Travelling Merchant

考虑如下算法流程：

（1）对于图中没有出度的（在队列中）点，更新指向它们的点并将指向它们的边删除，将这些点压入队列．如果产生了新的没有度数的点，则重复该流程．
（2）选出没有被删除的 \(r\) 最大的边，假设它是 \(e(u \rightarrow v,r,p)\)．用 \(r\) 更新 \(u\) 的答案．若 \(u\) 没有出度，将 \(u\) 压入队列．
（3）重复上面两步操作，直到所有边被删除．

以上算法的时间复杂度瓶颈在给边按 \(r\) 降序排序．

考虑算法的正确性．

显然从 \(u\) 出发，要保证无限游走必须要走到一个环上．

算法每次将可能在环上的最大边断掉（2），然后使用类似拓扑排序的方法更新可能在这个环上的点的答案（1）．

分两类：

若环上 \(r\) 最大的边在从 \(u\) 指出的边上．算法步骤（2）可以更新．
若环上 \(r\) 最大的边不是从 \(u\) 指出的边上．算法步骤（1）可以更新．

LOJ #6065. 「2017 山东一轮集训 Day3」第一题

分类枚举．
记 \(num(len)\) 表示长度为 \(len\) 的木棍的个数．

两条长度为边长的木棍 \(+\) 四条小木棍．先枚举边长，然后枚举四条木棍．答案为

\[\sum_{len}\binom{num(len)}{2}w(len)\ \]

这里的 \(w(len)\) 表示用四条木棍组成两条长为 \(len\) 的边的方案数量．这个方案是容易讨论的．
2. 三条长度为边长的木棍 \(+\) 三条小木棍．这时不能先枚举边长（处理会变得很麻烦）．存在两根小木棒相同或三根小木棒都相同的情况是容易解决的．考虑三根小木棒均不同如何统计．枚举三条小木棍中最长的一个．从大到小扫描每种长度的木棍．记 \(F_{i,j}\) 表示长度 \(\le i\) 的两根木棍拼起来，大小等于 \(j\) 的方案数．新加入长度为 \(i\) 的小木棍后，\(F\) 存在变化 \(F_{i,i+j}+=num(i)*num(j)\)．然后这时，我们再枚举边长 \(d\)，由于规定了最长的小木棍为 \(i\)，则对方案的贡献为

\[\binom{num(d)}{4} num(i)F_{i,d-i} \]

LOJ #6119. 「2017 山东二轮集训 Day7」国王

记 \(x\) 表示 \(u \in [l,r]\)，记 \(y\) 表示 \(u \notin [l,r]\)．

那么一个区间 \([l,r]\) 合法即判定

\[\sum_{(x_i,x_j)}[(x_i,x_j)\ is\ a\ correct\ path] > \sum_{(y_i,y_j)}[(y_i,y_j)\ is\ a\ correct\ path] \]

考虑在不等式左边加上

\[\sum_{(x_i,y_j)}[(x_i,y_j)\ is\ a\ correct\ path] \]

右边加上

\[\sum_{(y_i,x_j)}[(y_i,x_j)\ is\ a\ correct\ path] \]

显然这两个部分是相等的．
那么原来的判定式可以改写成：

\[\sum_{(x_i,*)}[(x_i,*)\ is\ a\ correct\ path] > \sum_{(y_i,*)}[(y_i,*)\ is\ a\ correct\ path] \]

即

\[2 \sum_{(x_i,*)}[(x_i,*)\ is\ a\ correct\ path] > \sum_{(*,*)}[(*,*)\ is\ a\ correct\ path] \]

记 \(\displaystyle w_i=\sum_{(i,*)}[(i,*)\ is\ a\ correct\ path]\)，求出所有 \(w_i\) 后双指针即可．

JZTXT

2023年 7月 做题记录