首页 > 其他分享 >第一场排位赛题解

第一场排位赛题解

时间：2022-09-01 16:14:18浏览次数：67  
标签：const int 排位赛 ans cin long 第一场 题解 INF

总结

阅读能力需要加强
这场的题除了最后一题图论建议都补了

A - Wilbur and Swimming Pool

在一个二维平面中有一个四边平行于坐标轴的矩形，给出\(1 - 4\)个坐标，分别对应矩形的\(1 - 4\)个顶点，求矩形的面积是多少；若面积无法确定则输出\(-1\)。

由于矩形四边平行于坐标轴，因此在所有坐标中取\(x\)与\(y\)的最值，相减再相乘得出矩形面积
若面积为\(0\)，则说明这些点围成的图形是一个点或者一条直线，输出\(-1\)即可
为什么那么多人写模拟

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
int main()
{
	int n;
	cin >> n;
	int mxx = -INF, mxy = -INF;
	int mnx = INF, mny = INF;
	while (n--) {
		int x, y;
		cin >> x >> y;
		mxx = max(mxx, x);
		mxy = max(mxy, y);
		mnx = min(mnx, x);
		mny = min(mny, y);
	}
	int ans = (mxx - mnx) * (mxy - mny);
	if (!ans) ans = -1;
	cout << ans;
	return 0;
}

B - Increasing Matrix

给出一个\(n*m\)的矩阵，你可以修改值为\(0\)的元素，使每行每列都构成严格递增的序列，并且让所有元素之和尽可能大，无法构造则输出\(-1\)。
矩阵的第一列和最后一列，以及第一行和最后一行都不会出现\(0\)

题目求最大的元素值之和，实际上在每个严格递增序列中就是要让每个数都尽可能大。
由于最后一列与最后一行都不会出现0，因此限制了每个序列的尾项。
可以发现要使元素尽量大，取值就只会被它右边或者下边的元素影响，因此我们可以从右下角逆推回去，取值为 $$min(a[x + 1][y], a[x][y + 1]) – 1$$即可满足题目条件
最后检查一遍每个序列是否符合题目要求即可，时间复杂度\(O(n*m)\)

#include <bits/stdc++.h>
using namespace std;
const int N = 550;
int a[N][N];
int main()
{
	int n, m;
	long long ans = 0;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> a[i][j], ans += a[i][j];
	for (int i = n - 1; i > 1; i--)
		for (int j = m - 1; j > 1; j--)
			if (!a[i][j]) a[i][j] = min(a[i + 1][j], a[i][j + 1]) - 1, ans += a[i][j];
	for (int i = 1; i <= n; i++)
		for (int j = 2; j <= m; j++)
			if (a[i][j - 1] >= a[i][j]) return cout << "-1", 0;
	for (int j = 1; j <= m; j++)
		for (int i = 2; i <= n; i++)
			if (a[i - 1][j] >= a[i][j]) return cout << "-1", 0;
	cout << ans;
	return 0;
}

C - Mishka and the Last Exam

给定整数\(n\)与长度为\(n/2\)的数组\(b\)，构造出一个非递减的序列\(a\)满足\(b[i] = a[i] + a[n – i + 1]\)

贪心地构造数组\(a\)，让左半部分的数尽量小，右半部分的数尽量大
先令当前左半部分的数等于它前一个数，即可得到右半部分对应的数
若此数大于后一个数，则令这个数等于后一个数，同时调整左半部分对应的数即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 2e18;
const int N = 4e5 + 10;
ll a[N], b[N];
int main()
{
	int n;
	cin >> n; n /= 2;
	for (int i = 1; i <= n; i++) cin >> b[i];
	a[2 * n + 1] = INF;
	for (int i = 2 * n, j = 1; j <= n; i--, j++) {
		a[i] = b[j] - (a[j] = a[j - 1]);
		if (a[i] > a[i + 1]) a[j] = b[j] - (a[i] = a[i + 1]);
	}
	for (int i = 2; i <= 2 * n; i++)
		if (a[i - 1] > a[i]) return cout << -1, 0;
	for (int i = 1; i <= 2 * n; i++)
		cout << a[i] << ' ';
	return 0;
}

D - Meme Problem

给出整数d，构造两个浮点数\(a\)和\(b\)满足 \(a + b = d\) 并且 \(a * b = d\)

两个方程两个未知数，代入即可得到一元二次方程 \(a * (d – a) = d\)，利用求根公式即可。注意特判\(0\)和无解的情况。
也可以用二分嗯写

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void solve()
{
	double d;
	cin >> d;
	if (fabs(d) < 1e-8) 
		return puts("Y 0.000000000 0.000000000"), void();
	if (d < 4) 
		return puts("N"), void();
	double a = (d - sqrt(d * d - 4 * d)) / 2;
	double b = d - a;
	printf("Y %.9f %.9f\n", a, b);
}
int main()
{
	int t;
	cin >> t;
	while (t--) solve();
	return 0;
}

E - Ehab and a 2-operation task

给出\(n\)个元素的序列，可以对此序列进行如下操作：
\(1\) 对序列前缀加上一个任意数
\(2\) 对序列前缀取任意模数
求进行不超过\(n + 1\)次操作之后能构成一个严格递增序列的操作序列

\(n + 1\)次操作可以说是很大的提示
由于每次都是对一个前缀进行操作，我们自然可以想到从后往前操作
我们可以给该序列定义任意一个大于\(n\)的模数\(mod\)
在此简化剩余系中，加法可以将当前数变化为任意一个数
因此从后往前对于序列每个前缀进行\(1\)操作之后，再整体取一次模即可

#include <bits/stdc++.h>
using namespace std;
const int N = 2e3 + 10;
const int mod = 2e5;
int a[N];
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int m = mod - a[n] - 1;
	printf("%d\n1 %d %d\n", n + 1, n, m);
	for (int i = n - 1, j = mod - 2; i >= 1; i--, j--)
	{
		int v = (j - (a[i] + m) % mod + mod) % mod;
		printf("1 %d %d\n", i, v);
		m = (m + v) % mod;
	}
	printf("2 %d %d\n", n, mod);
	return 0;
}

F - Balanced Ternary String

给出一个只包含\(0,1,2\)的字符串，长度保证为\(3\)的倍数，在一次操作中你可以修改任意一个字符，最终得到\(0,1,2\)这三种字符出现次数相同的字符串，在保证修改次数最少的情况下，求字典序最小的结果

易知题目要让\(0,1,2\)三种字符的数量都等于\(n/3\)
可以对三种字符都开一个双端队列

  • 若字符\(0\)达不到需求，可以在另外两种字符中选出一个最前的位置进行修改
  • 若字符\(2\)达不到需求，可以在另外两种字符中选出一个最后的位置进行修改
  • 若字符\(1\)达不到需求，先看字符\(2\)有没有多出，有的话选择最前的一个\(2\)进行修改，否则选择最后的一个\(0\)进行修改
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
const int INF = 1e9;
char s[N];
deque<int> q[3];
int main()
{
	int n;
	scanf("%d%s", &n, s + 1);
	for (int i = 1; i <= n; i++) q[s[i] - '0'].push_back(i);
	int cnt = n / 3;
	for (int i = q[0].size(); i < cnt; i++) {
		int u = q[1].size() > cnt ? q[1].front() : INF;
		int v = q[2].size() > cnt ? q[2].front() : INF;
		if (u < v) s[u] = '0', q[1].pop_front();
		else s[v] = '0', q[2].pop_front();
	}
	for (int i = q[2].size(); i < cnt; i++) {
		int u = q[0].size() > cnt ? q[0].back() : 0;
		int v = q[1].size() > cnt ? q[1].back() : 0;
		if (u > v) s[u] = '2', q[0].pop_back();
		else s[v] = '2', q[1].pop_back();
	}
	for (int i = q[1].size(); i < cnt; i++) {
		if (q[2].size() > cnt) s[q[2].front()] = '1', q[2].pop_front();
		else s[q[0].back()] = '1', q[0].pop_back();
	}
	printf("%s", s + 1);
	return 0;
}

G - Hard Process

给出一个01序列，在一次操作中你可以把0变成1，最多进行k次，求进行操作后最长的全1子串长度

尺取法（没见过可以去了解一下）
可以利用双指针，每次都取得修改k个0能取得的最长全1子串的长度
时间复杂度\(O(n)\)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 3e5 + 10;
int a[N];
int main()
{
	int n, k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> a[i];
	int L = 1, R = 1, cnt = 0, ansL = 0, ansR = 0, ans = 0;
	while (L <= n && R <= n) {
		// 在 L 确定的情况下，移动 R 指针到最右的位置
		while (R <= n && (a[R] == 1 || cnt < k)) cnt += !a[R++];
		if (R - L > ans) ansL = L, ansR = R, ans = R - L;
		while (a[L] == 1) L++;
		L++, cnt--;
	}
	cout << ans << '\n';
	for (int i = 1; i <= n; i++) {
		if (i >= ansL && i < ansR) cout << "1 ";
		else cout << a[i] << ' ';
	}
	return 0;
}

H - Fight Against Traffic

给出一个\(n\)个点\(m\)条边的无向连通图，要求再加一条无向边，保证加边之后无重边自环，且\(s\)到\(t\)的最短路长度不变，求有多少种加边方案。

\(n\)只有1000，考虑\(O(n^2)\)的做法
直接用两次dijkstra跑出\(s\)与\(t\)的最短路\(ds\)与\(dt\)
然后双重循环枚举每两个点\(u\)与\(v\)
首先判断是否原来就存在边，这个用map就可以解决
只需满足$$min(ds[u] + dt[v] + 1, ds[v] + dt[u] + 1) >= ds[t]$$
即可计入答案

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 1010, M = 2010, INF = 1e9;
int h[N], e[M], ne[M], idx;
int ds[N], dt[N];
int n, m, s, t;

void add(int a, int b)
{
	e[++idx] = b, ne[idx] = h[a], h[a] = idx;
}
void dij(int d[], int s)
{
	vector<int> v(n + 1);
	for (int i = 1; i <= n; i++) d[i] = INF;
	d[s] = 0;
	priority_queue<PII> q;
	q.push(make_pair(1, s));
	while (q.size()) {
		int x = q.top().second; q.pop();
		if (v[x]) continue;
		v[x] = 1;
		for (int i = h[x]; i; i = ne[i]) {
			int u = e[i];
			if (d[u] > d[x] + 1) {
				d[u] = d[x] + 1;
				q.push(make_pair(-d[u], u));
			}
		}
	}
}
int main()
{
	cin >> n >> m >> s >> t;
	map<PII, bool> mp;
	while (m--) {
		int u, v;
		cin >> u >> v;
		add(u, v); add(v, u);
		if (u > v) swap(u, v);
		mp[PII(u, v)] = 1;
	}
	dij(ds, s), dij(dt, t);
	int ans = 0;
	for (int i = 1; i < n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (mp.count(PII(i, j))) continue;
			if (min(ds[i] + dt[j] + 1, ds[j] + dt[i] + 1) >= ds[t]) ans++;
		}
	}
	cout << ans;
	return 0;
}

标签：const,int,排位赛,ans,cin,long,第一场,题解,INF
From： https://www.cnblogs.com/bous/p/16646831.html

相关文章

  • 题解 UVA1343 The Rotation Game
    题解区都是\(\text{IDA*}\)，实际上这题\(\text{A*}\)也可以，代码也很简单。Solution首先由于整个棋盘的形状是已知的，所以我们可以先处理出\(\text{A~H}\)操作对应行列......
  • CF1722G 题解
    题目构造一个长度为\(n\)的数列，数列中每个数各不相同且都不超过\(2^{31}\)，使得奇数项和偶数项的异或和相等。思路我提供一种比较神奇的构造方法。首先，两个数相等可......
  • CF351B Jeff and Furik 题解
    CF351BJeffandFurik有一个长度为n的排列p,Jeff每次操作选两个相邻元素交换，Furik每次操作随机执行下列操作之一：1.对于所有p[i]<p[i+1],随机取一对p[i]与p[i+1]交换2.......
  • onenote突然无法同步，同步报错以及创建笔记本都报错问题解决
    同步报错：OneNote当前无法同步笔记。将继续尝试。(错误代码:0x80004005bdf5j)创建笔记本报错：OneNote无法在以下位置新建笔记本打开笔记本报错：无法打开笔记本无法打开......
  • hzx的CSP-J模拟赛题解
    T1按题意模拟即可，注意不用考虑闰年。T2\(30\%\)的数据：使用\(Floyd\)求出图的全源最短路，时间复杂度\(O(n^3)\)。\(50\%\)的数据：对图上每个点使用\(Dijkstra\)求......
  • P1004 [NOIP2000 提高组] 方格取数 题解
    [NOIP2000提高组]方格取数题目描述设有\(N\timesN\)的方格图\((N\le9)\)，我们将其中的某些方格中填入正整数，而其他的方格中则放入数字\(0\)。如下图所示（见样例）:......
  • iOS自动化真机测试验证环境过程中常见问题解析
    ⬇️点击“下方链接”，提升测试核心竞争力！>>更多技术文章分享和免费资料领取本章节主要讲解iOS自动化真机配置以及在iOS真机执行自动化时常见问题与解决方法。真机使......
  • LG3565 [POI2014]HOT-Hotels 题解
    P3565[POI2014]HOT-Hotels给定一棵树，在树上选\(3\)个点，要求两两距离相等，求方案数。原题数据范围\(n\leq5000\)，可做到线性，空间\(62.5\text{MB}\)。sub1\(n\leq......
  • vue中render中src不生效问题解决
    在vue文件中写html代码的话可以直接用<imgsrc="xxx"/>但是在render中就不能正常工作。原理度娘上有，那render中要使用的话需要加requirerender<imgsrc={required(......
  • luoguP8085 [COCI2011-2012#4] KRIPTOGRAM 题解（KMP）
    /*给定明文和密文，密文与明文的某个字串格式相同，找出密文出现的最早位置。如：明文aaabcdabc 密文xy ans：3解：容易想到KMP算法。可以发现，密文和对应子串的格式相同......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99