题意

m份订单，每份订单需要从s天到t天租借d个教室，每天都有r个教室可供租借，每个订单含顺序执行，不需要考虑每天是否需要更换租借教室，求从哪份订单开始会供不应求

思路

​ 显然由于订单的不断积累，每天租借的教室数量保证会持续上涨，满足了单调性，再看一下时间复杂度，1e6的话O(nlogn)能卡，很自然的可以想到二分答案的做法。

​ 二分的难点主要在check，但是二分可以O(n)的来处理，那么我们可以将当前需要check的前x个订单内容加起来，再去查看每天是否有超出可租借范围的。这样思路上没问题，但是前x个订单内容加起来如果直接暴力执行的话，每天都加上某个值显然时间复杂度过高，这种区间加有两种处理方法，一种是直接上数据结构，无脑套线段树，另一种就是通过差分把区间加改为单点加，这样时间复杂度就没有问题了。

二分查找

最早接触二分一般都是从二分查找开始，对于一串有序数列（假设单调递增），如果中间值小了就往右半边找，如果中间值大了就往左半边找。

代码如下(此处为找最后一个等于x的数，如果没有x则为大于x的第一个数)：代码为什么这么写后面会讲

1
2
3
4
5
6
7

int l=1,r=n;
while(l<=r){
	int mid=l+r>>1;
	if(mid<=x)l=mid+1；
	else r=mid-1;
}
cout<<r<<endl;

显然对于二分不可能只局限于二分查找，我们经常会遇到对于答案进行二分的情况，将if语句中的mid<=x换成check(mid),就是我们常见的二分模板，其实二分查找也可以通过修改check函数得到

什么情况可能会使用二分

1. 单调有序数列

2. 最大值的最小值/最小值的最大值

3. O(nlogn)的时间复杂度（logn的二分，O(n)的暴力扫一遍）

题意

给定n位字符串，可以对每位进行+1/-1的操作，同时产生相应的进位/退位，9999+1将会变为0000，求变成目标串最少的操作次数

思路

这道题一开始还以为是ICPC沈阳的一道题Luggage Lock，但是那道题可以对连续几位同时进行+1/-1，本题只能对一位处理且会产生进位/退位。

正解为状态机dp，表示当前在第位,将要通过方式所需要的最少操作次数，其中方式分别表示：

• 0：不进位也不退位

• 1：退位

• 2：进位

状态转移方程式如下：

由于某一位的改变只会对他的前面一位产生影响，所以需要倒着进行遍历

不需要考虑第一位的改变对于最后一位的影响，显然第一位进位不会更优

题意

n个点，每个点都可以加整数升油，每个点加油的单价不同，1升油可以行驶d km，求到达终点所要花费的最少金钱

思路

贪心思路，每次遇到单价更少的就用单价更少的加油方式

开始回归算法了，先来波div 4练练手

Vlad and the Best of Five

题意

给定一个字符串，求A和B哪个更多

分析

直接遍历，拿两个变量记录下

介绍

定义

JSON 是一种按照 JavaScript 对象语法的数据格式，是一种文本规范。

优点

可以很好地表示树形结构，简洁易读。

注意

Json实际上是一种字符串，在程序使用json数据时，需要通过特定的方法转换为对应的对象变量。

介绍

定义

docker是一个用Go语言实现的开源项目，可以让我们方便的创建和使用容器，docker将程序以及程序所有的依赖都打包到docker container，这样你的程序可以在任何环境都会有一致的表现。

优势

1. docker可以屏蔽环境差异

2. 快速部署

介绍

定义

​ Git是一个开源的版本控制系统，可以将Git理解为存储文件的仓库，方便多个用户将文件集中存储到服务器中，或从服务器下载文件副本到本地磁盘。

​ Git服务并不是简单地存储文件，它会记录每一次文件修改。用户可翻看历史版本的文件，或者删除某些历史修改以还原文件。

​ 例如，在实际开发过程中，会经常出现一些功能回退。就是以前好用的，现在却出现BUG的情况。

​ 通过翻看代码文件的历史版本，可较快速地定位哪次修改影响了这个功能，也能知道团队中哪个人做了这次修改。

关系

那么，Git、Gitlab、GitHub是什么关系呢。

​ Git可以理解为系统核心，是没有界面的。

​ Gitlab、GitHub是在Git基础上建设的平台，里面包含Git服务，这些平台拥有更加完善的后台管理网站。也拥有更加丰富的功能，如项目管理、版本视图、权限管理等。

​ 所以我们一般不直接使用或部署Git服务，而是使用功能更加完善的Gitlab、GitHub平台服务，其中Gitlab支持私有化部署。

题意

小蓝得到了一副大小为 M × N 的格子地图，可以将其视作一个只包含字符‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。

在岛屿 A 所占据的格子中，如果可以从中选出 k 个不同的格子，使得他们的坐标能够组成一个这样的排列：$(x_0, y_0),(x_1, y_1), . . . ,(x_ {k−1}, y_{k−1})$，其中$(x_{(i+1)\%k} ,y_{(i+1)\%k})$是由 通过上/下/左/右移动一次得来的 ，此时这 k 个格子就构成了一个 “环”。如果另一个岛屿 B 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 B 视作是岛屿 A 的子岛屿。若 B 是 A 的子岛屿，C 又是 B 的子岛屿，那 C 也是 A 的子岛屿。

请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。

思路

题目简而言之，就是有很多岛屿，会出现大岛屿包着小岛屿的情况（这种情况只算一个岛屿），求岛屿数量

主体思路就是先把整张图划分为河流与大岛屿，各个大岛屿之间通过河流分割，大岛屿内部的河流直接用1填补，这样就避免了小岛屿、大岛屿之间的影响。然后剩下来没发现一个大岛屿，进行记数并将整个岛屿覆盖为河流。

题意

给定一个只含‘0’、’1’、’?’的字符串，？可以被修改为0或1，求最终转化为没有‘？’的字符串中含有“00”、“1”的最多不重叠子串个数

思路

和前一题FEBacwing 4993 FEB很像，甚至都不需要找规律，就是纯粹的分类讨论。

？尽可能去把相邻的奇数连续串弥补即可