《深入浅出程序设计竞赛 - 进阶篇》题单

警策看取 · 2022-04-03 15:59:49 · 个人记录

由于学业压力与实际原因，并没有标注难度、例题题号的对应，但保证所有题目按照书中顺序出现。

第18章由于洛谷爬虫、未收录、不在洛谷可提交范围内等综合原因，缺少4题。该问题无法解决，除非洛谷的爬虫更新。

如果您发现了一题并不属于该板块的题，那应该是我搞错了，请联系我。

源码

《深入浅出程序设计竞赛 - 进阶篇》题目列表

第一部分进阶技巧与思想

第一章常见优化列表

例题

P1102 A-B 数对
P1638 逛画展
P1115 最大子段和
P7072 [CSP-J2020] 直播获奖
P2671 [NOIP2015 普及组] 求和
P4147 玉蟾宫
P2866 [USACO06NOV]Bad Hair Day S
P1950 长方形
P2032 扫描
P2216 [HAOI2007]理想的正方形
习题
UVA11572 唯一的雪花 Unique Snowflakes
P4653 [CEOI2017]Sure Bet
P3143 [USACO16OPEN] Diamond Collector S
P7910 [CSP-J 2021] 插入排序
P1578 奶牛浴场
P3467 [POI2008]PLA-Postering
P1886 滑动窗口 /【模板】单调队列
P2880 [USACO07JAN] Balanced Lineup G
P1714 切蛋糕
P1725 琪露诺

第二章前缀和、差分与离散化

例题

B3612 【深进1.例1】求区间和
P1719 最大加权矩形
P1314 [NOIP2011 提高组] 聪明的质监员
P2367 语文成绩
P3397 地毯
P1496 火烧赤壁
P1955 [NOI2015] 程序自动分析
P1884 [USACO12FEB]Overplanting S
习题
P2004 领地选择
P3017 [USACO11MAR]Brownie Slicing G
P3406 海底高铁
P1083 [NOIP2012 提高组] 借教室
P2882 [USACO07MAR]Face The Right Way G
P4552 [Poetize6] IncDec Sequence
P3029 [USACO11NOV]Cow Lineup S
P1904 天际线
P4375 [USACO18OPEN]Out of Sorts G
P5937 [CEOI1999]Parity Game

第三章分治与倍增

例题

P1177 【模板】快速排序
P1908 逆序对
P1966 [NOIP2013 提高组] 火柴排队
P1226 【模板】快速幂||取余运算
P1045 [NOIP2003 普及组] 麦森数
P1115 最大子段和
P2880 [USACO07JAN] Balanced Lineup G
P7167 [eJOI 2020 Day1] Fountain
习题
P2415 集合求和
P1257 平面上的最接近点对
P1228 地毯填补问题
P2345 [USACO04OPEN] MooFest G
P3509 [POI2010]ZAB-Frog
P3517 [POI2011]WYK-Plot
P4155 [SCOI2015]国旗计划
P1816 忠诚
P6648 [CCC 2019] Triangle: The Data Structure
P7562 [JOISC 2021 Day4] イベント巡り 2 (Event Hopping 2)

第四章进阶搜索

例题

P1036 [NOIP2002 普及组] 选数
P1433 吃奶酪
P1120 小木棍
P1763 埃及分数
CF525E Anya and Cubes
P1379 八数码难题
P5507 机关
P2324 [SCOI2005]骑士精神
习题
P1074 [NOIP2009 提高组] 靶形数独
P1312 [NOIP2011 提高组] Mayan 游戏
P3959 [NOIP2017 提高组] 宝藏
P2960 [USACO09OCT]Invasion of the Milkweed G
CF912E Prime Gift
P2346 四子连棋
P4799 [CEOI2015 Day2]世界冰球锦标赛
P2483 【模板】k 短路 / [SDOI2010] 魔法猪学院
P1078 [NOIP2012 普及组] 文化之旅

第二部分进阶数据结构

第五章二叉堆

例题

P3378 【模板】堆
P1177 【模板】快速排序
P1090 [NOIP2004 提高组] 合并果子 / [USACO06NOV] Fence Repair G
P2168 [NOI2015] 荷马史诗
P2827 [NOIP2016 提高组] 蚯蚓
习题
P1801 黑匣子
P1168 中位数
P1631 序列合并
P4053 [JSOI2007]建筑抢修
P2085 最小函数值
P2278 [HNOI2003]操作系统

第六章线段树

例题

P3372 【模板】线段树 1
P3870 [TJOI2009] 开关
P1438 无聊的数列
P1253 [yLOI2018] 扶苏的问题
P3373 【模板】线段树 2
P4513 小白逛公园
P1908 逆序对
习题
P1816 忠诚
P1471 方差
P6492 [COCI2010-2011#6] STEP
P1637 三元上升子序列
P1558 色板游戏
P5522 [yLOI2019] 棠梨煎雪
P4145 上帝造题的七分钟 2 / 花神游历各国
P2572 [SCOI2010] 序列操作
CF19D Points

第七章树状数组与字典树

例题

P3374 【模板】树状数组 1
P3368 【模板】树状数组 2
P1908 逆序对
P1481 魔族密码
P2580 于是他错误的点名开始了
P4551 最长异或路径
P5283 [十二省联考 2019] 异或粽子
习题
P1966 [NOIP2013 提高组] 火柴排队
P5677 [GZOI2017]配对统计
P2161 [SHOI2009]会场预约
P3586 [POI2015] LOG
P2922 [USACO08DEC]Secret Message G
P3879 [TJOI2010] 阅读理解
P4592 [TJOI2018]异或
P3369 【模板】普通平衡树

第八章线段树的进阶用法

例题

P3834 【模板】可持久化线段树 2
P4587 [FJOI2016]神秘数
P3380 【模板】二逼平衡树（树套树）
P3810 【模板】三维偏序（陌上花开）
习题
P4093 [HEOI2016/TJOI2016]序列
P3157 [CQOI2011]动态逆序对
P3293 [SCOI2016]美味
CF960F Pathwalks
P2617 Dynamic Rankings
P3168 [CQOI2015]任务查询系统

第三部分图论

第九章树

例题

P5908 猫猫和企鹅
P1099 [NOIP2007 提高组] 树网的核
P1364 医院设置
P3379 【模板】最近公共祖先（LCA）
P3128 [USACO15DEC]Max Flow P
习题
P2052 [NOI2011] 道路修建
P5666 [CSP-S2019] 树的重心
P5588 小猪佩奇爬树
P5536 【XR-3】核心城市
P5836 [USACO19DEC]Milk Visits S
P1351 [NOIP2014 提高组] 联合权值
P4408 [NOI2003] 逃学的小孩
P3398 仓鼠找 sugar
P2680 [NOIP2015 提高组] 运输计划
P1600 [NOIP2016 提高组] 天天爱跑步

第十章最短路

例题

P3371 【模板】单源最短路径（弱化版）
P4568 [JLOI2011]飞行路线
P1629 邮递员送信
P3385 【模板】负环
P5960 【模板】差分约束算法
P2865 [USACO06NOV]Roadblocks G
P2910 [USACO08OPEN]Clear And Present Danger S
B3611 【模板】传递闭包
习题
P1144 最短路计数
P1875 佳佳的魔法药水
P1462 通往奥格瑞玛的道路
P1073 [NOIP2009 提高组] 最优贸易
P1993 小 K 的农场
P3275 [SCOI2011]糖果
P6464 传送门
P3403 跳楼机
P1119 灾后重建
P1037 [NOIP2002 普及组] 产生数
P2419 [USACO08JAN]Cow Contest S
P2047 [NOI2007] 社交网络

第十一章最小生成树

例题

P3366 【模板】最小生成树
P1194 买礼物
CF472D Design Tutorial: Inverse the Problem
P4180 [BJWC2010]严格次小生成树
习题
P1396 营救
P1195 口袋的天空
P1550 [USACO08OCT]Watering Hole G
P1967 [NOIP2013 提高组] 货车运输
P2700 逐个击破
CF1245D Shichikuji and Power Grid
P3623 [APIO2008]免费道路
CF1120D Power Tree

第十二章连通性问题

例题

P1656 炸铁路
P2860 [USACO06JAN]Redundant Paths G
P3388 【模板】割点（割顶）
P4630 [APIO2018] Duathlon 铁人两项
P2863 [USACO06JAN]The Cow Prom S
P3387 【模板】缩点
习题
CF1000E We Need More Bosses
P3469 [POI2008]BLO-Blockade
P4606 [SDOI2018]战略游戏
CF487E Tourists
P1262 间谍网络
P2341 [USACO03FALL / HAOI2006] 受欢迎的牛 G
P5025 [SNOI2017]炸弹
P3825 [NOI2017] 游戏
P4819 [中山市选]杀人游戏
P7737 [NOI2021] 庆典

第三部分动态规划

第十三章动态规划的引入

例题

P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
P1048 [NOIP2005 普及组] 采药
P2196 [NOIP1996 提高组] 挖地雷
P1434 [SHOI2002]滑雪
P4017 最大食物链计数
P1115 最大子段和
习题
P1802 5 倍经验日
P1002 [NOIP2002 普及组] 过河卒
P1049 [NOIP2001 普及组] 装箱问题
P1616 疯狂的采药
P1164 小A点菜
P1077 [NOIP2012 普及组] 摆花
P3842 [TJOI2007]线段
P1064 [NOIP2006 提高组] 金明的预算方案
P2392 kkksc03考前临时抱佛脚

第十四章线性状态动态规划

例题

P1020 [NOIP1999 普及组] 导弹拦截
P2285 [HNOI2004]打鼹鼠
P1725 琪露诺
P4933 大师
P1874 快速求和
P2758 编辑距离
P1439 【模板】最长公共子序列
P2679 [NOIP2015 提高组] 子串
习题
P1091 [NOIP2004 提高组] 合唱队形
P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落
P1854 花店橱窗布置
P1833 樱花
P2340 [USACO03FALL]Cow Exhibition G
P1541 [NOIP2010 提高组] 乌龟棋
P4310 绝世好题
P3147 [USACO16OPEN]262144 P

第十五章区间与环形动态规划

例题

P1435 [IOI2000] 回文字串 / [蓝桥杯 2016 省] 密码脱落
P1774 最接近神的人
CF607B Zuma
P3205 [HNOI2010]合唱队
P1880 [NOI1995] 石子合并
习题
P1140 相似基因
P4170 [CQOI2007]涂色
P4290 [HAOI2008]玩具取名
P3146 [USACO16OPEN]248 G
P1063 [NOIP2006 提高组] 能量项链
P1070 [NOIP2009 普及组] 道路游戏
P4342 [IOI1998]Polygon
P1220 关路灯

第十六章树与图上的动态规划

例题

P1352 没有上司的舞会
P2015 二叉苹果树
P2014 [CTSC1997] 选课
P1613 跑路
P6772 [NOI2020] 美食家
P4316 绿豆蛙的归宿
P2656 采蘑菇
习题
P1040 [NOIP2003 提高组] 加分二叉树
P1122 最大子树和
P2016 战略游戏
P2585 [ZJOI2006]三色二叉树
P1273 有线电视网
P2515 [HAOI2010]软件安装
P2986 [USACO10MAR] Great Cow Gathering G
P3953 [NOIP2017 提高组] 逛公园
P7077 [CSP-S2020] 函数调用
P7516 [省选联考 2021 A/B 卷] 图函数

第十七章状态压缩动态规划

例题

P1896 [SCOI2005]互不侵犯
P2622 关灯问题II
CF11D A Simple Task
P3959 [NOIP2017 提高组] 宝藏
P4484 [BJWC2018]最长上升子序列
P4363 [九省联考 2018] 一双木棋 chess
P1357 花园
P1450 [HAOI2008]硬币购物
习题
P3694 邦邦的大合唱站队
P1441 砝码称重
P1879 [USACO06NOV]Corn Fields G
P2704 [NOI2001] 炮兵阵地
P2831 [NOIP2016 提高组] 愤怒的小鸟
P4045 [JSOI2009] 密码
AT2365 [AGC012E] Camel and Oases
CF1209E2 Rotate Columns (hard version)
P5369 [PKUSC2018]最大前缀和
P2761 软件补丁问题
P2473 [SCOI2008] 奖励关
P2167 [SDOI2009]Bill的挑战

第十八章动态规划的设计与优化

例题

CF708E Student's Camp
P3800 Power收集
CF833E Caramel Clouds
P3648 [APIO2014]序列分割
P4027 [NOI2007] 货币兑换
习题
P2513 [HAOI2009]逆序对数列
P4099 [HEOI2013]SAO
P3572 [POI2014]PTA-Little Bird
P2254 [NOI2005] 瑰丽华尔兹
P2305 [NOI2014] 购票
P1973 [NOI2011] NOI 嘉年华
P1912 [NOI2009] 诗人小G
P3195 [HNOI2008]玩具装箱
P5468 [NOI2019] 回家路线

第五部分数学专题选讲

第十九章进阶数论

例题

P1516 青蛙的约会
P4942 小凯的数字
P3811 【模板】乘法逆元
P1495 【模板】中国剩余定理(CRT)/曹冲养猪
P3861 拆分
P5091 【模板】扩展欧拉定理
P2568 GCD
P2303 [SDOI2012] Longge 的问题
习题
P1082 [NOIP2012 提高组] 同余方程
P4549 【模板】裴蜀定理
P2421 [NOI2002] 荒岛野人
P2613 【模板】有理数取余
CF757B Bash's Big Day
CF776B Sherlock and his girlfriend
P2155 [SDOI2008] 沙拉公主的困惑
P2152 [SDOI2009]SuperGCD
CF632D Longest Subsequence
CF582A GCD Table
CF687B Remainders Game
P2261 [CQOI2007]余数求和
P2158 [SDOI2008] 仪仗队
P6583 回首过去
P4139 上帝与集合的正确用法

第二十章组合数学与计数

例题

P3197 [HNOI2008]越狱
P5664 [CSP-S2019] Emiya 家今天的饭
P1287 盒子与球
P1450 [HAOI2008]硬币购物
P5520 [yLOI2019] 青原樱
P4071 [SDOI2016]排列计数
P1313 [NOIP2011 提高组] 计算系数
CF1332E Height All the Same
P1044 [NOIP2003 普及组] 栈
习题
P2567 [SCOI2010]幸运数字
P5505 [JSOI2011]分特产
P3223 [HNOI2012] 排队
P2822 [NOIP2016 提高组] 组合数问题
P3214 [HNOI2011] 卡农
P2532 [AHOI2012]树屋阶梯
P3200 [HNOI2009]有趣的数列
CF1278F Cards
P3228 [HNOI2013]数列
CF961G Partitions

第二十一章概率与统计

例题

P2719 搞笑世界杯
P1654 OSU!
CF280C Game on Tree
习题
UVA11181 条件概率 Probability|Given
P1365 WJMZBMR打osu! / Easy
P4316 绿豆蛙的归宿
P1297 [国家集训队]单选错位
P2111 考场奇遇
P1850 [NOIP2016 提高组] 换教室

第二十二章基础线性代数

例题

P1962 斐波那契数列
P2455 [SDOI2006]线性方程组
习题
P2520 [HAOI2011]向量
P1349 广义斐波那契数列
P1939 【模板】矩阵加速（数列）
P2447 [SDOI2010] 外星千足虫
P7112 【模板】行列式求值
P3216 [HNOI2011]数学作业
P4910 帕秋莉的手环
P2151 [SDOI2009]HH去散步
P4035 [JSOI2008]球形空间产生器
P2973 [USACO10HOL]Driving Out the Piggies G