# 2026 海亮夏令营题单与知识点总结

## 总览

日期 | 作业题数 | 比赛题数 | 去重后题数 | 主要算法
--- | --- | --- | --- | ---
7 月 7 日 | 4 | 8 | 8 | 模拟、BFS、括号贡献、生成树
7 月 8 日 | 15 | 0 | 15 | 基环树 DP、单调队列、线段树
7 月 9 日 | 3 | 4 | 4 | 排序、分组背包、单调队列
7 月 10 日 | 6 | 0 | 6 | 离散化、权值树、可持久化线段树
7 月 11 日 | 4 | 4 | 4 | 贪心、0/1 背包、高维差分
7 月 13 日 | 4 | 4 | 4 | 位运算、字典序 BFS、树上贪心、容斥
7 月 14 日 | 10 | 0 | 10 | 质数、分解、gcd、同余与逆元
7 月 15 日 | 4 | 4 | 4 | 二分、分类讨论、字符串 DP、搜索剪枝
7 月 16 日 | 7 | 0 | 7 | 组合数学、欧拉函数、区间筛、反素数
7 月 17 日 | 4 | 4 | 4 | 环上模拟、反射展开、树形 DP、树上覆盖
7 月 19 日 | 4 | 4 | 4 | 构造、贪心拆分、债务净额、路径背包
7 月 20 日 | 6 | 0 | 6 | 次短路、最短路计数、0-1 BFS、负环
7 月 21 日 | 4 | 4 | 4 | 字典序、多边形判定、数据结构优化 DP
7 月 22 日 | 7 | 0 | 7 | 直径、树上 DP、Tarjan LCA、树上差分
7 月 23 日 | 5 | 8 | 8 | 最短路、最大生成树、逆序对、欧拉函数

## 7 月 7 日

### 题单

来源 | 题号 / 题名（全部可点）
--- | ---
比赛 + 订正作业 | A 地雷 · 2863 地雷（订正）
比赛 + 订正作业 | B 立方体 · 2864 立方体（订正）
比赛 + 订正作业 | C 括号 · 2865 括号（订正）
比赛 | D 卡牌
比赛 | E 区间
比赛 + 订正作业 | F 生成树 · 2868 生成树（订正）
比赛 | G 排列
比赛 | H 字符串

### 知识点

- 地雷按每颗雷把周围八格的计数加一，复杂度 $O(nm+k)$；立方体把每个可走位置看成状态，跑三维 BFS，第一次到终点就是最短路。
- 括号不是把巨大的值真的算出来，而是算贡献：一个最内层 `()` 前面若有 $c$ 个还没匹配的左括号，它贡献 $2^c$。只比较大小时，可以直接维护二进制位，没必要高精度。
- 生成树先由 $n-m$ 反解代码里的二次式，得到 $x\approx\frac32+\sqrt{\frac94-2(n-m)}$，化简再把 $x$ 代入计数公式并对 $998244353$ 取模。

### Code

A 地雷

    	for(int i = 1;i <= k;i++){
    		int x, y;cin >> x >> y;
    		b[x][y] = -1;
    		d[x + 1][y]++;
    		d[x][y + 1]++;
    		d[x - 1][y]++;
    		d[x][y - 1]++;
    		d[x + 1][y + 1]++;
    		d[x - 1][y + 1]++;
    		d[x + 1][y - 1]++;
    		d[x - 1][y - 1]++;
    	}

B 立方体

    void bfs(int sx, int sy, int sz, int cnt) {
    	queue<node> q;
        q.push({sx, sy, sz, cnt});
        v[sx][sy][sz] = 1;
        while (q.size()) {
            node u = q.front();
            q.pop();
            int x = u.x, y = u.y, z = u.z, cnt = u.cnt;
            v[x][y][z] = 0;
            if (x > n or y > n or z > n or x < 1 or y < 1 or z < 1)
                continue;
            if (u.cnt > ds[x][y][z])
                continue;
            ds[x][y][z] = u.cnt;
            if (!d[x + 1][y][z] and !v[x + 1][y][z]) {
                q.push({ x + 1, y, z, cnt + 1 });
                v[x + 1][y][z] = 1;
            }
            if (!d[x][y + 1][z] and !v[x][y + 1][z]) {
                q.push({ x, y + 1, z, cnt + 1 });
                v[x][y + 1][z] = 1;
            }
            if (!d[x - 1][y][z] and !v[x - 1][y][z]) {
                q.push({ x - 1, y, z, cnt + 1 });
                v[x - 1][y][z] = 1;
            }
            if (!d[x][y - 1][z] and !v[x][y - 1][z]) {
                q.push({ x, y - 1, z, cnt + 1 });
                v[x][y - 1][z] = 1;
            }
            if (!d[x][y][z + 1] and !v[x][y][z + 1]) {
                q.push({ x, y, z + 1, cnt + 1 });
                v[x][y][z + 1] = 1;
            }
            if (!d[x][y][z - 1] and !v[x][y][z - 1]) {
                q.push({ x, y, z - 1, cnt + 1 });
                v[x][y][z - 1] = 1;
            }
        }

C 括号

    void solve(string ss){
    	stack<int> s;int cnt = 0;
    	for(int i = 0;i < ss.size();i++){
    		if(ss[i] == '('){
    			cnt++;
    		}
    		if(ss[i] == ')'){
    			cnt--;
    			if(ss[i - 1] == '('){
    				B[cnt]++;
    			}
    		}
    	}int x = 0;
    	for(int i = 0;i <= 5000000;i++){
    		B[i] += x;
    		x = B[i] / 2;
    		B[i] %= 2;
    //		cout << B[i];
    	}
    //	cout << endl;
    }

F 生成树

    	while(T--){
    		scanf("%lld%lld", &n, &m);
    		int x = 1.5 + sqrt(2.25 - 2 * (n - m));
    //		printf("%lld\n", x);
    		int ans = (((x*x)+5)*x/6 + (n-x-1)*(2*m-n+x+2)/2)%MOD;
    		printf("%lld\n", ans);
    	}

### 20260707周赛：复盘

题目顺序：T1 = A 地雷；T2 = B 立方体；T3 = C 括号；T4 = D 卡牌；T5 = E 区间；T6 = F 生成树；T7 = G 排列；T8 = H 字符串

项目 | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8
--- | --- | --- | --- | --- | --- | --- | --- | ---
涉及算法标签 | 模拟 | 搜索 | 模拟？ | 数学？ | - | - | 数学推导 | -
得分 | 100 | 32.89 | 26 | - | - | - | - | -
备注 | (拉了）
错误原因 | - | □ 算法盲区 | □ 代码实现写挂 | □ 时间不够 | □ 时间不够 | □ 时间不够 | □ 时间不够 | □ 时间不够
正确解法核心 | 同上 | 同上 | 同上 | - | - | - | 同上 | -
以前做过的同类型题 | 好像无所谓 | 貌似无 | [Junior] 括号匹配 | - | - | - | - | -
今天最大的教训 | 纯傻福来的
需要补的知识漏洞 | 三维的BFS???

## 7 月 8 日

### 题单（去重后 15 题）

来源 | 题号 / 题名（全部可点）
--- | ---
作业 | P3554 [POI 2013] LUK-Triumphal arch
作业 | P1613 跑路
作业 | P10933 创世纪
作业 | 255 [ZJOI2008] 骑士
作业 | 2929 城市环路
作业 | DPM Candies
作业 | P1886 滑动窗口 /【模板】单调队列
作业 | 2887 琪露诺
作业 | P6040 「ACOI2020」课后期末考试滑溜滑溜补习班
作业 | P2569 [SCOI2010] 股票交易
作业 | DPQ Flowers
作业 | P3372 【模板】线段树 1
作业 | P3373 【模板】线段树 2
作业 | P2846 [USACO08NOV] Light Switching G
作业 | 2931 [USACO08FEB] Hotel G

### 知识点

- DP 优化的常见形状是 $dp[i]=w_i+\max\limits_{j\in[L_i,R_i]}dp[j]$。窗口滑动时用单调队列维护候选最大值，把一层 $O(n^2)$ 压到 $O(n)$。
- 树形 DP、基环树 DP 要先认清依赖方向；有环时通常断环、枚举环上状态，再把挂在环上的树合并进去。

### Code

P10933 创世纪

    void dfs(int u, int root, bool flag) {
        dfn[u] = 1;
        dp[u][0] = 0;
        int mi = INT_MAX;
        for (auto v : adj[u]) {
            if (v == root)
                continue;
            dfs(v, root, flag);
            dp[u][0] += max(dp[v][1], dp[v][0]);
            mi = min(mi, max(dp[v][0], dp[v][1]) - dp[v][0]);
        }
    	dp[u][1] = 1 + dp[u][0] - mi;
    	if (flag && u == a[root]){
    		dp[u][1] += mi;
    	}
    }
    int main() {
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
            adj[a[i]].push_back(i);
        }
        int sum = 0;
        for (int x = 1; x <= n; x++) {
            if (!dfn[x]) {
                while (!vis[x]) {   //环
                    vis[x] = 1;
                    x = a[x];
                }
                dfs(x, x, 0);
    //			cout << x;
                int ans = max(dp[x][0], dp[x][1]);
                dfs(x, x, 1);
                sum += max(dp[x][0], ans);
            }
        }
        cout << sum;

## 7 月 9 日

### 题单（去重后 4 题）

来源 | 题号 / 题名（全部可点）
--- | ---
比赛 + 订正作业 | A 数对（Pair） · A. 数对（Pair）（订正）
比赛 + 订正作业 | B 魔法升级（Magic） · 2911 魔法升级（Magic）（订正）
比赛 + 订正作业 | C 香蕉树（Banana） · 2912 香蕉树（Banana）（订正）
比赛 | D 天赋点（Talent）

### 知识点

- 数对题先令每对 $a_i\le b_i$。讲评把答案化成 $\sum\max(a_i,b_i)-\text{最小的 }n\text{ 个 }(a_i+b_i)\text{ 之和}$，排序后就是 $O(n\log n)$。
- 魔法升级：分组背包模板
- 香蕉树的转移窗口会滑动，用单调队列维护上一层可转移的最大 $dp$。

### Code

A 数对（Pair）

    	for(int i = 1;i <= n * 2;i++){
    		int x, y;cin >> x >> y;
    		ans += max(x, y);sum[i] = x + y;
    	}
    	sort(sum + 1, sum + 1 + n * 2);
    	for(int i = 1;i <= n;i++){
    		ans -= sum[i];
    	}
    	cout << ans;

B 魔法升级（Magic）

    	for(int ii = 1;ii <= tot;ii++){
    		bool i = ii % 2;
    		for(int j = 0;j <= m;j++){
    			dp[i][j][0] = dp[i][j][1] = 0;
    		}
    		for(int j = 0;j <= m;j++){
    			ans[i][j][0] = ans[i][j][1] = zero;
    			if(j >= c[num[ii]]){
    				if(num[ii] != num[ii - 1]){
    					int kk = dp[!i][j - c[num[ii]]][0] < dp[!i][j - c[num[ii]]][1] ? 1 : 0;
    					dp[i][j][1] = dp[!i][j - c[num[ii]]][kk] + w[ii];
    					ans[i][j][1] = ans[!i][j - c[num[ii]]][kk];
    					add(i, j, 1, ii);
    				}else{
    					dp[i][j][1] = dp[!i][j - c[num[ii]]][1] + w[ii];
    					ans[i][j][1] = ans[!i][j - c[num[ii]]][1];
    					add(i, j, 1, ii);
    				}
    			}
    			int kk = dp[!i][j][0] < dp[!i][j][1] ? 1 : 0;
    			dp[i][j][0] = dp[!i][j][kk];
    			ans[i][j][0] = ans[!i][j][kk];

C 香蕉树（Banana）

    	for(int j = 1;j <= k;j++){
    		for(int i = 2;i <= n;i++){
    			while(l <= r and dp[q[j - 1][r]][j - 1] <= dp[i - 1][j - 1]){
    				r--;
    			}q[j - 1][++r] = i - 1;
    			while(l <= r and abs(d[i] - d[q[j - 1][l]]) > m){
    				l++;
    			}

    //			cout << q[j-1][l] << ' ';
    			dp[i][j] = max(dp[q[j - 1][l]][j - 1] + a[i], dp[i][j]);
    //			cout << i << ' ' << j << ' ' << dp[i][j] << endl;
    			ans = max(ans, dp[i][j]);
    		}
    	}

### 普转提20260709模拟赛：复盘

题目顺序：T1 = A 数对（Pair）；T2 = B 魔法升级（Magic）；T3 = C 香蕉树（Banana）；T4 = D 天赋点（Talent）

项目 | T1 | T2 | T3 | T4
--- | --- | --- | --- | ---
涉及算法标签 | 数学推导 | 分组背包 | 单调队列优化DP | 概率DP
得分 | 100 | 100 | 0 | -
错误原因 | - | - | □ 代码实现写挂 | □ 时间不够
正确解法核心 | 同上 | 同上 | 同上 | -
以前做过的同类型题 | 无 | 分组背包－旅行者的背包 | 分组背包－旅行者的背包 | 无
今天最大的教训 | 提升代码实现&debug能力
需要补的知识漏洞 | （概率DP？）

## 7 月 10 日

### 题单（去重后 6 题）

来源 | 题号 / 题名（全部可点）
--- | ---
作业 | P1496 火烧赤壁
作业 | P1908 逆序对
作业 | luogu#P3369 【模板】普通平衡树
作业 | P3919 【模板】可持久化线段树 1（可持久化数组）
作业 | 2944 【模板】可持久化线段树 2
作业 | P3168 [CQOI2015] 任务查询系统

### 知识点

- 可持久化线段树只复制从根到被修改位置的一条链，因此单次修改新增 $O(\log n)$ 个节点；版本根节点数组就是时间轴。
- 主席树做第 $k$ 小时，用两个前缀版本相减，递归判断左儿子计数够不够：若 $cnt_L\ge k$ 就走左边，否则走右边并令 $k\leftarrow k-cnt_L$。
- 权值线段树把值域当区间维护出现次数；单点增删后，按左子树计数找第 $k$ 小，排名则查询小于 $x$ 的数有多少个再加一。

### Code

2944 【模板】可持久化线段树 2

    void mdy(int &p, int l, int r, int d) {
    	t[++id] = t[p]; p = id;
    	t[p].d++;
    //	pushup(pp);
        if (l == r) {
            return;
        }
        int mid = (l + r) >> 1;
        if (d <= mid)
            mdy(t[p].l, l, mid, d);
        else
            mdy(t[p].r, mid + 1, r, d);
    }
    int qry(int p, int q, int l, int r, int k) {
        if (l == r)
            return l;
        int mid = (l + r) >> 1;
        int lcnt = t[t[p].l].d - t[t[q].l].d;
        if (k <= lcnt)
            return qry(t[p].l, t[q].l, l, mid, k);
        else
            return qry(t[p].r, t[q].r, mid + 1, r, k - lcnt);
    }

luogu#P3369 【模板】普通平衡树

    void mdy(int &p, int l, int r, int d, int v) {
    	if (!p) p = ++id;
        if (l == r) {
            t[p].d += v;
            return;
        }
        int mid = (l + r) >> 1;
        if (d <= mid)
            mdy(t[p].l, l, mid, d, v);
        else
            mdy(t[p].r, mid + 1, r, d, v);
        pushup(p);
    }
    int tk(int p, int l,int r,int v){
    	if(l == r) return l;
    	int mid = (l + r) >> 1;
    	if(v <= t[t[p].l].d) return tk(t[p].l, l, mid, v);
    	else return tk(t[p].r, mid + 1, r, v - t[t[p].l].d);
    }

## 7 月 11 日

### 题单（去重后 4 题）

来源 | 题号 / 题名（全部可点）
--- | ---
比赛 + 订正作业 | A 慢跑 · 2983 慢跑（订正）
比赛 + 订正作业 | B 对战 · 2984 对战（订正）
比赛 + 订正作业 | C 回文串 · 2985 回文串（订正）
比赛 + 订正作业 | D 读档 · 2986 读档（订正）

### 知识点

- 慢跑从队尾往前扫，维护当前最小速度。当前速度更快就会追上并合并，否则新开一队，直接 $O(n)$。
- 对战是 0/1 背包找最接近总和一半的子集。若总和为 $S$、最好子集和为 $x\le S/2$，最小差就是 $S-2x$。
- 回文串看每个字符的奇偶性：一个回文最多容纳一种奇数频次字符，先确定至少要拆多少组，再把成对字符尽量平均分。
- 读档是高维前缀和的逆运算。对每个点枚举维度子集：$a_x=\sum\limits_{mask=0}^{2^d-1}(-1)^{\operatorname{popcount}(mask)}b_{x-\delta(mask)}$。

### Code

A 慢跑

    	int cnt = 1, j = n;
    	for(int i = j - 1;i >= 1;i--){
    		while(b[i] > b[j]) i--;
    		if(b[i] <= b[j] and i > 0){
    			cnt++;j = i;
    //			cout << i << endl;
    		}
    	}

B 对战

        for (int i = 1; i <= n; i++) { cin >> a[i]; tot += a[i]; }
        dp[0] = 1;
        for (int i = 1; i <= n; i++)
            for (int j = tot; j >= a[i]; j--)
                dp[j] |= dp[j - a[i]];
        for (int i = tot / 2; i >= 0; i--)
            if (dp[i]) { cout << tot - 2 * i << '\n'; return 0; }

C 回文串

    		int o = 0, e = 0, cnt = 0;
    		for(int i = 1;i <= n;i++){
    			cin >> a[i];
    			if(a[i] % 2 == 0) e += a[i];
    			else{
    				cnt++;
    				o += a[i] - 1;
    			}
    		}
    		if(cnt == 0) cout << e <<'\n';
    		else cout << (int)((o + e) / cnt / 2) * 2 + 1 << '\n';
    	}

D 读档

    	for(int i = n;i >= 1;i--){
    		st[i] = tot;tot *= s[i];
    	}
    	for(int i = 0;i < tot;i++) cin >> b[i];
    	for(int d = 1;d <= n;d++){
    		for(int i = tot - 1;i >= 0;i--){
    			if(i / st[d] % s[d]) b[i] -= b[i - st[d]];
    		}
    	}

### 普转提20260711模拟赛：复盘

题目顺序：T1 = A 慢跑；T2 = B 对战；T3 = C 回文串；T4 = D 读档

项目 | T1 | T2 | T3 | T4
--- | --- | --- | --- | ---
涉及算法标签 | 模拟？ | DP | 模拟 | 高维差分（前缀和）
得分 | 100 | 20 | 100 | 10
错误原因 | - | □ 数组越界：j-a[i]>0忘判了 | - | □ 时间不够
正确解法核心 | 同上 | 同上 | 同上 | 同上
以前做过的同类型题 | 无所谓，，，。。。 | （类似）01 背包 | 无 | 二维差分数组的操作（PLUS 版）
今天最大的教训 | 检查数组是否越界！
需要补的知识漏洞 | 高维差分？

## 7 月 13 日

### 题单（去重后 4 题）

来源 | 题号 / 题名（全部可点）
--- | ---
比赛 + 订正作业 | A 数位跃迁 · 2988 数位跃迁（订正）
比赛 + 订正作业 | B 秘符石板 · 2989 秘符石板（订正）
比赛 + 订正作业 | C 果树引枝 · 2990 果树引枝（订正）
比赛 + 订正作业 | D 小樱的库洛牌 · 2991 小樱的库洛牌（订正）

### 知识点

- 数位跃迁先把状态看成二进制点。最优中转点是全 $1$ 的掩码 $M=2^n-1$，因此不同状态间的代价可写成 $(s\oplus M)+(t\oplus M)$。
- 秘符石板要求字典序最小路径。按路径长度一层层扩展，只保留当前层字符最小的前沿点，像 BFS 一样推进，复杂度 $O(nm)$。
- 果树引枝是树上贪心：每个节点只把“最短、最值得留给父亲处理”的那条链往上抛，其余链在当前节点结算；答案也有单调性，因此能套二分检查。
- 库洛牌先统计未知位置数 $k$，以及可能形成固定点的位置数 $c$，再做容斥：$ans=\sum_{i=0}^{c}(-1)^i\binom{c}{i}(k-i)!$。

### Code

A 数位跃迁

    	while(T--){
    		int n, s, t;
    		cin >> n >> s >> t;
    		if(s == t) cout << 0 << '\n';
    		else if((s | t) == (1 << n) - 1) cout << (s ^ t) << '\n';
    		else cout << (s ^ ((1 << n) - 1)) + (t ^ ((1 << n) - 1)) << '\n';
    	}

B 秘符石板

    	for(int k = 1;k <= n + m - 2;k++){
    		char mn = 'z' + 1;

    		for(auto x : q){
    			int i = x.fi, j = x.se;
    			if(i < n) mn = min(mn, a[i + 1][j]);
    			if(j < m) mn = min(mn, a[i][j + 1]);
    		}

    		nq.clear();

    		for(auto x : q){
    			int i = x.fi, j = x.se;

    			if(i < n and a[i + 1][j] == mn and !vis[i + 1][j]){
    				vis[i + 1][j] = 1;
    				nq.push_back({i + 1, j});
    			}

    			if(j < m and a[i][j + 1] == mn and !vis[i][j + 1]){
    				vis[i][j + 1] = 1;
    				nq.push_back({i, j + 1});
    			}
    		}

    		cout << mn;
    		q = nq;
    	}

C 果树引枝

    void dfs(int u, int fa,int k){
    	if(adj[u].size() == 0){
    		dp[u] = k + 1;
    		return ;
    	}
    	for(int v : adj[u]){
    		if(v == fa) continue;
    		dfs(v, u, k);
    		dp[u] = max(dp[u], dp[v] - 1);
    		if(dp[v] < 2) flag = 0;
    	}
    //	cout << u << ' ' << dp[u]<<'\n';
    }
    bool check(int k){
    	flag = 1;
    	memset(dp, 0, sizeof dp);
    	dfs(1, 0, k);
    	if(dp[1] > 0 and flag) return 1;
    	else return 0;
    }

D 小樱的库洛牌

    	int ans = 0;

    	for(int i = 0;i <= c;i++){
    		int tmp = C(c, i) * fac[k - i] % MOD;

    		if(i & 1){
    			ans = (ans - tmp + MOD) % MOD;
    		}else{
    			ans = (ans + tmp) % MOD;
    		}
    	}

### 普转提20260713模拟赛：复盘

题目顺序：T1 = A 数位跃迁；T2 = B 秘符石板；T3 = C 果树引枝；T4 = D 小樱的库洛牌

项目 | T1 | T2 | T3 | T4
--- | --- | --- | --- | ---
涉及算法标签 | 推导（结论题） | 类似BFS搜索 | 树上DP | 容斥+阶乘逆元（类似错排的一般公式）
得分 | 100 | 70 | 80 | 10
错误原因 | - | □ 审题看漏条件 | □ 手贱开longlong被卡常（？？？） | □ 时间不够
正确解法核心 | 同上 | 同上 | 同上 | 同上
以前做过的同类型题 | 无（吧） | 犯罪团伙（大数据版）？？？算法类似吧 | [POI 2013] LUK-Triumphal Arch | 无
今天最大的教训 | 不要瞎开longlong？？
需要补的知识漏洞 | 错排

## 7 月 14 日

### 题单（去重后 10 题）

来源 | 题号 / 题名（全部可点）
--- | ---
作业 | HLP804 倒水
作业 | HLP821 越狱
作业 | H1003 判素数
作业 | HLP812 回文质数
作业 | B2084 质因数分解
作业 | 3019 Prime Distance
作业 | HLP1393 Hankson的趣味题
作业 | HLP372 【NOIP2012提高组】同余方程
作业 | HLP1429 青蛙的约会
作业 | HLP375 求逆元

### 知识点

- 若 $n=\prod p_i^{c_i}$，则 $d(n)=\prod(c_i+1)$，$\sigma(n)=\prod\frac{p_i^{c_i+1}-1}{p_i-1}$。
- 扩展欧几里得：$\gcd(a,b)=\gcd(b,a\bmod b)$；扩展欧几里得求 $ax+by=\gcd(a,b)$，也可以解决线性同余。
- 当 $\gcd(a,m)=1$ 时，逆元满足 $ax\equiv1\pmod m$。可以用 exgcd，也可以在模数为质数时用费马小定理 $a^{m-2}\bmod m$。

### Code

HLP372 同余方程

    void exgcd(int a, int b, int &x, int &y) {
        if (b == 0) {
            x = 1;
            y = 0;
            return;
        }
        exgcd(b, a % b, y, x);
        y -= a / b * x;
    }

    signed main() {
        int a, b, x, y;
        cin >> a >> b;
        exgcd(a, b, x, y);
        x = (x % b + b) % b;
        cout << x << endl;

## 7 月 15 日

### 题单（去重后 4 题）

来源 | 题号 / 题名（全部可点）
--- | ---
比赛 + 订正作业 | A 砍伐树木 · 2987 砍伐树木（订正）
比赛 + 订正作业 | B 恶作剧1 · 3020 恶作剧1（订正）
比赛 + 订正作业 | C 恶作剧2 · 3021 恶作剧2（订正）
比赛 + 订正作业 | D 卡牌游戏 · 3022 卡牌游戏（订正）

### 知识点

- 砍树二分答案。
- 折纸纵向和横向分开算；横向分“完全落在重叠区、跨界”两种情况讨论。
- 恶作剧 2 是字符串切分 DP：$dp[pos][sum]$ 表示处理到 `pos`、当前和为 `sum` 时最少加号数。枚举上一刀位置即可，过长且已超过目标的数字可以直接剪掉。
- 卡牌游戏是质因数需求分配。先用必要条件判无解，再 DFS 分配卡牌；把“质因子多”的卡牌先搜，剪掉坏分支。

### Code

A 砍伐树木

    bool check(int k){
    	int tot = 0;
    	for(int i = 1;i <= n;i++){
    		if(a[i] - k >= 0) tot += a[i] - k;
    		if(tot >= m) return 1;
    	}
    	return 0;
    }

B 恶作剧1

    		int k = (yy - y) * (xx - x);

    		f = min(f, w - f);

    		int b = 0;
    		if(x < f){
    			b = (min(xx, f) - x) * (yy - y);
    		}

    		k += b;

    		cout << w * h - k * (c + 1) << '\n';
    	}

C 恶作剧2

    	memset(dp,0x3f,sizeof(dp));
    	dp[0][0]=-1;

    	for(int i=0;i<len;i++){
    		for(int j=0;j<=n;j++){
    			for(int v=1;v<=i+1;v++){
    				int l=i-v+1;
    				if(sum[l][i]>j) continue;
    				if(dp[l][j-sum[l][i]]>1000) continue;

    				dp[i+1][j]=min(dp[i+1][j],
    					dp[l][j-sum[l][i]]+1);
    			}
    		}
    	}

D 卡牌游戏

    void dfs(int id,long long sum[]){
    	if(find_ans==1) return;
    	if(id==1){
    		bool flag=1;
    		for(int i=1;i<=n;i++){
    			if(sum[i]!=score[i]){
    				flag=0;
    				break;
    			}
    		}
    		if(flag==1){
    			find_ans=1;
    		}
    		return;
    	}
    	//branch 1
    	for(int i=1;i<=n;i++){
    //		if(i>1&&sum[i]==sum[i-1]) continue;
    		long long nxt_sum=sum[i]*id;
    		if(nxt_sum>score[i]) continue;
    		if(score[i]%nxt_sum!=0) continue;
    		sum[i]=nxt_sum;
    		dfs(id-1,sum);
    		sum[i]/=id;
    		if(find_ans==1) return;
    	}
    	//branch 2
    	dfs(id-1,sum);
    }

### 普转提260715模拟赛：复盘

题目顺序：T1 = A 砍伐树木；T2 = B 恶作剧1；T3 = C 恶作剧2；T4 = D 卡牌游戏

项目 | T1 | T2 | T3 | T4
--- | --- | --- | --- | ---
涉及算法标签 | 二分答案 | 数学？ | DP | DFS剪枝
得分 | 0 | 40 | 100 | -
错误原因 | □ 手滑删东西 -> CE!!!! | □ 代码实现写挂 | - | □ 时间不够
正确解法核心 | 同上 | 同上 | 同上 | 同上
以前做过的同类型题 | 二分查找－整数序列 | 无。。。 | 没找见，，？？ | -
今天最大的教训 | 交之前/后检查
需要补的知识漏洞 | 没啥

## 7 月 16 日

### 题单（去重后 7 题）

来源 | 题号 / 题名（全部可点）
--- | ---
作业 | P1305C Kuroni and Impossible Calculation
作业 | P48 【UR #3】核聚变反应强度
作业 | P2822 [NOIP 2016 提高组] 组合数问题
作业 | HLP383 【bzoj2705】[SDOI2012]Longge的问题
作业 | BZOJ1607 轻拍牛头
作业 | 3019 Prime Distance
作业 | BZOJ1053 [HAOI2007] 反素数

### 知识点

- 组合数取模不一定能直接除。先看模数是否为质数、是否能预处理阶乘逆元；模数较小时还会用 Lucas、质因数分解或按素因子统计指数。
- 欧拉函数满足 $\varphi(n)=n\prod_{p\mid n}(1-1/p)$。像 Longge 这类 gcd 求和，通常先按 $\gcd$ 值分组，再把计数化成 $\varphi$。
- Prime Distance 是区间筛：先筛出 $\sqrt R$ 内质数，再标记 $[L,R]$ 的倍数，空间只跟区间长度有关。
- 反素数常用 DFS 枚举质因子指数，而且指数要单调不增；这样既避免重复，又能按约数个数剪枝。

### Code

3019 Prime Distance

    		for(int j = 1;j <= m;j++){
    			int st = max(2ll, (l + prime[j] - 1) / prime[j]);

    			for(int i = st;i <= r / prime[j];i++){
    				p[prime[j] * i - l] = 1;
    			}
    		}

    		int cnt = 0;
    		for(int i = l;i <= r;i++){
    			if(!p[i - l]){
    				a[++cnt] = i;
    			}
    		}

## 7 月 17 日

### 题单（去重后 4 题）

来源 | 题号 / 题名（全部可点）
--- | ---
比赛 + 订正作业 | A 跑步 · 3040 跑步（订正）
比赛 + 订正作业 | B 反射 · 3041 反射（订正）
比赛 + 订正作业 | C 树 · 3042 树（订正）
比赛 + 订正作业 | D 店铺 · 3043 店铺（订正）

### 知识点

- 跑步直接模拟两人的环上位置：整圈先计入答案，剩下的位移取模，再判断这一段有没有跨过对方当前位置，复杂度 $O(m)$。
- 反射题用展开法：把每次镜面反射改成穿过镜像矩形的直线。是否撞角、反射多少次，就变成比较 $n,m$ 的公倍数和 $\gcd(n,m)$。
- 树题先 DFS 算每个点向下的最大深度 $md$，再用第二遍 DFS 维护父亲方向的最远距离；转移时要记儿子中的最大值、次大值，最后答案是 $\max(md[u],father[u])$。
- 店铺题是若干条向根路径覆盖需求点。可以二分时间 $T$，再在树上贪心判断 $m$ 台机器能否覆盖；越深、越来不及的需求要优先处理。

### Code

A 跑步

    	for(int i = 1;i <= m;i++){
    		cin >> a >> b;
    		cnt += a / n;
    		a %= n;
    		if((a + x >= y and y > x) or ((a + x) % n >= y and (a + x) % n < x)) cnt++;
    		x += a;x %= n;
    		cnt += b / n;
    		b %= n;
    		if((b + y >= x and x > y) or ((b + y) % n >= x and (b + y) % n < y)) cnt++;
    		y += b;y %= n;
    	}

B 反射

        int n, m;
        cin >> n >> m;

        int g = __gcd(n, m);
        int ans = (n + m) / g - 2;

        cout << ans;

C 树

    void dfs2(int u, int fa){
    	int m1 = 0, m2 = 0, v1 = 0;
    	for(int v : adj[u]){
    		if(v == fa) continue;
    		int k = md[v] + 1;
    		if(k > m1){
    			m2 = m1;
    			m1 = k;
    			v1 = v;
    		}else if(k > m2){
    			m2 = k;
    		}
    	}

    	for(int v : adj[u]){
    		if(v == fa) continue;
    		int k = (v == v1 ? m2 : m1);
    		father[v] = max(father[u], k) + 1;
    		dfs2(v, u);
    	}
    }

D 店铺

    bool check(int x){
        for(int i = (int)node.size() - 1;i >= 0;i--){
            int u = node[i];
            int sum = 0, best = INF;

            for(auto [v, w] : g[u]){
                sum += cnt[v];
                sum = min(sum, m + 1);

                if(len[v] + w <= x){
                    best = min(best, len[v] + w);
                }
            }

            if(g[u].empty()){

                cnt[u] = 1;
                len[u] = 0;
            }else if(best != INF){

                cnt[u] = sum;
                len[u] = best;
            }else{

                cnt[u] = min(m + 1, sum + 1);
                len[u] = 0;
            }
        }

        int sum = 0;

        for(int u : root){
            sum += cnt[u];
            if(sum > m) return 0;
        }

        return 1;
    }

### 普转提20260717模拟赛：复盘

题目顺序：T1 = A 跑步；T2 = B 反射；T3 = C 树；T4 = D 店铺

项目 | T1 | T2 | T3 | T4
--- | --- | --- | --- | ---
涉及算法标签 | 模拟 | 搜索/数学推导 | 树的直径 | DP
得分 | 100 | 100 | 40 | 10
错误原因 | - | - | □ 代码实现写挂 | □ 时间不够
正确解法核心 | 同上 | 同上 | 同上 | 同上
以前做过的同类型题 | 无所谓， | CF982E E. Billiard | 【模板】树的直径 | 无
今天最大的教训 | maybe算法熟练度不高？
需要补的知识漏洞 | 树的直径？

## 7 月 19 日

### 题单（去重后 4 题）

来源 | 题号 / 题名（全部可点）
--- | ---
比赛 + 订正作业 | A 语言 · 3045 语言（订正）
比赛 + 订正作业 | B 数字划分 · 3046 数字划分（订正）
比赛 + 订正作业 | C 债权 · 3047 债权（订正）
比赛 + 订正作业 | D 礼物 · 3048 礼物（订正）

### 知识点

- 语言题按位置直接构造答案：先单独判断第一个位置，后面的第 $i$ 位只需要看 $i\le m$，所以整题就是一遍 $O(n)$ 输出。
- 数字划分从最大的全 1 数开始贪心，例如依次尝试 $1111111,111111,\ldots,1$；每取一次就加上这一段的位数，最后还有余数就无解。
- 债权转移后，真正重要的是每个人的净收支。先把所有边累加成 balance，能互相抵消的债不必保留；最小总转账额等价于正余额之和（或负余额绝对值之和）。
- 礼物只在根到节点的一条短链上选物品，是路径 0/1 背包。完全二叉树深度只有 $O(\log n)$，可以按深度分层预处理，前10层dp，后10层搜索。

### Code

A 语言

    	int n, m;cin >> n >> m;
    	if(m < 2) cout << 1;
    	else cout << 0;
    	for(int i = 2;i <= n;i++){
    		if(i > m) cout << 0;
    		else cout << 1;
    	}

B 数字划分

    	for(int i = 1;i <= n;i++){
    		int t = 1111111, j = i, tot = 7, cnt = 0;
    		while(t){
    			while(t * m <= j){
    				j -= t * m;
    				cnt += tot;
    			}
    			t /= 10;tot--;
    		}
    		if(j > 0) cout << -1 << ' ';
    		else cout << cnt << ' ';
    	}

C 债权

        for(int i = 1;i <= m;i++){
            int x, y, z;
            cin >> x >> y >> z;
            a[x] += z;
            a[y] -= z;
        }

        int ans = 0;
        for(int i = 1;i <= n;i++){
            if(a[i] > 0) ans += a[i];
        }

        cout << ans / 10 << '.' << ans % 10;

D 礼物

    void dfs(int u, int fa){
    	for(int j = 0;j <= lmt;j++){
    		dp[u][j] = dp[fa][j];
    		if(j - w[u] >= 0){
    			dp[u][j] = max(dp[u][j], dp[fa][j - w[u]] + v[u]);
    		}
    	}
    	for(int j = 1;j <= lmt;j++){
    		dp[u][j] = max(dp[u][j], dp[u][j - 1]);
    	}
    	if(u * 2 <= n && u * 2 <= 127) dfs(u * 2, u);
    	if(u * 2 + 1 <= n && u * 2 + 1 <= 127) dfs(u * 2 + 1, u);
    }

    void solve(int now, int sumw, int sumv){
    	if(now == cnt + 1){
    		maxx = max(maxx, sumv + dp[ed][x - sumw]);
    		return;
    	}
    	if(sumw + w[a[now]] <= x){
    		solve(now + 1, sumw + w[a[now]], sumv + v[a[now]]);
    	}
    	solve(now + 1, sumw, sumv);
    }

### 普转提260719模拟赛：复盘

题目顺序：T1 = A 语言；T2 = B 数字划分；T3 = C 债权；T4 = D 礼物

项目 | T1 | T2 | T3 | T4
--- | --- | --- | --- | ---
涉及算法标签 | 模拟 | 模拟？ | 稍微推导 | DP+DFS（剪枝）
得分 | 100 | 100 | 100 | 30
错误原因 | - | - | - | □ 边界 □ 时间不够
正确解法核心 | 同上 | 同上 | 同上 | 同上
以前做过的同类型题 | 「第一届太原五中算法与程序挑战赛入门组」语言（同一道！） | 无吧 | 无？ | ？？？
今天最大的教训 | 数组开错大小-30pts
需要补的知识漏洞 | 居然还能DP预处理再DFS暴搜

## 7 月 20 日

### 题单（去重后 6 题）

来源 | 题号 / 题名（全部可点）
--- | ---
作业 | P2865 [USACO06NOV] Roadblocks G
作业 | 2384 最短路计数
作业 | P10947 [BAPC 2006 Qualification] Sightseeing
作业 | P1063B Labyrinth
作业 | P2850 [USACO06DEC] Wormholes G
作业 | P1205B Shortest Cycle

### 知识点

- 次短路要给每个点维护最短和严格次短两个距离；0/1 边权用双端队列，权 0 放队头、权 1 放队尾。
- 最短路计数不仅存 $dist[v]$，还要存 $cnt[v]$：找到更短路就覆盖计数，找到等长路就累加。
- 有负边 就SPFA 的负环判定；多源问题可以建超级源点或把多个源一起入队。

### Code

P2865 Roadblocks G

    void di(long long q){
        memset(dis,0x3f3f3f3f3f3f3f3f,sizeof(dis));
        dis[q][0]=0;
        pq.push({0,q});
        while(!pq.empty()){
            long long u=pq.top().x,d=pq.top().s;
            pq.pop();
            if(d>dis[u][1]) continue;
            for(int i=0;i<tree[u].size();i++){
                long long r=tree[u][i].r,v=tree[u][i].v;
                if(dis[r][0]>d+v){
                    dis[r][1]=dis[r][0];
                    dis[r][0]=d+v;
                    pq.push({dis[r][0],r});
                }else if(dis[r][1]>d+v&&d+v>dis[r][0]){
                    dis[r][1]=d+v;
                    pq.push({dis[r][1],r});
                }else if(dis[r][1]>d+v&&d+v>dis[r][0]){
                    dis[r][1]=d+v;
                    pq.push({dis[r][1],r});
                }
            }
        }
    }

## 7 月 21 日

### 题单（去重后 4 题）

来源 | 题号 / 题名（全部可点）
--- | ---
比赛 + 订正作业 | A 比较 · 3104 比较（订正）
比赛 + 订正作业 | B 多边形 · 3100 多边形（订正）
比赛 + 订正作业 | C 传送 · 3101 传送（订正）
比赛 + 订正作业 | D 项链 · 3102 项链（订正）

### 知识点

- 比较题直接用 `std::string` 的字典序运算：`F < Y` 输出 `F`，相等输出 `-1`，否则输出 `Y`。
- 若若干边能组成凸多边形，核心条件是最长边不超过（严格凸时小于）其余边之和。排序后只检查最大值和总和，不用真的构造图形。
- 传送题的转移是 $dp[i]=1+\max\{dp[j]\mid j>i,\ a_j<a_i\}$。按位置倒序扫，用树状数组或线段树维护前缀最大值。
- 项链的“染一段同色”很像 strange printer：$dp[l][r]$ 表示区间最少操作；环形还要枚举断点，镜像等价时再把反转序列一起比较。

### Code

A 比较

    	int n; cin >> n;
    	string F, Y;cin >> F >> Y;
    	cout << (F < Y ? "F" : (F == Y ? "-1" : "Y"));

B 多边形

    	while(T--){
    		int n; cin >> n;
    			int cnt = 0, maxn = 0;
    			for(int i = 1;i <= n;i++){
    				int a;cin >> a;
    				cnt += a;maxn = max(maxn, a);
    			}
    			if(cnt - maxn <= maxn) cout << "NO\n";
    			else cout << "YES\n";
    	}

C 传送

        for (int i = n; i >= 1; i--) {
    //        for (int j = i + 1; j <= n; j++) {
    //            if (a[i] > a[j])
    //                f[i] = max(f[i], f[j] + 1);
    //        }
    //		f[i] = maxf[a[i] - 1] + 1;
    		f[i] = qry(1, 1, a[i] - 1) + 1;
    //		maxf[a[i]] = max(maxf[a[i]], f[i]);
    		mdy(1, 1, INF, a[i], f[i]);

D 项链

    int solve(int t[]) {
        memset(dp, 0, sizeof(dp));

        for(int i = 1; i <= n; i++) {
            dp[i][i] = 1;
        }

        for(int len = 2; len <= n; len++) {
            for(int l = 1; l + len - 1 <= n; l++) {
                int r = l + len - 1;

                dp[l][r] = dp[l + 1][r] + 1;

                for(int k = l + 1; k <= r; k++) {
                    if(t[l] == t[k]) {
                        int now = dp[k][r];

                        if(k > l + 1) {
                            now += dp[l + 1][k - 1];
                        }

                        dp[l][r] = min(dp[l][r], now);
                    }
                }
            }
        }

### 普转提20260721模拟赛：复盘

题目顺序：T1 = A 比较；T2 = B 多边形；T3 = C 传送；T4 = D 项链

项目 | T1 | T2 | T3 | T4
--- | --- | --- | --- | ---
涉及算法标签 | 模拟？？ | 数学 | 线段树优化DP（最长上升子序列） | 区间DP
得分 | 100 | 100 | 100 | 100
错误原因 | - | - | - | -
正确解法核心 | 同上 | 同上 | 同上 | 同上
以前做过的同类型题 | ？？ | 无 | 最长上升子序列（基础版）（大数据版） | 【CQOI2007】涂色
今天最大的教训 | 认真
需要补的知识漏洞 | 无！

## 7 月 22 日

### 题单（去重后 7 题）

来源 | 题号 / 题名（全部可点）
--- | ---
作业 | 3105 【模板】树的直径
作业 | P14D Two Paths
作业 | P3629 [APIO2010] 巡逻
作业 | P1395 会议
作业 | P3379 【模板】最近公共祖先（LCA）
作业 | P4281 [AHOI2008] 紧急集合 / 聚会
作业 | P3128 [USACO15DEC] Max Flow P

### 知识点

- 树的直径两遍 DFS/BFS 就够：任取一点找到最远点 $s$，再从 $s$ 找最远点 $t$。
- LCA 用的是 Tarjan 离线算法：DFS 回溯时把儿子所在集合并到父亲；查询另一端已经访问过，就用并查集祖先得到 LCA。总复杂度接近 $O((n+m)\alpha(n))$。
- 多条路径统计经过次数，先做树上差分：点差分与边差分的加减位置不同，最后一次后序 DFS 汇总。

### Code

P3379 最近公共祖先（LCA）

    int find(int u) {
        if (u == fa[u])
            return u;
        return fa[u] = find(fa[u]);
    }
    void tarjan(int u) {
        vis[u] = 1;
        for (int v : e[u]) {
            if (!vis[v]) {
                tarjan(v);
                fa[v] = u;
            }
        }
        for (PII q : qry[u]) {
            int v = q.fi, i = q.se;
            if (vis[v])
                ans[i] = find(v);
        }
    }

## 7 月 23 日

### 题单（去重后 8 题）

来源 | 题号 / 题名（全部可点）
--- | ---
比赛 + 订正作业 | A 求和 · P8772 求和（订正）
比赛 + 订正作业 | B 拜年 · P5764 拜年（订正）
比赛 + 订正作业 | C 最大生成树 · P9488 最大生成树（订正）
比赛 + 订正作业 | D 序列操作 · P11208 序列操作（订正）
比赛 + 订正作业 | E 摆靶子 · P4388 摆靶子（订正）
比赛 | F 树
比赛 | G 简单的询问
比赛 | H 砝码称重

### 知识点

- 求和用累加降维，把双重枚举从 $O(n^2)$ 降到 $O(n)$，而且答案要用 `long long`。
- 拜年只有 5 个目标点：从起点和 5 个目标各跑一次 Dijkstra，得到 6 个关键点之间的距离，再枚举 $5!$ 种访问顺序。
- 最大生成树题不必建 $O(n^2)$ 条边，先筛最小质因数，按结构直接连边；线性筛能把预处理做到 $O(n)$。
- 序列操作把答案写成“删掉多少个 + 剩余逆序对数”，逆序对用树状数组统计，再利用删除顺序的单调性做前后缀贡献。
- 摆靶子先得到 $f(R,C)=\gcd(R,C)\,f(R/g,C/g)$，互质时 $f(R,C)=R+C-1$；计数进一步落到欧拉函数和约数枚举。
- 简单的询问先定义二维前缀答案 $F(x,y)=\sum_v cnt(v,[1,x])cnt(v,[1,y])$。原询问用四项容斥：$F(r_1,r_2)-F(l_1-1,r_2)-F(r_1,l_2-1)+F(l_1-1,l_2-1)$；再把四倍询问按 $(x,y)$ 跑二维莫队。移动两个指针时用 `cnt1`、`cnt2` 维护两段前缀中每个值的出现次数，当前答案就是 $\sum_v cnt1[v]cnt2[v]$，复杂度约 $O((n+q)\sqrt n)$。

### Code

A 求和

    	int t = 0;
    	for(int i = n;i >= 1;i--){
    		t += x[i] * cnt;
    		cnt += x[i];
    	}
    	cout << t;

B 拜年

        for(int i = 0; i < 6; i++) {
            dijkstra(p[i], i);
        }

        int a[5] = {1, 2, 3, 4, 5};
        int ans = INF;

        do {
            int sum = d[0][a[0]];

            for(int i = 1; i < 5; i++) {
                sum += d[a[i - 1]][a[i]];
            }

            ans = min(ans, sum);
        } while(next_permutation(a, a + 5));

C 最大生成树

        for(int i = n / 2;i >= 1;i--){
            int x = find(i);

            for(int j = 1;j <= cnt and prime[j] <= n / i;j++){
                int y = find(i * prime[j]);

                if(x == y) continue;

                fa[y] = x;
                ans += i;
            }
        }

D 序列操作

        int sum = 0;

        for(int i = 1;i <= n;i++){
            if(p[i] < n){
    		    sum += qry(rt1, 1, n, p[i] + 1, n);
    		}
            mdy(rt1, 1, n, p[i], 1);
        }

        for(int i = 1;i <= n;i++){
            mdy(rt2, 1, n, i, 1);
        }

        int ans = sum;

        for(int x = 1;x <= n;x++){
            int cnt = 0;
    		if(pos[x] > 1) cnt = qry(rt2, 1, n, 1, pos[x] - 1);

            sum -= cnt;
    //        cout << x << ' ' << cnt << ' ' << sum << '\n';
            mdy(rt2, 1, n, pos[x], -1);

            ans = min(ans, x + sum);
        }

E 摆靶子

    int calc(int k) {
        if(k == 1) return 1;
        return phi[k + 1] / 2;
    }

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

        cin >> n;

        init(n + 1);

        int ans = 0;

        for(int i = 1;i <= n / i;i++) {
            if(n % i != 0) continue;

            ans += calc(i);

            if(i != n / i) {
                ans += calc(n / i);
            }
        }

G 简单的询问

    void add1(int p) {
        anss += cnt2[a[p]];
        cnt1[a[p]]++;
    }

    void del1(int p) {
        cnt1[a[p]]--;
        anss -= cnt2[a[p]];
    }

    void add2(int p) {
        anss += cnt1[a[p]];
        cnt2[a[p]]++;
    }

    void del2(int p) {
        cnt2[a[p]]--;
        anss -= cnt1[a[p]];
    }

        cin >> q;
        for (int i = 1; i <= q; i++) {
            int l1, r1, l2, r2;
            cin >> l1 >> r1 >> l2 >> r2;

            add_query(r1, r2, i, 1);
            add_query(l1 - 1, r2, i, -1);
            add_query(r1, l2 - 1, i, -1);
            add_query(l1 - 1, l2 - 1, i, 1);
        }

        sort(e + 1, e + tot + 1, cmp);

        int nowl = 0, nowr = 0;

        for (int i = 1; i <= tot; i++) {
            int l = e[i].l, r = e[i].r;

            while (nowl < l) add1(++nowl);
            while (nowl > l) del1(nowl--);
            while (nowr < r) add2(++nowr);
            while (nowr > r) del2(nowr--);

            ans[e[i].id] += e[i].k * anss;
        }

### 20260723周赛：复盘

题目顺序：T1 = A 求和；T2 = B 拜年；T3 = C 最大生成树；T4 = D 序列操作；T5 = E 摆靶子；T6 = F 树；T7 = G 简单的询问；T8 = H 砝码称重

项目 | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8
--- | --- | --- | --- | --- | --- | --- | --- | ---
涉及算法标签 | 模拟 | Dijkstra+全排列 | 并查集+欧拉筛+推导 | 线段树优化模拟（？） | 数学推导+phi函数 | - | 莫队+二维前缀和 | -
得分 | 100 | 100 | 100 | 100 | 0 | 0 | 0 | 0
错误原因 | - | - | - | - | □ 时间不够 | □ 时间不够 | □ 时间不够 | □ 时间不够
正确解法核心 | 同上 | 同上 | 同上 | 同上 | 同上 | - | 同上 | -
以前做过的同类型题 | 无所谓，， | 非负权单源最短路 | 【并查集】亲戚 + 再求素数 | 逆序对 | Longge 的问题 | - | 小B的询问 | -
今天最大的教训 | 不要死磕一道题不看后面的题，尤其是IOI赛制!
需要补的知识漏洞 | 换根DP??