Contestant(alt). 开摆Rank 5778. Rating -11(+89 -100).

A. Beautiful Sequence

题意

给定一个序列，输出是否存在一个子序列，存在一个元素满足 $a_i = i$。

思路

显然，我们只需遍历一遍序列，找出一个 $a_i$，满足 $a_i \leq i$ 即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

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

void init(){}

void solve() {
    int n;
    cin >> n;
    bool f = false;
    for(int i=1;i<=n;i++){
        int cur;
        cin >> cur;
        if(cur <= i) f = true;
    }
    cout << (f ? "YES\n" : "NO\n");
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t --) solve();
}

水

B. Candies

题意

对于一个数 $x$，定义操作如下：

$x :=2x + 1$
$x := 2x - 1$

给定一个若干次操作后的数，判断初始值是否为 $1$，并输出方案。

思路

首先，得到的数都是奇数，所以我们从这里下手即可。

我们判断 $\frac{x-1}{2}$ 的奇偶性，若为奇数，那么 $x := \frac{x-1}{2}$，否则 $x := \frac{x + 1}{2}$ 。

可以断定，只要一开始 $x$ 不是偶数，最后的结果一定是 $1$。

时间复杂度：$O(\log_2n)$

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

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

void init(){}

void solve() {
    int n;
    cin >> n;
    if(n % 2 == 0) {
        cout << -1 << '\n';
        return;
    }
    vector<int> ans;
    while(n > 1){
        if((n - 1) / 2 % 2 == 0) n = (n + 1) / 2, ans.emplace_back(1);
        else n = (n - 1) / 2, ans.emplace_back(2);
    }
    reverse(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(auto e : ans) cout << e << ' ';
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t;
    cin >> t;
    while(t --) solve();
}

你说我这脑子怎么就转不过来呢

C. Make It Permutation

题意

给定一个序列，定义操作为下面两者任选其一：

删除一个元素，代价为 $c$；
插入一个元素，代价为 $d$。

找出代价最小的一种方案，使最后的序列变为任意长度的排列，输出最小代价。

思路

贪心。

我们先记最后的答案为 $cost$。

首先，我们不妨先把序列排个序，然后用 $unique$ 剔除重复元素，毕竟重复元素是一定要删去的，我们记剔除这些元素的总代价为 $rm$。

然后，我们从大到小遍历，处理相邻的两个数。对于这两个数，我们定义差值为 $dist$，以及右边那个数的后面还有 $cnt$ 个数字。那么，我们有两种处理：

$dist=1$，那么不用管之
$dist > 1$，我们需要比较一下删除这个元素和补上缺少的数的代价。

需要注意的是，如果我们决定删除这个数，那么后面的数都要一并删去。因为后面的数不删去的话，需要补全的数就更多了，而我们已经判定删除的代价更小。也就是说，删除后总代价更新为 $rm + c (cnt + 1)$。

而补全数字的代价为 $d(dist-1)$，也就是说，更新后的总价值为 $cost+d(dist-1)$。

因此，我们比较 $cost+d(dist-1)$ 和 $rm + c (cnt + 1)$ 即可。

需要注意的是，当第一个数不是 $1$ 的时候，我们不能删完所有数，所以一定会出现补全的代价。

到这里并没有结束，你会发现样例过不去。

这里有个有趣的点，我们为何不直接删掉所有数，然后放一个 $1$ 进去呢？我们将其和答案取最小值即可。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e7 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int n, c, d;
    cin >> n >> c >> d;
    //反着做，看看删掉和补充哪个赚
    vector<int> a(n);
    for(int i=0;i<n;i++) cin >> a[i];
    sort(a.begin(), a.end());
    int rm = a.size(), sz = unique(a.begin(), a.end()) - a.begin();
    rm -= sz;
    if(a[0] != 1) a.insert(a.begin(), 0ll), sz ++;
    int cost = rm * c;
    for(int i=sz-1;i>0;i--){
        int dis = a[i] - a[i - 1] - 1;
        if(a[i - 1] != 0 && cost + dis * d > rm * c + c * (sz - i)){
            cost = rm * c + c * (sz - i);
        }else cost += dis * d;
    }
    cout << min(d + c * n, cost) << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

简单的贪心捏，就是我怎么老搞错（

D. Climbing the Tree

题意

定义一个蜗牛在爬树，每天上升 $a$，下降 $b$，当某一天距离树的顶部小于等于 $a - 1$ 时，即可爬到顶。树的高度记为 $h$。

定义询问为下者二选一：

$1\ a\ b \ n$，表示给定一组限制，在 $a, b$ 的条件下在第 $n$ 爬到顶。若限制不满足前面得到的范围，输出 $0$；否则输出 $1$，并更新 $h$ 的可能范围；
$2\ a\ b$，判定这个条件下所需天数是否有唯一解，有的话输出，否则输出 $-1$。

思路

首先，这是一道数学题。

我们先来考虑第一个：

如果它要在第 $n$ 天到达，首先前提是第 $n - 1$ 天不会到达，也就是说，$h \geq (a - b)(n - 1) + b$；

其次，爬到顶的条件是距离树的顶部小于等于 $a - 1$，也就是说，$h \leq (a - b)(n - 1) + (a - 1)$。

所以，若原求得的区间和 $[(a - b)(n - 1) + b, (a - b)(n - 1) + (a - 1)]$ 有交集，那么更新区间为两者交集，否则输出 $0$。

我们记得到的 $h \in [lh, rh]$。

我们再来看看第二个：

首先，如果能一步登天，即 $a - 1 \geq rh$，那么直接输出 $1$ 即可。

否则，我们只需满足一个不等式：$(a - b)(n - 1) + b \leq h \leq (a - b)(n - 1) + (a - 1)$。

化简可得：

$ \[\begin{cases} n \leq \frac{h - b}{a - b} + 1 \\ n \geq \frac{h - (a - 1)}{a - b} + 1\end{cases}\]

那么，我们把 $rh$ 带入第一个式子，$lh$ 带入第二个式子，即可求出 $n$ 的所有可能范围。

那么，我们判断一下左右端点取整后是否相等即可。注意，右端点向下取整，左端点向上取整，因为这样取整后得到的区间是在原区间内的最长区间。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second

const int N = 2e7 + 10, inf = 0x3f3f3f3f3f3f3f3f;

void init(){}

void solve() {
    int q;
    cin >> q;
    int lh = -1, rh = inf;
    while(q --){
        int tp;
        cin >> tp;
        if(tp == 1){
            int a, b, n;
            cin >> a >> b >> n;
            int now = (a - b) * (n - 1);
            int now_l = n == 1 ? 0 : now + b, now_r = n == 1 ? a - 1 : now + a - 1;
            if(a <= b || now_l > rh || now_r < lh) cout << 0 << ' ';
            else{
                cout << 1 << ' ';
                lh = max(lh, now_l), rh = min(rh, now_r);
            }
        }else{
            int a, b;
            cin >> a >> b;
            if(a > rh) {
                cout << 1 << ' ';
                continue;
            }
            int min_x = (int) ceil((double) (lh - (a - 1)) / (double) (a - b)) + 1, max_x = (int) floor((double) (rh - (b)) / (double) (a - b)) + 1;
            if(min_x != max_x) cout << -1 << ' ';
            else cout << min_x << ' ';
        }
    }
    cout << '\n';
}

signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    int t = 1;
    cin >> t;
    while(t --) solve();
}

别用 C++ 64位交即可.