2026“钉耙编程”暑期联赛（1）

1001. 小丑牌

算术
分类讨论

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
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
const int N = 1e4 + 5;
const int INF = 1e18;
#define exp 1e-12
const int mod = 998244353;
int dp[N],ndp[N];
void init() {}
void solve() {
    int x,y,n,m;
    cin >> x >> y >> n >> m;
    int x1=x,y1=y,x2=x,y2=y;
    for(int i = 0; i < n; i++) {
        int c;
        cin >> c;
        x1=min(x1,x+c);
        x2=max(x2,x+c);
    }
    for(int i = 0; i < m; i++) {
        int c;
        cin >> c;
        y1=min(y1,y+c);
        y2=max(y2,y+c);
    }
    int ans=x*y;
    ans=max({ans,x1*y1,x1*y2,x2*y1,x2*y2});
    cout << ans << "\n";
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

1004. 搭积木

贪心
并查集
树结构集合与映射
排序

贪心先合并 b / a 最小的。

cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 200010;
struct Node {
    LL a, b;
    int id;

    bool operator <(const Node &_) const {
        if (b * _.a == _.b * a) return id < _.id;
        else return b * _.a < _.b * a;
    }
} a[N];
int f[N], fa[N];
set<Node> s;

int getfa(int x) {
    return x == fa[x] ? x : fa[x] = getfa(fa[x]);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        assert(s.empty());
        int n;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i].a, a[i].id = i;
        for (int i = 1; i <= n; ++i) cin >> a[i].b;
        for (int i = 1; i <= n; ++i) cin >> f[i];
        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
            if (i != 1) s.insert(a[i]);
        }
        LL res = 0;
        for (int i = 1; i < n; ++i) {
            auto it = s.begin();
            auto &p = a[it->id];
            s.erase(it);
            auto &q = a[getfa(f[p.id])];
            if (q.id != 1) {
                s.erase(q);
            }
            res += q.b * p.a;
            fa[p.id] = q.id;
            q.a += p.a, q.b += p.b;
            if (q.id != 1) {
                s.insert(q);
            }
        }
        cout << res << '\n';
    }
    return 0;
}

1005. 摩卡数

构造
贪心
字符串

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
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
const int N = 1e4 + 5;
const int INF = 1e18;
#define exp 1e-12
const int mod = 998244353;
void init() {}
void solve() {
    int n;
    cin >> n;
    string ans="a";
    int cur = 1;
    while(n>0){
        // cout<<n<<endl;
        if(cur<=n){
            ans+='a';
            n-=cur;
            cur++;
        }else{
            ans+='b';
            n--;
            cur=1;
        }
    }
    cout<<sz(ans)<<" "<<2<<endl;
    cout<<ans<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

1006. 开关灯

组合数学
预处理
模逆元

cpp

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

const ll mod = 998244353;
const int N = 2e5;
#define int long long

ll fact[N + 5], inv[N + 5], inv2[N + 5];
#define debug(x) cout << #x << '=' << x << '\n';

ll qpow(ll a, ll b, ll p) {
	ll res = 1 % p;
	a %= p;
	while (b) {
		if (b & 1) res = res * a % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

ll a[N + 5], b[N + 5];

void init() {
	fact[0] = 1;
	for (int i = 1; i <= N; i ++) fact[i] = fact[i - 1] * i % mod;
	inv[N] = qpow(fact[N], mod - 2, mod);
	for (int i = N; i >= 1; i --) inv[i - 1] = inv[i] * i % mod;

	for (int i = 1; i <= N; i ++) inv2[i] = qpow(i, mod - 2, mod);
	a[4] = 8, b[4] = 4;
	for (int i = 5; i <= N; i ++) {
		b[i] = a[i - 1] * i % mod;
		a[i] = b[i] * inv2[i - 3] % mod * (i - 2) % mod;
	}
}


void solve() {
	int n;
	cin >> n;

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

	if (n == 1) {
		cout << v[1] << '\n';
		return;
	} else if (n == 2) {
		cout << (v[1] + v[2]) % mod << '\n';
		return;
	} else if (n == 3) {
		cout << (7 * v[1] + 6 * v[2] + 7 * v[3]) % mod * inv[3] % mod << '\n';
		return;
	}

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

	ll ans = 0;
	for (int i = 2; i < n; i ++) {
		ans += v[i] * (b[n] + fact[n]) % mod;
		ans %= mod;
	}
	ans += v[1] * ((a[n] + fact[n]) % mod) % mod;
	ans += v[n] * ((a[n] + fact[n]) % mod) % mod;
	ans %= mod;

	ans *= inv[n];
	ans %= mod;

	cout << ans << '\n';
}

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

	init();

	int t;
	cin >> t;
	while (t --) solve();
}

1008. 数字子序列

动态规划
字符串
数据结构
排序

按照长度分层，基数排序决定顺序 + 树状数组大型 DP。直接干成了超级大模拟（所以这题归我了）。

cpp

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int N = 100010, M = 450;
int f[M][N], g[M][N], a[N];
int b[N], c[N], rk[N], rk1[N], cnt[11];
int tr[N], n;

void add(int x, int v) {
    // cout << "[ADD] " << a[x] << ' ' <<  x << ' ' << v << endl;
    for (; x <= n; 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 T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        n = s.length();
        memset(rk, 0, sizeof(int) * (n + 2));
        int l = 0;
        while ((l + 1) * (l + 2) / 2 <= n) l++;
        for (int i = 1; i <= n; ++i) a[i] = s[i - 1] - '0', b[i] = i;
        b[n + 1] = n + 1;
        for (int j = 1; j <= l; ++j) {
            memset(cnt, 0, sizeof(cnt));
            memset(tr, 0, sizeof(int) * (n + 1));
            for (int i = 1; i <= n - j + 1; ++i) cnt[a[i] + 1]++;
            for (int i = 1; i <= 10; ++i) cnt[i] += cnt[i - 1];
            for (int i = 1; i <= n - j + 2; ++i) {
                int cur = b[i];
                if (cur == 1) continue;
                c[++cnt[a[cur - 1]]] = cur - 1;
            }
            memcpy(b, c, sizeof(int) * (n - j + 2));
            int t = 0;
            for (int i = 1; i <= n - j + 1; ++i) {
                int cur = b[i];
                if (i == 1) t++;
                else {
                    int pre = b[i - 1];
                    if (a[cur] != a[pre] || rk[cur + 1] != rk[pre + 1]) t++;
                }
                rk1[cur] = t;
            }
            memcpy(rk, rk1, sizeof(int) * (n - j + 2));
            for (int i = 1; i < j; ++i) f[j][i] = f[j - 1][i];
            for (int i = 1, k = 1; i <= n - j + 1; ++i) {
                int cur = b[i];
                while (rk[cur] != rk[b[k]]) add(b[k] + j - 1, f[j][b[k] + j - 1]), k++;
                if (a[cur] == 0 && j != 1) f[j][cur + j - 1] = g[j - 1][cur + j - 1];
                else f[j][cur + j - 1] = max(max(g[j - 1][cur + j - 1], query(cur - 1) + 1), g[j - 1][cur - 1] + 1);
            }
            // cout << endl;
            for (int i = 1; i <= n; ++i) {
                // cout << f[j][i] << ' ';
                g[j][i] = max(f[j][i], g[j][i - 1]);
            }
        }
        cout << g[l][n] << endl;
    }
    return 0;
}

1010. 游戏

前缀和
贪心
分类讨论

cpp

#pragma GCC optimize("O2")
#include <bits/stdc++.h>
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
const int N = 1e4 + 5;
const int INF = 1e18;
#define exp 1e-12
const int mod = 998244353;
void init() {}
void solve() {
    int n;
    cin >> n;
    vi a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vi sum(n + 1);
    for (int i = 1; i <= n; i++) {
        sum[i] = sum[i - 1] + a[i - 1];
    }
    for (int i = 1; i <= n/2; i++) {
        if(sum[n/2+1-i]-sum[0]>sum[n]-sum[n/2+i]){
            cout<<"YES"<<endl;
            return;
        }else if(sum[n/2+1-i]-sum[0]==sum[n]-sum[n/2+i]){
            continue;
        }else{
            cout<<"NO"<<endl;
            return;
        }
    }
    cout<<"NO"<<endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    init();
    int t = 1;
    cin >> t;

    while (t--) {
        solve();
    }

    return 0;
}

1012. 向量

构造
模拟
算术

cpp

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

#define int long long
#define vi vector<int>
using i128 = __int128_t;

const int LIM = 1000000000LL;

void solve() {
    int n, k, m;
    cin >> n >> k >> m;

    vi u(n);
    for (int &x : u) cin >> x;

    vi x(m), y(m);
    for (int i = 0; i < m; i++) {
        cin >> x[i];
        --x[i];
    }
    for (int i = 0; i < m; i++) {
        cin >> y[i];
        --y[i];
    }

    vi now = u;
    vi digit(n);
    vi residue(n, 0);

    int M = 1;

    while (M <= 2 * LIM) {
        for (int i = 0; i < n; i++) {
            digit[i] = now[i] % k;
            if (digit[i] < 0) digit[i] += k;
            residue[i] += digit[i] * M;
        }

        for (int i = 0; i < m; i++) {
            now[x[i]] -= digit[y[i]] * k;
        }

        for (int i = 0; i < n; i++) {
            now[i] -= digit[i];

            if (now[i] % k != 0) {
                cout << "No Solution\n";
                return;
            }

            now[i] /= k;
        }

        M *= k;
    }

    vi ans(n);

    for (int i = 0; i < n; i++) {
        if (residue[i] <= LIM) {
            ans[i] = residue[i];
        } else if (residue[i] >= M - LIM) {
            ans[i] = residue[i] - M;
        } else {
            cout << "No Solution\n";
            return;
        }
    }

    vector<i128> check(n);
    for (int i = 0; i < n; i++) {
        check[i] = ans[i];
    }

    for (int i = 0; i < m; i++) {
        check[x[i]] += (i128)k * ans[y[i]];
    }

    for (int i = 0; i < n; i++) {
        if (check[i] != (i128)u[i]) {
            cout << "No Solution\n";
            return;
        }
    }

    for (int i = 0; i < n; i++) {
        if (i) cout << ' ';
        cout << ans[i];
    }
    cout << '\n';
}

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

    int T;
    cin >> T;

    while (T--) {
        solve();
    }

    return 0;
}

1001. 小丑牌 ​

1004. 搭积木 ​

1005. 摩卡数 ​

1006. 开关灯 ​

1008. 数字子序列 ​

1010. 游戏 ​

1012. 向量 ​

1001. 小丑牌

1004. 搭积木

1005. 摩卡数

1006. 开关灯

1008. 数字子序列

1010. 游戏

1012. 向量