题意

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

思路

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

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

• 0：不进位也不退位

• 1：退位

• 2：进位

状态转移方程式如下：

$$f_{i,0}=\min {f_{i+1,0}+abs(a-b),f_{i+1,1}+abs(a-1-b),f_{i+1,2}+abs(a+1-b)}\\ f_{i,1}=\min {f_{i+1,0}+a+10-b,f_{i+1,1}+(a-1)+10-b,f_{i+1,2}+(a+1)+10-b}\\ f_{i,2}=\min {f_{i+1,0}+b+10-a,f_{i+1,1}+b+10-(a-1),f_{i+1,2}+b+10-(a+1)}$$

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

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

题意

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很像，甚至都不需要找规律，就是纯粹的分类讨论。

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

题意

给定一个只含‘E’、’B’、’F’的字符串，F可以被修改为E或B，求最终转化为没有‘F’的字符串中含有“EE”、“BB”的子串个数和的各种情况

思路

通过找规律可以发现最终的结果是一段等差数列，然后列举F的情况：

1. 首尾的F转变为E或B可以给答案增加0或1的贡献

2. 对于中间的F，若两边相同，转变为E或B可以给答案增加0或2的贡献；若两边不同，可以给答案增加1的贡献，这种F可以直接当作E或者B来看
   所以可以得出结论，如果首尾有F，那公差为1，否则公差为2，因此我们只需贪心的求最小值和最大值即可。然后，对于一连串的F，最小值尽可能间隔着以EBEBEB的形式放，最大值尽可能以EEE或BBB的形式放：

3. 对于情况1，最小值只要和最近的非F字符不同即可，可以做到贡献为0，最大值和最近的非F字符相同即可

4. 对于情况2，最小值由于需要间隔放，考虑到F串的左右两边相同或否，需要根据奇偶判断贡献为1/0；最大值无论和左边相同还是和右边相同结果一样

以下是我的字符串模板：编辑距离、后缀数组、回文树、扩展KMP、字符串哈希、AC自动机、Border、KMP、Manacher、SAM