Educational Codeforces Round 24

https://codeforces.com/contest/818
有些题就是从某个角度想好复杂，不好实现，但是换一种思考方式，从另一个角度想就会豁然开朗，也很好写。这么讲很抽象，但是做题的时候会发现，自己是在一方向上耗死了，结果一看题解就觉得，哇塞tql

A. Diplomas and Certificates

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main () {
    ll n, m, k;
    cin >> n >> k;
    m = n;
    n /= 2;
    ll x = n / (k + 1);
    if ((k + 1) * x > n)    x = 0;
    cout << x << ' ' << k * x << ' ' << m - (k + 1) * x;
}

B. Permutation Game

差分构造

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 105;
int a[N], b[N], n, m;

int main () {
    cin >> n >> m;
    for (int i = 1; i <= m; i++)    cin >> b[i];
    set<int> s; //未放的数字
    for (int i = 1; i <= n; i++)    s.insert (i);
    for (int i = 1; i < m; i++) {
        int idx = b[i], dx = (b[i+1] - b[i] + n) % n;
        if (dx == 0)    dx = n;
        if ((a[idx] && a[idx] != dx) || (!a[idx] && !s.count (dx))) {
            cout << -1;
            return 0;
        }
        s.erase (dx), a[idx] = dx;
        //cout << idx << ' ' << dx << endl;
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == 0)  a[i] = *s.begin (), s.erase (s.begin ());
        cout << a[i] << ' ';
    }
}

C. Sofa Thief

D. Multicolored Cars

这个就是要换一个角度去想，记录不可能来check

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1e5 + 5;
int a[N], n, A;

int main () {
    scanf ("%d%d", &n, &A);
    for (int i = 1; i <= n; i++)    scanf ("%d", &a[i]);
    map<int, int> mp;
    set<int> s;
    for (int i = 1; i <= 1e6; i++)  s.insert (i);
    s.erase (A);
    for (int i = 1; i <= n; i++) {
        mp[a[i]] ++;
        if (a[i] != A) {
            if (mp[a[i]] <= mp[A])  s.erase (a[i]);
        }
    }
    for (auto i : s) {
        if (mp[i] >= mp[A]) {
            printf ("%d", i);
            return 0;
        }
    }
    printf ("-1");
}

//每个阶段可能的答案取个交集

E. Card Game Again

半暴力优化查找
再已知确实有答案(前/后缀乘积)的情况下,找到最小区间
记录上一个位置防止重复查找
特别关注循环边界的退出条件！！

#include <bits/stdc++.h>
#define ll long long

using namespace std;
const int N = 1e5 + 5;
ll a[N], n, k;

int main () {
    cin >> n >> k;
    ll ans = 0, lst = n, mul = 1;
    for (int i = 1; i <= n; i++)    cin >> a[i];
    for (int i = n, j; i >= 1; i--) {
        mul = mul * a[i] % k;
        if (mul)    continue;
        mul = 1;
        for (j = i; mul * a[j] % k; ) {
            mul = mul * a[j++] % k;
            if (mul * a[j] % k == 0) { //最小区间[i,j]
                break;
            }
        }
        ans += i * (lst - j + 1);
        lst = j - 1;
    }
    cout << ans << endl;
}

//半暴力优化查找
//再已知确实有答案(前/后缀乘积)的情况下,找到最小区间
//记录上一个位置防止重复查找

F. Level Generation

G. Four Melodies