2026夏组队训练赛第八场

A. Matrix Equation

线性代数
数学

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 = 5e5 + 5;
const int N = 205;

int work(vector<bitset<N>> &a) {
    int n = a.size();
    for (int i = 0; i < n; ++i) {
        int p = i, t = N;
        for (int j = i; j < n; ++j) {
            for (int k = 0; k < n; ++k) {
                if (a[j][k]) {
                    if (k < t) {
                        t = k;
                        p = j;
                    }
                    break;
                }
            }
        }
        if (t == N) return i;
        swap(a[p], a[i]);
        for (int j = i + 1; j < n; ++j) {
            if (a[j][t]) a[j] ^= a[i];
        }
    }
    return n;
}
void init() {
    
}
int qp(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b/=2;
    }
    return res;
}
void solve() {
    int n;
    cin>>n;
    vvi a(n,vi(n,0)),b(n,vi(n,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>a[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>b[i][j];
        }
    }
    int ans=1;
    for(int i=0;i<n;i++){
        vector<bit>bt(n);
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++){
                bt[j][k]=a[j][k];
            }
            if(b[j][i]){
                if(bt[j][j])bt[j][j]=0;
                else bt[j][j]=1;
            }
        }
        ans=ans*qp(2,n-work(bt))%mod;
    }
    cout<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

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

    return 0;
}

C. Stone Game

贪心
数学

cpp

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    ll ans = 0;
    ll a, b, c;
    cin >> a >> b >> c;

    ll need = min(a, b);
    a -= need;
    b -= need;
    ans += need * 2;
    
    if (a) {
        ll t = a / 3;
        ans += t * 3;
        a %= 3;
        if (a == 2) ans ++;
    }

    if (b) {
        ll t = b / 3;
        ans += t * 6;
        b %= 3;
        if (b == 2) ans += 4;
    }
    cout << ans;
}

D. Fight against involution

贪心
排序

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<pair<ll, ll>> a(n);
 
    for (int i = 0; i < n; i ++) cin >> a[i].first >> a[i].second;
 
    sort(a.begin(), a.end(), [&](pair<ll, ll> &x, pair<ll, ll> &y){
        return x.second < y.second;
    });
 
    ll ans = 0;
 
    ll mx_l = a[0].first, r = a[0].second, cnt = 1;
    for (int i = 1; i < n; i ++) {
        if (a[i].second == r) {
            mx_l = max(mx_l, a[i].first);
            cnt ++;
        } else {
            ans += mx_l * cnt;
            mx_l = max(mx_l, a[i].first), r = a[i].second, cnt = 1;
        }
    }
    ans += cnt * mx_l;
    cout << ans;
}

G. Xor Transformation

位掩码
构造

cpp

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    LL a, b;
    cin >> a >> b;
    int h1, h2;
    for (int i = 61; i >= 0; --i) {
        if (a >> i & 1) {
            h1 = i;
            break;
        }
    }
    for (int i = 61; i >= 0; --i) {
        if (b >> i & 1) {
            h2 = i;
            break;
        }
    }
    vector<LL> res;
    if (h1 > h2) {
        if (!(a >> h2 & 1)) {
            res = {1LL << h2};
            a ^= 1LL << h2;
        }
        LL t = 0;
        for (int i = h1; i > h2; --i) {
            t |= a & 1LL << i;
        }
        a ^= t;
        res.emplace_back(t);
    }
    res.emplace_back(a ^ (1LL << h2));
    res.emplace_back(b ^ (1LL << h2));
    cout << res.size() << '\n';
    for (LL i : res) cout << i << ' ';
    cout << '\n';
}

J. Tree Constructer

构造
位掩码
图论

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;

void init() {}

void solve() {
    int n;
    cin >> n;
    vvi g(n + 1);

    for (int i = 1; i < n; i++) {
        int u, v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
    }
    
    vvi c(2);
    auto dfs=[&](auto dfs,int u,int p,int d)->void{
        c[d%2].pb(u);
        for(auto i:g[u]){
            if(i==p)continue;
            dfs(dfs,i,u,d+1);
        }
    };
    dfs(dfs,1,0,0);
    if(sz(c[0])>sz(c[1]))swap(c[0],c[1]);
    int full=(1ll<<60)-1;
    vi ans(n+1);
    for(int i=0;i<sz(c[0]);i++){
        ans[c[0][i]]=full^(1ll<<i)^(1ll<<59);
    }
    for(int i=0;i<sz(c[1]);i++){
        for(auto j:g[c[1][i]]){
            ans[c[1][i]]^=(full^ans[j])^(1ll<<59);
        }
        ans[c[1][i]]^=(1ll<<59);
    }
    for(int i=1;i<=n;i++){
        cout<<ans[i]<<" ";
    }
    cout<<endl;
}

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

    init();

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

    return 0;
}

L. Bit Sequence

动态规划
位掩码

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() {
    for (int i = 0; i < N; i++) p[i] = __builtin_popcount(i) % 2;
    p2[0] = 1;
    for (int i = 1; i < 60; i++) p2[i] = p2[i - 1] * 2;
}

vi get(int n) {
    vi res(4, 0);
    int k = n / 2;
    int c0 = k / 2, c1 = k / 2;
    if (k % 2 == 0) {
        if (__builtin_popcountll(k) % 2)
            c1++;
        else
            c0++;
    } else {
        c0++;
        c1++;
    }
    res[1] += c0;
    res[2] += c1;
    if (n >= 1) {
        auto t = get((n - 1) / 2);
        for (int i = 0; i < 4; i++) {
            int x = i >> 1;
            int y = i & 1;
            res[((x ^ 1) << 1) | y] += t[i];
        }
    }
    return res;
}

void solve() {
    int n, l;
    cin >> n >> l;
    vi a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    int bs = 1, h = 0;
    while (bs < n) bs *= 2, h++;
    vector<vvi> dp(n, vvi(bs, vi(4, 0)));
    for (int i = 0; i < bs; i++) {
        int op = (i < n - 1);
        for (int j = 0; j < 4; j++) {
            int x = op ? (j & 1) : (j >> 1);
            if ((x ^ p[i]) == a[n - 1]) {
                dp[n - 1][i][j] = 1;
            }
        }
    }
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 0; j < bs; j++) {
            int nj = (j - 1 + bs) % bs;
            int op = (nj < i - 1);
            for (int k = 0; k < 4; k++) {
                if (!dp[i][j][k])
                    continue;
                int x = op ? (k & 1) : (k >> 1);
                if ((x ^ p[nj]) == a[i - 1]) {
                    dp[i - 1][nj][k] = 1;
                }
            }
        }
    }
    int ans = 0;
    for (int i = 0; i < bs; i++) {
        if (i > l)
            continue;
        int g = (l - i) / bs;
        auto c = get(g);
        for (int j = 0; j < 4; j++) {
            if (dp[0][i][j]) {
                ans += c[j];
            }
        }
    }
    cout << ans << endl;
}

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

    init();

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

    return 0;
}

M. Cook Pancakes!

数学
Ad Hoc

cpp

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

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

    int n, m;
    cin >> n >> m;
    
    n <<= 1;

    cout << max(2, (n + m - 1) / m);
}

其他没做的题

Number Game
Tree Transform
Gcd Product
Path Killer
Random Walk On Tree
Kth Query

2026夏组队训练赛第八场 ​

A. Matrix Equation ​

C. Stone Game ​

D. Fight against involution ​

G. Xor Transformation ​

J. Tree Constructer ​

L. Bit Sequence ​

M. Cook Pancakes! ​

2026夏组队训练赛第八场

A. Matrix Equation

C. Stone Game

D. Fight against involution

G. Xor Transformation

J. Tree Constructer

L. Bit Sequence

M. Cook Pancakes!