一年又要过去了,oier们又要为下一次的普及测试准备了,以后将提供普及练习场的各题题解。加油!RP++
章节 1. 简单的模拟
开始普及组的训练!所谓模拟,就是直接根据题意编写,思维难度简单。
12 | 12 | 2 | ||
P1393 Mivik 的标题 | 2 | 2 | 6 | |
16 | 5 | 3 | ||
P1382 楼房 | 1 | 1 | 5 | |
P1559 运动员最佳匹配问题 | 0 | 0 | 4 | |
P1560 [USACO5.2] 蜗牛的旅行Snail Trails | 0 | 0 | 5 |
章节 2. 交叉模拟
这里也是模拟,但是会混有些别的部分。思维难度不大,但是编写起来会有些难度。
P1348 Couple number | 1 | 1 | 2 | |
P1356 数列的整除性 | 1 | 0 | 4 | |
P1368 【模板】最小表示法 | 1 | 1 | 5 | |
P1412 经营与开发 | 0 | 0 | 5 | |
P1424 小鱼的航程(改进版) | 128 | 47 | 1 | |
P1632 点的移动 | 0 | 0 | 3 |
章节 3. 排序
将杂乱无章的数据变得有规律。有各种各样的排序算法,看情况使用。
P2584 [ZJOI2006] GameZ游戏排名系统 | 0 | 0 | 6 | |
P1385 密令 | 0 | 0 | 4 | |
P1394 山上的国度 | 1 | 1 | 3 | |
P2585 [ZJOI2006] 三色二叉树 | 2 | 1 | 5 |
章节 4. 排序Ex
这里的排序就更上一层了。不仅融合了别的算法与技巧,排序本身也有各种花招。
P2586 [ZJOI2008] 杀蚂蚁 | 0 | 0 | 6 | |
P1377 [TJOI2011] 树的序 | 3 | 1 | 5 | |
P1419 寻找段落 | 0 | 0 | 4 | |
P1715 [USACO16DEC] Lots of Triangles P | 0 | 0 | 6 |
章节 5. 字符串处理
这里的字符串处理还会变得更加的有意思,难度也更大。需要好好地思考一下。
P2587 [ZJOI2008] 泡泡堂 | 0 | 0 | 5 | |
P1397 [NOI2013] 矩阵游戏 | 1 | 0 | 5 | |
P1337 [JSOI2004] 平衡点 / 吊打XXX | 33 | 5 | 4 | |
P2588 [ZJOI2008] Risk | 0 | 0 | 6 |
章节 6. 贪心
贪心就是只考虑眼前的利益。对于我们人生来说太贪是不好的,不过oi中,有时是对的。
P1416 攻击火星 | 0 | 0 | 2 | |
P2589 [ZJOI2006] 碗的叠放 | 0 | 0 | 5 | |
P2590 [ZJOI2008] 树的统计 | 6 | 5 | 5 | |
P2591 [ZJOI2009] 函数 | 0 | 0 | 5 | |
P1420 最长连号 | 7 | 6 | 1 | |
P1732 [TJOI2011] 序列 | 0 | 0 | 2 | |
P1356 数列的整除性 | 1 | 0 | 4 | |
P1406 方格填数 | 0 | 0 | 4 |
章节 7. 深度优先搜索
搜索可以穷举各种情况。很多题目都可以用搜索完成。就算不能,搜索也是骗分神器。
P2592 [ZJOI2008] 生日聚会 | 0 | 0 | 5 | |
P1344 [USACO4.4] 追查坏牛奶Pollutant Control | 2 | 2 | 6 | |
P2593 [ZJOI2006] 超级麻将 | 0 | 0 | 5 | |
P2594 [ZJOI2009] 染色游戏 | 0 | 0 | 6 | |
P1365 WJMZBMR打osu! / Easy | 1 | 1 | 5 | |
P1418 [TJOI2011] 构造矩阵 | 0 | 0 | 5 |
章节 8. 广度优先搜索
广度优先搜索可以用来找有关“最短步数”的问题。恩,也可以用来“地毯式搜索”。
P2599 [ZJOI2009] 取石子游戏 | 2 | 2 | 6 | |
P1357 花园 | 2 | 2 | 5 | |
P2600 [ZJOI2008] 瞭望塔 | 0 | 0 | 6 | |
P2601 [ZJOI2009] 对称的正方形 | 4 | 1 | 6 | |
P2602 [ZJOI2010] 数字计数 | 4 | 2 | 5 |
章节 9. 带有技巧的搜索
这里的搜索不仅包含了dfs和bfs,还包括剪枝、记录等技巧以加快速度。
P2603 [ZJOI2008] 无序运动 | 0 | 0 | 6 | |
P2604 [ZJOI2010] 网络扩容 | 4 | 2 | 6 | |
P2605 [ZJOI2010] 基站选址 | 0 | 0 | 7 | |
P1400 [CERC2016] Easy Equation | 1 | 0 | 10 |
章节 10. 分治算法
将大问题拆分为小问题,分而治之,各个击破,然后在合并回来。
P2606 [ZJOI2010] 排列计数 | 2 | 1 | 5 | |
P1335 [NOI2013] 小Q的修炼 | 0 | 0 | 7 | |
P2607 [ZJOI2008] 骑士 | 5 | 2 | 6 | |
P2608 [ZJOI2010] 任务安排 | 0 | 0 | (无) |
章节 11. 简单数学问题
用计算机解决某些麻烦数学问题,再合适不过了。这真是绝妙的搭配啊!
P1414 又是毕业季II | 0 | 0 | 3 | |
P1371 NOI元丹 | 1 | 1 | 3 | |
P2609 [ZJOI2012] 数列 | 0 | 0 | 6 | |
P1342 请柬 | 4 | 4 | 3 | |
P2610 [ZJOI2012] 旅游 | 0 | 0 | 6 | |
P1354 房间最短路问题 | 2 | 2 | 6 |
章节 12. 递推与递归二分
递推,层层递进,由基础推向顶层。二分不仅可以用来查找数据,还可以确定最合适的值。
P2611 [ZJOI2012] 小蓝的好友 | 1 | 1 | 6 | |
P1350 车的放置 | 2 | 2 | 5 | |
P1383 高级打字机 | 3 | 2 | 5 | |
P2612 [ZJOI2012] 波浪 | 2 | 1 | 7 | |
P2216 [HAOI2007] 理想的正方形 | 2 | 2 | 5 | |
P2613 【模板】有理数取余 | 1 | 1 | 4 | |
P2614 计算器弹琴 | 0 | 0 | 2 |
章节 13. 线性数据结构
数组,链表,队列,栈,都是线性结构。巧用这些结构可以做出不少方便的事情。
P2615 [NOIP2015 提高组] 神奇的幻方 | 9 | 8 | 2 | |
P2200 炉石collection | 1 | 1 | 10 | |
P2616 [USACO10JAN] Buying Feed, II S | 0 | 0 | 2 | |
P2617 Dynamic Rankings | 9 | 4 | 6 | |
P2618 数字工程 | 0 | 0 | 5 |
章节 14. 树形数据结构
由一个根节点分叉,越分越多,就成了树。树可以表示数据之间的从属关系
P1413 坚果保龄球 | 0 | 0 | 2 | |
P1355 神秘大三角 | 1 | 1 | 3 | |
P2619 [国家集训队] Tree I | 1 | 1 | 5 | |
P1643 完美数 | 0 | 0 | 5 |
章节 15. 动态规划的背包问题
P1386 座位安排 | 0 | 0 | 5 | |
P2212 [USACO14MAR] Watering the Fields S | 2 | 0 | 4 | |
P1390 公约数的和 | 3 | 3 | 5 | |
P1374 进攻幽暗城 | 1 | 0 | 4 | |
P1375 小猫 | 0 | 0 | 3 | |
P2620 虫洞 | 0 | 0 | 4 |
章节 16. 线性动态规划
这也是基础的动态规划。是在线性结构上面的动态规划,一定要掌握。
P1345 [USACO5.4] 奶牛的电信Telecowmunication | 3 | 3 | 5 | |
P1417 烹调方案 | 1 | 1 | 4 | |
P2225 [HNOI2001] 棋盘变换 | 0 | 0 | 5 | |
P2622 关灯问题II | 0 | 0 | 5 | |
P2209 [USACO13OPEN] Fuel Economy S | 0 | 0 | 5 | |
P2623 物品选取 | 0 | 0 | 3 |
章节 17. 多维动态规划
这里的动态规划就不止一维了。不仅要小心时间复杂度,也要注意空间复杂度。
P2624 [HNOI2008] 明明的烦恼 | 1 | 0 | 6 | |
P1331 海战 | 4 | 3 | 2 | |
P2625 豪华游轮 | 0 | 0 | 5 | |
P2626 斐波那契数列(升级版) | 2 | 2 | 2 | |
P2627 [USACO11OPEN] Mowing the Lawn G | 0 | 0 | 5 | |
P2628 冒险岛 | 0 | 0 | 2 |
以后会更新题解,敬请期待。