2026夏组队训练赛第十二场

A. Arcade Crane

cpp

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

int vis[100000];

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

    int n;
    cin >> n;

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

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

    vector<pair<int, int>> ans;

    auto op = [&ans](int x, int y, bool f, vector<int> &a) -> void {
        if (x == y) return;
        if (f) ans.push_back({x, y});
        //cout << x << ' ' << y << '\n';

        if (x < y) {
            int num1 = a[x], num2 = a[x + 1], num3 = a[x + 2];
            for (int i = x; i < y; i ++) {
                a[i] = a[i + 3];
            }
            a[y] = num1, a[y + 1] = num2, a[y + 2] = num3;
        } else {
            int num1 = a[x], num2 = a[x + 1], num3 = a[x + 2];
            for (int i = x - 1; i >= y; i --) {
                a[i + 3] = a[i];
            }
            a[y] = num1, a[y + 1] = num2, a[y + 2] = num3;
        }
        
    };

    for (int i = 1; i <= n - 5; i ++) {
        for (int j = i; j <= n; j ++) if (a[j] == i) {
            //cout << "j = " << j << '\n';

            if (i == j) break;
            if (j == n) {
                op(n - 2, n - 4, 1, a);
                //print();
                op(n - 2, i, 1, a);
            } else if (j == n - 1) {
                op(n - 2, n - 3, 1, a);
                //print();
                op(n - 2, i, 1, a);
            } else op(j, i, 1, a);
            
            //print();
            break;
        }
    }

    vector<int> b = {a[n - 4], a[n - 3], a[n - 2], a[n - 1], a[n]};
    for (auto &i : b) i -= n - 5;

    bool ok = 0;
    vector<pair<int, int>> path;

    auto get = [&b]() -> int {
        return b[0] * 10000 + b[1] * 1000 + b[2] * 100 + b[3] * 10 + b[4];
    };

    auto dfs = [&](auto self) {
        if (ok) return;
        int g = get();
        if (vis[g]) return;
        vis[g] = 1;

        if (g == 12345) {
            ok = 1;
            return;
        }

        for (int i = 0; i <= 2; i ++) {
            for (int j = 0; j <= 2; j ++) {
                if (i == j) continue;
                op(i, j, 0, b);
                path.push_back({i, j});
                
                self(self);

                if (ok) return;
                op(j, i, 0, b);
                path.pop_back();
            }
        }
    };

    dfs(dfs);
    for (auto [l, r] : path) {
        op(l + n - 4, r + n - 4, 1, a);
    }
    cout << size(ans) << '\n';
    for (auto [a, b] : ans) cout << a << ' ' << b << '\n';
}

B. Bisecting Bargain

超级大暴力。

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 = 105;
int vis[N][N][N];
db w = 3;

void init() {}
void solve() {
    int n;
    cin>>n;
    vi a={1,2,5,10,20,50,100,200,500};
    if(n%2){
        cout<<n<<endl;
        for(int i=0;i<n;i++)cout<<1<<" ";
        cout<<endl;
        return;
    }
    auto get=[&](int c1,int c2,int c5,int c10,int c20,int c50,int c100,int c200,int c500){
        vi q;
        for(int i=0;i<c1;i++)q.pb(1);
        for(int i=0;i<c2;i++)q.pb(2);
        for(int i=0;i<c5;i++)q.pb(5);
        for(int i=0;i<c10;i++)q.pb(10);
        for(int i=0;i<c20;i++)q.pb(20);
        for(int i=0;i<c50;i++)q.pb(50);
        for(int i=0;i<c100;i++)q.pb(100);
        for(int i=0;i<c200;i++)q.pb(200);
        for(int i=0;i<c500;i++)q.pb(500);
        return q;
    };
    auto get1=[&](vi a,int n)->int{
        bitset<5001>dp;
        dp[0]=1;
        for(int i=0;i<sz(a);i++){
            auto ndp=dp<<a[i];
            dp|=ndp;
        }
        if(dp[n])return 1;
        else return 0;
    };
    for(int c1=0;c1<2;c1++){
        for(int c2=0;c2<5;c2++){
            for(int c5=0;c5<2;c5++){
                for(int c10=0;c10<5;c10++){
                    for(int c20=0;c20<5;c20++){
                        for(int c50=0;c50<2;c50++){
                            for(int c100=0;c100<2;c100++){
                                for(int c200=0;c200<=(n-c1-c2*2-c5*5-c10*10-c20*20-c50*50-c100*100)/200;c200++){
                                    int t=(n-c1-c2*2-c5*5-c10*10-c20*20-c50*50-c100*100-c200*200);
                                    if(t%500||t<0)continue;
                                    if(!get1(get(c1,c2,c5,c10,c20,c50,c100,c200,t/500),n/2)){
                                        auto q=get(c1,c2,c5,c10,c20,c50,c100,c200,t/500);
                                        cout<<sz(q)<<endl;
                                        for(auto i:q){
                                            cout<<i<<" ";
                                        }
                                        cout<<endl;
                                        return;
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout<<"splittable"<<endl;
}

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

    init();
    cout << fixed << setprecision(10);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

C. Canal Crossing

如果有解那么只有一条路，用树上差分维护异或和容斥出来路径即可。

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
vector<pair<int, int>> adj[N];
int f[N];
long long res;

void dfs(int x, int fa) {
    for (auto &[w, y] : adj[x]) {
        if (y == fa) continue;
        dfs(y, x);
        f[x] ^= f[y];
        if (f[y]) res += w;
    }
}

int 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, z;
        cin >> x >> y >> z;
        adj[x].emplace_back(z, y);
        adj[y].emplace_back(z, x);
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        f[x] ^= 1, f[y] ^= 1;
    }
    dfs(1, 0);
    cout << res << '\n';
    return 0;
}

D. Dreamcatcher

一定是一个接近 n / 2 的和 n 互质的树，考虑到素数间隔很小，直接暴力枚举。

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);
    LL n;
    cin >> n;
    LL j = n / 2;
    while (gcd(j, n) != 1) {
        j--;
    }
    cout << j << '\n';
    return 0;
}

E. Erratic Lights

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 = 105;
int vis[N][N][N];
db w = 3;

void init() {}

void solve() {
    int n;
    cin >> n;
    vi c(3);
    string s;
    cin >> s;
    for (int i = 0; i < n; i++) {
        if (s[i] == 'r')
            c[0]++;
        else if (s[i] == 'g')
            c[1]++;
        else
            c[2]++;
    }
    sort(all(c));
    vector<vector<vector<db>>> dp(n + 1, vector<vector<db>>(n + 1, vector<db>(n + 1, INF)));
    auto get = [&](int a, int b, int c) -> db {
        vi e = {a, b, c};
        sort(all(e));
        return dp[e[0]][e[1]][e[2]];
    };
    dp[0][0][n] = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (i + j + k != n)
                    continue;
                if (i > j || j > k)
                    continue;
                if (i == 0) {
                    dp[i][j][k] = 3 + get(i,j-1,k+1);
                } else {
                    dp[i][j][k] = 1.5 + (get(i-1,j+1,k) + get(i-1,j,k+1)) / 2;
                }
            }
        }
    }
    cout << dp[c[0]][c[1]][c[2]] << endl;
}

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

    init();
    cout << fixed << setprecision(10);
    int t = 1;
    // cin >> t;
    while (t--)
        solve();

    return 0;
}

题目非常的绕，如果读懂了就不难（如果读懂了）。

cpp

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

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

    int n;
    cin >> n;

    vector<ll> a(n + 1), b(n + 1), pre(n + 2), suf(n + 2); // pre 和 suf 是没用的，之前读错题忘记删了
    for (int i = 1; i <= n; i ++) cin >> a[i] >> b[i];

    ll sum = 0, sb = 0;
    for (int i = 1; i <= n; i ++) sum += a[i], sb += b[i];

    pre[0] = 0x3f3f3f3f, suf[n + 1] = 0x3f3f3f3f;
    for (int i = 1; i <= n; ++i) pre[i] = min(b[i], pre[i - 1]);
    for (int i = n; i; --i) suf[i] = min(suf[i + 1], b[i]);

    for (int i = 1; i <= n; ++i) {
        // cout << sb - sum + a[i] << ' ' << min(pre[i - 1], suf[i + 1]) << '\n';
        if (sb - sum + a[i] <= b[i]) {
            cout << i << '\n';
            return 0;
        }
    }

    cout << "impossible\n";
}

G. Group Photo

看了题解之后补的，考虑从小到大放，每次添加都是从左右两端往中间补，记一个 $f_{i, j}$ 表示左边填 i 个右边填 j 个，在原位的数的个数最大值，不难发现每个原序列的位置至多贡献两次 +1 的转移，转移只有 $O (n)$ 个，把向 i + 1 方向转移和向 j + 1 方向转移的箭头中点的作为坐标，可以转换成一个二维表上的 LIS 问题。

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 500010;
int tr[N * 2], a[N], m;

void add(int x, int v) {
    for (; x <= m; x += x & -x) tr[x] = max(tr[x], v);
}

int query(int x) {
    int res = 0;
    for (; x; x -= x & -x) res = max(res, tr[x]);
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    vector<pair<int, int>> b;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        if (a[i] - i >= 0) b.emplace_back(i * 2 - 1, (a[i] - i) * 2); // i - 1 -> i
        if (a[i] - n + i - 1 >= 0) b.emplace_back((a[i] - n + i - 1) * 2, (n - i + 1) * 2 - 1); // j - 1 -> j
    }
    sort(b.begin(), b.end());
    m = n * 2;
    for (auto &[_, x] : b) {
        add(x + 1, query(x + 1) + 1);
    }
    cout << n - query(m) << '\n';
    return 0;
}

I. Juggling Keys

模拟一下，只有一队人回来之前没人在屋里就得拿钥匙。

cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

map<int, tuple<int, int, int>> mp;
map<int, int> ps;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, k, q;
    cin >> n >> k >> q;
    vector<int> res(q + 1);
    vector<pair<int, int>> a(q + 1);
    for (int i = 1; i <= q; ++i) {
        int p, l, r;
        cin >> p >> l >> r;
        mp[l] = {p, i, 1};
        mp[r] = {p, i, -1};
        a[i] = {l, r};
    }
    int cnt = 0;
    for (auto &[_, t] : mp) {
        auto &[p, i, v] = t;
        if (v == 1) cnt++;
        else {
            if (cnt == n) {res[i] = 1;
            ps[a[i].first]++, ps[a[i].second]--;}
            cnt--;
        }
    }
    cnt = 0;
    int cur = 0;
    for (auto &[_, v] : ps) {
        cur += v;
        // cout << cur << ' ';
        cnt = max(cnt, cur);
    }
    // cout << '\n';
    if (cnt > k) cout << "impossible\n";
    else {
        for (int i = 1; i <= q; ++i) cout << res[i];
        cout << '\n';
    }
    return 0;
}

J. KIT Finding

cpp

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

int main() {
    int n, m, a, b, c;
    cin >> n >> m >> a >> b >> c;

    cout << "KIT";
    a --, b --, c --;
    for (int j = 4; j <= m; j ++) {
        if (a) {
            a --;
            cout << "K";
        } else if (c) {
            c --;
            cout << "T";
        } else {
            b --;
            cout << "I";
        }
    }
    cout << '\n';
    for (int i = 2; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            if (a) {
                a --;
                cout << "K";
            } else if (c) {
                c --;
                cout << "T";
            } else {
                b --;
                cout << "I";
            }
        }
        cout << '\n';
    }
}

K. Last Christmas

cpp

#include <bits/stdc++.h>

using namespace std;

map<string, vector<int>> mp;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 10; ++j) {
            string s;
            cin >> s;
            if (mp[s].empty()) mp[s].assign(10, 0);
            mp[s][j]++;
        }
    }
    vector<vector<int>> t;
    for (auto [a, b] : mp) t.emplace_back(b);
    sort(t.begin(), t.end(), [&](vector<int> a, vector<int> b) {
        int s1 = 0, s2 = 0;
        for (int i = 0; i < 10; ++i) s1 += a[i], s2 += b[i];
        if (s1 != s2) return s1 < s2;
        else return a < b;
    });
    if (t.back() == t[t.size() - 2]) {
        cout << "tie\n";
    }
    else {
        for (auto [a, b] : mp) {
            if (b == t.back()) {
                cout << a << '\n';
                break;
            }
        }
    }
    return 0;
}

其他没做的题

Illuminated Stalls

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

A. Arcade Crane ​

B. Bisecting Bargain ​

C. Canal Crossing ​

D. Dreamcatcher ​

E. Erratic Lights ​

F. Fair Share ​

G. Group Photo ​

I. Juggling Keys ​

J. KIT Finding ​

K. Last Christmas ​