这个文章只记录一些比赛场上感觉有收获的题目(全是收获)🥸
目前赛时题目补完了,9月份之前补完所有题目 + 寒假多校 + HDU春季联赛的一些题目.
牛客多校第一场
I题
这个题目是一个区间DP,写了一会的递归形式想把这个题目的一些基础思想理解,但是写完以后发现题目看错了😭
整体思路:
-
记录每一个区间的每一种可能的{价值, b}
-
然后使用二分查找 子区间小于 b 的最小价值,只要求最接近的b的位置的信息(信息用前缀求最小来处理)
条件一:
条件二:
AND
总体思路:
就是一个大区间的价值是子区间中满足条件二的最小价值,所以针对于 满足条件二,我们就可以使用 前缀和的操作,将小于条件二的最小价值存储在 大的 b 的元素(优化关键)
感觉:
区间DP像一种感觉,你仔细去思考其中的流程反而容易将自己绕晕,就是要深刻理解DP的灵魂,就是我目前的状态只跟我前面一个状态有关其实这个题目也好理解,因为 b要求递增,但是b其实就跟目前的切割点有关,所以我只要看b和子区间的b的关系就行了,b并没有顺推关系
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
| void slove(){
int n;
cin >> n;
vector<int> a(n + 1),sum(n + 1, 0);
for(int i = 1; i <= n; i++) cin >> a[i],sum[i] = sum[i - 1] + a[i];
vector dp(n + 1, vector(n + 1, vector<PII>()));
for(int i = 1; i <= n; i++) dp[i][i].push_back({0ll,0ll});
auto get = [&](int x, vector<PII>& t) -> int{
int l = 0, r = t.size() - 1, mid, ans = -1;
while(l <= r){
mid = (l + r) >> 1;
if(t[mid].sc <= x){
l = mid + 1;
ans = t[mid].fr;
}else r = mid - 1;
}
return ans;
};
for(int len = 2; len <= n; len++){
for(int l = 1, r = l + len - 1; r <= n; l++,r++){
for(int k = l; k < r; k++){
int l1 = sum[k] - sum[l - 1], l2 = sum[r] - sum[k];
int b = abs(l1 - l2), cost = (min(l1, l2) * ceil(log2(l1 + l2)));
int c_l1 = get(b, dp[l][k]), c_l2 = get(b, dp[k + 1][r]);
if(len == n){
if(c_l1 == -1 || c_l2 == -1){
cout << -1 << " ";
}else cout << c_l1 + c_l2 + cost << " ";
continue;
}
if(c_l1 == -1 || c_l2 == -1) continue;
dp[l][r].push_back({c_l1 + cost + c_l2, b});
}
sort(dp[l][r].begin(), dp[l][r].end(), [&](PII p1, PII p2){
if(p1.sc == p2.sc) return p1.fr < p2.fr;
else return p1.sc < p2.sc;
});
for(int i = 1; i < dp[l][r].size(); i++){
dp[l][r][i].fr = min(dp[l][r][i].fr, dp[l][r][i - 1].fr);
}
}
}
cout << "\n";
}
|
牛客多校第二场
A题
这个题目相对比较基础,但是我比赛场上没有写出来,针对于 DP线形动态规划的问题还是不太敏感(其实比赛的时候想过 DP,但是没有把转移方程写出来,比较遗憾[主要是包子丸写的太快了,导致我方程都没写明白,😈])
题解思路:
-
针对于这个题目,自然而然的会想到 递归,然后又是针对于一个数据的线性访问,所以我们可以不由自主的想到 DP(动态规划)
-
状态转移方程的问题: 我一开始是想将 0,1都进行合并然后再去观察这个题目
G[i][j] 就表示 前i 个数字 中 以 j 结尾的 1的段的数量
f[i - 1][0]其实就是为了统计 k 的影响的,可以理解为k构造了多少个新的子序列
以下是代码:
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;
const int mod = 998244353;
void slove(){
int n;
cin >> n;
int last = -1;
vector<int> a;
int t;
for(int i = 0; i < n; i++){
cin >> t;
if(t != last || t == -1){
a.push_back(t);
last = t;
}
}
n = a.size();
vector<array<int,2>> f(n + 1,{0,0});
vector<array<int,2>> g(n + 1,{0,0});
f[0][0] = 1;
for(int i = 1; i <= n; i++){
if(a[i - 1] == 1){
g[i][1] = ((g[i - 1][0] + f[i - 1][0]) % mod + g[i - 1][1]) % mod;
f[i][1] = (f[i - 1][0] + f[i - 1][1]) % mod;
}else if(a[i - 1] == 0){
g[i][0] = (g[i - 1][0] + g[i - 1][1]) % mod;
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
}else{
g[i][1] = ((g[i - 1][0] + f[i - 1][0]) % mod + g[i - 1][1]) % mod;
f[i][1] = (f[i - 1][0] + f[i - 1][1]) % mod;
g[i][0] = (g[i - 1][0] + g[i - 1][1]) % mod;
f[i][0] = (f[i - 1][0] + f[i - 1][1]) % mod;
}
}
cout << (g[n][0] + g[n][1]) % mod << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
slove();
}
return 0;
}
|
牛客多校第三场
B
题目介绍: 有四种操作,通过不超过 64次操作,使a, b, c相等
思路: 其实操作都是固定的,我可以先将 a 变成 c,然后在这个过程中 b先变成0,然后 b^a == c
但是这个思路还是很巧妙的.从中也有一个特殊性质: if(a != b) 则 a ^ 1 == b,这个性质也是解答这个题目的关键
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;
void slove(){
int a, b, c;
cin >> a >> b >> c;
if(a == b && b == c && c == a){
cout << "0" << "\n";
cout << '\n';
return;
}
if(a == 0 && b == 0 && c != 0){
cout << "-1" << '\n';
return;
}
int ans = 0;
vector<int> falg;
int ha, hb, hc;
auto get = [&](int x) -> int{
int i;
for(i = 31; i >= 0; i--){
if((x >> i) & 1 == 1){
break;
}
}
return i;
};
ha = get(a), hb = get(b), hc = get(c);
if(ha > hb){
falg.push_back(4);
b = b ^ a;
}else if(ha < hb){
falg.push_back(3);
a = a ^ b;
}
ha = max(ha, hb);
if(ha < hc){
for(int i = 0; i <= ha; i++){
int t1 = (a >> (ha - i)) & 1;
int t2 = (c >> (hc - i)) & 1;
if(t1 != t2){
falg.push_back(3);
a ^= b;
}
if(i < ha){falg.push_back(2); b >>= 1;}
}
for(int i = hc - ha - 1; i >= 0; i--){
a <<= 1; falg.push_back(1);
if(((c >> i) & 1) == 1) {
falg.push_back(3);
a ^= b;
}
}
b >>= 1; b ^= a;
falg.push_back(2); falg.push_back(4);
}else{
for(int i = ha; i >= 0; i--){
int t1 = (a >> i) & 1;
int t2 = (c >> i) & 1;
if(t1 != t2){
falg.push_back(3);
a ^= b;
}
b >>= 1;
falg.push_back(2);
}
b ^= a;
falg.push_back(4);
}
cout << falg.size()<< endl;
for(auto x : falg) cout << x << " ";
cout << endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
slove();
}
return 0;
}
|
牛客多校第九场
F
题目介绍: 给定一个长度为1的棒子,通过固定一个点选择90度,最少旋转多少次,能旋转到目标棒子的状态的最少次数
思路: 这道题目首先会想到就是暴力模拟,但是其实因为你是固定一个点去移动的话,两个点的状态很难考虑,我们可以尝试去思考一下,两个都是变化的状态能不能转变成就一个变化状态呢…我的想法就是因为你移动的时候,其实可以理解成棒子的中间坐标也是在移动的,而且这个移动是不需要看棒子固定哪一个点进行移动,目标的状态也只有一个,因为中间坐标其实就决定了棒子的状态,所以我们可以用中间坐标去替代棒子目前的状态
收获: 这道题给我的感觉就是其实思路是比较简单的,但是越是简单的思路就要考察你解决问题的速度,但是其实简单的思路中可能就隐藏了一些快速的解决方案…
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
| #include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define endl '\n'
using PII = pair<int,int>;
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while(t--){
array<int,2> l, r, tl, tr;
cin >> l[0] >> l[1] >> r[0] >> r[1] >> tl[0] >> tl[1] >> tr[0] >> tr[1];
array<double,2> d, dt;
d[0] = (double)(l[0] + r[0]) / 2; d[1] = (double)(l[1] + r[1]) / 2;
dt[0] = (double)(tl[0] + tr[0]) / 2; dt[1] = (double)(tl[1] + tr[1]) / 2;
int ans = max(abs(d[0] - dt[0]), abs(d[1] - dt[1])) * 2;
cout << ans << endl;
}
return 0;
}
|