2023年湖北省大学生程序设计竞赛题解

比赛链接:2023 Hubei Provincial Collegiate Programming Contest

文章目录

  • C. Darkness I(思维+构造)
  • F. Inverse Manacher(思维+构造)
  • H. Binary Craziness(暴力)
  • I. Step(exgcd)
  • J. Expansion(前缀和)
  • K. Dice Game(概率)
  • M. Different Billing(暴力)

C. Darkness I(思维+构造)

只要最上面一行和最左边一列填满就可以使整个矩阵填满了

所以怎么能让最上面一行和最左边一列填满呢?隔着填就好啦,所以输出 (n + m + 1) / 2

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
using i64 = long long;
 
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
 
const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
 
void solve()
{
	int n, m;
	cin >> n >> m;
	int ans = (m + n + 1) / 2;
	cout << ans << '\n';
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

F. Inverse Manacher(思维+构造)

给出 2n + 2 个数,首先我们可以确定前4个位置一定是 &|a| ,然后其实不用关注字母位的数字,只需要关注 | 位的数字即可,如果数字是 1,说明它左右两边的字母不一样,如果大于 1,说明左右两边字母一样,根据这个填上右边的字母就好了

#include <bits/stdc++.h>
 
using namespace std;
 
#define int long long
using i64 = long long;
 
typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;
 
const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;
 
void solve()
{
	int n;
	cin >> n;
	vector<char> s(2 * n + 3);
	s[1] = '&', s[2] = '|', s[3] = 'a';
	vector<int> a(2 * n + 3);
	for (int i = 1; i <= 2 * n + 2; i ++ ) cin >> a[i];
	for (int i = 4; i <= 2 * n + 2; i ++ )
	{
		if (i % 2 == 0)
		{
			s[i] = '|';
			if (a[i] > 1) s[i + 1] = s[i - 1];
			else
			{
				if (s[i - 1] == 'a') s[i + 1] = 'b';
				else s[i + 1] = 'a';
			}
		}
	}
	for (int i = 3; i <= 2 * n + 2; i ++ )
	{
		if (i & 1) cout << s[i];
	}
	cout << '\n';
}
 
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
 
	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

H. Binary Craziness(暴力)

把相同的数值放在一起算就行了,一个一个算肯定会t的

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n, m;
	cin >> n >> m;
	vector<int> ind(n + 1);
	for (int i = 0; i < m; i ++ )
	{
		int u, v;
		cin >> u >> v;
		ind[u] ++ ;
		ind[v] ++ ;
	}
	map<int, int> mp;
	for (int i = 1; i <= n; i ++ ) mp[ind[i]] ++ ;
	vector<PII> v;
	for (auto t : mp) v.push_back(t);
	int ans = 0;
	for (int i = 0; i < v.size(); i ++ )
	{
		for (int j = i + 1; j < v.size(); j ++ )
		{
			ans = (ans + (v[i].second * v[j].second) % mod * ((v[i].first & v[j].first) % mod * (v[i].first | v[j].first) % mod * (v[i].first ^ v[j].first) % mod) % mod) % mod;
		}
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

I. Step(exgcd)

设所有环长度的最小公倍数是 t ,答案的最小天数是 k,那么一共走的步数就是 ( 1 + k ) k 2 \frac{(1+k)k}{2} 2(1+k)k,如果要让所有马都回到 1 的位置,就要让 ( 1 + k ) k 2 \frac{(1+k)k}{2} 2(1+k)k 是 t 的倍数,也就是让 ( k + 1 ) k (k+1)k (k+1)k 2 t 2t 2t 的倍数

2 t = a × b 2t=a\times b 2t=a×b,让 k 是 a 的倍数,k + 1 是 b 的倍数,即 a x = k ,   b y = k + 1 ax=k,\ by=k+1 ax=k, by=k+1,得到 a x + 1 = b y ax+1=by ax+1=by,也就是 a ( − x ) + b y = 1 a(-x)+by=1 a(x)+by=1,如果我们知道了 a 和 b(且 a 和 b 要互质),这个式子就可以用 exgcd 解出来了

我们可以对 2 t 2t 2t 进行分解,分解出所有的质数,将不同的质数种类分配给 a 和 b(用二进制分配),然后解出 x 和 y,取最小的 a x ax ax 作为答案

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 5e7 + 10;
const int maxn = 1e7 + 10;
const int mod = 80112002;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool isprime[maxn]; // isprime[i]表示i是不是素数
int prime[maxn]; // 现在已经筛出的素数列表
int n; // 上限,即筛出<=n的素数
int cnt; // 已经筛出的素数个数

void euler()
{
    memset(isprime, true, sizeof(isprime)); // 先全部标记为素数
    isprime[1] = false; // 1不是素数
    for(int i = 2; i < maxn; ++i) // i从2循环到n(外层循环)
    {
        if(isprime[i]) prime[++cnt] = i;
        // 如果i没有被前面的数筛掉,则i是素数
        for(int j = 1; j <= cnt && i * prime[j] <= n; ++j)
        // 筛掉i的素数倍,即i的prime[j]倍
        // j循环枚举现在已经筛出的素数(内层循环)
        {
            isprime[i * prime[j]] = false;
            // 倍数标记为合数,也就是i用prime[j]把i * prime[j]筛掉了
            if(i % prime[j] == 0) break;
            // 最神奇的一句话,如果i整除prime[j],退出循环
            // 这样可以保证线性的时间复杂度
        }
    }
}

int exgcd(int a, int b, int &x, int &y) // 扩展欧几里得
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b, a % b, x, y);
    int temp = y;
    y = x - (a / b) * y;
    x = temp;
    return r; // 得到a b的最大公因数
}

void solve()
{
	euler();
	int n;
	cin >> n;
	map<int, int> mp;
	vector<int> v;
	int res = 1;
	for (int i = 1; i <= n; i ++ )
	{
		int x; cin >> x;
		res = lcm(res, x);
	}
	int tmp = 2 * res;
	for (int j = 1; j <= cnt; j ++ )
	{
		if (tmp % prime[j]) continue;
		mp[prime[j]] = 1;
		v.push_back(prime[j]);
		while (tmp % prime[j] == 0)
		{
			mp[prime[j]] *= prime[j];
			tmp /= prime[j];
		}
		if (tmp == 1) break;
	}
	int ans = INF;
	for (int i = 0; i < (1ll << v.size()); i ++ )
	{
		int a = 1;
		for (int j = 0; j < v.size(); j ++ )
		{
			if ((i >> j) & 1) a *= mp[v[j]];
		}
		int b = 2 * res / a;
		int x, y, d = exgcd(a, b, x, y);
		x = -x;
		x = (x % (b / d) + (b / d)) % (b / d);
		if (a * x) ans = min(ans, a * x);
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

J. Expansion(前缀和)

首先预处理一下前缀和 pre[i] ,在第 i 个位置加的值就是 pre[i]

然后再处理一下每个位置前面的最大值

然后从前往后遍历,到某一个位置,如果值小于0,那么就加这个位置之前的最大值,直到加到大于等于 0 为止

要注意预先判断一下第一个非零 pre 的值一定要大于 0,pre[n] 一定要小于 0

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int n;
	cin >> n;
	vector<int> a(n + 1);
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	vector<int> pre(n + 1);
	for (int i = 1; i <= n; i ++ ) pre[i] = pre[i - 1] + a[i];
	if (pre[n] < 0 || pre[1] < 0)
	{
		cout << -1 << '\n';
		return;
	}
	int maxx = 1;
	vector<int> maxn(n + 1);
	for (int i = 2; i <= n; i ++ )
	{
		maxn[i] = maxx;
		if (pre[i] > pre[maxx]) maxx = i;
	}
	int ans = 1, have = pre[1];
	for (int i = 2; i <= n; i ++ )
	{
		if (have + pre[i] < 0)
		{
			if (pre[maxn[i]] <= 0)
			{
				cout << -1 << '\n';
				return;
			}
			int cnt = (-have - pre[i]) / pre[maxn[i]];
			if ((-have - pre[i]) % pre[maxn[i]] != 0) cnt ++ ;
			ans += cnt;
			have += cnt * pre[maxn[i]];
		}
		have += pre[i];
		ans ++ ;
	}
	cout << ans << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

K. Dice Game(概率)

做完这题终于知道逆元怎么用了(

感性理解一下,如果第一个人的值是 x,其他人必须要比 x 大才能让第一个人输(如果也是 x 的话相当于没作用),所以情况总数是 m - 1 ,能赢的情况是 m - x,所以 每一个人赢了第一个人的概率就是 (m - x) / (m - 1) ,n 个人就是 n 次方

需要注意一下取模的情况

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int pow(int a, int n, int p) // 快速幂取模
{
    int ans = 1;
    while (n)
    {
        if (n & 1) ans = ans * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return ans;
}

int niYuan(int a, int b)	//费马小定理求逆元
{
    return pow(a, b - 2, b);
}

void solve()
{
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= m; i ++ )
	{
		int ans = pow((m - i) * niYuan((m - 1), mod) % mod, n, mod);
		cout << ans << ' ';
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

M. Different Billing(暴力)

枚举 a,然后解方程求 b c

#include <bits/stdc++.h>

using namespace std;

#define int long long
using i64 = long long;

typedef pair<int, int> PII;
typedef pair<int, char> PIC;
typedef pair<double, double> PDD;
typedef pair<int, PII> PIII;
typedef pair<int, pair<int, bool>> PIIB;

const int N = 1e6 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve()
{
	int x, y;
	cin >> x >> y;
	if (y % 500 != 0)
	{
		cout << -1 << '\n';
		return;
	}
	int tmp = y / 500;
	int a, b, c;
	for (int i = 0; i <= x; i ++ )
	{
		int tmp2 = 2 * x - 2 * i;
		if (tmp2 < 0)
		{
			cout << -1 << '\n';
			return;
		}
		int tmp3 = tmp - tmp2;
		if (tmp3 % 3 == 0)
		{
			c = tmp3 / 3;
			b = x - i - c;
			a = i;
			if (c >= 0 && a >= 0 && b >= 0 && a + b + c == x && 1000 * b + 2500 * c == y)
			{
				cout << a << ' ' << b << ' ' << c << '\n';
				return;
			} 
		}
	}
	cout << -1 << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	int t = 1;
	// cin >> t;
	while (t--)
	{
		solve();
	}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/606305.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

Linux|了解如何使用 awk 内置变量

引言 当我们揭开 Awk 功能部分时&#xff0c;我们将介绍 Awk 中内置变量的概念。您可以在 Awk 中使用两种类型的变量&#xff1a;用户定义的变量和内置变量。 内置变量的值已经在 Awk 中定义&#xff0c;但我们也可以仔细更改这些值&#xff0c;内置变量包括&#xff1a; FILEN…

实时路况信息获取的意义:点亮盲人前行的每一寸道路

在这个日新月异的科技时代&#xff0c;一款名为“蝙蝠避障”的创新应用正以温暖而坚定的步伐&#xff0c;为盲人朋友们的日常出行编织着安全与自由的网络。这款应用的核心——激光雷达技术&#xff0c;正以前所未有的方式&#xff0c;重新定义着实时路况信息获取的意义&#xf…

第二证券午评:沪指涨近1%,地产、半导体等板块拉升,锂电池概念活跃

9日早盘&#xff0c;两市股指全线走高&#xff0c;沪指涨近1%&#xff0c;创业板指大涨近2%&#xff1b;北向资金大举出场扫货&#xff0c;半日净买入超100亿元。 到午间收盘&#xff0c;沪指涨0.91%报3156.96点&#xff0c;深成指涨1.63%&#xff0c;创业板指涨1.85%&#xf…

【基于 PyTorch 的 Python深度学习】5 机器学习基础(2)

前言 文章性质&#xff1a;学习笔记 &#x1f4d6; 学习资料&#xff1a;吴茂贵《 Python 深度学习基于 PyTorch ( 第 2 版 ) 》【ISBN】978-7-111-71880-2 主要内容&#xff1a;根据学习资料撰写的学习笔记&#xff0c;该篇主要介绍了如何选择合适的激活函数、损失函数和优化器…

学习大数据,所需更要的shell基础(2)

文章目录 read读取控制台输入函数系统函数bashnamedirname 自定义函数Shell工具&#xff08;重点&#xff09;cutawk 正则表达式入门常规匹配常用特殊字符 read读取控制台输入 1&#xff09;基本语法 read (选项) (参数) ①选项&#xff1a; -p&#xff1a;指定读取值时的提示…

【福利】思科CCNP考试介绍(附CCNP题库下载)

网络行业有两个大神级别的证书&#xff1a;思科认证和华为认证&#xff0c;目前相比思科认证&#xff0c;华为认证在国内更加吃香哦&#xff0c;如果你在国内就业或发展考虑建议考华为的。不过还是有少部分在外企或有出国计划的IT人员考思科的。 那今天小微就来给大家介绍下思科…

SpringBoot启动流程源码解析

目录 一、SpringApplication构造方法解析 1. web应用类型 2. BootstrapRegistryInitializer 3. ApplicationContextInitializer 4. ApplicationListener 5. 推断Main方法所在类 二、SpringApplication.run(String... args)方法解析 1.创建DefaultBootstrapContext 2.获…

回顾5款我非常喜欢的软件,希望大家也能喜欢

​ 我喜欢分享好软件,这就像与老友聊天一样让我感到快乐。在这个过程中,我可以回顾这些实用的小工具,也希望它们可以帮助到更多人。 1.备份工具——Cobian Backup ​ Cobian Backup是一款功能强大的备份软件&#xff0c;支持自动定时备份、增量备份、差异备份等多种备份方式。…

Java八股文系列之四(JVM)

什么是Java虚拟机&#xff1f;为什么Java被称作是“平台无关的编程语言”&#xff1f; Java虚拟机是一个可以执行Java字节码的虚拟机进程。 Java 实现跨平台的主要原因在于它的编译和执行方式。Java 程序首先被编译成中间代码&#xff08;bytecode&#xff09;&#xff0c;然…

九泰智库 | 医械周刊- Vol.26

⚖️ 法规动态 国家卫健委等八部门印发《关于加强重症医学医疗服务能力建设的意见》 5月6日&#xff0c;国家卫健委发布《关于加强重症医学医疗服务能力建设的意见》&#xff0c;明确我国重症医学领域的重要部署。数据显示&#xff0c;我国在重症救治设备方面依然存在巨大缺口…

vue中使用element的i18n语言转换(保姆式教程-保证能用)

1、项目中需要使用的插件&#xff0c;vue2或vue3、element、vue-i18n、js-cookie、vuex我是在vue2中使用 npm i element-ui -S npm i js-cookie -S npm i vue-i18n8.28.2 //因为我项目使用的vue2&#xff0c;直接安装报错了,就下载了固定的版本2、在main.js中引入i18n impor…

芸众商城电商专业版400+插件源码+搭建教程

介绍&#xff1a; 芸众商城社交电商系统SAAS平台前端基于vue开发&#xff0c;后端基于研发积分商城系统源码 php&#xff0c;本文安装芸众商城全插件&#xff08;400多个&#xff09;商业版平台源码&#xff0c;可同时支持多端口部署运行&#xff1b;使用宝塔面板一键部署的形…

出货300万片后,智舱界「小高通」浮出水面

‍作者 |张祥威 编辑 |德新 2024年北京车展&#xff0c;本土芯片公司开始截击外企供应商。 很长一段时间内&#xff0c;汽车行业智驾芯片看英伟达&#xff0c;座舱芯片看高通。英伟达Orin系列广受欢迎&#xff0c;高通8155席卷主流智能汽车&#xff0c;8295更是被视为最强配置…

倍思|西圣开放式耳机哪个好用?热门机型深度测评!

在数字化生活的浪潮中&#xff0c;耳机已成为我们不可或缺的伴侣。然而&#xff0c;长时间佩戴传统的耳机容易导致的耳道疼痛等问题&#xff0c;严重的话将影响听力。许多人开始寻找更为舒适的佩戴体验。开放式耳机因为不需要需直接插入耳道的设计&#xff0c;逐渐受到大众的青…

不会pdf修改编辑文字怎么办?看完秒懂

不会pdf修改编辑文字怎么办&#xff1f;在日常生活中&#xff0c;PDF文件已成为我们工作、学习不可或缺的一部分。然而&#xff0c;很多人对PDF文件的编辑操作感到困惑&#xff0c;尤其是修改其中的文字。今天&#xff0c;我们就来详细解析一下&#xff0c;不会PDF修改编辑文字…

全局变量在 Python 中的应用场景

在Python中&#xff0c;全局变量是在程序的全局范围内定义的变量&#xff0c;可以在整个程序中访问。虽然在Python中使用全局变量并不像在其他编程语言中那样被推荐&#xff0c;因为它可能导致代码不易理解和维护&#xff0c;但在一些特定的情况下&#xff0c;全局变量仍然是有…

企业微信hook接口协议,ipad协议http,设置是否自动同意

设置是否自动同意 参数名必选类型说明uuid是String每个实例的唯一标识&#xff0c;根据uuid操作具体企业微信 请求示例 {"uuid":"bc4800492083fdec4c1a7e5c94","state":1 //1 是需要验证同意&#xff08;需要手动点击同意&#xff09; 0关闭验证…

gtest的编译与使用

文章目录 gtest的编译与使用概述笔记CMake参数官方文档测试程序测试效果END gtest的编译与使用 概述 gTest是 googletest的缩写&#xff0c;如果直接找gTest项目&#xff0c;是找不到的。 库地址 https://github.com/google/googletest.git 迁出到本地后&#xff0c;切到最新…

中电金信:看 “咨询+技术”如何引领数字化变革新风向

当前&#xff0c;新一轮创新技术和产业变革正在重塑全球的经济格局。日本政府及社会各界也从各个领域着手推进数字化。2021年&#xff0c;日本政府成立了“数字厅”&#xff0c;通过一系列举措推动数字化升级&#xff0c;希望将日本加速转型为数字经济的区域领导者&#xff0c;…

继续SQL

主知识点六&#xff1a;having 聚合前的筛选用where&#xff0c;聚合后的筛选用having Having和where的区别是&#xff1a;运行顺序和对象不用 Having是在group by聚合后的基础上进行筛选。 ● 【例题27*】&#xff08;运行原理&#xff09;查询总人口数至少为3亿的大洲和…
最新文章