- 1Zookeeper（七）Zokeeper 系统模型
- 2windows11安全中心打不开怎么办 win11无法启动安全中心服务_win11安全中心无法打开
- 3【MySQL】sql语句知识点_mysql查询用户
- 4MyBatis 如何通过拦截器修改 SQL
- 5【人工智能革命】：AIGC时代的到来 | 探索AI生成内容的未来_aigc源于人工智能技术的进步,特别是自然语言处理(nlp)、计算机视觉(cv)、语音
- 6Redis的特点&持久化的原理及优缺点_redis的优点和原理
- 7JavaFX+Jfoenix 学习笔记（序）--引言And软件截图
- 8Android Studio开发之路（十）app中使用aar以及报错记录_error inflating class androidx.camera.view.preview
- 9Go 如何通过 Kafka 客户端库 生产与消费消息_go kafka 消费
- 10搭建基于 ChatGPT 的问答系统第五章-思维链推理
【牛客】2024暑期牛客多校2 补题记录_牛客多校2024第2场
赞
踩
A - Floor Tiles（构造）
- 首先要能确定四条边上的曲线数量是固定的，因为在边上的每一个方格都会贡献一个“线头”，这种曲线不可能在中间形成圆，所以必定会从另一条边出去，因此边缘的贡献为 2 × n + 2 × m 2 \frac{2\times n+2\times m}{2} 22×n+2×m 即 m + n m+n m+n
- 其余的贡献必然是中间形成的闭合曲线提供的，那么中间的闭合曲线最多能有多少贡献呢？想让贡献最多，闭合曲线就尽可能小，所以形如：
A B B A AB\\ BA ABBA
这样的圆是最好的 - 中间贡献出圆的数量怎么计算呢？我们注意到，左上角是
A
A
A 和左上角是
B
B
B 实际上是不一样的，左上角是
A
A
A 时类似下面这张图：
粉色那一排的圆形个数是 n 2 × m 2 \frac{n}{2}\times \frac{m}{2} 2n×2m，蓝色那一排的圆形个数是 n − 1 2 × m − 1 2 \frac{n-1}{2}\times \frac{m-1}{2} 2n−1×2m−1 ，二者相加即可，左上角是 B B B 时同理，这里不再详细解释 - 到现在我们就知道了可以构造出曲线的最大值和最小值，如果 k k k 处于二者中间，那就可以构造出来，否则直接输出 “No”
- 怎么构造呢？先按最多的情况也就是相邻两个放不同种类砖块的情况来构造，最后多了多少个，就毁掉多少个圆，毁掉一个圆只需要毁掉一个角就可以了
- 需要注意的是，不能毁掉题目给定位置的圆
（代码写的很烂。。。）
#include <bits/stdc++.h> using namespace std; #define int long long using i64 = long long; typedef pair<int, int> PII; typedef pair<int, char> PIC; typedef pair<double, double> PDD; typedef pair<int, PII> PIII; typedef pair<int, pair<int, bool>> PIIB; const int N = 1e6 + 10; const int maxn = 1e6 + 10; const int mod = 1e9 + 7; const int mod1 = 954169327; const int mod2 = 906097321; const int INF = 0x3f3f3f3f3f3f3f3f; void solve() { int n, m, k; cin >> n >> m >> k; int x, y; char tt, type; cin >> x >> y >> tt; if ((x + y) & 1) { if (tt == 'A') type = 'B'; else type = 'A'; } else type = tt; int minn = n + m; int maxx = n + m; if (type == 'A') maxx += ((n - 1) * (m - 1) + 1) / 2; else maxx += (n - 1) * (m - 1) / 2; if (k < minn || k > maxx) { cout << "No" << '\n'; return; } cout << "Yes\n"; vector<vector<char>> g(n + 1, vector<char>(m + 1)); if (type == 'A') { for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { if ((i + j) & 1) g[i][j] = 'B'; else g[i][j] = 'A'; } } // b换a if (tt == 'A') { for (int i = 1; i <= n; i ++ ) { int start = 2; if (i % 2 == 0) start = 3; for (int j = start; j <= m; j += 2) { if (maxx != k) { g[i][j] = 'A'; maxx -- ; } } } } else // a换b { for (int i = 1; i <= n; i ++ ) { int start = 1; if (i % 2 == 0) start = 2; for (int j = start; j < m; j += 2) { if (maxx != k) { g[i][j] = 'B'; maxx -- ; } } } } } else { for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { if ((i + j) & 1) g[i][j] = 'A'; else g[i][j] = 'B'; } } // b换a if (tt == 'A') { for (int i = 1; i <= n; i ++ ) { int start = 3; if (i % 2 == 0) start = 2; for (int j = start; j <= m; j += 2) { if (maxx != k) { g[i][j] = 'A'; maxx -- ; } } } } else // a换b { for (int i = 1; i <= n; i ++ ) { int start = 1; if (i % 2 == 1) start = 2; for (int j = start; j < m; j += 2) { if (maxx != k) { g[i][j] = 'B'; maxx -- ; } } } } } for (int i = 1; i <= n; i ++ ) { for (int j = 1; j <= m; j ++ ) { cout << g[i][j]; } cout << '\n'; } } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } }
- 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
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
- 131
- 132
- 133
- 134
- 135
- 136
- 137
- 138
- 139
- 140
- 141
- 142
- 143
- 144
- 145
- 146
- 147
- 148
- 149
- 150
- 151
- 152
- 153
- 154
B - MST（最小生成树）
- 数据真的很抽象，std居然是暴力跑过的。。。
- 根号分治，点少的时候双层循环枚举两个点之间的边，点多的时候枚举所有边，判断两个端点是否都在点集里
#include <bits/stdc++.h> using namespace std; #define int long long using i64 = long long; typedef pair<int, int> PII; typedef pair<int, char> PIC; typedef pair<double, double> PDD; typedef pair<int, PII> PIII; typedef pair<int, pair<int, bool>> PIIB; const int N = 1e5 + 10; const int maxn = 1e6 + 10; const int mod = 1e9 + 7; const int mod1 = 954169327; const int mod2 = 906097321; const int INF = 0x3f3f3f3f3f3f3f3f; int p[N]; bool st[N]; map<int, int> mp[N]; PIII edge[N]; void solve() { int n, m, q; cin >> n >> m >> q; for (int i = 0; i < m; i ++ ) { int a, b, c; cin >> a >> b >> c; if (a > b) swap(a, b); edge[i] = {c, {a, b}}; } sort(edge, edge + m); for (int i = 0; i < m; i ++ ) { int u = edge[i].second.first, v = edge[i].second.second; int w = edge[i].first; if (!mp[u].count(v)) mp[u][v] = i; } while (q -- ) { int k; cin >> k; vector<int> s(k); function<int(int)> find = [&](int x) { if (p[x] != x) p[x] = find(p[x]); return p[x]; }; for (int i = 0; i < k; i ++ ) { cin >> s[i]; p[s[i]] = s[i]; } sort(s.begin(), s.end()); int ans = 0; int cnt = 0; auto work1 = [&]() { vector<PIII> e; for (int i = 0; i < k; i ++ ) { int a = s[i]; for (int j = i + 1; j < k; j ++ ) { int b = s[j]; if (mp[a].count(b)) { int tmp = mp[a][b]; e.push_back({edge[tmp].first, {a, b}}); } } } sort(e.begin(), e.end()); for (auto t : e) { int a = t.second.first, b = t.second.second; int pa = find(a), pb = find(b); if (pa != pb) { p[pa] = pb; ans += t.first; cnt ++ ; } } }; auto work2 = [&]() { for (int i = 0; i < k; i ++ ) st[s[i]] = true; for (int i = 0; i < m; i ++ ) { int a = edge[i].second.first, b = edge[i].second.second; if (st[a] && st[b]) { int pa = find(a), pb = find(b); if (pa != pb) { ans += edge[i].first; p[pa] = pb; cnt ++ ; } } } for (int i = 0; i < k; i ++ ) st[s[i]] = false; }; if (k < 300) work1(); else work2(); if (cnt == k - 1) cout << ans << '\n'; else cout << -1 << '\n'; } } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } }
- 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
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
- 119
- 120
- 121
- 122
- 123
- 124
- 125
- 126
- 127
- 128
- 129
- 130
C - Red Walking on Grid（dp / 贪心）
dp[0/1]表示走到第 0 行和第 1 行当前的最大路径长度- 如果当前位置第 0 行为
R，就将dp[0] ++，第 1 行同理 - 如果第 0 行和第 1 行都为
R，dp[0] = max(dp[0], dp[1] + 1)dp[1] = max(dp[1], dp[0] + 1) - 每次更新
ans
#include <bits/stdc++.h> using namespace std; #define int long long using i64 = long long; typedef pair<int, int> PII; typedef pair<int, char> PIC; typedef pair<double, double> PDD; typedef pair<int, PII> PIII; typedef pair<int, pair<int, bool>> PIIB; const int N = 1e6 + 10; const int maxn = 1e6 + 10; const int mod = 1e9 + 7; const int mod1 = 954169327; const int mod2 = 906097321; const int INF = 0x3f3f3f3f3f3f3f3f; void solve() { int n; cin >> n; vector<string> s(2); cin >> s[0] >> s[1]; s[0] = " " + s[0], s[1] = " " + s[1]; vector<int> dp(2); int ans = 0; for (int i = 1; i <= n; i ++ ) { if (s[0][i] == 'R') dp[0] ++ ; else dp[0] = 0; if (s[1][i] == 'R') dp[1] ++ ; else dp[1] = 0; if (s[1][i] == 'R' && s[0][i] == 'R') { int tmp0 = dp[0], tmp1 = dp[1]; dp[0] = max(tmp0, tmp1 + 1); dp[1] = max(tmp1, tmp0 + 1); } ans = max({ans, dp[0], dp[1]}); } cout << max(ans - 1, 0ll) << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } }
- 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
E - GCD VS XOR（签到）
- 输出 x − l o w b i t ( x ) x-lowbit(x) x−lowbit(x)
- x x x 为 2 2 2 的整数次幂无解
#include <bits/stdc++.h> using namespace std; #define int long long using i64 = long long; typedef pair<int, int> PII; typedef pair<int, char> PIC; typedef pair<double, double> PDD; typedef pair<int, PII> PIII; typedef pair<int, pair<int, bool>> PIIB; const int N = 1e6 + 10; const int maxn = 1e6 + 10; const int mod = 1e9 + 7; const int mod1 = 954169327; const int mod2 = 906097321; const int INF = 0x3f3f3f3f3f3f3f3f; void solve() { int y; cin >> y; auto lowbit = [&](int x) { return x & -x; }; int ans = y - lowbit(y); if (ans == 0) cout << -1 << '\n'; else cout << ans << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t = 1; cin >> t; while (t--) { solve(); } }
- 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
H - Instructions Substring（前缀和）
- 对于每一步，我们都能确定从第一步执行到这一步所到达的坐标
- 枚举以每一步为开头的时候，第一次到达指定点的操作下标，这个下标之后的操作都符合要求
直接糊队友的码了
#include<cstdio> #include<map> std::map<std::pair<int,int>,std::map<int,bool> > hs; std::pair<int,int> co[1000005]; int main() { int n,x,y; long long ans=0; scanf("%d%d%d",&n,&x,&y); if(x==0&&y==0) { printf("%lld",1ll*n*(n+1)/2); return 0; } co[0]={0,0}; for(int i=1;i<=n;i++) { char c; do{scanf("%c",&c); }while(c!='A'&&c!='D'&&c!='W'&&c!='S'); co[i]=co[i-1]; if(c=='A') co[i].first--; if(c=='D') co[i].first++; if(c=='W') co[i].second++; if(c=='S') co[i].second--; if(!hs.count(co[i])) hs[co[i]]=std::map<int,bool>{}; hs[co[i]][i]=1; } for(int i=0;i<n;i++) { int X=co[i].first+x,Y=co[i].second+y; if(!hs.count({X,Y})) continue; auto id=hs[{X,Y}].lower_bound(i); if(id!=hs[{X,Y}].end()) { ans+=n-id->first+1; } } printf("%lld",ans); 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
I - Red Playing Cards（区间dp）
-
一个特殊的区间dp，可以作为trick积累一下
-
用 l i l_i li 和 r i r_i ri 表示两个 i i i 的坐标， d p [ i ] dp[i] dp[i] 表示 [ l i , r i ] [l_i,\ r_i] [li, ri] 这一段合并的最大贡献，很容易想到这一段贡献是可以由区间内的贡献更新的，所以我们先计算长度小的区间再计算长度大的区间
-
对于每一个区间 [ l i , r i ] [l_i,\ r_i] [li, ri]，可以先将区间内每个元素的贡献看做 i i i，再看有没有在这一步之前合并过的小区间， g [ k ] g[k] g[k] 表示 [ l r , k ] [l_r,\ k] [lr, k] 的区间贡献，有这样两种更新方式：
- 如果 a [ k ] a[k] a[k] 在数组中第二次出现，且第一次出现的位置 p o s > = l r pos>=l_r pos>=lr，有 g [ k ] = max ( g [ k − 1 ] + i , g ( p o s − 1 ) + d p [ a [ k ] ] ) g[k] = \max(g[k-1]+i,\ g(pos-1)+dp[a[k]]) g[k]=max(g[k−1]+i, g(pos−1)+dp[a[k]])
- 否则 g [ k ] = g [ k − 1 ] + i g[k]=g[k-1]+i g[k]=g[k−1]+i
-
d p [ i ] = g [ r i ] dp[i]=g[r_i] dp[i]=g[ri]，为了方便统计答案，可以将数组两段填 0 0 0 ，最终答案就是 d p [ 0 ] dp[0] dp[0]
#include <bits/stdc++.h> using namespace std; #define int long long using i64 = long long; typedef pair<int, int> PII; typedef pair<int, char> PIC; typedef pair<double, double> PDD; typedef pair<int, PII> PIII; typedef pair<int, pair<int, bool>> PIIB; const int N = 1e6 + 10; const int maxn = 1e6 + 10; const int mod = 1e9 + 7; const int mod1 = 954169327; const int mod2 = 906097321; const int INF = 0x3f3f3f3f3f3f3f3f; void solve() { int n; cin >> n; vector<int> a(n * 2 + 2); vector<PII> pos(n + 1, {-1, -1}); vector<PII> len(n + 1); a[0] = 0, a[n * 2 + 1] = 0; for (int i = 1; i <= n * 2; i ++ ) { cin >> a[i]; if (pos[a[i]].first == -1) pos[a[i]].first = i; else { pos[a[i]].second = i; len[a[i]] = {pos[a[i]].second - pos[a[i]].first + 1, a[i]}; } } len[0] = {n * 2 + 2, 0}; pos[0] = {0, n * 2 + 1}; sort(len.begin(), len.end()); vector<int> dp(n + 1); for (int i = 0; i <= n; i ++ ) { int v = len[i].second; int l = pos[v].first, r = pos[v].second; vector<int> g(n * 2 + 2); for (int j = l; j <= r; j ++ ) { int init = a[j]; if (j >= 1) g[j] = g[j - 1] + v; else g[j] = 0; if (pos[init].second == j && pos[init].first >= l && pos[init].first >= 1) { g[j] = max(g[j], g[pos[init].first - 1] + dp[init]); } } dp[v] = g[r]; } cout << dp[0] << '\n'; } signed main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int t = 1; // cin >> t; while (t--) { solve(); } }
- 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
