Contestant~. Rank 1116. Rating -8(+92 -100).

A. Desorting

题意

给定一个序列 \(a\)，定义操作如下：

选择一个下标 \(i \in [1, n - 1]\)；
将 \(a_1, a_2, \ldots, a_i\) 中所有元素 \(+1\)；
将 \(a_{i+1}, a_{i+2}, \ldots, a_n\) 中所有元素 \(-1\)

输出使序列 \(a\) 不是不递减序列的最小操作数。

思路

显然，我们只需贪心地认为序列中某两个相邻数满足 \(a_i > a_{i + 1}\)，就可以判定其不是不递减序列。

那么，我们先判断给定序列是否是不递减序列，如果不是，直接输出 \(0\)；

否则，我们找出相邻差值的最小值 \(d\)，答案即为 \(\frac{d}{2} + 1\)。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    bool f = true;
    for(int i=1;i<n;i++) {
        if(a[i - 1] > a[i]) f = false;
    }
    if(!f){
        cout << 0 << '\n';
        return;
    }
    int ans = inf;
    for(int i=0;i<n-1;i++){
        ans = min(ans, (a[i + 1] - a[i] + 2) / 2);
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
}

\(A\) 就整要绕一圈的思维题

B. Fibonaccharsis

题意

给定序列的最后一项 \(n\)，以及序列的长度 \(k\)，输出序列的所有数量，满足其为非负整数的斐波那契数列。

思路

首先，因为 \(2e5\) 范围内的斐波那契数列最多只有 \(20\) 多项，所以题面中的 \(k \leq 1e9\) 纯属诈骗。

那么，因为我们知道最后一项，我们直接枚举倒数第二项的值，然后倒推即可。

最后，这个序列需要满足下面的条件：

\(a_i \leq a_{i + 1}\)；
第一个数可以是 \(0\)，其余不可以是 \(0\)

暴力枚举即可。

时间复杂度：\(O(nk)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n, k;
    cin >> n >> k;
    int ans = 0;
    for(int i=n;i>=0;i--){
        int rr = n, rl = i;
        bool f = true;
        for(int j=3;j<=k;j++){
            int tmp = rr - rl;
            rr = rl, rl = tmp;
            if(rl > rr || (rl == 0 && j != k)){
                f = false;
                break;
            }
        }
        if(f) ans ++;
    }
    cout << ans << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
}

正推就寄咯

C. Ntarsis' Set

题意

给定一个升序无重复数字的数组 \(a\)，定义一次操作如下：

枚举 \(i \in [1, n]\)；
按顺序删除给定序列的第 \(a_i\) 个数。

现在，对 \(\{1, 2, 3, \ldots, inf\}\) 序列，执行 \(k\) 次操作，输出第一小的数。

思路

首先，在删除第 \(a_n\) 个数的时候，不难发现，前面删除了多少数是已知的。

也就是说，我们会固定删除 \(a_n, a_n + n, a_n + 2n, \ldots\)。

同理，我们可以发现，我们在不考虑后面的数字的时候，如果假设最后答案 \(x\) 已知，那么前 \(x - 1\) 个数的约束下，我们就可以确定我们需要删多少数了。

具体来说，我们在 \(a_1 - 1, a_2 - 2,\ldots, a_n - n\) 位置的后面加上一个 \(0\)，就可以保证需要删除的位置都是 \(0\)。至此，我们完成了将相对位置转换为绝对位置的操作。

因此，我们枚举 \(a_i\)，并考虑能在当前答案 \(ans\) 前找到多少个 \(a_i - i\)，从而更新当前答案的范围。

如果能放 \(p\) 个 \(a_i - i\)，那么范围扩大 \(i \times p\)，即可保证在所有 \(a_i\) 位置都插上了 \(0\)。

时间复杂度：\(O(n)\)

对应AC代码

#include <bits/stdc++.h>

using namespace std;

//#define FLOATING_OCEAN

#define int long long
#define pii pair<int, int>
#define pipi pair<pii, pii>
#define ppii pair<int, pii>
#define pci pair<char, int>
#define fs first
#define sc second
#define pb emplace_back
#define rall(x) x.rbegin(),x.rend()
#define all(x) x.begin(),x.end()

const int N = 2e5 + 10, M = 2e5 + 10, mod = 998244353, inf = 0x3f3f3f3f3f3f3f3f;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1, inf);
    for(int i=0;i<n;i++){
        cin >> a[i];
        a[i] -= i;
    }
    if(a[0] != 1){
        cout << 1 << '\n';
        return;
    }
    int ans = 1, inc = 1;
    while(inc < n){
        int now = (a[inc] - ans + inc - 1) / inc; //前面有多少a[inc] - inc
        if(now >= k){
            ans += k * inc;
            k = 0;
            break;
        }
        ans += now * inc;
        k -= now;
        while(a[inc] <= ans) inc ++;
    }
    cout << ans + k * n << '\n';
}

signed main() {
# ifdef FLOATING_OCEAN
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
# endif
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) solve();
}

这题做法挺多，但都很难解释，这边给出了官方题解的做法.