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

题目大意

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

3
4 2 10
4 2 16
4 2 7

输出 #1

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……）