- 1Ollama_ollama导入自定义模型
- 2mysql8 插入数据报错：1292 incorrect datetime value:‘‘ for column_mysql8 incorrect datetime value
- 3sqoop命令大全和踩坑大全_sqoop 导入 sql函数单引号问题
- 4SpringBoot实现发邮箱验证码简单实现_springboot发送邮箱验证码
- 5sqoop安装及配置_第1关:sqoop的安装与配置
- 6完全二叉树的创建与堆排序代码实现_c语言二叉树堆排序
- 7数据结构——栈（详细分析）
- 8FPGA设计思想_fpga开发思维
- 9鸿蒙OS开发系列分享（1）
- 10在matlab中使用A*算法进行二维路径规划_matlab路径规划改进a*算法
Codeforces Round #742 Div.2 （A~E）题解_codeforces round #742 (div. 2) e
赞
踩
比赛链接：点击这里传送
官方题解链接：点击这里传送
Codeforces 1567A 题目链接：点击这里传送
题意：
给出n个1
×
\times
× 2大小的多米诺骨牌组成2
×
\times
×n的矩形。现输入第一行的多米诺骨牌的方向，根据上图的格式输出排列方法。
思路：
上下左右四个方向都取其对立面输出就行。
#include<bits/stdc++.h> using namespace std; int t, n; string s; string ans; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while (t--) { ans = ""; cin >> n; cin >> s; int i = 0; while (i < s.length()) { if (s[i] == 'L') { ans += 'L'; } else if (s[i] == 'R') { ans += 'R'; } else if (s[i] == 'D') { ans += 'U'; } else if (s[i] == 'U') { ans += 'D'; } i++; } cout << ans << endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
Codeforces 1567B 题目链接：点击这里传送
题意：
给出两个数a和b，要求你构造出一个数组并使其长度尽可能短，使得这个数组的最小未出现过的数字为a，数组中所有元素的异或为b。输出这个数组的长度。
思路：
先把MEX构造出来，然后求出这些数的异或和。打个表列出规律可得
- 偶数%4=0 为本身
- 偶数%4!=0 本身+1
- 奇数%4=3 0
- 奇数%4=1 1
设这个异或和为temp，当temp ⨁ \bigoplus ⨁b=b时，只需要n个数；当temp ⨁ \bigoplus ⨁a=b时，需要n+2个数，其他情况需要n+1个数。（找一x使得temp ⨁ \bigoplus ⨁x=b,x可以为除a外的任意数）
```cpp #include<bits/stdc++.h> using namespace std; int t, n, a, b; //偶数%4==0 为本身 //偶数%4!=0 本身+1 //奇数%4==3 0 //奇数%4==1 1 int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while (t--) { cin >> a >> b; //1 1 temp^x=b temp^b=x 当且仅当x=a时，不成立，需要再加一个数 n = a;//为了满足MEX a--; int temp = 0; if (a % 4 == 0) temp = a; if (a % 4 == 2) temp = a + 1; if (a % 4 == 1) temp = 1; if (a % 4 == 3) temp = 0; if (temp == b) cout << n << endl; else if ((temp^b)!=n) cout << n + 1 << endl; else cout << n + 2 << endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
Codeforces 1567C 题目链接：点击这里传送
题意：
Alice学加法的时候进位不是进大一位的，而是进大两位的。现在给出一个数，其由两个正数a和b通过Alice的加法得到，现在问a和b有几种取法。
思路：
分析题意可得，奇数位进奇数位，偶数位进偶数位。把奇数位的数字和偶数位的数分别提出来组成两个数。此时只需要找出有多少种方法组成x，有多少种方法组成y，然后将他们相乘。显而易见是(x+1)
×
\times
×(y+1)。这个答案还得减去2，因为题意要求为正数，有两种情况会使两个数中的某一个数奇偶位全为0.
例如12345这个数，奇数提出来为135，偶数提出来为24.135=90+45,24=15+9
1 9 5 0 和 4 9 5 加起来就是12345
上面看懂了0的两种特例应该也能很好理解。
#include<bits/stdc++.h> using namespace std; int t; string s; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while (t--) { cin >> s; string even; string odd; for (int i = 0; i < s.length(); i++) { if (i % 2) even += s[i]; else odd += s[i]; } long long a; if (even.size() == 0) a = 0; else a = stol(even); long long b = stol(odd); cout << (a + 1) * (b + 1) - 2 << endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
Codeforces 1567D 题目链接：点击这里传送
题意：
给出一个数，要求你将其分成n个数，然后将这n个数看做十一进制求和。求出最后这个和的最大值（十进制）
思路：
不知道这题是怎么放到D题的，应该是测试数据不够？思路也很简单，最大的数让其位数尽可能大（1开头），次大的也尽可能大。当然要保证后面的数得大于0。就这样一直到最后一个数。
#include<bits/stdc++.h> using namespace std; int t, n, m; int get_length(int x) { return to_string(x).size(); } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while (t--) { cin >> n >> m; for (int i = 1; i < m; i++) { int j = pow(10, (int)log10(n - (m - i))); n = n - j; cout << j <<" "; } cout << n << endl; } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
Codeforces 1567E 题目链接：点击这里传送
题意：
给出n个数，有两个操作。一：改变某个元素的值 二：求某个区间非递减序列的个数（单个元素也算）
思路：
线段树+区间修改。好好复习 (预习)一下这个知识点
先给出本人线段树的码风
struct segtreenode
{
int l, r,len;
long long sum, lm, rm;//连续递增区间的个数，左子树递增区间长度最大值，右子树递增区间长度最大值
}tree[MAXN<<2];
- 1
- 2
- 3
- 4
- 5
我们将某个区间分为左区间和右区间。先不考虑区间合并的情况，一个区间的递增区间个数等于左右两边加起来，一个区间左边递增区间长度最大值等于左子树的最大值，右边递增区间长度最大值等于右子树的最大值，就有了如下代码。
tree[rt].lm = tree[rt << 1].lm; tree[rt].rm = tree[rt << 1 | 1].rm;
tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum;
- 1
- 2
现在考虑区间合并的情况。如果左边一整个区间都是递增区间，那么lm就可以加上右子树的lm；如果右边一整个区间都是递增区间，那么rm就可以加上左子树的rm。sum就会中间多出来一部分。
a
+
b
+
c
+
d
+
e
+
.
.
.
+
i
,
j
,
k
,
l
∣
分
割
线
∣
m
,
o
⏟
n
+
m
+
.
.
.
+
u
+
w
+
x
+
y
+
z
⏞
\overbrace{a+b+c+d+e+...+\underbrace{i,j,k,l|分割线|m,o}_{n+m}+...+u+w+x+y+z}^{}
a+b+c+d+e+...+n+m
i,j,k,l∣分割线∣m,o+...+u+w+x+y+z
设左区间的rm为n，右区间的lm为m，多出来的总数就为m*n。
综上，完成了区间合并也就是pushup的处理
void pushup(int rt) { tree[rt].lm = tree[rt << 1].lm; tree[rt].rm = tree[rt << 1 | 1].rm; tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; if (a[tree[rt << 1].r] <= a[tree[rt << 1 | 1].l])//左右区间可以合并 { if (tree[rt << 1].lm == tree[rt << 1].len)//如果左区间都是递增区间 { tree[rt ].lm += tree[rt << 1 | 1].lm; } if (tree[rt << 1 | 1].rm == tree[rt << 1 | 1].len)//如果右区间都是递增区间 { tree[rt ].rm += tree[rt << 1].rm; } tree[rt].sum += tree[rt << 1].rm * tree[rt << 1 | 1].lm; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
由于查询时不一定是整个区间，所以查询里面重新加了一段区间合并的代码。需要注意的是区间查询不是一整个区间时，得写两行代码划好左区间rm的上限和右区间lm的上限。
long long lsum = min(tree[rt << 1].rm,mid-l+1);
long long rsum = min(tree[rt << 1 | 1].lm,(r-(mid+1)+1));
- 1
- 2
AC代码：
#include<bits/stdc++.h> using namespace std; #define MAXN 200005 int a[MAXN]; int n, m; struct segtreenode { int l, r,len; long long sum, lm, rm;//连续递增区间的个数，左子树递增区间长度最大值，右子树递增区间长度最大值 }tree[MAXN<<2]; void pushup(int rt) { tree[rt].lm = tree[rt << 1].lm; tree[rt].rm = tree[rt << 1 | 1].rm; tree[rt].sum = tree[rt << 1].sum + tree[rt << 1 | 1].sum; if (a[tree[rt << 1].r] <= a[tree[rt << 1 | 1].l])//左右区间可以合并 { if (tree[rt << 1].lm == tree[rt << 1].len)//如果左区间都是递增区间 { tree[rt ].lm += tree[rt << 1 | 1].lm; } if (tree[rt << 1 | 1].rm == tree[rt << 1 | 1].len)//如果右区间都是递增区间 { tree[rt ].rm += tree[rt << 1].rm; } tree[rt].sum += tree[rt << 1].rm * tree[rt << 1 | 1].lm; } } void build(int rt, int l, int r) { tree[rt].l = l; tree[rt].r = r; tree[rt].len = r - l + 1; if (l == r) { tree[rt].lm = 1; tree[rt].rm = 1; tree[rt].sum = 1; return; } int mid = (l + r) / 2; build(rt << 1, l, mid); build(rt << 1 | 1, mid + 1, r); pushup(rt); } void update(int rt, int k, int x)//将下标为k的值修改为x { if (tree[rt].l > k || tree[rt].r < k) return; if (tree[rt].l == tree[rt].r) { a[k] = x; return; } update(rt << 1, k, x); update(rt << 1 | 1, k, x); pushup(rt); } long long query(int rt, int l, int r) { if (tree[rt].l > r || tree[rt].r < l) return 0; if (tree[rt].l >= l && tree[rt].r <= r) return tree[rt].sum; long long ans = 0; long long mid = (tree[rt].l + tree[rt].r) / 2; if (mid >= l) ans += query(rt << 1, l, r); if (mid < r) ans += query(rt << 1 | 1, l, r); if (a[tree[rt << 1].r] <= a[tree[rt << 1 | 1].l])//如果可以合并 { long long lsum = min(tree[rt << 1].rm,mid-l+1); long long rsum = min(tree[rt << 1 | 1].lm,(r-(mid+1)+1)); if (lsum > 0 && rsum > 0) { ans += lsum * rsum; } } return ans; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++) cin >> a[i]; build(1, 1, n); int f; while (m--) { cin >> f; if (f == 1)//修改 { int k, x; cin >> k >> x; update(1, k, x); } else//查询 { int x, y; cin >> x >> y; cout << query(1, x, y)<<endl; } } return 0; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
