A. Live Love

最大值就是把所有的\(P\)放在一起，最小值是尽可能的均分.

#include <bits/stdc++.h>

using namespace std;

#define int long long

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

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}

K. XOR Clique

符合条件的\(a_i,a_j\)在二进制下最高位的 1 一定是在同一个位置。所以我们只要计算出每个数字最高位1 的位置，然后统计一下个数最多的即为答案。

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> cnt( 35 );
    for( int i = 1 , x , y ; i <= n ; i ++ ){
        cin >> x , y = 0;
        while( x > 1 ) y ++ , x >>= 1;
        cnt[y] ++;
    }
    cout << *max_element( cnt.begin(), cnt.end() ) << "\n";
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}

赛后想到了求最高位的一其实可以直接log2(x)

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> cnt(35);
    for (int i = 1, x, y; i <= n; i++)
        cin >> x, cnt[(int) (log2(x))]++;
    cout << *max_element(cnt.begin(), cnt.end()) << "\n";
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}

C. Halting Problem

这题因为\(r\)的值只有\(256\)，并且在确定\((i,r)\)的情况下后继是确定的。所以模拟过程，并标记已经访问过的\((i,r)\)即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 256;

void solve() {
    int n;
    bool flag = false;
    cin >> n;
    vector<array<bool, N>> f(n + 1);
    vector<string> op(n + 1);
    vector<int> v(n + 1), k(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> op[i] >> v[i];
        if (op[i] != "add") cin >> k[i];
    }
    for (int r = 0, i = 1;;) {
        if (i == n + 1) {
            flag = true;
            break;
        }
        if (f[i][r]) break;
        f[i][r] = true;
        if (op[i] == "add") r = (r + v[i]) % N, i++;
        else if (op[i] == "beq") {
            if (r == v[i]) i = k[i];
            else i++;
        } else if (op[i] == "bne") {
            if (r != v[i]) i = k[i];
            else i++;
        } else if (op[i] == "blt") {
            if (r < v[i]) i = k[i];
            else i++;
        } else {
            if (r > v[i]) i = k[i];
            else i++;
        }
    }
    if( flag ) cout << "Yes\n";
    else cout << "No\n";
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}

H. Traveling on the Axis

考虑\(t(l,r)\)与\(t(l,r-1)\)的关系。

\[t(l,r)=t(l,r-1)+d_r,d_r=\left\{\begin{matrix} 1 & s_r\ne s_{r-1}\\ 2& s_r = s{r-1} \end{matrix}\right. \]

记

\[a_l=t(l,l+1)=\left\{\begin{matrix} 1 & s_l= 1\\ 2& s_l \ne1 \end{matrix}\right. \]

所以

\[t(l,r) = a_l+\sum_{i=l+1}^{r} d_i \]

令

\[f(r)=\sum_{l=0}^{r-1} t(l,r) \]

则\(res =\sum f(i)\)

现在考虑如何求出\(f(i)\)

\[f(i)=t(0,i)+t(1,r)+\cdots+t(r-2,r)+t(r-1,r)\\ = (a_0+d_1+d_2\cdots+d_{i-1}+d_i)\\ +(a_1+d_2+d_3\cdots d_{i-1}+d_i)\\ + \cdots\\ +(a_{i-1}+d_i)\\ +(a_i)\\ =(t(0,i-1)+d_i)+(t(1,i-1)+d_i)+\cdots+t(i-2,i-1)+a_i\\ =f(i-1)+(i-1)\times d_i + a_i \]

并且\(f(0)=0\)，所以可以递推出\(f(i)\)

#include <bits/stdc++.h>

using namespace std;

#define int long long

void solve() {
    string s;
    cin >> s;
    int n = s.size(), res = 0;
    s = "0" + s;
    for (int i = 1, sum = 0, d; i <= n; i++) {
        sum += (i - 1) * (s[i] != s[i - 1] ? 1 : 2);
        sum += (s[i] == '1' ? 1 : 2);
        res += sum;
    }
    cout << res << "\n";
    return ;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--)
        solve();
    return 0;
}

J. Press the Button

\(press[i]\)表示\(i\)秒按了多少次，显然\(press[i]\)是会出现循环的，循环节就是\(lcm(a , c)\)。

我们可以先暴力求出循环节内部的贡献，然后再加上剩下的部分即可。

但是要注意的是，可能循环节内最后一次按的时间和下一个循环节第一次按的时间间隔小于\(v\)。如果出现这种情况，则除了第一个循环节外，其他循环节（包括最后一个不完整的循环节）第一次都会多按一下，要特判这种情况。

#include <bits/stdc++.h>

using namespace std;

#define int long long
using pii = pair<int, int>;

void solve() {
    int a, b, c, d, v, t, n;
    map<int, int> press;
    cin >> a >> b >> c >> d >> v >> t;
    n = lcm(a, c);
    if (n >= t) { // 没有循环节
        for (int i = 0; i <= t; i += a) press[i] += b;
        for (int i = 0; i <= t; i += c) press[i] += d;
        int res = 0, last = LLONG_MIN;
        for (auto [x, y]: press) {
            if (last + v < x) y--;
            last = x;
            res += y;
        }
        cout << res << "\n";
        return;
    } else {
        for (int i = 0; i < n; i += a) press[i] += b;
        for (int i = 0; i < n; i += c) press[i] += d;
        int last = LLONG_MIN;
        vector<pii> pre;
        pre.emplace_back(-1ll, 0ll);
        for (auto [x, y]: press) {
            if (last + v < x) y--;
            last = x;
            if (y > 0) pre.emplace_back(x, y + pre.back().second);
        }
        int qqq = 1;
        if( pre.back().first + v < n ) qqq = 0;
        int res = (t / n) * pre.back().second + max( 0ll,  t / n - 1 ) * qqq;
        t %= n;
        int l = 1 , r = pre.size() - 1 , it = -1;
        for( int mid ; l <= r ; ){
            mid = ( l + r ) >> 1;
            if( pre[mid].first <= t ) it = mid , l = mid + 1;
            else r = mid - 1;
        }
        res += pre[it].second + qqq;
        cout << res << "\n";
    }
    return;
}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int t;
    for (cin >> t; t; t--) solve();
    return 0;
}

B. Red Black Tree

先建树，建树后在树上通过 bfs 求出任意点到最近的红色父亲节点的距离。

对于每个询问考虑二分答案，如果当前点到红色点的距离小于\(mid\)，则不用处理。对于剩下的点，要修改一个点使得这些点距离减少，那么修改的点应该是LCA。所以求出 LCA 后，在逐个计算距离即可。

#include <bits/stdc++.h>

using namespace std;

#define int long long

using pii = pair<int, int>;

const int inf = 1e15;


void solve() {
    int n, m, q, logN, dn = 0;
    cin >> n >> m >> q;
    vector<vector<pii>> e(n + 1), g(n + 1);
    vector<int> dfn(n + 1), dis(n + 1), dist(n + 1, LLONG_MAX);
    queue<int> que;
    for (int i = 1, x; i <= m; i++) {
        cin >> x;
        que.push(x), dist[x] = 0;
    }

    logN = log2(n);
    vector f(logN + 1, vector<int>(n + 1));

    for (int i = 1, x, y, z; i < n; i++)
        cin >> x >> y >> z , e[x].emplace_back(y, z), e[y].emplace_back(x, z);

    auto build = [e, &g, &dn, &dfn, &f, &dis](auto &&self, int x, int fa) -> void {
        f[0][dfn[x] = ++dn] = fa;
        for (auto [y, w]: e[x]) {
            if (y == fa) continue;
            g[x].emplace_back(y, w), dis[y] = dis[x] + w;
            self(self, y, x);
        }
    };

    dis[1] = 0;
    build(build, 1, 0);
    vector<bool> vis(n + 1, false);
    while (!que.empty()) {
        int x = que.front();
        que.pop();
        if (vis[x]) continue;
        vis[x] = true;
        for (auto [y, w]: g[x]) {
            if (vis[y] or dist[y] <= dist[x] + w) continue;
            dist[y] = dist[x] + w, que.push(y);
        }
    }
    auto get = [dfn](int x, int y) {
        if (dfn[x] < dfn[y]) return x;
        return y;
    };

    for (int i = 1; i <= logN; i++)
        for (int j = 1; j + (1 << i) - 1 <= n; j++)
            f[i][j] = get(f[i - 1][j], f[i - 1][j + (1 << i - 1)]);

    auto lca = [dfn, get, f](int u, int v) {
        if (u == v) return u;
        u = dfn[u], v = dfn[v];
        if (u > v) swap(u, v);
        int d = log2(v - u++);
        return get(f[d][u], f[d][v - (1 << d) + 1]);
    };

    for (int k, l, r, res; q; q--) {
        cin >> k;
        vector<int> a(k);
        for (auto &i: a) cin >> i;
        l = 0, r = inf, res = -1;
        for (int mid, t, flag; l <= r;) {
            mid = (l + r) >> 1, t = -1, flag = 1;
            for (auto i: a) {
                if (dist[i] <= mid) continue;
                if (t == -1) t = i;
                else t = lca(t, i);
            }
            for (auto i: a) {
                if (min(dist[i], dis[i] - dis[t]) <= mid) continue;
                flag = 0;
                break;
            }
            if (flag) res = mid, r = mid - 1;
            else l = mid + 1;
        }
        cout << res << "\n";
    }


}

int32_t main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int TC;
    for (cin >> TC; TC; TC--)
        solve();
    return 0;
}