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

1001. 让路径生存吧！

离线查询
广度优先搜索
图论

cpp

#include<bits/stdc++.h>
#define int long long
#define mx 100010
using namespace std;
vector<int> e[mx];
vector<int> re[mx];

void solve(){
    int n,m,q;
    cin>>n>>m>>q;
     for(int i = 1;i <= n;i++){
        e[i].clear();
        re[i].clear();
    }
    for(int i = 1;i <= m;i++){
        int x,y;
        cin>>x>>y;
        e[x].push_back(y);
        re[y].push_back(x);
    }
    vector<int> p(q + 1);
    vector<int> act(n + 1,1);

    for(int i = 1;i <= q;i++){
        cin>>p[i];
        act[p[i]] = 0;
    }
    vector<int>can(n + 1, 0);
    queue<int> que;

    can[n] = 1;
    que.push(n);

    while(!que.empty()){
        int x = que.front();
        que.pop();

        for(int v:re[x]){
            if(act[v] && !can[v]){
                can[v] = 1;
                que.push(v);
            }
        }
    }

    if(can[1]){
        cout<<"YES"<<endl;
        return;
    }


    for(int i = q;i >= 1;i--){
        int x = p[i];
        act[x] = 1;

        if(!can[x]){
            for(int v:e[x]){
                if(can[v]){
                    can[x] = 1;
                    que.push(x);
                    break;
                }
            }
        }

        while(!que.empty()){
            int u = que.front();
            que.pop();

            for(int v:re[u]){
                if(act[v] && !can[v]){
                    can[v] = 1;
                    que.push(v);
                }
            }
        }

        if(can[1]){
            cout<<i - 1<<endl;
            return;
        }
    }

    cout<<"NO"<<endl;
}

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

    int T;
    cin>>T;

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

    return 0;
}

1002. 会自动求和的序列

线段树
懒标记线段树
线性代数

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 500010;
uint64_t t1[3], t2[3][3];
uint64_t I[3][3] = {{1, 0, 0}, {0, 1, 0}, {0, 0, 1}};

struct Mat {
    uint64_t a[3][3];

    void reset() {
        memcpy(a, I, sizeof(a));
    }

    bool isI() {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                if (a[i][j] != I[i][j]) return false;
            }
        }
        return true;
    }

    void mul(const Mat &b) {
        memset(t2, 0, sizeof(t2));
        for (int k = 0; k < 3; ++k) {
            for (int i = 0; i < 3; ++i) {
                for (int j = 0; j < 3; ++j) {
                    t2[i][j] += a[i][k] * b.a[k][j];
                }
            }
        }
        memcpy(a, t2, sizeof(a));
    }
};

struct Vec {
    uint64_t a[3];

    void mul(const Mat &b) {
        memset(t1, 0, sizeof(t1));
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                t1[i] += a[j] * b.a[j][i];
            }
        }
        memcpy(a, t1, sizeof(a));
    }
};

struct Node {
    uint64_t a;
    Vec b; // len b sb
    Mat c; // len & b + len * v & b + len * v + sb
} tr[N * 4];

void pushup(int u) {
    tr[u].a = tr[u << 1].a + tr[u << 1 | 1].a;
    for (int i = 0; i < 3; ++i) tr[u].b.a[i] = tr[u << 1].b.a[i] + tr[u << 1 | 1].b.a[i];
}

void pushdown(int u, int l, int r) {
    if (!tr[u].c.isI()) {
        tr[u << 1].b.mul(tr[u].c), tr[u << 1 | 1].b.mul(tr[u].c);
        tr[u << 1].c.mul(tr[u].c), tr[u << 1 | 1].c.mul(tr[u].c);
        tr[u].c.reset();
    }
}

void build(int u, int l, int r, uint64_t a[], uint64_t b[]) {
    tr[u].c.reset();
    if (l == r) tr[u] = {a[l], {1, b[l], b[l]}};
    else {
        int mid = l + r >> 1;
        build(u << 1, l, mid, a, b), build(u << 1 | 1, mid + 1, r, a, b);
        pushup(u);
    }

}

void modify(int u, int l, int r, int ql, int qr, uint64_t v) {
    if (ql <= l && r <= qr) {
        Mat t = {{{1, v, v}, {0, 1, 1}, {0, 0, 1}}};
        tr[u].c.mul(t);
        tr[u].b.mul(t);
    }
    else {
        pushdown(u, l, r);
        int mid = l + r >> 1;
        if (ql <= mid) modify(u << 1, l, mid, ql, qr, v);
        if (qr > mid) modify(u << 1 | 1, mid + 1, r, ql, qr, v);
        pushup(u);
    }
}

uint64_t query(int u, int l, int r, int ql, int qr) {
    if (ql <= l && r <= qr) return tr[u].a + tr[u].b.a[2];
    else {
        pushdown(u, l, r);
        uint64_t res = 0;
        int mid = l + r >> 1;
        if (ql <= mid) res += query(u << 1, l, mid, ql, qr);
        if (qr > mid) res += query(u << 1 | 1, mid + 1, r, ql, qr);
        return res;
    }
}

uint64_t a[N], b[N];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, q;
        cin >> n >> q;
        for (int i = 1; i <= n; ++i) cin >> a[i] >> b[i];
        build(1, 1, n, a, b);
        while (q--) {
            int op;
            cin >> op;
            if (op == 1) {
                int l, r;
                uint64_t x;
                cin >> l >> r >> x;
                if (l != 1) modify(1, 1, n, 1, l - 1, 0);
                modify(1, 1, n, l, r, x);
                if (r != n) modify(1, 1, n, r + 1, n, 0);
            }
            else {
                int l, r;
                cin >> l >> r;
                cout << query(1, 1, n, l, r) << '\n';
                modify(1, 1, n, 1, n, 0);
            }

            // for (int i = 1; i <= n; ++i) cout << query(1, 1, n, i, i) << ' ';
            // cout << "\n\n";
        }
    }
    return 0;
}

1003. 太近就不合法了

分块
组合数学
动态规划
离线查询

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 = 5e5 + 5;

void init() {}

struct Comb {
    int n;
    long long mod;
    vector<long long> fac, invfac;

    Comb(int _n, long long _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;
        }
    }

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

    long long A(int n, int m) {
        if (m < 0 || m > n) return 0;
        return fac[n] * invfac[n - m] % mod;
    }

    long long C(int n, int m) {
        if (m < 0 || m > n) return 0;
        return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
    }
};

Comb c(N, mod);
const int B=300;
int get(int n,int k){
    int res=0;
    for(int i=0;(i-1)*(k-1)<=n&&i<=n;i++){
        res+=c.C(n-(i-1)*(k-1),i);
        res%=mod;
    }
    return res;
}
void solve() {
    int n,q;
    cin>>n>>q;
    vi ans(q);
    vvpii q1(n+1);
    for(int i=0;i<q;i++){
        int m,k;
        cin>>m>>k;
        q1[k].pb({i,m});
    }
    for(int i=1;i<min(B,(int)sqrt(n));i++){
        if(q1[i].empty())continue;
        vi dp(n+1);
        dp[0]=1;
        for(int j=1;j<=n;j++){
            dp[j]=(dp[max(0ll,j-i)]+dp[j-1])%mod;
        }
        for(auto [id,m]:q1[i]){
            ans[id]=dp[n]-dp[max(0ll,m-i)]*dp[max(0ll,n-(m+i-1))]%mod;
            // if(get(n,i)-get(max(0ll,m-i),i)*get(max(0ll,n-(m+i-1)),i)%mod!=ans[id]){
            //     cout<<"Wrong"<<endl;
            //     return;
            // }
            ans[id]=(ans[id]+mod)%mod;
        }
    }
    for(int i=min(B,(int)sqrt(n));i<=n;i++){
        if(q1[i].empty())continue;
        for(auto [id,m]:q1[i]){
            ans[id]=get(n,i)-get(max(0ll,m-i),i)*get(max(0ll,n-(m+i-1)),i)%mod;
            ans[id]=(ans[id]+mod)%mod;
        }
    }
    for(int i=0;i<q;i++){
        cout<<ans[i]<<endl;
    }
}

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

    init();

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

    return 0;
}

1007. 用传送门来让网格连通吧

网格图
广度优先搜索
图搜索

cpp

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

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

struct FastIO {
	static const int S = 1 << 20;
	int idx = 0, len = 0;
	char buf[S];

	inline char gc() {
		if (idx >= len) {
			len = fread(buf, 1, S, stdin);
			idx = 0;
			if (!len) return 0;
		}
		return buf[idx++];
	}

	template<class T>
	inline void read(T &x) {
		char c = gc();
		while (c < '0' || c > '9') c = gc();
		x = 0;
		while (c >= '0' && c <= '9') {
			x = x * 10 + c - '0';
			c = gc();
		}
	}

	inline void read(char &c) {
		c = gc();
		while (c != '.' && c != '#') c = gc();
	}
} io;

int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};

void solve() {
	int n, m, k, q;
	io.read(n), io.read(m), io.read(k), io.read(q);

	vector<vector<char>> b(n + 1, vector<char>(m + 1));
	vector<vector<int>> a(n + 1, vector<int>(m + 1));

	for (int i = 1; i <= n; i ++)
		for (int j = 1; j <= m; j ++)
			io.read(b[i][j]);

	auto valid = [&](int x, int y) -> bool {
		return x >= 1 && x <= n && y >= 1 && y <= m;
	};

	int id = 0;
	for (int i = 1; i <= n; i ++) for (int j = 1; j <= m; j ++) {
		if (b[i][j] == '.' && a[i][j] == 0) {
			queue<pair<int, int>> que;
			a[i][j] = ++id;
			que.push({i, j});

			while (!que.empty()) {
				auto [x, y] = que.front();
				que.pop();

				for (int k = 0; k < 4; k ++) {
					int nx = x + dx[k];
					int ny = y + dy[k];

					if (valid(nx, ny) && b[nx][ny] == '.' && a[nx][ny] == 0) {
						a[nx][ny] = id;
						que.push({nx, ny});
					}
				}
			}
		}
	}

	vector<vector<int>> g(id + 1);
	vector<int> has_trans(id + 1);

	for (int i = 1; i <= k; i ++) {
		int x1, y1, x2, y2;
		io.read(x1), io.read(y1), io.read(x2), io.read(y2);

		int u = a[x1][y1], v = a[x2][y2];
		g[u].push_back(v);
		has_trans[u] = has_trans[v] = 1;
	}

	vector<int> trans_id(id + 1), inv(id + 1);
	int cnt = 0;

	for (int i = 1; i <= id; i ++) {
		if (has_trans[i]) {
			trans_id[i] = ++cnt;
			inv[cnt] = i;
		}
	}

	vector<vector<int>> f(cnt + 1, vector<int>(cnt + 1));

	for (int i = 1; i <= cnt; i ++) {
		queue<int> que;
		que.push(i);

		while (!que.empty()) {
			int u = que.front();
			que.pop();

			for (int v : g[inv[u]]) {
				v = trans_id[v];
				if (f[i][v] == 0) {
					f[i][v] = 1;
					que.push(v);
				}
			}
		}
	}

	auto calc = [&](int x, int y) -> bool {
		if (x == y) return 1;
		if (!has_trans[x] || !has_trans[y]) return 0;

		x = trans_id[x];
		y = trans_id[y];

		return f[x][y];
	};

	for (int i = 1; i <= q; i ++) {
		int x1, y1, x2, y2;
		io.read(x1), io.read(y1), io.read(x2), io.read(y2);
		int u = a[x1][y1], v = a[x2][y2];
		puts(calc(u, v) ? "1" : "0");
	}
}

int main() {
	int t;
	io.read(t);
	while (t --) solve();
}

1008. 分数越小还是越大越好

树形 DP
树
深度优先搜索

cpp

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

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

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

	vector<vector<int>> g(n + 1);
	vector<int> deg(n + 1), sz(n + 1);
	bool has3 = 0;
	for (int i = 1; i < n; i ++) {
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
		deg[u] ++, deg[v] ++;
	}

	for (int i = 1; i <= n; i ++) if (deg[i] >= 3) has3 = 1;

	ll ans1 = n + 1;
	//debug(has3) DL
	if (!has3) ans1 = n * 2 - 1;

	ll ans2 = 0;
	vector<int> fa(n + 1);
	auto dfs_sz = [&](auto self, int u, int f) -> void {
		fa[u] = f;
		sz[u] = 1;
		for (int v : g[u]) if (v != f) {
			self(self, v, u);
			sz[u] += sz[v];
		}
	};
	dfs_sz(dfs_sz, 1, 0);

	auto side = [&](int u, int v) -> int {
		if (fa[v] == u) return n - sz[v];
		return sz[u];
	};

	vector<vector<int>> nxt(n + 1, vector<int>(n + 1));

	auto dfs_nxt = [&](auto self, int s, int u, int f, int fi) -> void {
		nxt[s][u] = fi;
		for (int v : g[u]) if (v != f)
			self(self, s, v, u, fi);
	};

	for (int s = 1; s <= n; s ++) {
		nxt[s][s] = s;
		for (int v : g[s]) {
			dfs_nxt(dfs_nxt, s, v, s, v);
		}
	}

	vector<ll> one(n + 1);
	ll all = 1ll * n * (n + 1) / 2;

	for (int u = 1; u <= n; u ++) {
		ll bad = 0;
		for (int v : g[u]) {
			ll s = side(v, u);
			bad += s * (s + 1) / 2;
		}
		one[u] = all - bad;
	}

	vector<vector<ll>> dp(n + 1, vector<ll>(n + 1, -1));

	auto calc = [&](auto self, int u, int v) -> ll {
		if (dp[u][v] != -1) return dp[u][v];
		if (u == v) return dp[u][v] = one[u];

		int a = nxt[u][v];
		int b = nxt[v][u];

		ll w = 1ll * side(u, a) * side(v, b);
		ll res = w + max(self(self, a, v), self(self, u, b));

		dp[u][v] = dp[v][u] = res;
		return res;
	};

	for (int u = 1; u <= n; u ++) for (int v = u; v <= n; v ++) {
		ans2 = max(ans2, calc(calc, u, v));
	}
	cout << ans1 << ' ' << ans2 << '\n';
}

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

	//freopen("in.txt", "r", stdin);

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

1009. 价值总是越大越好

组合数学
排序
贪心

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 = 5e5 + 5;

void init() {}

struct Comb {
    int n;
    long long mod;
    vector<long long> fac, invfac;

    Comb(int _n, long long _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;
        }
    }

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

    long long A(int n, int m) {
        if (m < 0 || m > n) return 0;
        return fac[n] * invfac[n - m] % mod;
    }

    long long C(int n, int m) {
        if (m < 0 || m > n) return 0;
        return fac[n] * invfac[m] % mod * invfac[n - m] % mod;
    }
};

Comb c(N, mod);

void solve() {
    int n;
    cin >> n;
    vi a(2 * n);
    vi vis(2 * n + 1, 0);
    for (int i = 0; i < 2 * n; i++) {
        cin >> a[i];
        vis[a[i]] = 1;
    }
    int cnt4 = 0;
    vi x;
    for (int i = 0; i < n; i++) {
        int a1 = a[i * 2];
        int a2 = a[i * 2 + 1];
        if (a1 == 0 && a2 == 0) {
            cnt4++;
        } else if (a1 == 0 || a2 == 0) {
            x.pb(max(a1, a2));
        }
    }
    vi b;
    for (int i = 1; i <= 2 * n; i++) {
        if (!vis[i]) b.pb(i);
    }
    sort(all(x));
    int m = sz(b);
    int cnt5 = sz(x);
    int q = 0;
    while (q < cnt5) {
        int k = cnt4 + q;
        if (b[m - k - 1] > x[q]) q++;
        else break;
    }
    int k = cnt4 + q;
    int ans = c.fac[k] * c.fac[m - k] % mod;
    ans = ans * c.qpow(2, cnt4) % 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;
}

1010. 合并之后字典序就变小了

动态规划
前缀和
算术

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 = 2e5 + 5;

void init() {}

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

    vi a(n);
    for (auto &x : a) cin >> x;

    int S[3] = {1, 0, 0};
    int H[3] = {1, 0, 0};

    int pre = 0;
    int ans = 0;

    for (auto x : a) {
        pre = (pre + x) % 3;

        int b = pre;

        int x1 = (b + 2) % 3;
        int x2 = (b + 1) % 3;

        ans += S[x1];
        ans += S[x2] + H[x2];
        ans %= mod;

        S[b] = (S[b] * 3 + 1) % mod;
        H[b] = S[b];

        int p = (b + 2) % 3;
        H[p] = H[p] * 3 % mod;
    }

    cout << ans % mod << endl;
}

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

    init();

    int T;
    cin >> T;
    while (T--) solve();

    return 0;
}

1012. 数一数环的个数

组合数学
树结构集合与映射
算术

cpp

#include <iostream>
#include <map>

using namespace std;

typedef long long LL;
const int MOD = 998244353;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        map<pair<int, int>, int> mp;
        int n, m, k;
        cin >> n >> m >> k;
        for (int i = 1; i <= m; ++i) {
            int x, y;
            cin >> x >> y;
            if (x > y) swap(x, y);
            mp[{x, y}]++;
        }
        if (k != 2) cout << 0 << '\n';
        else {
            LL res = 0;
            for (auto &[a, b] : mp) {
                res += (LL)b * (b - 1) / 2;
                res %= MOD;
            }
            cout << res << '\n';
        }
    }
    return 0;
}

1001. 让路径生存吧！ ​

1002. 会自动求和的序列 ​

1003. 太近就不合法了 ​

1007. 用传送门来让网格连通吧 ​

1008. 分数越小还是越大越好 ​

1009. 价值总是越大越好 ​

1010. 合并之后字典序就变小了 ​

1012. 数一数环的个数 ​

1001. 让路径生存吧！

1002. 会自动求和的序列

1003. 太近就不合法了

1007. 用传送门来让网格连通吧

1008. 分数越小还是越大越好

1009. 价值总是越大越好

1010. 合并之后字典序就变小了

1012. 数一数环的个数