ROJ

题目单

一本通 · 算法提高篇

《信息学奥赛一本通（C++版）》算法提高篇：252 题，本站收录 252（100%）。

简介
《信息学奥赛一本通（C++版）》算法提高篇：252 题，本站收录 252（100%）。
标签
一本通, 教材配套, 刷题计划, 算法提高篇
题目数
252
本站收录
252
来源
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 前缀才能点开。

本篇概览

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

目录

算法提高篇

一、基础算法(提高篇)

第1章 贪心算法

序号 一本通题号 题目名称 ROJ 收录
1 1422 【例题1】活动安排 ROJ 1422
2 1423 【例题2】种树 ROJ 1423
3 1424 【例题3】喷水装置 ROJ 1424
4 1425 【例题4】加工生产调度 ROJ 1425
5 1426 【例题5】智力大冲浪 ROJ 1426
6 1427 数列极差 ROJ 1427
7 1428 数列分段 ROJ 1428
8 1429 线段 ROJ 1429
9 1430 家庭作业 ROJ 1430
10 1431 钓鱼 ROJ 1431
11 1432 糖果传递 ROJ 1432

第2章 二分与三分

序号 一本通题号 题目名称 ROJ 收录
1 1433 【例题1】愤怒的牛 ROJ 1433
2 1434 【例题2】Best Cow Fences ROJ 1434
3 1435 【例题3】曲线 ROJ 1435
4 1436 数列分段II ROJ 1436
5 1437 扩散 ROJ 1437
6 1438 灯泡 ROJ 1438
7 1439 【SCOI2010】传送带 ROJ 1439

第3章 深搜的剪枝技巧

序号 一本通题号 题目名称 ROJ 收录
1 1440 【例题1】数的划分 ROJ 1440
2 1441 【例题2】生日蛋糕 ROJ 1441
3 1442 【例题3】小木棍 ROJ 1442
4 1443 【例题4】Addition Chains ROJ 1443
5 1444 埃及分数 ROJ 1444
6 1445 平板涂色 ROJ 1445
7 1446 素数方阵 ROJ 1446（ROJ 题名：「一本通 1.3 练习 3」质数方阵）
8 1447 靶形数独 ROJ 1447

第4章 广搜的优化技巧

序号 一本通题号 题目名称 ROJ 收录
1 1448 【例题1】电路维修 ROJ 1448
2 1449 【例题2】魔板 ROJ 1449
3 1450 【例 3】Knight Moves ROJ 1450
4 1451 棋盘游戏 ROJ 1451
5 1452 Keyboarding ROJ 1452
6 1453 移动玩具 ROJ 1453
7 1454 山峰和山谷 ROJ 1454

二、字符串算法(提高篇)

第1章 哈希和哈希表

序号 一本通题号 题目名称 ROJ 收录
1 1455 【例题1】Oulipo ROJ 1455
2 1456 【例题2】图书管理 ROJ 1456
3 1457 Power Strings ROJ 1457
4 1458 Seek the Name, Seek the Fame ROJ 1458
5 1459 friends ROJ 1459（ROJ 题名：「一本通 2.1 练习 3」Friends）
6 1460 A Horrible Poem ROJ 1460
7 1461 Beads ROJ 1461
8 1462 Antisymmetry ROJ 1462
9 1463 门票 ROJ 1463
10 1464 收集雪花 ROJ 1464

第2章 KMP算法

序号 一本通题号 题目名称 ROJ 收录
1 1465 【例题1】剪花布条 ROJ 1465
2 1466 【例题2】Power Strings ROJ 1466
3 1467 Radio Transmission ROJ 1467
4 1468 OKR-Periods of Words ROJ 1468
5 1469 似乎在梦中见过的样子 ROJ 1469
6 1470 Censoring ROJ 1470

第3章 trie字典树

序号 一本通题号 题目名称 ROJ 收录
1 1471 【例题1】Phone List ROJ 1471
2 1472 【例题2】The XOR Largest Pair ROJ 1472
3 1473 【例题3】Codechef REBXOR ROJ 1473（ROJ 题名：「一本通 2.3 例 3」Nikitosh 和异或）
4 1474 Immediate Decodability ROJ 1474
5 1475 L语言 ROJ 1475
6 1476 Secret Message 秘密信息 ROJ 1476
7 1477 【SCOI2016】背单词 ROJ 1477
8 1478 The xor-longest Path ROJ 1478（ROJ 题名：「一本通 2.3 练习 5」The Xor-longest Path）

第4章 AC自动机

序号 一本通题号 题目名称 ROJ 收录
1 1479 【例题1】Keywords Search ROJ 1479
2 1480 玄武密码 ROJ 1480
3 1481 Censoring ROJ 1481
4 1482 单词 ROJ 1482
5 1483 最短母串 ROJ 1483
6 1484 病毒 ROJ 1484
7 1485 文本生成器 ROJ 1485

三、图论(提高篇)

第1章 最小生成树

序号 一本通题号 题目名称 ROJ 收录
1 1486 【例题1】黑暗城堡 ROJ 1486
2 1487 【例 2】北极通讯网络 ROJ 1487
3 1488 新的开始 ROJ 1488
4 1489 构造完全图 ROJ 1489
5 1490 秘密的牛奶运输 ROJ 1490
6 1491 Tree ROJ 1491
7 1492 最小生成树计数 ROJ 1492
8 1493 次小生成树 ROJ 1493

第2章 最短路问题

序号 一本通题号 题目名称 ROJ 收录
1 1494 【例 1】Sightseeing Trip ROJ 1494
2 1495 【例 2】孤岛营救问题 ROJ 1495（ROJ 题名：「一本通 3.2 例 2」拯救大兵瑞恩）
3 1496 【例 3】架设电话线 ROJ 1496
4 1497 农场派对 ROJ 1497
5 1498 Roadblocks ROJ 1498
6 1499 最短路计数 ROJ 1499
7 1500 新年好 ROJ 1500
8 1501 最优贸易 ROJ 1501
9 1502 汽车加油行驶问题 ROJ 1502（ROJ 题名：「一本通 3.2 练习 6」汽车加油行驶）
10 1503 道路和航线 ROJ 1503

第3章 SPFA算法优化

序号 一本通题号 题目名称 ROJ 收录
1 1504 【例 1】Word Rings ROJ 1504
2 1505 【例 2】双调路径 ROJ 1505
3 1506 最小圈 ROJ 1506
4 1507 虫洞 Wormholes ROJ 1507（ROJ 题名：「一本通 3.3 练习 2」虫洞）
5 1508 Easy SSSP ROJ 1508

第4章 差分约束系统

序号 一本通题号 题目名称 ROJ 收录
1 1509 【例 1】Intervals ROJ 1509
2 1510 【例 2】出纳员问题 ROJ 1510
3 1511 【SCOI2011】糖果 ROJ 1511
4 1512 排队布局 ROJ 1512

第5章 强连通分量

序号 一本通题号 题目名称 ROJ 收录
1 1513 【 例 1】受欢迎的牛 ROJ 1513
2 1514 【例 2】最大半连通子图 ROJ 1514
3 1515 网络协议 ROJ 1515
4 1516 消息的传递 ROJ 1516
5 1517 间谍网络 ROJ 1517
6 1518 抢掠计划 ROJ 1518
7 1519 和平委员会 ROJ 1519

第6章 割点和桥

序号 一本通题号 题目名称 ROJ 收录
1 1520 【 例 1】分离的路径 ROJ 1520
2 1521 【 例 2】矿场搭建 ROJ 1521
3 1522 网络 ROJ 1522
4 1523 嗅探器 ROJ 1523
5 1524 旅游航道 ROJ 1524
6 1525 电力 ROJ 1525
7 1526 Blockade ROJ 1526

第7章 欧拉回路

序号 一本通题号 题目名称 ROJ 收录
1 1527 【例 1】欧拉回路 ROJ 1527
2 1528 【例 2】单词游戏 ROJ 1528
3 1529 欧拉回路 ROJ 1529
4 1530 Ant Trip ROJ 1530
5 1531 John‘s Trip ROJ 1531（ROJ 题名：「一本通 3.7 练习 3」John’s Trip）
6 1532 太鼓达人 ROJ 1532
7 1533 相框 ROJ 1533
8 1534 原始生物 ROJ 1534

四、数据结构(提高篇)

第1章 树状数组

序号 一本通题号 题目名称 ROJ 收录
1 1535 【例 1】数列操作 ROJ 1535
2 1536 【例 2】数星星 Stars ROJ 1536
3 1537 【例 3】校门外的树 ROJ 1537
4 1538 清点人数 ROJ 1538
5 1539 简单题 ROJ 1539
6 1540 打鼹鼠_二维树状数组 ROJ 1540（ROJ 题名：「一本通 4.1 练习 3」打鼹鼠）

第2章 RMQ 问题

序号 一本通题号 题目名称 ROJ 收录
1 1541 【例 1】数列区间最大值 ROJ 1541
2 1542 【例 2】最敏捷的机器人 ROJ 1542
3 1543 【例 3】与众不同 ROJ 1543
4 1544 天才的记忆 ROJ 1544
5 1545 Balanced Lineup ROJ 1545（ROJ 题名：「一本通 4.2 练习 2」奶牛排队 Balanced Lineup）
6 1546 NOIP2011 选择客栈 ROJ 1546（ROJ 题名：「一本通 4.2 练习 3」选择客栈）

第3章 线段树

序号 一本通题号 题目名称 ROJ 收录
1 1547 【 例 1】区间和 ROJ 1547
2 1548 【例 2】A Simple Problem with Integers ROJ 1548
3 1549 最大数 ROJ 1549
4 1550 花神游历各国 ROJ 1550
5 1551 维护序列 ROJ 1551
6 1992 书架book ROJ 1992
7 1993 开关switch ROJ 1993
8 1994 音乐会 ROJ 1994

第4章 倍增求 LCA

序号 一本通题号 题目名称 ROJ 收录
1 1552 【例 1】点的距离 ROJ 1552
2 1553 【例 2】暗的连锁 ROJ 1553
3 1554 【例 3】异象石 ROJ 1554
4 1555 【例 4】次小生成树 ROJ 1555
5 1556 Dis ROJ 1556
6 1557 祖孙询问 ROJ 1557
7 1558 聚会 ROJ 1558
8 1559 跳跳棋 ROJ 1559

第5章 树链剖分

序号 一本通题号 题目名称 ROJ 收录
1 1560 【例 1】树的统计 ROJ 1560
2 1561 「HAOI2015」树上操作 ROJ 1561
3 1562 「NOI2015」软件包管理器 ROJ 1562
4 1563 染色 ROJ 1563
5 1564 「SDOI2014」旅行 ROJ 1564

第6章 平衡树 Treap

序号 一本通题号 题目名称 ROJ 收录
1 1565 【例 1】营业额统计 ROJ 1565
2 1566 宠物收养所 ROJ 1566
3 1567 郁闷的出纳员 ROJ 1567
4 1568 普通平衡树 ROJ 1568

五、动态规划(提高篇)

第1章 区间类动态规划

序号 一本通题号 题目名称 ROJ 收录
1 1569 【 例 1】石子合并 ROJ 1569
2 1570 【例 2】能量项链 ROJ 1570
3 1571 【例 3】凸多边形的划分 ROJ 1571
4 1572 括号配对 ROJ 1572
5 1573 分离与合体 ROJ 1573
6 1574 矩阵取数游戏 ROJ 1574

第2章 树型动态规划

序号 一本通题号 题目名称 ROJ 收录
1 1575 【例 1】二叉苹果树 ROJ 1575
2 1576 【例 2】选课 ROJ 1576
3 1577 【例 3】数字转换 ROJ 1577
4 1578 【例 4】战略游戏 ROJ 1578
5 1579 【例 5】皇宫看守 ROJ 1579
6 1580 加分二叉树 ROJ 1580
7 1581 旅游规划 ROJ 1581
8 1582 周年纪念晚会 ROJ 1582
9 1583 叶子的染色 ROJ 1583（ROJ 题名：「一本通 5.2 练习 4」叶子的颜色）
10 1584 骑士 ROJ 1584

第3章 数位动态规划

序号 一本通题号 题目名称 ROJ 收录
1 1585 【例 1】Amount of Degrees ROJ 1585
2 1586 【 例 2】数字游戏 ROJ 1586
3 1587 【例 3】Windy 数 ROJ 1587
4 1588 数字游戏 ROJ 1588
5 1589 不要 62 ROJ 1589
6 1590 恨 7 不成妻 ROJ 1590
7 1591 数字计数 ROJ 1591

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

序号 一本通题号 题目名称 ROJ 收录
1 1592 【例 1】国王 ROJ 1592（ROJ 题名：「一本通 5.4 例 1」骑士）
2 1593 【例 2】牧场的安排 ROJ 1593
3 1594 涂抹果酱 ROJ 1594
4 1595 炮兵阵地 ROJ 1595
5 1596 动物园 ROJ 1596

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

序号 一本通题号 题目名称 ROJ 收录
1 1597 【 例 1】滑动窗口 ROJ 1597
2 1598 【 例 2】最大连续和 ROJ 1598
3 1599 【 例 3】修剪草坪 ROJ 1599
4 1600 【例 4】旅行问题 ROJ 1600
5 1601 【例 5】Banknotes ROJ 1601
6 1602 烽火传递 ROJ 1602
7 1603 绿色通道 ROJ 1603
8 1604 理想的正方形 ROJ 1604
9 1605 股票交易 ROJ 1605

第6章 斜率优化动态规划

序号 一本通题号 题目名称 ROJ 收录
1 1606 【 例 1】任务安排 1 ROJ 1606
2 1607 【 例 2】任务安排 2 ROJ 1607
3 1608 【 例 3】任务安排 3 ROJ 1608
4 1609 【例 4】Cats Transport ROJ 1609
5 1610 玩具装箱 ROJ 1610
6 1611 仓库建设 ROJ 1611
7 1612 特别行动队 ROJ 1612
8 1613 打印文章 ROJ 1613
9 1614 锯木厂选址 ROJ 1614

六、数学基础(提高篇)

第1章 快速幂

序号 一本通题号 题目名称 ROJ 收录
1 1615 【例 1】序列的第 k 个数 ROJ 1615（ROJ 题名：「一本通 6.1 例 1」序列的### 第 k 个数）
2 1616 A 的 B 次方 ROJ 1616
3 1617 转圈游戏 ROJ 1617
4 1618 越狱 ROJ 1618

第2章 质数

序号 一本通题号 题目名称 ROJ 收录
1 1619 【例 1】Prime Distance ROJ 1619
2 1620 质因数分解 ROJ 1620
3 1621 轻拍牛头 ROJ 1621
4 1622 Goldbach’s Conjecture ROJ 1622（ROJ 题名：「一本通 6.2 练习 3」Goldbach’s Conjecture）
5 1623 Sherlock and His Girlfriend ROJ 1623
6 1624 樱花 ROJ 1624

第3章 约数

序号 一本通题号 题目名称 ROJ 收录
1 1625 【例 1】反素数 Antiprime ROJ 1625
2 1626 【例 2】Hankson 的趣味题 ROJ 1626
3 1627 【例 3】最大公约数 ROJ 1627
4 1628 X-factor Chain ROJ 1628
5 1629 聪明的燕姿 ROJ 1629
6 1630 SuperGCD ROJ 1630

第4章 同余问题

序号 一本通题号 题目名称 ROJ 收录
1 1631 【例 1】青蛙的约会 ROJ 1631
2 1632 【 例 2】[NOIP2012]同余方程 ROJ 1632
3 1633 【例 3】Sumdiv ROJ 1633
4 1634 【例 4】曹冲养猪 ROJ 1634
5 1635 【例 5】Strange Way to Express Integers ROJ 1635
6 1636 【例 6】计算器 ROJ 1636
7 1637 荒岛野人 ROJ 1637
8 1638 五指山 ROJ 1638
9 1639 Biorhythms ROJ 1639
10 1640 C Looooops ROJ 1640

第5章 矩阵乘法

序号 一本通题号 题目名称 ROJ 收录
1 1641 【例 1】矩阵 A×B ROJ 1641
2 1642 【例 2】Fibonacci 第 n 项 ROJ 1642（ROJ 题名：「一本通 6.5 例 2」Fibonacci ### 第 n 项）
3 1643 【例 3】Fibonacci 前 n 项和 ROJ 1643
4 1644 【例 4】佳佳的 Fibonacci ROJ 1644
5 1645 Fibonacci ROJ 1645
6 1646 GT 考试 ROJ 1646
7 1647 迷路 ROJ 1647

第6章 组合数学

序号 一本通题号 题目名称 ROJ 收录
1 1648 【例 1】「NOIP2011」计算系数 ROJ 1648
2 1649 【例 2】2^k 进制数 ROJ 1649
3 1650 【例 3】组合 ROJ 1650
4 1651 【例 4】古代猪文 ROJ 1651
5 1652 牡牛和牝牛 ROJ 1652（ROJ 题名：「一本通 6.6 练习 1」牡牛和牝）
6 1653 方程的解 ROJ 1653
7 1654 车的放置 ROJ 1654
8 1655 数三角形 ROJ 1655
9 1656 Combination ROJ 1656
10 1657 序列统计 ROJ 1657
11 1658 超能粒子炮 · 改 ROJ 1658
12 1659 礼物 ROJ 1659
13 1660 网格 ROJ 1660
14 1661 有趣的数列 ROJ 1661
15 1662 树屋阶梯 ROJ 1662

第7章 博弈论

序号 一本通题号 题目名称 ROJ 收录
1 1663 【 例 1】取石子游戏 1 ROJ 1663
2 1664 【例 2】取石子游戏 2 ROJ 1664
3 1665 【例 3】移棋子游戏 ROJ 1665
4 1666 取石子游戏 ROJ 1666
5 1667 巧克力棒 ROJ 1667
6 1668 取石子 ROJ 1668
7 1669 S-Nim ROJ 1669
8 1670 取石子游戏 ROJ 1670

附录 A：同题异号对照

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

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

（无）

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

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

（无）

数据来源与更新

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