2026-08-09~08-14 hetao1733837 的刷题记录

hetao1733837

114人浏览 · 2026-08-14 21:58:05

hetao1733837 · 2026-08-14 21:58:05 发布

2026-08-09~08-14 hetao1733837 的刷题记录

LGP3808 AC 自动机（简单版）

原题链接：AC 自动机（简单版）

分析

正式开学之后再学吧。

LGP14212 [ROI 2016 Day2] 二进制输入

原题链接：[ROI 2016 Day2] 二进制输入

分析

一个 $01$ 串，扔到字典树上是一个二叉树……然后呢？
前后缀我们都可以按照正着、反着往上放，所以，我们会有一个东西就是说，我们匹配到了哪，我们都会知道到达这里的最小值（不过，这个的局限性在于，我们没有办法多次使用一个串），那咋办？~~嵌套一个 DP？~~
好吧，我们换一。

LGP13271 [NOI2025] 机器人

原题链接：[NOI2025] 机器人

分析

有点……怎么说呢？
就是，我们发现，可以把这个东西的状态看成 $(u, p)$ ，即我们位于点 $u$ ，参数为 $p$ 。状态的数量仅与边的数量有关（ $p$ 可以取的值有很多，但是，边数是一定的）。那么，我们直接把 $(u, p)$ 和 $(v, p^{'})$ ，难道这个 $p^{'}$ 不应该 $\in[1,deg_v]$ 之间吗？呃，感觉 aoao 写错了……那，我们的建图似乎还是 $O (m)$ 的？好吧，这个……怎么说呢？又是分层图，又是拆状态的，很抽象吧……

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 300005;
int c, n, m, k, v[N], w[N], deg[N];
int ans[N];
unordered_map<int, long long> dis[N];
unordered_map<int, bool> vis[N];
vector<pair<int, int>> e[N];
int up(int x, int y){
    return v[y - 1] - v[x - 1];
}
int down(int x, int y){
    return w[x] - w[y];
}
priority_queue<pair<int, pair<int, int>>, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> q;
void dijkstra(){
    memset(ans, 0x3f, sizeof(ans));
    dis[1][1] = 0;
    vis[1][1] = true;
    ans[1] = 0;
    q.push({0, {1, 1}});
    while (!q.empty()){
        auto tmp = q.top();
        q.pop();
        int dist = tmp.first;
        int u = tmp.second.first;
        int p = tmp.second.second;
        if (dis[u].find(p) == dis[u].end() || dis[u][p] != dist){
            continue;
        } 
        if (p != 1 && deg[u]){
            int val;
            if (p > deg[u])
                val = deg[u];
            else    
                val = p - 1;
            if (!vis[u][val] || dist + down(p, val) < dis[u][val]){
                dis[u][val] = dist + down(p, val);
                q.push({dis[u][val], {u, val}});
                vis[u][val] = true;
            }
        }
        if (p < min(k, deg[u])){
            if (!vis[u][p + 1] || dist + up(p, p + 1) < dis[u][p + 1]){
                dis[u][p + 1] = dist + up(p, p + 1);
                q.push({dis[u][p + 1], {u, p + 1}});
                vis[u][p + 1] = true;
            }
        }
        if (deg[u] < p)
            continue;
        auto tmp2 = e[u][p - 1];
        if (!vis[tmp2.first][p] || dist + tmp2.second < dis[tmp2.first][p]){
            dis[tmp2.first][p] = dist + tmp2.second;
            q.push({dis[tmp2.first][p], {tmp2.first, p}});
            ans[tmp2.first] = min(ans[tmp2.first], dis[tmp2.first][p]);
            vis[tmp2.first][p] = true;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> c;
    cin >> n >> m >> k;
    for (int i = 1; i < k; i++){
        cin >> v[i];
        v[i] += v[i - 1];
    }
    for (int i = 2; i <= k; i++){
        cin >> w[i];
        w[i] += w[i - 1];
    }
    for (int u = 1, to, val; u <= n; u++){
        cin >> deg[u];
        for (int i = 1; i <= deg[u]; i++){
            cin >> to >> val;
            e[u].push_back({to, val});
        }
    }
    dijkstra();
    for (int i = 1; i <= n; i++){
        if (ans[i] == 0x3f3f3f3f3f3f3f3f)
            cout << -1 << " ";
        else
            cout << ans[i] << " ";
    }
}

LGP6775 [NOI2020] 制作菜品

原题链接：[NOI2020] 制作菜品

分析

不是，怎么背包？但是，呃……似乎……可以吗？好像不行/ll
我们按照 $d$ 升序排序，发现，对于 $m\ge n-1$ 始终有解。
我们很容易发现，在 $m = n - 1$ 的时候，总有 $d_1<k$ ， $d_1+d_n\ge k$ ，构造形如先用 $d_1$ ，剩下的用 $d_n$ 补全。
在 $m\ge n$ 的时候， $d_n\ge k$ ，让 $d_n$ 单独出一个，剩下的按照 $m = n - 1$ 做就行了。
对于 $m = n - 2$ ，这个情况成立，当且仅当可以找到一个原料的真子集，设其大小为 $sz$ ，其和 $sum=(sz-1)\times k$ ，剩下的按照 $m = n - 1$ 做。这个拿一个 bitset 优化背包就行（~~我怎么觉得直接做就行？~~）

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 505, M = 5000005;
int T, n, m, k, d[N];
int id1[N], len1;
int id2[N], len2;
bitset<M> dp[N];
bool cmp(int a, int b){
    return d[a] < d[b];
}
void find(int u, int tot){
    if (!u)
        return ;
    int delta = d[u] - k;
    if (tot - delta >= 0 && dp[u - 1][tot - delta]){
        id1[++len1] = u;
        find(u - 1, tot - delta);
    }
    else{
        id2[++len2] = u;
        find(u - 1, tot);
    }
}
void solve(int *id, int len){
    sort(id + 1, id + len + 1, cmp);
    while (len > 1){
        cout << id[1] << " " << d[id[1]] << " " << id[len] << " " << k - d[id[1]] << '\n';
        d[id[len]] -= k - d[id[1]];
        for (int i = 1; i < len; i++)
            id[i] = id[i + 1];
        len--;
        sort(id + 1, id + len + 1, cmp);
    }
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> T;
    for (int cs = 1; cs <= T; cs++){
        cin >> n >> m >> k;
        for (int i = 1; i <= n; i++){
            cin >> d[i];
        }
        if (m == n - 2){
            int tmp = m * k;
            dp[0].reset();
            dp[0][tmp] = 1;
            for (int i = 1; i <= n; i++){
                int delta = d[i] - k;
                if (delta >= 0)
                    dp[i] = dp[i - 1] | (dp[i - 1] << delta);
                else
                    dp[i] = dp[i - 1] | (dp[i - 1] >> (-delta));
            }
            if (!dp[n][tmp - k]){
                cout << -1 << '\n';
                continue;
            }
            len1 = len2 = 0;
            find(n, tmp - k);
            solve(id1, len1);
            solve(id2, len2);
        }
        else{
            for (int i = 1; i <= n; i++)
                id1[i] = i;
            sort(id1 + 1, id1 + n + 1, cmp);
            while (m >= n && m){
                int mx = id1[n];
                cout << mx << " " << k << '\n';
                d[mx] -= k;
                if (!d[mx])
                    n--;
                sort(id1 + 1, id1 + n + 1, cmp);
                m--;
            }
            solve(id1, n);
        }
    }
}

LGP3702 [SDOI2017] 序列计数

原题链接：[SDOI2017] 序列计数

分析

猜对了
然后，那个和之类的直接 DP 就可以了。
对，如果和要求正好是某个值，我们可以直接插板。
我们设 $P_{i,j}$ 表示 $i$ 个数 $mod {p}$ 为 $j$ 的方案数， $cnt_{i}$ 表示 $[1, m]$ 中 $\mod p$ 等于 $i$ 的个数。
那么，转移形如：
$P_{i,j}=\sum\limits_{k}^{}{P_{i-1,k}}$

正解

#include <bits/stdc++.h>
#define int long long
#define mod 20170408
using namespace std;
const int N = 205, M = 20000005;
struct mat{
    int m, n, ma[N][N];
    mat(){}
    mat(int _m, int _n) : m(_m), n(_n){
        memset(ma, 0, sizeof(ma));
    }
	friend mat operator * (mat a, mat b){
		mat res = mat(a.m, b.n);
		for (int i = 1; i <= res.m; i++){
			for (int j = 1; j <= res.n; j++){
				for (int k = 1; k <= a.n; k++){
					res.ma[i][j] = (res.ma[i][j] 
						+ a.ma[i][k] * b.ma[k][j] % mod) % mod;	
				}
			}
		}
		return res;
	} 
	friend mat operator ^ (mat a, int b){
		mat c = a, res = mat(a.m, a.n);
		for (int i = 1; i <= res.m; i++)
			res.ma[i][i] = 1;
		while (b){
			if (b & 1)
				res = res * c;
			c = c * c;
			b >>= 1;
		}
		return res;
	}
}P, Q, V, W;
int n, m, p, cnt[N], cntt[N];
bool prime[M];
int pr[M], tot;
void init(){
	memset(prime, true, sizeof(prime));
	prime[1] = false;
	for (int i = 2; i <= m; i++){
		if (prime[i] == true){
			pr[++tot] = i;
		}
		for (int j = 1; i * pr[j] <= m && j <= tot; j++){
			prime[i * pr[j]] = false;
			if (i * pr[j] == 0)
				break;
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> p;
	for (int i = 0; i < p; i++){
		cnt[i] = m / p;
	}
	for (int i = 1; i <= m % p; i++){
		cnt[i]++;
	}
	P = mat(p, p);
	P.ma[1][1] = cnt[0];
	for (int i = 2; i <= p; i++)
		P.ma[1][i] = cnt[p - i + 1];
	for (int i = 2; i <= p; i++){
		for (int j = 2; j <= p; j++){
			P.ma[i][j] = P.ma[i - 1][j - 1];
		}
		P.ma[i][1] = P.ma[i - 1][p];
	}
	init();
	for (int i = 1; i <= m; i++){
		if (!prime[i])
			cntt[i % p]++;
	}
	Q = mat(p, p);
	Q.ma[1][1] = cntt[0];
	for (int i = 2; i <= p; i++){
		Q.ma[1][i] = cntt[p - i + 1];
	}
	for (int i = 2; i <= p; i++){
		for (int j = 2; j <= p; j++){
			Q.ma[i][j] = Q.ma[i - 1][j - 1];
		}
		Q.ma[i][1] = Q.ma[i - 1][p];
	}
	for (int i = 1; i <= p; i++){
		for (int j = 1; j <= p; j++){
			P.ma[i][j] %= mod;
			Q.ma[i][j] %= mod;
		}
	}
	V = mat(p, 1);
	W = mat(p, 1);
	for (int i = 1; i <= p; i++){
		V.ma[i][1] = cnt[i - 1] % mod;
		W.ma[i][1] = cntt[i - 1] % mod;
	}
	P = (P ^ (n - 1)) * V;
	Q = (Q ^ (n - 1)) * W;
	cout << (P.ma[1][1] - Q.ma[1][1] + mod) % mod;
}

ZYZOJ A.礼物 gift

原题链接：A.礼物 gift

分析

好像是一个图论建模……就是，我们把那个 $B_i$ 当成 $d e g$ 之类的东西……
天啊，就是说，这个部分分给的很奇特，第一档是一个状压 DP，第二档是一个 $O(n^2)$ ，第三档就是正解了。但是，如果说我们放在图上做了，那么，会出现什么呢？

~~虽然，这个上 JOI 完全可以盒出来吧……~~
我要不要先想一下 $O(n^2)$ 怎么写……那应该是一个更显然的 DP，然后，暴力进行临近的转移……
我们又发现，一个点变更，只会影响其临近的点……难道直接搜吗？复杂度对吗？好像不是很对……
那么，我似乎可以直接算类似于……
就是，我们处理入度，然后，计算一个点所抵达的点……假了……
那么，既然 DP 似乎不是很行，那，我还是贪心一下吧……
但是，贪心似乎也不是很行啊……
反悔，那困难完了。

我们设 $dp_{i,0/1}$ 表示考虑了前 $i$ 个点，第 $i$ 个点为送出饼干🍪/蛋糕🎂的最大喜悦值，然后在图上转移，就可以获得一定的分数了……
好的，我成功在 T1 获得了 31pts😭
白瞎了我的图论建模了😭

天啊，我竟然不使用原题机就盒出了这道题。更可悲的是，我从 2014 年开始刷 JOISC 的，这个是 2013 年的/ll
天啊，这个树是一个基环树。
不是，n 个点 n 条边，不是基环树是什么？那，之前那个 DP 式子完全是树上 DP 来的，直接做吧……
失误了，失误了。
搬的 LGP14442 [JOISC 2013] 礼物 / Presents……

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005; 
int n;
struct edge{
    int to, nxt, val;
}e[N];
int head[N], tot;
int indeg[N]; 
int fa[N], pts[N], edg[N];
bool rd[N];
void add(int u, int v, int w){
    indeg[v]++;
    e[++tot].to = v;
    e[tot].nxt = head[u];
    e[tot].val = w;
    head[u] = tot;
}
int find(int x){
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y){
    int fx = find(x), fy = find(y);
    edg[fx]++;
    if (fx == fy){
        rd[tot] = true;
        return;
    }
    fa[fx] = fy;
    pts[fy] += pts[fx];
    edg[fy] += edg[fx];
}
int sum[N][2], dp[N][2];
bool vis[N];
void dfs(int u){
    for (int i = head[u]; i; i = e[i].nxt){
        int v = e[i].to;
        if (vis[i]) 
            continue;
        dfs(v);
        dp[u][0] += max(dp[v][0] + e[i].val * sum[u][0],
                        dp[v][1] + e[i].val * sum[u][1]);
        dp[u][1] += max(dp[v][0] + e[i].val * sum[u][1],
                        dp[v][1] + e[i].val * sum[u][0]);
    }
}
vector<int> block[N];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        head[i] = -1;
        fa[i] = i;
        pts[i] = 1;
    }
    for (int i = 1; i <= n; i++){
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        sum[i][0] = c;
        sum[i][1] = d;
        add(a, i, b);
        merge(a, i);
    }
    for (int i = 1; i <= n; i++){
        block[find(i)].push_back(i);
    }
    int ans = 0;
    for (int i = 1; i <= n; i++){
        if (find(i) != i) 
            continue;
        if (pts[i] - 1 == edg[i]){
            for (int root : block[i]) {
                if (!indeg[root]){
                    dfs(root);
                    ans += max(dp[root][0], dp[root][1]);
                    break;
                }
            }
        } 
        else{
            int tu, tv, tw;
            bool found = false;
            for (int u : block[i]){
                for (int j = head[u]; j != -1; j = e[j].nxt){
                    if (rd[j]){
                        tu = u;
                        tv = e[j].to;
                        tw = e[j].val;
                        vis[j] = true;
                        found = true;
                        break;
                    }
                }
                if (found) 
                    break;
            }
            dp[tu][1] = 0xc0c0c0c0c0c0c0c0;
            dfs(tv);
            int tmp = max(dp[tv][1] + tw * sum[tu][1],
                          dp[tv][0] + tw * sum[tu][0]);
            for (int u : block[i]) dp[u][0] = dp[u][1] = 0;
            dp[tu][0] = 0xc0c0c0c0c0c0c0c0;
            dfs(tv);
            ans += max({tmp,
                        dp[tv][0] + sum[tu][1],
                        dp[tv][1] + sum[tu][0]});
        }
    }
    cout << ans;
}

ZYZOJ B.循环移位 string

原题链接：B.循环移位 string

分析

期望是认真的吗/xia
其实吧……嗯……也……比较困难……
感觉这个更类似与省选场。

天啊，为什么这么难/ll
我真的能推出来式子吗/ll
天啊，我竟然不知道每个字符串的长度需要用在哪/ll
哦，天啊，我来思考一下。
那么，我应该设的期望 DP 就是设 $dp_{i,j}$ 表示正确了 $i$ 个，一共有 $j$ 种 $F (S)$ 的取值时的期望。天啊，这个真的有前途吗？而且，这个怎么转移？更可怕的是，这个东西他要是按照前多少个的话，似乎更没法转移。

等一下，他的输出顺序是一定的/jk
也就是说，我设 $dp_{i}$ 表示对了 $i$ 个，那么，有多少种情况呢？
要不还是再加一维吧，我没有演草纸/ll
好吧，我又回到了，假设……不行，因为这个并不统一啊/ll
算了，还是这样弄吧。我们假设 $cnt_i$ 表示长度大于等于 $i$ 的字符串的个数。
那么，我们设 $dp_{i}$ 表示有 $i$ 个正确的期望。
问题转化为，有 $m$ 个数，将最后一位放到开头，与原序列比对，发现有 $i$ 个位置是对的。我们发现，连续 $x$ 个相同会出现 $x - 1$ 个相同的。然后呢？

嗯……我好像除了概率不会算，其他在场上基本想出来完了。而且，和我预估的差不多，算概率的时候需要容斥。
不过，找理由是错误的，我们需要正确面对。然后，这个题其实在 QOJ 上有原。

题目中给出了 pwepwepwe 这个状物，我们发现他是一个规律性的东西，然后，我们有发现，对于一个长度为 $∣ S ∣$ 的串串，如果他的周期的长度为 $∣ T ∣$ ，那么，他有 $\frac{|S|}{|T|}$ 此机会取到我们想要的位置。
那么，长度为 $i$ ，且最小周期长度为 $i$ 的字符串的个数（不妨设为 $f (i)$ ）为：
$f(i)={26}^{i}-\sum\limits_{j|i}^{j\neq i}{f(j)}$
那么，长度为 $k$ ，其 $F (S) = i$ 的字符串 $S$ 的期望 $p (k, i)$ 可以为：
$p(k,i)=\frac{\sum\limits_{j|k}^{j\ge i}{\frac{f(j)}{j}}}{{26}^{k}}$
然后，我们使用一下朴素的乘法原理还有高中概率的部分知识，可知答案为：
$\sum{p(k_1,i)\times p(k_2,i)}$
想要理解前面为什么要除，可以这么理解：因为我们的字符串保证了随机，所以，显然会有重复，我们有多少个位置，就应该把这些除掉。
但是，这个还是 $O(n^2)$ 的（~~剩下的 20pts 真的还有要的必要吗？~~）。
我来问一问怎么优化吧。

好吧，就是说，我们发现，答案是一坨，一坨，一坨的（就是配对），然后，我们把这些看成一个一个一一对应的，那么，我们拿一个双指针就可以了……
搬的 QOJ1855……

正解

#include <bits/stdc++.h>
#define int long long
#define mod 998244353
using namespace std;
const int N = 200005;
int m, n[N];
int pw[N], f[N];
int mx;
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;
}
vector<pair<int, int>> p[N];
int solve(int x, int y){
    auto idx = p[x].begin(), idy = p[y].begin();
    int res = 0, cur = 0;
    while (idx != p[x].end() && idy != p[y].end()){
        int tp = min(idx->first, idy->first);
        res = (res + idx->second * idy->second % mod * (tp - cur)) % mod;
        if (idx->first == tp) 
            idx++;
        if (idy->first == tp) 
            idy++;
        cur = tp;
    }
    return res % mod;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> m;
    for (int i = 1; i <= m; i++){
        cin >> n[i];
        mx = max(mx, n[i]);
    }
    if (m == 1){
        cout << 1 << '\n';
        return 0;
    }
    pw[0] = 1;
    for (int i = 1; i <= mx; i++){
        pw[i] = pw[i - 1] * 26 % mod;
        f[i] = pw[i] + f[i] % mod + mod;
        for (int j = 2 * i; j <= mx; j += i)
            f[j] -= f[i];
        for (int j = i; j <= mx; j += i)
            p[j].push_back({i, 0});
        f[i] = f[i] * qpow(i, mod - 2) % mod;
    }
    for (int i = 1; i <= mx; i++){
        int inv = qpow(pw[i], mod - 2);
        for (auto &j : p[i])
            j.second = f[j.first] * inv % mod;
        for (int j = (int)p[i].size() - 2; j >= 0; j--)
            p[i][j].second = (p[i][j].second + p[i][j + 1].second) % mod;
    }
    int ans = 0;
    for (int i = 1; i <= m; i++)
        ans = (ans + solve(n[i], n[i % m + 1])) % mod;
    cout << ans % mod;
    return 0;
}

ZYZOJ C.聚会 party

原题链接：C.聚会 party

分析

天啊，我竟然我竟无言以对/ll
搬的 LGP7565 [JOISC 2021] ビーバーの会合 2 (Day3)……
有空再补吧。
这题主要是一个树论里重要的结论：树上一条链（直径之类的），给树新加进去一个点（非插入），该链的端点要么不变，要么变成这个新的点。

ZYZOJ D.星座 star

原题链接：D.星座 star

分析

呃……也就是说，我们要么让所有的星星都变黑，要么，让所有含有保留有星星的矩阵都含有小白船……
天啊，这场困难完了/ll

就是，我们发现，星座的构型，似乎都类似于下面一个星星⭐，上面一个⭐（~~这好像是废话~~），不过，当高度逐渐上升，小白船的密度似乎会变小，所以，此时星座的连通性变好了。
那么，我们使用一个并查集记录星星的连通性。拿一个树状数组从下往上扫，每次遇到一个⭐，我们删去它，然后，我们在权值上做一点操作，当遇到更优的时候，做一下反悔。对，没了，但是，aoao 写的是啥啊/ll
哦，他把船……就是他维护了没有船的连通块的左右边界。对，那就可以了。
然后，反悔里面还有一些需要注意的，不要弄重复了。
搬的 LGP7219 [JOISC 2020] 星座 3……

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200005;
int n;
vector<int> a[N];
int m;
vector<pair<int, int>> star[N];
struct dsu{
	int fa[N];
	void init(){
		for (int i = 0; i <= n + 1; i++){
			fa[i] = i;
		}
	}
	int find(int x){
		return (x == fa[x]) ? fa[x] : fa[x] = find(fa[x]);
	}
	void merge(int x, int y){
		int fx = find(x), fy = find(y);
		if (fx == fy)
			return ;
		fa[fx] = fy;
	}
}l, r;
int c[N];
void add(int x, int val){
	for (int i = x; i <= n + 1; i += i & (-i))
		c[i] += val;
}
int query(int x){
	int res = 0;
	for (int i = x; i; i -= i & (-i))
		res += c[i];
	return res;
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1, A; i <= n; i++){
		cin >> A;
		a[A].push_back(i);
	}
	cin >> m;
	for (int i = 1, X, Y, C; i <= m; i++){
		cin >> X >> Y >> C;
		star[Y].push_back({X, C});
	}
	l.init();
	r.init();
	int ans = 0;
	for (int i = 1; i <= n; i++){
		for (auto tmp : star[i]){
			int pos = tmp.first, val = tmp.second;
			int cur = query(pos);
			if (val <= cur){
				ans += val;
			}
			else{
				ans += cur;
				add(l.find(pos) + 1, val - cur);
				add(r.find(pos), cur - val);
			}
		}
		for (auto tmp : a[i]){
			l.merge(tmp, tmp - 1);
			r.merge(tmp, tmp + 1);
		}
	}
	cout << ans;
}