比赛链接:(1条未读通知) 牛客小白月赛52_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)
由于我个人比较菜,只做出了5题,所以就写一下A-E这5题的题解吧。

A - 签到时刻
在处理时间时,常用的方法是单位标准化,也就是全部转化成分钟或者秒。
这道题应该全部转化成分钟,然后再比较一下就好了,属于签到题。
注意用scanf格式化输入会方便很多。
时间复杂度O(N)
代码
#include <bits/stdc++.h> #define int long long using namespace std; void solve() { int N;scanf("%lld", &N); int cnt1 = 0, cnt2 = 0; for(int i = 1;i <= N; ++ i) { int hh, mm;scanf("%lld:%lld", &hh, &mm); int t = hh * 60 + mm; if(t <= 480)continue; else if(t - 480 <= 5)cnt1 ++; else cnt2 ++; } printf("%lld %lld\n",cnt1, cnt2); } signed main() { int _;scanf("%lld", &_); while(_ --)solve(); return 0; }
B - 牛牛的身高
这道题就是要求一个数字最大可以四舍五入到多少,因为这里要四舍五入,其实就是找到某一位进位,后面的都变成0。
稍微贪心一下,就知道进位的位置越靠前越好,这个数字会越大,所以只需要先处理出哪些数字可以进位,然后找最大的进位就好了。
时间复杂度O(NlogN)
代码
#include <bits/stdc++.h> #define int long long using namespace std; int a[100]; bitset<100> up; bool dfs(int i) { if(i == 0)return 0; bool res = 0; if(dfs(i - 1))a[i] ++; //如果下一位能进位,那么当前这一位就要 + 1 //这里无需考虑a[i] == 10的情况,因为a[i]只要大于等于5就都会进位且变为0 if(a[i] >= 5)a[i] = 0, res = 1; return up[i] = res; } void solve() { int N;scanf("%lld", &N); int k = 0; up.reset(); //注意清零 while(N)a[++ k] = N % 10, N /= 10; bool tag = 0; //tag标记是否已经完成第一次进位 if(dfs(k))printf("1"), tag = 1; //如果第一位就要进位,那么输出1并标记 for(int i = k;i >= 1; -- i) { if(tag)printf("0"); else printf("%lld", a[i]); if(up[i])tag = 1; } puts(""); } signed main() { int _;scanf("%lld", &_); while(_ --)solve(); return 0; }
C - 说谎的机器
理解题意之后不难发现,每一个机器都对应一条线段,那么k所处的点被x条线段覆盖到就说明有x条指令是正确的,剩下的就是错的。
线段、覆盖、条数、只有一次检测,不难想到用前缀和。
先处理出一个差分数组,然后通过前缀和扫一遍,得到最终的线段覆盖数组,就能得到每个点被多少线段覆盖,最后扫描一遍求个错误指令的最大值,再扫一遍求有多少满足要求的点即可。
时间复杂度O(N)
代码
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn = 1e6 + 9; int prefix[maxn]; signed main() { int N, M;scanf("%lld %lld", &N, &M); for(int i = 1;i <= M; ++ i) { int op;scanf("%lld", &op); if(op == 1) { int x, y;scanf("%lld %lld", &x, &y); prefix[x] ++, prefix[y + 1] --; }else if(op == 2) { int x;scanf("%lld", &x); prefix[x] ++, prefix[N + 1] --; }else if(op == 3) { int x;scanf("%lld", &x); prefix[1] ++, prefix[x + 1] --; } } for(int i = 1;i <= N; ++ i)prefix[i] += prefix[i - 1]; int ans = 0, cnt = 0; for(int i = 1;i <= N; ++ i)ans = max(ans, M - prefix[i]); for(int i = 1;i <= N; ++ i)if(prefix[i] == M - ans)cnt ++; printf("%lld %lld\n", ans, cnt); return 0; }
D - 环上食虫
问题大意是在一个环上取一段区间使得区间的饱食度和大于等于S且奶油含量最大值尽可能小。
设饱食度a[i],奶油含量b[i]。
首先要注意将数组大小开两倍,并且将数组拓展一倍,这是环形题目的经典做法。
一开始以为是个滑动窗口,后面发现这个要求的是奶油含量最大值而不是奶油含量的和。所以想到要处理每一个点作为答案时,这个区间最多向左和向右拓展多少,再判断以一下这个区间的饱食度是否满足要求,再从可能是答案的点中找到最小值。
这个向左向右拓展多少意思是 i 向左走多少步依然可以保证 b[i] 是最大值,右边同理。
而处理这个状态可以通过单调栈O(1)处理出来。
在之前的题目也讲过用单调栈处理这个最值区间的,《[牛客网]小A的柱状图(单调栈)》《Largest Rectangle in a Histogram(单调栈)》。
时间复杂度O(N)
代码
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; const int maxn = 5e5 + 9, inf = 8e18; int a[maxn], b[maxn]; int l[maxn], r[maxn]; int p[maxn]; pair<int, int> stk[maxn]; int top = 0; signed main() { int N, S;scanf("%lld %lld", &N, &S); for(int i = 1;i <= N; ++ i)scanf("%lld", a + i); for(int i = 1;i <= N; ++ i)scanf("%lld", b + i); for(int i = N + 1;i <= 2 * N; ++ i)a[i] = a[i - N], b[i] = b[i - N]; for(int i = 1;i <= 2 * N; ++ i)p[i] = p[i - 1] + a[i]; if(p[N] < S)return printf("-1"), 0; for(int i = 1;i <= 2 * N; ++ i) { while(top && b[i] >= stk[top].fi)l[i] += stk[top --].se; stk[++ top] = {b[i], l[i] + 1}; } top = 0; for(int i = 2 * N;i >= 1; -- i) { while(top && b[i] >= stk[top].fi)r[i] += stk[top --].se; stk[++ top] = {b[i], r[i] + 1}; } int ans = inf; for(int i = 1;i <= 2 * N; ++ i) if(p[i + r[i]] - p[i - l[i] - 1] >= S)ans = min(ans, b[i]); printf("%lld\n", ans); return 0; }
E - 分组求对数和
这道题感觉比D简单。
从诸多数组中任意不同的数组中选两个数字,求使得两数之和>=K的方案数。相同大小、不同位置的数字看作不同方案。
对每个数组进行排序时基本操作。
一开始想用一个multiset从左往右不断延伸过去,并将遍历到的数组加到multiset中,这个multiset作为数字池。
但是multiset二分不能O(1)得到位置,还有O(N),我要你有何用?
所以可以考虑集合容斥思想,将所有数字都加到一个数组中,然后遍历每一个数组,再遍历数组中每一个数字,我们要找的是自己 - 别人的合法组数有多少,可以先找到自己 - 所有人 再减去 自己 - 自己的。
因为这里的选择是没有方向性的,所以是一个双向选择,最后要对答案除以2。
时间复杂度O(NlogN)
代码
#include <bits/stdc++.h> #define fi first #define se second #define int long long using namespace std; const int maxn = 1e6 + 9, p = 998244353; vector<int> v[maxn], all; signed main() { int N, K;scanf("%lld %lld", &N, &K); int sum = 0; for(int i = 1;i <= N; ++ i) { int cnt;scanf("%lld", &cnt); sum += cnt; while(cnt --) { int x;scanf("%lld", &x); v[i].push_back(x); all.push_back(x); } sort(v[i].begin(), v[i].end()); } sort(all.begin(), all.end()); int ans = 0; for(int i = 1;i <= N; ++ i) { for(int j = 0, sz = v[i].size();j < sz; ++ j) { int p1 = lower_bound(all.begin(), all.end(), K - v[i][j]) - all.begin(); int p2 = lower_bound(v[i].begin(), v[i].end(), K - v[i][j]) - v[i].begin(); p1 = sum - p1; p2 = v[i].size() - p2; ans = (ans + p1 - p2 + p) % p; } } printf("%lld\n" ,ans / 2); return 0; }
Comments NOTHING