A - Circle of Apple Trees

答案就是 distinct numbers 的数量。std::unique 一下即可。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T, N) std::array<T, N>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;

int n;

void Run() {
    std::cin >> n;
    std::vector<int> a(n);
    repeat(i, 0, n - 1) std::cin >> a[i];
    std::sort(all(a));
    a.erase(std::unique(all(a)), a.end());

    std::cout << a.size() << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
#endif

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

B - Bitwise Reversion

因为是 bitwise and，所以每一位之间是互相独立的。考虑 x,y,zx,y,z 在 ii-th bit 上分别取 0,10,1（共 88 种情况），发现，如果 a,b,ca,b,c 中有 22 个数，其 ii-th bit 为 11，那么就是不可能的。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T, N) std::array<T, N>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

int a, b, c;
constexpr int N = 50;

void Run() {
    std::cin >> a >> b >> c;
    until(i, N, 0) {
        auto get = [&](int x) { return x >> i & 1; };
        int f = get(a) + get(b) + get(c);
        if (f == 2) {
            std::cout << "NO\n";
            return;
        }
    }
    std::cout << "YES\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
#endif

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

C - Symmetrical Polygons

唉可惜啊，浪费了太多时间在这个上面

考虑先贪心地把所有可以成对的棍子 ℓi\ell_i 放进来。这样最后就剩下了一些单根木棍，记其集合为 ℓi∈R\ell_i\in R。假设所有已选的木棍集合为 si∈Ss_i\in S.

因为要对称，所以最多只能放两根单根木棍进来. 如果不加木棍，答案已经求出来了；如果只加一根木棍，那么我们枚举木棍长度，一根木棍 ℓ\ell 能放进来的条件是

2max⁡{ ℓ,si }<ℓ+∑si∈Ssi 2\max\set{\ell, s_i}\lt \ell + \sum_{s_i\in S}s_i

如果可以加两根木棍，那么因为要让最终周长最长，我们一定选择的是 ℓi>ℓi−1\ell_i\gt\ell_{i-1} 即两根长度相邻的木棍.

如果 ℓi,ℓi−1\ell_i, \ell_{i-1} 无法与其他木棍组成多边形，此时有

2max⁡{ ℓi,si }≥ℓi+ℓi−1+∑si∈Ssi2\max\set{\ell_i, s_i}\ge \ell_i+\ell_{i-1}+\sum_{s_i\in S} s_i

那么 ℓi\ell_i 和 ℓj,j<i−1\ell_j, j\lt i-1 也必然无法组成. 因为左式不变，而右式更小.

细节是，还需要判断最终选出来的边是否可以围成多边形。时间复杂度 O(nlog⁡n)O(n\log n)

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T, N) std::array<T, N>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10;
ll n, a[N];

void Run() {
    std::cin >> n;
    std::map<ll, ll> cnt;

    repeat(i, 1, n) {
        std::cin >> a[i];
        cnt[a[i]]++;
    }

    ll ans = 0, ecnt = 0;
    std::vector<ll> rm;
    for (auto &[x, c] : cnt) {
        ans += x * (c - c % 2);
        ecnt += c - c % 2;
        c %= 2;
        if (c == 0) rm.push_back(x);
    }
    for (auto x : rm) cnt.erase(x);
    rm.clear();

    // invalid
    if (ecnt == 0) {
        std::cout << "0\n";
        return;
    }
    // no more single
    if (cnt.size() == 0) {
        std::cout << (ecnt == 2 ? 0 : ans) << "\n";
        return;
    }

    // select one
    ll tans = ans;
    for (auto it = cnt.begin(); it != cnt.end(); it++) {
        auto [x, c] = *it;
        assert(c == 1);
        if (x < ans) tans = std::max(tans, ans + x);
    }

    // select 2
    ll fans = ans;
    if (cnt.size() >= 2) {
        auto it = cnt.rbegin(), iit = std::next(it);

        while (true) {
            if (iit == cnt.rend()) break;
            if (ans + iit->first > it->first) fans = std::max(ans + iit->first + it->first, fans);
            it++, iit++;
        }
    }

    ll fe = ecnt;
    if (tans > ans) fe = ecnt + 1, ans = tans;
    if (fans > ans) fe = ecnt + 2, ans = fans;

    std::cout << (fe >= 3 ? ans : 0) << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
#endif

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

D - Not Alone

首先假设我们想调整 kk 个数到相同的值，不妨设 −∞=a0<a1≤a2≤⋯≤ak<ak+1=∞-\infin=a_0\lt a_1\le a_2\le \dots\le a_k\lt a_{k+1}=\infin，假设都调整到 vv，则最终需要的步数为

∑i=1k∣ai−v∣ \sum_{i=1}^k |a_i-v|

我们希望这个步数越小越好，所以应该取中位数。

接下来考虑五个数，ai≤ai+1a_i\le a_{i+1}，如果泉币改到 a3a_3，则花费为 a5+a4−a2−a1a_5+a_4-a_2-a_1；而如果分成 2+32+3，那么花费为 a5+a2−a3−a1a_5+a_2-a_3-a_1，或者 a5+a3−a4−a1a_5+a_3-a_4-a_1，可见都比它小。所以最佳决策是每一块的长度为 2,32,3.

所以可以直接 DP\tt{DP}，需要特殊处理一下 1,2,n−1,n1,2,n-1,n 这几个位置作为开头。

AC Code
 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
#define mid(l, r) (l + ((r - l) >> 1))
#define sz(x) (int(x.size()))
#define repeat(i, a, b) for (int i = (a); i <= (b); i++)
#define until(i, a, b) for (int i = (a); i >= (b); i--)
#define array_of(T, N) std::array<T, N>
#define all(x) x.begin(), x.end()
#define range(x, a, b) x + a, x + b + 1
using ll = long long;
using vi = std::vector<int>;
using pii = std::pair<int, int>;

constexpr int N = 2e5 + 10, N2 = 4e5 + 10;
constexpr ll inf = 1e18;

ll n, a[N2];
ll dp[N2];

int gn(int i) { return i == n ? 1 : (i + 1); }
int ggn(int i) { return gn(gn(i)); }
ll c3(int i) { return std::max({a[i], a[gn(i)], a[ggn(i)]}) - std::min({a[i], a[gn(i)], a[ggn(i)]}); }
ll c2(int i) { return std::abs(a[i] - a[gn(i)]); }

void Run() {
    std::cin >> n;
    repeat(i, 1, n) std::cin >> a[i];

    auto dppath = [&](int L, int R) -> ll {
        if (L > R) return 0;
        // repeat(i, 1, L - 1) dp[i] = 0;
        // repeat(i, L, n + 1) dp[i] = inf;
        dp[L - 1] = 0;
        repeat(i, L, R) {
            ll best = inf;
            if (i - 2 >= L - 1) best = std::min(best, dp[i - 2] + c2(i - 1));
            if (i - 3 >= L - 1) best = std::min(best, dp[i - 3] + c3(i - 2));
            dp[i] = best;
        }
        return dp[R];
    };

    ll ans = inf;
    // std::cerr << c2(1) << " " << c2(n) << " " << c3(1) << " " << c3(n) << " " << c3(n - 1) << "\n";
    ans = std::min(
        {ans,
         c2(1) + dppath(3, n),
         c2(n) + dppath(2, n - 1),
         c3(1) + dppath(4, n),
         c3(n) + dppath(3, n - 1),
         c3(n - 1) + dppath(2, n - 2)}
    );

    std::cout << ans << "\n";
}

int main() {
#ifdef ONLINE_JUDGE
    std::cin.tie(0)->sync_with_stdio(0);
    std::cout.tie(0), std::cerr.tie(0);
#endif

    int t = 1;
    std::cin >> t;
    while (t--) Run();
}

E - Zero Trailing Factorial

F - Odd Queries on Odd Array

Codeforces
License

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。