牛客小白月赛52 A-E 题解

比赛链接：(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;
}