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

A. Beautiful Sequence

题意

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

思路

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

时间复杂度：

对应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

题意

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

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

思路

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

我们判断 的奇偶性，若为奇数，那么 ，否则 。

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

时间复杂度：

对应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

题意

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

1. 删除一个元素，代价为 ；

2. 插入一个元素，代价为 。

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

思路

贪心。

我们先记最后的答案为 。

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

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

1. ，那么不用管之

2. ，我们需要比较一下删除这个元素和补上缺少的数的代价。

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

而补全数字的代价为 ，也就是说，更新后的总价值为 。

因此，我们比较 和 即可。

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

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

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

时间复杂度：

对应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

题意

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

定义询问为下者二选一：

1. ，表示给定一组限制，在 的条件下在第 爬到顶。若限制不满足前面得到的范围，输出 ；否则输出 ，并更新 的可能范围；

2. ，判定这个条件下所需天数是否有唯一解，有的话输出，否则输出 。

思路

首先，这是一道数学题。

我们先来考虑第一个：

如果它要在第 天到达，首先前提是第 天不会到达，也就是说，；

其次，爬到顶的条件是距离树的顶部小于等于 ，也就是说，。

所以，若原求得的区间和 有交集，那么更新区间为两者交集，否则输出 。

我们记得到的 。

我们再来看看第二个：

首先，如果能一步登天，即 ，那么直接输出 即可。

否则，我们只需满足一个不等式：。

化简可得：

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

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

时间复杂度：

对应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位交即可.