2023年ICPC杭州站题解

比赛链接：The 2023 ICPC Asia Hangzhou Regional Contest (The 2nd Universal Cup. Stage 22: Hangzhou)

文章目录

  • D. Operator Precedence（构造）
  • G. Snake Move（最短路）
  • H. Sugar Sweet II（基环树+概率）
  • J. Mysterious Tree（图论交互）
  • M. V-Diagram（思维）

D. Operator Precedence（构造）

介于一乘起来就没完没了了，所以尽可能不让乘法里出现大于等于2的数，于是可以想到构造一个类似于：x 2 -1 2 -1 … 2 -1 y

然后让 y 为 1，求 x

（自己这次还是没能想出来，感谢队友）

#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 = 1e5 + 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;
	cout << 2 * n - 3 << ' ' << 2 << ' ';
	for (int i = 0; i < (2 * n - 4); i ++ )
	{
		if (i % 2 != 0) cout << 2 << ' ';
		else cout << -1 << ' ';
	}
	cout << -1 << ' ' << 1 << '\n';
}

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

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

G. Snake Move（最短路）

标记一下蛇身在的位置需要多少次之后才能访问（用 flag 标记），其他就正常跑最短路，然后距离在 dd + 1 和 flag[nx][ny] + 1 里取 max 即可

#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 = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int dx[] = {0, 0, 1, -1}, dy[] = {1, -1, 0, 0};

void solve()
{
	int n, m, k;
	cin >> n >> m >> k;
	vector<vector<char>> g(n + 2, vector<char>(m + 2));
	vector<vector<int>> flag(n + 2, vector<int>(m + 2));
	vector<vector<bool>> st(n + 2, vector<bool>(m + 2));
	vector<vector<int>> dist(n + 2, vector<int>(m + 2, INF));
	priority_queue<PIII, vector<PIII>, greater<PIII>> pq;
	int px, py;
	for (int i = 1; i <= k; i ++ )
	{
		int x, y;
		cin >> x >> y;
		flag[x][y] = k - i;
		if (i == 1)
		{
			px = x, py = y;
			dist[x][y] = 0;
			pq.push({0, {x, y}});
		}
	}
	for (int i = 1; i <= n; i ++ )
		for (int j = 1; j <= m; j ++ )
			cin >> g[i][j];
	while (pq.size())
	{
		auto t = pq.top();
		pq.pop();

		int dd = t.first, x = t.second.first, y = t.second.second;
		if (st[x][y]) continue;
		st[x][y] = true;

		for (int i = 0; i < 4; i ++ )
		{
			int nx = x + dx[i], ny = y + dy[i];
			if (nx <= 0 || nx > n || ny <= 0 || ny > m) continue;
			if (st[nx][ny] || g[nx][ny] == '#') continue;
			if (dist[nx][ny] > max(dd + 1, flag[nx][ny] + 1))
			{
				dist[nx][ny] = max(dd + 1, flag[nx][ny] + 1);
				pq.push({dist[nx][ny], {nx, ny}});
			}
		}
	}

	unsigned long long ans = 0;
	for (int i = 1; i <= n; i ++ )
	{
		for (int j = 1; j <= m; j ++ )
		{
			if (dist[i][j] == INF) continue;
			ans = ans + dist[i][j] * dist[i][j];
		}
	}
	cout << ans << '\n';
}

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

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

H. Sugar Sweet II（基环树+概率）

首先我们可以根据题目中给的关系建一个基环森林（也就是 b[i] 向 i 建边，因为 b[i] 的状态会影响 i 要不要加 w[i]）

然后我们把所有的点分成三类：

  • a[i] < a[b[i]] 此时 b[i] 不管加不加 w[b[i]] ， a[i] 都是要加 w[i] 的，将 dist[i] 标记为 1
  • a[i] >= a[b[i]] + w[b[i]] 此时 b[i] 不管加不加 w[b[i]] ， a[i] 都是不加 w[i] 的，将 dist[i] 标记为 0
  • a[b[i]] + w[b[i]] < a[i] < a[b[i]] 此时 b[i] 加 i 就加，b[i] 不加 i 就不加，因为只有这里是不确定的，所以只在这种情况建边

先利用 dfs 算出每个第一类点到第三类点的距离，如果第一类点在随机排序中达到了现在我们建的图这种情况，那么第三类点就要加，那有多大的概率能达到呢？第一类点到第三类点的距离我们在 dfs 中预处理过了，所以就是全排列分之一，即 1 ( d i s t [ i ] ! ) \frac{1}{(dist[i]!)} (dist[i]!)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 = 1e5 + 10;
const int maxn = 5e6 + 10;
const int mod = 1e9 + 7;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int Jc[maxn];

void calJc()	//求 maxn 以内的数的阶乘 不知道开多少就1e6吧爆不了
{
    Jc[0] = Jc[1] = 1;
    for(int i = 2; i < maxn; i++) Jc[i] = Jc[i - 1] * i % mod;
}

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;
	cin >> n;
	vector<int> a(n + 1), b(n + 1), w(n + 1);
	for (int i = 1; i <= n; i ++ ) cin >> a[i];
	for (int i = 1; i <= n; i ++ ) cin >> b[i];
	for (int i = 1; i <= n; i ++ ) cin >> w[i];
	vector<vector<int>> g(n + 1);
	vector<int> dist(n + 1);
	for (int i = 1; i <= n; i ++ )
	{
		if (a[b[i]] > a[i]) dist[i] = 1;
		else if (a[b[i]] + w[b[i]] <= a[i]) dist[0] = 0;
		else g[b[i]].push_back(i);
	}
	function<void(int)> dfs = [&](int u)
	{
		for (int i = 0; i < g[u].size(); i ++ )
		{
			int j = g[u][i];
			dist[j] = dist[u] + 1;
			dfs(j);
		}
	};
	for (int i = 1; i <= n; i ++ )
	{
		if (dist[i] == 1) dfs(i);
	}
	vector<int> ans(n + 1);
	for (int i = 1; i <= n; i ++ )
	{
		if (dist[i] == 0) ans[i] = a[i];
		else ans[i] = (a[i] + w[i] * niYuan(Jc[dist[i]], mod) % mod) % mod;
		cout << ans[i] << ' ';
	}
	cout << '\n';
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	calJc();
	int t = 1;
	cin >> t;
	while (t--)
	{
		solve();
	}
}

J. Mysterious Tree（图论交互）

首先关注操作次数 ⌈ n 2 ⌉ + 3 \lceil \frac{n}{2} \rceil + 3 ⌈2n​⌉+3 ，看到这就很容易想到那个 n/2 是两两之间连一次吧，如果从头到尾都没碰到相连的边，说明不可能是星形（因为根本没有中间的那个点），一定是链，一旦碰到一个相连的边，就立刻停下

假设这条边的两个端点是 i j，如果 i j 不是 1 2 的话，直接先让 i 和 i - 2 连，有边再让 i 和 i - 1 连，如果还是有边就说明是星形，如果没有边就让 j 和 i - 2、i - 1 连（很容易判断就不详细说了），如果 i j 是 1 2 的话就需要单独注意一下

另外 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 = 1e5 + 10;
const int maxn = 1e6 + 10;
const int mod = 998244353;
const int mod1 = 954169327;
const int mod2 = 906097321;
const int INF = 0x3f3f3f3f3f3f3f3f;

int print(int a, int b)
{
	cout << "? " << a << ' ' << b << endl;
	int x; cin >> x;
	return x;
}

void solve()
{
	int n;
	cin >> n;
	int pos = -1;
	for (int i = 1; i + 1 <= n; i += 2)
	{
		int x = print(i, i + 1);
		if (x == 1)
		{
			pos = i;
			break;
		}
	}
	if (pos == -1 && n & 1)
	{
		int x = print(n - 1, n);
		if (x == 1) pos = n - 1;
	}
	if (pos == -1)
	{
		cout << "! 1" << endl;
		return;
	}
	if (pos != 1)
	{
		int x = print(pos, pos - 2);
		if (x == 1)
		{
			int y = print(pos, pos - 1);
			if (y == 1)
			{
				cout << "! 2" << endl;
				return;
			}
			else
			{
				cout << "! 1" << endl;
				return;
			}
		}
		else
		{
			int y = print(pos + 1, pos - 2);
			if (y == 0)
			{
				cout << "! 1" << endl;
				return;
			}
			else
			{
				int z = print(pos + 1, pos - 1);
				if (z == 1)
				{
					cout << "! 2" << endl;
					return;
				}
				else
				{
					cout << "! 1" << endl;
					return;
				}
			}
		}
	}
	else
	{
		int x = print(1, 3);
		if (x == 1)
		{
			int y = print(1, 4);
			if (y == 1)
			{
				cout << "! 2" << endl;
				return;
			}
			else
			{
				cout << "! 1" << endl;
				return;
			}
		}
		else
		{
			int y = print(2, 3);
			if (y == 0)
			{
				cout << "! 1" << endl;
				return;
			}
			else
			{
				int z = print(2, 4);
				if (z == 1)
				{
					cout << "! 2" << endl;
					return;
				}
				else
				{
					cout << "! 1" << endl;
					return;
				}
			}
		}
	}
}

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

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

M. V-Diagram（思维）

首先我们一定要选中间的三个数，然后我们只要再选一个比当前数大的数，整体平均值就一定会上升，（设中间最小坐标是pos）所以答案只可能是 [1, pos + 1] [pos - 1, n] [pos - 1, pos +1] [1, 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 = 1e5 + 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);
	int pos = 0;
	for (int i = 1; i <= n; i ++ )
	{
		cin >> a[i];
		if (i != 1 && a[i] > a[i - 1] && pos == 0) pos = i - 1;
	}
	int sum1 = 0, sum2 = 0;
	for (int i = 1; i < pos - 1; i ++ ) sum1 += a[i];
	for (int i = pos + 2; i <= n; i ++ ) sum2 += a[i];
	double ans = a[pos] + a[pos - 1] + a[pos + 1];
	ans = max({1.0 * ans / 3, 1.0 * (ans + sum1) / (pos + 1), 1.0 * (ans + sum2) / (n - pos + 2), 1.0 * (ans + sum2 + sum1) / n});
	printf("%.10lf\n", ans);
}

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/581317.html

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

相关文章

一文读懂Partisia Blockchain 的互操作方案：Oracle 服务框架

一文读懂Partisia Blockchain 的互操作方案：Oracle 服务框架

Partisia Blockchain 是一个以 MPC 技术为特点的创新隐私公链&#xff0c;其通过将 MPC 技术方案引入到区块链系统中&#xff0c;并以零知识证明&#xff08;ZK&#xff09;技术和多方计算&#xff08;MPC&#xff09;等方案为基础&#xff0c;共同保障在不影响网络完整性和安全…
阅读更多...
面试八股——HashMap

面试八股——HashMap

实现原理 红黑树是为了解决链表过长之后&#xff0c;查找时间过长的问题&#xff0c;将链表存储变为红黑树存储。 put方法的实现&#xff08;5⭐&#xff09; 相关属性&#xff1a; 1. 容量&#xff1a;初始容量为2^4。 2. 加载因子&#xff1a;初始值为0.75 上面两个属性的…
阅读更多...
GITEE本地项目上传到远程

GITEE本地项目上传到远程

由于需要&#xff0c;我这边将本地的仓库上传至GITEE。之前在网上搜索了相关的文档&#xff0c;但是步骤很繁琐&#xff0c;我这边介绍一个非常简单的。 一、在GITEE新建仓库 跟着指引一步步新建。 二、打开本地仓库&#xff0c;删除.git文件 默认情况下不会有这个.git文件&a…
阅读更多...
李廉洋：4.29周一黄金原油走势分析，做单必看策略，

李廉洋：4.29周一黄金原油走势分析，做单必看策略，

在关于美联储是否降息以及何时降息的争论中&#xff0c;另一场重要的争论正在展开&#xff1a;长期来看&#xff0c;利率将何去何从&#xff1f;问题的关键在于中性利率&#xff1a;即能够使储蓄供求平衡、同时保证经济增长和通胀稳定的利率。中性利率有时被称为“r*”或“r-st…
阅读更多...
便携式iv检测仪解析

便携式iv检测仪解析

TH-PV31光伏电站便携式IV功率测试仪是一种专门用于光伏电站运维和故障排查的设备。它具备高精度、快速测试以及便携性等特点&#xff0c;成为光伏电站日常运维中不可或缺的工具。 首先&#xff0c;从工作原理来看&#xff0c;光伏电站便携式IV功率测试仪通过模拟太阳光照射光伏…
阅读更多...
GaussianCube：使用最优传输构造高斯溅射用于3D生成建模

GaussianCube：使用最优传输构造高斯溅射用于3D生成建模

GaussianCube: Structuring Gaussian Splatting using Optimal Transport for 3D Generative Modeling GaussianCube&#xff1a;使用最优传输构造高斯溅射用于3D生成建模 Bowen Zhang1⁣*    Yiji Cheng2⁣*   Jiaolong Yang3   Chunyu Wang3 张博文 1⁣* 程一季 2⁣* …
阅读更多...
第三节课，后端登录【1】.1--本人

第三节课，后端登录【1】.1--本人

一、后端登录逻辑&#xff0c;检测账户密码是否合法及密码输入是否正确 视频链接&#xff1a; 网址&#xff1a; 第三节&#xff1a;【视频】后端登录逻辑&#xff0c;检测账户密码是否合法及密码输入是否正确视频链接&#xff1a;-CSDN博客 从5.1开始 这是一个Java方法&am…
阅读更多...
网工内推 | 云计算运维，厂商云相关认证优先，股票期权，全勤奖

网工内推 | 云计算运维，厂商云相关认证优先，股票期权，全勤奖

01 国科科技 招聘岗位&#xff1a;云计算运维 职责描述&#xff1a; 1、负责私有云平台的运维管理工作,包括云平台日常运维、故障处理、扩容、版本升级、优化和维护等。 2、根据业务需求,从技术角度支持及配合各业务系统上云工作。 3、为云上业务系统提供云产品、云服务方面的…
阅读更多...
嵌入式全栈开发学习笔记---Linux基本命令4

嵌入式全栈开发学习笔记---Linux基本命令4

目录 压缩和解压缩 tar -zcf 压缩包的名字 需要压缩的文件 tar -xzf 压缩包的名字 查找命令 Find 路径 -name “文件名” grep “搜索的关键字” 路径 -R 我们最后学习几个命令&#xff1a; 我们有的时候下载一些文件、软件、库&#xff0c;它会以压缩包的形式出现&am…
阅读更多...
Git零基础

Git零基础

Git工作流程图 操作指令 分支 、 指令总结 远程仓库
阅读更多...
玄子Share-PXE高效批量网络装机

玄子Share-PXE高效批量网络装机

玄子Share-PXE高效批量网络装机 部署PXE远程安装服务 PXE 概述 PXE&#xff08;Preboot eXcution Environment&#xff09; 预启动执行环境&#xff0c;在操作系统之前运行 服务端 运行DHCP服务&#xff0c;用来分配地址、定位引导程序运行TFTP服务&#xff0c;提供引导程…
阅读更多...
计算机网络——应用层协议(1)

计算机网络——应用层协议(1)

在这篇文章初识网络中&#xff0c;我介绍了关于计算机网络的相关知识&#xff0c;以及在这两篇文章中Socket编程和Socket编程——tcp&#xff0c;介绍了使用套接字在两种协议下的网络间通信方式。本篇文章中我将会进一步介绍网络中网络协议的部分&#xff0c;而这将会从应用层开…
阅读更多...
基于SpringBoot+Vue乡村养老服务管理系统

基于SpringBoot+Vue乡村养老服务管理系统

项目介绍&#xff1a; 使用旧方法对乡村养老服务管理系统登录的信息进行系统化管理已经不再让人们信赖了&#xff0c;把现在的网络信息技术运用在乡村养老服务管理系统登录的管理上面可以解决许多信息管理上面的难题&#xff0c;比如处理数据时间很长&#xff0c;数据存在错误…
阅读更多...
[笔试训练](十)

[笔试训练](十)

目录 028&#xff1a;最长回文子串 029&#xff1a;买卖股票的最好时机&#xff08;一&#xff09; 030&#xff1a;过河卒 028&#xff1a;最长回文子串 最长回文子串_牛客题霸_牛客网 (nowcoder.com) 题目&#xff1a; 题解&#xff1a; 1.中心扩展算法&#xff1a; 每…
阅读更多...
Docker镜像和容器操作

Docker镜像和容器操作

目录 一.Docker镜像创建与操作 1. 搜索镜像 2. 获取镜像 3. 镜像加速下载 4. 查看镜像信息 5. 查看下载的镜像文件信息 ​编辑6. 查看下载到本地的所有镜像 7. 根据镜像的唯一标识ID号&#xff0c;获取镜像详细信息 8. 为本地的镜像添加新的标签 9. 删除镜像 10. 存入…
阅读更多...
Linux 第十一章

Linux 第十一章

&#x1f436;博主主页&#xff1a;ᰔᩚ. 一怀明月ꦿ ❤️‍&#x1f525;专栏系列&#xff1a;线性代数&#xff0c;C初学者入门训练&#xff0c;题解C&#xff0c;C的使用文章&#xff0c;「初学」C&#xff0c;linux &#x1f525;座右铭&#xff1a;“不要等到什么都没有了…
阅读更多...
BUUCTF-WEB2

BUUCTF-WEB2

[SUCTF 2019]EasySQL1 1.启动靶机 2.寻找注入点和注入方法 随便输入一个字母&#xff0c;没有回显 随便输入一个数字&#xff0c;发现有回显&#xff0c;并且回显结果一样 3.堆叠注入 1; show databases; #查看数据库 1; show tables; #查看数据表 里面有个flag 1;set …
阅读更多...
Three.js和Cesium.js中坐标

Three.js和Cesium.js中坐标

在了解Three.js和Cesium.js前先了解并弄清楚图形学关于空间的基本概念流程&#xff1a; 计算机图形学 图形学中涉及到多个坐标空间&#xff0c;这些空间之间的变换是图形渲染中的核心部分。下面是一些常见的图形学空间及其变换顺序&#xff1a; 对象空间&#xff08;Object Sp…
阅读更多...
【完整指南】如何在Visual Studio Code中轻松运行Llama 3模型？

【完整指南】如何在Visual Studio Code中轻松运行Llama 3模型？

Meta 发布了最新的开源语言模型Llama 3。因为它是开源的&#xff0c;你可以下载这个模型&#xff0c;并在自己的电脑上运行。 我清楚&#xff0c;你可能会想&#xff0c;在个人笔记本上运行一个拥有80亿参数的AI模型似乎只有技术高手才能做到。但别担心&#xff01;这篇文章会…
阅读更多...
MATLAB 运算符

MATLAB 运算符

MATLAB 运算符 运算符是一个符号&#xff0c;告诉编译器执行特定的数学或逻辑操作。MATLAB设计为主要在整个矩阵和数组上运行。因此&#xff0c;MATLAB中的运算符既可以处理标量数据&#xff0c;也可以处理非标量数据。MATLAB允许以下类型的基本运算- 算术运算符 关系运算符…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站