Codeforces Round#905 解题报告

发布时间 2023-10-26 19:03:37作者: yspm

按理来说最近开始了一天一套 div2 计划,第一天做了一套 Div1,第二天做了 hustfc,第三天因为要赶 latex 期末考试,所以什么也没做。

明天写一下 hustfc 比较牛的几题。

A

暴力怎么做,是不是加加加,然后判断。

B

本质上是让长度为 \(i\) 的后缀全是 \(0\) 那么找到最短的有 \(i\)\(0\) 的后缀求一下逆序对就行了。

C

注意到 \(\min(a)\)\(1\) 或者 \(m\) 最好使,暴力找到 \(\max(a)\) 即可。

差分哦

D

\(x\in [1,n]\) 计算是不是在 \(a\) 中存在 \(x\) 的因子。再通过差分计算有多少对子的 \(\rm{gcd}\)\(t\in[1,n]\) 不能输入一个 \(a_i\) 标记一下哦!

E

策略大概就是笛卡尔树上 父亲权值减去儿子权值 × 儿子控制区间长度。换一个想法,如果出现了 \(a_l\ge a_k\le a_r\)\(a_k=\max\limits_{i=l}^r\{a_i\}\) 则需要进行 \(\min\{a_l,a_r\}-a_k\) 次操作。

看到 shift 你是不是想到复制一倍接到后面!