2022年6月第十三届蓝桥杯大赛软件赛全国决赛C++A组题解

• • 试题 A: 小蓝与钥匙
  • 试题 B: 排列距离
  • 试题 C: 内存空间
  • 试题 D: 最大公约数
  • 试题 E: owo
  • 试题 F: 环境治理
  • 试题 G: 选素数
  • 试题 H: 替换字符
  • 试题 I: 三角序列
  • 试题 J: 括号序列树

C(28,14)*错排

康托展开

预计得分：100%

模拟即可

代码如下：

#include 
using namespace std;

const int N = 1e5 + 5;
const long long mod = 1e9 + 7;
string str;

void solve()
{
	int n;
	scanf("%d", &n);
	getchar();
	long long ans = 0;
	for (int i = 1; i <= n; i++)
	{
		getline(cin, str);
		string TP = "";
		int m = str.size();
		bool f = 0;
		for (int i = 0; i < m; i++)
		{
			if (!f)
			{
				TP += str[i];
				if (TP == "int" || TP == "long" || TP == "String")
					f = 1;
				continue;
			}
			if (TP == "String")
			{
				bool flag = 0;
				for (int j = i; j < m; j++)
				{
					if (!flag)
					{
						if (str[j] == '"')
							flag = 1;
						continue;
					}
					if (str[j] == '"')
					{
						flag = 0;
						continue;
					}
					ans++;
				}
				break;
			}
			if (str[i] == '[')
			{
				bool flag = 0;
				long long res;
				for (int j = i + 2; j < m; j++)
				{
					if (!flag)
					{
						if (str[j] == '[')
							flag = 1, res = 0;
						continue;
					}
					if (str[j] == ']')
					{
						flag = 0;
						ans += res * (TP == "int" ? 4 : 8);
						continue;
					}
					res = res * 10 + str[j] - '0';
				}
				break;
			}

			for (int j = i; j < m; j++)
			{
				if (str[j] == ',' || str[j] == ';')
					ans += (TP == "int" ? 4 : 8);
			}
			break;
		}
	}
	long long B = ans % 1024;
	long long KB = ans / 1024 % 1024;
	long long MB = ans / 1024 / 1024 % 1024;
	long long GB = ans / 1024 / 1024 / 1024 % 1024;
	if (GB)
		printf("%lldGB", GB);
	if (MB)
		printf("%lldMB", MB);
	if (KB)
		printf("%lldKB", KB);
	if (B)
		printf("%lldBn", B);
}
int main()
{
	solve();
	return 0;
}

预计得分：100%

如果数组中已经有 1 1 1，那么直接用 1 1 1平铺即可。

否则找出最小区间满足区间 G C D = 1 GCD=1 GCD=1，用这个 1 1 1进行平铺。

寻找方法可以使用二分+RMQ。

代码如下：

#include 
using namespace std;

const int N = 1e5 + 5;
const long long mod = 1e9 + 7;
const long long INF = 0x3f3f3f3f;
int a[N];

struct node
{
	int l, r, g;
} tr[N << 2];

void pushup(int k)
{
	tr[k].g = __gcd(tr[k * 2].g, tr[k * 2 + 1].g);
}

void build(int k, int l, int r)
{
	tr[k].l = l, tr[k].r = r;
	if (l == r)
	{
		tr[k].g = a[l];
		return;
	}
	int mid = l + r >> 1;
	build(k * 2, l, mid);
	build(k * 2 + 1, mid + 1, r);
	pushup(k);
}

int query(int k, int L, int R)
{
	if (tr[k].l == L && tr[k].r == R)
	{
		return tr[k].g;
	}
	int mid = (tr[k].l + tr[k].r) >> 1;
	if (R <= mid)
		return query(k * 2, L, R);
	else if (L > mid)
		return query(k * 2 + 1, L, R);
	else
		return __gcd(query(k * 2, L, mid), query(k * 2 + 1, mid + 1, R));
}

void solve()
{
	int n;
	scanf("%d", &n);
	int ct = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		ct += a[i] == 1;
	}
	if (ct) //有1直接平铺
	{
		printf("%dn", n - ct);
		return;
	}
	build(1, 1, n);
	if (query(1, 1, n) != 1) //肯定不行
	{
		puts("-1");
		return;
	}

	int min_step = INF;
	for (int i = 1; i <= n; i++)
	{
		int l = i + 1, r = n, res = INF;
		while (l <= r)
		{
			int mid = l + r >> 1;
			if (query(1, i, mid) == 1)
			{
				res = mid - i;
				r = mid - 1;
			}
			else
				l = mid + 1;
		}
		min_step = min(min_step, res);
	}
	printf("%dn", min_step + n - 1);
}
int main()
{
	solve();
	return 0;
}

预计得分：10%

应该是个DP，刚开始没什么思路，后面也没时间想了，交了暴力。

代码如下：

#include 
using namespace std;

const int N = 1e6 + 5;

int ans = 0;
string s[N];

int ct = 0;
int func()
{
	int r = 0;
	for (int i = 1; i <= 1e3; i++)
	{
		random_shuffle(s + 1, s + 1 + ct);
		string tmp;
		for (int i = 1; i <= ct; i++)
			tmp += s[i];
		int n = tmp.size();
		int res = 0;
		for (int i = 2; i < n; i++)
			res += tmp[i - 2] == 'o' && tmp[i - 1] == 'w' && tmp[i] == 'o';
		r = max(r, res);
	}
	return r;
}
void solve()
{
	srand(time(NULL));
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		string str;
		cin >> str;
		if (str[0] != 'o' && str[0] != 'w' && str[(int)str.size() - 1] != 'o' && str[(int)str.size() - 1] != 'w') //剪枝
		{
			printf("%dn", ans);
			continue;
		}
		else
		{
			s[++ct] = str;
			ans = func();
			printf("%dn", ans);
		}
	}
}
int main()
{
	solve();
	return 0;
}

预计得分：100%

比较简单的一个题，二分+FLOYD求最短路。时间复杂度 n 3 l o g m n^3logm n3logm，其中m为把所有路径清理到下限的所需天数（开个 1 e 8 、 1 e 9 1e8、1e9 1e8、1e9都行）。

代码如下：

#include
using namespace std;

const int N = 105;
const long long mod = 1e9+7;
const int INF= 0x3f3f3f3f;

int w[N][N];
int ww[N][N];
int minn[N][N];
int n , q;
int check(int day)
{
	int ans =0 ;
	for(int i =0; i
		int val = day/n+(day%n>=i+1?1:0);
		for(int j =0 ; j
	scanf("%d %d",&n,&q);
	for(int i =0; i
		int mid = l+r>>1;
		if(check(mid)<=q)
		{
			r= mid -1;
			ans = mid;
		}
		else
			l=mid+1;
	}
	cout<
	solve();
	return 0;
}

预计得分：30%

数学废物，没思路，交了暴力。

代码如下：

#include 
using namespace std;

const int N = 5005;
const long long mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;

bool f[N];
int prime[N];
int ct;

void init()
{
	f[0] = f[1] = 1;
	for (int i = 2; i < N; i++)
		if (!f[i])
		{
			prime[++ct] = i;
			for (int j = i + i; j < N; j += i)
				f[j] = 1;
		}
}
void solve()
{
	init();
	int n;
	cin >> n;
	for (int x = 2; x <= n; x++)
	{
		for (int p1 = 1; p1 <= ct && prime[p1] < x; p1++)
		{
			int xx = x;
			int a = prime[p1];
			if (x % a)
				xx = (xx / a + 1) * a;
			if (xx > n) //剪枝
				continue;
			for (int p2 = 1; p2 <= ct && prime[p2] < xx; p2++)
			{
				a = prime[p2];
				int xxx = xx;
				if (xx % a)
					xxx = (xx / a + 1) * a;
				if (xxx == n)
				{
					cout << x << endl;
					return;
				}
			}
		}
	}
	puts("-1");
}
int main()
{
	solve();
	return 0;
}

预计得分：40%

感觉需要神奇的数据结构来维护，并不会，交了暴力。

#include 
using namespace std;

const int N = 1e5 + 5;
const long long mod = 1e9 + 7;
const long long INF = 0x3f3f3f3f;
char s[N];
int l, r;
char a[3], b[3];

void solve()
{
	scanf("%s", s + 1);
	int n = strlen(s + 1);
	int m;
	scanf("%d", &m);
	while (m--)
	{
		scanf("%d %d %s %s", &l, &r, a, b);
		for (int i = l; i <= r; i++)
			if (s[i] == a[0])
				s[i] = b[0];
	}
	printf("%s", s + 1);
}
int main()
{
	solve();
	return 0;
}

预计得分：40%

单独维护每个三角形， 类似于分块的思想，边界单独维护一下。

时间复杂度： n m l o g n l o g n nmlognlogn nmlognlogn

代码如下：

#include 
using namespace std;

const int N = 2e5 + 5;
const long long mod = 1e9 + 7;
const long long INF = 0x3f3f3f3f;

struct tri
{
	int typ, len, l, r;
} a[N];
long long pre[N]; //前缀列数量之和
int n, m;
long long cal2(int len, int h) //计算边长为len的三角形 高度<=h的贡献
{
	long long sum = 1ll * len * (len + 1) / 2;
	long long len2 = max(0, len - h);
	long long res = 1ll * len2 * (len2 + 1) / 2;
	return sum - res;
}
long long cal(int col, int idx, int h) //计算 第idx个三角形，从第col列开始， 高度<=h的贡献
{
	if (col > a[idx].r)
		return 0;
	if (a[idx].typ == 0)
	{
		long long s1 = cal2(a[idx].len, h);
		long long len2 = col - a[idx].l;
		long long s2 = cal2(len2, h);
		return s1 - s2;
	}
	else
	{
		long long len2 = a[idx].r - col + 1;
		return cal2(len2, h);
	}
}
int check(int l, int r, int h)
{
	int left_idx = lower_bound(pre + 1, pre + 1 + n, l) - pre;
	int right_idx = lower_bound(pre + 1, pre + 1 + n, r) - pre;
	if (left_idx == right_idx) //只有一个三角形
		return cal(l, left_idx, h) - cal(r + 1, left_idx, h);
	else
	{
		long long ans = 0;
		ans += cal(l, left_idx, h);
		ans += cal(a[right_idx].l, right_idx, h) - cal(r + 1, right_idx, h);
		for (int i = left_idx + 1; i < right_idx; i++) //计算中间的三角形贡献
			ans += cal(a[i].l, i, h);
		return ans;
	}
}

void solve()
{

	scanf("%d %d", &n, &m);
	int max_h = 0;
	for (int i = 1; i <= n; i++)
	{
		scanf("%d %d", &a[i].len, &a[i].typ);
		pre[i] = pre[i - 1] + a[i].len;
		a[i].l = pre[i - 1] + 1;
		a[i].r = pre[i];
		max_h = max(max_h, a[i].len);
	}

	for (int i = 1; i <= m; i++)
	{
		int L, R, v;
		scanf("%d %d %d", &L, &R, &v);
		int l = 1, r = max_h, h = -1;
		while (l <= r)
		{
			int mid = l + r >> 1;
			if (check(L, R, mid) >= v)
			{
				h = mid;
				r = mid - 1;
			}
			else
				l = mid + 1;
		}
		printf("%dn", h);
	}
}
int main()
{
	solve();
	return 0;
}

树的最大匹配的定义？