2026夏组队训练赛第四场

A. Tatami Renovation

• 位掩码bitmask
• 分类讨论case_work

#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;
    LL L;
    cin >> n >> L;
    map<LL, int> mp;
    for (int i = 1; i <= n; ++i) {
        LL x, y;
        cin >> y >> x;
        mp[x] |= y;
    }
    if (n & 1) {
        cout << "no\n";
        return 0;
    }
    int cur = -1, res = 0;
    for (auto &[i, j] : mp) {
        if (j == 3) {
            if (cur != -1) {
                cur ^= 1;
                res++;
            }
        }
        else {
            if (cur != -1) {
                if (cur == (i + j & 1)) {
                    res++;
                }
                cur = -1;
            }
            else cur = i + j & 1;
        }
    }
    cout << res << '\n';
    return 0;
}

C. Seagull Population

• 贪心greedy
• 队列queue

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
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 endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 2e5;
void init() {}
void solve() {
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    int ans = 0;
    for(int i = 0; i < n; i++)ans+=max(0ll,a[i]-a[(i-1+n)%n]);
    int mx = *max_element(all(a));
    if(max(mx,ans)>N){
        cout<<max(mx,ans)<<endl;
        return;
    }
    int t=max(0ll,mx-ans);
    for(int i = 0; i < n; i++)a[i]-=t;
    queue<int> q;
    vvi g(n);
    for(int i = 0; i < a[n-1]; i++)q.push(-1);
    for(int i=0;i<n;i++){
        for(int j = 0; j < max(0ll,a[i]-a[(i-1+n)%n]); j++){
            q.push(i);
        }
        for(int j = 0; j < max(0ll,a[(i-1+n)%n]-a[i]); j++){
            int u = q.front();
            q.pop();
            g[i].pb(u);
        }
    }
    vpii as;
    for(int i = 0; i < t; i++)as.pb(mp(1,n));
    for(int i = 0; i < n; i++){
        for(int j = 0; j < sz(g[i]); j++){
            if(g[i][j]==-1){
                int u = q.front();
                q.pop();
                as.pb(mp(u+1,(i==0?n:i)));
            }else as.pb(mp(g[i][j]+1,(i==0?n:i)));
        }
    }
    cout<<sz(as)<<endl;
    for(auto [u,v]:as)cout<<u<<" "<<v<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    init();
 
    int t = 1;
    // cin >> t;
    while (t--)
        solve();
 
    return 0;
}

D. Decompose and Concatenate

• 分类讨论case_work
• 数学math

n = input()
if n.startswith("10"):
    print(int(n) - 10 ** (len(n) - 2), 10 ** (len(n) - 2), sep='')
elif n.startswith("1"):
    print(max(
        int(str(int(n) - 10 ** (len(n) - 1)) + str(10 ** (len(n) - 1))),
        int(str(int(n) - 10 ** (len(n) - 2)) + str(10 ** (len(n) - 2)))
    ))
else:
    print(int(n) - 10 ** (len(n) - 1), 10 ** (len(n) - 1), sep='')

E. Cutting Tofu

• 二分查找binary_search
• 数学math

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}

pair<LL, LL> solve(LL a, LL b, LL c, LL k) {
    auto check = [&](LL mid) -> bool {
        vector<__int128_t> t = {mid, (__int128_t)mid * b / a, (__int128_t)mid * c / a};
        sort(t.begin(), t.end());
        __int128_t tmp = 1;
        for (auto tt : t) {
            tmp *= tt;
            if(tmp<0)cout<<11<<endl;
            if (tmp >= k) return true;
        }

        return tmp >= k;
        // return (__int128_t)mid * (b * mid / a) * (c * mid / a) >= k;
    };
    // cout << check(512) << '\n';
    LL l = 1, r = 1000000000;
    while (l < r) {
        LL mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    LL g = gcd(a, l);
    return {a / g, l / g};
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        LL a, b, c, k;
        cin >> a >> b >> c >> k;
        // solve(a, b, c, k);
        vector<pair<LL, LL>> d = {solve(a, b, c, k), solve(b, a, c, k), solve(c, a, b, k)};
        sort(d.begin(), d.end(), [](pair<LL, LL> a, pair<LL, LL> b) {
            return a.first * b.second > a.second * b.first;
        });
        cout << d[0].first << ' ' << d[0].second << '\n';
    }
    return 0;
}

G. Charity Raffle

• 组合数学combinatorics
• 容斥原理inclusion_and_exclusion
• 模逆元modular_multiplicative_inverse

 #pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
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 endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 2e6 + 5;
void init() {}
struct Comb {
    int n;
    int mod;
    vector<int> fac, invfac;

    Comb(int _n, int _mod) {
        n = _n;
        mod = _mod;
        fac.assign(n + 1, 1);
        invfac.assign(n + 1, 1);

        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i - 1] * i % mod;
        }

        invfac[n] = qpow(fac[n], mod - 2);

        for (int i = n - 1; i >= 0; i--) {
            invfac[i] = invfac[i + 1] * (i + 1) % mod;
        }
    }

    int qpow(int a, int b) {
        int res = 1;
        while (b) {
            if (b & 1) res = res * a % mod;
            a = a * a % mod;
            b >>= 1;
        }
        return res;
    }
    int A(int n, int m) {
        if (m < 0 || m > n) return 0;
        return fac[n] * invfac[n - m] % mod;
    }
    int C(int n, int m) {
        if (m < 0 || m > n) return 0;
        return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
    }
};
Comb comb(N, mod);
int get(int n,int m,int s) {
    int ans = 0;
    for (int k = 0; k * (m + 1) <= s; k++) {
        int cur =
            comb.C(n, k) *
            comb.C(n + s - k * (m + 1) - 1,
                   s - k * (m + 1)) %
            mod;
        if (k & 1)
            ans -= cur;
        else
            ans += cur;
        ans %= mod;
    }

    return (ans + mod) %mod;
}
void solve() {
    int n,k,m;
    cin>>n>>k>>m;
    cout<<(get(n,m,k)-get(n,m-1,k-1)+mod)%mod<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

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

    return 0;
}

H. U-Shaped Panels

• 数据结构data_structures
• 模拟simulation

#include <bits/stdc++.h>

using namespace std;

struct BIT {
    vector<int> tr;
    int n;

    void init(int n) {
        tr.resize(n + 1);
        fill(tr.begin(), tr.end(), 0);
        this->n = n;
    }

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

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

    int query(int l, int r) {
        return query(r) - query(l - 1);
    }
};

const int N = 1010;
BIT row[N], col[N];
char c[N][N];

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) row[i].init(m);
    for (int i = 1; i <= m; ++i) col[i].init(n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            cin >> c[i][j];
            if (c[i][j] == '#') {
                row[i].add(j, 1);
                col[j].add(i, 1);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (c[i][j] == '#') {
                if (i + k - 1 <= n && j + k - 1 <= m) {
                    int uu = row[i].query(j, j + k - 1);
                    int dd = row[i + k - 1].query(j, j + k - 1);
                    int ll = col[j].query(i, i + k - 1);
                    int rr = col[j + k - 1].query(i, i + k - 1);

                    if (uu == k && dd == k && rr == k) {
                        for (int l = j; l <= j + k - 1; ++l) {
                            c[i][l] = c[i + k - 1][l] = '.';
                            row[i].add(l, -1), row[i + k - 1].add(l, -1);
                            col[l].add(i, -1), col[l].add(i + k - 1, -1);
                        }
                        for (int l = i + 1; l <= i + k - 2; ++l) c[l][j + k - 1] = '.', col[j + k - 1].add(l, -1), row[l].add(j + k - 1, -1);
                        continue;
                    }

                    if (uu == k && dd == k && ll == k) {
                        for (int l = j; l <= j + k - 1; ++l) {
                            c[i][l] = c[i + k - 1][l] = '.';
                            row[i].add(l, -1), row[i + k - 1].add(l, -1);
                            col[l].add(i, -1), col[l].add(i + k - 1, -1);
                        }
                        for (int l = i + 1; l <= i + k - 2; ++l) c[l][j] = '.', col[j].add(l, -1), row[l].add(j, -1);
                        continue;
                    }

                    if (uu == k && ll == k && rr == k) {
                        for (int l = i; l <= i + k - 1; ++l) {
                            c[l][j] = c[l][j + k - 1] = '.';
                            row[l].add(j, -1), row[l].add(j + k - 1, -1);
                            col[j].add(l, -1), col[j + k - 1].add(l, -1);
                        }
                        for (int l = j + 1; l <= j + k - 2; ++l) c[i][l] = '.', row[i].add(l, -1), col[l].add(i, -1);
                        continue;
                    }

                    if (dd == k && ll == k && rr == k) {
                        for (int l = i; l <= i + k - 1; ++l) {
                            c[l][j] = c[l][j + k - 1] = '.';
                            row[l].add(j, -1), row[l].add(j + k - 1, -1);
                            col[j].add(l, -1), col[j + k - 1].add(l, -1);
                        }
                        for (int l = j + 1; l <= j + k - 2; ++l) c[i + k - 1][l] = '.', row[i + k - 1].add(l, -1), col[l].add(i + k - 1, -1);
                        continue;
                    }
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            // cout << c[i][j];
            if (c[i][j] == '#') {
                cout << "no\n";
                return;
            }
        }
        // cout << '\n';
    }
    cout << "yes\n";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}

I. Game of Names

• 博弈论game_theory
• 贪心greedy

 #pragma GCC optimize("O2")
#include <bits/stdc++.h>
#include <numeric>
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 endl '\n'
const int mod = 998244353;
const int INF = 1e18;
const int N = 5e3 + 5;
void init() {}
void solve() {
    int n;
    cin>>n;
    string s;
    cin>>s;
    if(count(all(s),'.')==n){
        if(n==1){
            cout<<"alice"<<endl;
        }else{
            cout<<"bob"<<endl;
        }
        return;
    }
    int sc=0;
    int cnt=0,l=0;
    for(int i=0;i<n;i++){
        if(s[i]=='a')sc-=2;
        else if(s[i]=='b') sc+=2;
    }
    for(int i=0;i<n;i++){
        if(s[i]=='.')cnt++;
        else{
            l=s[i];
            break;
        }
    }
    int ct=0;
    if(cnt==0){
        if(l=='a')sc++;
        else sc--;
    }else if(cnt==1){
        if(l=='a')sc--;
        else sc++;
    }else{
        ct++;
    }
    cnt=0;
    int r=0;
    for(int i=n-1;i>=0;i--){
        if(s[i]=='.')cnt++;
        else{
            r=s[i];
            break;
        }
    }
    if(cnt==0){
        if(r=='a')sc++;
        else sc--;
    }else if(cnt==1){
        if(r=='a')sc--;
        else sc++;
    }else{
        ct++;
    }
    // cout<<sc<<endl;
    if(ct==1)sc++;
    if(sc>0)cout<<"alice"<<endl;
    else cout<<"bob"<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    init();

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

    return 0;
}

J. ICPC Board

• 构造constructive
• 暴力bruteforcing

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

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

vector<vector<char>> solve(vector<vector<char>> &a, int n, int m) {
	//奇数行全C 
	vector<vector<char>> res;
	bool ok = 1;
	for (int i = 1; i < n; i += 2) {
		if (ok == 0) break;
		for (int j = 0; j < m; j ++) {
			if (ok == 0) break;
			if (a[i][j] == 'I' || a[i][j] == 'P') {
				ok = 0;
				break;
			}
		}
	}

	vector<char> fi(n);
	for (int i = 0; i < n; i += 2) {
		if (ok == 0) break;
		for (int j = 0; j < m; j ++) {
			if (ok == 0) break;
			if (a[i][j] == 'C') {
				ok = 0;
				break;
			} else if (a[i][j] == '?') {
				continue;
			} else {
				char f;
				if (j % 2 == 0) {
					f = a[i][j];
				} else {
					f = 'I' + 'P' - a[i][j];
				}

				if (fi[i] == 0) {
					fi[i] = f;
				} else if (fi[i] != f) {
					ok = 0;
					break;
				}
			}
		}
	}
	for (int i = 0; i < n; i += 2) if (fi[i] == 0) fi[i] = 'I';
	if (ok) {
		res.assign(n, vector<char>(m));
		for (int i = 0; i < n; i ++) {
			if (i % 2) for (int j = 0; j < m; j ++) res[i][j] = 'C';
			else {
				for (int j = 0; j < m; j ++) {
					if (j % 2 == 0) res[i][j] = fi[i];
					else res[i][j] = 'I' + 'P' - fi[i];
				}
			}
		}
		return res;
	}
	//偶数行全C 
	ok = 1;
	for (int i = 0; i < n; i += 2) {
		if (ok == 0) break;
		for (int j = 0; j < m; j ++) {
			if (ok == 0) break;
			if (a[i][j] == 'I' || a[i][j] == 'P') {
				ok = 0;
				break;
			}
		}
	}
	fi.assign(n, 0);
	for (int i = 1; i < n; i += 2) {
		if (ok == 0) break;
		for (int j = 0; j < m; j ++) {
			if (ok == 0) break;
			if (a[i][j] == 'C') {
				ok = 0;
				break;
			} else if (a[i][j] == '?') {
				continue;
			} else {
				char f;
				if (j % 2 == 0) {
					f = a[i][j];
				} else {
					f = 'I' + 'P' - a[i][j];
				}
				if (fi[i] == 0) {
					fi[i] = f;
				} else if (fi[i] != f) {
					ok = 0;
					break;
				}
			}
		}
	}
	for (int i = 1; i < n; i += 2) if (fi[i] == 0) fi[i] = 'I';
	if (ok) {
		res.assign(n, vector<char>(m));
		for (int i = 0; i < n; i ++) {
			if (i % 2 == 0) for (int j = 0; j < m; j ++) res[i][j] = 'C';
			else {
				for (int j = 0; j < m; j ++) {
					if (j % 2 == 0) res[i][j] = fi[i];
					else res[i][j] = 'I' + 'P' - fi[i];
				}
			}
		}
		return res;
	}
	//IP 
	ok = 1;
	vector<int> pos_c(m, -1);
	char fic = 0;

	for (int j = 0; j < m && ok; j++) {
		for (int i = 0; i < n && ok; i++) {
			char ch = a[i][j];
			if (ch == '?') continue;

			int required_c_parity;

			if (ch == 'C') {
				required_c_parity = i % 2;
			} else {
				required_c_parity = 1 - i % 2;
				char f;
				if (j % 2 == 0) {
					f = ch;
				} else {
					f = 'I' + 'P' - ch;
				}

				if (fic == 0) {
					fic = f;
				} else if (fic != f) {
					ok = 0;
					break;
				}
			}

			if (pos_c[j] == -1) {
				pos_c[j] = required_c_parity;
			} else if (pos_c[j] != required_c_parity) {
				ok = 0;
				break;
			}
		}
	}

	if (ok) {
		if (fic == 0) fic = 'I';
		for (int j = 0; j < m; j++) {
			if (pos_c[j] == -1) pos_c[j] = 0;
		}

		res.assign(n, vector<char>(m));

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (i % 2 == pos_c[j]) {
					res[i][j] = 'C';
				} else if (j % 2 == 0) {
					res[i][j] = fic;
				} else {
					res[i][j] = 'I' + 'P' - fic;
				}
			}
		}

		return res;
	}
	return {};
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	int t;
	cin >> t;
	while (t --) {
		int n, m;
		cin >> n >> m;

		vector<vector<char>> a(n, vector<char>(m));
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < m; j ++) {
				cin >> a[i][j];
			}
		}
		vector<vector<char>> b(m, vector<char>(n)); 
		for (int i = 0; i < n; i ++) {
			for (int j = 0; j < m; j ++) {
				b[j][i] = a[i][j];
			}
		}
		auto ans = solve(a, n, m);
		if (!ans.empty()) {
			cout << "yes\n";
			for (auto i : ans) {
				for (auto j : i) {
					cout << j;
				}
				cout << '\n';
			}
			continue;
		}
		ans = solve(b, m, n);
		if (!ans.empty()) {
			cout << "yes\n";
			for (int i = 0; i < n; i ++) {
				for (int j = 0; j < m; j ++) {
					cout << ans[j][i];
				}
				cout << '\n';
			}	
			continue;
		}
		cout << "no\n";
	}
}

其他没做的题

• Minimizing Wildlife Damage
• Astral Geometry
• Membership Structure of a Secret Society
• Common Tangent Lines