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

1002. The World Cup

排序
贪心
数学

cpp

#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 = 1e6 + 5;

void init() {}
void solve() {
    int n, w;
    cin >> n >> w;
    vi a(n);
    for (int i = 0; i < n; i++) cin >> a[i];
    sort(all(a));
    db ans = 0;
    db s = 0;
    for (int i = 0; i < n; i++)s+=1.0/a[i];
    ans=w/s;
    db cur=0;
    for(int i=0;i<n;i++){
        cur+=(a[i]-1)*1.0/a[i];
        ans=max(ans,(w/cur)*(i));
    }
    cout<<fixed<<setprecision(10)<<ans<<endl;
}

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

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

1003. Best

最长上升子序列
二分查找
动态规划

cpp

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 100010;

LL a[N];
__int128_t b[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        fill(b, b + N, 0);
        int n, len = 0;
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) {
            if (a[i] >= b[len]) {
                len++;
                b[len] = a[i] + b[len - 1];
            }
            else {
                int l = 1, r = len;
                while (l < r) {
                    int mid = l + r >> 1;
                    if (b[mid] > a[i]) r = mid;
                    else l = mid + 1;
                }
                b[l] = min(b[l], a[i] + b[l - 1]);
            }
        }
        cout << len << '\n';
    }
    return 0;
}

1004. toys

最小费用最大流
最短路
图论

cpp

#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 = 1e6 + 5;
vi prime;
void init() {}
struct MCMF {
    struct Edge {
        int to, rev, cap;
        long long cost;
    };

    int n;
    vector<vector<Edge>> g;

    MCMF(int n) : n(n), g(n + 1) {}

    void add(int u, int v, int c, long long w) {
        g[u].push_back({v, (int)g[v].size(), c, w});
        g[v].push_back({u, (int)g[u].size() - 1, 0, -w});
    }

    pair<int, long long> flow(int s, int t) {
        int mf = 0;
        long long mc = 0;

        const long long INF = 4e18;

        vector<long long> h(n + 1);
        vector<long long> dis(n + 1);
        vector<int> pv(n + 1), pe(n + 1);

        while (1) {
            fill(dis.begin(), dis.end(), INF);
            priority_queue<pair<long long,int>,
                           vector<pair<long long,int>>,
                           greater<pair<long long,int>>> pq;

            dis[s] = 0;
            pq.push({0, s});

            while (!pq.empty()) {
                auto [d, u] = pq.top();
                pq.pop();

                if (d != dis[u])
                    continue;

                for (int i = 0; i < (int)g[u].size(); i++) {
                    auto &e = g[u][i];

                    if (e.cap == 0)
                        continue;

                    long long nd = d + e.cost + h[u] - h[e.to];

                    if (nd < dis[e.to]) {
                        dis[e.to] = nd;
                        pv[e.to] = u;
                        pe[e.to] = i;
                        pq.push({nd, e.to});
                    }
                }
            }

            if (dis[t] == INF)
                break;

            for (int i = 1; i <= n; i++) {
                if (dis[i] < INF)
                    h[i] += dis[i];
            }

            int aug = INT_MAX;

            for (int v = t; v != s; v = pv[v]) {
                aug = min(aug, g[pv[v]][pe[v]].cap);
            }

            for (int v = t; v != s; v = pv[v]) {
                auto &e = g[pv[v]][pe[v]];
                e.cap -= aug;
                g[v][e.rev].cap += aug;
            }

            mf += aug;
            mc += 1LL * aug * h[t];
        }

        return {mf, mc};
    }
};
void solve() {
    int n, m;
    cin >> n >> m;
    int s = n + m + 1, t = n + m + 2;
    MCMF mcmf(t);
    for(int i = 1; i <= n; i++){
        int g;
        cin >> g;
        mcmf.add(s, i, 1, 0);
        for(int j = 0; j < g; j++){
            int x;
            cin >> x;
            mcmf.add(i, n + x, 1, 0);
        }
    }
    for(int i = 1; i <= m; i++){
        int y;
        cin >> y;
        for(int j = 0; j < y; j++){
            int x;
            cin >> x;
            mcmf.add(n + i, t, 1, x);
        }
    }
    cout << mcmf.flow(s, t).s << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();

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

    return 0;
}

1005. GCD

质因数分解
埃氏筛
数论

cpp

#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 = 1e6 + 5;
vi prime;
void init() {
    vi vis(N + 1);
    for (int i = 2; i <= N; i++) {
        if (!vis[i]) {
            prime.pb(i);
            for (int j = i * 2; j <= N; j += i) {
                vis[j] = 1;
            }
        }
    }
}
void solve() {
    int n;
    cin >> n;
    if (n == 1) {
        cout << 0 << endl;
        return;
    }
    int mxcnt = 1;
    for (int p : prime) {
        if (p > 1000000) break;
        if (n % p == 0) {
            int cnt = 0;
            while (n % p == 0) {
                n /= p;
                cnt++;
            }
            mxcnt = max(mxcnt, cnt);
        }
    }

    int g = sqrtl(n);
    while ((g + 1) <= n / (g + 1)) g++;
    while (g > n / g) g--;
    if (n != 1 && g * g == n) {
        mxcnt = max(mxcnt, 2ll);
    }

    int ans = 0;
    while (mxcnt > 0) {
        ans++;
        mxcnt /= 2;
    }
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();

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

    return 0;
}

1006. Special Judge

构造
数论

cpp

#include <iostream>

using namespace std;

typedef long long LL;
const int N = 1510;
bool f[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        fill(f, f + N, 0);
        int n;
        cin >> n;
        f[1] = true;
        for (int i = 3; i <= n; i += 2) {
            if (i % 3 == 0) {
                f[i] = true;
                f[i / 3 * 2] = true;
                f[i / 3] = false;

                int j = i / 3 * 2;
                while (j % 3 == 0) {
                    f[j / 3 * 2] = true;
                    f[j / 3] = false;

                    j = j / 3 * 2;
                }
            }
            else f[i] = true;
        }
        cout << (n + 1) / 2 << '\n';
        for (int i = 1; i <= n; ++i) {
            if (f[i]) cout << i << ' ';
        }
        cout << '\n';
    }
    return 0;
}

1008. FWT

线性代数
线段树
位掩码

cpp

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

const int mod = 998244353;

struct Mat {
    int a[4][4];

    Mat(bool id = false) {
        memset(a, 0, sizeof(a));
        if (id) {
            for (int i = 0; i < 4; i++) a[i][i] = 1;
        }
    }
};

Mat operator*(const Mat& A, const Mat& B) {
    Mat C;

    for (int i = 0; i < 4; i++) {
        for (int k = 0; k < 4; k++) {
            if ((i & k) != i || A.a[i][k] == 0) continue;

            for (int j = 0; j < 4; j++) {
                if ((k & j) != k || B.a[k][j] == 0) continue;

                C.a[i][j] =
                    (C.a[i][j] +
                     1LL * A.a[i][k] * B.a[k][j]) % mod;
            }
        }
    }

    return C;
}

Mat make_mat(int lb, int rb, int C) {
    Mat M;

    const int va[3] = {0, 1, 1};
    const int vb[3] = {0, 0, 1};
    const int w[3] = {1, C, 1};

    for (int s = 0; s < 4; s++) {
        int p = s & 1;
        int q = (s >> 1) & 1;

        for (int z = 0; z < 3; z++) {
            int a = va[z];
            int b = vb[z];

            if (!p && a > rb) continue;
            if (!q && b < lb) continue;

            int ns = s;

            if (!p && a < rb) ns |= 1;
            if (!q && b > lb) ns |= 2;

            M.a[s][ns] += w[z];
            if (M.a[s][ns] >= mod) M.a[s][ns] -= mod;
        }
    }

    return M;
}

struct Seg {
    int n;
    vector<Mat> tr;

    Seg(const vector<Mat>& a) {
        n = 1;
        while (n < (int)a.size()) n <<= 1;

        tr.assign(2 * n, Mat(true));

        for (int i = 0; i < (int)a.size(); i++) {
            tr[n + i] = a[i];
        }

        for (int i = n - 1; i; i--) {
            tr[i] = tr[i << 1] * tr[i << 1 | 1];
        }
    }

    void set(int p, const Mat& v) {
        p += n;
        tr[p] = v;

        while (p >>= 1) {
            tr[p] = tr[p << 1] * tr[p << 1 | 1];
        }
    }

    int answer() const {
        int ans = 0;

        for (int s = 0; s < 4; s++) {
            ans += tr[1].a[0][s];
            if (ans >= mod) ans -= mod;
        }

        return ans;
    }
};

int get_C(int n, const vector<pair<int, int>>& edges) {
    vector<int> need(n);

    for (int i = 0; i < n; i++) {
        need[i] |= 1 << 0;
        need[n - 1] |= 1 << i;
    }

    for (auto [a, b] : edges) {
        --a;
        --b;
        need[b] |= 1 << a;
    }

    int C = 0;
    int lim = 1 << (n - 2);

    for (int mask = 0; mask < lim; mask++) {
        int S = 1 | (mask << 1);
        int req = 0;

        int z = S;
        while (z) {
            int v = __builtin_ctz(z);
            req |= need[v];
            z &= z - 1;
        }

        if ((req & ~S) == 0) C++;
    }

    return C;
}

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

    vector<pair<int, int>> edges(m);
    for (auto& [a, b] : edges) cin >> a >> b;

    string l, r;
    cin >> l >> r;

    int nl = l.size();
    int nr = r.size();
    int len = max(nl, nr);

    int offl = len - nl;
    int offr = len - nr;

    l = string(offl, '0') + l;
    r = string(offr, '0') + r;

    int C = get_C(n, edges);

    vector<Mat> a(len);

    for (int i = 0; i < len; i++) {
        a[i] = make_mat(l[i] - '0', r[i] - '0', C);
    }

    Seg seg(a);

    cout << seg.answer() << '\n';

    while (t--) {
        int op, i;
        cin >> op >> i;
        --i;

        int p;

        if (op == 0) {
            p = offl + i;
            l[p] ^= 1;
        } else {
            p = offr + i;
            r[p] ^= 1;
        }

        seg.set(p, make_mat(l[p] - '0', r[p] - '0', C));

        cout << seg.answer() << '\n';
    }
}

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

    int T;
    cin >> T;

    while (T--) solve();

    return 0;
}

1009. Six Grade

图搜索
队列
图论

cpp

#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 = 1e6 + 5;
vi prime;
void init() {}
void solve() {
    int n;
    cin >> n;
    vvi g(n + 1);
    vi deg(n + 1);
    for(int i = 1; i <= n; i++){
        int u,v;
        cin >> u >> v;
        g[u].pb(v);
        g[v].pb(u);
        deg[u]++;
        deg[v]++;
    }
    queue<int> q;
    vi rm(n + 1);
    for (int i = 1; i <= n; i++) {
        if (deg[i] <= 1) q.push(i);
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (rm[u]) continue;
        rm[u] = 1;
        for (int v : g[u]) {
            if (rm[v]) continue;
            deg[v]--;
            if (deg[v] == 1) q.push(v);
        }
    }
    int sum=n-accumulate(all(rm),0);
    int ans=sum*(mod+1)/2%mod+n-sum;
    cout << ans << endl;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    init();

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

    return 0;
}

1010. Random

概率论
模逆元
快速幂

cpp

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

const ll mod = 998244353;

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 inv(ll x) {
	x %= mod;
	if (x < 0) x += mod;
	return qpow(x, mod - 2, mod);
}

void solve() {
	ll w, l;
	cin >> w >> l;

	ll k = inv(qpow(w, l, mod));
	ll q = (1 - k + mod) % mod;

	ll s = ((l + q * inv(1 - q) % mod) % mod) * inv(1 - q) % mod;
	ll E = k * s % mod;

	cout << E << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t;
	cin >> t;
	while (t --) solve();
}

1011. Mex

CDQ 分治
数据结构
离线查询

cpp

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

template <typename T>
struct Bit {
    int n;
    vector<T> tree;

    Bit(int _n):n(_n), tree(_n + 1, T()){}

    void add(int idx, T val) {
        for (; idx <= n; idx += idx & -idx) tree [idx] += val;
    }

    T query(int idx) {
        T res = T();
        for (; idx; idx -= idx & -idx) res += tree[idx];
        return res;
    }

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

struct Node {
	int x, y, z, id;
};

bool cmp1(const Node& a, const Node& b) {
	return a.x > b.x;
}
bool cmp2(const Node& a, const Node& b) {
	return a.y > b.y;
}

ll C(ll n, int k) {
	if (k == 2) return n * (n - 1) / 2;
	if (k == 3) return n * (n - 1) * (n - 2) / 6;
	return 0;
}

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

	vector<Node> a(n);
	for (int i = 0; i < n; i ++) cin >> a[i].x;
	for (int i = 0; i < n; i ++) cin >> a[i].y;
	for (int i = 0; i < n; i ++) cin >> a[i].z;
	for (int i = 0; i < n; i ++) a[i].id = i;

	vector<ll> d12(n), d13(n), d23(n), d123(n);
	Bit<int> bit123(n);

	auto cdq = [&](auto self, int l, int r) -> void {
		if (l >= r) return;

		int mid = (l + r) >> 1;
		self(self, l, mid), self(self, mid + 1, r);

		sort(a.begin() + l, a.begin() + mid + 1, cmp2);
		sort(a.begin() + mid + 1, a.begin() + r + 1, cmp2);

		int i = l, cnt = 0;
		for (int j = mid + 1; j <= r; j ++) {
			while (i <= mid && a[i].y > a[j].y) {
				bit123.add(a[i].z + 1, 1);
				i ++;
				cnt ++;
			}
			d123[a[j].id] += cnt - bit123.query(a[j].z + 1);
		}

		for (int j = l; j < i; j ++) bit123.add(a[j].z + 1, -1);
	};
	sort(a.begin(), a.end(), cmp1);
	cdq(cdq, 0, n - 1);
	sort(a.begin(), a.end(), cmp1);

	Bit<int> bit12(n), bit13(n);

	for (int i = 0; i < n; i ++) {
		auto [x, y, z, id] = a[i];

		d12[id] = i - bit12.query(y + 1);
		d13[id] = i - bit13.query(z + 1);

		bit12.add(y + 1, 1);
		bit13.add(z + 1, 1);
	}
	sort(a.begin(), a.end(), cmp2);

	Bit<int> bit23(n);

	for (int i = 0; i < n; i ++) {
		auto [x, y, z, id] = a[i];
		d23[id] = i - bit23.query(z + 1);
		bit23.add(z + 1, 1);
	};

	ll ans = 1 + n + C(n, 2) + C(n, 3);

	for (int i = 0; i < n; i ++) {
		ans -= d123[i];
		ans -= C(d12[i], 2);
		ans -= C(d13[i], 2);
		ans -= C(d23[i], 2);
		ans += 2 * C(d123[i], 2);
	}
	cout << ans << '\n';
}

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

	//init();

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

1002. The World Cup ​

1003. Best ​

1004. toys ​

1005. GCD ​

1006. Special Judge ​

1008. FWT ​

1009. Six Grade ​

1010. Random ​

1011. Mex ​

1002. The World Cup

1003. Best

1004. toys

1005. GCD

1006. Special Judge

1008. FWT

1009. Six Grade

1010. Random

1011. Mex