2024ICPC昆明

比赛链接

B. Brackets

首先，选出的两段要么均为空，要么一个为一堆左括号，另一个为一堆右括号且它们互补。

考虑给定的每一段区间，若它消除后剩下的是一堆左括号，则将剩下的那些左括号的哈希值塞进一个std::map中，然后将所有括号取反并翻转序列，重新做如上操作并将哈希值塞进另一个std::map中，这样就分别求得了“留下来的是左括号的序列的哈希值”和“留下来的是右括号的序列所能匹配的左括号序列的哈希值”，将它们贪心地匹配即可。

问题在于如何求得这些区间消除后的哈希值：从左往右依次考虑每个括号并维护一个栈，如果遇到一个左括号则将它入栈，否则如果它与栈顶匹配，则消除，否则清空栈。

当考虑完第 个括号时，处理右端点为 的询问，设其左端点为 ： - 如果左端点在某对匹配的括号内部，则该区间消除后的前缀一定是一个右括号（这对匹配的括号中的右括号无法消除），无需处理。 - 否则栈中所有位于该左端点右侧的左括号即为消除完后剩下的左括号序列，计算它的哈希值即可。

总时间复杂度为 ，若用std::unordered_map可以做到线性。

B. Brackets 示例代码

B. Brackets

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;

const ull BASE = 131;
map<char, int> Map;

const int N = 5e5 + 10;
int n, m, A[N];
ull Base[N];
vector<int> L[N];
int ans;

map<ull, int> calc() {
    map<ull, int> f;
    static int stk[N], sz[N], tp[N];
    static ull hash_val[N];
    int lim = 0, top = 0;
    for(int i = 1; i <= n; i ++) {
        if(A[i] & 1) {
            if((A[stk[top]] ^ A[i]) != 1) 
                top = 0, lim = i;
            else 
                top --;
        } else {
            stk[++top] = i;
            hash_val[top] = hash_val[top - 1] * BASE + A[i];
        }
        sz[i] = top, tp[i] = stk[top];
        for(int j : L[i]) if(j >= lim) {
            if(sz[i] < sz[j] || tp[j] != stk[sz[j]]) 
                continue;
            if(sz[i] > sz[j]) {
                ull hash = hash_val[top] - hash_val[sz[j]] * Base[sz[i] - sz[j]];
                f[hash] ++;
            } else ans ++;
        }
    }
    return f;
}

inline void solve() {
    cin >> n >> m;
    string S; cin >> S;
    vector<pair<int, int>> in(m);
    for(int i = 0; i < m; i ++)
        cin >> in[i].first >> in[i].second;
    for(int i = 0; i < n; i ++)
        A[i + 1] = Map[S[i]];
    for(auto [l, r] : in) L[r].emplace_back(l - 1);
    ans = 0;
    auto f = calc();
    for(int i = 1; i <= n; i ++)
        A[i] ^= 1, L[i].clear();
    reverse(A + 1, A + n + 1);
    for(int i = 0; i < m; i ++) {
        in[i].first = n - in[i].first + 1;
        in[i].second = n - in[i].second + 1;
        swap(in[i].first, in[i].second);
        L[in[i].second].emplace_back(in[i].first - 1);
    }
    auto g = calc();
    for(int i = 1; i <= n; i ++)
        L[i].clear();
    ans /= 4;
    for(auto [x, y] : f) ans += min(y, g[x]);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    Base[0] = 1;
    for(int i = 1; i < N; i ++)
        Base[i] = Base[i - 1] * BASE;
    Map['('] = 2, Map[')'] = 3, Map['['] = 4, Map[']'] = 5;
    Map['{'] = 6, Map['}'] = 7, Map['<'] = 8, Map['>'] = 9;

    int T; cin >> T;
    while(T --) solve();

    return 0;
}

C. Coin

考虑从最后倒推回去，这需要两部分的计算：

• 操作需要几轮才会结束
• 操作后的第 个位置在操作前的位置

先考虑第一部分，一次操作会使元素数量减少 ，这是个经典的整除分块形式， 接近 的时候，次数约为 ，暴力模拟无法接受，所以考虑将 相同的段一起处理。

设 ，要找到一个最小的 使得 ，化为不等式处理，即 ，解出 ，所以这段的轮数为 。

然后考虑第二部分，如果操作一次后在第 个位置，那么对它及前面的每 个元素，都是 个元素删掉一个元素形成的（最后一段可能不足 个元素），因此在它前面的被删掉的元素数为 ，因此它原先是第 个元素。

注意到 的变化次数也是 的，所以同样类似地整除分块处理即可，总时间复杂度 。

C. Coin 示例代码

C. Coin

#include <bits/stdc++.h>

using namespace std;

inline long long f(long long n, long long k) {
    // 计算游戏需要几轮才能结束
    long long ans = 0;
    while(n) {
        long long d = (n + k - 1) / k;
        long long c = (n - k * (d - 1) - 1) / d + 1;
        n -= c * d; ans += c;
    }
    return ans - 1;
}
long long g(long long p, long long k, long long C) {
    // 这里传进的 k 实际上为分母 k - 1
    // C 表示剩余轮数
    if(C == 0) return p;
    long long d = (p + k - 1) / k;
    long long x = (k * d - p) / d + 1;
    x = min(x, C);
    return g(p + x * d, k, C - x);
}

inline void solve() {
    long long n, k; cin >> n >> k;
    cout << g(1, k - 1, f(n, k)) << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) solve();

    return 0;
}

D. Dolls

引理：若一个序列可以被完全合并，则它的任一子区间都可以被完全合并，

根据引理可以得到：若一个区间不可以被完全合并，则所有包含它的区间都不能被完全合并。

因此可以从左往右考虑，每次贪心地合并最长的一段区间，否则不会更优。

给定左端点，二分最大的可能的右端点，问题化为如何检查一个序列是否可以被完全合并。不断合并两个相邻的、紧挨着的套娃，若最后只剩下一个套娃则可以被完全合并（例如， 与 就是两个紧挨着的套娃，它们合并变为 ），注意这里需要先离散化。

如果每次右端点初始值都设为 ，那么总的时间复杂度为 ，无法承受，我们需要保证二分的长度和为 级别的，这样时间复杂度就降为 ，为此，可以对每个左端点先倍增出第一个不可合并的右端点位置（倍增检查的的区间长度为 ），并将它设为二分的右端点，此时区间长度不超过二倍的最长区间长度，因此二分的长度和不超过 ，总时间复杂度降为 。

D. Dolls 示例代码

D. Dolls

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;
int n, A[N];

inline bool merge_check(pair<int, int> a, pair<int, int> b) {
    if(a.first > b.first) swap(a, b);
    return a.second + 1 == b.first;
}
inline pair<int, int> merge(pair<int, int> a, pair<int, int> b) {
    if(a.first > b.first) swap(a, b);
    return {a.first, b.second};
}

inline bool check(int l, int r) {
    vector<int> v(A + l, A + r + 1);
    vector<int> lsh = v;
    int n = r - l + 1;
    sort(lsh.begin(), lsh.end());
    for(int i = 0; i < n; i ++)
        v[i] = lower_bound(lsh.begin(), lsh.end(), v[i]) - lsh.begin();
    vector<pair<int, int>> stk;
    stk.push_back({v[0], v[0]});
    for(int i = 1; i < n; i ++) {
        stk.push_back({v[i], v[i]});
        while(stk.size() >= 2 && merge_check(stk[stk.size() - 2], stk[stk.size() - 1])) {
            stk[stk.size() - 2] = merge(stk[stk.size() - 2], stk[stk.size() - 1]);
            stk.pop_back();
        }
    }
    return stk.size() == 1;
}

inline void solve() {
    cin >> n;
    for(int i = 1; i <= n; i ++)
        cin >> A[i];
    int s = 0;
    for(int l = 1; l <= n; l ++) {
        int L = l + 1, R = l + 1, d = 2;
        while(R <= n && check(l, R)) 
            d <<= 1, R = min(n + 1, l + d - 1);
        R --;
        while(L < R) {
            int mid = (L + R + 1) >> 1;
            if(check(l, mid)) L = mid;
            else R = mid - 1;
        }
        s ++, l = R;
    }
    cout << (n - s) << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) solve();

    return 0;
}

E. Extracting Weights

距离为 的点对至多有 个，将每个看作是一个方程 ，，特别地，初始时给定了方程 ，只需要检验这些方程能否消元得到解。

为此可以一个一个地将方程插入线性基，检验最后是否可以插入 次（初始已经有方程 ），如果可行，就询问线性基中的这 个方程，最后消元求解。总的时间复杂度为 。

E. Extracting Weights 示例代码

E. Extracting Weights

#include <bits/stdc++.h>

using namespace std;
typedef unsigned long long ull;

const int N = 256;
int n, k; vector<int> G[N];
typedef bitset<N> bs;

bool vis[N]; bs B[N], val[N]; int cnt = 0; pair<int, int> pr[N];
inline void insert(bs M, pair<int, int> pr) {
    if(cnt == n) return;
    bs MM = M;
    while(true) {
        int i = M._Find_first();
        if(i > n) break;
        if(!vis[i]) {
            vis[i] = true, B[i] = M, val[i] = MM, ::pr[i] = pr;
            cnt ++; return;
        } else M ^= B[i];
    }
}
int anc;
void dfs(int u, int fa, bs &M, int dep) {
    M.flip(u);
    if(dep == k) {
        if(anc <= u) insert(M, {anc, u});
        M.flip(u);
        return;
    }
    for(int v : G[u]) {
        if(v == fa) continue;
        dfs(v, u, M, dep + 1);
    }
    M.flip(u);
}

inline void calc(vector<pair<bs, int>> &v) {
    for(int i = 1; i < n; i ++) {
        for(int j = 1; j <= i; j ++)
            if(v[i].first[j]) {
                v[i].first ^= v[j - 1].first;
                v[i].second ^= v[j - 1].second;
            }
    }
    for(int i = n - 2; i >= 0; i --) {
        for(int j = n; j > i + 1; j --)
            if(v[i].first[j]) {
                v[i].first ^= v[j - 1].first;
                v[i].second ^= v[j - 1].second;
            }
    }
    for(int i = 0; i < n; i ++) {
        v[i].first.flip(i+1);
        assert(v[i].first.none());
    }
    cout << "! ";
    for(int i = 1; i < n; i ++) 
        cout << v[i].second << ' ';
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    cin >> n >> k;
    for(int i = 1; i < n; i ++) {
        int a, b; cin >> a >> b;
        G[a].emplace_back(b), G[b].emplace_back(a);
    }
    
    bs a; a[1] = 1;
    vis[1] = true, B[1] = val[1] = a, cnt ++;
    bs M;
    for(int i = 1; i <= n; i ++)
        anc = i, dfs(i, 0, M, 0);
    if(cnt == n) {
        cout << "YES" << endl;
        cout << "? " << n - 1 << ' ';
        for(int i = 2; i <= n; i ++) 
            cout << pr[i].first << ' ' << pr[i].second << ' ';
        cout << endl;
        vector<int> ans(n + 1, 0);
        for(int i = 2; i <= n; i ++)
            cin >> ans[i];
        vector<pair<bs, int>> vec(n);
        for(int i = 1; i <= n; i ++)
            vec[i - 1] = {val[i], ans[i]};
        calc(vec);
    } else cout << "NO" << endl;

    return 0;
}

G. GCD

首先，答案一定不会超过 ，证明如下：

假如两个数均为偶数，那么将它们同时除以 ，答案不变。

否则，它们的 是一个奇数，选定 中的一个奇数，将它减去 ，我们就通过至多两次操作将 全部变为了偶数。而 ，因此至多 步就能将 变为 ，此时若 ，则仅需一次操作即可将 变为 。

因此直接爆搜即可，步骤大于 就剪掉。

G. GCD 示例代码

G. GCD

#include<bits/stdc++.h>

using namespace std;

int ans;
void dfs(long long a, long long b, int c) {
    if(a == 0 && b == 0) {
        ans = min(ans, c);
        return;
    }
    if(c > ans) return;
    if(a) dfs(a - __gcd(a, b), b, c + 1);
    if(b) dfs(a, b - __gcd(a, b), c + 1);
}

inline void solve() {
    long long a, b;
    cin >> a >> b;
    ans = 26;
    dfs(a, b, 0);
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) solve();

    return 0;
}

H. Horizon Scanning

将所有点极角排序，求相隔 个位置的极角差值的最大值即可，时间复杂度 ，瓶颈在排序。

H. Horizon Scanning 示例代码

H. Horizon Scanning

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;
int n, k; double theta[N];

inline void solve() {
    cin >> n >> k;
    for(int i = 1; i <= n; i ++) {
        int x, y; cin >> x >> y;
        theta[i] = atan2(y, x);
    }
    double ans = 0;
    sort(theta + 1, theta + n + 1);
    for(int i = 1; i <= n; i ++) {
        if(i + k <= n)
            ans = max(ans, theta[i + k] - theta[i]);
        else
            ans = max(ans, theta[i + k - n] -  theta[i] + acos(-1) * 2);
    }
    cout << fixed << setprecision(10) << ans << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) solve();

    return 0;
}

J. Just another Sorting Problem

• 如果 ，那么Alice必胜。

• 否则 ，此时设位置不对的数有 个

  • 若 ，则谁先手谁获胜
  • 否则，Alice获胜当且仅当 且Bob先手，证明就是讨论一下Bob能否使得Alice在每次操作前都维持

J. Just another Sorting Problem 示例代码

J. Just another Sorting Problem

#include <bits/stdc++.h>

using namespace std;

inline void solve() {
    int n; string S;
    cin >> n >> S;
    int c = 0;
    for(int i = 1; i <= n; i ++) {
        int x; cin >> x;
        if(x != i) c ++;
    }
    if(n >= 3) {
        if(c == 2) cout << S << '\n';
        else if(n == 3) {
            if(S == "Alice") cout << "Bob" << '\n';
            else cout << "Alice" << '\n';
        } else cout << "Bob" << '\n';
    } else cout << "Alice" << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) solve();

    return 0;
}

L. Last Chance: Threads of Despair

设序列 想要消灭序列 ，先用 中不为 的那些元素攻击 中元素，最后一起爆炸一定最优。

问题在于 中那些不为 的元素应该打谁：考虑将 升序排序，维护当前最后可以连锁爆炸几次、还剩下多少刀可以打，每遇到一个最后解决不了的 中元素就把它打到可以最后炸死的程度，然后让最后的爆炸次数加一。

最后如果剩下一些刀（可以为 ）说明答案为Yes，否则为No。时间复杂度 ，瓶颈在排序。

L. Last Chance: Threads of Despair 示例代码

L. Last Chance: Threads of Despair

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 10;
int n, m, A[N], B[N];

inline void solve() {
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
        cin >> A[i];
    for(int i = 1; i <= m; i ++)
        cin >> B[i];
    sort(A + 1, A + n + 1), sort(B + 1, B + m + 1);
    long long c = n; int k = 0;
    for(int i = 1; i <= n; i ++)
        k += (A[i] == 1);
    if(k) c -= (k - 1);
    int i = 1, j = 1; while(i <= n && A[i] == 1) i ++;
    for(int x = 1; x <= n; x ++) A[x] --;
    while(j <= m && c >= 0) {
        while(true) {
            if((j > m || B[j] > k) && (i > n || A[i] > k)) break;
            while(j <= m && B[j] <= k) k ++, j ++;
            while(i <= n && A[i] <= k) k ++, i ++;
        }
        if(j <= m) 
            c -= (B[j] - k), B[j] = k;
    }
    cout << (c >= 0 ? "Yes" : "No") << '\n';
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) solve();

    return 0;
}

M. Matrix Construction

一种可能的构造方案是沿副对角线方向从小到大填入数字，例如：

证明：考虑相邻两个数一定在相邻的两个副对角线上，如果两对相邻的数（ 和 ）所在的副对角线不同，那么由于处于左上方副对角线的元素一定更小，所以必然有

中的一个成立，于是 自然成立 如果位于相同的副对角线上，由于同一副对角线上元素是单调的，所以也不可能相等。

M. Matrix Construction 示例代码

M. Matrix Construction

#include <bits/stdc++.h>

using namespace std;

inline void solve() {
    int n, m; cin >> n >> m;
    vector<vector<int>> A(n, vector<int>(m));
    int k = 1;
    for(int i = 0; i < m; i ++) 
        for(int j = 0; j <= i && j < n; j ++) 
            A[j][i - j] = k ++;
    for(int i = 1; i < n; i ++) {
        for(int d = 0; i + d < n && m - 1 - d >= 0; d ++)
            A[i + d][m - 1 - d] = k ++;
    }
    cout << "Yes" << '\n';
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < m; j ++)
            cout << A[i][j] << " \n"[j == m - 1];
}

int main() {
    ios::sync_with_stdio(false), cin.tie(0);

    int T; cin >> T;
    while(T --) solve();

    return 0;
}