[牛客小白月赛51]A - E 题解

比赛链接：(8条未读通知) 牛客小白月赛51_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ (nowcoder.com)

快要期末考试了，就不搞头脑风暴了，来写几道简单题保持一下手感哈，暑假还要集训。

A.选择题

一个奇数加一个偶数，一定是一个奇数，所以如果N是奇数，那么答案就是N-2，如果N是偶数，答案就是N-1。

总之就是，答案是小于N的最大奇数。

代码 / Code

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main()
{
	int N;scanf("%lld", &N);
	printf("%lld\n", (N & 1) ? N - 2 : N - 1);
	return 0;
}

B.填空题

其实是个简单构造+贪心，要使得和最小且数组严格单增，那么每个空a[i] = a[i - 1] + 1，最后如果出现了单调不增的部分，说明不存在解。

代码 / Code

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e5 + 9;
int a[maxn];

signed main()
{
	int N;scanf("%lld", &N);
	for(int i = 1;i <= N; ++ i)scanf("%lld", a + i);
	int ans = 0;
	for(int i = 1;i <= N; ++ i)
	{
		if(a[i] == 0)a[i] = a[i - 1] + 1;
		if(a[i] > a[i - 1])ans += a[i];
		else
		{
			ans = -1;
			break;
		}
	}
	printf("%lld\n", ans);
	return 0;
}

C.零一题

将最终串分两种情况讨论，一种是01依次排列，一种是10依次排列。

只有当按照10 / 01 排列后剩下的0和1都是非负偶数才可能构造出答案。

答案的构造就很简单了，连续的0，连续的1和01 / 10的排列即可。

注意要判断a-c0>=0&&b-c1>=0，因为负数也可能是偶数。当然你一开始就特判x > a + b也可以。

代码 / Code

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define int long long
using namespace std;

void solve(int a,int b,int x)
{
	//方法1： 01依次排列作为最终结果
	{
		int c0 = x / 2, c1 = x / 2;
		if(x & 1)c0 ++;
		if(a - c0 >= 0 && b - c1 >= 0 && (a - c0) % 2 == 0 && (b - c1) % 2 == 0)
		{
			for(int i = 1;i <= a - c0; ++ i)printf("0");
			for(int i = 1;i <= b - c1; ++ i)printf("1");
			for(int i = 1;i <= x; ++ i)printf("%lld", (i & 1) ? 0 : 1);
			return;
		}
	}
	//方法2： 10依次排列作为最终结果
	{
		int c0 = x / 2, c1 = x / 2;
		if(x & 1)c1 ++;
		if(a - c0 >= 0 && b - c1 >= 0 && (a - c0) % 2 == 0 && (b - c1) % 2 == 0)
		{
			for(int i = 1;i <= a - c0; ++ i)printf("0");
			for(int i = 1;i <= b - c1; ++ i)printf("1");
			for(int i = 1;i <= x; ++ i)printf("%lld", (i & 1) ? 1 : 0);
			return;
		}
	}
	return printf("-1\n"), void();
}

signed main()
{
	int a, b, x;cin >> a >> b >> x;
	solve(a, b, x);
	return 0;
}

D.操作题

本来直观想这题可能是dfs，看一眼数据范围，太大了。

有个小技巧，做题往往从数据小的变量入手，这里的x比较小，然后看见0和1，乘x，不难想到将n用x进制表示，那么就可以用接近logN的步数从0变化到n。

方法就是将n用x进制表示存入一个数组，然后从后往前遍历数组，因为我们的数组中存放是从低位到高位的，而构造数字n要从高位往低位构造。

比如10的3进制是1010，在数组a中存放的是0101，那么我们构造时应该先遍历到1，发现要加1，就给a加上b，然后再乘x，遍历到0，不动，乘x，再到1，加上1次b 乘x......

代码 / Code

//Copyright (C) Eriktse 2022
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 30;

int a[100];

void solve()
{
	int n, x;scanf("%lld %lld", &n, &x);

	int k = 0, ans = 0;
	while(n)a[++ k] = n % x, n /= x, ans += a[k] + 1;
	printf("%lld\n",ans);
	
	for(int i = k;i >= 1; -- i)
	{
		printf("2 a\n");
		for(int j = 1;j <= a[i]; ++ j)printf("1 a\n");
	}
	
}

signed main()
{
	int _;scanf("%lld", &_);
	while(_ --)solve();
	return 0;
}

E.语法题

这题说实话有点小骚。

这么多条件语句中，至多执行一句，有可能一个条件都不符合就不执行。不执行也就是说n还是原来的n没变，那么方案数就是1，这个需要特判(n > max_num)。

我们将最初的n记作k。

假如程序可以执行到第i条判断语句，那么也就是说k要大于等于语句1 ~ i - 1的 a 的最大值。同时为了执行第i条，k应该要小于a[i]。

所以有了对于第i条语句有了第一个限制条件max_num <= k < a[i]。

接下来看n = k / b[i]向下取整，也就是说k >= n * b[i]，与此同时k < (n + 1) * b[i]，这样才能保证k / b[i]向下取整是n。

所以将两个限制条件取交集，得到的就是max(max_num, n * b[i]) <= k <= min(a[i] - 1, (n + 1) * b[i] - 1)。

稍加考虑就可以知道，这么多的线段是不会相交的。因为max_num >= a[i - 1] > a[i - 1] - 1。

(线段i-1)的终点一定比(线段i)的起点小。

将线段长度加起来就是答案。

代码 / Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;
const int inf = 8e18, maxn = 1e5 + 9;
int a[maxn], b[maxn];

signed main()
{
	int x, n;scanf("%lld", &x);
	
	int max_num = 1, ans = 0;
	
	for(int i = 1;i <= x; ++ i)scanf("%lld %lld", a + i, b + i);
	
	scanf("%lld", &n);

	for(int i = 1;i <= x; ++ i)
	{
		int k = n * b[i];
		int l = max(k, max_num);
		int r = min(k + b[i], a[i]);
		if(r > l)ans += r - l;
        
        max_num = max(max_num, a[i]);
	}
	printf("%lld\n", n >= max_num ? 1 : ans);
	return 0;
}