【复盘】CF890 Div.2

发布时间 2023-08-06 01:21:28作者: Aslf_Ek

A题过的很快。


B题刚开始读错题了。至少浪费了半小时到45分钟,说明题目还是一定要多读几遍!!!


C题感觉是贪心,贪了半天,先是样例过不去,然后再是交上去wa了,自己构造了反例,然后发现确实错了,想改,改了没调完结束了。花了至少1h+时间。

这证明,有时候确实是会被卡住的。这很正常。

然后问了LA群,说是二分+暴力

然后自己想了一下解法。

先挂C题链接To Become Max

二分答案,二分一个最值,就是最大能到多少。显然,答案满足单调性,大到一定程度经过k次操作也无法加出那么大的数。

所以二分+check。

然后就是check部分。

check部分:

  1. 枚举 \(i\in [1,n]\) ,让 \(i\) 成为最值点。那么,只要有一个 \(i\) 满足它可以成为最值点,那么这个最值就是可行的。

2.如何证明 \(i\) 可行呢?那就得给 \(a[i]\) 疯狂一顿加,加的方式就是:

每一次,从 \(i\) 开始,向右找最长的下降区间,一旦发现 \(a[j]<=a[j+1]\) ,开始不降,停止,

然后把那个 \(a[j]\) 加到 \(a[j+1]+1\),顺着 \(j\) ,一路跑回到 \(i\) ,对于每一个 \(j\),把 \(a[j]\) 加到 \(a[j+1]+1\),前提是可加,如果不可加,直接循环break.

加到什么时候为止呢? \(a[i]\) 大于等于这个二分的 \(mid\) 的时候就行了。

这样不断地发育 \(a[i]\) ,尽可能地使 \(a[i]\) 更大。

这样一定要加好多次吧?那么,看看加了这么多次,大于 \(k\) 次了吗?判断 \(k\) 行不行咯。

二分出 \(mid\) ,最后 \(ans\) 就是答案。


D、E1、E2没做。难的,但是要我去做,说不定还行,没看题,来不及了。

这也说明,CF是一场速度试炼赛。