2018 ACM-ICPC 亚洲青岛区域网络赛

A. Live Love

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    int n, m;
    cin >> n >> m;
    cout << m << ' ' << n / (n - m + 1) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C. Halting Problem

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

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

    vector<array<int, 3>> a;
    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;
        if (s == "add") {
            int v;
            cin >> v;
            a.push_back({0, v});
        } else if (s == "beq") {
            int v, k;
            cin >> v >> k;
            k--;
            a.push_back({1, v, k});
        } else if (s == "bne") {
            int v, k;
            cin >> v >> k;
            k--;
            a.push_back({2, v, k});
        } else if (s == "blt") {
            int v, k;
            cin >> v >> k;
            k--;
            a.push_back({3, v, k});			
        } else {
            int v, k;
            cin >> v >> k;
            k--;
            a.push_back({4, v, k});			
        }
    }

    vector<vector<int>> vis(n, vector<int>(256));
    int x = 0;
    for (int i = 0; i < n; ) {
        if (vis[i][x]) {
            cout << "No\n";
            return;
        }

        vis[i][x] = 1;
        auto &[o, v, k] = a[i];
        if (o == 0) {
            x = (x + v) % 256;
            i++;
        } else if (o == 1) {
            if (x == v) {
                i = k;
            } else {
                i++;
            }
        } else if (o == 2) {
            if (x != v) {
                i = k;
            } else {
                i++;
            }
        } else if (o == 3) {
            if (x < v) {
                i = k;
            } else {
                i++;
            }
        } else {
            if (x > v) {
                i = k;
            } else {
                i++;
            }
        }
    }
    cout << "Yes\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

H. Traveling on the Axis

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    string s;
    cin >> s;
    int n = s.size();
    vector<int> a(n);
    for (int i = 1; i < n; i++) {
        if (s[i] == s[i - 1]) {
            a[i] = 2;
        } else {
            a[i] = 1;
        } 
    }
    i64 ans = 0;
    for (int i = 0; i < n; i++) {
        int k = 2;
        if (s[i] == '1') {
            k = 1;
        }

        ans += i64(k) * (n - i) + i64(a[i]) * (n - i) * i;
    }
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

J. Press the Button

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

void solve() {
    i64 a, b, c, d, v, t;
    cin >> a >> b >> c >> d >> v >> t;

    i64 m = lcm(a, c);
    i64 ans = 0;
    i64 l = t % m, cnt = t / m;

    vector<i64> p;
    for (i64 i = 0; i < m; i += a) {
        if (i <= l) {
            ans += b;
        }
        ans += b * cnt;
        p.push_back(i);
    }
    for (i64 i = 0; i < m; i += c) {
        if (i <= l) {
            ans += d;
        }
        ans += d * cnt;
        p.push_back(i);
    }
    p.push_back(m);
    sort(p.begin(), p.end());

    int n = p.size();
    for (int i = 1; i < n; i++) {
        if (p[i] - p[i - 1] > v) {
            ans -= cnt;
            if (p[i] <= l) {
                ans--;
            }
        }
    }

    ans--;
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

K. XOR Clique

#include "bits/stdc++.h"

using namespace std;
using i64 = long long;

#define range(a) begin(a), end(a)

void solve() {
    int n;
    cin >> n;
    vector<int> a(32);
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        a[__lg(x)]++;
    }
    cout << *max_element(range(a)) << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}