Contestant'. Rank 1818. Rating +61(+561 -500).

A. Trust Nobody

题意

定义一群人中有一定数量的人撒谎。对于每个人 \(i\)，会给出他所说的撒谎的人至少有 \(a_i\) 人。输出撒谎的人的数量。

思路

我们直接遍历撒谎的人的数量 \(x\)，然后枚举 \(a_i > x\) 的数量，从而如果数量和 \(x\) 一致，我们就找到了答案。

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

对应AC代码

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define pii pair<int, int>
#define fs first
#define sc second
#define pb emplace_back
#define all(x) x.begin(), x.end()

const int N = 2e6, mod = 1e9 + 7;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int i=0;i<=n;i++){
        int cnt = 0;
        for(int j=1;j<=n;j++){
            if(a[j] > i) cnt ++;
        }
        if(i == cnt) {
            cout << i << '\n';
            return;
        }
    }
    cout << -1 << '\n';
}

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

一开始题目看错了，卡了半天（

B. Lunatic Never Content

重题了。原题链接：Abu Tahun Mod problem

题意

给定一个序列，找出最大的 \(x\)，满足将序列中所有元素对 \(x\) 取模后得到的新序列回文。

思路

首先，对于两个数，如果我们希望取模后的值相等，那么这两个数应该可以写成 \(k_1x + p, k_2x + p\)。

想让 \(x\) 尽可能大，那么就需要 \(k_1\) 和 \(k_2\) 尽可能小。

于是，我们不妨将差值的绝对值作为 \(x\)，这样即可让 \(x\) 尽可能大。

那么因此，我们会得到多组限制。

如果对于两个限制 \(x_1 = abs(a_i - a_{n - i + 1}), x_2 = abs(a_j - a_{n - j + 1})\)，要满足这两个限制，新的 \(x' = gcd(x_1, x_2)\)，

为何呢？不难证明如果两个数\(\mod x\) 后的值相等，那么如果 \(y\) 是 \(x\) 的因数，两个数\(\mod y\) 后的值也相等。

当然，如果差值为 \(0\)，就不需要参与计算了。

时间复杂度：\(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
#define pb emplace_back
#define all(x) x.begin(), x.end()

const int N = 2e6, mod = 1e9 + 7;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    if(n == 1){
        cout << 0 << '\n';
        return;
    }
    int ans = abs(a[1] - a[n]);
    for(int i=2;i<=n/2;i++){
        if(ans) ans = gcd(ans, abs(a[i] - a[n + 1 - i]));
        else ans = abs(a[i] - a[n + 1 - i]);
    }
    cout << ans << '\n';
}

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

好快的签

C. Dreaming of Freedom

题意

给定 \(n\) 个人和 \(m\) 个选择，每轮中每个人可以对任意一个选择投票，每轮结束后将会保留投票数最多的几个选择，并继续下一轮。如果可以无穷继续下去，输出 \(NO\)；否则如果最后可以确定一个选择，输出 \(YES\)。

思路

我们遍历 \(n\) 的所有质因子 \(x\)，如果 \(x \leq m\)，那么我们扔掉 \(m - x\) 个选择，对于剩下的 \(x\) 个选择，只需每个选择都有 \(\frac{n}{x}\) 票即可无穷继续下去。

那么，如果暴力枚举因子，我们会超时。

也许会想到枚举到根号，但如果我们恰好碰到了个质数 \(n\)，我们就寄了。

为何呢？因为质因子 \(n\) 没有被我们枚举到。

为了避免这样，我们直接加一个特判，如果 \(n \leq m\)，输出 \(NO\) 即可。

当然，如果 \(n = 1\)，一定可以确定一个选择（因为只有一个），所以再加一个特判。

时间复杂度：\(O(\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
#define pb emplace_back
#define all(x) x.begin(), x.end()

void solve(){
    int n, m;
    cin >> n >> m;
    if(m == 1 || n == 1){
        cout << "YES\n";
        return;
    }
    if(n <= m){
        cout << "NO\n";
        return;
    }
    for (int i = 2; i * i <= n; i ++) {
        if(n % i == 0){
            if(i <= m){
                cout << "NO\n";
                return;
            }
        }
    }
    cout << "YES\n";
}

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

被坑死了

D. Running Miles

题意

给定一个序列，确定一个长度大于等于 \(3\) 的区间 \([l, r]\)，区间的价值为最大的三个数减去 \(r - l\)。

输出最大的价值。

思路

我们不妨直接将 \(-r, +l\) 体现到序列中。

具体地说，我们确定中间的元素 \(a_i\)，那么前 \(i - 1\) 个元素中加上其下标后的最大值和后 \(n - i - 1\) 个元素中减去其下标后的最大值与 \(a_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
#define pb emplace_back
#define all(x) x.begin(), x.end()
#define r_all(x) x.rbegin(), x.rend()

const int inf = 0x3f3f3f3f3f3f3f3f;

void solve(){
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for(int i=1;i<=n;i++) cin >> a[i];
    vector<int> l(n + 2, -inf), r(n + 2, -inf);
    for(int i=1;i<=n;i++) l[i] = max(l[i - 1], a[i] + i);
    for(int i=n;i>=1;i--) r[i] = max(r[i + 1], a[i] - i);
    int ans = -inf;
    for(int i=1;i<=n;i++) ans = max(ans, l[i - 1] + a[i] + r[i + 1]);
    cout << ans << '\n';
}

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

学习了学习了（