CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)（CF1810）A~D题题解

如果一个数字的值 \(v\)，不大于当前的位置 \(p\)，那我们可以通过删除 \(p - v\) 个数字，使它们两个对应上。

比如 \([1, 7, 2, 5, 3]\) 中的 \(3\)，其数值为 \(3\)，位置为 \(5\)，数值 \(3\) 小于等于 \(5\)，那么在 \([1, 7, 2, 5]\) 中删除任意两个数字都可以达到目的，变成 \([X, Y, 3]\)。

#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int a[N];
int n;

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) {
        if (a[i] <= i) {
            cout << "YES\n";
            return;
        }
    }
    cout << "NO\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

应为最开始的数字为奇数 \(1\)，那么 \(奇数 \times 2 \pm 1\) 也一定是奇数，那么如果运算途中出现偶数，直接判无解即可。

接下来思考有解情况，我们不妨反过来思考。

• 如果一个数字 \(y = x \times 2 + 1\)，那么 \(x = \frac{y - 1}{2}\)。
• 如果一个数字 \(y = x \times 2 - 1\)，那么 \(x = \frac{y + 1}{2}\)。

因为最终的结果为 \(n\)，那么我们只要在 \(\frac{y + 1}{2}\) 和 \(\frac{y - 1}{2}\) 中选择一个，并将它赋值给 \(n\) 即可。

那怎么选呢？因为 \(n\) 为奇数，那么 \(\frac{y + 1}{2}\) 和 \(\frac{y - 1}{2}\) 必为一奇一偶，那么肯定选择哪个奇数的就可以了。

#include <bits/stdc++.h>

using namespace std;

void solve() {
    int x;
    cin >> x;
    if (x & 1) {
        vector<int> opt;
        opt.clear();
        while (x != 1) {
            if ((x + 1 >> 1) & 1) {
                x = (x + 1) >> 1;
                opt.push_back(1);
            }
            else if ((x - 1 >> 1) & 1) {
                x = (x - 1) >> 1;
                opt.push_back(2);
            }
            else {
                cout << "-1\n";
                return;
            }
        }
        if (opt.size() > 40) {
            cout << "-1\n";
            return;
        }
        cout << opt.size() << '\n';
        for (int i = opt.size() - 1; i >= 0; i--) cout << opt[i] << ' ';
        cout << '\n';
    }
    else cout << "-1\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

我们可以枚举一个 \(i\)，

对于 \([1, i]\) 的部分可以保留下来，那我们就要将 \([1, a[i]]\) 中缺少的数字补起来，代价为 \(d \times (a[i] - i)\)，即共有 \(a[i] - i\) 个数字要加上来，每次耗费 \(d\) 的金钱。

对于 \([i + 1, n]\) 的部分可以删去，共有 \(n - i\) 个要删除的数字，代价为 \(c \times (n - i)\)。

注意：
1. 也可以一个数字也不保留，但是一定要插入一个 \(1\) 呀，题目中说的：。
2. 一定要去重，并将删除重复数字需要的代价加到结果中。
3. 注意开long long。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 100010;

int n, c, d;
int a[N];

void solve() {
    cin >> n >> c >> d;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a + 1, a + n + 1);
    int tot = unique(a + 1, a + n + 1) - a - 1;
    int ans = 0x3f3f3f3f3f3f3f3f;
    for (int i = 0; i <= tot; i++) {
        int del = (tot - i + n - tot) * c;
        int get = (a[i] - i + (i == 0)) * d;
        ans = min(ans, del + get);
    }
    cout << ans << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}

经典的小学数学奥数题。

设 \(a\) 为每天往上爬的高度，\(b\) 为每天向下降的高度，\(n\) 为给定的需要爬上去的天数。

请注意，第 \(n\) 天爬上去了，就不会下降了。

对于操作为 \(1\) 的，我们可以确定其范围。

因为要保证第 \(n\) 天就可以到达，且第 \(n - 1\) 天不能到达，所以其范围为标红部分：

用表达式表示为 \([(a - b) \times (n - 2) + a + 1, (a - b) \times (n - 1) + a]\)，其中 \((a - b) \times (n - 2) + a\) 为第 \(n - 1\) 天可以到达的最大高度 \(+1\) 才可以符合题意；\((a - b) \times (n - 1) + a\) 为第 \(n\) 天可以到达的最大高度。

需要特判 \(n = 1\) 的情况，此时其范围为 \([1, a]\)。

如果这个区间与之前之前计算的结果有交集，那么就是可以保留的，并更新区间，否则就丢弃之。

对于操作类型为 \(2\) 的，我们先计算出爬上 \(l\) 的高度需要的时间 \(t\)，计算方法如下。

假设高度为 \(h\)。

1. 首先要预留一个 \(a\)。

2. 然后计算 \(\left\lfloor\frac{h - a}{a - b}\right\rfloor\) 表示到达小于等于 \(h - a\) 的位置所需要的时间。

3. 如果刚好到达 \(h - a\) 的位置 \(+1\) 就可以了，否则 \(+2\)。

注意最好不要直接上取整，因为容易引起精度问题。

这样就计算出了 \(t\)，然后计算出花 \(t + 1\) 天爬上的高度范围是否与已知范围 \([l, r]\) 有交集，计算方法与前面的操作 \(1\) 类似，如果有那么证明不能准确获取其天数，输出 \(-1\)，否则输出天数。

注意我们不能直接判断已知范围 \(l\) 是否等于 \(r\)，因为有可能对于这一组询问在该区间内只有一种可能性，也是满足题意的。

#include <bits/stdc++.h>

#define int long long

using namespace std;

bool check(int& l1, int& r1, int l2, int r2, bool flag) {
    int ll = max(l1, l2);
    int rr = min(r1, r2);
    if (ll > rr) return false;
    if (flag) {
        l1 = ll;
        r1 = rr;
    }
    return true;
}

void solve() {
    int q;
    cin >> q;
    int opt, a, b, c;
    int l = -1, r = 1e18;
    while (q--) {
        cin >> opt;
        if (opt == 1) {
            cin >> a >> b >> c;
            int lnew = -1, rnew = -1;
            if (c == 1) lnew = 1, rnew = a;
            else lnew = (a - b) * (c - 2) + a + 1, rnew = (a - b) * (c - 1) + a;
            if (check(l, r, lnew, rnew, true)) cout << "1 ";
            else cout << "0 ";
        }
        else {
            cin >> a >> b;
            int x = l, res = 0;
            if (a >= l) {
                res = 1;
            }
            else {
                x -= a;
                res = x / (a - b);
                x = res * (a - b);
                if (x == l - a) res++;
                else res += 2;
            }
            
            c = res + 1;
            int lnew = -1, rnew = -1;
            if (c == 1) lnew = 1, rnew = a;
            else lnew = (a - b) * (c - 2) + a + 1, rnew = (a - b) * (c - 1) + a;
            if (check(l, r, lnew, rnew, false)) res = -1;
            cout << res << ' ';
        }
    }
    cout << '\n';
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) solve();
    return 0;
}