2020 China Collegiate Programming Contest Weihai Site

A

最基础的时间 2 * (2 * n * t)

然后是等待时间, 即 要么在左边等 第 2 个 guy, 或者乘船返回的等 1 个 guy

即 max(0, min(x - 2 * n * t + t + t, max(t, x - 2 * n * t + t)))

int main() {
    IOS;
    for (cin >> _; _; --_) {
        ll n, x, t; cin >> n >> x >> t;
        ll s = n * t << 1;
        cout << s + s + max(0ll, min(x - s + t + t, max(t, x - s + t))) << '
';
    }
    return 0;
}

H

思维题, 我们没法维护每个学生的获得消息数, 看着数据量是想 nlogn, 但线段树之类的nlogn数据结构并不能维护

只能另想他法, 发现每次发消息除了 x, 组内其他成员都接收

我们能不能维护 每个组的消息数呢? 每次 x, 发消息, 就让这个组内的每个人的消息数++, x单独--

好像能维护了! 好像确实是差分的思想,

每次进新的组, 就先让 x 减去 当前 组的消息数

最后遍历每个组,对组内成员修改就好了

但是你不能 n * m 去修改, 会超时, 因该记录每个组有那些学生, 或者学生属于哪些组, 这样复杂度就降下来了

int main() {
    IOS; cin >> n >> m >> k;
    rep (i, 1, k) {
        int a, b, c; cin >> a >> b >> c;
        if (a == 1) ans[b] -= cnt[c], g[c].insert(b);
        else if (a == 2) ans[b] += cnt[c], g[c].erase(b);
        else --ans[b], ++cnt[c]; 
    }
    rep (i, 1, n) for (auto j : g[i]) ans[j] += cnt[i];
    rep (i, 1, m) cout << ans[i] << '
';
    return 0;
}

D

注意到 c 莫比乌斯为 0, 不然 rad(abc) >= c

所以 (c = q^2p)

然而直接求 莫比乌斯是 (T * sqrt{n} = 1e10) 直接gg

这条路行不通

只能找 q 或者 p 了

我们要记得 对于任何一个数 大于 (sqrt{n}) 的数最多有一个

对于直接找 q, 那无非是 c % q == 0 && c / q % q == 0

复杂度也会炸

对于 p, c % p == 0 && (c / p) is square

也会炸

那同时求 p 和 q 呢? (毕竟都有一步 c % x == 0)

当然可以! 我们这里 q 是质数, 我们可以现顺序找 q

而 p 是合数, 在找 q 的同时, 不断让 n /= i, 慢慢的就把 p 除完了

最后 n 也就成了 q^2

int main() {
    IOS; init(1e6); //求质数
    for (cin >> _; _; --_) {
        ll n; cin >> n;
        bool f = 0;
        rep (i, 1, tot) 
            if (n % prime[i] == 0) {
                n /= prime[i];
                if (n % prime[i] == 0) { f = 1; break; }
            }
        ll c = sqrt(n);
        if (!f && n != 1) f = c * c == n;
        if (f) cout << "yes
";
        else cout << "no
";
    }
    return 0;
}