黑大帅的动态

记录与收藏都在这里。

粉丝 1

优质贡献者 I初来乍到

动态

精华

和式的操作：从分配律到多重求和，一篇讲清常见变形技巧

黑大帅 2026-4-15 16:22:09

和式的操作：从分配律到多重求和，一篇讲清常见变形技巧很多同学一见到和式，就习惯“直接算”。
但实际上，和式真正厉害的地方，从来都不是硬算，而是变形。你可以把它理解成：
求和不是结束计算，而是开始操作。这篇文章就系统整理一下和式处理中最常见、最实用的一些方法：

和式的三大基本法则

等差和的经典推导

用指标函数描述“求和范围”

二重和式与换序

三角区域求和

扰动法与构造法

一个经典恒等式的推导

调和和式的二维转一维技巧

希望看完之后，你再遇到复杂求和，不会只想着“暴力展开”，而是能想到：这个式子能不能变一下？一、和式的三大基本操作和式最基础的三个法则，其实就是你熟悉的加法和乘法在“求和符号”下的延续：1. 分配律

\sum_{k\in K} c a_k = c \sum_{k\in K} a_k

这表示常数可以直接提出求和号。本质上就是：

ca_1+ca_2+\cdots+ca_n = c(a_1+a_2+\cdots+a_n)

2. 结合律这说明如果每一项本身是“两个量的和”，那么可以拆成两个和式分别算。这在做式子拆分时非常常见，尤其是遇到：

多项式

差分

递推展开

多重和式中的被加数拆分

3. 交换律（重排）

\sum_{k\in K} a_k = \sum_{p(k)\in K} a_{p(k)}

其中

p(k)

表示对下标做一个排列。意思很简单：
有限和式里，求和顺序不影响结果。这条性质在很多技巧里都非常关键，比如：

倒序求和

换元

枚举顺序改变

二重和式换序

二、等差和公式，其实就是“把和式倒过来”考虑最经典的和式：

S=\sum_{0\le k\le n}(a+bk)

也就是：

S=a+(a+b)+(a+2b)+\cdots+(a+nb)

这是一个等差数列求和。但它的经典推导，不是背公式，而是用“倒序重排”。把它倒着写：

S=\sum_{0\le n-k\le n}(a+b(n-k))

也就是：

S=\sum_{0\le k\le n}(a+bn-bk)

现在把两个

S

相加：

2S=\sum_{0\le k\le n}\bigl((a+bk)+(a+bn-bk)\bigr)

中间的

bk

与

-bk

抵消，于是得到：

2S=\sum_{0\le k\le n}(2a+bn)

因为

2a+bn

是常量，可以提出：

2S=(2a+bn)\sum_{0\le k\le n}1

而

\sum_{0\le k\le n}1=n+1

所以

2S=(2a+bn)(n+1)

最后得到：这就是等差数列求和公式。这个推导的本质是什么？不是“神奇配对”，而是两件事：

有限和式可以重排

两个和式可以逐项合并

这就是和式操作的威力。三、用集合和指标函数来描述求和范围很多时候，真正麻烦的不是“求和内容”，而是“求和范围”。比如：

只对偶数下标求和

只对满足某些条件的下标求和

两个集合相加、交、并的关系

这时候，一个非常好用的工具是指标函数。1. 指标函数写法

[k\in K]

表示一个逻辑值：

若 $k\in K$ ，取 $1$

若 $k\notin K$ ，取 $0$

于是我们可以把“只在集合

K

上求和”写成：

\sum_{k\in K} a_k = \sum_k a_k [k\in K]

这个式子非常重要。
它的意义是：

与其说“只对 $K$ 里的项求和”，不如说“对所有项求和，但不在 $K$ 里的那些项系数为 0”。

这一步，会让很多集合问题变成代数问题。2. 一个非常有用的恒等式如果

K,K'

是两个集合，那么有：这其实就是集合版的“容斥”。为什么对？因为对于任意一个

k

，它在左右两边被计算的次数完全一样。更本质地说，就是逻辑恒等式：3. 一个简单应用比如：

\sum_{k=1}^{m}a_k+\sum_{k=m}^{n}a_k

注意中间的

a_m

被算了两次，所以：这就是集合重叠导致的“多算一次”。四、多重和式：像多重循环一样去理解很多人一看到二重和式就发怵，其实你可以把它理解成程序里的二重循环。比如：

\sum_{j}\sum_{k} a_{j,k}

就是：

外层枚举 $j$

内层枚举 $k$

把 $a_{j,k}$ 全加起来

所以多重和式的核心问题通常有两个：

循环顺序能不能交换？

求和范围能不能拆开？

1. 无关变量可以分离如果

j

与

k

独立，并且被加数刚好是乘积形式

a_jb_k

，那么：这在竞赛里太常用了。本质原因是：

对固定的 $j$ ， $a_j$ 是常量

对固定的 $k$ ， $b_k$ 是常量

所以就能一步一步提出去。这可以理解成二维矩阵中，每个格子是

a_jb_k

，把整个矩阵所有格子求和，等于按列求和再乘，或按行求和再乘。2. 二重和式可以换序如果枚举区域不变，那么：

\sum_j\sum_k a_{j,k} = \sum_k\sum_j a_{j,k}

这就相当于：

原来按行扫描矩阵

现在按列扫描矩阵

只要区域一样，总和当然一样。五、三角区域求和：换序时要先看清区域多重和式最容易出错的地方，不是公式，而是范围。比如：

\sum_{j=1}^{n}\sum_{k=j}^{n} a_{j,k}

这表示：

$j$ 从 1 到 $n$

对每个 $j$ ， $k$ 从 $j$ 到 $n$

也就是满足

1\le j\le k\le n

的所有点。所以它也可以写成：

\sum_{1\le j\le k\le n} a_{j,k}

而如果换成先枚举

k

，那么对固定的

k

，

j

可以从

1

到

k

，于是：这个式子非常重要。经验看到二重和式，先别急着换序。
先把范围写成一个逻辑条件，比如：1\

187 浏览0 点赞0 收藏0 评论

202603七级

黑大帅 2026-3-14 19:57:39

T1 题目题目描述若求

\prod_{i=1}^{k} a_i

的最大值。输入格式第一行输入整数

T \quad (1 \le T \le 10^4)

表示测试组数。接下来

T

行，每行输入一个整数

n

。输出格式输出

T

行。每行输出最大乘积

\prod_{i=1}^{k} a_i \bmod 10^9

数据范围

40% 数据： $1 \le n \le 50$

所有数据： $1 \le n \le 10^6$

题解这是一个非常经典的问题：整数拆分最大乘积即：

把 $n$ 拆成若干正整数，使乘积最大。

40 分 DP / 完全背包做法因为

n \le 50

，每次

O(n^2)

就够了。40 分做法可用完全背包。设

dp[i]

表示和为

i

时的最大乘积。把每个正整数

x

看作一种可无限选取的物品，体积为

x

，收益为乘法因子

x

。转移为

dp[s]=\max(dp[s],dp[s-x]\times x)

初值

dp[0]=1

，最终输出

dp[n]

。把每个正整数

x

看成一种“物品”：

体积 = $x$

价值不是加法，而是乘法中的一个因子 $x$

我们希望选若干个物品，使总体积恰好为

n

，并让这些数的乘积最大。因为每个数可以取任意次，所以这本质上就是完全背包。这就是一个“恰好装满”的完全背包，只不过普通背包是“价值相加”，这里变成了“乘积最大”。如果直接这样写，那么对于

n=2

：

不拆：2

拆：1+1，乘积 1

题目要求是“若

S=\sum_{0\le n-k\le n}(a+b(n-k))

1\le k\le n

”
其实是允许

k=1

的，也就是允许不拆。那么最终答案就是：

dp[n]

并且转移时把

j=i

也允许即可。代码（完全背包写法）#include<bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 1e9; int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--) { int n; cin >> n; ll dp[55]; for(int i = 0; i <= n; i++) dp[i] = 0; dp[0] = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= i; j++) { dp[i] = max(dp[i], dp[i - j] * j); } } cout << dp[n] % mod << "\n"; } return 0; }为什么这就是完全背包因为：

每个整数 $x$ 都可以选很多次

每次选一个 $x$ ，就相当于消耗容量 $x$

最终总和恰好要到 $n$

这和完全背包“每种物品无限件”完全一致。只不过普通背包是：

dp[s]=\max(dp[s],dp[s-x]+v)

这题变成：

dp[s]=\max(dp[s],dp[s-x]\times x)

所以本质没变，只是“加法价值”换成了“乘法价值”。复杂度每组数据：

O(n^2)

在

n \le 50

时非常轻松。满分做法最优策略是：尽量拆成 3至于为什么，证明可以去以下这篇文章去看数学结论：当

n ≥ 5

时

3 \times (n-3) > n

说明拆出 3 会更优。分类讨论情况1：n % 3 = 0全部拆成3

3^{n/3}

情况2：n % 3 = 1例如：10 = 3 + 3 + 3 + 1但3 + 1 = 4更优：3 + 3 + 4所以

3^{(n/3-1)} \times 4

情况3：n % 3 = 2直接多一个2

3^{n/3} \times 2

特殊情况n = 1 → 1 n = 2 → 1 n = 3 → 2时间复杂度每个查询

O(\log n)

快速幂即可。T1 参考代码#include<bits/stdc++.h> using namespace std; using ll = long long; const ll mod = 1e9; ll ksm(ll a,ll b) { ll r = 1; while(b) { if(b&1) r = r * a % mod; a = a * a % mod; b >>= 1; } return r; } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while(T--) { ll n; cin >> n; if(n==1) cout<<1<<"\n"; else if(n==2) cout<<2<<"\n"; else if(n==3) cout<<3<<"\n"; else { ll a = n/3; ll b = n%3; if(b==0) cout<<ksm(3,a)<<"\n"; else if(b==1) cout<<ksm(3,a-1)*4%mod<<"\n"; else cout<<ksm(3,a)*2%mod<<"\n"; } } }T2 题目题目描述有

n

个城市，编号

1 \sim n

。有

m

条无向公路。每条公路有：

费用 $w_i$

风景好看度 $b_i$

汽车要从 1 号城市到 n 号城市。规则：可以 免去路径上一条风景好看度最高的公路费用
（如果有多条同样最高，只能免去一条）。求 最小总费用。若无法到达，输出-1输入格式第一行n m接下来

m

行u v w_i b_i表示一条连接

u,v

的无向边

费用 $w_i$

风景值 $b_i$

输出格式输出从

1

到

n

的最小费用。数据范围

1 \le n,m \le 5000

1 \le w_i,b_i \le 10^9

T2 题解这题难点不在最短路本身，而在于：

99 浏览1 点赞0 收藏0 评论

USACO-26-1-铜组

黑大帅 2026-1-10 8:32:55

T1 chip change题目描述奶牛 Bessie 手里有 A 个 A 类筹码，以及 B 个 B 类筹码（

0\le A,B\le 10^9

）。她可以进行如下操作任意多次：

如果当前 至少有 $c_B$ 个 B 类筹码，就可以用 $c_B$ 个 B 类筹码兑换 $c_A$ 个 A 类筹码。
其中

1\le c_A,c_B\le 10^9

。

现在问：最小的非负整数

x

是多少，使得满足下面的“保证”条件：

在 Bessie 额外收到 $x$ 个随机筹码之后（每个筹码可能是 A 类或 B 类，分配方式未知），无论这 $x$ 个筹码具体怎么分配成 A/B，Bessie 都一定能通过若干次兑换操作，使得最终拥有的 A 类筹码数量 至少为 $f_A$ （ $0\le f_A\le 10^9$ ）。

你需要对每个测试用例输出这个最小的

x

。输入格式第一行是整数

T

，表示测试用例个数（

1\le T\le 10^4

）。接下来

T

行，每行包含 5 个整数：

A,\ B,\ c_A,\ c_B,\ f_A

输出格式对每个测试用例输出一行一个整数：对应的答案

x

。

注意：数据范围很大，可能需要 64 位整数类型（例如 C/C++ 的 long long）。

样例样例输入1:2 2 3 1 1 6 2 3 1 1 4样例输出1:1 0样例输入1:5 0 0 2 3 5 0 1 2 3 5 1 0 2 3 5 10 10 2 3 5 0 0 1 1000000000 1000000000样例输出2:9 8 7 0 1000000000000000000并解释（原文意思）：

第 1 组（ $A=B=0,c_A=2,c_B=3,f_A=5$ ）：
Bessie 一开始没有筹码。只要她额外收到任意 9 个筹码，不管这 9 个里 A/B 怎么分配，她都能通过兑换最终得到至少 5 个 A。
比如她收到 2 个 A 和 7 个 B，可以兑换两次得到 6 个 A（ $\ge 5$ ）。
但如果只收到 8 个 B，则最多兑换 2 次得到 4 个 A（<5），所以 8 不够。

第 4 组：她一开始就已经有足够多的 A，因此答案是 0。

评分提示

输入 3：

c_A=c_B=1

输入 4-5：所有用例的

x\le 10

输入 6-7：

c_A=2, c_B=3

输入 8-12：无额外限制

参考代码#include <bits/stdc++.h> using namespace std; using ll = long long; using i128 = __int128; ll a, b, ca, cb, fa; i128 cal(ll y, ll tot) { return (i128)tot - y + ((i128)y / cb) * ca; } bool chk(ll x) { ll tot = a + b + x; ll lim = b + x; i128 mn = cal(lim, tot); ll tg = cb - 1; if (ca > cb) { ll r = b % cb; ll d = (tg - r + cb) % cb; ll y = b + d; if (y <= lim) mn = min(mn, cal(y, tot)); } else { ll r = lim % cb; ll d = (r - tg + cb) % cb; ll y = lim - d; if (y >= b) mn = min(mn, cal(y, tot)); } return mn >= fa; } void sol() { cin >> a >> b >> ca >> cb >> fa; ll l = 0, r = 2e18, ans = 2e18; while (l <= r) { ll md = l + (r - l) / 2; if (chk(md)) { ans = md; r = md - 1; } else { l = md + 1; } } cout << ans << "\n"; } int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t; cin >> t; while (t--) { sol(); } return 0; }T2 COW题目描述Bessie 得到一个正整数

N

和一个长度为

3N

的字符串

S

。字符串

S

的生成方式如下：把

N

个长度为 3 的字符串拼接起来，而每个长度为 3 的字符串都是 "COW" 的一个循环移位（cyclic shift），也就是说每段只能是下面三种之一：

"COW"

"OWC"

"WCO"

平方串（square string）字符串

X

被称为 平方串，当且仅当存在某个字符串

Y

，使得：

X = Y + Y

其中

+

表示字符串拼接。例如：

"COWCOW"、"CC" 是平方串（分别对应 $Y="COW"$ 、 $Y="C"$ ）

"COWO"、"OC" 不是平方串

操作一次操作中，Bessie 可以从

S

中删除任意一个子序列

T

，要求

T

是一个平方串。子序列指：从原串中删除若干个字符（可以删除 0 个），保持剩余字符的相对顺序得到的字符串。目标你需要判断：是否可以通过若干次操作，把

S

变成空串。如果可以，还要输出一种删除方案。参数

k

与操作次数要求题目还给一个参数

k\in\{0,1\}

。设你输出的方案使用了

M

次操作。

若

k=0

：必须保证

M

等于最少可能操作次数（最优）。

若

k=1

：允许

M

最多为 最少操作次数 + 1（几乎最优，多一次也行）。

输入格式第一行包含两个整数：

T

：测试组数（

1\le T\le 10^4

）

k

：参数（

0\le k\le 1

）

每个测试用例包含：

一行整数

N

（

1\le N\le 10^5

）

一行字符串

S

，长度为

3N

保证所有测试中

N

的总和不超过

10^5

。输出格式对每个测试用例，按如下方式输出：

如果无法把 $S$ 变成空串：输出一行 -1

否则：

第一行输出 $M$ ：你的方案操作次数
第二行输出 $3N$ 个整数，用空格分隔
第 $i$ 个整数 $x_i$ 表示：原串 $S$ 的第 $i$ 个字符是在第 $x_i$ 次操作中被删除的（要求 $1\le x_i\le M$ ）

样例样例输入13 1 3 COWOWCWCO 4 WCOCOWWCOCOW 6 COWCOWOWCOWCOWCOWC样例输出1-1 1 1 1 1 1 1 1 1 1 1 1 1 1 3 3 3 2 3 3 2 1 1 1 1 1 1 1 1 1 1 1 1样例解释1

对于最后一个测试用例，最优（最少）操作次数是 2，因此当 $k=1$ 时，只要你的构造满足 $M=2$ 或 $1 \le n,m \le 5000$ 都会被判正确（允许比最优多 1 次）。

如果取 $M=3$ ，下面给出一种可行方案：

第一次操作：删除最后 12 个字符。此时剩下字符串为 COWCOW。
第二次操作：删除子序列 WW。此时剩下字符串为 COCO。
第三次操作：删除所有剩余字符。最终变成空串。

124 浏览1 点赞0 收藏0 评论

基础语法训练大纲

黑大帅 2026-1-7 14:39:49

语法A训练大纲

大标题

小标题

核心考察知识点训练

顺序结构

OJ使用与输出

流输出，OJ评测与反馈机制

变量、常量与输入

const 修饰符，常量后缀（011），流输入

基本运算与类型转换

显示与隐式转换，强制类型转换，整数运算，小数运算，字符与 ASCII 码值，上取整：a / b → (a + b − 1) / b；四舍五入取整：a / b → (a + b / 2) / b；

分支结构

if语句

独立判断逻辑，互斥多路分类讨论

if…else语句

if…else if … else语句

switch…case语句

三元表达式

循环结构：while循环 / for循环 / do…while循环

顺序输出

基础循环枚举顺序输出，for/while 基本结构；控制步长；打印格式

倒序输出

倒序输出，逆向循环；边界（>= / >）；反向遍历

指定范围枚举

枚举指定范围：区间枚举模板，包含/不包含端点；步长枚举

while循环变化过程

while 变化过程：循环不变量，终止条件；调试观察（变量变化轨迹）

求和问题

求和累加，条件累加器，筛选求和；避免重复统计

计数器

计数：计数变量设计，分支内计数，多类计数

累乘

累乘：连乘；溢出意识

求最值

求最值：枚举范围求最值，最值更新条件；条件范围最值

标记法可行性与可行解

标记法（标志变量）→ 枚举可行解（可行性问题）

基础数学问题

质数判断，最大公约数，最小公倍数朴素计算，枚举因数对，根号优化

循环嵌套

枚举入门：双重循环结构；计数/求和/最值在嵌套中的位置

枚举排列：三层/多层枚举；去重条件；排列性质

枚举组合：递增下标控制（i<j<k）；组合计数

枚举进阶：剪枝；数学优化；枚举对象优化；贡献计算思想

一维数组基础1

基本存储与IO

一维数组读写，下标习惯，边界与容量

找元素

线性查找：第一次/最后一次出现（基础）

找最值（打擂台）

最值查找，最值位置，最值首次位置，最值末次位置

数组计数

频次统计；桶思想；值域分析

标记数组

存在性标记；去重；简单筛法雏形

元素移动

数组增删改查元素

连续性元素

连续段统计；最长连续；区间判断

大标题	小标题	核心考察知识点训练
顺序结构	OJ使用与输出	流输出，OJ评测与反馈机制
变量、常量与输入	const 修饰符，常量后缀（011），流输入
基本运算与类型转换	显示与隐式转换，强制类型转换，整数运算，小数运算，字符与 ASCII 码值，上取整：a / b → (a + b − 1) / b；四舍五入取整：a / b → (a + b / 2) / b；
分支结构	if语句	独立判断逻辑，互斥多路分类讨论
if…else语句
if…else if … else语句
switch…case语句
三元表达式
循环结构：while循环 / for循环 / do…while循环	顺序输出	基础循环枚举顺序输出，for/while 基本结构；控制步长；打印格式
倒序输出	倒序输出，逆向循环；边界（>= / >）；反向遍历
指定范围枚举	枚举指定范围：区间枚举模板，包含/不包含端点；步长枚举
while循环变化过程	while 变化过程：循环不变量，终止条件；调试观察（变量变化轨迹）
求和问题	求和累加，条件累加器，筛选求和；避免重复统计
计数器	计数：计数变量设计，分支内计数，多类计数
累乘	累乘：连乘；溢出意识
求最值	求最值：枚举范围求最值，最值更新条件；条件范围最值
标记法可行性与可行解	标记法（标志变量）→ 枚举可行解（可行性问题）
基础数学问题	质数判断，最大公约数，最小公倍数朴素计算，枚举因数对，根号优化
循环嵌套	枚举入门：双重循环结构；计数/求和/最值在嵌套中的位置
枚举排列：三层/多层枚举；去重条件；排列性质
枚举组合：递增下标控制（i<j<k）；组合计数
枚举进阶：剪枝；数学优化；枚举对象优化；贡献计算思想
一维数组基础1	基本存储与IO	一维数组读写，下标习惯，边界与容量
找元素	线性查找：第一次/最后一次出现（基础）
找最值（打擂台）	最值查找，最值位置，最值首次位置，最值末次位置
数组计数	频次统计；桶思想；值域分析
标记数组	存在性标记；去重；简单筛法雏形
元素移动	数组增删改查元素
连续性元素	连续段统计；最长连续；区间判断

121 浏览1 点赞0 收藏0 评论

划分DP

黑大帅 2025-9-17 1:25:49

划分DP划分型动态规划（划分DP）是一种处理特定类型问题的动态规划方法，常用于解决需要将数据结构（如数组、字符串等）划分成若干部分以优化某些目标函数的问题。这类动态规划问题的关键在于找到合适的状态表示和状态转移方程。下面是划分的

DP

一些常见做法：主要分为两种类型：

\color{red}\text{1、确定段数的划分}

\color{blue}\text{1.定义状态}

首先定义动态规划的状态：通常表示为

dp[i][j]

，其中

i

表示数据结构的某个终点（或起点），

j

可能表示划分的段数、划分的方式或其他根据问题需要定义的参数。

\color{blue}\text{2. 状态转移方程}

状态转移是动态规划的核心，需要找到从之前的状态到当前状态的转移方法。对于划分型DP，状态转移方程通常涉及枚举分割点或分割方式，从而将原问题分解为更小的子问题。形式上可能是这样的：$ dp[i][j] = \min 或 \max \{dp[k][j-1] + cost(k, i)\}，其中 k < i。 $这里

cost(k, i)

表示从

k

到

i

划分的代价，根据实际问题的需求，可以是求和、求最大值、求最小值等操作。

\color{blue}\text{3. 初始化}

合理的初始化是动态规划成功的关键。一般而言，

dp[0][0]

或

dp[i][0]

（根据问题定义而定）是比较容易确定的基础状态。有时候可能需要对

DP

数组进行特殊的初始化来适配边界条件。

\color{blue}\text{4. 计算顺序}

决定动态规划的计算顺序，是从小到大（自底向上）还是从大到小（自顶向下），以确保在计算当前状态时，所有需要的前置状态都已被计算。

\color{blue}\text{5. 答案提取}

根据问题的要求，最终的答案可能在中，也可能需要遍历

DP

表的某一行或某一列来找到答案，其中

n

和

m

分别代表数据结构的大小和问题中的其他参数。

n

数组分割问题：给定一个数组，将其分割为

k

个连续的子数组，使得这

k

个子数组的最大和最小。

字符串编辑问题：给定一个字符串，通过分割成若干部分，并对每一部分进行编辑（如反转、替换）来达到某个目标。

任务调度问题：将

N

个任务分配给

K

个机器处理，每个任务只能分配给一个机器，如何分配以最小化总完成时间或最大化利润。

划分型DP的关键在于理解如何将大问题划分为小问题，并通过动态规划表来优雅地解决这些小问题。每种类型的问题都有其独特之处，因此在实践中需要根据问题的具体情况来调整DP的定义和转移方程。

\color{red}\text{2、不确定段数的划分}

\color{blue}\text{1) 通用模板（枚举最后一段）}

状态： $dp[i]$ 表示前 $i$ 个元素被划成若干段后的最优值（最小/最大看题意）。

转移（不可取空段）：

初始化：

极小化： $dp[0]=0$ ，其余设为 $+\infty$ ；
极大化： $dp[0]=0$ ，其余设为 $-\infty$ 。

方案恢复：用 pre[i]=argmin/argmax k 回溯即可。

关键点：把“合法段”的判定（长度区间、区间和上界、max-min 上界等）嵌入到候选 $k$ 的集合定义里，只在合法 $k$ 上取最优。

\color{blue}\text{2) 常见目标类型与套路}

\color{purple}A.

最小化“各段代价之和”

形式： $\mathrm{segCost}(l,r)$ 给定，目标 $\min\sum \mathrm{segCost}$ 。

朴素： $O(n^2)$ 枚举 $k$ 。

优化 1（长度窗 + 区间最小）：若只允许段长 $L\le r-l+1 \le R$ ，

$$dp[i]=\min_{k\in[i-R,\,i-L]} \{ dp[k] + \mathrm{segCost}(k+1,i) \} $$

若 $\mathrm{segCost}$ 只依赖长度或能拆为 $N$ ，可用滑动窗口最小值 / 单调队列 / 线段树把区间最小做成 $O(\log n)$ 或摊还 $O(1)$ 。

优化 2（前缀和 O(1) 算段代价）：若 $\mathrm{segCost}$ 基于区间和/平方和等，预处理 prefix 即可 O(1) 求段代价，整体从 $O(n^2)$ 降到 $O(n^2)$ 的小常数版或配合其他优化进一步降复杂度。

优化 3（凸二次代价 → CHT/Li Chao）：若

\mathrm{segCost}(k+1,i)=(S_i-S_k)^2 + C

则

$$dp[i]=S_i^2 + \min_k \{ dp[k]+C+S_k^2 - 2S_i S_k \} $$

把 $k$ 看成直线 $y = m x + b$ （ $m=-2S_k$ , $b=dp[k]+S_k^2+C$ ），在 $x=S_i$ 处查询最小值，用凸包优化（CHT）/ Li Chao Tree可做到均摊 $O(\log n)$ 。

\color{purple}B.

最少段数（每段需“可行”）

目标：在每段满足约束（如区间和 $3^{n/3} \times 2$ 、max-min $\le D$ ）前提下，最少用多少段覆盖前 $i$ 。

形式：

O(\log n)

两指针 + 维护可行窗口：若可行性关于区间扩张是单调的（如区间和随右端点右移而非降），可用双指针维护最左可行 $L_i$ ，则

dp[i]=1+\min_{k\in[L_i-1,\,i-1]} dp[k]

用队列/多重集/线段树维护区间最小即可 $b_i$ 甚至 $O(n)$ 。

\color{purple}C.

段数-代价联合权衡（拉格朗日/Alien’s Trick）

想“段数不限，但尽量小且总代价也小”，可给每段加罚 $\lambda$ ：

$$f_\lambda[i] = \min_{k<i}\{ f_\lambda[k] + \mathrm{segCost}(k+1,i) + \lambda \} $$

同时维护使用段数 $cnt[i]=cnt[k]+1$ 的最优。

随 $\lambda$ 增大，最优段数单调不增。对 $\lambda$ 二分/三分/步进搜索，即可得到“恰好 $K$ 段”或“至多 $K$ 段”的最优值与方案（常用于把“未知段数”间接转成“控制段数”）。

\color{purple}D.

最大化类（奖励可加）

同理，把

\min

换成

\max

，把不可行段视为

-\infty

即可；优化思路一致。

\color{blue}\text{3) 决策单调性与分治优化（可选）}

若代价函数

w(k,i)

满足四边形不等式/凸性等条件，且最优决策

opt[i]

单调（

opt[i]\le opt[i+1]

），则

dp[i]=\min_{k<i}\{dp[k]+w(k,i)\}

可用分治优化将一层转移从

O(n^2)

降到

O(n\log n)

。
（是否满足条件需按题目 $

100 浏览1 点赞0 收藏0 评论

精华

概率与期望

黑大帅 2025-9-17 1:24:13

概率与期望概率论事件的运算及概率

包含： $0\le A,B\le 10^9$ ，发生 $B$ 时必然发生 $A$ ，发生 $A$ 时不一定发生 $\sum_{k\in K} c a_k = c \sum_{k\in K} a_k$ 。

并（和）事件： $A \cup B = A + B$ ， $A$ 发生或 $B$ 发生或两者都发生。

交（积）事件： $A \cap B = AB$ ， $A$ 和 $B$ 同时发生。

差事件： $A - B = A\overline{B} = A - AB$ ， $A$ 发生但 $B$ 不发生， $\overline{B}$ 表示 $B$ 的对立事件。

互斥事件： $AB=\varnothing$ ， $A$ 和 $B$ 不能同时发生。

对立（逆）事件： $A+\overline{A}=S,\quad A\overline{A}=\varnothing$ ， $A$ 发生时 $\overline{A}$ 不发生， $\overline{A}$ 发生时， $A$ 不发生。

独立事件： $P(AB)=P(A)P(B)$

$A$ 发生与否不影响 $B$ 的概率，反之亦然。

若 $A,B$ 独立，则 $dp[n]$ 、 $\overline{A},B$ 、 $\overline{A},\overline{B}$ 也相互独立。
若 $A,B,C$ $A, B, C$ 相互独立，那么
- $A,B,C$ 两两独立(但逆命题不成立)
- $P(ABC)=P(A)P(B)P(C)$ 。

德摩根律：

$$\overline{A\cup B}=\overline{A}\cap\overline{B}\\ \overline{A\cap B}=\overline{A}\cup\overline{B} $$

加法公式（容斥原理）：
$P(A+B)=P(A)+P(B)-P(AB)$
$x$

减法公式：
$P(A-B)=P(A)-P(AB)$

对立事件概率：
$P(\overline{A})=1-P(A)$

条件概率与乘法公式

条件概率：在 $A$ 已发生下 $B$ 的概率。
$P(B\mid A)=\dfrac{P(AB)}{P(A)}$

乘法公式：
$P(AB)=P(A)P(B\mid A)=P(B)P(A\mid B)$

全概率公式与贝叶斯公式（包括在 NOI 大纲内但大概率 useless）

全概率公式（ $\{B_i\}$ 为完备事件组）：

P(A)=\sum_{i=1}^{n}P(B_i)P(A\mid B_i)

贝叶斯（逆概）公式：

P(B_i\mid A)=\dfrac{P(B_i)P(A\mid B_i)}{P(A)}

离散型随机变量（一维）离散型随机变量是指取值为可列（通常是有限或可数无限）集合中某些具体数值的随机变量。分布列随机变量

X

可取值：

X_1,X_2,\dots,X_k

各取值对应的概率为：

P\{X=X_1\},P\{X=X_2\},\dots,P\{X=X_k\}

分布函数

F(x)=P\{X\le x\}。

重要性质 离散型一维随机变量的分布函数可视为前缀和）：

P\{a\le X\le b\}=F(b)-F(a-1)

。数学期望

E(X)=\sum_{i=1}^{n}x_i p_i

若

Y=g(X)

，则

E(Y)=\sum_{i=1}^{n}g(x_i)p_i

性质：

$E(c)=c,\quad E(ax+c)=aE(X)+c$ 。

$E(X\pm Y)=E(X)\pm E(Y)$

若 $X,Y$ 独立，则 $E(XY)=E(X)E(Y)$ 。

方差

D(X)=E(X^2)-E^2(X)

性质：

D(c)=0,\quad D(aX+b)=a^2D(X)

。

D(x\pm y)=D(x)+D(y)\pm 2\operatorname{Cov}(X,Y)

，其中

\operatorname{Cov}(X,Y)=E(XY)-E(X)E(Y)

为协方差。

若

X,Y

独立，则

\operatorname{Cov}(X,Y)=0

，因此

D(X\pm Y)=D(X)+D(Y)

。

常见分布【0–1 分布（伯努利分布）】进行一次独立试验，成功的概率为

p

，失败的概率为

1-p

。（即

n=1

的二项分布）

记作

分布列

数学期望

方差

X\sim B(1,p)

P\{X=0\}=1-p,\; P\{X=1\}=p

E(X)=p

D(X)=p(1-p)

【二项分布】进行

n

次独立试验，每次成功的概率为

p

，失败的概率为

1-p

。

记作

分布列

数学期望

方差

X\sim B(n,p)

P\{X=k\}=\binom{n}{k}p^k(1-p)^{n-k}

E(X)=np

D(X)=np(1-p)

【几何分布】进行独立试验，直到第一次成功为止；成功的概率为

p

，失败的概率为

1-p

。

记作

分布列

数学期望

方差

X\sim G(p)

P\{X=k\}=(1-p)^{k-1}p

E(X)=\dfrac{1}{p}

D(X)=\dfrac{1-p}{p^2}

【超几何分布】从

N

个物体中抽取

n

个物体，其中有

K

个是成功的，

N-K

个是失败的。

记作

分布列

数学期望

方差

X\sim H(N,K,n)

$P\{X=k\}=\dfrac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$

E(X)=\dfrac{nK}{N}

D(X)=\dfrac{nK(N-K)(N-n)}{N^2(N-1)}

概率与期望 DP与组合数 DP 类似，只是在 DP 转移时结合概率或期望的计算。常见有后效性方程，需要移项或高斯消元处理。【例题 1】Jerry's Protest（纯概率论应用）#include <bits/stdc++.h> using namespace std; using ll = long long; int main(){ ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin>>n; vector<int> a(n); for(i

记作	分布列	数学期望	方差
$X\sim B(1,p)$	$P\{X=0\}=1-p,\; P\{X=1\}=p$	$E(X)=p$	$D(X)=p(1-p)$

记作	分布列	数学期望	方差
$X\sim B(n,p)$	$P\{X=k\}=\binom{n}{k}p^k(1-p)^{n-k}$	$E(X)=np$	$D(X)=np(1-p)$

记作	分布列	数学期望	方差
$X\sim G(p)$	$P\{X=k\}=(1-p)^{k-1}p$	$E(X)=\dfrac{1}{p}$	$D(X)=\dfrac{1-p}{p^2}$

记作	分布列	数学期望	方差
$X\sim H(N,K,n)$	$P\{X=k\}=\dfrac{\binom{K}{k}\binom{N-K}{n-k}}{\binom{N}{n}}$	$E(X)=\dfrac{nK}{N}$	$D(X)=\dfrac{nK(N-K)(N-n)}{N^2(N-1)}$

137 浏览1 点赞0 收藏0 评论

DTZS-Round1-T5-数阵查询

黑大帅 2025-5-6 20:05:03

解析首先看到题目我们可以发现，或者应该要发现，变化

DP

次的这个矩阵的规模是多大；根据题意的变化规律：

当前有数字的方阵填充成

2 \times 2

的大方阵：

在其方阵的右边界和下边界填上当前数阵没有的最小正整数。

不难发现，每多变化一次，规模是

\times 2 + 1

的,所以显然可以得到递推式：记

d_i

为变化

i

次的规模，初始条件

d_0

= 1递推式：

d_i = d_{i - 1} \times 2 + 1

然后思考什么情况下是无解的呢？不难发现，当前给的

A - B = A\overline{B} = A - AB

是超出变化

n

次的规模的，显然是无解的直接输出

-1 \quad -1

;那么对于有解的情况怎么思考呢？有解的情况可以分为两类：

如果 $x,y$ 刚好处于当前变化的这一层的边界上，那么答案就是 $n + 1$

也就是以下情况：

2.如果

x,y

不处于当前变化的这一层的边界上也就是以下情况的其中一种：

不难发现，我们其实都可以把

x,y

映射到

A

区域去，因为

n \le 50

三个区域是由A区域变化过来的；所以如果处于A区域，不需要变化；如果不处于，直接做映射,然后发现，将

x,y

映射到

A

区域，其实就是找到变化次数少一次的对应的位置；这个时候，我们就不难想到递归了，将当前

x,y

转移传递到上一层的对应的节点的位置设映射后的位置为

x',y'

处于

D

区域

\rightarrow

A

x' = x - d_{n - 1},y' = y - d_{n - 1}

处于

C

区域

\rightarrow

A

x' = x - d_{n - 1},y' = y

处于

B

区域

\rightarrow

A

1\le k\le n

处于

A

区域

S

A

x' = x ,y' = y

然后规模缩小一层，变成大问题的子问题，直接递归即可参考代码#include<bits/stdc++.h> using namespace std; using ll = long long; ll b[45]; ll work(ll n , ll x , ll y){ if(x > b[n] || y > b[n]) return -1; if(x == b[n] || y == b[n]) return n + 1; ll x1 = x , y1 = y; if(x > b[n-1]) x1 = x-b[n-1]; if(y > b[n-1]) y1 = y-b[n-1]; return work(n-1,x1,y1); } int main(){ b[0] = 1; b[1] = 3; for(int i = 2;i <= 20;i++){ b[i] = b[i-1] * 2 + 1; } int t; cin >> t; while(t--){ ll n,x,y; cin >> n >> x >> y; cout << work(n,x,y) << "\n"; } return 0; }

104 浏览1 点赞0 收藏0 评论

黑大帅 的动态

和式的操作：从分配律到多重求和，一篇讲清常见变形技巧

和式的操作：从分配律到多重求和，一篇讲清常见变形技巧

一、和式的三大基本操作

1. 分配律

2. 结合律

3. 交换律（重排）

二、等差和公式，其实就是“把和式倒过来”

这个推导的本质是什么？

三、用集合和指标函数来描述求和范围

1. 指标函数写法

2. 一个非常有用的恒等式

3. 一个简单应用

四、多重和式：像多重循环一样去理解

1. 无关变量可以分离

2. 二重和式可以换序

五、三角区域求和：换序时要先看清区域

经验

202603七级

T1 题目

题目描述

输入格式

输出格式

数据范围

题解

40 分 DP / 完全背包做法

代码（完全背包写法）

复杂度

满分做法

分类讨论

情况1：n % 3 = 0

情况2：n % 3 = 1

情况3：n % 3 = 2

特殊情况

时间复杂度

T1 参考代码

T2 题目

题目描述

输入格式

输出格式

数据范围

T2 题解

USACO-26-1-铜组

T1 chip change

题目描述

输入格式

输出格式

样例

样例输入1:

样例输出1:

样例输入1:

样例输出2:

评分提示

参考代码

T2 COW

题目描述

平方串（square string）

操作

目标

参数 kkk 与操作次数要求

输入格式

输出格式

样例

样例输入1

样例输出1

样例解释1

基础语法训练大纲

语法A训练大纲

划分DP

划分DP

1、确定段数的划分\color{red}\text{1、确定段数的划分}1、确定段数的划分

1.定义状态\color{blue}\text{1.定义状态}1.定义状态

2. 状态转移方程\color{blue}\text{2. 状态转移方程}2. 状态转移方程

3. 初始化\color{blue}\text{3. 初始化}3. 初始化

4. 计算顺序\color{blue}\text{4. 计算顺序}4. 计算顺序

5. 答案提取\color{blue}\text{5. 答案提取}5. 答案提取

示例应用场景\color{blue}\text{示例应用场景}示例应用场景

2、不确定段数的划分\color{red}\text{2、不确定段数的划分}2、不确定段数的划分

1) 通用模板（枚举最后一段）\color{blue}\text{1) 通用模板（枚举最后一段）}1) 通用模板（枚举最后一段）

2) 常见目标类型与套路\color{blue}\text{2) 常见目标类型与套路}2) 常见目标类型与套路

黑大帅的动态

参数 $k$ 与操作次数要求

$\color{red}\text{1、确定段数的划分}$

$\color{blue}\text{1.定义状态}$

$\color{blue}\text{2. 状态转移方程}$

$\color{blue}\text{3. 初始化}$

$\color{blue}\text{4. 计算顺序}$

$\color{blue}\text{5. 答案提取}$

$\color{blue}\text{示例应用场景}$

$\color{red}\text{2、不确定段数的划分}$

$\color{blue}\text{1) 通用模板（枚举最后一段）}$

$\color{blue}\text{2) 常见目标类型与套路}$

$\color{purple}A.$ 最小化“各段代价之和”

$\color{purple}B.$ 最少段数（每段需“可行”）

$\color{purple}C.$ 段数-代价联合权衡（拉格朗日/Alien’s Trick）

$\color{purple}D.$ 最大化类（奖励可加）

$\color{blue}\text{3) 决策单调性与分治优化（可选）}$