> 科技资讯 > 2023 Hubei Provincial Collegiate Programming Contest题解 C F H I J K M

2023 Hubei Provincial Collegiate Programming Contest题解 C F H I J K M

科技资讯 投稿 7400℃ 0 评论

2023 Hubei Provincial Collegiate Programming Contest题解 C F H I J K M

原文链接：https://www.eriktse.com/algorithm/1136.html

M. Different Billing

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(
{
	ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
	int x, y;cin >> x >> y;
	for(int c = 0;c <= x; ++ c
	{
		int b = (y - 2500 * c / 1000;
		if(b < 0 || 1000 * b + 2500 * c != ycontinue;
		
		int a = x - b - c;
		
		if(a >= 0
		{
			cout << a << ' ' << b << ' ' << c << '\n';
			return 0;
		}
	}
	cout << -1 << '\n';
	return 0;
}

C. Darkness I

这题是对Minecraft中无限水的拓展过程为背景的一道思维题。

#include <bits/stdc++.h>
#define int long long
using namespace std;
 
 
signed main(
{
	ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
	int n, m;cin >> n >> m;
	int res = (n + 1 / 2 + (m + 1 / 2 - 1;
	if(n % 2 == 0 || m % 2 == 0res ++;
	cout << res << '\n';
	return 0;
}

J.Expansion

这题可以转化为以下题意：

我们模拟一下这个过程，如果到了某个点发现如果在当前点停留1秒会使得资源变为负数，就说明“我应该在左边的某个正数点多停留一会儿”，而为了使得停留时间最少，我会选择最大的点进行停留。

prefix[n]需要大于等于零，还有为了使得可以走到n，需要保证第一个非0的数为正数。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 9, p = 998244353;

int a[N], prefix[N];

signed main(
{
	ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
	int n;cin >> n;
	for(int i = 1;i <= n; ++ icin >> a[i];
	for(int i = 1;i <= n; ++ iprefix[i] = prefix[i - 1] + a[i];
	
	if(prefix[n] < 0
	{
		cout << -1 << '\n';
		return 0;
	}
	//遇到的第一个是负数
	for(int i = 1;i <= n; ++ i
	{
		if(prefix[i] != 0
		{
			if(prefix[i] < 0
			{
				cout << -1 << '\n';
				return 0;
			}
			break;
		}	
	}
	
	int ans = 0, res = 0, mx = 0;
	//前面一步步推进
	for(int i = 1;i <= n; ++ i
	{
		mx = max(mx, prefix[i];
		res += prefix[i];
		ans ++;//走一秒
		if(res < 0//说明走快了，应该在前面多停留一段时间的
		{
			//补几秒钟
			int ti = (-res + mx - 1 / mx;
			ans += ti;
			res += ti * mx;
		}
	}
	cout << ans << '\n';
	return 0;
}

H.Binary Craziness

赛时卡这道题了，一直在想拆位的做法（形成惯性思维了......糟糕）。

t）将会是1, 2, 3, 4, 5, ...其和为\(\frac{t(t + 1}{2} \le 2m\，所以长度t不会很大。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 9, p = 998244353;

int cnt[2 * N], a[N];

int f(int x, int y
{
	return (x ^ y * (x | y * (x & y;
}

signed main(
{
	ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
	int n, m;cin >> n >> m;
	
	for(int i = 1;i <= m; ++ i
	{
		int x, y;cin >> x >> y;
		a[x] ++, a[y] ++;
	}
	for(int i = 1;i <= n; ++ icnt[a[i]] ++;
	
	vector<int> v;
	for(int i = 1;i <= 2 * m; ++ iif(cnt[i]v.push_back(i;
	int res = 0;
	for(int i = 0;i < v.size(; ++ i
	{
		for(int j = i + 1;j < v.size(; ++ j
		{
			res = (res + cnt[v[i]] * cnt[v[j]] % p * f(v[i], v[j] % p % p;
		}
	}
	cout << res << '\n';
	
	return 0;
}

F.Inverse Manacher

这题甚至不需要会马拉车。

只需要理解回文半径的含义即可。

i时，如果a[i] > 1，说明我们要把i左边的一部分堆成到右边去，为了优化复杂度，我们可以用双指针，r表示此时b数组（也就是答案数组）的大小，也就是我们更新到的右端，当r < i + a[i] - 1时，我们就拓展得到b[r]，如果此时i > r，再根据一些情况来确定b[i]即可（交替的取a, b）。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 3e6 + 9;

int a[N];

char b[N];

signed main(
{
	ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
	int n;cin >> n;
	for(int i = 0;i <= 2 * n + 1; ++ icin >> a[i];
	
	char ch = 'a';
	
	for(int i = 0, r = 0;i <= 2 * n + 1; ++ i
	{
		while(i + a[i] - 1 > r++ r, b[r] = b[2 * i - r];
		if(i == 0b[i] = '&';
		else if(i & 1b[i] = '|';
		else if(b[i] == 0b[i] = ch, ch = (ch == 'a' ? 'b' : 'a';
	}
	for(int i = 2;i <= 2 * n + 1;i += 2cout << b[i];
	return 0;
}

K.Dice Game

这题主要难在分析出n个事件相互独立。

x确定时，对于n个人当中的某一个人，他胜利的概率是\(p = \frac{m-x}{m-1}\，这个有两种理解，第一个感性的理解就是，当投出y = x是没有意义的，所以有效的y一共是m个，其中m - x个是可以赢的。

t，胜利概率为q。

\[p= q + t * q + t^{2} * q + .... + t^{inf} * q \]

根据等比数列求和我们可以知道：

\[p = \frac{m-x}{m-1} \]
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 9, p = 998244353;

int qmi(int a, int b
{
	int res = 1;
	while(b
	{
		if(b & 1res = res * a % p;
		a = a * a % p, b >>= 1;
	}
	return res;
}

int inv(int x{return qmi(x, p - 2;}

signed main(
{
	ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
	int n, m;cin >> n >> m;
	int res = 1;
	for(int i = 1;i <= m; ++ i
	{
		cout << qmi((m - i * inv(m - 1 % p, n << ' ';
	}
	
	return 0;
}

I.Step

已知\(2t | k(k+1\，求最小的\(k\，其中\(t=lcm(p_1,p_2...,p_n\。

\[ax+1=by \]

转换一下得到：

\[a(-x+by=1 \]

a，可以算出b，然后exgcd搞出最小的x，即得到了k=ax答案。

a，我们看这个exgcd式子可以发现我们需要保证gcd(a, b = 1，且有2t = a * b，所以我们可以对2t进行唯一分解，然后选取不同质因子种类分配给a和b。

分配方案可以通过二进制直接做。

#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N = 1e6 + 9, inf = 8e18;

int p[N];

int gcd(int a, int b{return b == 0 ? a : gcd(b, a % b;}
int lcm(int a, int b{return a / gcd(a, b * b;}


map<int, int> mp;
vector<int> v;

void func(int x
{
	for(int i = 2;i <= x / i; ++ i
	{
		if(x % icontinue;
		v.push_back(i;
		mp[i] = 1;
		while(x % i == 0mp[i] *= i, x /= i;
	}
	if(x > 1v.push_back(x, mp[x] = x;
}

int exgcd(int a, int b, int &x, int &y
{
	if(!breturn x = 1, y = 0, a;
	int d = exgcd(b, a % b, y , x;
	y -= a / b * x;
	return d;
}

signed main(
{
	ios::sync_with_stdio(0, cin.tie(0, cout.tie(0;
	int n;cin >> n;
	for(int i = 1;i <= n; ++ icin >> p[i];
	int lc = p[1];
	for(int i = 2;i <= n; ++ ilc = lcm(lc, p[i];
	
	//对2 * lc进行质因数分解
	func(2 * lc;
	int res = inf;
	for(int i = 0;i < (1ll << v.size(; ++ i
	{
		//根据i得到a
		int a = 1;
		for(int j = 0;j < v.size(; ++ j
			if(i >> j & 1a = a * mp[v[j]];

		int b = 2 * lc / a;
		int x, y, d = exgcd(a, b, x, y;
		x = -x;
		x = (x % (b / d + (b /  d % (b / d;
		if(a * xres = min(res, x * a;
		//cout << "a = " << a << ' ' << "ax = " << a * x << '\n';
	}
	
	cout << res << '\n';
	
	return 0;
}

编程笔记 » 2023 Hubei Provincial Collegiate Programming Contest题解 C F H I J K M

赞同 (30) or 分享 (0)
游客 发表我的评论   换个身份
取消评论

表情
(0)个小伙伴在吐槽