P16231 [蓝桥杯 2026 省 A] 基因研究

Posted on 2026-04-12

题目大意

P16231 [蓝桥杯 2026 省 A] 基因研究

题目描述

DNA 分子的四种碱基分别记为 A、T、G、C。每个人的基因序列都可以认为是一个由 A、T、G、C 四种字符组成的长度为 $n$ 的字符串。

小蓝正在研究一种疾病。他观察到，这种疾病存在一个固定的易感序列（也可认为是一个由 A、T、G、C 构成的字符串）。若某人的基因序列中存在一个子串恰好等于这个易感序列，则称此人“易感”；若基因序列的任意子串都不等于这个易感序列，则称此人“不易感”。

小蓝希望根据这座城市中人们的基因序列情况，估计出城里“易感”人群所占的比例。

然而，直接获取整座城市中每个人完整的基因序列非常困难。为此，小蓝采用了抽样统计的方法：通过大量采样，他估计出了在这座城市中，每一个位置上碱基为 A、T、G、C 的人数占比。我们可以将其理解为：在所有人的基因序列中，第 $i$ 个位置为 A、T、G、C 的人数占比分别是多少。

为了简化模型，小蓝作出如下假设：对于任意一个人，其基因序列在每个位置上的碱基分布与采样结果完全一致，且不同位置之间的碱基相互独立。也就是说，即使已经确定了若干个位置上的碱基，剩余位置上的碱基仍然按照对应位置的分布独立生成。

现在，小蓝决定将这些概率以模 $998244353$ 的形式算出：如果“易感”人群所占比例为 $\frac{p}{q}$ ，则小蓝希望得到一个整数 $x$ ，满足 $x \times q \equiv p \pmod{998244353}$ 。请你根据给定的易感序列，以及每个位置上四种碱基的概率分布，帮小蓝计算并输出这个整数 $x$ 。

输入格式

第一行包含两个正整数 $n, m$ ，分别表示基因序列长度和易感序列长度。

第二行包含一个长度为 $m$ 的字符串 $s$ ，仅由 A、T、G、C 构成，表示疾病对应的易感序列。

接下来 $n$ 行，每行包含四个非负整数 $a_i, t_i, g_i, c_i$ 。其中：

$a_i$ 表示第 $i$ 个位置碱基为 A 的概率（模 $998244353$ 意义下）；
$t_i$ 表示第 $i$ 个位置碱基为 T 的概率（模 $998244353$ 意义下）；
$g_i$ 表示第 $i$ 个位置碱基为 G 的概率（模 $998244353$ 意义下）；
$c_i$ 表示第 $i$ 个位置碱基为 C 的概率（模 $998244353$ 意义下）。

保证对任意 $i$ ，均有 $(a_i + t_i + g_i + c_i) \bmod 998244353 = 1$ 。

输出格式

输出一行，包含一个非负整数，表示“基因序列中包含易感序列作为子串”的人群占比在模 $998244353$ 意义下的结果。

输入输出样例 #1

输入 #1

3 2
AA
499122177 499122177 0 0
499122177 0 499122177 0
499122177 0 0 499122177

输出 #1

623902721

说明/提示

【样例说明】

基因序列共有 $3$ 个位置：

第 $1$ 位有 $\frac{1}{2}$ 的概率是 $A$ ，有 $\frac{1}{2}$ 的概率是 $T$ ；
第 $2$ 位有 $\frac{1}{2}$ 的概率是 $A$ ，有 $\frac{1}{2}$ 的概率是 $G$ ；
第 $3$ 位有 $\frac{1}{2}$ 的概率是 $A$ ，有 $\frac{1}{2}$ 的概率是 $C$ 。

易感序列为 $AA$ 。因此，一个人被视为“易感”，当且仅当其基因序列中包含子串 $AA$ 。

所有可能产生的基因序列中，满足条件的共有 3 种，分别是 $AAC$ 、 $TAA$ 和 $AAA$ 。这 3 种序列出现的概率均为 $\frac{1}{8}$ ，因此“易感”人群所占的总比例为 $\frac{1}{8} + \frac{1}{8} + \frac{1}{8} = \frac{3}{8}$ ，其在模 $998244353$ 意义下的结果为 $623902721$ 。

【评测用例规模与约定】

对于 $30\%$ 的数据， $1 \le m \le n \le 5$ ；

另存在 $20\%$ 的数据， $a_i = t_i = g_i = c_i$ ；

对于 $100\%$ 的数据， $1 \le m \le n \le 3000, 0 \le a_i, t_i, g_i, c_i < 998244353$ 。

思路讲解

AI 生成的 latex 题解代码

No content to show

AC代码

源代码

心路历程（WA，TLE，MLE……）

P16230 [蓝桥杯 2026 省 A] 综合应变指标（把绝对值变为分类讨论，去掉绝对值，然后我们会发现好处理很多）

Posted on 2026-04-12

题目大意

P16230 [蓝桥杯 2026 省 A] 综合应变指标

题目描述

航空引擎涡轮叶片是确保国家空天安全的核心装备，其制造工艺代表了工业技术的巅峰。

这天，在精密检测实验室的中央，首席结构分析师小蓝正利用高精度传感器，沿涡轮叶片的中轴线进行连续扫描。扫描产生的反馈数据被转化为一条包含 $N$ 个元素的序列 $A = (A_1, A_2, \dots, A_N)$ 。

为了评估叶片在极限运行负载下的稳定性，小蓝需要针对这组序列计算出一个综合应变指标。计算该指标的第一步是选定三个分割点 $i, j, k$ （满足 $1 \le i < j < k < N$ ），将整条序列划分为以下四个连续且非空的子段：

第一段： $A_1, \dots, A_i$ ；
第二段： $A_{i+1}, \dots, A_j$ ；
第三段： $A_{j+1}, \dots, A_k$ ；
第四段： $A_{k+1}, \dots, A_N$ 。

第二步，需要计算每一个子段内所有数值的总和，并取其绝对值。这四个绝对值的累加总和被定义为该划分方案下的综合应变指标：

|A_1 + \cdots + A_i| + |A_{i+1} + \cdots + A_j| + |A_{j+1} + \cdots + A_k| + |A_{k+1} + \cdots + A_N|

分割点的选择有多种可能，不同的方案会导致不同的指标结果。

现在，请你帮助小蓝找出一种划分方案，使得得到的综合应变指标的数值最大。

输入格式

第一行包含一个正整数 $N$ ，表示扫描序列采集到的反馈节点总数。

第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$ ，表示序列的元素。

输出格式

输出一行一个整数，表示序列所能达到的最大综合应变指标。

输入输出样例 #1

输入 #1

1 2	5 1 -1 -2 3 5

输出 #1

说明/提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $4 \le N \le 100$ ；

对于 $60\%$ 的评测用例， $4 \le N \le 400$ ；

对于所有评测用例， $4 \le N \le 10^5$ ， $-10^9 \le A_i \le 10^9$ 。

思路讲解

AI 生成的 latex 题解代码

\documentclass{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xeCJK}
\usepackage{multicol}
\usepackage{tocloft}
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing, arrows.meta}
\usepackage[cachedir=_minted-main]{minted}
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}

\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}}

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref}

% --- TikZ 颜色定义 ---
\definecolor{seg1}{RGB}{50,120,200}     % 蓝色 — 第一段
\definecolor{seg2}{RGB}{220,80,60}      % 红色 — 第二段
\definecolor{seg3}{RGB}{0,160,80}       % 绿色 — 第三段
\definecolor{seg4}{RGB}{140,80,200}     % 紫色 — 第四段
\definecolor{highlight}{RGB}{255,160,0} % 橙色 — 高亮

\title{\textbf{P16230 [蓝桥杯 2026 省 A] 综合应变指标} \\ 题解}
\author{}
\date{}

\begin{document}
\maketitle

\section{题意概述}

给定长度为 $N$ 的整数序列 $A$，选取三个分割点 $i, j, k$（满足 $1 \le i < j < k < N$）将序列划分为四个非空连续子段，最大化四段元素和的绝对值之和：
$$|A_1 + \cdots + A_i| + |A_{i+1} + \cdots + A_j| + |A_{j+1} + \cdots + A_k| + |A_{k+1} + \cdots + A_N|$$

\section{第一层思考：前缀和改写目标函数}

定义前缀和 $P_m = \sum_{t=1}^{m} A_t$（$P_0 = 0$）。四段的元素和分别为 $P_i$、$P_j - P_i$、$P_k - P_j$、$P_N - P_k$。目标函数改写为：
$$f(i, j, k) = |P_i| + |P_j - P_i| + |P_k - P_j| + |P_N - P_k|$$

这一步把"子段求和"全部消解成了前缀和之差的绝对值，后续只需操作 $P$ 数组。

\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.75, every node/.style={font=\small}]
	% 序列格子
	\foreach \idx in {1,...,10} {
		\fill[gray!12] (\idx-0.45, -0.4) rectangle (\idx+0.45, 0.4);
		\draw[gray!50] (\idx-0.45, -0.4) rectangle (\idx+0.45, 0.4);
		\node at (\idx, 0) {$A_{\idx}$};
	}

	% 四段着色（底部色条）
	\draw[seg1, line width=3pt] (0.45, -0.65) -- (3.55, -0.65);
	\node[seg1, font=\bfseries] at (2, -1.15) {第 1 段};
	\node[seg1] at (2, -1.65) {和 $= P_i$};

	\draw[seg2, line width=3pt] (3.55, -0.65) -- (6.55, -0.65);
	\node[seg2, font=\bfseries] at (5, -1.15) {第 2 段};
	\node[seg2] at (5, -1.65) {和 $= P_j - P_i$};

	\draw[seg3, line width=3pt] (6.55, -0.65) -- (8.55, -0.65);
	\node[seg3, font=\bfseries] at (7.5, -1.15) {第 3 段};
	\node[seg3] at (7.5, -1.65) {和 $= P_k - P_j$};

	\draw[seg4, line width=3pt] (8.55, -0.65) -- (10.55, -0.65);
	\node[seg4, font=\bfseries] at (9.5, -1.15) {第 4 段};
	\node[seg4] at (9.5, -1.65) {和 $= P_N - P_k$};

	% 分割点标注
	\draw[thick, dashed] (3.55, 0.6) -- (3.55, -0.55);
	\node[above] at (3.55, 0.6) {$i$};
	\draw[thick, dashed] (6.55, 0.6) -- (6.55, -0.55);
	\node[above] at (6.55, 0.6) {$j$};
	\draw[thick, dashed] (8.55, 0.6) -- (8.55, -0.55);
	\node[above] at (8.55, 0.6) {$k$};
\end{tikzpicture}
\caption{%
	将序列 $A$ 在分割点 $i, j, k$ 处划分为四段。每段的元素和均可用前缀和 $P$ 简洁表示。%
}
\label{fig:partition}
\end{figure}

直接枚举三个分割点的时间复杂度为 $O(N^3)$，对 $N = 10^5$ 不可接受。能否把三重循环逐层拆解，每层都只做线性扫描？

\section{第二层思考：$O(N^2)$ 的朴素代码}

问题本身就是分段的，自然地逐段转移。定义四层 DP：\texttt{dp1[i]} 表示只切出第一段、该段以位置 $i$ 结尾时的最大贡献；\texttt{dp2[i]} 表示前两段的最大贡献，第二段以 $i$ 结尾；\texttt{dp3}、\texttt{dp4} 同理。答案为 \texttt{dp4[N]}。

第一层直接算：

\begin{minted}{cpp}
dp1[i] = abs(preA[i]);
\end{minted}

从 \texttt{dp1} 到 \texttt{dp2}、从 \texttt{dp2} 到 \texttt{dp3}、从 \texttt{dp3} 到 \texttt{dp4}，转移结构完全一样，写成一个通用函数：

\begin{minted}{cpp}
void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= i; ++j) {                   // ← 内层循环
			dp2[i] = max(dp2[i], dp1[j] + abs(preA[i] - preA[j]));
		}
	}
}
\end{minted}

调用三次 \texttt{excute\_dp}，每次 $O(N^2)$。瓶颈就在内层 \texttt{for(j)} 循环——能不能干掉它？

\section{第三层思考：干掉内层循环}

盯着内层循环体看：

\begin{minted}{cpp}
dp2[i] = max(dp2[i], dp1[j] + abs(preA[i] - preA[j]));
\end{minted}

\texttt{abs} 只有两种展开。代入后，把只跟 \texttt{j} 有关的项括起来：

\begin{minted}{cpp}
dp1[j] + preA[i] - preA[j]  =  (dp1[j] - preA[j]) + preA[i]
//                               ^^^^^^^^^^^^^^^^^^    ^^^^^^^^
//                               只跟 j 有关            只跟 i 有关

dp1[j] + preA[j] - preA[i]  =  (dp1[j] + preA[j]) - preA[i]
//                               ^^^^^^^^^^^^^^^^^^    ^^^^^^^^
//                               只跟 j 有关            只跟 i 有关
\end{minted}

所以内层循环等价于：

\begin{minted}{cpp}
dp2[i] = max(
	max_over_j(dp1[j] - preA[j]) + preA[i],
	max_over_j(dp1[j] + preA[j]) - preA[i]
);
\end{minted}

\texttt{max\_over\_j(dp1[j] - preA[j])} 和 \texttt{max\_over\_j(dp1[j] + preA[j])} 不依赖 \texttt{i}！而且随着 \texttt{i} 递增，\texttt{j} 的候选范围只增不减（$j \le i$）。用两个变量滚动维护前缀最大值就行了，内层循环彻底消失：

\begin{minted}{cpp}
void excute_dp(const vector<ll> &from, vector<ll> &to) {
	ll Mplus = -INF, Mminus = -INF;
	for (int i = 1; i <= N; ++i) {
		Mplus  = max(Mplus,  from[i] + preA[i]);   // 维护 max(dp1[j]+preA[j])
		Mminus = max(Mminus, from[i] - preA[i]);   // 维护 max(dp1[j]-preA[j])
		to[i]  = max(Mminus + preA[i], Mplus - preA[i]);
	}
}
\end{minted}

双重循环 $\to$ 单层循环，$O(N^2) \to O(N)$。调用三次，总计 $O(N)$。

\subsection{图像理解}

上面的优化可以用图~\ref{fig:v-shape} 直观看懂。

对每个候选 \texttt{j}，\texttt{dp1[j] + abs(preA[i] - preA[j])} 是关于 \texttt{preA[i]} 的一条 V 形曲线——谷底在 \texttt{preA[j]}，谷底高 \texttt{dp1[j]}，两臂斜率 $\pm 1$。内层循环就是对所有 V 形取最大值（上包络）。

关键：所有 V 形的斜率全一样（$\pm 1$），不同的只是截距。同斜率的平行线取最大值，只有截距最大的一条存活。所以上包络只由两条直线决定——截距就是代码里的 \texttt{Mminus} 和 \texttt{Mplus}。

\texttt{i} 每递增一步，候选集多出一条新 V 形。新 V 形的截距和当前 \texttt{Mminus}、\texttt{Mplus} 取一次 \texttt{max} 就完成更新——这就是循环体里那两行 \texttt{max} 在干的事。

\begin{figure}[H]
\centering
\begin{tikzpicture}[scale=0.85, every node/.style={font=\small}]
	\begin{scope}
	\clip (-0.5, -0.5) rectangle (8.2, 7.5);

	% 被淘汰的臂（灰色虚线）
	\draw[gray!40, line width=0.5pt, densely dashed] (0, 4) -- (2, 2);
	\draw[gray!40, line width=0.5pt, densely dashed] (0, 5.5) -- (4, 1.5) -- (7.5, 5);
	\draw[gray!40, line width=0.5pt, densely dashed] (6, 1) -- (8, 3);

	% 存活的冠军臂（粗实线）
	\draw[seg1, line width=2.5pt] (2, 2) -- (7.5, 7.5);
	\draw[seg3, line width=2.5pt] (0, 7) -- (6, 1);

	% 上包络（橙色）
	\draw[highlight, line width=3.5pt, opacity=0.45] (0, 7) -- (3.5, 3.5) -- (7.5, 7.5);
	\end{scope}

	% V 形谷底
	\fill[seg1] (2, 2) circle (3pt);
	\fill[seg2] (4, 1.5) circle (3pt);
	\fill[seg3] (6, 1) circle (3pt);
	\fill[highlight!80!black] (3.5, 3.5) circle (3pt);

	% 谷底到 y 轴的水平虚线
	\draw[seg1!40, densely dotted, thin] (0, 2) -- (2, 2);
	\draw[seg2!40, densely dotted, thin] (0, 1.5) -- (4, 1.5);
	\draw[seg3!40, densely dotted, thin] (0, 1) -- (6, 1);

	% 坐标轴
	\draw[-stealth, thick] (-0.5, 0) -- (8.2, 0) node[right] {\texttt{preA[i]}};
	\draw[-stealth, thick] (0, -0.5) -- (0, 7.8);

	% preA[j] 刻度
	\foreach \x/\col/\lab in {2/seg1/1, 4/seg2/2, 6/seg3/3} {
		\draw[\col] (\x, -0.08) -- (\x, 0.08);
		\node[\col, below, font=\footnotesize] at (\x, -0.2) {\texttt{preA[$j_\lab$]}};
	}

	% y 轴谷底值标注
	\node[seg1, left, font=\footnotesize] at (-0.15, 2) {\texttt{dp1[$j_1$]}};
	\node[seg2, left, font=\footnotesize] at (-0.15, 1.5) {\texttt{dp1[$j_2$]}};
	\node[seg3, left, font=\footnotesize] at (-0.15, 1) {\texttt{dp1[$j_3$]}};

	% 冠军臂箭头标注
	\draw[-stealth, seg1!80!black, thick] (7.2, 5.5) -- (6.2, 6.2);
	\node[seg1!80!black, font=\footnotesize, align=left, right] at (7.2, 5.0)
		{斜率 $+1$ 冠军\\[-1pt] 截距 $=$ \texttt{Mminus}};

	\draw[-stealth, seg3!80!black, thick] (0.6, 7.5) -- (1.2, 5.8);
	\node[seg3!80!black, font=\footnotesize, align=left, right] at (0.6, 7.7)
		{斜率 $-1$ 冠军，截距 $=$ \texttt{Mplus}};

	% 图例
	\draw[gray!40, line width=0.5pt, densely dashed] (4.5, -1.2) -- (5.3, -1.2);
	\node[gray!60, font=\footnotesize, right] at (5.4, -1.2) {被淘汰的臂};
	\draw[highlight, line width=3pt, opacity=0.45] (4.5, -1.7) -- (5.3, -1.7);
	\node[highlight!80!black, font=\footnotesize, right] at (5.4, -1.7) {上包络 $=$ \texttt{dp2[i]}};
\end{tikzpicture}
\caption{%
	每个候选 \texttt{j} 产生一条 V 形（谷底高 \texttt{dp1[j]}，位于 \texttt{preA[j]}）。所有 V 形斜率一样（$\pm 1$），上包络只由截距最大的两条臂决定——截距就是代码里的 \texttt{Mminus} 和 \texttt{Mplus}。其余臂（灰色虚线）全被淘汰。%
}
\label{fig:v-shape}
\end{figure}

\section{代码实现}

\begin{minted}{cpp}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll INF = (1ll << 61) - 1;

struct Solve {
	ll N;
	vector<ll> A, preA;
	vector<ll> dp1, dp2, dp3, dp4;

	// 核心：优化后的转移，O(N)
	void excute_dp(const vector<ll> &from, vector<ll> &to) {
		ll Mplus = -INF, Mminus = -INF;
		for (int i = 1; i <= N; ++i) {
			Mplus  = max(Mplus,  from[i] + preA[i]);
			Mminus = max(Mminus, from[i] - preA[i]);
			to[i]  = max(Mminus + preA[i], Mplus - preA[i]);
		}
	}

	Solve() {
		cin >> N;
		A.resize(N + 2);
		for (int i = 1; i <= N; ++i)
			cin >> A[i];
		preA.resize(N + 2);
		partial_sum(A.begin(), A.end(), preA.begin());

		dp1.resize(N + 2, -INF);
		for (int i = 1; i <= N; ++i)
			dp1[i] = abs(preA[i]);

		dp2.resize(N + 2, -INF);
		dp3.resize(N + 2, -INF);
		dp4.resize(N + 2, -INF);
		excute_dp(dp1, dp2);
		excute_dp(dp2, dp3);
		excute_dp(dp3, dp4);
		cout << dp4[N] << "\n";
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Solve solve;
	return 0;
}
\end{minted}

\section{复杂度分析}

\begin{itemize}
	\item \textbf{时间复杂度}：$O(N)$。\texttt{excute\_dp} 单次 $O(N)$，调用三次，总计 $O(N)$。
	\item \textbf{空间复杂度}：$O(N)$。四个 DP 数组加前缀和数组。
\end{itemize}

\end{document}

PDF

写出一个 $O(n^2)$ 的 dp 代码没有那么难。

void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= i; ++j) {
			dp2[i] = max(dp2[i], dp1[j] + abs(preA[i] - preA[j]));
		}
	}
}

现在最关键的就是如何把这个内层的 for 循环给优化掉。

有绝对值？那就要把绝对值去掉，用分类讨论。

说白了，其实就是这样子，因为我们有 max 函数，甚至可以不需要分类讨论。

void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= i; ++j) {
			dp2[i] = max(dp2[i], dp1[j] + preA[i] - preA[j]);
			dp2[i] = max(dp2[i], dp1[j] - (preA[i] - preA[j]));
		}
	}
}

AC代码

O（n*n）的这个源代码

// teamname: Gospel_rock
/**
 * Problem: P16230 [蓝桥杯 2026 省 A] 综合应变指标
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P16230
 * Created: 2026-04-12 12:29:30
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
	ll N;
	vector<ll> A;
	vector<ll> preA;
	vector<ll> dp1;
	vector<ll> dp2;
	vector<ll> dp3;
	vector<ll> dp4;

	void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
		for (int i = 1; i <= N; ++i) {
			for (int j = 1; j <= i; ++j) {
				dp2[i] = max(dp2[i], dp1[j] + abs(preA[i] - preA[j]));
			}
		}
	}

	Solve() {
		cin >> N;
		A.resize(N + 2);
		for (int i = 1; i <= N; ++i) {
			cin >> A[i];
		}
		preA.resize(N + 2);
		partial_sum(all(A), preA.begin());
		dp1.resize(N + 2, -INF);
		for (int i = 1; i <= N; ++i) {
			dp1[i] = abs(preA[i]);
		}
		dp2.resize(N + 2, -INF);
		dp3.resize(N + 2, -INF);
		dp4.resize(N + 2, -INF);
		excute_dp(dp1,dp2);
		excute_dp(dp2,dp3);
		excute_dp(dp3,dp4);
#ifdef LOCAL
		debug1d(dp1);
		debug1d(dp2);
		debug1d(dp3);
		debug1d(dp4);
#endif
		cout<<dp4[N]<<"\n";
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	// cin >> lT;
	// for (testcase=1;testcase<=lT;++testcase)
	Solve solve;
	return 0;
}

/*

*/

AC
https://www.luogu.com.cn/record/273684075

源代码

// teamname: Gospel_rock
/**
 * Problem: P16230 [蓝桥杯 2026 省 A] 综合应变指标
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P16230
 * Created: 2026-04-12 12:29:30
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
	ll N;
	vector<ll> A;
	vector<ll> preA;
	vector<ll> dp1;
	vector<ll> dp2;
	vector<ll> dp3;
	vector<ll> dp4;
	vector<array<ll, 2> > dp_1_preA;

	void excute_dp(const vector<ll> &dp1, vector<ll> &dp2) {
		for (int j = 1; j <= N; ++j) {
			dp_1_preA[j][0] = dp1[j] - preA[j];
			dp_1_preA[j][1] = dp1[j] + preA[j];
			dp_1_preA[j][0] = max(dp_1_preA[j - 1][0], dp_1_preA[j][0]);
			dp_1_preA[j][1] = max(dp_1_preA[j - 1][1], dp_1_preA[j][1]);
		}
		for (int i = 1; i <= N; ++i) {
			// for (int j = 1; j <= i; ++j) {
			// 	dp2[i] = max(dp2[i], dp1[j] + preA[i] - preA[j]);
			// 	dp2[i] = max(dp2[i], dp1[j] - (preA[i] - preA[j]));
			// }
			dp2[i] = max(dp2[i],dp_1_preA[i][0] + preA[i]);
			dp2[i] = max(dp2[i],dp_1_preA[i][1] - preA[i]);
		}
	}

	Solve() {
		cin >> N;
		A.resize(N + 2);
		for (int i = 1; i <= N; ++i) {
			cin >> A[i];
		}
		preA.resize(N + 2);
		partial_sum(all(A), preA.begin());
		dp1.resize(N + 2, -INF);
		for (int i = 1; i <= N; ++i) {
			dp1[i] = abs(preA[i]);
		}
		dp2.resize(N + 2, -INF);
		dp3.resize(N + 2, -INF);
		dp4.resize(N + 2, -INF);
		dp_1_preA.resize(N + 2, {-INF, -INF});
		excute_dp(dp1, dp2);
		excute_dp(dp2, dp3);
		excute_dp(dp3, dp4);
#ifdef LOCAL
		debug1d(dp1);
		debug1d(dp2);
		debug1d(dp3);
		debug1d(dp4);
#endif
		cout << dp4[N] << "\n";
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
#ifdef LOCAL
	cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

	// cin >> lT;
	// for (testcase=1;testcase<=lT;++testcase)
	Solve solve;
	return 0;
}

/*
AC
https://www.luogu.com.cn/record/273684075

*/

心路历程（WA，TLE，MLE……）

P16229 [蓝桥杯 2026 省 A] 外卖配送

Posted on 2026-04-12

题目大意

P16229 [蓝桥杯 2026 省 A] 外卖配送

题目描述

午高峰的外卖站点里，骑手小蓝正紧盯着屏幕上待处理的 $N$ 个订单。这些订单必须严格按照系统列表中的固定顺序依次配送，不可打乱或跳过。为了顺利完成任务，小蓝计划将这 $N$ 个订单分成若干个批次进行配送。

站点内停放着 $M$ 种不同的交通工具，每种工具都具备两个属性：平均路途耗时 $A_i$ 和箱体拥挤系数 $B_i$ 。对于每一个批次，小蓝可以根据该批次订单的数量，从 $M$ 种工具中独立选择一种最合适的。

假设某一个批次包含 $L$ 个订单，且小蓝选用第 $i$ 种交通工具，则该批次的总耗时由以下三部分组成：

路途耗时： $L \times A_i$ 秒。
取餐耗时：由于箱内挤压，整理 $L$ 个订单需处理 $\frac{L(L-1)}{2}$ 对挤压关系，每对耗时 $B_i$ ，共计 $\frac{L(L-1)}{2} \times B_i$ 秒。
折返耗时：分批配送存在额外的折返成本。处理第一个批次时，由于小蓝默认已在站点装车完毕可以直接出发，此项耗时为 $0$ 秒；但从第二个批次开始，每开启一个新的批次，都必须花费固定的 $X$ 秒用于返回站点装载下一批订单。

现在，请你帮助小蓝规划最优的分批方案，并计算出送完 $N$ 个订单所需的最小总耗时。

输入格式

一行包含三个整数 $N$ 、 $M$ 和 $X$ ，分别表示订单总数、交通工具的种类数，以及固定耗时。

接下来的 $M$ 行，每行包含两个整数 $A_i$ 和 $B_i$ ，依次表示第 $i$ 种交通工具的平均路途耗时与箱体拥挤系数。

输出格式

输出一个整数，表示完成全部 $N$ 个订单配送任务所需的最小总耗时（单位：秒）。

输入输出样例 #1

输入 #1

1
2
3

5 2 40
10 8
2 20

输出 #1

说明/提示

【样例说明】

一种最优的方案是分成 $2$ 批配送：

阶段	详情	耗时
第 $1$ 批（ $2$ 单，选工具 $2$ ）	路途 $2 \times 2 = 4$ ；取餐 $\frac{2 \times 1}{2} \times 20 = 20$	$24$ 秒
折返	固定耗时	$40$ 秒
第 $2$ 批（ $3$ 单，选工具 $1$ ）	路途 $3 \times 10 = 30$ ；取餐 $\frac{3 \times 2}{2} \times 8 = 24$	$54$ 秒
合计	<	$\mathbf{118}$ 秒

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $1 \le N, M \le 100$ ；

对于所有评测用例， $1 \le N, M \le 5000$ ， $1 \le X, A_i, B_i \le 10^9$ 。

思路讲解

AI 生成的 latex 题解代码

\documentclass{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xeCJK}
\usepackage{multicol}
\usepackage{tocloft}
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing, arrows.meta}
\usepackage[cachedir=_minted-main]{minted}
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}

\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}}

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref}

% --- TikZ 颜色定义 ---
\definecolor{batch}{RGB}{50,120,200}     % 蓝色 — 批次
\definecolor{vehicle}{RGB}{220,80,60}    % 红色 — 交通工具
\definecolor{dp}{RGB}{0,160,80}          % 绿色 — DP 转移
\definecolor{knapsack}{RGB}{140,80,200}  % 紫色 — 背包物品
\definecolor{highlight}{RGB}{255,160,0}  % 橙色 — 高亮

\title{\textbf{P16229 [蓝桥杯 2026 省 A] 外卖配送} \\ 题解}
\author{}
\date{}

\begin{document}
\maketitle

\section{题意概述}

将 $N$ 个订单按固定顺序分成若干批次依次配送。站点有 $M$ 种交通工具，第 $i$ 种的路途耗时为 $A_i$，箱体拥挤系数为 $B_i$。若某批次包含 $L$ 个订单且选用第 $i$ 种交通工具，该批次耗时为：
$$L \cdot A_i + \frac{L(L-1)}{2} \cdot B_i$$
此外，从第二个批次起，每开启一个新批次需额外花费固定的 $X$ 秒折返。求送完所有订单的最小总耗时。

\section{第一层思考：预处理单批次最优耗时}

先不考虑批次之间的分配问题，聚焦一个子问题：如果某批次恰好要送 $L$ 个订单，最少要花多少时间？

交通工具的选择仅取决于 $L$，与其他批次无关。因此，对于每个 $L$，我们遍历所有 $M$ 种交通工具，取最小耗时即可。定义：
$$C_L = \min_{1 \le i \le M} \left( L \cdot A_i + \frac{L(L-1)}{2} \cdot B_i \right)$$

$C_L$ 的含义是：单独配送一个包含 $L$ 个订单的批次所需的最小耗时（不含折返）。这一步的时间复杂度为 $O(NM)$。

\section{第二层思考：发现完全背包结构}

现在的问题变成了：将 $N$ 个订单分成若干批，第一批不需要折返，后续每批额外花费 $X$ 秒。怎样分批使得总耗时最小？

\subsection{统一折返代价的技巧}

为了让每一批的代价形式一致，我们使用一个常见技巧：\textbf{假设每一批都需要折返}（每批的代价统一为 $C_L + X$），最终答案再减去多算的第一批的那一次 $X$。

这样，每一批的代价就只取决于该批的订单数 $L$，是一个"物品"的概念了。

\subsection{转化为完全背包}

经过上述统一，问题可以精确地描述为：

\begin{quote}
有 $N$ 种"物品"，第 $L$ 种物品的"重量"为 $L$，"代价"为 $C_L + X$。每种物品可以使用任意多次。需要恰好装满容量为 $N$ 的背包，求最小总代价。
\end{quote}

这正是一个\textbf{完全背包问题}。定义状态 $f_w$ 为恰好配送前 $w$ 个订单的最小总耗时（含统一折返），转移方程为：
$$f_w = \min_{1 \le L \le w} \left( f_{w - L} + C_L + X \right)$$
初始条件 $f_0 = 0$，最终答案为 $f_N - X$。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.75, every node/.style={font=\small}]
	% 订单序列
	\foreach \i in {1,...,10} {
		\fill[gray!15] (\i-0.45, -0.4) rectangle (\i+0.45, 0.4);
		\draw[gray!60] (\i-0.45, -0.4) rectangle (\i+0.45, 0.4);
		\node at (\i, 0) {$\i$};
	}
	\node[font=\bfseries] at (5.5, 1) {$N = 10$ 个订单};

	% 分批
	\draw[batch, line width=2.5pt] (0.45, -0.6) -- (3.55, -0.6);
	\node[batch, font=\bfseries] at (2, -1.1) {第 1 批 ($L=3$)};

	\draw[vehicle, line width=2.5pt] (3.55, -0.6) -- (7.55, -0.6);
	\node[vehicle, font=\bfseries] at (5.5, -1.1) {第 2 批 ($L=4$)};

	\draw[dp, line width=2.5pt] (7.55, -0.6) -- (10.55, -0.6);
	\node[dp, font=\bfseries] at (9, -1.1) {第 3 批 ($L=3$)};

	% 代价标注
	\node[batch] at (2, -1.7) {$C_3 + X$};
	\node[vehicle] at (5.5, -1.7) {$C_4 + X$};
	\node[dp] at (9, -1.7) {$C_3 + X$};

	% 总代价
	\node[font=\bfseries] at (5.5, -2.5) {总代价 $= (C_3 + X) + (C_4 + X) + (C_3 + X) - X$};
\end{tikzpicture}
\caption{%
	将 $10$ 个订单分成 $3$ 批的示意图。每批统一计入折返代价 $X$，最后减去首批多算的一次 $X$。批次大小 $L$ 对应完全背包中的"物品重量"。%
}
\label{fig:batch}
\end{figure}

\subsection{完全背包的代码范式}

标准的完全背包写法是：外层枚举物品种类 $L$，内层从 $L$ 到 $N$ 正序枚举容量 $w$。正序枚举保证了同一种物品可以被重复选取：

\begin{minted}{cpp}
for (int L = 1; L <= N; ++L)
	for (int w = L; w <= N; ++w)
		dpN[w] = min(dpN[w], dp[L] + dpN[w - L] + X);
\end{minted}

这和 0-1 背包的唯一区别就在于内层循环是\textbf{正序}而非逆序。

\section{关于完全背包时间复杂度的讨论}

读者可能会注意到：这道题的 DP 部分是一个双重循环，时间复杂度为 $O(N^2)$。这和"完全背包的时间复杂度是 $O(nW)$"（$n$ 为物品种类数，$W$ 为背包容量）是一致的吗？

答案是\textbf{完全一致}的。

在本题中，"物品"是批次大小 $L \in \{1, 2, \ldots, N\}$，共有 $n = N$ 种物品；"背包容量"$W = N$（需要恰好配送 $N$ 个订单）。所以完全背包的时间复杂度 $O(nW) = O(N \times N) = O(N^2)$，恰好与代码中双重循环的复杂度吻合。

\medskip

更一般地，完全背包的时间复杂度\textbf{确实}是"物品种类数 $\times$ 背包容量"。我们来直观理解为什么：

\begin{itemize}
	\item 外层循环枚举的是"用哪种物品来更新"，共 $n$ 轮。
	\item 内层循环枚举的是"更新哪个容量的状态"，共 $W$ 步。
	\item 每一步的转移是 $O(1)$ 的（直接比较取 $\min$）。
\end{itemize}

因此总时间为 $O(nW)$。这与 0-1 背包的复杂度形式相同——区别仅在于内层循环的枚举方向（正序 vs 逆序），不影响循环次数。

如图~\ref{fig:knapsack} 所示，完全背包的 DP 表可以看作一个 $n \times W$ 的网格，每个格子恰好被访问一次。

\begin{figure}[htbp]
\centering
\begin{tikzpicture}[scale=0.62, every node/.style={font=\footnotesize}]
	\def\numItems{5}
	\def\capacity{8}

	% 网格
	\foreach \i in {1,...,\numItems} {
		\foreach \j in {1,...,\capacity} {
			\fill[knapsack!8] (\j-0.45, -\i+0.45) rectangle (\j+0.45, -\i-0.45);
			\draw[knapsack!30] (\j-0.45, -\i+0.45) rectangle (\j+0.45, -\i-0.45);
		}
	}

	% 高亮当前更新行
	\foreach \j in {1,...,\capacity} {
		\fill[highlight!30] (\j-0.45, -3+0.45) rectangle (\j+0.45, -3-0.45);
		\draw[highlight!60] (\j-0.45, -3+0.45) rectangle (\j+0.45, -3-0.45);
	}

	% 列标签 (容量)
	\foreach \j in {1,...,\capacity} {
		\node[above] at (\j, 0.5) {$w\!=\!\j$};
	}

	% 行标签 (物品)
	\foreach \i in {1,...,\numItems} {
		\node[left] at (0.3, -\i) {$L\!=\!\i$};
	}

	% 轴标签
	\node[above, font=\small\bfseries] at (4.5, 1.2) {背包容量 $W$};
	\node[left, rotate=90, font=\small\bfseries] at (-0.8, -3) {物品种类 $n$};

	% 箭头标注
	\draw[-{Stealth}, highlight, line width=1.5pt] (0.55, -3) -- (8.45, -3);
	\node[right, highlight!80!black, font=\small\bfseries] at (8.6, -3) {正序扫描};

	% 总计标注
	\node[font=\bfseries] at (4.5, -6.3) {每格 $O(1)$，共 $n \times W$ 格 $\Rightarrow$ 总 $O(nW)$};
\end{tikzpicture}
\caption{%
	完全背包的 DP 表示意图。外层遍历 $n$ 种物品（行），内层正序遍历容量 $W$（列），每格恰好访问一次，总复杂度为 $O(nW)$。%
}
\label{fig:knapsack}
\end{figure}

\section{完整算法流程}

\begin{enumerate}
	\item \textbf{预处理}：对每个批次大小 $L \in [1, N]$，遍历 $M$ 种交通工具，计算 $C_L$。时间 $O(NM)$。
	\item \textbf{完全背包 DP}：以批次大小为物品、订单总数为容量，求最小代价。时间 $O(N^2)$。
	\item \textbf{输出}：$f_N - X$。
\end{enumerate}

\section{代码实现}

\begin{minted}{cpp}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

static constexpr ll INF = (1ll << 61) - 1;

struct Solve {
	ll N, M, X;
	vector<array<ll, 2> > abls;
	vector<ll> dp;   // dp[L] = 单批送 L 个订单的最小耗时
	vector<ll> dpN;  // dpN[w] = 送前 w 个订单的最小总耗时（含统一折返）

	Solve() {
		cin >> N >> M >> X;
		abls.resize(M);
		for (int i = 0; i < M; ++i) {
			cin >> abls[i][0] >> abls[i][1];
		}
		// 预处理单批次最优耗时
		dp.resize(N + 2, INF);
		for (int L = 1; L <= N; ++L) {
			for (int i = 0; i < M; ++i) {
				auto [a, b] = abls[i];
				dp[L] = min(dp[L], a * L + ((L * (L - 1)) / 2) * b);
			}
		}
		// 完全背包：外层枚举物品(批次大小)，内层正序枚举容量(订单数)
		dpN.resize(N + 2, INF);
		dpN[0] = 0;
		for (int L = 1; L <= N; ++L) {
			for (int w = L; w <= N; ++w) {
				dpN[w] = min(dpN[w], dp[L] + dpN[w - L] + X);
			}
		}
		cout << dpN[N] - X << "\n";
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	Solve solve;
	return 0;
}
\end{minted}

\section{复杂度分析}

\begin{itemize}
	\item \textbf{时间复杂度}：预处理 $C_L$ 需 $O(NM)$，完全背包 DP 需 $O(N^2)$。总计 $O(NM + N^2)$。在 $N, M \le 5000$ 的范围下，运算量约 $5 \times 10^7$，C++ 下可在百毫秒内完成。
	\item \textbf{空间复杂度}：$O(N + M)$，用于存储 $C_L$ 数组、DP 数组和交通工具属性。
\end{itemize}

\end{document}

PDF

其实我觉得 AI 说的不好，不过为了方便索引还是贴过来了

其实就是一个完全背包问题

Solve() {
    cin >> N >> M >> X;
    abls.resize(M);
    for (int i = 0; i < M; ++i) {
        cin >> abls[i][0] >> abls[i][1];
    }
    dp.resize(N + 2, INF);
    for (int L = 1; L <= N; ++L) {
        for (int i = 0; i < M; ++i) {
            auto [a,b] = abls[i];
            dp[L] = min(dp[L], a * L + ((L * (L - 1)) / 2) * b);
        }
    }
    dpN.resize(N + 2, INF);
    dpN[0] = 0;
    for (int L = 1; L <= N; ++L) {
        for (int w = L; w <= N; ++w) {
            if (w - L < 0) {
                continue;
            }
            if (dp[L] + dpN[w - L] + X < dpN[w]) {
                dpN[w] = dp[L] + dpN[w - L] + X;
            }
        }
    }
    cout << dpN[N] - X << "\n";
}

AC代码

AC
https://www.luogu.com.cn/record/273605286

源代码

// teamname: Gospel_rock
/**
 * Problem: P16229 [蓝桥杯 2026 省 A] 外卖配送
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P16229
 * Created: 2026-04-12 10:06:32
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
    ll N, M, X;
    vector<array<ll, 2> > abls;
    vector<ll> dp;
    vector<ll> dpN;

    Solve() {
        cin >> N >> M >> X;
        abls.resize(M);
        for (int i = 0; i < M; ++i) {
            cin >> abls[i][0] >> abls[i][1];
        }
        dp.resize(N + 2, INF);
        for (int L = 1; L <= N; ++L) {
            for (int i = 0; i < M; ++i) {
                auto [a,b] = abls[i];
                dp[L] = min(dp[L], a * L + ((L * (L - 1)) / 2) * b);
            }
        }
        dpN.resize(N + 2, INF);
        dpN[0] = 0;
        for (int L = 1; L <= N; ++L) {
            for (int w = L; w <= N; ++w) {
                if (w - L < 0) {
                    continue;
                }
                if (dp[L] + dpN[w - L] + X < dpN[w]) {
                    dpN[w] = dp[L] + dpN[w - L] + X;
                }
            }
        }
        cout << dpN[N] - X << "\n";
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase = 1; testcase <= lT; ++testcase)
    Solve solve;
    return 0;
}

/*
AC
https://www.luogu.com.cn/record/273605286

*/

心路历程（WA，TLE，MLE……）

P16228 [蓝桥杯 2026 省 A] E. 读取指令

Posted on 2026-04-11 Edited on 2026-04-12

题目大意

P16228 [蓝桥杯 2026 省 A] 读取指令

题目描述

你正在管理一个老旧的线性机械硬盘，该硬盘被划分为 $N$ 个连续的扇区（编号从 $1$ 到 $N$ ）。

由于文件系统的特殊分配机制，第 $i$ 个扇区中存储的数据量为 $C \times i$ 字节（其中 $C$ 是系统簇大小的常数）。例如，当 $C = 2$ 时，第 $1$ 到 $4$ 个扇区的数据量分别为 $2, 4, 6, 8$ 字节。

现在，你需要从这块硬盘中恰好读取 $W$ 字节的数据来进行恢复。为了最小化磁头的寻道损耗，你只能向硬盘发送“读取指令”。每次指令可以指定一个连续的扇区区间 $[l, r]$ ，并读取该区间内的所有数据。

请问，要读取恰好 $W$ 字节的数据，最少需要发送多少次读取指令？注意：每个扇区最多只能被读取一次。如果无论如何也无法凑出恰好 $W$ 字节，请输出 $-1$ 。

输入格式

第一行包含一个整数 $T$ ，表示测试用例的组数。

接下来 $T$ 行，每行包含三个整数 $N, C, W$ ，相邻整数之间用空格隔开。

输出格式

对于每组测试用例，输出一行一个整数，表示最少的读取指令次数。如果无法完成，输出 $-1$ 。

输入输出样例 #1

输入 #1

输出 #1

1
2
3

1
2
-1

说明/提示

【评测用例规模与约定】

对于 $30\%$ 的评测用例， $1 \le N \le 1000$ ， $T = 2$ 。

对于所有的评测用例， $1 \le N \le 10^5$ ， $2 \le T \le 10$ ， $1 \le C \le 100$ ， $0 \le W \le 10^9$ 。

思路讲解

AI 生成的 latex 题解代码

\documentclass{article}

\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{xeCJK}
\usepackage{multicol}
\usepackage{tocloft}
\usepackage{xcolor}
\usepackage{tikz}
\usetikzlibrary{decorations.pathreplacing}
\usepackage[cachedir=_minted-main]{minted}
\usepackage[a4paper, left=2cm, right=2cm, top=2.5cm, bottom=2.5cm]{geometry}

\setminted{
	breaklines=true,
	breakanywhere=true,
	fontsize=\small,
	frame=single,
	bgcolor=gray!5,
	tabsize=2,
}

\renewcommand{\cftsecleader}{\cftdotfill{\cftdotsep}}

\usepackage[colorlinks=true, linkcolor=black, anchorcolor=black, citecolor=black, filecolor=black, menucolor=black, runcolor=black, urlcolor=blue]{hyperref}

% --- TikZ 颜色定义 ---
\definecolor{segA}{RGB}{50,120,200}    % 蓝色 — 区间 / 前缀
\definecolor{segB}{RGB}{220,80,60}     % 红色 — 挖去的元素
\definecolor{segC}{RGB}{0,160,80}      % 绿色 — 保留段
\definecolor{segD}{RGB}{140,80,200}    % 紫色 — 第二段
\definecolor{exceed}{RGB}{255,160,0}   % 橙色 — 超出部分

\title{\textbf{P16228 [蓝桥杯 2026 省 A] 读取指令} \\ 题解}
\author{}
\date{}

\begin{document}
\maketitle

\section{题意概述}

硬盘有 $N$ 个扇区，第 $i$ 个扇区的数据量为 $C \times i$ 字节。每次读取指令可以读取一段连续的扇区区间 $[l, r]$，每个扇区最多读一次。问恰好读取 $W$ 字节最少需要多少次读取指令。无解输出 $-1$。

\section{第一层思考：等价转化，剥离常数 $C$}

所有扇区的数据量都是 $C$ 的倍数。如果 $W$ 不是 $C$ 的倍数，那么无论怎么选取扇区区间，总字节数都是 $C$ 的倍数，永远凑不出 $W$，此时答案为 $-1$。

若 $C \mid W$，令 $K = W / C$。问题等价转化为：

\begin{quote}
	从数列 $1, 2, 3, \ldots, N$ 中，选取若干个\textbf{不相交的连续子段}，使得它们的元素之和恰好为 $K$，求最少的子段数。
\end{quote}

特别地，若 $K = 0$，不需要任何读取指令，答案为 $0$；若 $K > \frac{N(N+1)}{2}$（超过整块硬盘的数据总量），答案为 $-1$。

\section{第二层思考：答案只可能是 $0$、$1$、$2$ 或 $-1$}

对于 $0 < K \le \frac{N(N+1)}{2}$ 的情况，我们断言：

\begin{center}
	\fbox{答案要么是 $1$（存在单个连续子段凑出 $K$），要么是 $2$。}
\end{center}

这意味着我们只需要判断"能否只用一次指令搞定"，如果不能，答案就是 $2$。

\subsection{为什么答案至多为 $2$？—— 证明}

取最小的正整数 $r$，使得 $1 + 2 + \cdots + r \ge K$（记此和为 $T_r$）。若 $T_r = K$，则 $[1, r]$ 即为解，$1$ 次指令。以下证明 $T_r > K$ 时只需 $2$ 次指令。

\paragraph{第一步：$D < r$。}

令超出量 $D = T_r - K$。由 $r$ 的\textbf{最小性}，少取一个元素就不够：$T_{r-1} < K$。因此
$$D = T_r - K < T_r - T_{r-1} = r$$
又 $D \ge 1$，故 $1 \le D \le r - 1$。

如图~\ref{fig:D-bound} 所示，$K$ 被夹在两个相邻三角数 $T_{r-1}$ 与 $T_r$ 之间，二者的间距恰好是 $r$。$D$ 只是 $K$ 到 $T_r$ 的距离，自然\textbf{严格小于}这个间距。

\begin{figure}[H]
\centering
\begin{tikzpicture}[every node/.style={font=\small}]
	% === 主线段 ===
	\draw[line width=1.5pt] (0, 0) -- (8.4, 0);

	% === 三个关键点 ===
	\fill (0, 0) circle (3pt);
	\fill[segB] (2.4, 0) circle (3.5pt);
	\fill (8.4, 0) circle (3pt);

	% === 竖线 ===
	\draw[segB, thick] (2.4, -0.25) -- (2.4, 0.25);

	% === 点标签 ===
	\node[below=12pt] at (0, 0) {$T_{r-1}$};
	\node[below=12pt, segB, font=\small\bfseries] at (2.4, 0) {$K$};
	\node[below=12pt] at (8.4, 0) {$T_r$};

	% === 上方花括号：D ===
	\draw[decorate, decoration={brace, amplitude=5pt, raise=6pt}, segB, line width=1pt]
		(2.4, 0) -- (8.4, 0)
		node[midway, above=11pt, black, font=\bfseries] {$D = T_r - K$};

	% === 下方花括号：总间距 = r ===
	\draw[decorate, decoration={brace, amplitude=5pt, mirror, raise=6pt}, line width=1pt]
		(0, 0) -- (8.4, 0)
		node[midway, below=11pt, font=\bfseries] {间距 $= T_r - T_{r-1} = r$};

	% === 结论 ===
	\node[font=\Large\bfseries] at (10.8, 0) {$\Rightarrow D < r$};
\end{tikzpicture}
\caption{%
	$K$ 被夹在 $T_{r-1}$ 与 $T_r$ 之间。$D$ 是 $K$ 到右端 $T_r$ 的距离，严格小于总间距 $r$。%
}
\label{fig:D-bound}
\end{figure}

\paragraph{第二步：$D$ 一定在 $[1, r)$ 中。}

由第一步，$1 \le D < r$。而 $[1, r)$ 中包含了\textbf{每一个}小于 $r$ 的正整数——$D$ 一定是其中之一，即 $D$ 是前缀 $\{1, 2, \ldots, r\}$ 中的某个元素。从 $[1, r]$ 中去掉 $D$，区间分裂为 $[1, D-1]$ 和 $[D+1, r]$ 两段（如图~\ref{fig:remove} 所示），二者之和 $= T_r - D = K$，恰好 $2$ 次指令。

\begin{figure}[H]
\centering
\begin{tikzpicture}[
	scale=0.82,
	block/.style={minimum width=1.15cm, minimum height=0.9cm, draw, font=\small\bfseries},
	dot/.style={minimum width=0.8cm, minimum height=0.9cm, font=\bfseries},
]
	% ========== 第一行：完整前缀 [1, r] ==========
	\node[font=\small\bfseries, anchor=east] at (-0.3, 0) {$[1, r]$：};
	\node[block, fill=segA!20] at (1, 0) {$1$};
	\node[block, fill=segA!20] at (2.2, 0) {$2$};
	\node[dot] at (3.2, 0) {$\cdots$};
	\node[block, fill=segA!20] at (4.2, 0) {\footnotesize$D\!-\!1$};
	\node[block, fill=segB!35, draw=segB, line width=1.5pt] at (5.6, 0) {$D$};
	\node[block, fill=segA!20] at (7.0, 0) {\footnotesize$D\!+\!1$};
	\node[dot] at (8.0, 0) {$\cdots$};
	\node[block, fill=segA!20] at (9.0, 0) {$r$};

	% ========== 箭头 ==========
	\draw[-stealth, segB, line width=1.5pt] (5.6, -0.7) -- (5.6, -1.5)
		node[midway, right=3pt, font=\small] {去掉};

	% ========== 第二行：分裂结果 ==========
	\node[font=\small\bfseries, anchor=east] at (-0.3, -2.3) {结果：};

	% 段 1：[1, D-1]
	\node[block, fill=segC!25, draw=segC!70] at (1, -2.3) {$1$};
	\node[block, fill=segC!25, draw=segC!70] at (2.2, -2.3) {$2$};
	\node[dot, segC!70] at (3.2, -2.3) {$\cdots$};
	\node[block, fill=segC!25, draw=segC!70] at (4.2, -2.3) {\footnotesize$D\!-\!1$};

	% 空位
	\node[block, fill=gray!10, draw=gray!40, dashed, text=gray] at (5.6, -2.3) {};

	% 段 2：[D+1, r]
	\node[block, fill=segD!20, draw=segD!70] at (7.0, -2.3) {\footnotesize$D\!+\!1$};
	\node[dot, segD!70] at (8.0, -2.3) {$\cdots$};
	\node[block, fill=segD!20, draw=segD!70] at (9.0, -2.3) {$r$};

	% 段标注
	\draw[segC, line width=2.5pt] (0.35, -3.05) -- (4.85, -3.05);
	\node[segC!80!black, font=\footnotesize] at (2.6, -3.4) {$[1,\; D\!-\!1]$};

	\draw[segD, line width=2.5pt] (6.35, -3.05) -- (9.65, -3.05);
	\node[segD!80!black, font=\footnotesize] at (8.0, -3.4) {$[D\!+\!1,\; r]$};

	% 结论
	\node[font=\bfseries] at (5, -4.1)
		{两段之和 $= T_r - D = K$ \checkmark\quad 共 $2$ 次指令};
\end{tikzpicture}
\caption{%
	从 $[1, r]$ 中去掉元素 $D$，区间分裂为 $[1, D\!-\!1]$ 与 $[D\!+\!1, r]$ 两段，总和恰为 $K$。%
}
\label{fig:remove}
\end{figure}

$r \le N$ 由最小性保证（若 $r > N$ 则 $T_r > T_N \ge K$，矛盾）。证毕。

\section{第三层思考：如何判断答案是否为 $1$}

对 $1, 2, \ldots, N$ 这个递增正整数数列，连续子段 $[l, r]$ 的元素和为：
$$S(l, r) = \sum_{i=l}^{r} i = \frac{r(r+1)}{2} - \frac{(l-1) \cdot l}{2}$$

我们需要判断是否存在 $1 \le l \le r \le N$ 使得 $S(l, r) = K$。利用前缀和的单调性，可以用\textbf{双指针}（滑动窗口）在 $O(N)$ 时间内完成判定。

\begin{figure}[H]
	\centering
	\begin{tikzpicture}[scale=0.65, every node/.style={font=\small}]
		% 数轴
		\draw[-stealth, thick] (0,0) -- (11.5,0);
		\foreach \i in {1,...,10} {
			\draw (\i, -0.15) -- (\i, 0.15);
			\node[below=3pt] at (\i, -0.15) {$\i$};
		}
		\node[below=3pt] at (11.2, -0.15) {$\cdots$};

		% 滑动窗口
		\fill[segA!25] (3, 0.3) rectangle (7, 1.1);
		\draw[segA, line width=2pt] (3, 0.3) rectangle (7, 1.1);
		\node[segA, font=\bfseries] at (5, 0.7) {$l = 3,\ r = 7$};

		\draw[decorate, decoration={brace, amplitude=5pt, raise=2pt}]
			(3, 1.1) -- (7, 1.1)
			node[midway, above=7pt] {$3 + 4 + 5 + 6 + 7 = 25$};

		% 指针标注
		\draw[-stealth, segC, thick] (3, -0.8) -- (3, -0.2);
		\node[segC, below] at (3, -0.8) {$l$};
		\draw[-stealth, segD, thick] (7, -0.8) -- (7, -0.2);
		\node[segD, below] at (7, -0.8) {$r$};

		% 右移示意
		\draw[-stealth, gray, thick, dashed] (7.3, 0.7) -- (8.3, 0.7)
			node[right, font=\footnotesize] {和太小则右移 $r$};
		\draw[-stealth, gray, thick, dashed] (3.3, -0.5) -- (4.3, -0.5)
			node[right, font=\footnotesize] {和太大则右移 $l$};
	\end{tikzpicture}
	\caption{双指针在数列 $1, 2, \ldots, N$ 上滑动，寻找和恰好为 $K$ 的连续子段。}
	\label{fig:twopointer}
\end{figure}

代码实现中使用了等价的方式：枚举左端点 $l$，利用前缀和数组的单调性，对目标值 $K + \text{pre}[l-1]$ 进行二分查找，判断其是否恰好等于某个 $\text{pre}[r]$。二分查找与双指针的时间复杂度相同，均为 $O(N)$（二分是 $O(N \log N)$，但不影响最终通过）。

\section{完整算法流程}

\begin{enumerate}
	\item 若 $C \nmid W$，输出 $-1$。
	\item 令 $K \leftarrow W / C$。若 $K = 0$，输出 $0$。
	\item 若 $K > \frac{N(N+1)}{2}$，输出 $-1$。
	\item 用双指针/二分查找判断是否存在连续子段和为 $K$。若存在，输出 $1$。
	\item 否则，输出 $2$。
\end{enumerate}

\section{代码实现}

\begin{minted}{cpp}
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Solve {
	ll N, W, C;
	vector<ll> A;
	vector<ll> preA;

	Solve() {
		cin >> N >> C >> W;
		A.resize(N + 2);
		if (W % C != 0) {
			cout << -1 << "\n";
			return;
		}
		ll chu = W / C;
		if (chu == 0) {
			cout << 0 << "\n";
			return;
		}
		if (chu > (N + 1) * N / 2) {
			cout << -1 << "\n";
			return;
		}
		for (int i = 1; i <= N; ++i)
			A[i] = i;
		preA.resize(N + 2);
		partial_sum(A.begin(), A.end(), preA.begin());

		// 枚举左端点，二分查找右端点
		for (int i = 1; i <= N; ++i) {
			ll tar = chu + preA[i - 1];
			if (binary_search(preA.begin(), preA.end(), tar)) {
				cout << 1 << "\n";
				return;
			}
		}
		// 由构造性证明，此时答案必为 2
		cout << 2 << "\n";
	}
};

signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin >> T;
	while (T--)
		Solve solve;
	return 0;
}
\end{minted}

\section{复杂度分析}

\begin{itemize}
	\item \textbf{时间复杂度}：单组 $O(N \log N)$（枚举 $N$ 个左端点，每次二分 $O(\log N)$）。$T$ 组合计 $O(T \cdot N \log N)$。在 $N \le 10^5$、$T \le 10$ 的范围下约 $1.7 \times 10^7$ 次运算，远低于时限。若使用双指针可进一步优化至单组 $O(N)$。
	\item \textbf{空间复杂度}：$O(N)$，用于存储前缀和数组。
\end{itemize}

\end{document}

PDF

其实在考场上，我通过打表，有点猜出来了这个答案只可能是 -1,0,1,2 ，当然，我肯定也不是那么自信，而且，我也傻了，既然答案只能在这里面取，排除了 1，答案就只可能是 2 了（当然其他特殊情况前面早就搞定了）。

AC代码

AC
https://www.luogu.com.cn/record/273572038

源代码

// teamname: Gospel_rock
/**
 * Problem: P16228 [蓝桥杯 2026 省 A] 读取指令
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P16228?contestId=320702
 * Created: 2026-04-12 01:28:46
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
    ll N, W, C;
    vector<ll> A;
    vector<ll> preA;

    Solve() {
        cin >> N >> C >> W;
        A.resize(N + 2);
        if (W % C != 0) {
            cout << -1 << "\n";
            return;
        }
        ll chu = W / C;
        if (chu == 0) {
            cout << 0 << "\n";
            return;
        }
        if (chu > (N + 1) * N / 2) {
            cout << -1 << "\n";
            return;
        }
        for (int i = 1; i <= N; ++i) {
            A[i] = i;
        }
        preA.resize(N + 2);
        partial_sum(all(A), preA.begin());
#ifdef LOCAL
        debug(chu);
        debug((N + 1) * N / 2);
        debug1d(A);
        debug1d(preA);
#endif
        for (int i = 1; i <= N; ++i) {
            // chu=tar-preA[i-1]
            ll tar = chu + preA[i - 1];
            if (binary_search(all(preA), tar)) {
                cout << 1 << "\n";
                return;
            }
        }
        cout << 2 << "\n";
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve solve;
    return 0;
}

/*
AC
https://www.luogu.com.cn/record/273572038

*/

心路历程（WA，TLE，MLE……）

P16224 [蓝桥杯 2026 省 A] A. 均衡数

Posted on 2026-04-11 Edited on 2026-04-12

题目大意

P16224 [蓝桥杯 2026 省 A] 均衡数

题目描述

如果一个正整数的二进制表示中（无前导 $0$ ）， $1$ 的数量和 $0$ 的数量相同，则我们称其为一个“均衡数”。

现在，请你找到一个均衡数 $x$ ，使得 $|2026202620262026 - x|$ 的值最小。若存在多个均衡数使得 $|2026202620262026 - x|$ 的值相同且最小，则取其中最小的一个。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输入输出样例 #1

输入 #1

输出 #1

思路讲解

说白了，最靠近的就是 50 位最大均衡数和 52 位最小均衡数。

这个是 52 位最小均衡数，比这个 50 位的最大的更接近，故选这个。

1
2
3

>>> bin(2251799847239679)
'0b1000000000000000000000000001111111111111111111111111'
>>>

AC代码

AC
https://www.luogu.com.cn/record/273571661

源代码

// teamname: Gospel_rock
/**
 * Problem: P16224 [蓝桥杯 2026 省 A] 均衡数
 * Contest: 
 * Judge: Luogu
 * URL: https://www.luogu.com.cn/problem/P16224?contestId=320702
 * Created: 2026-04-12 01:08:52
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)    \
cerr << #a << " = [";   \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i]; \
cerr << "]\n";
#define debug2d(a)  \
cerr << #a << " = [\n";  \
for (int i = 0; i < (int)(a).size(); i++)  \
{   \
cerr << "  [";  \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];   \
cerr << "]\n";   \
}  \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT,testcase;

/*
 *
 */

struct Solve {
    // ll N;
    Solve() {
        // cin >> N;
        // cout<<"2251799847239679";
        ll ans=(1ll<<51)+(1ll<<25)-1;
        cout<<ans<<"\n";
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve solve;
    return 0;
}

/*

9003 0271 3419 402

*/