2025-12-04 hetao1733837的刷题记录

LG1495 【模板】中国剩余定理（CRT）/ 曹冲养猪

原题链接：【模板】中国剩余定理（CRT）/ 曹冲养猪

分析

很版，但是，我好像并不会 exgcd 求逆，我是**/(ㄒoㄒ)/~~

正解

#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int N = 15;
int n, a[N], b[N];
int exgcd(int a, int b, int &x, int &y){
	if (b == 0){
		x = 1;
		y = 0;
		return a;
	}
	int k = exgcd(b, a % b, x, y);
	int tmp = x;
	x = y;
	y = tmp - a / b * y;
	return k;
}
int crt(int r[], int m[]){
	int M = 1, ans = 0;
	for (int i = 1; i <= n; i++)
		M *= m[i];
	for (int i = 1; i <= n; i++){
		int c = M / m[i];
		int x, y;
		exgcd(c, m[i], x, y);
		ans = (ans + (r[i] * c * x) % M) % M;
	}
	return (ans % M + M) % M;
}
int read(){
	char c = getchar();
	int x = 0, f = 1;
	while (c < '0' || c > '9'){
		if (c == '-')
			f = -1;
		c = getchar();
	} 
	while (c >= '0' && c <= '9'){
		x = x * 10 + (c - '0');
		c = getchar();
	}
	return x * f;
}
void write(int x){
	if (x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	n = read();
	for (int i = 1; i <= n; i++){
		a[i] = read();
		b[i] = read();
	} 
	write(crt(b, a));
}

LG4777 【模板】扩展中国剩余定理（EXCRT）

原题链接：【模板】扩展中国剩余定理（EXCRT）

分析

此题不保证模数互质了。所以扩展了，像在废话。所以使用迭代法一层一层最终得到答案。

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
int n, a[N], m[N];
int mul(int a, int b, int mod){
    int res = 0;
    while (b){
        if (b & 1)
            res = (res + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return res;
}
int exgcd(int a, int b, int &x, int &y){
    if (b == 0){
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int excrt(){
    int x, y;
    int M = m[1]; 
    int ans = a[1] % M;
    for (int i = 2; i <= n; i++){
        int c = (a[i] - ans % m[i] + m[i]) % m[i];
        int d = exgcd(M, m[i], x, y);
        if (c % d != 0)
            return -1;
        x = mul(x, c / d, m[i] / d);
        ans += x * M;
        M = M / d * m[i];
        ans = (ans % M + M) % M;
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> m[i] >> a[i];
    }
    cout << excrt();
    return 0;
}

嘻嘻，回机房了，lz 能让我停文科吗？
学了树剖，先做点板子，然后考虑更强的思维。
感觉是时候把所有东西往满了点了，毕竟以我 NOIP 的分数，省选压力挺大的。
然后，树上的就是树剖，LCT，点分治，边分治，点分树，出不多就点满了，不知道会不会写题，但是先按这个学吧。
然后字符串就是复习 Manacher，KMP，哈希，字典树，AC自动机，多学一下二分哈希，后缀自动机，后缀数组，也就差不多了。
数据结构，平衡树，可持久化数据结构，也差不多没了。
数学，高中数学加紧学完，强化一下数数，这个很有必要，期望、概率论也是重点。
动态规划的话，我觉得数位DP，概率DP都可以提上日程，这个待定吧……主要是DP优化省选常考。
图论的话，就是Tarjan，这个以前接触过，但是不完全会，也要复习。
行，2025年结束之前尽全力全部过一遍，多刷题，通过数冲750+吧，每周打一下CF，差不多。
行，树剖，开始！

LG3384 【模板】重链剖分/树链剖分

原题链接：【模板】重链剖分/树链剖分

分析

主要还是懒标记下放，这个是极弱点，必须加强！
其他的没啥，主要记录一个 r k rk rk 数组，和 d f n dfn dfn 一起使用。

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
int n, m, r, mod, a[N];
int dfn[N], son[N], fa[N], de[N], sz[N], top[N]; //top表示重链顶
vector<int> e[N];
int ncnt;
int op, x, y, z;
int rk[N];
struct segtree{
    int sum[N << 2], tag[N << 2];
    void pushup(int p){
        sum[p] = (sum[p << 1] + sum[p << 1 | 1]) % mod;
    }
    void down(int p, int l, int r){
        if (!tag[p]) 
            return ; 
        int mid = (l + r) >> 1;
        tag[p << 1] = (tag[p << 1] + tag[p]) % mod;
        sum[p << 1] = (sum[p << 1] + tag[p] * (mid - l + 1) % mod) % mod;
        tag[p << 1 | 1] = (tag[p << 1 | 1] + tag[p]) % mod;
        sum[p << 1 | 1] = (sum[p << 1 | 1] + tag[p] * (r - mid) % mod) % mod;
        tag[p] = 0;
    }
    void build(int p, int l, int r){
        if (l == r){
            sum[p] = a[rk[l]] % mod;
            return ;
        }
        int mid = (l + r) >> 1;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        pushup(p);
    }
    void modify(int p, int l, int r, int s, int t, int v){
        if (s <= l && r <= t){
            tag[p] = (tag[p] + v) % mod;
            sum[p] = (sum[p] + v * (r - l + 1) % mod) % mod;
            return ;
        }
        down(p, l, r);
        int mid = (l + r) >> 1;
        if (s <= mid)
            modify(p << 1, l, mid, s, t, v);
        if (t > mid)
            modify(p << 1 | 1, mid + 1, r, s, t, v);
        pushup(p);
    }   
    int query(int p, int l, int r, int s, int t){
        if (s <= l && r <= t){
            return sum[p];
        }
        down(p, l, r);
        int mid = (l + r) >> 1;
        int ans = 0;
        if (s <= mid)
            ans = (ans + query(p << 1, l, mid, s, t)) % mod;
        if (t > mid)
            ans = (ans + query(p << 1 | 1, mid + 1, r, s, t)) % mod;
        return ans;
    }
}T;
void dfs1(int u, int f){
    fa[u] = f;
    sz[u] = 1;
    de[u] = de[f] + 1;
    for (auto v : e[u]){
        if (v == f)
            continue;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]])
            son[u] = v; //更新重儿子 
    }
} 
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++ncnt;
    rk[dfn[u]] = u;
    if (son[u])
        dfs2(son[u], tp);
    for (auto v : e[u]){
        if (v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}
void subadd(int u, int v){ //子树加 
    T.modify(1, 1, n, dfn[u], dfn[u] + sz[u] - 1, v);
}
int subquery(int u){ //子树查 
    return T.query(1, 1, n, dfn[u], dfn[u] + sz[u] - 1) % mod;
}
void pathadd(int u, int v, int val){ //路径加 
    while (top[u] != top[v]){
        if (de[top[u]] < de[top[v]])
            swap(u, v);
        T.modify(1, 1, n, dfn[top[u]], dfn[u], val);
        u = fa[top[u]];
    } 
    if (de[u] > de[v])
        swap(u, v);
    T.modify(1, 1, n, dfn[u], dfn[v], val);
} 
int pathquery(int u, int v){ //路径查 
    int res = 0; 
    while (top[u] != top[v]){
        if (de[top[u]] < de[top[v]])
            swap(u, v);
        
        res = (res + T.query(1, 1, n, dfn[top[u]], dfn[u])) % mod; 
        u = fa[top[u]];
    } 
    if (de[u] > de[v])
        swap(u, v);
    res = (res + T.query(1, 1, n, dfn[u], dfn[v])) % mod;
    return res;
} 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> r >> mod;
    for (int i = 1; i <= n; i++){
        cin >> a[i];
    }
    for (int i = 1; i < n; i++){
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    dfs1(r, 0);
    dfs2(r, r);
    T.build(1, 1, n);
    for (int i = 1; i <= m; i++){
        cin >> op;
        if (op == 1){
            cin >> x >> y >> z;
            pathadd(x, y, z);
        }
        if (op == 2){
            cin >> x >> y;
            cout << pathquery(x, y) << '\n';
        }
        if (op == 3){
            cin >> x >> z;
            subadd(x, z);
        }
        if (op == 4){
            cin >> x;
            cout << subquery(x) << '\n';
        }
    }
    return 0;
}

LG3038 [USACO11DEC] Grass Planting G

原题链接：[USACO11DEC] Grass Planting G

分析

何意味？我稍考一下，虽然很板吧……
跳到最后，只剩下一条边，所以，dfs 序上要做个 +1，否则是 WA 的。

正解

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 100005;
int n, m, u, v;
char op;
int sz[N], fa[N], top[N], dfn[N], de[N], ncnt, son[N];
int rk[N];
vector<int> e[N];
void dfs1(int u, int f){
    sz[u] = 1;
    fa[u] = f;
    for (auto v : e[u]){
        if (v == f) continue;
        de[v] = de[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
        if (sz[v] > sz[son[u]])
            son[u] = v;
    }
}
void dfs2(int u, int tp){
    top[u] = tp;
    dfn[u] = ++ncnt;
    rk[ncnt] = u;
    if (son[u])
        dfs2(son[u], tp);
    for (auto v : e[u]){
        if (v == fa[u] || v == son[u])
            continue;
        dfs2(v, v);
    }
}
struct segtree{
    int sum[N * 4], tag[N * 4];
    void pushup(int p){
        sum[p] = sum[p << 1] + sum[p << 1 | 1]; 
    }
    void build(int p, int l, int r){
        if (l == r){
            sum[p] = tag[p] = 0;
            return ;
        }
        int mid = (l + r) / 2;
        build(p * 2, l, mid);
        build(p * 2 + 1, mid + 1, r);
        pushup(p);
    }
    void down(int p, int l, int r){
        if (tag[p]){
            int mid = (l + r) / 2;
            tag[p << 1] += tag[p];
            tag[p << 1 | 1] += tag[p];
            sum[p << 1] += tag[p] * (mid - l + 1);
            sum[p << 1 | 1] += tag[p] * (r - mid);
            tag[p] = 0;
        }
    }
    void modify(int p, int l, int r, int s, int t, int v){
        if (l >= s && r <= t){
            tag[p] += v;
            sum[p] += v * (r - l + 1);
            return ;
        }
        down(p, l, r);
        int mid = (l + r) / 2;
        if (s <= mid)
            modify(p * 2, l, mid, s, t, v);
        if (t > mid)
            modify(p * 2 + 1, mid + 1, r, s, t, v);
        pushup(p);
    }
    int query(int p, int l, int r, int s, int t){
        if (l >= s && r <= t)
            return sum[p];
        down(p, l, r);
        int mid = (l + r) / 2;
        int ans = 0;
        if (s <= mid)
            ans += query(p * 2, l, mid, s, t);
        if (t > mid)
            ans += query(p * 2 + 1, mid + 1, r, s, t);
        return ans; 
    }
}T;
void add(int u, int v){
    while (top[u] != top[v]){
        if (de[top[u]] < de[top[v]])
            swap(u, v);
        T.modify(1, 1, n, dfn[top[u]], dfn[u], 1);
        u = fa[top[u]];
    }
    if (de[u] < de[v])
        swap(u, v);
    if (u != v)
        T.modify(1, 1, n, dfn[v] + 1, dfn[u], 1); //只有中间一条边，需要注意
}
int ask(int u, int v){
    int ans = 0;
    while (top[u] != top[v]){
        if (de[top[u]] < de[top[v]])
            swap(u, v);
        ans += T.query(1, 1, n, dfn[top[u]], dfn[u]);
        u = fa[top[u]];
    }
    if (de[u] < de[v])
        swap(u, v);
    if (u != v)
        ans += T.query(1, 1, n, dfn[v] + 1, dfn[u]); //只有中间一条边，需要注意
    return ans;
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i < n; i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    dfs1(1, 0);
    dfs2(1, 1);
    T.build(1, 1, n);
    for (int i = 1; i <= m; i++){
        cin >> op;
        if (op == 'P'){
            cin >> u >> v;
            add(u, v);
        }
        if (op == 'Q'){
            cin >> u >> v;
            cout << ask(u, v) << '\n';
        }
    }
}

LG4092 [HEOI2016/TJOI2016] 树

原题链接：[HEOI2016/TJOI2016] 树

分析

这是树剖Σ(っ °Д °;)っ
我学的树剖是假的吗/(ㄒoㄒ)/~~
首先，我们要明确如何使用树链剖分求 LCA，发现是跳 top，那很🍬。
考虑这题怎么写，由于经过树剖之后，链上的 dfs 序连续，所以，转化为单点修改，区间查第一个被修改的。
那离线做个并查集，反过来做，同一个最近被修改的为一个连通块，修改变为删除，破除连通性即可。

正解

#include <bits/stdc++.h>
using namespace std;
const int N = 100005;
int n, q, u, v;
struct ask{
	char op;
	int id, res;
}ans[N];
vector<int> e[N];
int fa[N]; //并查集
int father[N]; //父亲
int tag[N];
void dfs(int u, int f){
	father[u] = f; 
	if (tag[u])
		fa[u] = u;
	else
		fa[u] = f;
	for (auto v : e[u]){
		if (v == f)
			continue;
		dfs(v, u);
	}
} 
int find(int x){
	return x == fa[x] ? x : fa[x] = find(fa[x]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> q;
	for (int i = 1; i < n; i++){
		cin >> u >> v;
		e[u].push_back(v);
		e[v].push_back(u);
	}
	tag[1] = 1;
	for (int i = 1; i <= q; i++){
		cin >> ans[i].op >> ans[i].id;
		if (ans[i].op == 'C'){
			tag[ans[i].id]++;
		}
	}
	dfs(1, 0);
	father[1] = 1;
	fa[1] = 1;
	for (int i = q; i >= 1; i--){
		if (ans[i].op == 'C'){
			tag[ans[i].id]--;
			if (!tag[ans[i].id])
				fa[ans[i].id] = father[ans[i].id];
		}
		else{
			ans[i].res = find(ans[i].id);
		}
	}
	for (int i = 1; i <= q; i++){
		if (ans[i].op == 'Q')
			cout << ans[i].res << '\n';
	}
}
# c++ # 算法
Logo
开源鸿蒙跨平台开发者社区

开源鸿蒙跨平台开发社区汇聚开发者与厂商，共建“一次开发，多端部署”的开源生态，致力于降低跨端开发门槛，推动万物智联创新

更多推荐

cover

kmp openharmony 安全风险评估与防护建议

avatar 开源鸿蒙跨平台开发者社区

OpenHarmony Flutter 导航与路由实战：从基础跳转至分布式流转

dartdart@overridetitle: '路由拦截Demo',// 路由生成器：实现拦截逻辑// 需要登录的路由列表// 检查是否需要登录且未登录// 跳转到登录页，并记录目标路由// 正常路由跳转(context),},导航路由是应用的 “骨架”，从基础的页面跳转，到进阶的参数传递、路由拦截，再到开源鸿蒙特有的分布式流转，每个环节都需要结合业务需求和设备特性进行设计。

avatar 开源鸿蒙跨平台开发者社区
cover

鸿蒙 Flutter 开发实战：从入门到优化，打造高性能跨平台应用

avatar 开源鸿蒙跨平台开发者社区