oi-wiki-18.12.pdf

发布时间：2022-06-07 发布人：admin 分类：说明书资料大小：4.76M 资料格式：pdf 举报版权申诉

m0_37938791-12412478-16359647558467366317.pdf-第1页.png

第1页 / 共525页

m0_37938791-12412478-16359647558467366317.pdf-第2页.png

第2页 / 共525页

m0_37938791-12412478-16359647558467366317.pdf-第3页.png

第3页 / 共525页

m0_37938791-12412478-16359647558467366317.pdf-第4页.png

第4页 / 共525页

m0_37938791-12412478-16359647558467366317.pdf-第5页.png

第5页 / 共525页

m0_37938791-12412478-16359647558467366317.pdf-第6页.png

第6页 / 共525页

m0_37938791-12412478-16359647558467366317.pdf-第7页.png

第7页 / 共525页

m0_37938791-12412478-16359647558467366317.pdf-第8页.png

第8页 / 共525页

简介

欢迎来到 OI Wiki。

OI 赛制简介

赛事介绍

NOIP

省选

NOI

APIO

CTSC

IOI

赛制介绍

OI 赛制

IOI 赛制

ICPC 赛制

Codeforces (CF) 赛制

其他国家和地区的 OI 竞赛

美国：USACO

波兰：POI

克罗地亚：COCI

日本：JOI

台湾地区：資訊奧林匹亞競賽

俄罗斯：ROI

加拿大：CCC & CCO

法国与澳大利亚：FARIO

其它大洲级 OI 竞赛

BalticOI

BalkanOI

CEOI

Nordic Olympiads in Informatics (NOI)

学习资源

在线测试 (训练) 平台

国内

国外

教程

书籍

工具

题集

常见错误

常见技巧

评测工具

Cena

Lemon

自行编译

数据格式

Arbiter

使用方法

注意事项，槽点

自定义校验器的编写

测评时注意事项

诶我怎么只能看见代码不能看见每个点得多少分

诶这个测评系统好难看

诶怎么测提交答案题啊

诶这个测评系统有没有漏洞

吐槽

CCR-Plus

编辑工具

Vim – 编辑器之神

历史与争端

安装

编译

基础篇

插入模式 (insert)

普通模式 (normal)

命令行模式

可视模式

插件篇

文件管理

美化界面

启动界面

小方便性插件

配置篇

基础设置

快捷键设置

写代码好用的

关于插件

关于高效编辑的建议

Visual Studio Code - 微软家的编辑器

简介

WSL (Windows 10)

0x01 引言

0x02 准备

0x04 基础配置

更换为国内软件源

安装中文环境

安装编译环境

0x05 进阶操作

安装图形环境，并使用远程桌面连接

0x09 延伸内容

后记

Special Judge

Testlib

Lemon

Cena

CCR

Arbiter

HUSTOJ

QDUOJ

LibreOJ(SYZOJ 2)

Testlib

关于本项目

基础部分

基础部分简介

枚举

给出解空间

减少枚举的空间

选择合适的枚举顺序

模拟

递归 & 分治

递归

递归三要素

递归式

递归出口

界函数

递归模板

递归优化

分治

贪心

常见做法

证明方法

排序法

后悔法

code

排序

稳定性

时间复杂度

冒泡排序

归并排序

逆序对

参考

快速排序

STL

线性找第 k 大的数

参考

计数排序

参考

排序的应用

表达式求值

递归

非递归

习题

二分

二分搜索

STL 的二分查找

三分法

分数规划

二分法

Dinkelbach 算法

构造

前缀和 & 差分

前缀和

参考

文件操作

文件的概念

文件的操作步骤

freopen 函数

命令格式

参数说明

使用方法

模板

C++ 的 ifstream/ofstream 文件输入输出流

使用方法

模板

搜索

搜索部分简介

深度优先搜索 (DFS)

宽度优先搜索 (BFS)

双向宽度优先搜索

A 搜索

IDA 搜索

剪枝

极端法

调整法

数学方法

meet-in-middle 分治

DFS

模板

实现（对于图来说）

在树 / 图上 DFS

BFS

实现

open-closed 表

在树 / 图上 BFS

应用

例题

参考

双端队列 BFS

适用范围

实现

例题

Codeforces 173B

Code

优先队列 BFS

双向 BFS

启发式搜索

例题八数码

例题 k 短路

迭代加深搜索

简介

步骤

代码结构

注意事项

IDA*

IDA 简介

优点

缺点

例题

练习题

回溯法

Dancing Links

优化

前言

优化与剪枝

记忆化搜索

最优性剪枝

可行性剪枝

动态规划

动态规划部分简介

钢条切割

矩阵链乘法

动态规划原理

1. 最优子结构

2. 子问题重叠

重构最优解

最长公共子序列

最优二叉搜索树

最长连续不下降子序列

最长不下降子序列

最简单的第一种

稍复杂的第二种

经典问题（来自习题）

DAG 中的最长简单路径

最长回文子序列

最长回文子串

双调欧几里得旅行商问题

思路一

思路二

整齐打印

编辑距离

最优对齐问题

公司聚会计划

译码算法

基于接缝裁剪的图像压缩

字符串拆分

投资策略规划

库存规划

签约棒球自由球员

记忆化搜索

记忆化搜索是啥

总结一下记忆化搜索是啥

记忆化搜索与动态规划的关系

如何写记忆化搜索

方法 I

方法 II

记忆化搜索的优缺点

记忆化搜索的注意事项

模板

背包 DP

0-1 背包

完全背包

多重背包

区间 DP

什么是区间 DP？

怎样进行状态转移

怎样处理环

核心代码

几道练习题

DAG 上的 DP

例子

建立 DAG

转移

题解

树形 DP

例题

习题

状压 DP

状压 dp 简介

常用格式

典型例题

数位 DP

经典题型

几道练习题

插头 DP

DP 优化

二进制优化解多重背包

几道练习题

单调队列 & 单调栈优化

几道练习题

斜率优化

几道练习题

四边形不等式优化

什么是四边形不等式？

回到题目

说了这么多，怎么进行状态转移呢？

时间复杂度证明

一道练习题：

参考资料

其它 DP 方法

字符串

字符串部分简介

字符串是啥？

字符集

如何存字符串

字符串存储的位置

C / C++ 标准库中的字符串

C 标准库

strlen

printf

scanf

sscanf

sprintf

strcmp

strcpy

strncpy

strcat

strstr

strchr

strrchr

C++ 标准库

std::string

字符串匹配

字符串匹配问题

单串匹配

多串匹配

匹配一个串的任意后缀

匹配多个串的任意后缀

暴力做法

Hash 的方法

KMP 算法

哈希

Hash 的思想

Hash 的实现

Hash 的分析与改进

Hash 的应用

前缀函数与 KMP 算法

前缀函数定义

朴素算法

高效算法

第一个优化

第二个优化

最终算法

实现

应用

在字符串中查找子串：Knuth-Morris-Pratt 算法

统计每个前缀的出现次数

一个字符串中本质不同子串的数目

字符串压缩

根据前缀函数构建一个自动机

练习题目

字典树 (Trie)

Trie

在 Trie 上 KMP

回文自动机

回文树

后缀数组 (SA)

1. 前言

后缀数组和后缀树

各种定义

2. 一些构造方法

最简单的暴力

倍增

AC 自动机

KMP 自动机

AC 算法就是 Trie 上的自动机

AC 自动机的实现

后缀自动机 (SAM)

后缀自动机的定义

子串的性质

构造后缀自动机的实例

在线性时间内构造后缀自动机

结束位置 endpos

后缀链接

小结

算法

正确性证明

对操作次数为线性的证明

实现

更多的性质

状态数

转移数

应用

检查字符串是否出现

不同子串个数

所有不同子串的总长度

字典序第k大子串

最小循环移位

出现次数

第一次出现的位置

所有出现的位置

最短的没有出现的字符串

两个字符串的最长公共子串

多个字符串间的最长公共子串

例题

最近公共祖先

定义

性质

求法

朴素算法

倍增算法

Tarjan 算法

转化为 RMQ 问题

树链剖分

动态树

标准 RMQ

DFS 序

树的其他问题

树的重心

定义

性质

求法

参考

树链剖分

树链剖分的思想及能解决的问题

例题 luogu P2590 ZJOI2008 树的统计

一些定义

解法

完整代码

时间复杂度证明

练习

树分治

动态树分治

有向无环图

定义

性质

判定

拓扑排序

定义

Kahn 算法

时间复杂度

实现

DFS 算法

合理性证明

参考

最小生成树

定义

Kruskal 算法

证明

实现

“集合” 数据结构的一种实现

Prim 算法

证明

实现

最小生成树小结

最小生成树题目

最小生成树的唯一性

次小生成树

第 k 小生成树

最短路

定义

性质

Floyd 算法

实现

应用

Bellman-Ford 算法

实现

应用

队列优化：SPFA

SPFA 的优化之 SLF

Dijkstra 算法

实现

不同方法的比较

拓展：分层图最短路

模板题：JLOI2011 飞行路线

差分约束

常用变形技巧

例题 luogu P1993 小 K 的农场

例题 P4926 1007 倍杀测量者

Bellman-Ford 判负环代码实现

习题

k 短路

强连通分量

简介

Tarjan 算法

定义

DFS 树的性质

实现

Kosaraju 算法

实现

Garbow 算法

应用

推荐题目

双连通分量

简介

定义

DFS

DFS 找桥并判断边双联通

DFS 找割点并判断点双联通

割点和桥

割点

如何实现？

例题

Code

割边

实现

2-SAT

定义

现实意义

常用解决方法

Tarjan SCC 缩点

爆搜

爆搜模板

例题

HDU3062 Party

练习题

欧拉图

二分图

定义

性质

判定

应用

二分图匹配

最大匹配

最大权匹配

一般图匹配

最小环

问题

暴力解法

Dijkstra

Floyd

例题

网络流简介

浅谈网络流基础

网络流基础知识以及解法

流量

最大流

最小费用最大流 (MCMF)

最大流解法锦集

Edmond-Karp 动能算法（EK 算法）

Dinic

ISAP

最小费用最大流解法

网络流基础知识拓展

最小割

二分图匹配

建模

网络流拆点

例题经典问题结点有流量限制的最大流

例题 luogu P4568 飞行路线

最大流

最小割

费用流

上下界网络流

计算几何

计算几何部分简介

二维计算几何基础

0. 前置技能

1. 图形的记录

1.1. 点

1.2. 向量

1.3. 线

1.3.1. 直线与射线

1.3.2. 线段

1.4. 多边形

1.5. 曲线

2. 基本公式

2.1. 正弦定理

2.2. 余弦定理

3. 基本操作

3.1. 判断一个点在直线的哪边

3.2. 快速排斥实验与跨立实验

3.3. 判断一点是否在任意多边形内部

3.3.1. 光线投射算法 (Ray casting algorithm)

3.3.2. 回转数算法 (Winding number algorithm)

3.4. 求两条直线的交点

3.5. 求任意多边形的周长和面积

3.5.1. 求任意多边形的周长

3.5.2. 求任意多边形的面积

3.6. 圆与直线相关

3.6.1. 求直线与圆的交点

3.6.2. 求两圆交点

3.7. 极角序

4. 代码编写注意事项

三维计算几何基础

Pick 定理

三角剖分

凸包

扫描线

旋转卡壳

半平面交

计算几何杂项

杂项

杂项简介

这个板块主要介绍的是一些难以分类的实用算法、实用技巧

非传统题

CDQ 分治

引子

CDQ 分治解决和点对有关的问题

三维偏序

例题 [CQOI2011]动态逆序对

2 CDQ 分治优化 1D/1D 动态规划的转移

例题[SDOI2011] 拦截导弹

需要 CDQ 将动态问题转化为静态问题的题

矩形加矩形求和

[Ynoi2016]镜中的昆虫

[HNOI2010]城市建设

莫队算法

普通莫队算法

概述

形式

实现

排序方法

模板

复杂度分析

例题 & 代码

带修改

特点

例题

树上莫队

爬山算法

简介

实现

代码

劣势

分数规划

习题

模拟退火

简介

实现

模拟退火算法描述

如何退火（降温）？

代码

习题

朱刘算法

矩阵树定理

本篇记号声明

无向图情况

有向图情况

定理叙述

BEST 定理

例题

注释

随机增量法

随机化

离线处理

距离

OI 中常用的几类距离

曼哈顿距离

切比雪夫距离

欧几里得距离（又称欧氏距离）

L_m 距离

汉明距离

字节顺序

小端序

大端序

惯例

复杂度

渐进符号

符号

O 符号

符号

常见性质

主定理 (Master Theorem)

均摊复杂度

势能分析

读入、输出优化

关闭同步 / 解除绑定

std::ios::sync_with_stdio(false)

tie

代码实现

读入优化

原理

代码实现

输出优化

原理

代码实现

更快的读入 / 输出优化

参考

离散化

简介

实现

树上启发式合并

引入

算法内容

复杂度

大致代码

运用

练习题

参考资料 / 扩展阅读

OI Wiki.pdf version: 18.12-874a2f8 OI Wiki Team 2018 年 11 ⽉ 30 ⽇

iii 前⾔声明 OI Wiki 致⼒于成为⼀个免费开放且持续更新的知识整合站点，⼤家可以在这⾥获取关于编程竞赛 (compet- itive programming) 有趣⼜实⽤的知识，我们为⼤家准备了竞赛中的基础知识、常⻅题型、解题思路以及常⽤⼯具等内容，帮助⼤家更快速深⼊地学习编程竞赛。建议访问 https://oi-wiki.org 以阅读持续更新的内容。 OI Wiki 除了代码部分均采⽤ (Creative Commons BY-SA 4.0) 知识共享署名 - 相同⽅式共享 4.0 国际许可协议及附加的 The Star And Thank Author License 进⾏许可。换⾔之，使⽤过程中您可以⾃由地共享、演绎，但是必须署名、以相同⽅式共享、分享时没有附加限制，⽽且需要为 GitHub 仓库点赞（Star）。 OI Wiki 源于社区，提倡知识⾃由，在未来也绝不会商业化，将始终保持独⽴⾃由的性质。在编写过程中，作者听取了⼤量同学的意⻅和观点，并尽可能地将各种观点统⼀在项⽬的框架下。但是我们并不能保证内容中没有对其他组织的误解或偏⻅，⽽内容的正确性也没有经过权威审查。我们亦⽆⼒确认⼿册是否违反了读者所在地的各种法规，或是⼿册内容是否会对读者⾝⼼健康产⽣不良影响。对于未经授权的传播⽽产⽣的各种问题，我们概不负责。如果您有任何问题或建议，可以通过 Github Issues，讨论群，或发邮件到 hi@oi-wiki.org 来联络我们。欢迎⼀起来完善 OI Wiki！

iv 致谢很荣幸在此感谢那些帮助我们的⼈们。我们要感谢 CTF Wiki，本项⽬是受他们启发。另外在编写过程中我们参考了诸多资料，在此也⼀并致谢。 Ir1d, LeoJacob, 和 MingqiHuang 制作了这个 Pdf。⾮常感谢⼀起完善 OI Wiki 的⼩伙伴们，他们充满感染⼒的精⼒和热情给了这个项⽬极⼤的⽀持： saffah, wangyisong1996, Xeonacid, greyqz, hsfzLZH1, abc1763613206, cjsoft, frank- xjh, i-Yirannn, Planet6174, MingqiHuang, Zhoier, LuoshuiTianyi, Anguei, Mosa-Linking, ACodreamer, CBW2007, dsy031120, HeRaNO, StudyingFather, stevebraveman, Steaunk, billchenchina, AndrewWayne, Dev-XYS, interestingLSY, Chrogeek, yeguanghao, LeoJacob, cesonic, Dev- jqe, siger-young, ChungZH, HXLLL, JulieSigtuna, SysConKonn, Ycrpro, pw384, wjy-yy, konnyakuxzy, Yukimaikoriya, ZhangBo1191, juicymio, Kewth, NiroBC, ShadowsEpic, Xarfa, goldimax, ksyx, s0cks5, wangchong, ywwywwyww, cqnuljs, Alpha1022, 2997ms, Konano, SkqLiao, zj713300, Siej, yjl9903, kzoacn, saotomeku, cutekibry, henrytbtrue, qq1010903229, qq2964, shadowice1984, AljcC, DeepThink1, cquptEthan, FTYC919, Frankaiyou, GldHkkowo, BalanceUhen, lushl9301, Enter-tainer, MingqiHuang@yandex.com, NeverBehave, Too-Naive, VirtualHawthorn, WaterWan, sailordiary, Yukimaikoriya, Zhaoyangzhen, evrmji, gryzhmq, pretend-fal, sunqingyanstc, akakw1。图 1: Contributors 另外，也要特别感谢 24OI 的朋友们的⼤⼒⽀持！最后，感谢董⼩姐，让这⼀切成为可能。

⽬录 1 简介 1.1 欢迎来到 OI Wiki。 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . OI 赛制简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 1.2.1 赛事介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NOIP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 省选 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . NOI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . WC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . APIO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CTSC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IOI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.2 赛制介绍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . OI 赛制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . IOI 赛制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ICPC 赛制 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Codeforces (CF) 赛制 . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.3 其他国家和地区的 OI 竞赛 . . . . . . . . . . . . . . . . . . . . . . . . . 美国：USACO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 波兰：POI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 克罗地亚：COCI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ⽇本：JOI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 台湾地区：資訊奧林匹亞競賽 . . . . . . . . . . . . . . . . . . . . . . . . 俄罗斯：ROI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 加拿⼤：CCC & CCO . . . . . . . . . . . . . . . . . . . . . . . . . . . . 法国与澳⼤利亚：FARIO . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2.4 其它⼤洲级 OI 竞赛 . . . . . . . . . . . . . . . . . . . . . . . . . . . . BalticOI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . BalkanOI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . CEOI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Nordic Olympiads in Informatics (NOI) . . . . . . . . . . . . . . . . 1.3 学习资源 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.1 在线测试 (训练) 平台 . . . . . . . . . . . . . . . . . . . . . . . . . . . 国内 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 国外 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.2 教程 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 5 5 5 5 5 5 6 6 6 6 6 6 7 7 i

ii 1.6.3 Arbiter 1.3.3 书籍 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.4 ⼯具 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3.5 题集 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4 常⻅错误 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5 常⻅技巧 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.6 评测⼯具 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ⽬录 8 8 9 9 9 9 1.6.1 Cena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.6.2 Lemon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 ⾃⾏编译 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 数据格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 使⽤⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 注意事项，槽点 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 ⾃定义校验器的编写 . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 测评时注意事项 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 诶我怎么只能看⻅代码不能看⻅每个点得多少分 . . . . . . . . . . . . . . . . 15 诶这个测评系统好难看 . . . . . . . . . . . . . . . . . . . . . . . . . . 15 诶怎么测提交答案题啊 . . . . . . . . . . . . . . . . . . . . . . . . . . 15 诶这个测评系统有没有漏洞 . . . . . . . . . . . . . . . . . . . . . . . . 15 吐槽 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.6.4 CCR-Plus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.7 编辑⼯具 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.7.1 Vim – 编辑器之神 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 历史与争端 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 安装 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 编译 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 基础篇 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 插⼊模式 (insert) . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 普通模式 (normal) . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 命令⾏模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 可视模式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 插件篇 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 ⽂件管理 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 美化界⾯ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 启动界⾯ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 ⼩⽅便性插件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 配置篇 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 基础设置 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 快捷键设置 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 写代码好⽤的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 关于插件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 关于⾼效编辑的建议 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.7.2 Visual Studio Code - 微软家的编辑器 . . . . . . . . . . . . . . . . . . 26 简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

⽬录 1.8 1.9 iii WSL (Windows 10) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.8.1 0x01 引⾔ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.8.2 0x02 准备 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.8.3 0x04 基础配置 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 更换为国内软件源 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 安装中⽂环境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 安装编译环境 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.8.4 0x05 进阶操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 安装图形环境，并使⽤远程桌⾯连接 . . . . . . . . . . . . . . . . . . . . . . 32 1.8.5 0x09 延伸内容 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 后记 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 Special Judge . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.9.1 Testlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 1.9.2 Lemon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 1.9.3 Cena . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 1.9.4 CCR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.9.5 Arbiter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.9.6 HUSTOJ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 1.9.7 QDUOJ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.9.8 LibreOJ(SYZOJ 2) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 1.10 Testlib . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 1.11 关于本项⽬ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2 基础部分 41 2.1 基础部分简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2 枚举 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2.1 给出解空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.2.2 减少枚举的空间 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.2.3 选择合适的枚举顺序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.3 模拟 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42 2.4 递归 & 分治 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.4.1 递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 递归三要素 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 递归式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 递归出⼝ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 界函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 递归模板 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 递归优化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.4.2 分治 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5 贪⼼ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5.1 常⻅做法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5.2 证明⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5.3 排序法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.5.4 后悔法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

iv ⽬录 code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 2.6 排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.6.1 稳定性 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.6.2 时间复杂度 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.6.3 冒泡排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.6.4 归并排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 逆序对 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 参考 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 2.6.5 快速排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 STL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 线性找第 k ⼤的数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 参考 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.6.6 计数排序 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 参考 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.6.7 排序的应⽤ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.7 表达式求值 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.7.1 递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.7.2 ⾮递归 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52 2.7.3 习题 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.8 ⼆分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.8.1 ⼆分搜索 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 STL 的⼆分查找 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.8.2 三分法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.8.3 分数规划 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 ⼆分法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 Dinkelbach 算法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 2.9 构造 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.10 前缀和 & 差分 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.10.1 前缀和 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 参考 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.11 ⽂件操作 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.11.1 ⽂件的概念 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.11.2 ⽂件的操作步骤 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 2.11.3 freopen 函数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 命令格式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 参数说明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57 使⽤⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 模板 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.11.4 C 的 ifstream/ofstream ⽂件输⼊输出流 . . . . . . . . . . . . . . . . 58 使⽤⽅法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 模板 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 3 搜索 61 3.1 搜索部分简介 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

分享到：

赞收藏

资料库

oi-wiki-18.12.pdf

相关推荐

操作系统

热门标签

最新资料