第十五届吉林省赛个人题解【中档题(不过可能对你来说是简单题)】(H、G、C)

这篇具有很好参考价值的文章主要介绍了第十五届吉林省赛个人题解【中档题(不过可能对你来说是简单题)】(H、G、C)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

H. Visit the Park(STL)

题意:给你一个无向图,每条边上都有一个数码,然后给你一个路径,每次你必须从Ai走到Ai+1(直接走到,必须相邻),如果有多条路径,你等概率的选择这些路径,这样从头走到尾,你依次把这些数码写下来,得到一个十进制数,现在问你最后可以得到的期望是多少?
思路:我们可以单独考虑每一位的贡献,个位上的某种在所有从左到右写下来的数的个位的占比仅和个位自身各种数码的比例有关,尽管高其他位右各种选择,但是个位上出现这个数码的概率是相同的。利用map我们维护总数,和各种数码出现的次数。
注意:这里容易被卡常,我们可以发现求逆元的常数为30,加上10个数码,如果放到循环內部的话,就是300,再乘上3e5,9e7加上其他常数,tle4了。所以必须放外面。logn最多是20,常数小1.5倍。

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 3e5 + 5, mod = 998244853;
map<pair<int, int>, int> g[N];//这是一个map<pair<int,int>, int>为元素的数组
map<pair<int, int>, int> sum;
ll po(ll rad, ll idx) {
	ll res = 1;
	while (idx) {
		if (idx & 1) res = res * rad % mod;
		rad = rad * rad % mod;
		idx >>= 1;
	}
	return res;
}
int a[N];
void solve() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		g[u][{v, w}]++;
		g[v][{u, w}]++;
		sum[{u, v}]++;
		sum[{v, u}]++;
	}
	for (int i = 1; i <= k; i++) cin >> a[i];
	ll ans = 0;
	for (int i = k; i > 1; i--) {
		int u = a[i], v = a[i - 1];
		int ss = sum[{u, v}];
		if (!ss) {
			cout << "Stupid Msacywy!\n";
			return;
		}
		ll mul = po(10, k - i), sub = po(ss, mod - 2);//这里很重要 
		for (int j = 1; j <= 9; j++) {
			if (g[u].count({v, j})) ans = (ans + mul * j % mod * g[u][{v, j}] % mod * sub % mod) % mod; 
		}
	}
	cout << ans << '\n';
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
//	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

G. Matrix Repair(思维题)

背景:在数据传输当中常见的奇偶性检查
题意:给你一个破损的矩阵,给你原来的矩阵的行列的奇偶性,让你复原这个矩阵,如果矩阵唯一,就输出这个矩阵,如果矩阵不唯一,就输出-1。
思路:(借用oiwiki的图)
第十五届吉林省赛个人题解【中档题(不过可能对你来说是简单题)】(H、G、C)
我们如果把所有-1处和所在的行列列出方程,我们可以发现,如果说任何一行一列都不存在只有一个-1的情况,那么每条方程,至少有两个未知数。对于不同行,不同列,这些方程最多只有一个相同的未知元。(也就是某行和某列相交的情况有一个相同的未知元(-1)),因此我们无法通过加减消元解出任何一个确定的未知元,无论如何消元都至少有两个未知元。因此我们拓扑排序,逐步带入某个确定的未知元即可。

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
const int N = 1005, mod = 998244853;
int a[N][N], r[N], c[N], nr[N], nc[N];
set<int> g[N << 1];
void solve() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> a[i][j];
		}
	}
	for (int i = 1; i <= n; i++) {
		cin >> nr[i];
		int s = 0;
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == -1) {
				g[i].insert(j);
				continue;
			}
			s ^= a[i][j];
		}
		r[i] = s;
	}
	for (int j = 1; j <= n; j++) {
		cin >> nc[j];
		int s = 0;
		for (int i = 1; i <= n; i++) {
			if (a[i][j] == -1) {
				g[j + n].insert(i);
				continue;
			}
			s ^= a[i][j];
		}
		c[j] = s;
	}
	set<pair<int, int>> st;
	for (int i = 1; i <= n * 2; i++) {
		st.insert({g[i].size(), i});
	}
	while (!st.empty()) {
		pair<int, int> pii = *st.begin();
		int fi = pii.first, se = pii.second;
		st.erase(st.begin());
		if (fi == 0) continue;
		if (fi != 1) break;
		if (se > n) {//如果是某列的话 
			int x = *g[se].begin();//该列含有的唯一的-1 
			g[se].erase(g[se].begin());//删除-1 
			st.erase({g[x].size(), x});//-1所在行删除 
			int y = se - n;//对应列 
			g[x].erase(y);//对应行删除本列
			st.insert({g[x].size(), x});//更新对应行 
			a[x][y] = c[y] ^ nc[y];//填数字 
			c[y] = nc[y];//更新列 
			r[x] ^= a[x][y];//更新行 
		} else {
			int y = *g[se].begin();//该行含有的唯一的-1 
			g[se].erase(g[se].begin());//删除-1 
			int x = se;//对应行 
			st.erase({g[y + n].size(), y + n});//删除对应列,这里要+n 
			g[y + n].erase(x);
			st.insert({g[y + n].size(), y + n});//更新对应列 
			a[x][y] = r[x] ^ nr[x];//更新 
			r[x] = nr[x];
			c[y] ^= a[x][y];
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (a[i][j] == -1) {
				cout << -1 << '\n';
				return;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << a[i][j] << " \n"[j == n];
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
//	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

C.Random Number Generator(BSGS算法)

题意:给定x0,a,b,m,问利用线性同余方法xi+1=axi+b(mod m)判断某个数是否在xn的集合内。
思路:参考这篇
补充一下如何求出等比式子,待定系数法。
A X n + 1 + B = a ( A X n + B ) AX_{n+1}+B=a(AX_n+B) AXn+1+B=a(AXn+B)
A X n + 1 = a A X n + a B − B = A a X n + A b AX_{n+1}=aAX_n+aB-B=AaX_{n}+Ab AXn+1=aAXn+aBB=AaXn+Ab
A = 1 , B = b a − 1 A=1,B=\frac{b}{a-1} A=1,B=a1b
评论:BSGS就是暴力根号分治加哈希。
关于特判:a= 1的时候b=0的时候是no,注意不要使用 a- 1作为逆元,0逆元会把人橄榄。文章来源地址https://www.toymoban.com/news/detail-438267.html

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
using namespace std;
ll a, b, x0, m, x;
ll po(ll rad, ll idx) {
	ll res = 1;
	while (idx) {
		if (idx & 1) res = res * rad % m;
		rad = rad * rad % m;
		idx >>= 1;
	}
	return res;
}
ll bsgs(ll a, ll b) {
	map<ll, ll> mp;
	ll cur = 1, t = sqrtl(m) + 1;
	for (int B = 1; B <= t; B++) {
		cur = cur * a % m;
		mp[cur * b % m] = B;
	}
	ll now = cur;
	for (int A = 1; A <= t; A++) {
		if (mp.count(now)) return A * t - mp[now];
		now = now * cur % m;
	}
	return -1;
}
void solve() {
	cin >> a >> b >> m >> x0 >> x;
	if (x == x0) {
		cout << "YES\n";
		return;
	}
	if (a == 0) {
		cout << (x == b % m ? "YES\n" : "NO\n");
		return;
	}
	if (a == 1) {
		if (b == 0) {
			cout << "NO\n";
			return;
		} 
	}
	ll aa = a;
	ll bb = (x * (a - 1) + b % m) % m * po((x0 * (a - 1) + b) % m, m - 2) % m;
	cout << (bsgs(aa, bb) == -1 ? "NO\n" : "YES\n");
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
//	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

到了这里,关于第十五届吉林省赛个人题解【中档题(不过可能对你来说是简单题)】(H、G、C)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 第十五届蓝桥杯模拟赛(第一期)

    大家好,我是晴天学长,本次分享,制作不易,需要的小伙伴可以点赞关注评论一波哦!后续会继续更新第二期第三期的。💪💪💪 问题描述 请找到一个大于 2022 的最小数,这个数转换成十六进制之后,所有的数位(不含前导 0)都为字母(A 到 F)。 请将这个数的十进制形

    2024年02月04日
    浏览(65)
  • 第十五届蓝桥杯模拟赛(第一期 C++)

    问题描述 请找到一个大于 2022 的最小数,这个数转换成十六进制之后,所有的数位(不含前导 0)都为字母(A 到 F)。请将这个数的十进制形式作为答案提交。    答案: 2730 思路分析: 直接暴力秒了 问题描述 在 Excel 中,列的名称使用英文字母的组合。前 26 列用一个字母

    2024年02月05日
    浏览(55)
  • 第十五届蓝桥杯模拟赛(第一期)Python

    创作不易,欢迎小伙伴们关注、点赞+收藏! 问题描述 请找到一个大于 2022 的最小数,这个数转换成十六进制之后,所有的数位(不含前导 0)都为字母(A 到 F)。 请将这个数的十进制形式作为答案提交。 答案提交 这是一道结果填空的题,你只需要算出结果后提交即可。本

    2024年02月05日
    浏览(79)
  • 第十五届蓝桥杯模拟赛(第二期)JAVA

    (做的时候忘记小题截图了,没有题目,个人答案,可能会有问题) 1. 108 2.608 3.4169 4.901440 5.541(有问题,看错题目了) 6. 问题描述 给定一个正好六位的正整数 x,请将 x 循环左移一位后输出。 所谓循环左移一位,是指将原来的十万位变为个位,原来的万位到个位向左移动依

    2024年02月04日
    浏览(59)
  • 第十五届全国大学生信息安全竞赛部分WriteUp

    做了10个,都是烂大街的题目,分数很低。CTF榜单186,以为稳进分区赛了。理论题算上变一千五百多名,华东南二百多名,进不去了,WriteUp也不想上传了。 不是密码选手,但密码非预期搞出来几个 签到电台 关注公众号给的提示“弼时安全到达了”,查找这几个字的中文电码

    2024年02月06日
    浏览(61)
  • 第十五届全国大学生信息安全竞赛创新实践能力赛

    ​ 这两个应该是属于非预期,查找文件内容,两个flag都出了: find / |xargs grep -ri flag{ 2/dev/null flag{34f5fdaf-c373-47fd-afab-01ed2914c11a} 解题步骤同上 使用hydra爆破获得root密码toor。 登陆查找(find / |xargs grep -ri flag{ 2/dev/null)获得flag flag{7b352ef0-1bb1-41af-a7d7-b74f62ff23f0} 爆破sha256老脚本套

    2024年02月07日
    浏览(49)
  • 2023第十五届电工杯数学建模AB题思路模型

    (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor “中国电机工程学会杯”全国大学生电工数学建模竞赛已成功举办十四届,累计参赛高校千余所,参赛学生近10万人,是目前国内最具影响力、显著提高学生创新意识和综合素质的大学生竞赛项目之一。“中国电机

    2024年02月11日
    浏览(45)
  • 第十五届蓝桥杯模拟赛B组(第二期)C++

    前言: 第一次做蓝桥模拟赛的博客记录,可能有很多不足的地方,现在将第十五届蓝桥杯模拟赛B组(第二期)的题目与代码与大家进行分享,我是用C++做的,有好几道算法题当时自己做的也是一脸懵,所以有好个别几道也是请教了其他大佬才分享出来的。 目录 ​编辑 一、

    2024年02月05日
    浏览(56)
  • 第十五届蓝桥杯模拟赛(第二期)第5题(Python)

    最难的才有挑战性,才值得学习! 小蓝有一个01矩阵。他打算将第一行第一列的 0 变为 2 。变化过程有传染性,每次 2 的上下左右四个相邻的位置中的 0 都会变成 2 。直到最后每个 2 的周围都是 1 或 2 结束。 请问,最终矩阵中有多少个 2 ? 以下是小蓝的矩阵,共 30 行 40 列。

    2024年02月04日
    浏览(49)
  • 第十五届蓝桥杯单片机组备赛——中断系统与外部中断应用

      内核与外设之间的主要交互方式有两种: 轮询 和 中断 。   轮询的方式貌似公平,但实际工作效率很低,且不能及时响应紧急事件;   中断系统使得内核具备了应对突发事件的能力。在执行CPU当前程序时,由于系统中出现了某种急需处理的情况,CPU暂停正在执行的程

    2024年01月17日
    浏览(56)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包