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

1001. 今晚吃什么

AC 自动机
最近公共祖先
树
排序

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;

struct AC {
    struct Node {
        int32_t ch[26];
        int32_t fail;

        Node() {
            memset(ch, 0, sizeof ch);
            fail = 0;
        }
    };

    vector<Node> tr;
    vector<int32_t> bfs;

    AC() {
        tr.emplace_back();
    }

    int32_t add(const string &s) {
        int32_t u = 0;

        for (char c : s) {
            int x = c - 'a';

            if (!tr[u].ch[x]) {
                tr[u].ch[x] = tr.size();
                tr.emplace_back();
            }

            u = tr[u].ch[x];
        }

        return u;
    }

    void build() {
        queue<int32_t> q;

        bfs.clear();
        bfs.pb(0);

        for (int c = 0; c < 26; c++) {
            int32_t v = tr[0].ch[c];
            if (v)
                q.push(v);
        }

        while (!q.empty()) {
            int32_t u = q.front();
            q.pop();

            bfs.pb(u);

            for (int c = 0; c < 26; c++) {
                int32_t v = tr[u].ch[c];

                if (v) {
                    tr[v].fail = tr[tr[u].fail].ch[c];
                    q.push(v);
                } else {
                    tr[u].ch[c] = tr[tr[u].fail].ch[c];
                }
            }
        }
    }
};

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

    vector<string> a(n);
    vector<int32_t> ed(n);

    AC ac;

    int S = 0;

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        S += a[i].size();
        ed[i] = ac.add(a[i]);
    }

    ac.build();

    int M = ac.tr.size();

    vector<vector<int32_t>> son(M);

    for (int u = 1; u < M; u++)
        son[ac.tr[u].fail].pb(u);

    vector<int32_t> tin(M), dep(M);

    int32_t tim = 0;

    vector<pair<int32_t, int32_t>> st;

    st.pb({0, 0});

    while (!st.empty()) {
        auto &[u, it] = st.back();

        if (it == 0)
            tin[u] = tim++;

        if (it == (int32_t)son[u].size()) {
            st.pop_back();
            continue;
        }

        int32_t v = son[u][it++];

        dep[v] = dep[u] + 1;

        st.pb({v, 0});
    }

    int LOG = 1;

    while ((1LL << LOG) <= M)
        LOG++;

    vector<vector<int32_t>> up(LOG, vector<int32_t>(M));

    for (int u = 0; u < M; u++)
        up[0][u] = ac.tr[u].fail;

    for (int k = 1; k < LOG; k++) {
        for (int u = 0; u < M; u++)
            up[k][u] = up[k - 1][up[k - 1][u]];
    }

    auto lca = [&](int32_t a, int32_t b) {
        if (dep[a] < dep[b])
            swap(a, b);

        int d = dep[a] - dep[b];

        for (int k = 0; k < LOG; k++) {
            if (d >> k & 1)
                a = up[k][a];
        }

        if (a == b)
            return a;

        for (int k = LOG - 1; k >= 0; k--) {
            if (up[k][a] != up[k][b]) {
                a = up[k][a];
                b = up[k][b];
            }
        }

        return (int32_t)ac.tr[a].fail;
    };

    vector<vector<int32_t>> path(n), cut(n);

    for (int i = 0; i < n; i++) {
        int32_t u = 0;

        path[i].reserve(a[i].size());

        for (char c : a[i]) {
            u = ac.tr[u].ch[c - 'a'];
            path[i].pb(u);
        }

        sort(path[i].begin(), path[i].end(),
             [&](int32_t x, int32_t y) {
                 return tin[x] < tin[y];
             });

        cut[i].reserve(max<int>(0, sz(path[i]) - 1));

        for (int j = 1; j < sz(path[i]); j++)
            cut[i].pb(lca(path[i][j - 1], path[i][j]));
    }

    vector<int> ways(n + 1);

    ways[1] = n;

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

    vector<int> w(M);
    vector<int> pre(M);

    int H = min<int>(
        n,
        (sqrtl(8.0L * S + 1) - 1) / 2 + 2
    );

    for (int len = 2; len <= H; len++) {
        for (int i = 0; i < n; i++)
            w[ed[i]] = cur[i];

        pre[0] = 0;

        for (int i = 1; i < sz(ac.bfs); i++) {
            int32_t u = ac.bfs[i];

            pre[u] = pre[ac.tr[u].fail] + w[u];

            if (pre[u] >= mod)
                pre[u] -= mod;
        }

        int sum = 0;
        bool ok = false;

        for (int i = 0; i < n; i++) {
            if ((int)a[i].size() < len) {
                nxt[i] = 0;
                continue;
            }

            int val = 0;

            for (int32_t v : path[i])
                val += pre[v];

            for (int32_t v : cut[i])
                val -= pre[v];

            val %= mod;

            if (val < 0)
                val += mod;

            val -= cur[i];

            if (val < 0)
                val += mod;

            nxt[i] = val;

            sum += val;

            if (sum >= mod)
                sum -= mod;

            if (val)
                ok = true;
        }

        ways[len] = sum;

        if (!ok)
            break;

        cur.swap(nxt);
    }

    for (int k = 0; k < n; k++) {
        cout << ways[n - k];

        if (k + 1 != n)
            cout << ' ';
    }

    cout << endl;
}

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

    int T;
    cin >> T;

    while (T--)
        solve();

    return 0;
}

1002. 今晚吃……

暴力
字符串

cpp

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

void solve() {
	string s;
	cin >> s;

	int n = size(s);
	vector<int> vis(4);

	for (int i = 1; i < n; i ++) {
		int v = 0;
		if (s[i - 1] == '0' && s[i] == '0') v = 0;
		else if (s[i - 1] == '0' && s[i] == '1') v = 1;
		else if (s[i - 1] == '1' && s[i] == '0') v = 2;
		else v = 3;
		vis[v] = 1;
	}

	vector<int> pos;
	for (int i = 0; i < 4; i ++) if (vis[i]) pos.push_back(i);

	vector<int> p(size(pos));
	iota(p.begin(), p.end(), 0);

	int ans = 1000000;

	do {
		string check = "#";
		for (auto i : p) {
			int v = pos[i];
			if (v == 0) {
				if (check.back() == '0') check += '0';
				else check += "00";
			} else if (v == 1) {
				if (check.back() == '0') check += '1';
				else check += "01";
			} else if (v == 2) {
				if (check.back() == '1') check += '0';
				else check += "10";
			} else {
				if (check.back() == '1') check += '1';
				else check += "11";
			}
		}
		check = check.substr(1);
		int len = size(check);
		int pos = 0;
		bool ok = 0;
		for (auto &c : s) {
			if (c == check[pos]) pos ++;
			if (pos >= len) {
				ok = 1;
				break;
			}
		}
		if (ok) ans = min(ans, len);

	} while (next_permutation(p.begin(), p.end()));

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

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

1003. 今晚吃春天

回溯
暴力
模拟

cpp

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

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

int to(char c) {
	int num;
	if (c >= '3' && c <= '9') num = c - '2';
	else if (c == 'T') num = 8;
	else if (c == 'J') num = 9;
	else if (c == 'Q') num = 10;
	else if (c == 'K') num = 11;
	else if (c == 'A' || c == '1') num = 12;
	else if (c == '2') num = 13;
	else if (c == 'w') num = 14;
	else if (c == 'W') num = 15;
	return num;
}

bool valid = 0;
int cnt[20], r[20];
int lft = 0, mx_x = 0, mx_a = 0;

bool last() {
	for (int i = 1; i <= 15; i ++) if (lft == cnt[i]) return 1;

	if (lft == 5) for (int i = 1; i <= 13; i ++) if (cnt[i] == 3) {
		for (int j = 1; j <= 15; j ++) {
			if (i == j) continue;
			if (cnt[j] == 2) {
				return 1;
			}
		}
	}

	for (int k = 1; k <= 3; k ++) {
		if (lft % k) continue;
		int len = lft / k;
		if (k == 1) if (len < 5) return 0;
		if (k == 2) if (len < 3) return 0;
		if (k == 3) if (len < 2) return 0;
		for (int l = 1, rr = l + len - 1; rr <= 12; l ++, rr ++) {
			int ok = 1;
			for (int j = l; j <= rr; j ++) if (cnt[j] != k) {
				ok = 0;
				break;
			}
			if (ok == 1) {
				return 1;
			}
		}
	}
	if (lft % 5) return 0;
	int len = lft / 5;
	if (len == 1) return 0;

	for (int l = 1, rr = l + len - 1; rr <= 12; l ++, rr ++) {
		int ok = 1;
		for (int j = l; j <= rr; j ++) if (cnt[j] < 3) {
			ok = 0;
			break;
		}
		if (ok) {
			for (int j = l; j <= rr; j ++) cnt[j] -= 3;
			for (int j = 1; j <= 15; j ++) if (cnt[j] % 2) {
				ok = 0;
				break;
			}
			if (ok) {
				return 1;
			}
			for (int j = l; j <= rr; j ++) cnt[j] += 3;
		}
	}

	return 0;
}

void dfs() {
	if (lft == 0 || valid || last()) {
		valid = 1;
		return;
	}

	if (cnt[14] == 2 && cnt[15] == 2) {
		cnt[14] -= 2;
		cnt[15] -= 2;
		lft -= 4;
		dfs();
		lft += 4;
		cnt[14] += 2;
		cnt[15] += 2;
	}

	for (int i = 1; i <= 13; i ++) {
		for (int j = 4; j <= cnt[i]; j ++) {
			if (j > mx_x || (j == mx_x && i >= mx_a)) {
				lft -= j;
				cnt[i] -= j;
				dfs();
				lft += j;
				cnt[i] += j;
			}
		}
	}
}

void init() {
	memset(cnt, 0, sizeof cnt);
	lft = 33, valid = 0, mx_x = 0, mx_a = 0;
	string s;
	cin >> s;

	for (auto &c : s) cnt[to(c)] ++;
	for (int i = 1; i <= 13; i ++) r[i] = 8 - cnt[i];
	r[14] = 2 - cnt[14], r[15] = 2 - cnt[15];

	for (int i = 1; i <= 13; i ++) {
		if (r[i] > mx_x) {
			mx_x = r[i];
			mx_a = i;
		} else if (r[i] == mx_x) {
			mx_a = i;
		}
	}
}

void solve() {
	init();

	if (r[14] == 2 && r[15] == 2) {
		//debug(last()) DL
		if (last()) cout << "Yes\n";
		else cout << "No\n";
		return;
	}

	dfs();

	if (valid) cout << "Yes\n";
	else cout << "No\n";
}

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

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

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

1004. 今晚吃转转

树同构
哈希
随机化
树重心

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 = 5e2 + 5;
void init() {}
ull mask = mt19937_64(chrono::steady_clock::now().time_since_epoch().count())();

ull sft(ull x) {
    x ^= mask;
    x ^= x << 13;
    x ^= x >> 7;
    x ^= x << 17;
    x ^= mask;
    return x;
}
vector<vector<int>> useful_func(vector<vector<int>> &adj) {
    int n = adj.size() - 1;

    vector<int> flg(n + 1);
    vector<int> values;
    for (int i = 1; i <= n; ++i) {
        if (adj[i].size() != 2) {
            values.emplace_back(i);
            flg[i] = true;
        }
    }
    vector<vector<int>> res(values.size() + 1);

    auto get = [&](int x) -> int {
        return lower_bound(values.begin(), values.end(), x) - values.begin() + 1;
    };

    auto dfs = [&](auto &&self, int x, int fa, int p) -> void {
        for (int &y : adj[x]) {
            if (y == fa) continue;
            if (flg[y]) {
                int t = get(y);
                res[p].emplace_back(t);
                res[t].emplace_back(p);
                self(self, y, x, t);
            }
            else self(self, y, x, p);
        }
    };

    dfs(dfs, values[0], 0,  1);
    return res;
}

bool check(vvi &g) {
    int n = sz(g) - 1;
    if (n & 1)
        return false;
    int c = n / 2;
    vi siz(n + 1);
    pii cut = {-1, -1};
    auto dfs = [&](auto &&self, int u, int fa) -> void {
        siz[u] = 1;
        for (int v : g[u]) {
            if (v == fa)
                continue;
            self(self, v, u);
            siz[u] += siz[v];
            if (siz[v] == c)
                cut = {u, v};
        }
    };
    dfs(dfs, 1, 0);
    if (cut.f == -1)
        return false;
    int a = cut.f, b = cut.s;
    auto gs = [&](int st, int ban) -> pair<ull, ull> {
        vi s(n + 1);
        vi cen;
        auto dfs1 = [&](auto &&self, int u, int fa) -> void {
            s[u] = 1;
            int mx = 0;
            for (int v : g[u]) {
                if (v == fa)
                    continue;
                if ((u == st && v == ban) || (u == ban && v == st))
                    continue;

                self(self, v, u);
                s[u] += s[v];
                mx = max(mx, s[v]);
            }
            mx = max(mx, c - s[u]);
            if (mx * 2 <= c)
                cen.pb(u);
        };
        dfs1(dfs1, st, 0);
        auto dfs2 = [&](auto &&self, int u, int fa) -> ull {
            ull h = 1;
            for (int v : g[u]) {
                if (v == fa)
                    continue;
                if ((u == st && v == ban) || (u == ban && v == st))
                    continue;
                h += sft(self(self, v, u));
            }
            return h;
        };
        ull h1 = dfs2(dfs2, cen[0], 0);
        ull h2 = h1;
        if (sz(cen) == 2)
            h2 = dfs2(dfs2, cen[1], 0);

        if (h1 > h2)
            swap(h1, h2);
        return {h1, h2};
    };
    return gs(a, b) == gs(b, a);
}

vector<vector<ull>> get(vvi &a) {
    int n = sz(a) - 1;
    vi siz(n + 1);
    vi cen;

    auto dfs1 = [&](auto &&self, int u, int fa) -> void {
        siz[u] = 1;
        int mx = 0;
        for (int v : a[u]) {
            if (v == fa)
                continue;
            self(self, v, u);
            siz[u] += siz[v];
            mx = max(mx, siz[v]);
        }
        mx = max(mx, n - siz[u]);
        if (mx * 2 <= n)
            cen.pb(u);
    };

    dfs1(dfs1, 1, 0);

    auto dfs2 = [&](auto &&self, int u, int fa) -> ull {
        ull h = 1;
        for (int v : a[u]) {
            if (v == fa)
                continue;
            h += sft(self(self, v, u));
        }
        return h;
    };
    vector<vector<ull>> res;
    for (int rt : cen) {
        vector<ull> cur;
        for (int v : a[rt]) {
            cur.pb(dfs2(dfs2, v, rt));
        }
        res.pb(cur);
    }
    return res;
}
int gcd(int a, int b) {
    return b ? gcd(b, a % b) : a;
}
vi get1(int x) {
    vi res;
    for (int i = 1; i * i <= x; i++) {
        if (x % i == 0) {
            res.pb(i);
            if (i * i != x)
                res.pb(x / i);
        }
    }
    return res;
}
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);
    }
    g = useful_func(g);
    // for(int i = 1; i <sz(g); i++){
    //     for(auto x : g[i]){
    //         cout << i << " " << x << endl;
    //     }
    // }
    vector<vector<ull>> res = get(g);
    vi ans;
    ans.pb(1);
    if (check(g))
        ans.pb(2);
    for (auto &cur : res) {
        map<ull, int> cnt;
        for (ull x : cur) {
            cnt[x]++;
        }
        int gd = 0;
        for (auto [x, y] : cnt) {
            gd = gcd(gd, y);
        }
        // cout << gd << endl;
        vi ds = get1(gd);
        for (int x : ds) {
            ans.pb(x);
        }
    }
    sort(all(ans));
    ans.erase(unique(all(ans)), ans.end());
    cout << sz(ans) << endl;
    for (int x : ans) {
        cout << x << " ";
    }
    cout << endl;
}

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

    init();

    int t = 1;
    cin >> t;

    while (t--) solve();

    return 0;
}

1006. 今晚吃流年

2-SAT
强连通分量
构造

cpp

#include <bits/stdc++.h>

using namespace std;

const int N = 1200010;

vector<int> adj[N];
int dfn[N], low[N], st[N], inst[N], scc_id[N];
int scc_cnt, tp, t;

void add(int x, int y) {
    adj[x].emplace_back(y);
}

void tarjan(int x) {
    dfn[x] = low[x] = ++t;
    st[++tp] = x;
    inst[x] = 1;

    for (int y : adj[x]) {
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        } else if (inst[y]) {
            low[x] = min(low[x], dfn[y]);
        }
    }

    if (dfn[x] == low[x]) {
        ++scc_cnt;
        while (1) {
            int y = st[tp--];
            inst[y] = 0;
            scc_id[y] = scc_cnt;
            if (y == x)
                break;
        }
    }
}

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

    int T;
    cin >> T;

    while (T--) {
        int n, m;
        cin >> n >> m;

        for (int i = 1; i <= 6 * n; ++i) {
            adj[i].clear();
            dfn[i] = low[i] = inst[i] = scc_id[i] = 0;
        }

        scc_cnt = tp = t = 0;

        auto a1le = [&](bool f, int x) {
            if (!f)
                return 2 * n + x;
            return 3 * n + x;
        };

        auto a2le = [&](bool f, int x) {
            if (!f)
                return 4 * n + x;
            return 5 * n + x;
        };

        auto ch = [&](bool f, int x) {
            if (!f)
                return x;
            return n + x;
        };

        auto ng = [&](int x) {
            int k = (x - 1) / n;
            if (k & 1)
                return x - n;
            return x + n;
        };
        auto imp = [&](int x, int y) {
            add(x, y);
            add(ng(y), ng(x));
        };
        imp(a1le(0, 1), a1le(1, 1));
        imp(a2le(1, n), a2le(0, n));
        for (int i = 1; i < n; ++i) {
            imp(a1le(0, i), a1le(0, i + 1));
            imp(a2le(0, i), a2le(0, i + 1));
            imp(a2le(0, i + 1), a1le(0, i));
        }

        for (int i = 1; i <= m; ++i) {
            int c, p;
            cin >> c >> p;

            if (c > p)
                swap(c, p);
            imp(ch(0, c), ch(1, p));
            imp(ch(1, c), ch(0, p));
            imp(ch(0, c), a1le(1, c));
            imp(ch(1, c), a1le(0, c));
            imp(ch(1, c), a2le(1, c));
            imp(ch(1, p), a1le(0, p));
            imp(ch(1, p), a2le(1, p));
            imp(ch(0, p), a2le(0, p));
        }

        for (int i = 1; i <= 6 * n; ++i) {
            if (!dfn[i])
                tarjan(i);
        }

        bool ok = true;

        for (int i = 1; i <= n; ++i) {
            if (scc_id[ch(0, i)] == scc_id[ch(1, i)] ||
                scc_id[a1le(0, i)] == scc_id[a1le(1, i)] ||
                scc_id[a2le(0, i)] == scc_id[a2le(1, i)]) {
                ok = false;
                break;
            }
        }

        if (!ok) {
            cout << "No\n";
            continue;
        }

        cout << "Yes\n";

        int a1 = -1, a2 = -1;

        for (int i = 1; i <= n; ++i) {
            if (scc_id[a1le(0, i)] < scc_id[a1le(1, i)]) {
                a1 = i;
                break;
            }
        }

        for (int i = 1; i <= n; ++i) {
            if (scc_id[a2le(0, i)] < scc_id[a2le(1, i)]) {
                a2 = i;
                break;
            }
        }

        cout << a1 << ' ' << a2 << '\n';
    }

    return 0;
}

1008. 今晚吃 NPC

构造
字符串

cpp

#include <bits/stdc++.h>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, w;
        string s;
        cin >> n >> w >> s;
        vector<int> a(n);
        if (s[0] == '&') {
            a[0] = w;
            for (int i = 0; i < n - 1; ++i) {
                if (s[i] == '&') {
                    a[i + 1] = w;
                }
                else break;
            }
        }
        else {
            a[0] = w;
        }
        cout << "Yes\n";
        for (int i : a) cout << i << ' ';
        cout << '\n';
    }
    return 0;
}

1009. 今晚吃草莓

队列优化 DP
单调队列优化
动态规划

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 = 5e2 + 5;
void init() {}

void solve() {
    int n,m,s;
    cin >> n >> m >> s;
    s--;
    vvi dp(m+1,vi(n,INF));
    dp[0][s] = 0;
    for(int i = 0; i < m; i++){
        vvi ndp(m+1,vi(n,INF));
        int k,c;
        cin >> k >> c;
        for(int j=0; j < i+1; j++){
            deque<int> q;
            for(int l=0;l<n&&l<k;l++){
                while(sz(q) && dp[j][q.back()] > dp[j][l]) q.pop_back();
                q.push_back(l);
            }
            ndp[j+1][0]=dp[j][q.front()]+c;
            for(int l=0;l<n;l++){
                while(sz(q) && q.front()<l-k+1) q.pop_front();
                if(l+k-1<n){
                    while(sz(q) && dp[j][q.back()] > dp[j][l+k-1]) q.pop_back();
                    q.push_back(l+k-1);
                }
                ndp[j][l]=min(ndp[j][l],dp[j][q.front()]);
                if(l-k>=0)ndp[j][l]=min(ndp[j][l],dp[j][l-k]+c);
                if(l+k<n)ndp[j][l]=min(ndp[j][l],dp[j][l+k]+c);
            }
            while(sz(q) && q.front()<n-k) q.pop_front();
            ndp[j+1][n-1]=min(ndp[j+1][n-1],dp[j][q.front()]+c);
        }
        dp.swap(ndp);
    }
    for(int i=0;i<n;i++){
        int x;
        cin >> x;
        int ans=-1;
        for(int j=0;j<=m;j++)if(dp[j][i]<=x)ans=j;
        cout << ans << " ";
    }
    cout << endl;
}

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

    init();

    int t = 1;
    cin >> t;

    while (t--) solve();

    return 0;
}

1010. 今晚吃黑子

动态规划
组合数学
前缀和

cpp

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

const int mod = 998244353;

void solve(){
    string s;
    cin>>s;
    int n = s.size();
    bool ok = 1;
    for(int i = 1;i < n;i++){
        if(s[i] == s[i - 1]){
            ok = 0;
            break;
        }
    }

    if(ok){
        cout<<1<<endl;
        return;
    }

    vector<int>dp(2 * n + 10);

    int base = n + 3;
    int sum = 0;

    dp[base] = 1;

    int ans = 0;

    for(int i = 0;i < n;i++){
        if(s[i] == '1')sum++;
        else sum--;
        int now = 0;
        now += dp[base + sum - 1];
        now += dp[base + sum + 1];

        if(sum == 0)now++;

        now %= mod;

        dp[base + sum] = now;

        ans = now;
    }

    if(sum == 0){
        ans--;
        if(ans < 0)ans += mod;
    }

    cout<<ans<<endl;
}

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

    int T;
    cin>>T;

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

    return 0;
}

1011. 今晚吃电脑配件

并查集
线性代数

cpp

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 1000010;

int fa[N], flg[N], op[N];
LL s[N], v[N];


// v[x] = op[x] * v[fa[x]] + s[x]
// v[fa[x]] = op[fa[x]] * v[fa[fa[x]]] + s[fa[x]]
// v[x] = op[x] * (op[fa[x]] * v[fa[fa[x]]] + s[fa[x]]) + s[x]
//
// v[x] = op[x] * op[fa[x]] * v[fa[fa[x]]] + op * s[fa[x]] + s[x];

int getfa(int x) {
    if (x == fa[x]) return x;
    else {
        int px = getfa(fa[x]);
        s[x] = op[x] * s[fa[x]] + s[x];
        op[x] = op[x] * op[fa[x]];
        return fa[x] = px;
    }
}

LL calc(int x) {
    int p = getfa(x);
    return v[p] * op[x] + s[x];
}

/*
v[x] = op[x] * v[px] + s[x]
v[y] = op[y] * v[py] + s[y]

(v[x] - s[x]) * op[x] = (v[y] - s[y]) * op[y]

op * op = -1 : v[x] + v[y] = s[x] + s[y]
op * op =  1 : v[x] - v[y] = s[x] - s[y]
*/

bool merge(int x, int y, LL c) {
    int px = getfa(x), py = getfa(y);
    if (flg[px] && flg[py]) {
        if (calc(x) + calc(y) == c) return true;
        else return false;
    }
    else if (px == py) {
        if (op[x] * op[y] == -1) {
            // v[x] + v[y] = s[x] + s[y]
            return c == s[x] + s[y];
        }
        else {
            // v[x] - v[y] = s[x] - s[y]
            // v[x] + v[y] = c
            LL vx = (s[x] - s[y] + c) / 2;
            v[px] = (vx - s[x]) * op[x];
            flg[px] = 1;
            return true;
        }
    }
    else {
        if (flg[py]) swap(x, y), swap(px, py);
        /*
        flg[y] == false y -> x
        op[x] * v[px] + s[x] + op[y] * v[py] + s[y] = c
        v[py] = op[y] * -op[x] * (v[px]) + op[y] * (c - s[x] - s[y])
        */
        fa[py] = px;
        s[py] = op[y] * (c - s[x] - s[y]);
        op[py] = op[y] * -op[x];
        return true;
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        int k = 0;
        for (int i = 1; i <= n; ++i) {
            fa[i] = i;
            op[i] = 1;
            s[i] = flg[i] = v[i] = 0;
        }
        while (m--) {
            LL a, b, c;
            cin >> a >> b >> c;
            a = (a + k - 1) % n + 1;
            b = (b + k - 1) % n + 1;
            c = (c + k) % 1000000000 + 1;

            if (merge(a, b, c * 2)) {
                cout << "Yes\n";
                k++;
            }
            else cout << "No\n";
        }
    }
    return 0;
}

1012. 今晚吃 TopTree

贪心
优先队列
二分查找
树

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() {}
int get(vi a) {
    pqi q;
    int res = 0;
    for (int i = 0; i < sz(a); i++) {
        q.push(a[i]);
    }
    while (sz(q) > 2) {
        int u = q.top();
        q.pop();
        int v = q.top();
        q.pop();
        res += u + v;
        q.push(u + v);
    }
    return res;
}
int get1(vi b) {
    if(sz(b)<1)return 0;
    int l=0,r=1e6+5,res=0;
    while(l<=r){
        bool flag=true;
        int mid=(l+r)/2;
        vi cnt(22);
        for(int i=0;i<sz(b);i++){
            int x=b[i];
            if(b[i]>mid){
                flag=false;
            }else{
                if(mid-x>20)continue;
                else cnt[mid-x]++;
            }
        }
        int cur=2;
        for(int i=0;i<=20;i++){
            if(cnt[i]>cur){
                flag=false;
            }
            cur=(cur-cnt[i])*2;
        }
        if(flag){
            res=mid;
            r=mid-1;
        }else{
            l=mid+1;
        }
    }
    return res;
}
void solve() {
    int n;
    cin >> n;
    vvi g(n + 1);
    for (int i = 1; i < n; i++) {
        int p;
        cin >> p;
        g[p].pb(i+1);
    }
    vi dp1(n + 1), siz(n + 1);
    int ans = 0;
    auto dfs = [&](auto self, int u, int p) -> void {
        siz[u] = 1;
        vi a,b;
        for (int v : g[u]) {
            if (v == p)
                continue;
            self(self, v, u);
            siz[u] += siz[v];
            b.pb(dp1[v]);
            a.pb(siz[v]);
        }
        if(u!=1){
            ans += get(a)+siz[u];
            dp1[u] = get1(b)+1;
        }else{
            ans += get(a);
            dp1[u] = get1(b);
        }
    };
    dfs(dfs, 1, -1);
    cout<<dp1[1]<<" "<<ans<<endl;
}

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

    init();

    int t = 1;
    cin >> t;

    while (t--) solve();

    return 0;
}

1001. 今晚吃什么 ​

1002. 今晚吃…… ​

1003. 今晚吃春天 ​

1004. 今晚吃转转 ​

1006. 今晚吃流年 ​

1008. 今晚吃 NPC ​

1009. 今晚吃草莓 ​

1010. 今晚吃黑子 ​

1011. 今晚吃电脑配件 ​

1012. 今晚吃 TopTree ​

1001. 今晚吃什么

1002. 今晚吃……

1003. 今晚吃春天

1004. 今晚吃转转

1006. 今晚吃流年

1008. 今晚吃 NPC

1009. 今晚吃草莓

1010. 今晚吃黑子

1011. 今晚吃电脑配件

1012. 今晚吃 TopTree