题意

给定长度为n的数列，求出连续序列和为k的倍数的序列个数。

思路

首先，对于每一段前缀和都进行对k取余。

那么根据同余定理，,如果一段前缀和如果和前面的某段前缀和的值相同，那么前面的那个前缀所缺少的几个数（除最后一个元素）的和一定是k的倍数，对于每个余数所对应的前缀和数量，用一个map记录一下即可。

最后记得再加上，因为每次前缀和所得的那几个数并不包括尾部，所以当遍历到最后一个元素时，并无法得出包括最后一个元素的符合条件的连续序列数量，而是包括最后一个前面的那个元素的符合条件的连续序列数量。

题意

几间房间有各自的温度，每次操作可以对连续的几间房间+1/-1度，请问使每个房间都到达目标温度的最小操作次数

思路

​ 将目标温度减去起始温度后会得到一串数列a，目标就是求使这串数列全部为0的操作次数，由于需要实现区间加，比较容易联想到使用差分来进行操作。

​ 转化为差分数组后，每次操作就可以转化为对于某个位置+1/-1，在对某个位置-1/+1，或者不存在后者（就是位置为数列尾部+1）。

​ 这样就只需要比较到底是+1的次数多还是-1的次数多即可

题意

对一些墙壁进行作画，被作画的墙不会毁掉，只有和一面墙相邻的会被毁掉，每天可以画一面墙，每天画的墙必须和昨天画的相邻，然后会有一面墙被毁掉，每堵墙都有美观分，求使最终剩下的墙美观分能够到达的总和最高的值。

思路

首先只有和一面墙相邻的会被毁掉意思就是从两端开始毁掉，由于每天画一面墙，毁一面墙，那最终是能保留面墙，那么题目就是求长度为的连续序列和的最大值。

然后，我们就需要枚举每个起点，来比较以此为起点的连续序列和。其实循环下去每次减一个头元素，再加一个尾元素也可以。但是这边用前缀和来处理，每个连续序列和的计算公式为，需要注意的是，虽然是以为起点，但是号元素还是需要的，想要获取以为起点的连续序列和，需要减去前面的前缀和。

题意

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. 快速部署