当前位置：网站首页>牛客小白月赛52
牛客小白月赛52
2022-06-30 07:59:00 【晁棠】
牛客小白月赛52
Problem A
直接分类讨论判断，7点每次到，八点1分~5分迟到，其余旷课。
Problem B
模拟，按10位数的规则去试是否可以进位。注意当看到 5000 的时候可以进位变成 10000 。
Problem C
前缀和维护区间累加，最后看哪一部分累加次数最少，此时除了该指令外其他指令都是错的情况下是错误指令最多的。
Problem D
树状数组 & ST表
一个圆桌，所以要增长至2倍。由题意的值每次只能取一个圆弧（也可以是整圆），依次枚举从每个蛋糕开始吃，用二分找出在能吃饱的情况下吃到哪一个蛋糕，然后再用ST表找到这一区间内的奶油最大值。时间复杂度 O ( n log n ) O(n\log n) O(nlogn)
这种方法过了，但在写题解的时候有点疑惑为什么能过，感觉这么枚举似乎不能恰好保证奶油量最高的最低的所在的奶油组是不包括其他更高的奶油吧？好像我也表达不太清楚。
Problem E
一开始想了想平衡数，抄了一发模板然后WA了，因为没有考虑后面加入的组的元素的贡献。
题解的正解是：二分加容斥
找出需求值在所有数之中的贡献，再减去需求值在该组之中的贡献即可。
Problem F
分组背包，没做。
Code：
Problem A
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
int n, T = 1;
void ready()
{
int a = 0, b = 0;
cin >> n;
while (n--) {
string st;
cin >> st;
if (st[0] == '7') continue;
if (st[0] == '9') b++;
if (st[0] == '8') {
int t = (st[2] - '0') * 10 + st[3] - '0';
if (t <= 5 && t != 0) a++;
else if (t > 5) b++;
}
}
cout << a << ' ' << b << '\n';
}
void work()
{
}
signed main()
{
IOS;
cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
Problem B
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
int n, T = 1;
void ready()
{
cin >> n;
}
void work()
{
int t = 1, ans = n;
if (ans < 10) {
if (ans >= 5) ans = 10;
}
while (n >= t) {
t *= 10;
int b = n % t;
if (b >= 10) while (b >= 10) b = b / 10;
n = n / t * t;
if (b >= 5) n += t;
//cout << "b=" << b << '\n';
ans = max(ans, n);
//cout << "n= " <<n<< '\n';
//cout << "t=" << t << '\n'<<'\n';
}
cout << ans << '\n';
}
signed main()
{
IOS;
cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
Problem C
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
const int N = 1e6 + 6;
int n, T = 1, m;
int sum[N];
void ready()
{
cin >> n >> m;
ffor(i,1,m) {
int op, x, y;
cin >> op;
if (op == 1) {
cin >> x >> y;
sum[x]++; sum[y + 1]--;
}
if (op == 2) {
cin >> x;
sum[x]++;
}
if (op == 3) {
cin >> x;
sum[1]++; sum[x+1]--;
}
}
int ans = inf, cnt = 0;
ffor(i, 1, n) {
sum[i] += sum[i - 1];
ans = min(sum[i], ans);
}
// ffor(i, 1, n) cout << sum[i] << ' '; cout << '\n';
cout << m - ans << ' ';
ffor(i, 1, n) {
if (sum[i] == ans) {
cnt++;
// cout << "i=" << i << '\n';
}
}
cout << cnt;
}
void work()
{
}
signed main()
{
IOS;
// cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
Problem D
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
const int N = 1e6 + 5;;
int n, T = 1, s;
int b[N], d[N][22];
int lowbite(int x)
{
return x & (-x);
}
void add_in(int i, int num, int c[])
{
while (i <= n * 2)
{
c[i] += num;
i += lowbite(i);
}
return;
}
int get_sum(int x, int c[])
{
int sum = 0;
while (x)
{
sum += c[x];
x -= lowbite(x);
}
return sum;
}
void ready()
{
cin >> n >> s;
ffor(i, 1, n) {
int bi;
cin >> bi;
add_in(i, bi, b);
add_in(i + n, bi, b);
}
ffor(i, 1, n) {
int di;
cin >> di;
d[i][0] = d[n + i][0] = di;
}
ffor(j, 1, 19) {
ffor(i, 1, 2 * n) {
d[i][j] = max(d[i][j - 1], d[i + (1 << (j - 1))][j - 1]);
}
}
}
int get_max(int x, int y)
{
int mid = log2(y - x + 1);
return max(d[x][mid], d[y - (1 << mid) + 1][mid]);
}
void work()
{
if (get_sum(n, b) < s) {
cout << -1;
return;
}
int ans = inf;
for (int i = 1; i <= n; i++) {
int l = i, r = n + i - 1, mid;
while (l < r) {
mid = l + r >> 1;
if (get_sum(mid, b) - get_sum(i - 1, b) < s) l = mid + 1;
else r = mid;
}
ans = min(ans, get_max(i, l));
}
cout << ans;
}
signed main()
{
IOS;
// cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
Problem E
// Good Good Study, Day Day AC.
#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <stdlib.h>
#include <string>
#include <string.h>
#include <cstring>
#include <math.h>
#include <cmath>
#include <queue>
#include <deque>
#include <stack>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define ffor(i,a,b) for(int i=(a) ;i<=(b) ;i++)
#define rrep(i,a,b) for(int i=(a) ;i>=(b) ;i--)
#define mst(v,s) memset(v,s,sizeof(v))
#define IOS ios::sync_with_stdio(false),cin.tie(0)
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
#define inf 0x7f7f7f7f
#define PII pair<int,int>
#define int long long
using namespace std;
const int N = 1e6 + 6;
const int mod = 998244353;
int n, T = 1, k;
vector<int> ve[N], alls;
void ready()
{
cin >> n >> k;
ffor(i, 1, n) {
int s;
cin >> s;
ffor(j, 1, s) {
int x;
cin >> x;
alls.push_back(x);
ve[i].push_back(x);
}
sort(ve[i].begin(), ve[i].end());
}
sort(alls.begin(), alls.end());
}
void work()
{
int ans = 0;
ffor(i, 1, n) {
for (auto item : ve[i]) {
int x = k - item;
ans += (alls.end() - lower_bound(alls.begin(), alls.end(), x)) - (ve[i].end() - lower_bound(ve[i].begin(), ve[i].end(), x));
}
}
ans /= 2;
cout << ans % mod;
}
signed main()
{
IOS;
// cin>>T;
while (T--) {
ready();
work();
}
return 0;
}
边栏推荐
- Deep learning -- using word embedding and word embedding features
- 【花雕体验】12 搭建ESP32C3之Arduino开发环境
- Introduction notes to pytorch deep learning (10) neural network convolution layer
- At the age of 25, I started to work in the Tiankeng industry with buckets. After going through a lot of hardships to become a programmer, my spring finally came
- Deep learning - brnn and DRNN
- Deep learning - residual networks resnets
- 2021-10-29 [microbiology] a complete set of 16s/its analysis process based on qiime2 tool (Part I)
- 342 maps covering exquisite knowledge, one of which is classic and pasted on the wall
- 1162 Postfix Expression
- Palindrome substring, palindrome subsequence
猜你喜欢
At the end of June, you can start to make preparations, otherwise you won't have a share in such a profitable industry
Deep learning -- Realization of convolution by sliding window
期末複習-PHP學習筆記5-PHP數組
Cadence innovus physical implementation series (I) Lab 1 preliminary innovus
期末复习-PHP学习笔记4-PHP自定义函数
CRM能为企业带来哪些管理提升
National technology n32g45x series about timer timing cycle calculation
![January 23, 2022 [reading notes] - bioinformatics and functional genomics (Chapter 6: multiple sequence alignment)](/img/48/cfe6ab95b4d4660e3ac3d84ae5303b.jpg)
January 23, 2022 [reading notes] - bioinformatics and functional genomics (Chapter 6: multiple sequence alignment)
期末複習-PHP學習筆記3-PHP流程控制語句
Vulfocus entry target
随机推荐
期末复习-PHP学习笔记3-PHP流程控制语句
Efga design open source framework fabulous series (I) establishment of development environment
深度学习——序列模型and数学符号
Lodash filter collection using array of values
Deep learning vocabulary representation
November 21, 2021 [reading notes] - bioinformatics and functional genomics (Chapter 5 advanced database search)
November 22, 2021 [reading notes] - bioinformatics and functional genomics (Section 5 of Chapter 5 uses a comparison tool similar to blast to quickly search genomic DNA)
Introduction notes to pytorch deep learning (11) neural network pooling layer
Xiashuo think tank: 42 reports on planet update today (including 23 planning cases)
The counting tool of combinatorial mathematics -- generating function
Conversion between basic data types in go data types
Personal blog one article multi post tutorial - basic usage of openwriter management tool
深度学习——卷积的滑动窗口实现
Given a fixed point and a straight line, find the normal equation of the straight line passing through the point
right four steps of SEIF SLAM
多快好省，低门槛AI部署工具FastDeploy测试版来了!
TP5 set direct download file
Miracle Mu server rental selection is real and easy to use, stable and intrusion proof
NMOS model selection
Bingbing learning notes: quick sorting