KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）

A - Century

int main() {
    IOS; cin >> n;
    n = n / 100 + (n % 100 != 0);
    cout << n;
    return 0;
}

B - 200th ABC-200

怕爆ll, 直接128

int main() {
    __int128 n; int k; read(n, k);
    rep (i, 1, k) {
        if (n % 200 == 0) n /= 200;
        else n = n * 1000 + 200;
    }
    write(n);
    return 0;
}

C - Ringo's Favorite Numbers 2

取膜相同, 相减就是相等

int a[N];
 
int main() {
    IOS; cin >> n; map<int, int> st; ll ans = 0;
    rep (i, 1, n) {
        cin >> m; ans += st[m % 200];
        ++st[m % 200];
    }
    cout << ans;
    return 0;
}

D - Happy Birthday! 2

有零必定有解, 无零

则当序列为\(1, 2, 4, 8, ...\)的时候才无解

然而是取膜\(200\), 即\(log2(200) < 8\)

只要序列长度大于8必定有解, 状压完事

int a[N];
VI g[200];

int main() {
    IOS; cin >> n; rep (i, 0, n - 1) cin >> a[i];
    rep (i, 1, (1 << min(8, n)) - 1) {
        int s = 0; VI cur;
        rep (j, 0, min(n, 8) - 1) if (i >> j & 1)
            s = (s + a[j]) % 200, cur.pb(j + 1);
        if (g[s].empty()) { swap(g[s], cur); continue; }
        cout << "Yes\n" << g[s].size();
        for (auto &j : g[s]) cout << ' ' << j;
        cout << '\n' << cur.size();
        for (auto &j : cur) cout << ' ' << j;
        return 0;
    }
    cout << "No";
    return 0;
}

E - Patisserie ABC 2

容斥, 我们首先要找到三个数字的和,

先把每个数字\(x \leqslant n\) 这个条件扔掉,

则三个数字总和为\(sum\)的情况有\(\frac{(n - 1) \times (n - 2)}{2}\)

然后减去有\(1/2/3\)个数字\(x > n\) 的情况

首先是\(3\)个数都大于\(n\) 那直接先默认给\(3\)个位置加上\(n\), 即现在数字和为\(sum - 3 \times n\)

即\(\frac{(n - 1 - 3 \times n) \times (n - 2 - 3 \times n)}{2}\)

然后我们默认给位置\(1(2, 3)\)加上\(n\), 当前总和为\(sum - n\)

(注意, \(sum \leqslant 3 \times n\) 即不存在 \(sum - n \geqslant 3 \times n\) 的情况)

这一步我们做了\(3\)次, 因为有三个位置, 其中位置\((1, 2), (2, 3), (1, 3)\) 会算重一次有 \(2\) 个数大于 \(n\) 的

所以我们还要加上\(3\)次有两个位置数大于\(n\) 的, 即\(sum - 2 \times n\), \(\frac{(n - 1 - 2 \times n) \times (n - 2 - 2 \times n)}{2}\)

找到了所求的3个数的数位和, 剩下的就好求了,

逐一确定位置\(1, 2, 3\)为几即可, 保证\(1 \leqslant x \leqslant n\) 即可

ll calc(ll x) { return x < 3 ? 0 : (x - 1) * (x - 2) >> 1; }

ll work(ll x) { return calc(x) - calc(x - 3 * n) - 3 * calc(x - n) + 3 * calc(x - 2 * n); }

int main() {
    IOS; ll k, s; cin >> n >> k; s = work(m = 3);
    while (s < k) k -= s, s = work(++m);
    rep (i, max(m - 2 * n, 1), n) {
        s = min(n, m - i - 1) - max(m - n - i, 1) + 1;
        if (k > s) { k -= s; continue; }
        return cout << i << ' ' << max(m - n - i, 1) + k - 1 << ' ' << m - i - max(m - n - i, 1) - k + 1, 0;
    }
    return 0;
}