引言
今天还是三道新题，多练多想才会有出路。
一、保险箱
标签：状态机DP
思路：这道题看的我懵的很，大概意思就是每一位有三种状态 f [ i ] [ 3 ] f[i][3] f[i][3] 分别为借位、啥也不干、进位，然后从 i i i 到 n n n 已经相等的最优方案数。然后有个判断条件 10 ∗ j = a [ i ] + k + t − b [ i ] 10*j = a[i] + k + t - b[i] 10∗j=a[i]+k+t−b[i] ，就说明这是种解决方案，然后就循环遍历，找最小的就行。 其实自己
题目描述：
小蓝有一个保险箱，保险箱上共有 n 位数字。
小蓝可以任意调整保险箱上的每个数字，每一次操作可以将其中一位增加 1 或减少 1。
当某位原本为 9 或 0时可能会向前（左边）进位/退位，当最高位（左边第一位）上的数字变化时向前的进位或退位忽略。
例如:
00000 的第 5 位减 1 变为 99999；
99999 的第 5 位减 1 变为 99998；
00000 的第 4 位减 1 变为 99990；
97993 的第 4 位加 1 变为 98003；
99909 的第 3 位加 1 变为 00009。
保险箱上一开始有一个数字 x，小蓝希望把它变成 y，这样才能打开它，问小蓝最少需要操作的次数。
输入格式
输入的第一行包含一个整数 n。
第二行包含一个 n 位整数 x。
第三行包含一个 n 位整数 y。
输出格式
输出一行包含一个整数表示答案。
数据范围
对于 30% 的评测用例，1≤n≤300；
对于 60% 的评测用例，1≤n≤3000；
对于所有评测用例，1≤n≤105，x,y 中仅包含数字 0 至 9，可能有前导零。
输入样例：
5
12349
54321
输出样例：
11
示例代码：
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
char a[N], b[N];
int f[N][3];
int main()
{
scanf("%d%s%s", &n, a, b);
memset(f, 0x3f, sizeof f);
f[n][1] = 0;
for(int i = n - 1; i >= 0; --i)
{
for(int j = 0; j < 3; ++j) //j表示向高位操作
{
for(int k = -9; k <= 9; ++k)
{
for(int t = 0; t < 3; ++t) //t表示向低位操作
{
if(a[i] + k + t - 1 - b[i] == (j-1) * 10)
f[i][j] = min(f[i][j], f[i+1][t] + abs(k));
}
}
}
}
printf("%d\n", min({
f[0][0], f[0][1], f[0][2]}));
return 0;
}
二、棋盘
标签：差分
思路：这就是一个差分的标准题，差分解决的是给[l,r]加上一个数，能实现O(1)的复杂度，这题只不过是二维的，不过也一样，忘了的话，可以看我之前的博客前缀和与差分
题目描述：
小蓝拥有 n×n 大小的棋盘，一开始棋盘上全都是白子。
小蓝进行了 m 次操作，每次操作会将棋盘上某个范围内的所有棋子的颜色取反(也就是白色棋子变为黑色，黑色棋子变为白色)。
请输出所有操作做完后棋盘上每个棋子的颜色。
输入格式
输入的第一行包含两个整数 n,m，用一个空格分隔，表示棋盘大小与操作数。
接下来 m 行每行包含四个整数 x1,y1,x2,y2，相邻整数之间使用一个空格分隔，表示将在 x1 至 x2 行和 y1 至 y2 列中的棋子
颜色取反。
输出格式
输出 n 行，每行 n 个 0 或 1 表示该位置棋子的颜色。
如果是白色则输出 0，否则输出 1。
数据范围
对于 30% 的评测用例，1≤n,m≤500；
对于所有评测用例，1≤n,m≤2000，1≤x1≤x2≤n，1≤y1≤y2≤n。
输入样例：
3 3
1 1 2 2
2 2 3 3
1 1 3 3
输出样例：
001
010
100
示例代码：
#include <cstdio>
#include <iostream>
using namespace std;
const int N = 2010;
int n, m;
int g[N][N];
void insert(int x1, int y1, int x2, int y2)
{
g[x1][y1] += 1;
g[x2+1][y1] -= 1;
g[x1][y2+1] -= 1;
g[x2+1][y2+1] += 1;
}
int main()
{
scanf("%d%d", &n, &m);
while(m--)
{
int x1,x2,y1,y2;
scanf("%d%d%d%d", &x1, &y1, &x2, &y2);
insert(x1,y1,x2,y2);
}
for(int i = 1; i <= n; ++i)
{
for(int j = 1; j <= n; ++j)
{
g[i][j] = g[i-1][j] + g[i][j-1] - g[i-1][j-1] + g[i][j];
if(g[i][j] % 2 == 1) printf("1");
else printf("0");
}
puts("");
}
return 0;
}
三、翻转
标签：思维题
思路：也不知道为什么是思维题，感觉挺简单的。就是变肯定两边不能变，然后就是依次从左往右枚举就行了。
题目描述：
小蓝用黑白棋的 n 个棋子排成了一行，他在脑海里想象出了一个长度为 n 的 01 串 T，他发现如果把黑棋当做 1
，白棋
当做 0，这一行棋子也是一个长度为 n 的 01 串 S。
小蓝决定，如果在 S 中发现一个棋子和它两边的棋子都不一样，就可以将其翻转变成另一个颜色。
也就是说，如果 S 中存在子串 101 或者 010，就可以选择将其分别变为 111 和 000，这样的操作可以无限重复。
小蓝想知道最少翻转多少次可以把 S 变成和 T 一模一样。
输入格式
输入包含多组数据。
输入的第一行包含一个正整数 D 表示数据组数。
后面 2D 行每行包含一个 01 串，每两行为一组数据，第 2i−1 行为第 i 组数据的 Ti，第 2i 行为第 i 组数据的
Si，Si 和 Ti 长度均为 ni。
输出格式
对于每组数据，输出一行包含一个整数，表示答案，如果答案不存在请输出 −1。
数据范围
对于 20% 的评测用例，1≤∑1Dni≤10；
对于所有评测用例，保证 1≤∑1Dni≤106，ni>0。
输入样例：
2
1000111
1010101
01000
11000
输出样例：
2
-1
示例代码：
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e6+10;
int q;
char a[N], b[N];
int main()
{
scanf("%d", &q);
while(q--)
{
scanf("%s%s", b, a);
int n = strlen(a);
int res = 0;
//cout << a[0] << " " << b[0] << " " << a[n-1] << " " << b[n-1] << endl;
if(a[0] != b[0] || a[n-1] != b[n-1])
{
printf("-1\n");
continue;
}
for(int i = 1; i < n - 1; ++i)
{
if(a[i] != b[i])
{
if(a[i-1] == a[i+1] && a[i-1] != a[i])
{
a[i] = b[i];
res++;
}
else
{
res = -1;
break;
}
}
}
printf("%d\n", res);
}
return 0;
}
总结
今天写了三道题分别是状态机DP、差分、思维题，有一说一这个状态机DP就是不好写，尤其遇到这种时间复杂度特别高的题目，一般都用dp或者贪心来做，本来以为是高精度问题，还专门把高精度加法、减法、比较写了一下，再一读题不是这样的，这种题没啥办法，只有多练才会。差分写这道题时，顺便把一维和二维和模板题做了，虽然会做，但是时间久了确实就忘了，就不会了，想起来了就有思路了，瞬间就会了。思维题还是经验一般都是从前往后遍历，前面的确定了后面的方案就是唯一的。
