交互题

签到题看了半个小时;T2 没有考虑到只需要包含最优解即可,非要确定另一多余状态,只拿了部分分。

T3 只会考虑 “x,yx, y 的公共祖先中含有 ll 的概率”,不会高效计算“当二者的 lca\operatorname{lca} 恰为 ll 时”的期望/概率与总长之和的乘积,仍然只有暴力分。

T4 无思路。

一句话(?)题解

A – 签到题

可以简单用归纳法证明,仅有所有管道中通行时间最大的会阻塞进度,是为两数据包到达终点的时间间隔。算出首个数据包到达的时间再将前者相加即可。

B – 简单题

第一反应是类似笛卡尔树一样,在区间上依次合并区域最大值并计算贡献。n300n \leq 300 似乎也在暗示这是一个区间 DP。

48 pts\text{48 pts} 做法

f(l,r,mx)f(l,r,\text{mx}) 表示“考虑完成区间 [l,r][l,r] 内所有贡献,且最大值恰好为 mx\text{mx}”的最大权值和。转移时从小到大枚举最大值 mx=Vi,j\text{mx}=V_{i,j},枚举包含它的区间,尝试转移 f(l,r,mx)f(l,i1,mx’)Ci,j+mxcalc(l,r,i)+f(i+1,r,mx”)f(l,r,\text{mx})\leftarrow f(l,i-1,\text{mx}’)-C_{i,j}+\text{mx}\cdot \operatorname{calc}(l,r,i)+f(i+1,r,\text{mx}”),其中 calc(l,r,i)\operatorname{calc}(l,r,i) 计算 l=lir=irQl,r\sum_{l’=l}^{i}\sum_{r’=i}^{r}Q_{l’,r’},可以由二维前缀和实现。稍加演算会发现,这样转移不会重复计算贡献。时间复杂度 O(KiN2)\operatorname{O}(\sum K_{i}N^2)(更多…)

More
  • 2022年10月19日

给大家表演一个一场下青

CodeForces Round 770 Div.2 Problem D – Finding Zero

一道非常有意思的交互和构造题。

考虑能否固定两个数x,yx, y,通过它们的相对大小关系,确定其他数中是否存在00或最大值amaxa_{\text{max}}

经过一番推导,我们发现,设xyx \geq y的情况下,对于三元组(ai=x,aj=y,ak=z)(a_i=x, a_j=y, a_k=z),有g(i,j,k)=max(ai,aj,ak)min(ai,aj,ak)={zy,z>xxy,z[y,x]xz,z<yg(i, j, k)\newline =\max(a_i, a_j, a_k) – \min(a_i, a_j, a_k)= \begin{cases}z-y, & z > x \\ x-y, & z \in [y, x]\\ x-z, & z < y\end{cases}。所以,设x=6,y=4x=6, y=4以上式结果为因变量,zz为自变量,应有以下图像:

(更多…)

More
  • 2022年2月7日