2026夏组队训练赛第十五场

A. A Little Leftover Pizza

cpp

#include <bits/stdc++.h>

using namespace std;

int cnt[128];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        char c;
        int t;
        cin >> c >> t;
        cnt[c] += t;
    }
    cout << (cnt['S'] + 5) / 6 + (cnt['M'] + 7) / 8 + (cnt['L'] + 11) / 12 << '\n';
    return 0;
}

B. Andor Strikes Again

用 bfs 建树，成功建树之后就是简单树形 DP 了。

cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 100010;
vector<int> adj[N];
int f[N][2], tot;

void dfs(int x, int t) {
    // and : 1, or : 0
    if (adj[x].size() == 0) return;
    vector<int> a = {0, 0x3f3f3f3f};
    for (int y : adj[x]) {
        dfs(y, t ^ 1);
        f[x][t] += f[y][t];
        a = {a[0] + f[y][t], min(a[1] + min(f[y][0], f[y][1]), a[0] + f[y][t ^ 1])};
    }
    f[x][t ^ 1] = a[1];   
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    char c;
    cin >> n >> c;
    tot++;
    string s;
    cin >> s;
    if (s == "T" || s == "F") {
        cout << "1\n";
        return 0;
    }
    else {
        queue<pair<int, int>> q;
        q.emplace(1, stoi(s));
        while (!q.empty()) {
            auto [x, siz] = q.front();
            q.pop();
            for (int i = 0; i < siz; ++i) {
                cin >> s;
                adj[x].emplace_back(++tot);
                if (s == "T" || s == "F") {
                    f[tot][1] = s == "F";
                    f[tot][0] = s == "T";
                }
                else {
                    int nsiz = stoi(s);
                    q.emplace(tot, nsiz);
                }
            }
        }
        dfs(1, c == 'A');
        cout << max(f[1][0], f[1][1]) << '\n';
    }
    return 0;
}

D. But I Want to Win

DP 一下前 i 个人被淘汰的最小轮数。

cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
#define vi vector<int>
const int N = 30;
LL a[N];
const LL INF=1e9;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    LL s = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        s += a[i];
    }
    sort(a + 1, a + n + 1);
    int flag=-1;
    if (a[n] * 2 > s) {
        cout << "IMPOSSIBLE TO WIN\n";
        return 0;
    }
    else {
        LL cur = a[n - 1];
        for (int i = 1; i < n - 1; ++i) {
            cur += a[i];
            if (cur * 2 > s) {
                flag=i;
                break;
            }
        }
        if(flag==-1){
            cout << "IMPOSSIBLE TO WIN\n";
            return 0;
        }
    }
    vi dp(flag+1,INF);
    dp[1]=1;
    int cur=0;
    for(int i=1;i<=flag;i++){
        cur+=a[i];
        int sum=0;
        for(int j=i+1;j<=flag;j++){
            sum+=a[j];
            if(cur+sum>=a[j]*(j-i))dp[j]=min(dp[j],dp[i]+1);
        }
    }
    cout<<dp[flag]<<endl;
    return 0;
}

E. Chess Solitaire

大模拟。

cpp

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

#define debug(x) // cout << #x << '=' << x << ' ';
#define DL // cout << '\n';

int n, m;
char a[10][10];

bool valid(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

pair<int, int> pos[10];
vector<tuple<char, pair<int, int>, pair<int, int>>> path;
char type[10];
bool vis[10];

vector<pair<int, int>> d_knight = {
    {1, 2}, {1, -2}, 
    {2, 1}, {2, -1}, 
    {-1, 2}, {-1, -2}, 
    {-2, 1}, {-2, -1}
};
vector<pair<int, int>> d_king = {
    {-1, -1}, {-1, 0}, {-1, 1}, 
    {0, -1}, {0, 1}, 
    {1, -1}, {1, 0}, {1, 1}
};

void print(){
    for (auto [type, a, b] : path) {
        cout << type << ": " << char('A' + a.first - 1) << a.second << " -> " << char('A' + b.first - 1) << b.second << '\n';
    }
}

void dfs(int step) {//已经吃掉step - 1 开始吃 step
    debug(step) DL
    if (step == m) {
        print();
        exit(0);
    }

    for (int i = 1; i <= n; i ++) for (int j = 1; j <= n; j ++) if (a[i][j]) {
        int p = a[i][j];
        auto t = type[p];
		int x = pos[p].first, y = pos[p].second;

        vector<pair<int, int>> eats;

        auto eat = [&](int nx, int ny) {
            int np = a[nx][ny];
            if (np == p) return;
            vis[np] = 1;
            a[x][y] = 0;
            a[nx][ny] = p;
            pos[p] = {nx, ny};
            path.push_back({t, {x, y}, {nx, ny}});
            dfs(step + 1);
            a[x][y] = p;
            path.pop_back();
            pos[p] = {x, y};
            a[nx][ny] = np;
            vis[np] = 0;
        };

        auto op1 = [&]() {
            for (int i = x - 1; i >= 1; i --) {
                int nx = i, ny = y;
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                    break;
                }
            }
            for (int i = x + 1; i <= n; i ++) {
                int nx = i, ny = y;
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                    break;
                }
            }
            for (int i = y + 1; i <= n; i ++) {
                int nx = x, ny = i;
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                    break;
                }
            }
            for (int i = y - 1; i >= 1; i --) {
                int nx = x, ny = i;
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                    break;
                }
            }
        };

        auto op2 = [&]() {
            int nx = x, ny = y;
            while (nx - 1 >= 1 && ny - 1 >= 1) {
                nx --, ny --;
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                    debug(nx) debug(ny) DL
                    break;
                }
            }
            nx = x, ny = y;
            while (nx - 1 >= 1 && ny + 1 <= n) {
                nx --, ny ++;
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                    debug(nx) debug(ny) DL
                    break;
                }
            }
            nx = x, ny = y;
            while (nx + 1 <= n && ny - 1 >= 1) {
                nx ++, ny --;
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                    debug(nx) debug(ny) DL
                    break;
                }
            } 
            nx = x, ny = y;
            while (nx + 1 <= n && ny + 1 <= n) {
                nx ++, ny ++;
                debug(nx) debug(ny) DL
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                    debug(nx) debug(ny) DL
                    break;
                }
            } 
        };
        if (t == 'N') {
            for (auto &[dx, dy] : d_knight) {
                int nx = x + dx, ny = y + dy;
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                }
            }
        } else if (t == 'B') {
            op2();
        } else if (t == 'R') {
            op1();
        } else if (t == 'Q') {
            op1();
            op2();
        } else if (t == 'K') {
            for (auto &[dx, dy] : d_king) {
                int nx = x + dx, ny = y + dy;
                if (valid(nx, ny) && a[nx][ny] != 0) {
                    eats.push_back({nx, ny});
                }
            }
        }

        sort(eats.begin(), eats.end());
        for (auto &[nx, ny] : eats) eat(nx, ny);
    }
}

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

    cin >> n >> m;

    for (int i = 1; i <= m; i ++) {
        char _type;
        string _pos;
        cin >> _type >> _pos;

        int x = _pos[0] - 'A' + 1;
        int y = _pos[1] - '0';
        a[x][y] = i;
        type[i] = _type;
        pos[i] = {x, y};
    }
    dfs(1);
    cout << "No solution";
}

F. Fractional Sequence

cpp

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

#define debug(x) cout << #x << '=' << x << '\n';

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

    ll n;
    cin >> n;

    if (n == 1) {
        cout << 1;
        return 0;
    }

    ll l = 0, r = 1e9; 
    while (l < r) {
        ll mid = (l + r + 1) >> 1;
        if (mid * (mid + 1) / 2 <= n) l = mid;
        else r = mid - 1;
    }
    
    ll left = n - l * (l + 1) / 2;

    if (left == 0) {
        left = l - 1;
        cout << l << ' ' << left << '/' << l;
        return 0;
    }

    left --;
    if (left == 0) {
        cout << l + 1;
        return 0;
    }
    
    l ++;
    ll d = l;
    ll g = std::gcd(left, d);
    
    left /= g;
    d /= g;
    cout << l << ' ' << left << '/' << d << '\n';
}

G. How Many Balls?

cpp

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

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

    ll p, q;
    cin >> p >> q;

    for (ll r = 1; r <= 1e6; r ++) {
        ll a = p;
        ll b = 2 * p * r - 2 * r * q - p;
        ll c = p * r * r - p * r;

        ll delta = b * b - 4 * a * c ;
        if (delta <= 0) continue;
        
        ll t = sqrt(delta);
        if (t * t != delta) continue;
        ll u1 = -b + t, u2 = -b - t;
        if (u1 % (a * 2) == 0) {
            ll x1 = u1 / (a * 2);
            if (x1 >= r) {
                cout << r << ' ' << x1 << '\n';
                return 0;
            }
        }
        if (u2 % (a * 2) == 0) {
            ll x2 = u2 / (a * 2);
            if (x2 >= r) {
                cout << r << ' ' << x2 << '\n';
                return 0;
            }
        }
    }
    cout << "impossible\n";

}

H. Move It, Slowpoke!

分层图最短路，记录当前点 x，前驱 pre，已经连续走了 d 长度的最短路。

cpp

#include <bits/stdc++.h>

using namespace std;

using tiii = tuple<int, int, int, int>;
const int N = 110;
vector<pair<int, int>> adj[N];
int dis[N][N][N], vis[N][N][N];
set<tuple<int, int, int>> sst;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, k, d, s, t;
    cin >> n >> m >> k >> d >> s >> t;
    for (int i = 1; i <= m; ++i) {
        int x, y, z;
        cin >> x >> y >> z;
        adj[x].emplace_back(z, y);
        adj[y].emplace_back(z, x);
    }
    for (int i = 1; i <= k; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        sst.emplace(a, b, c);
    }
    memset(dis, 0x3f, sizeof(dis));
    priority_queue<tiii, vector<tiii>, greater<tiii>> q;
    dis[s][0][0] = 0;
    q.emplace(dis[s][0][0], s, 0, 0);
    while (!q.empty()) {
        auto [_, x, pre, cd] = q.top();
        q.pop();
        if (vis[x][pre][cd]) continue;
        vis[x][pre][cd] = true;
        for (auto [w, y] : adj[x]) {
            int f = sst.count({pre, x, y});
            int nd = min(d + 1, f * cd + w);
            if ((f == 0 || cd + w <= d) && y != pre && dis[y][x][nd] > dis[x][pre][cd] + w) {
                dis[y][x][nd] = dis[x][pre][cd] + w;
                q.emplace(dis[y][x][nd], y, x, nd);
            }
        }
    }
    int res = 0x3f3f3f3f;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j <= d + 1; ++j) {
            res = min(res, dis[t][i][j]);
        }
    }
    if (res == 0x3f3f3f3f) cout << "impossible\n";
    else cout << res << '\n';
    return 0;
}

I. Number Pyramid

cpp

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

int a[101][101];

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

    int n;
    cin >> n;

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

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= i; j ++) {
            if (a[i][j] == 100) a[i][j] = 1e9;
        }
    }

    for (int _ = 1; _ <= 10000; _ ++)
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= i; j ++) {
            if (i - 1 >= 1 && j - 1 >= 1 && a[i - 1][j - 1] != 1e9 && a[i][j - 1] != 1e9) {
                int nx = a[i - 1][j - 1] - a[i][j - 1];

                if (a[i][j] != 1e9 && a[i][j] != nx) {
                    cout << "no solution";
                    return 0;
                }

                if (a[i][j] == 1e9) a[i][j] = nx;

                if (a[i][j] > 99 || a[i][j] < -99) {
                    cout << "no solution";
                    return 0;
                }
                
            }
            if (i - 1 >= 1 && j + 1 <= i && a[i - 1][j] != 1e9 && a[i][j + 1] != 1e9) {
                int nx = a[i - 1][j] - a[i][j + 1];
                
                if (a[i][j] != 1e9 && a[i][j] != nx) {
                    cout << "no solution";
                    return 0;
                }

                if (a[i][j] == 1e9) a[i][j] = nx;

                if (a[i][j] > 99 || a[i][j] < -99) {
                    cout << "no solution";
                    return 0;
                }
            }

            if (i + 1 <= n && a[i + 1][j] != 1e9 && a[i + 1][j + 1] != 1e9) {
                int nx = a[i + 1][j] + a[i + 1][j + 1];
                if (a[i][j] != 1e9 && a[i][j] != nx) {
                    cout << "no solution";
                    return 0;
                }

                if (a[i][j] == 1e9) a[i][j] = nx;

                if (a[i][j] > 99 || a[i][j] < -99) {
                    cout << "no solution";
                    return 0;
                }
            }

        }
    }

    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= i; j ++) {
            if (a[i][j] == 1e9) {
                cout << "ambiguous";
                return 0;
            }
        }
    }

    cout << "solvable\n";
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= i; j ++) {
            cout << a[i][j] << ' ';
        }
        cout << '\n';
    }
}

K. Triptych

$n^{3}$ 暴力不考虑 d 的情况下所有的 a, b, c 的组合，然后统计答案的时候再次枚举 a, b, c 的数量检查 d，然后再来一轮扣掉回文。

cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 60;

LL f[N][N][N][4];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int w, d;
    cin >> w >> d;
    f[1][0][0][0] = f[0][1][0][1] = f[0][0][1][2] = 1;
    for (int i = 2; i <= w; ++i) { 
        for (int x = 0; x <= i; ++x) {
            for (int y = 0; x + y <= i; ++y) {
                int z = i - x - y;
                if (x) {
                    f[x][y][z][0] += f[x - 1][y][z][1];
                    f[x][y][z][0] += f[x - 1][y][z][2];
                    f[x][y][z][0] += f[x - 1][y][z][3];
                }
                if (y) {
                    f[x][y][z][1] += f[x][y - 1][z][0];
                    f[x][y][z][1] += f[x][y - 1][z][2];

                    f[x][y][z][3] += f[x][y - 1][z][1];
                }
                if (z) {
                    f[x][y][z][2] += f[x][y][z - 1][0];
                    f[x][y][z][2] += f[x][y][z - 1][1];
                    f[x][y][z][2] += f[x][y][z - 1][3];
                }
                // cout << x << ' ' << y << ' ' << z << '\n';
                // cout << f[x][y][z][0] << ' ' << f[x][y][z][1] << ' ' << f[x][y][z][2] << ' ' << f[x][y][z][3] << '\n';
            }
        }
    }
    LL res = 0;
    for (int x = 0; x <= w; ++x) {
        for (int y = 0; x + y <= w; ++y) {
            int z = w - x - y;
            if (abs(x - y) <= d && abs(x - z) <= d && abs(y - z) <= d) {
                for (int i = 0; i < 4; ++i) res += f[x][y][z][i];
            }
        }
    }
    if (w & 1)
        for (int x = 0; x <= w / 2; ++x) {
            for (int y = 0; x + y <= w / 2; ++y) {
                int z = w / 2 - x - y;
                if (abs(x * 2 + 1 - y * 2) <= d && abs(x * 2 + 1 - z * 2) <= d && abs(y - z) * 2 <= d) {
                    res -= f[x][y][z][1];
                    res -= f[x][y][z][2];
                    res -= f[x][y][z][3];
                }
                if (abs(x * 2 - y * 2 - 1) <= d && abs(x * 2 - z * 2) <= d && abs(y * 2 + 1 - z * 2) <= d) {
                    res -= f[x][y][z][0];
                    res -= f[x][y][z][2];
                }
                if (abs(x * 2 - y * 2) <= d && abs(x * 2 - z * 2 - 1) <= d && abs(y * 2 - z * 2 - 1) <= d) {
                    res -= f[x][y][z][0];
                    res -= f[x][y][z][1];
                    res -= f[x][y][z][3];
                }
            }
        }
    else
        for (int x = 0; x <= w / 2; ++x) {
            for (int y = 0; x + y <= w / 2; ++y) {
                int z = w / 2 - x - y;
                if (abs(x - y) <= d / 2 && abs(x - z) <= d / 2 && abs(y - z) <= d / 2) {
                    res -= f[x][y][z][1];
                }
            }
        }
    cout << res << '\n';
    return 0;
}

其他没做的题

AROD
Polyomino Tiling
Valley Gulls

2026夏组队训练赛第十五场 ​

A. A Little Leftover Pizza ​

B. Andor Strikes Again ​

D. But I Want to Win ​

E. Chess Solitaire ​

F. Fractional Sequence ​

G. How Many Balls? ​

H. Move It, Slowpoke! ​

I. Number Pyramid ​

K. Triptych ​