首页 > 其他分享 >2023 CSP-J

2023 CSP-J

时间：2024-01-15 23:01:49浏览次数：26  
标签：10 le cur int 站点 2023 CSP dis

2023 CSP-J

P9748 小苹果（模拟）

题意

\(n\) 个苹果从左到右排成一列，编号为从 \(1\) 到 \(n\)。

每天从左侧第 \(1\) 个苹果开始，每隔 \(2\) 个苹果拿走 \(1\) 个苹果。

求出多少天能拿完所有的苹果，编号为 \(n\) 的苹果是在第几天被拿走。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le n\le 10^9\)。

题解

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
void Solve(void)
{
	int n; cin >> n;
	int ans1 = 0, ans2 = 0;
	while (n != 0)
	{
		ans1++;
		if (n % 3 == 1 && ans2 == 0)
		{
			ans2 = ans1;
		}
		n -= n / 3 + (n % 3 == 0 ? 0 : 1);
	}
	cout << ans1 << " " << ans2 << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}

P9749 公路（贪心，模拟）

题意

公路上一共有 \(n\) 个站点，编号为从 \(1\) 到 \(n\)。其中站点 \(i\) 与站点 \(i + 1\) 的距离为 \(v_i\) 公里。

公路上每个站点都可以加油，编号为 \(i\) 的站点一升油的价格为 \(a_i\) 元，且每个站点只出售整数升的油。

现在要从站点 \(1\) 开车到站点 \(n\)，一开始在站点 \(1\) 且车的油箱是空的。已知车的油箱足够大，可以装下任意多的油，且每升油可以让车前进 \(d\) 公里。问从站点 \(1\) 开到站点 \(n\)，至少要花多少钱加油？

数据规模与约定

对于 \(100\%\) 的数据，\(1 \le n \le 10^5,1 \le d \le 10^5,1 \le v_i \le 10^5,1 \le a_i \le 10^5\)。

题解

一个很重要的性质：假设当前有两个站点 \(x,y\)，\(y\) 站点在 \(x\) 站点后面；要在 \(x\) 站点加 \(k_x\) 升油，单位油价为 \(a_x\)；要在 \(y\) 站点加 \(k_y\) 升油，单位油价为 \(a_y\)。如果 \(a_y \ge a_x\)，那我为什么不在 \(x\) 站点就把这 \(k_y\) 升油买了？

于是我们发现，我们要买油的站点，一定价格是严格单调递减的。然后模拟就可以了。模拟细节详见代码。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e5 + 10;
/*====================*/
int n;
lnt d;
lnt v[N];//从1号站到i号站的距离
lnt a[N];//i号站一升油的价格
/*====================*/
void Solve(void)
{
	do
	{
		cin >> n >> d;
		for (int i = 2; i <= n; ++i)
		{
			cin >> v[i];
		}
		for (int i = 1; i <= n; ++i)
		{
			cin >> a[i];
		}
	} while (false);

	do
	{
		for (int i = 2; i <= n; ++i)
		{
			v[i] += v[i - 1];
		}
	} while (false);

	vector<int>station;//需要到达的站
	do
	{
		for (int i = 1; i < n; ++i)
		{
			if (station.empty())
			{
				station.push_back(i);
			}
			else
			{
				if (a[i] < a[station.back()])
				{
					station.push_back(i);
				}
			}
		}
		station.push_back(n);
	} while (false);

	do
	{
		lnt lastmeter = 0, money = 0;//还能跑多少米，花的钱数
		for (int i = 1; i < station.size(); ++i)
		{
			int cur = station[i - 1];//当前所处的站点编号
			int nxt = station[i + 0];//下一个要到达的站点编号
			lnt dis = v[nxt] - v[cur];//两站相差的距离
			lnt k = max((dis - lastmeter + d - 1) / d, 0ll);//至少要加多少升油
			lastmeter += d * k; money += a[cur] * k;//加油
			lastmeter -= dis;//跑完这一段距离
		}
		cout << money << endl;
	} while (false);
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}

P9750 一元二次方程（模拟）

题意

现在给定一个一元二次方程的系数 \(a, b, c\)，其中 \(a, b, c\) 均为整数且 \(a \neq 0\)。你需要判断一元二次方程 \(a x ^ 2 + bx + c = 0\) 是否有实数解，并按要求的格式输出。

在本题中输出有理数 \(v\) 时须遵循以下规则：

  • 由有理数的定义，存在唯一的两个整数 \(p\) 和 \(q\)，满足 \(q > 0\)，\(\gcd(p, q) = 1\) 且 \(v = \frac pq\)。
  • 若 \(q = 1\)，则输出 {p}，否则输出 {p}/{q}，其中 {n} 代表整数 \(n\) 的值；

对于方程的求解，分两种情况讨论：

  1. 若 \(\Delta = b ^ 2 - 4ac < 0\)，则表明方程无实数解，此时你应当输出 NO；

  2. 否则 \(\Delta \geq 0\)，此时方程有两解（可能相等），记其中较大者为 \(x\)，则：

    1. 若 \(x\) 为有理数，则按有理数的格式输出 \(x\)。

    2. 否则根据上文公式，\(x\) 可以被唯一表示为 \(x = q _ 1 + q _ 2 \sqrt r\) 的形式，其中：\(q _ 1, q _ 2\) 为有理数，且 \(q _ 2 > 0\)\(r\) 为正整数且 \(r > 1\)，且不存在正整数 \(d > 1\) 使 \(d ^ 2 \mid r\)（即 \(r\) 不应是 \(d ^ 2\) 的倍数）；

    此时：

    1. 若 \(q _ 1 \neq 0\)，则按有理数的格式输出 \(q _ 1\)，并再输出一个加号 +；
    2. 否则跳过这一步输出；

    随后：

    1. 若 \(q _ 2 = 1\)，则输出 sqrt({r})；

    2. 否则若 \(q _ 2\) 为整数，则输出 {q2}*sqrt({r})；

    3. 否则若 \(q _ 3 = \frac 1{q _ 2}\) 为整数，则输出 sqrt({r})/{q3}；

    4. 否则可以证明存在唯一整数 \(c, d\) 满足 \(c, d > 1, \gcd(c, d) = 1\) 且 \(q _ 2 = \frac cd\)，此时输出 {c}*sqrt({r})/{d}；

    上述表示中 {n} 代表整数 {n} 的值，详见样例。

    如果方程有实数解，则按要求的格式输出两个实数解中的较大者。否则若方程没有实数解，则输出 NO。

数据规模与约定

对于 \(100\%\) 的数据，\(1 \leq T \leq 5000\)，\(1 \leq M \leq 10 ^ 3\)，\(|a|,|b|,|c| \leq M\)，\(a \neq 0\)。。

题解

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
int gcd(int a, int b)
{
	return b == 0 ? a : gcd(b, a % b);
}
/*====================*/
void Reduction(int& up, int& dw)
{
	if (dw < 0)dw *= -1, up *= -1;
	int d = gcd(abs(up), abs(dw)); up /= d, dw /= d;
}
void Simplification(int& up, int& dw, int& r)
{
	for (int d = 2; d * d <= r; ++d)
	{
		while (r % (d * d) == 0)
		{
			up *= d, r /= d * d;
		}
	}
}
bool PutFraction(int up, int dw)
{
	if (up == 0)
	{
		return false;
	}
	else
	{
		Reduction(up, dw);
		if (dw == 1)
		{
			cout << up;
		}
		else
		{
			cout << up << "/" << dw;
		}
		return true;
	}
}
/*====================*/
void Solve(void)
{
	int a, b, c; cin >> a >> b >> c;

	int delta = b * b - 4 * a * c;

	if (delta < 0)
	{
		cout << "NO";
	}
	else
	{
		int up1 = -b, dw1 = 2 * a; 
		int up2 = 1, dw2 = 2 * abs(a), r = delta; Simplification(up2, dw2, r); 
		if (r == 0)
		{
			if (PutFraction(up1, dw1) == false)
			{
				cout << 0;
			}
		}
		else if (r == 1)
		{
			if (PutFraction(up1 * dw2 + up2 * dw1, dw1 * dw2) == false)
			{
				cout << 0;
			}
		}
		else
		{
			if (PutFraction(up1, dw1) == true)
			{
				cout << "+";
			}
			Reduction(up2, dw2);
			if (up2 == 1 && dw2 == 1)
			{
				cout << "sqrt(" << r << ")";
			}
			else if (dw2 == 1)
			{
				cout << up2 << "*" << "sqrt(" << r << ")";
			}
			else if (up2 == 1)
			{
				cout << "sqrt(" << r << ")" << "/" << dw2;
			}
			else
			{
				cout << up2 << "*" << "sqrt(" << r << ")" << "/" << dw2;
			}
		}
	}
	cout << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; cin >> T;
	int M = 1; cin >> M;
	while (T--)Solve();
	return 0;
}

P9751 旅游巴士（最短路）

题意

给定一张 \(n\) 点 \(m\) 边的有向图，每条边需要花费的时间为 \(1\)。

每条边存在开放时间 \(a_i\)，只有不早于 \(a_i\) 时间到达该条边的起点才能通行。

现在要从 \(1\) 号点到 \(n\) 号点，到达 \(1\) 号点的时间和离开 \(n\) 号点的时间必须是 \(k\) 的倍数，且不允许在点或边上停留。

问最少花费的时间是多少。

数据规模与约定

对于 \(100\%\) 的数据，\(2 \le n \le 10^4 ,1 \le m \le 2*10^4,1 \le k \le 10^2,1 \le u,v \le n,0 \le a_i \le 10^6\)。

题解

首先我们发现，如果提前到达了一条边我们需要等待。而等待时间如果是 \(k\) 的倍数，我们相当于在起点先等待。

而路上花费的时间不一定是 \(k\) 的倍数，所以我们需要对 \(k\) 进行取模来分类讨论。

跑最短路即可。

#include<bits/stdc++.h>
using namespace std;
/*====================*/
#define endl "\n"
/*====================*/
typedef long long lnt;
/*====================*/
const int N = 1e4 + 10;
const int M = 2e4 + 10;
const int K = 1e2 + 10;
/*====================*/
const int INF = 0X3F3F3F3F;
/*====================*/
int n, m, k;
/*====================*/
namespace _Graph
{
	struct Edge
	{
		int u, v, a;
		Edge(int _u = 0, int _v = 0, int _a = 0)
		{
			u = _u, v = _v, a = _a;
		}
		int node(int x)const
		{
			return x == u ? v : u;
		}
	};
	/*====================*/
	int cntedge;
	Edge edge[M];
	vector<int>G[N];
	/*====================*/
	void AddEdge(int u, int v, int a)
	{
		edge[++cntedge] = Edge(u, v, a);
		G[u].push_back(cntedge);
	}
}
/*====================*/
namespace _Dijkstra
{
	using namespace _Graph;
	/*====================*/
	struct Unit
	{
		int v, r, w;
		Unit(int _v = 0, int _r = 0, int _w = 0)
		{
			v = _v, r = _r, w = _w;
		}
		friend bool operator<(const Unit& a, const Unit& b)
		{
			return a.w > b.w;
		}
	};
	/*====================*/
	int dis[N][K]; bool vis[N][K];
	/*====================*/
	void Init(int s, int r)
	{
		memset(dis, INF, sizeof(dis));
		memset(vis, false, sizeof(vis));
		priority_queue<Unit>q;
		q.push(Unit(s, r, dis[s][r] = 0));
		while (!q.empty())
		{
			int cur_v = q.top().v, cur_r = q.top().r; q.pop();
			if (vis[cur_v][cur_r])continue; vis[cur_v][cur_r] = true;
			for (int i = 0; i < G[cur_v].size(); ++i)
			{
				int val = 1 + max(0, (edge[G[cur_v][i]].a - dis[cur_v][cur_r] + k - 1) / k) * k;
				int nxt_v = edge[G[cur_v][i]].node(cur_v), nxt_r = (cur_r + 1) % k;
				if (dis[nxt_v][nxt_r] > dis[cur_v][cur_r] + val)
				{
					dis[nxt_v][nxt_r] = dis[cur_v][cur_r] + val;
					q.push(Unit(nxt_v, nxt_r, dis[nxt_v][nxt_r]));
				}
			}
		}
	}
}
/*====================*/
void Solve(void)
{
	cin >> n >> m >> k;
	for (int i = 1; i <= m; ++i)
	{
		int u, v, a; 
		cin >> u >> v >> a;
		_Graph::AddEdge(u, v, a);
	}
	_Dijkstra::Init(1, 0);
	int ans = _Dijkstra::dis[n][0];
	if (ans == INF)ans = -1;
	cout << ans << endl;
}
/*====================*/
int main()
{
#ifndef ONLINE_JUDGE
	freopen("IN.txt", "r+", stdin);
#endif
	ios::sync_with_stdio(false);
	cin.tie(NULL), cout.tie(NULL);
	int T = 1; //cin >> T;
	while (T--)Solve();
	return 0;
}

标签：10,le,cur,int,站点,2023,CSP,dis
From： https://www.cnblogs.com/ProtectEMmm/p/17966608

相关文章

  • 2019 CSP-J
    2019CSP-JP5660数字游戏（语法）题意给定一个长度最大为\(8\)的01字符串，求字符串中有多少个\(1\)。题解#include<bits/stdc++.h>usingnamespacestd;/*====================*/#defineendl"\n"/*====================*/typedeflonglonglnt;/*===================......
  • 2019 CSP-J 江西
    2019CSP-J江西P5681面积（语法）题意求出边长为\(a\)的正方形与长宽分别为\(b,c\)的矩形哪一个面积更大。题解#include<bits/stdc++.h>usingnamespacestd;/*====================*/#defineendl"\n"/*====================*/typedeflonglonglnt;/*===========......
  • 2020 CSP-J
    P7071优秀的拆分（语法）题意给定一个正整数，输出二进制拆分。如果这个数是奇数输出-1。数据规模与约定对于\(100\%\)的数据，\(1\len\le10^7\)。题解#include<bits/stdc++.h>usingnamespacestd;/*====================*/#defineendl"\n"/*====================*/......
  • 2021 CSP-J
    P7909分糖果（数学）题意给定\(n,l,r\)，求一个数\(x\)，当\(l\lex\ler\)时，最大的\(x\bmodn\)。数据规模与约定对于\(100\%\)的数据，\(1\len\lel\ler\le10^9\)。题解假设\(l=K_l*n+R_l,r=K_r*n+R_r,x=K_x*n+R_x\)。我们要求\(R_x\)尽......
  • 2019 CSP-J
    P5660数字游戏（语法）题意给定一个长度最大为\(8\)的01字符串，求字符串中有多少个\(1\)。题解#include<bits/stdc++.h>usingnamespacestd;/*====================*/#defineendl"\n"/*====================*/typedeflonglonglnt;/*====================*/voidSo......
  • 2023 CSP-J
    P9748小苹果（模拟）题意\(n\)个苹果从左到右排成一列，编号为从\(1\)到\(n\)。每天从左侧第\(1\)个苹果开始，每隔\(2\)个苹果拿走\(1\)个苹果。求出多少天能拿完所有的苹果，编号为\(n\)的苹果是在第几天被拿走。数据规模与约定对于\(100\%\)的数据，\(1\len\le10^9......
  • 2022 CSP-J
    P8813乘方（数学，模拟）题意给定两个数\(a,b\)，如果\(a^b\le10^9\)，输出\(a^b\)的值。否则输出\(-1\)。数据规模与约定对于\(100\%\)的数据，\(1\lea,b\le10^9\)。题解记得开longlong。如果\(a=1\)，那么无论\(b\)是多少结果都是\(1\)。如果\(a\ne1\)，那么\(a......
  • 创新逛展体验！实时云渲染助力2023天河区首届房博会元宇宙
    2023年11月10日-12日，2023广州市天河区首届房博会暨家居家电消费节在体育中心南广场落幕。举办期间，参展的天河区明星楼盘、家居家电品牌大派优惠券，让消费者买得更加爽手。值得一提的是，此次活动除了线下热闹的展会外，还引入了元宇宙概念，市民在11月内通过扫描活动的二维码，就能进行......
  • 全视通2023年度总结大会 | 风雨不改凌云志，长空无崖任搏击
    时间记录坚实的脚步，岁月镌刻奋斗的历程，沉淀来路方可擘画长远。2023年，全视通在智慧医康养领域大放异彩，全视通人奋力争先，取得了显著的成就。1月13日，我们以“风雨不改凌云志，长空无崖任搏击”为主题，在珠海总部报告厅召开了2023年度工作总结大会。珠海总部的员工以及各地的驻外员工跨越......
  • 云原生周刊：OpenTofu 宣布正式发布 ｜ 2023.1.15
    开源项目推荐kubeauditkubeaudit是一个开源项目，旨在帮助用户对其Kubernetes集群进行常见安全控制的审计。该项目提供了工具和检查规则，可以帮助用户发现潜在的安全漏洞和配置问题。ChronosChronos是一款综合性开发人员工具，可监控通过RESTAPI或gRPC通信的容器化（Docker......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99