洛谷试炼场怀旧

liuxingran · 2020-08-24 13:58:02 · 个人记录

新手村

任何一个伟大的目标，都有一个微不足道的开始。

洛谷的第一个任务

勇敢的迈出第一步，了解下语言和洛谷。跟着书本和老师走，不会难的。

• P1000
• P1001
• P1421
• P1425

顺序与分支

计算机的智能性开始得以体现，因为计算机能够根据不同的条件选择了。

• P1422
• P1085
• P1089
• P1909

循环！循环！循环！

计算机最不怕的就是重复。你让它做10000次同样的事它也不怕啦，但是让他做1亿亿次的话……

• P1008
• P1035
• P1423
• P1424
• P1980

数组

跟数组有关的题目基本上都要用到循环，所以请先完成1-3。

• P1046

• P1047

• P1427

• P1428

• P2141

• P1567

  简单字符串

  计算机不仅可以处理数字，还能处理文字！就是其实跟数字也没什么差。

• P1055

• P1200

• P1308

• P1553

• P1598

• P1914

过程函数与递归

将代码串进行打包，就是过程与函数。过程与函数调用自己则为递归。有一点小难但不要怕哦。

• P1028

• P1036

• P1149

• P1217

  BOSS战-入门综合练习1

  这里将前面的内容综合起来了，会有点难，不过你可以问老师同学，也能上网查资料。

• P1478

• P1618

• P1579

• P2089

  BOSS战-入门综合练习2

  勇士，竟然来到了BOSS的老巢！来一场恶斗，证明自己的实力，解锁下一个级别！

• P1426

• P1464

• P1014

• P1022

• P1307

  普及练习场

  普及组选手可冲刺训练，提高组选手亦可在此巩固基础。

简单的模拟

开始普及组的训练！所谓模拟，就是直接根据题意编写，思维难度简单。

• P1003

• P1067

• P1540

• P1056

• P1328

• P1563

  交叉模拟

  这里也是模拟，但是会混有些别的部分。思维难度不大，但是编写起来会有些难度。

• P1023

• P1031

• P1042

• P1086

• P1098

• P3952

  排序

  将杂乱无章的数据变得有规律。有各种各样的排序算法，看情况使用。

• P1177

• P1059

• P1068

• P1781

  排序Ex

  这里的排序就更上一层了。不仅融合了别的算法与技巧，排序本身也有各种花招。

• P1583

• P1051

• P1093

• P1309

  字符串处理

  这里的字符串处理还会变得更加的有意思，难度也更大。需要好好地思考一下。

• P1603

• P1071

• P1012

• P1538

  贪心

  贪心就是只考虑眼前的利益。对于我们人生来说太贪是不好的，不过oi中，有时是对的。

• P1090

• P1181

• P1208

• P1223

• P1094

• P1803

• P1031

• P1080

  深度优先搜索

  搜索可以穷举各种情况。很多题目都可以用搜索完成。就算不能，搜索也是骗分神器。

• P1219

• P1019

• P1101

• P1605

• P1040

• P1092

  广度优先搜索

  广度优先搜索可以用来找有关“最短步数”的问题。恩，也可以用来“地毯式搜索”。

• P1162

• P1032

• P1141

• P1126

• P1443

  带有技巧的搜索

  这里的搜索不仅包含了dfs和bfs，还包括剪枝、记录等技巧以加快速度。

• P1118

• P1434

• P1433

• P1074

  分治算法

  将大问题拆分为小问题，分而治之，各个击破，然后在合并回来。

• P1226

• P1010

• P1908

• P1498

  简单数学问题

  用计算机解决某些麻烦数学问题，再合适不过了。这真是绝妙的搭配啊！

• P1088

• P1045

• P1403

• P1017

• P1147

• P1029

  递推与递归二分

  递推，层层递进，由基础推向顶层。二分不仅可以用来查找数据，还可以确定最合适的值。

• P1192

• P1025

• P1057

• P1135

• P1216

• P1182

• P1316

  线性数据结构

  数组，链表，队列，栈，都是线性结构。巧用这些结构可以做出不少方便的事情。

• P1996

• P1115

• P1739

• P1160

• P1449

  树形数据结构

  由一个根节点分叉，越分越多，就成了树。树可以表示数据之间的从属关系

• P1087

• P1030

• P1305

• P5018

  动态规划的背包问题

  这是最基础的动态规划。不过如果是第一次接触会有些难以理解。加油闯过这个坎。

• P1060

• P1164

• P1064

• P1048

• P1049

• P1616

  线性动态规划

  这也是基础的动态规划。是在线性结构上面的动态规划，一定要掌握。

• P1020

• P1091

• P1280

• P1880

• P1140

• P1282

  多维动态规划

  这里的动态规划就不止一维了。不仅要小心时间复杂度，也要注意空间复杂度。

• P1508

• P1006

• P1387

• P1417

• P1855

• P1736

  更要技巧的动规与记忆化

  这边的题目有各种搞法。当然有的题目也可以使用记忆化搜索来降低思维难度。

• P1064

• P1541

• P1026

• P1063

• P1156

• P1052

  高精度算法

  就算是long long（或int64）还不够怎么办？用高精度算法。自己动手丰衣足食。

• P1601

• P2142

• P1303

• P1255

• P1604

  贪心EX

  虽然是贪心题，可能不是你当时你虐着玩的贪心惹qwq

• P1080

• P1031

• P1233

• P2123

  简单数学

  数学和oi是密切相关的，数学不仅是oi的基础，而且是算法的核心。

• P1865

• P1372

• P1338

• P2158

• P1582

  BOSS战-普及综合练习1

  好不容易闯到这一关，你那还等什么呢？抄起家伙赶快上啊！

• P1478

• P1203

• P1363

• P1736

  BOSS战-普及综合练习2

  来搞定第二个BOSS。虽然战斗艰难，但你一定没有问题。

• P1201

• P1095

• P1058

• P2258

• P1108

  BOSS战-普及综合练习3

  普及练习场的大BOSS：“一定让你有去无回”。怎么办呢？只能打倒他开启下一个级别！

• P1328

• P1062

• P1969

• P1037

  普及常见模板

  这里集中了比较基础的算法的模板。提高和省选也有模板题哦！

• P1177

• P3366

• P3367

• P3371

• P3383

  提高历练地

  已经去除了普及组难度的，请组织放心。成长大牛之必写题！！！

搜索Ex

开始提高组的试炼。这里已经去除了所有普及组难度的题目。哼哼，怕了吧。。

• P1120

• P1378

• P1514

• P1312

• P1441

• P1242

  动态规划TG.lv(1)

  这是提高组难度中比较基础的动态规划，也许一两个转移方程就可以写出。

• P1005

• P1373

• P2279

• P1220

• P1156

  动态规划TG.lv(2)

  这里的动态规划稍稍有所加大难度，思考转移方程的时间可能会与编写程序的时间持平。

• P1273

• P1169

• P2577

• P1070

• P2051

  动态规划TG.lv(3)

  比较需要技巧的动态规划。有的不仅仅需要状态转移方程，可能还会与别的算法综合。

• P1415

• P2157

• P2216

• P2331

• P2467

• P3084

  数论

  数论就是研究整数的理论。包括公约公倍数、质数、欧拉定理和同余方程等。

• P2152

• P1414

• P1134

• P1313

• P1306

  博弈论

  博弈论考虑游戏中的个体的预测行为和实际行为，并研究它们的优化策略。

• P1199

• P1288

• P1290

• P2148

• P1247

• P2575

  其他数学问题

  听说学oi的同志们数学都挺好。那么。就请完成下面的题目证明这一点吧！

• P1357

• P1641

• P2059

• P2154

• P2261

• P2327

• P1066

  图的遍历

  图是一种非常重要的数据结构，描述对象复杂的练习。这里开始接触图的基本概念。

• P2661

• P1330

• P1341

• P2921

  最短路问题

  最短路是图论中最重要的部分，多种算法可以应用。很多题目都可以抽象成这种模型。

• P1339

• P1462

• P1346

• P1119

• P1144

• P1522

  最小生成树

  最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

• P1546

• P2330

• P1991

• P1265

  较复杂图论I

  别的些图论问题，包括树、拓扑排序等。要过这一关，需要学习不少新的算法。

• P1113

• P1268

• P1525

• P1983

  较复杂图论II

  更高级的图论算法。包括差分约束、强连通、二分图等。会更难一些。

• P1993

• P1726

• P2055

• P2149

• P1345

  并查集

  用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。

• P1111

• P2024

• P1197

• P1196

  堆

  堆总是一棵完全树；堆中某个节点的值总是不大于或不小于其父节点的值。

• P1801

• P2278

• P1631

• P2085

• P1484

  线段树树状数组基础

  这都是比较高级的线性数据结构。在处理一些询问与修改线性问题时，是很好用的。

• P1972

• P1198

• P2023

• P2161

  神奇的解法

  有些问题刚开始觉得无从下手。好好想一想，尽量别看题解，否则你会大呼“简单”。

• P1007

• P1984

• P2022

• P2320

  倍增

  一种特殊的枚举算法，但可大大加快效率。近年noip有考到。难度较大。

• P1967

• P1081

• P1613

  强连通分量

  强连通分量

• P2341

• P3469

• P2746

• P3119

• P3225

  BOSS战-提高综合练习1

  年轻人，又是个送上门的，让我来看看你真实的本领。啊哈哈哈哈哈！

• P2264

• P1772

• P1083

• P1979

• P2939

  BOSS战-提高综合练习2

  再来！这里有的题目并非单纯的考察某个算法，而是考察一种综合性的思维。

• P1901

• P1314

• P2144

• P1073

• P2324

  BOSS战-提高综合练习3

  既然已经打倒了前面2个boss，那么第3个也是没有问题的。少年，来吧！

• P1965

• P1311

• P2296

• P1084

  提高模板-nlogn数据结构

  虽然这些算法不是noip必须的，但是不算困难，很多题目可以使用这些方法。

• P3374

• P3368

• P3372

• P3373

• P1439

• P3378

  省选斗兽场/NOI神殿

  为省选及以上选手制作的训练场。其实，省选水平的oier不需要一些外加的刷题列表，本栏仅供参考，也欢迎各位指出不足。

省选基础-读入/输出优化

读入/输出优化是省选刷题时必要的一个东西，这里给出了几题，需要自己手写相应的读入输出处理。作为第一关，这一关相对简单。

• P1580

• P2393

• P2394

  省选基础-位运算

  位运算往往在必要的时候,能带你优化一下常数,也许是空间;也许是时间;有的时候这样可以多过很多分

• P2114

• P2396

• P2397

  省选基础-打表

  打表虽然很赖皮,而且基本都是非正解,但是这种办法能让我们在省选中拿到一些会超时或者会超空间的一些数据点

• P1149

• P1463

• P1896

  动态规划1

  动态规划

• P2051

• P1879

• P1850

• P2831

• P1131

• P1169

  动态规划2

  动态规划

• P1273

• P3648

• P2519

• P2515

• P3233

• P2501

  网络流——最大流

  最大流

• P2765

• P2764

• P2763

• P2766

• P2774

• P2805

  网络流——费用流

  费用流

• P2153

• P2053

• P3159

• P2604

• P2050

• P3980

  单调队列

  单调队列

• P2698

• P2216

• P2219

• P2564

• P2569

  概率期望

  概率期望

• P2473

• P2221

• P3317

• P3343

• P3600

• P3830

  二分图

  二分图

• P3386

• P1640

• P1129

• P1963

• P3231

• P2526

  点分治

  点分治

• P2634

• P2664

• P3806

• P3676

  后缀数组

  后缀数组

• P3809

• P1117

• P2178

• P2463

• P2336

  主席树

  主席树

• P2468

• P3157

• P3302

• P3168

• P3313

  数位D* P

  数位D* P

• P2602

• P3281

• P2518

• P2606

  AC自动机

  AC自动机

• P3808

• P3796

• P2444

• P2414

  平衡树

  平衡树

• P2042

• P2596

• P1110

• P3285

• P3644

• P3765

• P3369

  树链剖分

  树链剖分

• P2590

• P2486

• P2146

• P3258

• P3178

  动态树

  动态树

• P3690

• P2387

• P3203

• P3348

  树套树

  树套树

• P1903

• P3157

• P3332

• P2166

• P3380

• P2137

• P3759

  可持久化Trie树

  可持久化Trie树

• P2048

• P3527

• P3302

• P3168

• P3242

• P3241

• P3293

  莫队算法

  莫队算法

• P1972

• P2336

• P3709

• P2709

• P3674

  分块

  分块

• P1972

• P3396

• P1822

• P2801

• P3203

  莫比乌斯反演

  莫比乌斯反演

• P3768

• P3172

• P3455

• P2522

• P3327

  其他

  其他

• P3377

• P3261

• P3382

• P2571

• P3222

• P3187

• P3199

• P3292

• P2824

• P3285

• P1552

  USACO

  美国经典的算法练习题库，值得一刷

USACO Section 1.1

• P1200

• P1201

• P1202

• P1203

  USACO Section 1.2

  完全枚举

• P3864

• P1204

• P1205

• P1206

• P1207

  USACO Section 1.3

  贪心

• P1208

• P1209

• P1211

• P1444

• P3650

• P2693

  USACO Section 1.4

  有技巧的枚举

• P1214

• P1215

  USACO Section 1.5

  二进制数

• P1216

• P1217

• P1218

  USACO Section 2.1

  图论和洪水填充

• P1457

• P1458

• P1459

• P1460

• P1461

  USACO Section 2.2

  数据结构与动态规划

• P1465

• P1466

• P1467

• P1468

  USACO Section 2.3

• P1470

• P1472

• P1473

• P1474

• P1475

  USACO Section 2.4

  最短路径

• P1518

• P1519

• P1522

• P1529

• P1530

  USACO Section 3.1

  最小生成树

• P1546

• P2722

• P2723

• P2724

• P2725

  USACO Section 3.2

  背包问题

• P1134

• P2727

• P2728

• P2729

• P2730

• P1828

  USACO Section 3.3

  欧拉回路

• P2731

• P2732

• P1930

• P2733

• P2734

  USACO Section 3.4

  计算几何

• P1827

• P2735

• P2736

  USACO Section 4.1

  最优化

• P2737

• P2738

  USACO Section 4.2

  网络流

• P2740

• P1894

• P2751

  USACO Section 4.3

  高精度

• P2687

• P2752

• P2753

  USACO Section 4.4

• P1344

• P2739

• P2741

  USACO Section 5.1

  二维凸包

• P2742

• P2743

• P2749

  USACO Section 5.2

• P1560

  USACO Section 5.3

  启发式搜索

• P2701

• P2744

• P2745

• P2746

  USACO Section 5.4

• P1345

• P2747

• P2748

  USACO Section 5.5

• P1709

• P1856

• P2750