洛谷新手村
新手村
任何一个伟大的目标,都有一个微不足道的开始。
洛谷的第一个任务
勇敢的迈出第一步,了解下语言和洛谷。跟着书本和老师走,不会难的。
顺序与分支
计算机的智能性开始得以体现,因为计算机能够根据不同的条件选择了。
循环!循环!循环!
计算机最不怕的就是重复。你让它做10000次同样的事它也不怕啦,但是让他做1亿亿次的话……
数组
跟数组有关的题目基本上都要用到循环,所以请先完成1-3。
简单字符串
计算机不仅可以处理数字,还能处理文字!就是其实跟数字也没什么差。
- P1055 ISBN号码
- P1200 [USACO1.1]你的飞碟在这儿Your Ride Is Here
- P1308 统计单词数
- P1553 数字反转(升级版)
- P1598 垂直柱状图
- P1914 小书童——密码
过程函数与递归
将代码串进行打包,就是过程与函数。过程与函数调用自己则为递归。有一点小难但不要怕哦。
BOSS战-入门综合练习1
这里将前面的内容综合起来了,会有点难,不过你可以问老师同学,也能上网查资料。
BOSS战-入门综合练习2
勇士,竟然来到了BOSS的老巢!来一场恶斗,证明自己的实力,解锁下一个级别!
普及练习场
普及组选手可冲刺训练,提高组选手亦可在此巩固基础。
简单的模拟
开始普及组的训练!所谓模拟,就是直接根据题意编写,思维难度简单。
交叉模拟
这里也是模拟,但是会混有些别的部分。思维难度不大,但是编写起来会有些难度。
排序
将杂乱无章的数据变得有规律。有各种各样的排序算法,看情况使用。
排序Ex
这里的排序就更上一层了。不仅融合了别的算法与技巧,排序本身也有各种花招。
字符串处理
这里的字符串处理还会变得更加的有意思,难度也更大。需要好好地思考一下。
贪心
贪心就是只考虑眼前的利益。对于我们人生来说太贪是不好的,不过oi中,有时是对的。
- P1090 合并果子 / [USACO06NOV]Fence Repair G
- P1181 数列分段Section I
- P1208 [USACO1.3]混合牛奶 Mixing Milk
- P1223 排队接水
- P1094 纪念品分组
- P1803 凌乱的yyy / 线段覆盖
- P1031 均分纸牌
- P1080 国王游戏
深度优先搜索
搜索可以穷举各种情况。很多题目都可以用搜索完成。就算不能,搜索也是骗分神器。
广度优先搜索
广度优先搜索可以用来找有关“最短步数”的问题。恩,也可以用来“地毯式搜索”。
带有技巧的搜索
这里的搜索不仅包含了dfs和bfs,还包括剪枝、记录等技巧以加快速度。
分治算法
将大问题拆分为小问题,分而治之,各个击破,然后在合并回来。
简单数学问题
用计算机解决某些麻烦数学问题,再合适不过了。这真是绝妙的搭配啊!
递推与递归二分
递推,层层递进,由基础推向顶层。二分不仅可以用来查找数据,还可以确定最合适的值。
- P1192 台阶问题
- P1025 数的划分
- P1057 传球游戏
- P1135 奇怪的电梯
- P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
- P1182 数列分段 Section II
- P1316 丢瓶盖(重题 P1824)
线性数据结构
数组,链表,队列,栈,都是线性结构。巧用这些结构可以做出不少方便的事情。
树形数据结构
由一个根节点分叉,越分越多,就成了树。树可以表示数据之间的从属关系
动态规划的背包问题
这是最基础的动态规划。不过如果是第一次接触会有些难以理解。加油闯过这个坎。
线性动态规划
这也是基础的动态规划。是在线性结构上面的动态规划,一定要掌握。
多维动态规划
这里的动态规划就不止一维了。不仅要小心时间复杂度,也要注意空间复杂度。
更要技巧的动规与记忆化
这边的题目有各种搞法。当然有的题目也可以使用记忆化搜索来降低思维难度。
高精度算法
就算是long long(或int64)还不够怎么办?用高精度算法。自己动手丰衣足食。
贪心EX
虽然是贪心题,可能不是你当时你虐着玩的贪心惹qwq
简单数学
数学和oi是密切相关的,数学不仅是oi的基础,而且是算法的核心。
BOSS战-普及综合练习1
好不容易闯到这一关,你那还等什么呢?抄起家伙赶快上啊!
BOSS战-普及综合练习2
来搞定第二个BOSS。虽然战斗艰难,但你一定没有问题。
BOSS战-普及综合练习3
普及练习场的大BOSS:“一定让你有去无回”。怎么办呢?只能打倒他开启下一个级别!
普及常见模板
这里集中了比较基础的算法的模板。提高和省选也有模板题哦!
提高历练地
已经去除了普及组难度的,请组织放心。成长大牛之必写题!!!
搜索Ex
开始提高组的试炼。这里已经去除了所有普及组难度的题目。哼哼,怕了吧。。
动态规划TG.lv(1)
这是提高组难度中比较基础的动态规划,也许一两个转移方程就可以写出。
动态规划TG.lv(2)
这里的动态规划稍稍有所加大难度,思考转移方程的时间可能会与编写程序的时间持平。
动态规划TG.lv(3)
比较需要技巧的动态规划。有的不仅仅需要状态转移方程,可能还会与别的算法综合。
- P1415 拆分数列
- P2157 [SDOI2009]学校食堂
- P2216 [HAOI2007]理想的正方形
- P2331 [SCOI2005]最大子矩阵
- P2467 [SDOI2010]地精部落
- P3084 [USACO13OPEN]Photo G
数论
数论就是研究整数的理论。包括公约公倍数、质数、欧拉定理和同余方程等。
博弈论
博弈论考虑游戏中的个体的预测行为和实际行为,并研究它们的优化策略。
其他数学问题
听说学oi的同志们数学都挺好。那么。就请完成下面的题目证明这一点吧!
- P1357 花园
- P1641 [SCOI2010]生成字符串
- P2059 [JLOI2013]卡牌游戏
- P2154 [SDOI2009]虔诚的墓主人
- P2261 [CQOI2007]余数求和
- P2327 [SCOI2005]扫雷
- P1066 2^k进制数
图的遍历
图是一种非常重要的数据结构,描述对象复杂的练习。这里开始接触图的基本概念。
最短路问题
最短路是图论中最重要的部分,多种算法可以应用。很多题目都可以抽象成这种模型。
- P1339 [USACO09OCT]Heat Wave G
- P1462 通往奥格瑞玛的道路
- P1346 电车
- P1119 灾后重建
- P1144 最短路计数
- P1522 [USACO2.4]牛的旅行 Cow Tours
最小生成树
最小生成树可以用kruskal(克鲁斯卡尔)算法或prim(普里姆)算法求出。
较复杂图论I
别的些图论问题,包括树、拓扑排序等。要过这一关,需要学习不少新的算法。
较复杂图论II
更高级的图论算法。包括差分约束、强连通、二分图等。会更难一些。
- P1993 小K的农场
- P1726 上白泽慧音
- P2055 [ZJOI2009]假期的宿舍
- P2149 [SDOI2009]Elaxia的路线
- P1345 [USACO5.4]奶牛的电信Telecowmunication
并查集
用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。
堆
堆总是一棵完全树;堆中某个节点的值总是不大于或不小于其父节点的值。
线段树树状数组基础
这都是比较高级的线性数据结构。在处理一些询问与修改线性问题时,是很好用的。
神奇的解法
有些问题刚开始觉得无从下手。好好想一想,尽量别看题解,否则你会大呼“简单”。
倍增
一种特殊的枚举算法,但可大大加快效率。近年noip有考到。难度较大。
强连通分量
强连通分量
- P2341 [USACO03FALL][HAOI2006]受欢迎的牛 G
- P3469 [POI2008]BLO-Blockade
- P2746 [USACO5.3]校园网Network of Schools
- P3119 [USACO15JAN]Grass Cownoisseur G
- P3225 [HNOI2012]矿场搭建
BOSS战-提高综合练习1
年轻人,又是个送上门的,让我来看看你真实的本领。啊哈哈哈哈哈!
BOSS战-提高综合练习2
再来!这里有的题目并非单纯的考察某个算法,而是考察一种综合性的思维。
BOSS战-提高综合练习3
既然已经打倒了前面2个boss,那么第3个也是没有问题的。少年,来吧!
提高模板-nlogn数据结构
虽然这些算法不是noip必须的,但是不算困难,很多题目可以使用这些方法。
省选斗兽场/NOI神殿
为省选及以上选手制作的训练场。其实,省选水平的oier不需要一些外加的刷题列表,本栏仅供参考,也欢迎各位指出不足。
省选基础-读入/输出优化
读入/输出优化是省选刷题时必要的一个东西,这里给出了几题,需要自己手写相应的读入输出处理。作为第一关,这一关相对简单。
省选基础-位运算
位运算往往在必要的时候,能带你优化一下常数,也许是空间;也许是时间;有的时候这样可以多过很多分
省选基础-打表
打表虽然很赖皮,而且基本都是非正解,但是这种办法能让我们在省选中拿到一些会超时或者会超空间的一些数据点
动态规划1
动态规划
- P2051 [AHOI2009]中国象棋
- P1879 [USACO06NOV]Corn Fields G
- P1850 换教室
- P2831 愤怒的小鸟
- P1131 [ZJOI2007]时态同步
- P1169 [ZJOI2007]棋盘制作
动态规划2
动态规划
- P1273 有线电视网
- P3648 [APIO2014]序列分割
- P2519 [HAOI2011]problem a
- P2515 [HAOI2010]软件安装
- P3233 [HNOI2014]世界树
- P2501 [HAOI2006]数字序列
网络流——最大流
最大流
网络流——费用流
费用流
- P2153 [SDOI2009]晨跑
- P2053 [SCOI2007]修车
- P3159 [CQOI2012]交换棋子
- P2604 [ZJOI2010]网络扩容
- P2050 [NOI2012]美食节
- P3980 [NOI2008]志愿者招募
单调队列
单调队列
- P2698 [USACO12MAR]Flowerpot S
- P2216 [HAOI2007]理想的正方形
- P2219 [HAOI2007]修筑绿化带
- P2564 [SCOI2009]生日礼物
- P2569 [SCOI2010]股票交易
概率期望
概率期望
- P2473 [SCOI2008] 奖励关
- P2221 [HAOI2012]高速公路
- P3317 [SDOI2014]重建
- P3343 [ZJOI2015]地震后的幻想乡
- P3600 随机数生成器
- P3830 [SHOI2012]随机树
二分图
二分图
- P3386 【模板】二分图最大匹配
- P1640 [SCOI2010]连续攻击游戏
- P1129 [ZJOI2007]矩阵游戏
- P1963 [NOI2009]变换序列
- P3231 [HNOI2013]消毒
- P2526 [SHOI2001]小狗散步
点分治
点分治
后缀数组
后缀数组
- P3809 【模板】后缀排序
- P1117 [NOI2016]优秀的拆分
- P2178 [NOI2015]品酒大会
- P2463 [SDOI2008]Sandy的卡片
- P2336 [SCOI2012]喵星球上的点名
主席树
主席树
- P2468 [SDOI2010]粟粟的书架
- P3157 [CQOI2011]动态逆序对
- P3302 [SDOI2013]森林
- P3168 [CQOI2015]任务查询系统
- P3313 [SDOI2014]旅行
数位DP
数位DP
AC自动机
AC自动机
平衡树
平衡树
- P2042 [NOI2005]维护数列
- P2596 [ZJOI2006]书架
- P1110 [ZJOI2007]报表统计
- P3285 [SCOI2014]方伯伯的OJ
- P3644 [APIO2015]八邻旁之桥
- P3765 总统选举
- P3369 【模板】普通平衡树
树链剖分
树链剖分
- P2590 [ZJOI2008]树的统计
- P2486 [SDOI2011]染色
- P2146 [NOI2015]软件包管理器
- P3258 [JLOI2014]松鼠的新家
- P3178 [HAOI2015]树上操作
动态树
动态树
树套树
树套树
- P1903 [国家集训队]数颜色 / 维护队列
- P3157 [CQOI2011]动态逆序对
- P3332 [ZJOI2013]K大数查询
- P2166 Gty的超级妹子树
- P3380 【模板】二逼平衡树(树套树)
- P2137 Gty的妹子树
- P3759 [TJOI2017]不勤劳的图书管理员
可持久化Trie树
可持久化Trie树
- P2048 [NOI2010]超级钢琴
- P3527 [POI2011]MET-Meteors
- P3302 [SDOI2013]森林
- P3168 [CQOI2015]任务查询系统
- P3242 [HNOI2015]接水果
- P3241 [HNOI2015]开店
- P3293 [SCOI2016]美味
莫队算法
莫队算法
分块
分块
莫比乌斯反演
莫比乌斯反演
- P3768 简单的数学题
- P3172 [CQOI2015]选数
- P3455 [POI2007]ZAP-Queries
- P2522 [HAOI2011]Problem b
- P3327 [SDOI2015]约数个数和
其他
其他
- P3377 【模板】左偏树(可并堆)
- P3261 [JLOI2015]城池攻占
- P3382 【模板】三分法
- P2571 [SCOI2010]传送带
- P3222 [HNOI2012]射箭
- P3187 [HNOI2007]最小矩形覆盖
- P3199 [HNOI2009]最小圈
- P3292 [SCOI2016]幸运数字
- P2824 [HEOI2016/TJOI2016]排序
- P3285 [SCOI2014]方伯伯的OJ
- P1552 [APIO2012]派遣
USACO
美国经典的算法练习题库,值得一刷
USACO Section 1.1
- P1200 [USACO1.1]你的飞碟在这儿Your Ride Is Here
- P1201 [USACO1.1]贪婪的送礼者Greedy Gift Givers
- P1202 [USACO1.1]黑色星期五Friday the Thirteenth
- P1203 [USACO1.1]坏掉的项链Broken Necklace
USACO Section 1.2
完全枚举
- P3864 [USACO1.2]命名那个数字 Name That Number
- P1204 [USACO1.2]挤牛奶Milking Cows
- P1205 [USACO1.2]方块转换 Transformations
- P1206 [USACO1.2]回文平方数 Palindromic Squares
- P1207 [USACO1.2]双重回文数 Dual Palindromes
USACO Section 1.3
贪心
- P1208 [USACO1.3]混合牛奶 Mixing Milk
- P1209 [USACO1.3]修理牛棚 Barn Repair
- P1211 [USACO1.3]牛式 Prime Cryptarithm
- P1444 [USACO1.3]虫洞 wormhole
- P3650 [USACO1.3]滑雪课程设计Ski Course Design
- P2693 [USACO1.3]号码锁 Combination Lock
USACO Section 1.4
有技巧的枚举
USACO Section 1.5
二进制数
- P1216 [USACO1.5][IOI1994]数字三角形 Number Triangles
- P1217 [USACO1.5]回文质数 Prime Palindromes
- P1218 [USACO1.5]特殊的质数肋骨 Superprime Rib
USACO Section 2.1
图论和洪水填充
- P1457 [USACO2.1]城堡 The Castle
- P1458 [USACO2.1]顺序的分数 Ordered Fractions
- P1459 [USACO2.1]三值的排序 Sorting a Three-Valued Sequence
- P1460 [USACO2.1]健康的荷斯坦奶牛 Healthy Holsteins
- P1461 [USACO2.1]海明码 Hamming Codes
USACO Section 2.2
数据结构与动态规划
- P1465 [USACO2.2]序言页码 Preface Numbering
- P1466 [USACO2.2]集合 Subset Sums
- P1467 [USACO2.2]循环数 Runaround Numbers
- P1468 [USACO2.2]派对灯 Party Lamps
USACO Section 2.3
- P1470 [USACO2.3]最长前缀 Longest Prefix
- P1472 [USACO2.3]奶牛家谱 Cow Pedigrees
- P1473 [USACO2.3]零的数列 Zero Sum
- P1474 [USACO2.3]Money System / [USACO07OCT]Cow Cash G
- P1475 [USACO2.3]控制公司 Controlling Companies
USACO Section 2.4
最短路径
- P1518 [USACO2.4]两只塔姆沃斯牛 The Tamworth Two
- P1519 [USACO2.4]穿越栅栏 Overfencing
- P1522 [USACO2.4] 牛的旅行 Cow Tours
- P1529 [USACO2.4]回家 Bessie Come Home
- P1530 [USACO2.4]分数化小数 Fractions to Decimals
USACO Section 3.1
最小生成树
- P1546 [USACO3.1]最短网络 Agri-Net
- P2722 [USACO3.1]总分 Score Inflation
- P2723 [USACO3.1]丑数 Humble Numbers
- P2724 [USACO3.1]联系 Contact
- P2725 [USACO3.1]邮票 Stamps
USACO Section 3.2
背包问题
- P1134 [USACO3.2]阶乘问题
- P2727 [USACO3.2]01串 Stringsobits
- P2728 [USACO3.2]纺车的轮子 Spinning Wheels
- P2729 [USACO3.2]饲料调配 Feed Ratios
- P2730 [USACO3.2]魔板 Magic Squares
- P1828 [USACO3.2]香甜的黄油 Sweet Butter
USACO Section 3.3
欧拉回路
- P2731 [USACO3.3]骑马修栅栏 Riding the Fences
- P2732 [USACO3.3]商店购物 Shopping Offers
- P1930 [USACO3.3]亚瑟王的宫殿
- P2733 [USACO3.3]家的范围 Home on the Range
- P2734 [USACO3.3]游戏 A Game
USACO Section 3.4
计算几何
- P1827 [USACO3.4] 美国血统 American Heritage
- P2735 [USACO3.4]网 Electric Fences
- P2736 [USACO3.4]“破锣摇滚”乐队 Raucous Rockers
USACO Section 4.1
最优化
USACO Section 4.2
网络流
- P2740 [USACO4.2]草地排水Drainage Ditches
- P1894 [USACO4.2]完美的牛栏The Perfect Stall
- P2751 [USACO4.2]工序安排Job Processing
USACO Section 4.3
高精度
- P2687 [USACO4.3]逢低吸纳Buy Low, Buy Lower
- P2752 [USACO4.3]街道赛跑Street Race
- P2753 [USACO4.3]字母游戏Letter Game
USACO Section 4.4
- P1344 [USACO4.4]追查坏牛奶Pollutant Control
- P2739 [USACO4.4]棋盘游戏Shuttle Puzzle
- P2741 [USACO4.4]重叠的图像Frame Up
USACO Section 5.1
二维凸包
- P2742 [USACO5.1]圈奶牛Fencing the Cows /【模板】二维凸包
- P2743 [USACO5.1]乐曲主题Musical Themes
- P2749 [USACO5.1]夜空繁星Starry Night
USACO Section 5.2
USACO Section 5.3
启发式搜索
- P2701 [USACO5.3]巨大的牛棚Big Barn
- P2744 [USACO5.3]量取牛奶Milk Measuring
- P2745 [USACO5.3]窗体面积Window Area
- P2746 [USACO5.3]校园网Network of Schools
USACO Section 5.4
- P1345 [USACO5.4]奶牛的电信Telecowmunication
- P2747 [USACO5.4]周游加拿大Canada Tour
- P2748 [USACO16OPEN]Landscaping P