Atcoder ARC149D – Simultaneous Sugoroku

官方题解做法是线性的,在此不再赘述。

考虑对于纸片 X=1,2,,max{Xi}X=1,2,\cdots,\max\{X_i\} 分别计算答案。每次暴力枚举显然不可取,但假若我们知晓对于 XX,在 i=0,1,,Mi=0,1,\cdots,M 次操作以后纸片在数轴上的坐标 x0=X,x1,,xmx_0=X,x_1,\cdots,x_m,其中 pos\text{pos} 是最小的取到 xpos=1x_\text{pos}=-1 的位置,则对于 x0=X=X+1{x_0}’=X’=X+1

  • 如果 pos\text{pos} 不存在,则所有坐标整体向数轴正半轴平移 11 单位;
  • 否则,pos\text{pos} 就将是起始点为 XX’ 的纸片首次到达 00 点的位置,也即题目所求。所有小于 pos\text{pos} 的坐标仍向正半轴平移 11 单位;而 pos\geq \text{pos} 的坐标,由于偏移量 DiD_i 符号翻转,则有 xixi1=(xixi1){x_i}’-{x_{i-1}}’=-(x_i-x_{i-1})。依次考虑每一坐标,就会得到 xi=1xi,posim{x_i}’=1-x_i,\forall \text{pos}\leq i\leq m。 (这里认为当 xpos=0x_\text{pos}=0 时仍然继续执行操作。维护 pos\geq\text{pos} 的坐标位置是为了计算 X>XX”>X’ 的答案。)

这是可以用区间树维护的:我们想要快速求出全局非正数最大值以及首次取到该最大值的位置,同时支持全局加 11、后缀所有数符号翻转×1\times -1)。那么同时维护区间非负数最大值、正数最小值以及首次取到他们的位置,采用延迟标记更新(两种操作对于前述信息是具有结合律的,形成幺半群)即可。

时间复杂度 O(max{Xi}logM)\operatorname{O}(\max\{X_i\}\log M),常数一般。

Submission #36155560 (更多…)

More
  • 2022年11月2日

感冒咳嗽,头实在是太晕了,打完前两题和后两题的暴力之后跑去睡了会觉。结果考得还行。

一句话题解

A – 破坏

简单的 O(m2k)\newcommand{\bigO}{\operatorname{O}}\bigO(m2^k) DP。记录每个节点的路径数奇偶性考虑是否翻转即可。

B – 共识

std::bitset 写的暴力大家都会。不过如果你胆子大些,不判断是否为部分分数据范围直接提交(加入随机化的)暴力,将喜提 100 pts\text{100 pts}

命题:现有一个由 2n2n 个元素构成的集合,保证 2n2\mid n。有 n+1n+1 个大小恰为 nn 的子集 S1,,Sn+1S_1,\cdots,S_{n+1}。则至少存在 n/2n/2 对无序对 (i,j),ij,i,j[1,n+1](i,j),i\neq j, i,j\in[1,n+1],使得 SiSjn/2|S_i\cap S_j|\geq n/2

证明(引自宋佳兴学长):记元素 p,p{1,,2n}p,p\in\{1,\cdots,2n\} 在所有子集中出现的次数为 cnt(p)\newcommand{\cnt}{\operatorname{cnt}}\cnt(p)。则显然有“所有子集两两之交的大小” i=1nj=i+1n+1SiSj=p=12n(cnt(p)2)\sum_{i=1}^{n}\sum_{j=i+1}^{n+1}|S_i\cap S_j|=\sum_{p=1}^{2n}\binom{\cnt(p)}{2}

考虑计算该式最小为何。不妨先考虑 (ab)+(nab)\binom{a}{b}+\binom{n-a}{b} 在何时取最小值。

引理(ab)+(nab),bn,a0,an\binom{a}{b}+\binom{n-a}{b}, b\leq n, a\geq 0, a\leq na=n/2a=\lfloor n/2\rfloor 处取最小值。

(更多…)

More
  • 2022年10月26日

堪堪能接受的一场。前两题一个半小时左右做完,后两题实在没什么思路,打完所有可能的暴力之后跑路了。

他们告诉我题目名称可以从上到下连起来读。

一句话题解

A – (种)菜

可以发现,假若同时有 ai,ai+1\newcommand{\bigO}{\operatorname{O}}a_i,a_{i+1}ai+1,ai+2a_{i+1},a_{i+2} 都可合并,则取 ai,ai+2a_i, a_{i+2} 中任意一个合并之后,质因数集合总是变为原来的超集,另外一项仍可合并。

故而可以贪心合并所有合法的邻项,最终检查是否仅剩一项即可。注意到 [1,700][1,700] 仅含 125125 个质因数,故可以用 std::bitset 保存每一项的质因子集合。复杂度 O(128nω)O(\frac{128n}{\omega})赛时竟然还开了数组保存每个质因子的实际指数! (更多…)

More
  • 2022年10月26日

恕我语文不好,实在不晓得用何种词汇来描述看到下文的感受:

此比赛为正常的提高组难度,甚至可以用来作为普及组模拟赛。 请选手 AK 后不要大声喧哗,以免影响他人 AK。

尤其是这套题的出题人是张隽铠的情况下。当然,OI 圈风气本就如此,我也不好过多评价。No comment.

T1 还算顺利,半小时左右搞定。T2 是大分类讨论,足够恶心人,但好在有相当可观的可以通过暴力与观察拿到的部分分。T3 猜测与线性基相关,但没有相应知识储备,暴力跑路。

T4 就……反正出题人开心就好。到现在都没人改出来。

一句话题解

A – 序列

依次往某个子序列中添加元素。则添加的元素必然成为新的最大值/最小值之一,否则违背题意。

于是枚举子序列首元素,将以其开头的严格上升子序列数与严格下降子序列数相乘即可。使用树状数组转移即可。复杂度 O(nlogn)\operatorname{O}(n \log n)(更多…)

More
  • 2022年10月19日

签到题看了半个小时;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日

LibreOJ #138 类欧几里得算法

题意

T1000T \leq 1000 组数据。给定 n,a,b,c[0,109],k1,k2[0,10],k1+k210n, a, b, c\in [0, 10^9], k_1,k_2\in [0, 10], k_1+k_2\leq 10,求取 x=0nxk1ax+bck2 \sum_{x=0}^{n}x^{k_1}\left\lfloor\frac{ax+b}{c}\right\rfloor^{k_2}

部分分——观察性质

k1=0,k2=1k_1=0,k_2=1 时,是为一般类欧几里得算法的模板。上述链接亦给出了 k1=0,k2=2;k1=1,k2=1k_1=0,k_2=2; k_1=1,k_2=1 时的解法。

k2=0k_2=0 时,该式退化为 x=0nxk1\sum_{x=0}^{n}x^{k_1},即 k1k_1 次的等幂求和。有一个模糊的结论:

nn 为正整数。则kk 次的等幂求和,x=0nxk\sum_{x=0}^{n}x^k,是一个关于 nnk+1k+1 次多项式。

该结论来源于 zyw 学姐多项式专题所选题目 BZOJ 3453 – tyvj 1858 XLkxc。之所以说模糊,是因为该多项式的系数是已知的。不过我们仍然可以暴力计算 k+2k+2 个点以插值。

再观察 OI-Wiki 上对于 k1+k22k_1+k_2\leq 2 时的解法。在求取 h(n,a,b,c)=x=0nax+bc2h(n,a,b,c)=\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2时采取了如下转化:

x2=2×x(x+1)2x=2(y=1xy)xx=0nax+bc2=x=0n2(y=1ax+bcy)ax+bc\begin{aligned} x^2&=2\times \frac{x(x+1)}{2}-x\\ &=2\left(\sum_{y=1}^{x}y\right)-x\end{aligned} \quad\begin{aligned} \Longrightarrow\sum_{x=0}^n\left\lfloor\frac{ax+b}{c}\right\rfloor^2=\sum_{x=0}^n2\left(\sum_{y=1}^{\left\lfloor\frac{ax+b}{c}\right\rfloor}y\right)-\left\lfloor\frac{ax+b}{c}\right\rfloor\\ \end{aligned}

这样一来,由于 yy 是一个线性算子,在 ax+bycax+b\geq yc 时都有 yy 向总和贡献,于是我们可以应用类似于 k1=0,k2=1k_1=0,k_2=1 时的方法转化贡献。这个过程对 k2k_2 作了降次。

那么,对于更高次项,有无办法采取同样的办法转化呢?是否可以设计一些转化,使得要求取的函数 f(,k1,k2)f(\cdots,k_1,k_2) 能够由 f(,k1?,k2?)f(\cdots,k_1-?,k_2-?) 推出呢? (更多…)

More
  • 2022年10月13日

策略和思维活跃度都极其糟糕的一个上午。

那么“在能力不足以保证完成更多正解”的情况下获取尽可能多的暴力分从而提高总分下限,又被重新提上议程。切记切记。

思维广度待进一步提升。

一句话题解

A – 道路

发现了是平面图,想到了数据结构与区间可达性,就是没把俩概念结合起来。

由题目保证的“两边不交”性质,可以发现,若不考虑无法从任何一个左侧点到达的右侧点,如有 (A,y1),(A,y2),y1<y2(A,y_1),(A,y_2),y_1<y_2 均可从 (0,y0)(0,y_0) 达,则若有 (A,y3),y3[y1,y2](A,y_3),y_3\in [y_1,y_2],则其必然亦可达。

缩点后拓扑排序求出每个连通块能到达的右侧点 yy 坐标区间即可。复杂度 (O)(nlogn+m)\operatorname(O)(n\log n+m)

B – 地震后的H市

联想到了 HDU “杭电杯”超级联赛(3) Spanning Tree Game 钦定最小生成树,按边权从小到大依次加边的动规方法。

可惜这是最小瓶颈生成树。

解一(刘晟林)

(更多…)

More
  • 2022年10月6日