电子商务的网站怎么做,wordpress改地址错误,一嗨租车网站建设的功能特色,高端网站源码目录 引言一、保险箱二、棋盘三、翻转总结 引言
今天还是三道新题#xff0c;多练多想才会有出路。 一、保险箱
标签#xff1a;状态机DP
思路#xff1a;这道题看的我懵的很#xff0c;大概意思就是每一位有三种状态 f [ i ] [ 3 ] f[i][3] f[i][3] 分别为借位、啥也不… 目录 引言一、保险箱二、棋盘三、翻转总结 引言
今天还是三道新题多练多想才会有出路。 一、保险箱
标签状态机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∗ja[i]kt−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≤105x,y 中仅包含数字 0 至 9可能有前导零。输入样例
5
12349
54321
输出样例
11示例代码
#include cstdio
#include iostream
#include cmath
#include cstring
#include algorithmusing namespace std;const int N 1e510;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[i1][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≤20001≤x1≤x2≤n1≤y1≤y2≤n。输入样例
3 3
1 1 2 2
2 2 3 3
1 1 3 3
输出样例
001
010
100示例代码
#include cstdio
#include iostreamusing 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[x21][y1] - 1;g[x1][y21] - 1;g[x21][y21] 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 组数据的
SiSi 和 Ti 长度均为 ni。输出格式
对于每组数据输出一行包含一个整数表示答案如果答案不存在请输出 −1。数据范围
对于 20% 的评测用例1≤∑1Dni≤10
对于所有评测用例保证 1≤∑1Dni≤106ni0。输入样例
2
1000111
1010101
01000
11000
输出样例
2
-1示例代码
#include cstdio
#include iostream
#include cstringusing namespace std;const int N 1e610;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[i1] a[i-1] ! a[i]){a[i] b[i];res;}else {res -1;break;}}}printf(%d\n, res);}return 0;
}总结
今天写了三道题分别是状态机DP、差分、思维题有一说一这个状态机DP就是不好写尤其遇到这种时间复杂度特别高的题目一般都用dp或者贪心来做本来以为是高精度问题还专门把高精度加法、减法、比较写了一下再一读题不是这样的这种题没啥办法只有多练才会。差分写这道题时顺便把一维和二维和模板题做了虽然会做但是时间久了确实就忘了就不会了想起来了就有思路了瞬间就会了。思维题还是经验一般都是从前往后遍历前面的确定了后面的方案就是唯一的。
