[C++知识库]Codeforces Round #773 (Div. 2) A～D

有空就写题解

A. Hard Way

思路

签到
特判，一条边平行于 $y=0$ 的直线，且第三个点在该边下方

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t -- ) {
        int x1, y1, x2, y2, x3, y3;
        cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
        if (y1 == y2 && y1 && y3 < y1) {
            printf("%d\n", abs(x1 - x2));
        } else if (y2 == y3 && y2 && y1 < y2) {
            printf("%d\n", abs(x3 - x2));
        } else if (y1 == y3 && y1 && y2 < y1) {
            printf("%d\n", abs(x1 - x3));
        } else {
            printf("%d\n", 0);
        }
    }
    return 0;
}

B. Power Walking

思路

签到

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while (t -- ) {
        int n;
        map<int, int> mp;
        scanf("%d", &n);
        for (int i = 1; i <= n; i ++ ) {
            int a;
            scanf("%d", &a);
            mp[a] ++;
        }
        int cnt = mp.size();
        for (int i = 1; i <= n; i ++ ) 
            if (i <= cnt) printf("%d ", cnt);
            else printf("%d ", i);
        puts("");
    }
    return 0;
}

C. Great Sequence

思路

签到

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
char str[N];
int main() {
    int t;
    scanf("%d", &t);
    while (t -- ) {
        int n, x;
        map<int, int> mp;
        scanf("%d%d", &n, &x);
        for (int i = 1; i <= n; i ++ ) {
            int a;
            scanf("%d", &a);
            mp[a] ++;
        }
        int ans = 0;
        for (auto [val, cnt] : mp) {
            if (1ll * val * x <= 1e9 && mp[val * x]) {
                int num = mp[val * x];
                mp[val * x] -= min(num, cnt);
                mp[val] -= min(num, cnt);
            }
            ans += mp[val];
        }
        printf("%d\n", ans);
    }
    return 0;
}

优化版

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    scanf("%d", &t);
    while (t -- ) {
        int n, x;
        scanf("%d%d", &n, &x);
        multiset<int> st;
        VI a(n);
        for (int i = 0; i < n; i ++ ) scanf("%d", &a[i]);
        sort(a.begin(), a.end());
        for (int i = 0; i < n; i ++ ) {
            if (a[i] % x == 0 && st.find(a[i] / x) != st.end()) {
                st.erase(st.find(a[i] / x));
            } else st.insert(a[i]);
        }
        printf("%d\n", st.size());
    }
    return 0;
}

D. Repetitions Decoding

思路

每两个一样的数消除一次，最多要 $n$ 个操作，那么 $q$ 最多为 $n^2/2$，每次从后面开始找，每找到就往前面插入数字，然后消除这两个一样的数字。算了，举例子吧
3 2 1 1 2 3
操作 1：2 2 3 2 1 1 2 3
操作 2：2 1 1 2 3 2 1 1 2 3
操作 3：2 1 1 1 1 2 3 2 1 1 2 3
操作 4：2 1 1 2 2 1 1 2 3 2 1 1 2 3
2 1 1 2
操作 1：1 1 2 1 1 2
操作 2：1 1 1 1 2 1 1 2
1 1
操作 1：1 1 1 1

#include <bits/stdc++.h>
using namespace std;
void work() {
    int n;
    cin >> n;
    VI a(n);
    for (int i = 0; i < n; i ++ ) cin >> a[i];
    vector<PII> res;
    VI len;
    while (a.size()) {
        int i = a.size() - 1, j = i - 1;
        for (; j >= 0; j -- ) 
            if (a[j] == a[i]) 
            	break;
        if (j == -1) {
            cout << -1 << endl;
            return;
        }
        for (int k = 0; k < i - j - 1; k ++ ) 
            res.PB({j + k, a[i - k - 1]});
        reverse(a.begin() + j, a.end() - 1);
        len.PB(2 * (i - j));
        a.pop_back(), a.pop_back();
    }
    cout << res.size() << endl;
    for (auto [p, c] : res) 
        cout << p << ' ' << c << endl;
    cout << len.size() << endl;
    for (int i = len.size() - 1; i >= 0; i -- ) 
        cout << len[i] << ' ';
    cout << endl;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t -- ) {
        work();
    }
    return 0;
}