题目单

一本通 · 高手训练篇

《信息学奥赛一本通（C++版）》高手训练篇：149 题，本站收录 149（100%）。

简介: 《信息学奥赛一本通（C++版）》高手训练篇：149 题，本站收录 149（100%）。
标签: 一本通, 教材配套, 刷题计划, 高手训练篇
题目数: 149
本站收录: 149
来源: https://ybt.ssoier.cn/index.php

本单进度

正在读取进度…

按《信息学奥赛一本通（C++版）》在线题库 ybt.ssoier.cn 左侧「题库全部题目分类索引」整理的 高手训练篇，可对照原书顺序刷题。

怎么用这份单子

一本通题号 链接到一本通原题页；ROJ 收录 列是站内链接，在本站点开直接看题面；
ROJ 列为 — 表示 ROJ 暂未收录这道题（仍可去一本通原站做）；
括号里标注「ROJ 题名」的，表示 ROJ 侧题目名称与一本通不同（多为改名/换译），题面是同一道题；
附录 A 列出 ROJ 中『同题不同编号』的情况，分「已核对」「待核对」两档可信度；
一本通题目单共 5 篇（C++编程语言 / 基础算法 / 数据结构基础 / 算法提高篇 / 高手训练篇），可在题目单列表里切换；勾选进度在站内按题号全局共享，跨篇不会丢；
在 GitHub 上阅读时，/problem/… 是站内路径，需补上 https://roj.ac.cn 前缀才能点开。

本篇概览

本篇 149 题，本站收录 149（100%）；一本通题目单共 5 篇、895 题。

目录

一、基础算法(高手训练)
二、字符串算法(高手训练)
三、图论(高手训练)
四、数据结构(高手训练)
五、动态规划(高手训练)
六、数学基础(高手训练)
附录 A：同题异号对照

高手训练篇

一、基础算法(高手训练)

第1章贪心算法

序号	一本通题号	题目名称	ROJ 收录
1	1671	扑克牌	ROJ 5007（ROJ 题号 5007）
2	1672	游戏通关	ROJ 5008（ROJ 题号 5008）
3	1673	楼间跳跃	ROJ 5009（ROJ 题号 5009）
4	1674	堆蛋糕	ROJ 5010（ROJ 题号 5010）
5	1675	塔	ROJ 5011（ROJ 题号 5011）

第2章二分与三分

序号	一本通题号	题目名称	ROJ 收录
1	1676	手机游戏	ROJ 5012（ROJ 题号 5012）
2	1677	软件开发	ROJ 5013（ROJ 题号 5013）
3	1678	独木桥	ROJ 5014（ROJ 题号 5014）
4	1679	子集	ROJ 5015（ROJ 题号 5015）
5	1680	序列	ROJ 5016（ROJ 题号 5016）

第3章深搜

序号	一本通题号	题目名称	ROJ 收录
1	1681	统计方案	ROJ 5017（ROJ 题号 5017）
2	1682	最小字典序	ROJ 1682
3	1683	稗田阿求	ROJ 1683
4	1684	翻转序列	ROJ 1684
5	1685	新版方格取数	ROJ 1685

第4章广搜

序号	一本通题号	题目名称	ROJ 收录
1	1686	最小操作次数	ROJ 1686
2	1687	积水问题	ROJ 1687
3	1688	最优路径	ROJ 1688
4	1689	堆排问题	ROJ 1689
5	1690	棋盘问题	ROJ 1690

二、字符串算法(高手训练)

第1章哈希表

序号	一本通题号	题目名称	ROJ 收录
1	1691	文章评分	ROJ 1691
2	1692	字符串编码	ROJ 1692
3	1693	正确答案	ROJ 1693
4	1694	回文串	ROJ 1694
5	1695	独特的树叶	ROJ 1695

第2章 KMP算法

序号	一本通题号	题目名称	ROJ 收录
1	1696	前缀和	ROJ 1696
2	1697	深意	ROJ 1697
3	1698	字符串匹配	ROJ 1698
4	1699	石环	ROJ 1699

第3章 Trie树

序号	一本通题号	题目名称	ROJ 收录
1	1700	PFS集合	ROJ 1700
2	1701	最大值	ROJ 1701
3	1702	异或运算	ROJ 1702
4	1703	量子纠缠	ROJ 1703
5	1704	奇特的猫	ROJ 1704

第4章 AC自动机

序号	一本通题号	题目名称	ROJ 收录
1	1705	DNA序列	ROJ 1705
2	1706	串包含问题	ROJ 1706
3	1707	敲键盘	ROJ 1707
4	1708	无限链计数	ROJ 1708
5	1709	寻找好串	ROJ 1709

三、图论(高手训练)

第1章最小生成树

序号	一本通题号	题目名称	ROJ 收录
1	1710	构造完全图	ROJ 1710
2	1711	最小花费	ROJ 1711
3	1712	汉堡店	ROJ 1712
4	1713	生成树	ROJ 1713
5	1714	地壳运动	ROJ 1714

第2章最短路径

序号	一本通题号	题目名称	ROJ 收录
1	1715	公交旅行	ROJ 1715
2	1716	次短路计数	ROJ 1716
3	1717	负环	ROJ 1717
4	1718	益智游戏	ROJ 1718
5	1719	过河	ROJ 1719

第3章 SPFA算法的优化

序号	一本通题号	题目名称	ROJ 收录
1	1720	均值最小环	ROJ 1720
2	1721	最小边权和	ROJ 1721
3	1722	骑士游戏	ROJ 1722
4	1723	交通	ROJ 1723

第4章差分约束系统

序号	一本通题号	题目名称	ROJ 收录
1	1724	小K的农场	ROJ 1724
2	1725	账本核算	ROJ 1725
3	1726	矩阵	ROJ 1726
4	1727	魔棒	ROJ 1727
5	1728	构造序列	ROJ 1728

第5章强连通分量

序号	一本通题号	题目名称	ROJ 收录
1	1729	魔法石	ROJ 1729
2	1730	二分图	ROJ 1730
3	1731	最大流	ROJ 1731
4	1732	情报传递	ROJ 1732
5	1733	连续数字区间	ROJ 1733

第6章割点和桥

序号	一本通题号	题目名称	ROJ 收录
1	1734	删边问题	ROJ 1734
2	1735	环上计数	ROJ 1735
3	1736	最大连通块	ROJ 1736

第7章欧拉回路

序号	一本通题号	题目名称	ROJ 收录
1	1737	邮递员	ROJ 1737
2	1738	圆桌聚会	ROJ 1738
3	1739	观光巴士	ROJ 1739
4	1740	星空穿越	ROJ 1740

四、数据结构(高手训练)

第1章树状数组

序号	一本通题号	题目名称	ROJ 收录
1	1741	电子速度	ROJ 1741
2	1742	导线问题	ROJ 1742
3	1743	数羊	ROJ 1743
4	1744	跳台阶	ROJ 1744
5	1745	分组	ROJ 1745

第2章 RMQ问题

序号	一本通题号	题目名称	ROJ 收录
1	1746	矩阵最值	ROJ 1746
2	1747	奶牛排队	ROJ 1747
3	1748	大数计数	ROJ 1748
4	1749	矩阵求和	ROJ 1749
5	1750	取数字	ROJ 1750

第3章线段树

序号	一本通题号	题目名称	ROJ 收录
1	1751	字符串排序	ROJ 1751
2	1752	纪念碑	ROJ 1752
3	1753	区间连通性	ROJ 1753
4	1754	栈的维护	ROJ 1754
5	1755	星际探测	ROJ 1755

第4章倍增求LCA

序号	一本通题号	题目名称	ROJ 收录
1	1756	过路费	ROJ 1756
2	1757	避难向导	ROJ 1757
3	1758	连通能力	ROJ 1758
4	1759	采访计划	ROJ 1759
5	1760	树上数颜色	ROJ 1760

第5章树链剖分

序号	一本通题号	题目名称	ROJ 收录
1	1761	最小割	ROJ 1761
2	1762	与非	ROJ 1762
3	1763	简单树	ROJ 1763
4	1764	社会送温暖	ROJ 1764
5	1765	树上斐波那契	ROJ 1765

五、动态规划(高手训练)

第1章区间类动态规划

序号	一本通题号	题目名称	ROJ 收录
1	1766	成绩单	ROJ 1766
2	1767	字符合并	ROJ 1767
3	1768	交换	ROJ 1768
4	1769	景中人	ROJ 1769
5	1770	跳跳棋	ROJ 1770

第2章树形动态规划

序号	一本通题号	题目名称	ROJ 收录
1	1771	仓库选址	ROJ 1771
2	1772	动漫排序	ROJ 1772
3	1773	消息传递	ROJ 1773
4	1774	大逃杀	ROJ 1774
5	1775	梦中漫步	ROJ 1775

第3章数位动态规划

序号	一本通题号	题目名称	ROJ 收录
1	1776	最大值	ROJ 1776
2	1777	寻找整数	ROJ 1777
3	1778	好数字	ROJ 1778
4	1779	第K小数	ROJ 1779
5	1780	修墙	ROJ 1780

第4章状态压缩类动态规划

序号	一本通题号	题目名称	ROJ 收录
1	1781	死亡之树	ROJ 1781
2	1782	分层图	ROJ 1782
3	1783	矩阵填数	ROJ 1783
4	1784	山谷	ROJ 1784
5	1785	简单的期望	ROJ 1785

第5章单调队列优化动态规划

序号	一本通题号	题目名称	ROJ 收录
1	1786	01背包	ROJ 1786
2	1787	保龄球	ROJ 1787
3	1788	爬山	ROJ 1788
4	1789	分班	ROJ 1789
5	1790	序列划分	ROJ 1790

第6章斜率优化动态规划

序号	一本通题号	题目名称	ROJ 收录
1	1791	太空飞船	ROJ 1791
2	1792	小P的牧场	ROJ 1792
3	1793	鏖战字符串	ROJ 1793
4	1794	分数	ROJ 1794

六、数学基础(高手训练)

第1章快速幂矩乘

序号	一本通题号	题目名称	ROJ 收录
1	1795	散步	ROJ 1795
2	1796	斐波那契串	ROJ 1796
3	1797	K维斐波那契	ROJ 1797
4	1798	递推数列	ROJ 1798
5	1799	数列	ROJ 1799

第2章素数约数

序号	一本通题号	题目名称	ROJ 收录
1	1800	质数	ROJ 1800
2	1801	异或	ROJ 1801
3	1802	寿司晚宴	ROJ 1802
4	1803	列数字	ROJ 1803
5	1804	最大真因数	ROJ 1804

第3章同余问题

序号	一本通题号	题目名称	ROJ 收录
1	1805	数数	ROJ 1805
2	1806	计算器	ROJ 1806
3	1807	区间计数	ROJ 1807
4	1808	斐波那契数列	ROJ 1808
5	1809	日食	ROJ 1809

4章组合数学

序号	一本通题号	题目名称	ROJ 收录
1	1810	登山	ROJ 1810
2	1811	多项式相乘	ROJ 1811
3	1812	网格	ROJ 1812
4	1813	图的计数	ROJ 1813
5	1814	方格染色	ROJ 1814

第5章博弈论

序号	一本通题号	题目名称	ROJ 收录
1	1815	放石子	ROJ 1815
2	1816	取石子	ROJ 1816
3	1817	染色游戏	ROJ 1817
4	1818	树上取石子	ROJ 1818
5	1819	字符串游戏	ROJ 1819

附录 A：同题异号对照

下表的题目在本篇中没有同题号的记录，但 ROJ 的其他题号下可能有同一道题（同一道经典题被多个题库收录、题号各不相同）。做题时任选其一即可。

A.1 已核对（同一场真题，年份与组别一致）

（无）

A.2 待核对（题目同名）

同名不等于同题（比如两本书里都有叫「最大公约数」的题），刷题前请先对照题面。

（无）

数据来源与更新

分类树与题目标题抓取自 ybt.ssoier.cn（快照：scripts/ybt_catalog.json）；ROJ 收录情况取自本仓库 problems/*/config.json。
表格区（ 与  之间）由 python3 scripts/gen_ybt_list.py 重新生成，引言、笔记等区块外内容可手工修改。