CF1852

你谷的加题速度实在太慢了

被 CF 的题目薄纱

A

可以选任意次 \(i\in [1,n]\)，使 \(a[1\sim i]++,a[i+1\sim n]--\)。求最少操作次数使得原数列变成非从小到大排序的。

首先判断原数列是否已经非排序。然后看每一个相邻位置 \(a[i],a[i+1]\)，令 \(ans=\min(ans,(a[i+1]-a[i])\div2+1).\)

B

斐波那契式数列：\(a_i=a_{i-1}+a_{i-2}\)，但 \(a_{1,2}\) 不定。每项非负。

有多少个斐波那契式数列满足第 \(k\) 项是 \(n\)。

Hint: Can a sequence involving \(n\), which is up to \(10^5\), really have up to \(10^9\) terms?

其实，根据斐波那契数列的增长速度，根本到达不了 \(10^9\) 的项数。我们枚举数列倒数第二项 \(1\sim n\)，倒推 \(k\) 项，看看是否满足每一项都非负。

C

\(1\sim +\infty\)，每次会删去这些数中的第 \(a_{1\sim n}\) 小的数。问：删除 \(k\) 次后，剩下的最小数是多少。

反向考虑。我们不是删除，而是在 \(a_i-i\) 个位置后面插入数。这样的好处是我们不用看我们删完之后谁接上来，只用在一个固定的位置不断插入即可。

记 \(res\) 为最终最小值，这只是我们记出来方便思考。初始令一变量 \(ans=1\)，表示第 \(k\) 天后 \(res\) 的排名是 \(1\)。（最后答案前面的删完了自然是 \(1\)）

考虑插入一些数回到前一天的状态，等回到第 \(1\) 天前，此时 \(ans\) 的值就是初始时 \(res\) 的位置，也就是要输出的答案。（先特判 \(a[1]\ne1\) 则答案必为 \(1\)）

在所有 \(a_i-i\) 位置插入数，保证 \(a_i-i\le ans\)，因为插入到 \(ans\) 位置后面没有意义。

注意我们并不在乎插入了什么数，只需统计每次在 \(ans\) 前又插入了几个数 \(cnt\)，同时在这次结束时\(ans\leftarrow ans+cnt\) 即可。

然后在更新了 \(ans\) 时，要注意又有一些 \(a_i-i\) 可以插入到 \(ans\) 前面了，同步更新。

解释一下 CF 官方代码。

#include <bits/stdc++.h>
using namespace std;

int n, k, a[200010];

void solve() {
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        a[i] -= i; //是在a[i]-i位置插入,而非a[i]
    }
    if (a[0] != 1) { //特判
        cout << 1 << "\n";
        return;
    }
    a[n] = 2e9; //边界守卫
    long long ans = 1; //答案
    int inc = 1; //inc表示本次插入会在ans前插入多少个
    while (inc < n) {
        int days = (a[inc] - ans + inc - 1) / inc;
        //插入1次不能让下一个a[i]-i排到ans前
        //一次性加很多次,跳到下一个a[i]-i也排前,优化
        if (days >= k){
            //如果要下一个a[i]-i排前
            //已经超过剩余插入次数，就结束
            ans += k * inc;
            //那还能插入(剩余次数)*(插入个数)个
            k = 0;
            break;
        }
        ans += days * inc;
        //插入了(插入次数)*(多少个插入位置在ans前)
        k -= days;//减少剩余插入次数
        while (a[inc] <= ans) inc++;
        //拓展在ans前的个数
    }
    ans += 1ll * k * n;
    //1.上面没等到inc>=n就没有了剩余次数,k=0无影响
    //2.inc=n出来的,剩下k次每次都插入n个
    cout << ans << "\n";//输出
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--)
    	solve();
}

D

定义长度 \(n\) 的“不平衡数组” \(\{b_n\}\):

1. \(-n\le b_i\le n.\)

2. \(\forall i,j,b_i+b_j\ne 0.\)

3. 恰有 \(a_i\) 个位置 \(j\)，使 \(b_i+b_j>0\)，允许 \(i=j\).

现给定 \(\{a_n\}\)。要么指出不存在 \(\{b_n\}\)，要么构造出一组 \(\{b_n\}\)。

提示：

\((n,-n),(n-1,-(n-1)),\dots,(1,-1)\)。
每对里只能选一种。

\(b_i>b_j\iff a_i>a_j.\)

设 \(x\) 是使 \(|b_i|\) 最大的 \(i\)。若 \(b_x<0\)，则 \(a_x=0\)；否则 \(a_x=n\)。同时，不可能有另一个 \(a_y=0\) 或 \(n\)。

所以“存在绝对值最大的 \(|b_i|\)” $\iff $

“\((\)存在一个 \(a_i=0)\)”\(\bigoplus\) “存在一个 \(a_i=n\)”。

先判断是否存在绝对值最大，然后固定此位置为绝对值最大，就可以递归处理剩余没处理的数！！！

如果在某次递归中不存在绝对值最大，说明答案不存在。

但是每次循环找 \(a_i=0/n\) 是 \(O(n^2)\) 的。我们可以将 \(a_i\) 排序。这样每次判断就是 \(O(1)\) 的了！