【信息学奥赛一本通】题解目录

信息学奥赛一本通OJ
以下本人做的OJ题解
针对每一道题我都会给出题目考点、解题思路、题解代码。必要时也会给出不同的解题方法。
本人水平有限，如有不足之处，欢迎大家指正。如看过后还有不明白的地方，欢迎在评论区留言。
作者：君义_noip

基础(一) C++语言

第一章 C++语言入门

1001 Hello,World!：点击这里
2060 【例1.1】计算机输出： 点击这里
2061 【例1.2】梯形面积：点击这里
2062 【例1.3】电影票：点击这里
2063 【例1.4】牛吃牧草：点击这里
1002 输出第二个整数：点击这里
1003 对齐输出：点击这里
1004 字符三角形：点击这里
1005 地球人口承载力估计：点击这里

第二章 顺序结构程序设计

第一节 运算符和表达式

2064 【例2.1】交换值：点击这里
2065 【例2.2】整数的和：点击这里
2066 【例2.3】买图书：点击这里
1006 A+B问题：点击这里
1007 计算(a+b)×c的值：点击这里
1008 计算(a+b)/c的值：点击这里
1009 带余除法：点击这里
1010 计算分数的浮点数值：点击这里

第二节 常量和变量

2067 【例2.5】圆：点击这里
2068 【例2.6】鸡兔同笼：点击这里
1011 甲流疫情死亡率：点击这里
1012 计算多项式的值：点击这里
1013 温度表达转化：点击这里
1014 与圆相关的计算：点击这里
1015 计算并联电阻的阻值：点击这里

第三节 标准数据类型

1414 【17NOIP普及组】成绩：点击这里
1016 整型数据类型存储空间大小：点击这里
1017 浮点型数据类型存储空间大小：点击这里
1018 其他数据类型存储空间大小：点击这里
1019 浮点数向零舍入：点击这里
1020 打印ASCII码：点击这里
1021 打印字符：点击这里
1022 整型与布尔型的转换：点击这里
1023 Hello,World!的大小：点击这里

第四节 数据输入输出

2069 【例2.12】糖果游戏：点击这里
1024 保留3位小数的浮点数：点击这里
1025 保留12位小数的浮点数：点击这里
1026 空格分隔输出：点击这里
1027 输出浮点数：点击这里
1028 字符菱形：点击这里

第五节 顺序结构实例

2070 【例2.13】数字对调：点击这里
2071 【例2.14】平均分：点击这里
2072 【例2.15】歌手大奖赛：点击这里
2073 【例2.16】三角形面积：点击这里
1029 计算浮点数相除的余：点击这里
1030 计算球的体积：点击这里
1031 反向输出一个三位数：点击这里
1032 大象喝水查：点击这里
1033 计算线段长度：点击这里
1034 计算三角形面积：点击这里
1035 等差数列末项计算：点击这里
1036 A×B问题：点击这里
1037 计算2的幂：点击这里
1038 苹果和虫子：点击这里

第三章 程序的控制结构

第一节 if选择结构

2051 【例3.1】偶数：点击这里
2052 【例3.2】范围判断：点击这里
2053 【例3.3】三个数：点击这里
2054 【例3.4】适合晨练：点击这里
2055 【例3.5】收费：点击这里
2056 【例3.7】最大的数：点击这里
1039 判断数正负：点击这里
1040 输出绝对值：点击这里
1041 奇偶数判断：点击这里
1042 奇偶ASCII值判断：点击这里
1043 整数大小比较：点击这里
1044 判断是否为两位数：点击这里
1045 收集瓶盖赢大奖：点击这里
1046 判断一个数能否同时被3和5整除：点击这里
1047 判断能否被3，5，7整除：点击这里
1048 有一门课不及格的学生：点击这里

第二节 switch语句

2057 【例3.9 】星期几：点击这里
2058 【例3.10】简单计算器：点击这里
2059 【例3.11】买笔：点击这里
1049 晶晶赴约会：点击这里
1050 骑车与走路：点击这里
1051 分段函数：点击这里
1052 计算邮资：点击这里
1053 最大数输出：点击这里
1054 三角形判断：点击这里
1055 判断闰年：点击这里
1056 点和正方形的关系：点击这里
1057 简单计算器：点击这里
1058 求一元二次方程：点击这里

第四章 循环结构的程序设计

第一节 for语句

2016 【例4.1】for循环求和：点击这里
2017 【例4.2】输出偶数：点击这里
2018 【例4.3】输出奇偶数之和：点击这里
2019 【例4.4】求阶乘：点击这里
1059 求平均年龄：点击这里
1060 均值：点击这里
1061 求整数的和与均值：点击这里
1062 最高的分数：点击这里
1063 最大跨度值：点击这里
1064 奥运奖牌计数：点击这里
1065 奇数求和：点击这里
1066 满足条件的数累加：点击这里
1067 整数的个数：点击这里
1068 与指定数字相同的数的个数：点击这里
1069 乘方计算：点击这里
1070 人口增长：点击这里
1071 菲波那契数：点击这里
1072 鸡尾酒疗法：点击这里
1073 救援：点击这里
1074 津津的储蓄计划：点击这里
1075 药房管理：点击这里
1076 正常血压：点击这里
1077 统计满足条件的4位数：点击这里
1078 求分数序列和：点击这里
1079 计算分数加减表达式的值：点击这里
1080 余数相同问题：点击这里
1081 分苹果：点击这里
1082 求小数的某一位：点击这里
1083 计算星期几：点击这里
1084 幂的末尾：点击这里

第二节 while语句 / 第三节 do-while语句

2020 【例4.5】第几项：点击这里
2021 【例4.6】最大公约数：点击这里
2022 【例4.7】最小n值：点击这里
2023 【例4.8】数据统计：点击这里
2024 【例4.10】末两位数：点击这里
2025 【例4.11】体操队：点击这里
1085 球弹跳高度的计算：点击这里
1086 角谷猜想：点击这里
1087 级数求和：点击这里
1088 分离整数的各个数：点击这里
1089 数字反转：点击这里
1090 含k个3的数：点击这里

第四节 循环嵌套

2026 【例4.12】阶乘和：点击这里
2027 【例4.13】三角形：点击这里
2028 【例4.14】百钱买百鸡：点击这里
2029 【例4.15】水仙花数：点击这里
2030 【例4.16】找素数：点击这里
2031 【例4.17】四位完全平方数：点击这里
2032 【例4.18】分解质因数：点击这里
2033 【例4.19】阶乘之和：点击这里
1091 求阶乘的和：点击这里
1092 求出e的值：点击这里
1093 计算多项式的值：点击这里
1094 与7无关的数：点击这里
1095 数1的个数：点击这里
1096 数字统计：点击这里
1097 画矩形：点击这里
1098 质因数分解：点击这里
1099 第n小的质数：点击这里
1100 金币：点击这里
1101 不定方程求解：点击这里

第五章 数组

第一节 一维数组

2034 【例5.1】反序输出：点击这里
2035 【例5.2】平移数据：点击这里
2036 【例5.3】开关门：点击这里
2037 【例5.4】约瑟夫问题：点击这里
2038 【例5.5】最大数位置：点击这里
2039 【例5.6】冒泡排序：点击这里
2040 【例5.7】筛选法找质数：点击这里
1102 与指定数字相同的数的个数：点击这里
1103 陶陶摘苹果：点击这里
1104 计算书费：点击这里
1105 数组逆序重存放：点击这里
1106 年龄与疾病：点击这里
1107 校门外的树：点击这里
1108 向量点积计算：点击这里
1109 开关灯：点击这里
1110 查找特定的值：点击这里
1111 不高兴的津津：点击这里
1112 最大值和最小值的差：点击这里
1113 不与最大数相同的数字之和：点击这里
1114 白细胞计数：点击这里
1115 直方图：点击这里
1116 最长平台：点击这里
1117 整数去重：点击这里
1118 铺地毯：点击这里

第二节 二维数组

2041 【例5.9】新矩阵：点击这里
2042 【例5.10】稀疏矩阵：点击这里
2043 【例5.11】杨辉三角形：点击这里
2044 【例5.12】回文字串：点击这里
2045 【例5.13】蛇形填数：点击这里
1119 矩阵交换行：点击这里
1120 同行列对角线的格：点击这里
1121 计算矩阵边缘元素之和：点击这里
1122 计算鞍点：点击这里
1123 图像相似度：点击这里
1124 矩阵加法：点击这里
1125 矩阵乘法：点击这里
1126 矩阵转置：点击这里
1127 图像旋转：点击这里
1128 图像模糊处理：点击这里

第三节 字符类型和字符数组

2046 【例5.15】替换字母：点击这里
2047 【例5.16】过滤空格：点击这里
2048 【例5.18】串排序：点击这里
2049 【例5.19】字符串判等：点击这里
2050 【例5.20】字串包含：点击这里
1839 【05NOIP提高组】谁拿了最多奖学金：点击这里
1129 统计数字字符个数：点击这里
1130 找第一个只出现一次的字符：点击这里
1131 基因相关性：点击这里
1132 石头剪子布：点击这里
1133 输出亲朋字符串：点击这里
1134 合法C标识符查：点击这里
1135 配对碱基链：点击这里
1136 密码翻译：点击这里
1137 加密的病历单：点击这里
1138 将字符串中的小写字母转换成大写字母：点击这里
1139 整理药名：点击这里
1140 验证子串：点击这里
1141 删除单词后缀：点击这里
1142 单词的长度：点击这里
1143 最长最短单词：点击这里
1144 单词翻转：点击这里
1145 字符串p型编码：点击这里
1146 判断字符串是否为回文：点击这里
1147 最高分数的学生姓名：点击这里
1148 连续出现的字符：点击这里
1149 最长单词2：点击这里

第六章 函数

第一节 函数

1150 求正整数2和n之间的完全数：点击这里
1151 素数个数：点击这里
1152 最大数max(x,y,z)：点击这里
1153 绝对素数：点击这里
1154 亲和数：点击这里
1155 回文三位数：点击这里
1156 求π的值：点击这里
1157 哥德巴赫猜想：点击这里
1397 简单算术表达式求值：点击这里
1398 短信计费：点击这里
1399 甲流病人初筛：点击这里
1400 统计单词数：点击这里
1401 机器翻译：点击这里
1402 Vigenère密码：点击这里
1403 素数对：点击这里
1404 我家的门牌号：点击这里
1405 质数的和与积：点击这里
1406 单词替换：点击这里
1407 笨小猴：点击这里
1408 素数回文数的个数：点击这里
1409 判决素数个数：点击这里
1410 最大质因子序列：点击这里
1411 区间内的真素数：点击这里
1412 二进制分类：点击这里
1413 确定进制：点击这里

第二节 递归算法

1158 求1+2+3+…：点击这里
1159 斐波那契数列：点击这里
1160 倒序数：点击这里
1161 转进制：点击这里
1162 字符串逆序：点击这里
1163 阿克曼(Ackmann)函数：点击这里
1164 digit函数：点击这里
1165 Hermite多项式：点击这里
1166 求f(x,n)：点击这里
1167 再求f(x,n)：点击这里

基础(二) 基础算法

第一章 高精度计算

1307 【例1.3】高精度乘法：点击这里
1308 【例1.5】高精除：点击这里
1309 【例1.6】回文数：点击这里
1168 大整数加法：点击这里
1169 大整数减法：点击这里
1170 计算2的N次方：点击这里
1171 大整数的因子：点击这里
1172 求10000以内n的阶乘：点击这里
1173 阶乘和：点击这里
1174 大整数乘法：点击这里
1175 除以13：点击这里

第二章 数据排序

1310 【例2.2】车厢重组：点击这里
1311 【例2.5】求逆序对：点击这里
1176 谁考了第k名：点击这里
1177 奇数单增序列：点击这里
1178 成绩排序：点击这里
1179 奖学金：点击这里
1180 分数线划定：点击这里
1181 整数奇偶排序：点击这里
1182 合影效果：点击这里
1183 病人排队：点击这里
1184 明明的随机数：点击这里
1185 单词排序：点击这里
1186 出现次数超过一半的数：点击这里
1187 统计字符数：点击这里

第三章 递推算法

1312 【例3.4】昆虫繁殖：点击这里
1313 【例3.5】位数问题：点击这里
1314 【例3.6】过河卒(Noip2002)：点击这里
1188 菲波那契数列(2)：点击这里
1189 Pell数列：点击这里
1190 上台阶：点击这里
1191 流感传染：点击这里
1192 放苹果：点击这里
1193 吃糖果：点击这里
1194 移动路线：点击这里
1195 判断整除：点击这里
1196 踩方格：点击这里
1197 山区建小学：点击这里

第四章 递归算法

1315 【例4.5】集合的划分：点击这里
1316 【例4.6】数的计数(Noip2001)：点击这里
1198 波兰表达式：点击这里
1199 全排列：点击这里
1200 分解因数：点击这里
1201 菲波那契数列：点击这里
1202 Pell数列：点击这里
1203 扩号匹配问题：点击这里
1204 爬楼梯：点击这里
1205 汉诺塔问题：点击这里
1206 放苹果：点击这里
1207 求最大公约数问题：点击这里
1208 2的幂次方表示：点击这里
1209 分数求和：点击这里
1210 因子分解：点击这里
1211 判断元素是否存在：点击这里

第五章 搜索与回溯算法

1317 【例5.2】组合的输出：点击这里
1318 【例5.3】自然数的拆分：点击这里
1212 LETTERS：点击这里
1213 八皇后问题：点击这里
1214 八皇后：点击这里
1215 迷宫：点击这里
1216 红与黑：点击这里
1217 棋盘问题：点击这里
1218 取石子游戏：点击这里
1219 马走日：点击这里
1220 单词接龙：点击这里
1221 分成互质组：点击这里
1222 放苹果：点击这里

第六章 贪心算法

1319 【例6.1】排队接水：点击这里
1321 【例6.3】删数问题(Noip1994)：点击这里
1322 【例6.4】拦截导弹问题(Noip1999)：点击这里
1323 【例6.5】活动选择：点击这里
1324 【例6.6】整数区间：点击这里
1223 An Easy Problem：点击这里
1224 最大子矩阵：点击这里
1225 金银岛：点击这里
1226 装箱问题：点击这里
1227 Ride to Office：点击这里
1228 书架：点击这里
1229 电池的寿命：点击这里
1230 寻找平面上的极大点：点击这里
1231 最小新整数：点击这里
1232 Crossing River：点击这里
1233 接水问题：点击这里

第七章 分治算法

1325 【例7.4】 循环比赛日程表：点击这里
1326 【例7.5】 取余运算（mod）：点击这里
1327 【例7.6】黑白棋子的移动：点击这里
1328 【例7.7】光荣的梦想：点击这里
1234 2011：点击这里
1235 输出前k大的数：点击这里
1236 区间合并：点击这里
1237 求排列的逆序数：点击这里
1238 一元三次方程求解：点击这里
1239 统计数字：点击这里
1240 查找最接近的元素：点击这里
1241 二分法求函数的零点：点击这里
1242 网线主管：点击这里
1243 月度开销：点击这里
1244 和为给定数：点击这里
1245 不重复地输出数：点击这里
1246 膨胀的木棍：点击这里
1247 河中跳房子：点击这里

第八章 广度优先搜索算法

1329 【例8.2】细胞：点击这里
1330 【例8.3】最少步数：点击这里
1248 Dungeon Master：点击这里
1249 Lake Counting：点击这里
1250 The Castle：点击这里
1251 仙岛求药：点击这里
1252 走迷宫：点击这里
1253 抓住那头牛：点击这里
1254 走出迷宫：点击这里
1255 迷宫问题：点击这里
1256 献给阿尔吉侬的花束：点击这里
1257 Knight Moves：点击这里

第九章 动态规划

第一节 动态规划的基本模型

1258 【例9.2】数字金字塔：点击这里
1259 【例9.3】求最长不下降序列：点击这里
1260 【例9.4】拦截导弹(Noip1999)：点击这里
1261 【例9.5】城市交通路网：点击这里
1262 【例9.6】挖地雷：点击这里：点击这里
1263 【例9.7】友好城市：点击这里
1264 【例9.8】合唱队形：点击这里
1265 【例9.9】最长公共子序列：点击这里
1266 【例9.10】机器分配：点击这里
1281 最长上升子序列：点击这里
1282 最大子矩阵：点击这里
1283 登山：点击这里
1284 摘花生：点击这里
1285 最大上升子序列和：点击这里
1286 怪盗基德的滑翔翼：点击这里
1287 最低通行费：点击这里
1288 三角形最佳路径问题：点击这里
1289 拦截导弹：点击这里

第二节 背包问题

1267 【例9.11】01背包问题：点击这里
1268 【例9.12】完全背包问题：点击这里
1269 【例9.13】庆功会：点击这里
1270 【例9.14】混合背包：点击这里
1271 【例9.15】潜水员：点击这里
1272 【例9.16】分组背包：点击这里
1273 【例9.17】货币系统：点击这里
1290 采药：点击这里
1291 数字组合：点击这里
1292 宠物小精灵之收服：点击这里
1293 买书：点击这里
1294 Charm Bracelet：点击这里
1295 装箱问题：点击这里
1296 开餐馆：点击这里

第三节 动态规划经典题

1274 【例9.18】合并石子：点击这里
1275 【例9.19】乘积最大：点击这里
1276 【例9.20】编辑距离：点击这里
1277 【例9.21】方格取数：点击这里
1278 【例9.22】复制书稿(book)：点击这里
1279 【例9.23】橱窗布置(flower)：点击这里
1280 【例9.24】滑雪：点击这里
1297 公共子序列：点击这里
1298 计算字符串距离：点击这里
1299 糖果：点击这里
1300 鸡蛋的硬度：点击这里
1301 大盗阿福：点击这里
1302 股票买卖：点击这里
1303 鸣人的影分身：点击这里
1304 数的划分：点击这里
1305 Maximum sum：点击这里
1306 最长公共子上升序列：点击这里

基础(三) 数据结构

第一章 栈

1331 【例1-2】后缀表达式的值：点击这里
1353 表达式括号匹配(stack)：点击这里
1354 括弧匹配检验：点击这里
1355 字符串匹配问题(strs)：点击这里
1356 计算(calc)：点击这里
1357 车厢调度(train)：点击这里
1358 中缀表达式值(expr)：点击这里

第二章 队列

1332 【例2-1】周末舞会：点击这里
1333 【例2-2】Blah数集：点击这里
1334 【例2-3】围圈报数：点击这里
1335 【例2-4】连通块：点击这里
1359 围成面积：点击这里
1360 奇怪的电梯(lift)：点击这里
1361 产生数(Produce)：点击这里
1362 家庭问题(family)：点击这里

第三章 树

第一节 二叉树

1336 【例3-1】找树根和孩子：点击这里
1337 【例3-2】单词查找树：点击这里
1338 【例3-3】医院设置：点击这里
1339 【例3-4】求后序遍历：点击这里
1340 【例3-5】扩展二叉树：点击这里
1363 小球(drop)：点击这里
1364 二叉树遍历(flist)：点击这里
1365 FBI树(fbi)：点击这里
1367 查找二叉树(tree_a)：点击这里
1368 对称二叉树(tree_c)：点击这里

第二节 堆及其应用

1369 合并果子(fruit)：点击这里
1370 最小函数值(minval)：点击这里
1371 看病：点击这里
1372 小明的账单：点击这里
1373 鱼塘钓鱼(fishing)：点击这里

第四章 图论算法

第一节 图的遍历

1341 【例题】一笔画问题：点击这里
1374 铲雪车(snow)：点击这里
1375 骑马修栅栏(fence)：点击这里

第二节 最短路径算法

1342 【例4-1】最短路径问题：点击这里
1343 【例4-2】牛的旅行：点击这里
1344 【例4-4】最小花费：点击这里
1345 【例4-6】香甜的黄油：点击这里
1376 信使(msner)：点击这里
1377 最优乘车(travel)：点击这里
1378 最短路径(shopth)：点击这里
1379 热浪(heatwv)：点击这里
1380 分糖果(candy)：点击这里
1381 城市路(Dijkstra)：点击这里
1382 最短路(Spfa)：点击这里

第三节 图的连通性问题

1383 刻录光盘(cdrom)：点击这里
1384 珍珠(bead)：点击这里

第四节 并查集

1346 【例4-7】亲戚(relation)：点击这里
1347 【例4-8】格子游戏：点击这里
1385 团伙(group)：点击这里
1386 打击犯罪(black)：点击这里
1387 搭配购买(buy)：点击这里
1388 家谱(gen)：点击这里
1389 亲戚：点击这里
1390 食物链【NOI2001】

第五节 最小生成树

1348 【例4-9】城市公交网建设问题：点击这里
1349 【例4-10】最优布线问题：点击这里
1350 【例4-11】最短网络(agrinet)：点击这里
1351 【例4-12】家谱树：点击这里
1391 局域网(net)：点击这里
1392 繁忙的都市(city)：点击这里
1393 联络员(liaison)：[点击这里]
1394 连接格点(grid)：[点击这里]

第六节 拓扑排序与关键路径

1352 【例4-13】奖金：点击这里
1395 烦人的幻灯片(slides)：[点击这里]
1396 病毒(virus)：[点击这里]