Contestant. Rank 1247. Rating +30.

A. Walking Master

题意

给定两个点 ，定义对于点 的操作为下面任选一：

1. ；

输出从 走到 需要的最小操作数，无解输出 。

思路

画个图即可。

首先，我们需要向上移动 ，如果 就是无解。

此时，横坐标变为 ，还需要向左移动 ，如果 也是无解。

若有解，输出 。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

const int N = 2e5 + 10;

void solve(){
    int a, b, c, d;
    cin >> a >> b >> c >> d;
    if(b > d || a + d - b < c) cout << -1 << '\n';
    else cout << a + d - b - c + d - b << '\n';
}

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

就还是那么签（

B. Mex Master

题意

给定一个序列，定义答案为 由相邻数相加构成的新序列中 不在 这个序列中的 最小自然数。将序列重新排序，输出最小答案。

思路

首先，若 的个数小于等于 ，那么一定可以在连续的两个 里面插入一个数，使最后的序列没有 ，答案即为 ；

其次，若整个序列的最大值大于 ，那么我们只需将 全部放到后面，然后第一个 之前不要放 即可，答案即为 ；

接着，若整个序列的最大值为 ，那么一定有一个 会和 去相加，使最后的序列出现 ，而因为 的个数足够多，我们只需在所有 之间插 ，就可以避免出现 ，答案即为 ；

否则，整个序列都是 ，答案一定是 。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void solve(){
    int n;
    cin >> n;
    map<int, int> cnt;
    int mx = 0;
    for(int i=0;i<n;i++) {
        int cur;
        cin >> cur;
        mx = max(mx, cur);
        cnt[cur] ++;
    }
    if(cnt[0] <= (n + 1) / 2) cout << 0 << '\n';
    else if(cnt[0] == n) cout << 1 << '\n';
    else cout << (mx == 1 ? 2 : 1) << '\n';
}

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

一开始想错了（（

C. Sequence Master

题意

若一个长为 的序列，它的所有长度为 的子序列满足选定的数的 乘积 与剩余数的 和 相等，那么定义其为好序列。

给定一个长为 的序列 ，选定一个好序列，定义答案为 ，输出答案的最小值。

思路

猜想

首先，我们来以小见大，看看 如何成为一个好序列：

拿出其中两个式子：，我们可以得出 或 。

同理，那么我们不妨猜测整个序列都是相等的数 ，或者会有至少一个数 不是 。

讨论1

下面我们来探讨一下第一个条件的局限性：

1. 首先，它是一定成立的，毕竟 一定是一个解，但可能出现其他解；

2. 若只有两个数，那么 可以为任意值；

3. 若只有四个数，满足 ，；

4. 若超过四个数，那么我们不难发现 对于 为偶数的情况下是无整数解的。

讨论2

下面我们来探讨一下第二个条件的局限性：

1. 我们无法让大于等于 个数不为 ，列式可发现无实数解；

2. 为奇数的时候，依然无解；

3. 其余情况，我们可以解得 。

总结

最后，答案即为上面条件所算出的答案的最小值。

时间复杂度：

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>

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

void solve(){
    int n;
    cin >> n;
    int ans = inf;
    vector<int> a(2 * n);
    for(int i=0;i<2*n;i++) cin >> a[i];
    if(n == 1){
        if(a[0] > a[1]) swap(a[0], a[1]);
        ans = a[1] - a[0];
    }else if(n == 2){
        ans = 0;
        for(int i=0;i<4;i++) ans += abs(a[i] - 2);
    }
    if(n % 2 == 0){
        int mn = inf, sum = 0;
        for(int i=0;i<2*n;i++){
            sum += abs(a[i] + 1);
            mn = min(mn, abs(a[i] - n) - abs(a[i] + 1));
        }
        ans = min(ans, sum + mn);    
    }
    int sum = 0;
    for(int i=0;i<2*n;i++) sum += abs(a[i]);
    ans = min(ans, sum);
    cout << ans << '\n';
}

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

漏了奇数的情况，md

有更直接的做法，这里比较麻烦