2026夏组队训练赛第九场

C. Bay

从外往里搜是很多棵树，回溯的时候统计块大小，枚举边的时候去两侧答案较小的一个（取儿子而不是父亲）

cpp

#include <bits/stdc++.h>

using namespace std;
const int N = 310;
int f[N][N], row[N][N], col[N][N];
int n, m;

void dfs(int x, int y, int px, int py) {
    if (f[x][y] != f[0][0]) return;
    f[x][y] = 1;
    if (x + 1 < n && !row[x + 1][y] && (x + 1 != px || y != py)) dfs(x + 1, y, x, y), f[x][y] += f[x + 1][y];
    if (x - 1 >= 1 && !row[x][y] && (x - 1 != px || y != py)) dfs(x - 1, y, x, y), f[x][y] += f[x - 1][y];
    if (y + 1 < n && !col[x][y + 1] && (x != px || y + 1 != py)) dfs(x, y + 1, x, y), f[x][y] += f[x][y + 1];
    if (y - 1 >= 1 && !col[x][y] && (x != px || y - 1 != py)) dfs(x, y - 1, x, y), f[x][y] += f[x][y - 1];
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n * n - 1; ++i) {
        int a, b;
        cin >> a >> b;
        pair<int, int> aa = {(a - 1) / n + 1, (a - 1) % n + 1}, bb = {(b - 1) / n + 1, (b - 1) % n + 1};
        if (aa.first == bb.first) row[aa.first][aa.second] = 1;
        else col[aa.first][aa.second] = 1;
    }
    memset(f, 0x3f3f3f3f, sizeof(f));
    for (int i = 1; i < n; ++i) {
        if (!row[1][i]) dfs(1, i, 0, 0);
        if (!row[n][i]) dfs(n - 1, i, 0, 0);
        if (!col[i][1]) dfs(i, 1, 0, 0);
        if (!col[i][n]) dfs(i, n - 1, 0, 0);
    }
    int t = 0, x = 0, y = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            // if (j != n && !row[i][j]) cout << min(f[i][j], f[i - 1][j]) << '\n';
            if (j != n && !row[i][j] && min(f[i][j], f[i - 1][j]) == m) {
                t++;
                if (!x) x = (i - 1) * n + j, y = (i - 1) * n + j + 1;
            }
            if (i != n && !col[i][j] && min(f[i][j], f[i][j - 1]) == m) {
                t++;
                if (!x) x = (i - 1) * n + j, y = i * n + j;
            }
        }
    }
    cout << t << '\n' << x << ' ' << y << '\n';
    return 0;
}

D. Bookshelf

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <complex>
using namespace std;
#define int long long
#define i64 int64_t
#define db long double
#define pii pair<int, int>
#define tiii tuple<int, int, int>
#define ull unsigned long long
#define vi vector<int>

using i128 = __int128;
#define vpii vector<pii>
#define vvpii vector<vector<pii>>
#define vvi vector<vi>
#define pqpii priority_queue<pii, vector<pii>, greater<pii>>
#define pqi priority_queue<int, vi, greater<int>>
#define f first
#define s second
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define eb emplace_back
#define sz(x) (x).size()
#define mp make_pair
#define bit bitset<N>
#define endl '\n'
void pr(vector<int> a) {
    for (auto i : a)
        cout << i << ' ';
    cout << '\n';
}
const int mod = 998244353;
const int INF = 1e18;
const int N = 129;
int p[N], p2[N];

void init() {}

void solve() {
    int n, l;
    cin >> n >> l;
    vpii a(n);
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i].f;
    }
    for (int i = 0; i < n; i++) {
        cin >> a[i].s;
        sum += a[i].s;
    }
    int ps, h;
    cin >> ps >> h;
    int sum1 = 0;
    for (int i = 0; i < n; i++) {
        if (a[i].s > l - sum)
            sum1 += a[i].s;
    }
    if (a[ps - 1].s <= l - sum) {
        int q = 0;
        if (q <= h && l - sum1 + q >= h + a[ps - 1].s) {
            cout << "YES" << endl;
            return;
        }
        for (int i = 0; i < n; i++) {
            if (a[i].s > l - sum)
                q += a[i].s;
            if (q <= h && l - sum1 + q >= h + a[ps - 1].s) {
                cout << "YES" << endl;
                return;
            }
        }
        // cout << 111 << endl;
        cout << "NO" << endl;
    } else {
        int q = 0;
        for (int i = 0; i < ps - 1; i     ++) {
            if (a[i].s > l - sum)
                q += a[i].s;
        }
        if (q <= h && l - sum1 + q >= h)
            cout << "YES" << endl;
        else
            cout << "NO" << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

E. Clean Arrangement

显然子树的下标是连续的，把连向父亲的边拆成从自己到边界，和从边界到父亲两段。在对于非根的节点需要统计自己内部的和从自己到边界的，根节点只需要统计自己内部的。考虑贡献，对于非根节点贡献值为子树数量 + 子树大小构成的数组和 0,1,1,2,2,3,3... 内积最小值求和，对于根节点贡献值为子树数量 + 子树大小构成的数组和 0,0,1,1,2,2,3,3... 内积最小值求和，显然一个顺序和一个逆序的内积是最小的，直接按照子树大小排个序算即可。

cpp

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 5010;

int f[N], cnt[N];
vector<int> adj[N];

bool cmp(const int &a, const int &b) {
    return cnt[a] < cnt[b];
}

void dfs(int x, int fa) {
    cnt[x] = 1;
    vector<int> t;
    for (int &y : adj[x]) {
        if (y == fa) continue;
        dfs(y, x);
        f[x] += f[y];
        cnt[x] += cnt[y];
        t.emplace_back(y);
    }
    sort(t.begin(), t.end(), cmp);
    f[x] += t.size();

    // cout << x << '\n';
    // for (int i = 0; i < t.size(); ++i) cout << cnt[t[i]] << ' ';
    // cout << '\n';
    for (int i = 0; i < t.size(); ++i) {
        f[x] += (i + (x != 1)) / 2 * cnt[t[t.size() - i - 1]];
    }
}


signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i < n; ++i) {
        int x, y;
        cin >> x >> y;
        adj[x].emplace_back(y);
        adj[y].emplace_back(x);
    }
    dfs(1, 0);
    // for (int i = 1; i <= n; ++i) cout << f[i] << ' ';
    // cout << '\n';
    cout << f[1] << '\n';
    return 0;
}

G. Extraterrestrial Creatures

cpp

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

    ll n, x;
    cin >> n >> x;

    vector<ll> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i ++) cin >> a[i];
    for (int i = 1; i <= n; i ++) cin >> b[i];

    ll l = 0, r = 1e18;

    auto calc = [&](ll t) -> bool {
        __int128_t use = 0;
        for (int i = 1; i <= n; i ++) {
            if (b[i] == 0) {
                use += 1e12;
                continue;
            }
            ll need = (t - a[i]);
            ll k = max(0ll,(need + b[i] - 1) / b[i]);
            use += k;
        }
        return use <= x;
    };

    while (l < r) {
        ll mid = (l + r + 1) >> 1;
        if (calc(mid)) l = mid;
        else r = mid - 1;
    }

    for (int i = 1; i <= n; i ++) {
        ll need = (l - a[i]);
        ll k = max(0ll,(need + b[i] - 1) / b[i]);
        x -= k;
        a[i] += k * b[i];
    }

    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;

    for (int i = 1; i <= n; i ++) {
        pq.push({a[i], i});
    }

    while (x --) {
        auto [val, pos] = pq.top();
        pq.pop();
        a[pos] += b[pos];
        pq.push({a[pos], pos});
    }

    for (int i = 1; i <= n; i ++) cout << a[i] << ' ';
}

I. Magic Door

cpp

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

int a[81][81];
//-3 ac_bomb
//-2 blank
//-1 wall
//0 bomb

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            cin >> a[i][j];
        }
    }

    int x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;

    swap(a[x1][y1], a[x2][y2]);
    int changes = 1, bomb_active = 0;

    queue<pair<int, int>> bombs, dels;

    auto print = [&]() {
        cout << "-----------------\n";
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
    };

    auto fall = [&]() -> void {
        //cout << "fall\n";
        //print();
        for (int col = 1; col <= m; col ++) {
            int pos = n;
            for (int row = n; row >= 1; row --) {
                if (a[row][col] == -2) continue;
                if (pos != row) changes = 1;
                if (a[row][col] == 0 && pos != row) {
                    a[pos --][col] = -3;
                    bomb_active = 1;
                }
                else a[pos --][col] = a[row][col];

            }
            for (; pos >= 1; pos --) a[pos][col] = -2;
        }
    };

    auto del = [&]() -> void {
        changes = 0;
        int na[81][81];
        for (int i = 1; i <= 80; i ++) for (int j = 1; j <= 80; j ++) na[i][j] = a[i][j];

        for (int row = 1; row <= n; row ++) {
            for (int col = 1; col <= m; col ++) {
                if (a[row][col] <= 0) continue;
                int r = col;
                while (r + 1 <= m && a[row][r + 1] == a[row][col]) r ++;
                if (r - col + 1 >= 3) for (int i = col; i <= r; i ++) na[row][i] = -2;
                col = r;
            }
        }
        for (int col = 1; col <= m; col ++) {
            for (int row = 1; row <= n; row ++) {
                if (a[row][col] <= 0) continue;
                int r = row;
                while (r + 1 <= n && a[r + 1][col] == a[row][col]) r ++;
                if (r - row + 1 >= 3) for (int i = row; i <= r; i ++) na[i][col] = -2;
                row = r;
            }
        }
        
        for (int i = 1; i <= 80; i ++) {
            for (int j = 1; j <= 80; j ++) {
                a[i][j] = na[i][j];
            }
        }
        fall();
    };

    auto bomb = [&]() -> void {
        bomb_active = 0;
        int na[81][81];
        for (int i = 1; i <= 80; i ++) for (int j = 1; j <= 80; j ++) na[i][j] = a[i][j];

        for (int row = 1; row <= n; row ++) {
            for (int col = 1; col <= m; col ++) {
                if (a[row][col] == -3) {
                    na[row][col] = -2;
                    for (int u = row - 1; u >= 1; u --) {
                        if (a[u][col] == -1) break;
                        else na[u][col] = -2;
                    }
                    for (int d = row + 1; d <= n; d ++) {
                        if (a[d][col] == -1) break;
                        else na[d][col] = -2;
                    }
                    for (int l = col - 1; l >= 1; l --) {
                        if (a[row][l] == -1) break;
                        else na[row][l] = -2;
                    }
                    for (int r = col + 1; r <= m; r ++) {
                        if (a[row][r] == -1) break;
                        else na[row][r] = -2;
                    }
                }
            }
        }

        for (int i = 1; i <= 80; i ++) {
            for (int j = 1; j <= 80; j ++) {
                a[i][j] = na[i][j];
            }
        }
        fall();
    };



    //print();
    while (changes || bomb_active) {
        while(changes) {
            del();
            //cout << "del\n";
            //print();
        }
        if (bomb_active) {
            bomb();
            //cout << "bomb\n";
            //print();
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            if (a[i][j] == -2) ans ++;
        }
    }
    cout << ans;
}

L. Segments

实际上 y 坐标没用，只需要右端点最小值和左端点最大值。

cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, q;
    LL mn = LLONG_MAX, mx = LLONG_MIN;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        LL a, b, c;
        cin >> a >> b >> c;
        mn = min(mn, b), mx = max(mx, a);
    }
    while (q--) {
        LL x;
        cin >> x;
        cout << max(0LL, max(x - mn, mx - x)) << '\n';
    }
    return 0;
}

M. Triple Fairness

cpp

#include <bits/stdc++.h>
using namespace std;

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

    int n;
    cin >> n;
    
    for (int i = 1; i <= n; i ++) cout << i << ' ';

    if (n % 3 == 0) {
        for (int i = 2; i <= n; i ++) cout << i << ' ';
        cout << 1 << ' ';

        for (int i = 3; i <= n; i ++) cout << i << ' ';
        cout << 1 << ' ';
        cout << 2;
    }
    else {
        for (int i = 1; i <= n; i ++) cout << i << ' ';
        for (int i = 1; i <= n; i ++) cout << i << ' ';
    }
}

其他没做的题

Adventurer Dabi
Badge Relay
CPEquivalence
Fair Problemset
Mex Culpa
Quadrants

2026夏组队训练赛第九场 ​

C. Bay ​

D. Bookshelf ​

E. Clean Arrangement ​

G. Extraterrestrial Creatures ​

I. Magic Door ​

L. Segments ​

M. Triple Fairness ​