Codeforces——870

A. Trust Nobody

题目大意

给你一个长度为\(n\)的数组\(a\)，\(a\)中每个元素\(a_i\)表示当前人认为\(n\)个人中至少有\(a_i\)个人说谎，让你找出说谎的人的个数。

思路：

枚举说谎人数\(x\)，遍历\(a\)数组，对于当前\(a_i\)，如果有\(a_i \geq x\)，那么显然第\(i\)个人在说谎，记录人数看是否等于 \(x\)即可。

代码：

#include <bits/stdc++.h>

void solve() {
    int n;
    std::cin >> n;

    std::vector<int> a(n);

    for (int i = 0; i < n; ++i) std::cin >> a[i];

    int ans = -1;
    for (int cnt = 0; cnt <= n; ++cnt) {
        int cur = 0;
        for (int num : a) {
            if (num > cnt) cur++;
        }
        if (cur == cnt) {
            std::cout << cnt << "\n";
            return;
        }
    }
    std::cout << -1 << "\n";
}

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) solve();

    return 0;
}

B. Lunatic Never Content

题目大意

给你一个包含\(n\)个非负整数的数组\(a\)，定义\(f{(a, x)}\)= \([a_1modx,a_2modx,…,a_nmodx]\)，找出最大的\(x\)，是的\(f{(a, x)}\)是回文数组，如果\(x\)的值可能为无穷大，输出0代替

思路

对于回文序列，它必须满足\(b_i=b_{n−i+1}\)，在我们的情况下\(b_i=a_i（mod\ x）\)，将回文方程重写为\(a_i（mod\ x）=a_{n−i+1}（mod\ x）\)，移项得：\(a_i−a_{n−i+1}\equiv0（mod\ x）\)，也就是说\(x\)可以被\(a_i - a_{n-i-1}\)整除，那么找最大的\(x\)也就转换为找\(GCD(a_i, \ a_{n-i-1}) \ for \ all \ i\)。

代码

#include <bits/stdc++.h>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n);
    int ok = 1;
    for (int i = 0; i < n; ++i) {
    	std::cin >> a[i];
    }
    for (int i = 0; i < n / 2; ++i) {
    	if (a[i] != a[n - i - 1]) {
            ok = 0;
            break;
        }
    }

    int ans = 0;
    for (int i = 0; i < n / 2; ++i) {
        int d = a[i] - a[n - i - 1];
        ans = std::__gcd(ans, abs(d));
    }

    if (ok) std::cout << "0\n";
    else std::cout << ans << "\n";
}

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) solve();

    return 0;
}

C. Dreaming of Freedom

题目大意

给你\(n\)个人， \(m\)个选项，\(n\)个人每轮都会进行投票，在每轮结束后，会去掉得票最多的那个选项，问能否使得投票无限进行下去。

思路

枚举\(n\)的所有的\(\ge2\)的因子\(d\)，如果存在 \(d\)使得 \(n \% d=0\)并且 \(d\le m\)那显然游戏可以一直进行下去，先每次都投给某个选项，踢掉它，直到使得选项数目等于\(d\)，然后每次均匀投票即可。

代码

#include <bits/stdc++.h>

void solve() {
	int n, m;
    std::cin >> n >> m;
    int ok = 1;
    for (int i = 1; i * i <= n; ++i) 
        if (n % i == 0) {
            if (2 <= i and i <= m) ok = 0;
            if (2 <= n / i and n / i <= m) ok = 0;
        }
    
    if (ok) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) solve();

    return 0;
}

D. Running Miles

题目大意

有一条街道上有\(n\)个景点，第\(i\)个景点距离街道起点\(i\)英里，第\(i\)个景点有美丽值\(b_i\)。你想要在街道上跑步，从第\(l\)英里开始跑步，到第\(r\)英里结束。你可以看到你跑步经过的景点（包括第\(l\)英里和第\(r\)英里的景点）。选择\(l\)和\(r\)，使得你经过的景点中至少有三个，且三个最美丽的景点的美丽值之和减去你需要跑的英里数最大化。

选择\(l\)和\(r\)，使得\(b_{i1}+b_{i2}+b_{i3}-(r-l)\))最大化，其中\(i1\)、\(i2\)和\(i3\)是范围\([l，r]\)中三个最大元素的索引。

思路

贪心

要使得\(b_l - l + b_r + r + b_{mid}\)的值最大，我们可以将原式看成三部分，\(b_l - l\)，\(b_{mid}\)，\(b_r + r\)使得这三项分别是最大值即可。那么我们可以维护\(b_i - i\)的前缀最大值数组，\(b_r + r\)的后缀最大值数组，然后枚举中心点\(mid\)即可

代码

#include <bits/stdc++.h>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
    	std::cin >> a[i];
    }
	
    //vl维护的是前缀a_l + l
    //vr维护的是后缀a_r - r
    std::multiset<int> vl, vr;

    for (int i = 3; i <= n; ++i) vr.insert(a[i] - i);
    vl.insert(a[1] + 1);
    int ans = 0;
    for (int i = 2; i < n; ++i) {
        auto itl = vl.rbegin(), itr = vr.rbegin();
        ans = std::max(ans, (*itl + *itr + a[i]));
        vl.insert(a[i] + i);
        vr.erase(vr.find(a[i + 1] - i - 1));
    }
    std::cout << ans << "\n";
}

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) solve();

    return 0;
}

动态规划

定义\(dp1[i]\)表示\(1-i\)范围内的的\(a_i - i\)的最大值，\(dp2[i]\)表示\(1-i\)范围内\(a_l - l + a_{mid}\)的最大值。

​ \(dp1[i] = max(dp1[i - 1],\ a[i] - i)\)

​ \(dp2[i] = max(dp2[i - 1], \ dp1[i -1] + a[i])\)

那么当前答案即为 \(max(ans, \ dp2[i - 1] + a[i] + i) \ \ \ \ \ \ \ \ (i \ge 3)\)

代码

#include <bits/stdc++.h>

void solve() {
    int n;
    std::cin >> n;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; ++i) {
    	std::cin >> a[i];
    }

    //DP
    std::vector<int> dp1(n + 1), dp2(n + 2);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        dp1[i] = std::max(dp1[i - 1], a[i] + i);
        dp2[i] = std::max(dp2[i - 1], dp1[i - 1] + a[i]);
        if (i >= 3) {
            ans = std::max(ans, dp2[i - 1] + a[i] - i);
        }
    }
    std::cout << ans << "\n";
}

int main() {
    std::cin.sync_with_stdio(false);
    std::cin.tie(0);
    int t;
    std::cin >> t;
    for (int i = 1; i <= t; ++i) solve();

    return 0;
}