首页 > 其他分享 >Codeforces Round #790 (Div.4) A-H2题解

Codeforces Round #790 (Div.4) A-H2题解

时间：2022-11-23 16:03:53浏览次数：45  
标签：return 790 H2 题解 ll long int while solve

原题链接：

https://codeforces.com/contest/1676

A. Lucky?

题意：给定长度为6由数字组成的字符串问前三个数字的和是否等后三个数字的和。

题解：直接相加比较即可。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
void solve()
{
	string s;
	cin >> s;
	if (s[0] + s[1] + s[2] == s[3] + s[4] + s[5])
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

B. Equal Candies

题意：每个盒子有一定数量的糖果，问让每个盒子糖果数量一样要吃掉多少糖果。

题解：很明显每个盒子糖果数量是由糖果数最少的决定的，只要记录一下最小值计算一下即可。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n, a[N];
void solve()
{
	ll ans = 0, mi = INT_MAX;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i], mi = min(mi, a[i]), ans += a[i];
	//ans记录所有糖果的数量
	cout << ans - mi * n << endl;
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

C. Most Similar Words

题意：给定一系列长度为n的字符串，找到difference最小的一对字符串，输出它们的difference值。

difference值为每个字符的差距值，如a和b的差距值为1。

题解：范围不大，暴力枚举每一对字符串，记录差距值最小即可。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n;
string str[N];
void solve()
{
	ll res, k, mi = INT_MAX;
	cin >> n >> k;
	for (int i = 1; i <= n; i++) cin >> str[i];
	for (int i = 1; i <= n; i++)
	{
		for (int j = i + 1; j <= n; j++)
		{
			res = 0;
			for (int x = 0; x < k; x++)
			{
				res += abs(str[i][x] - str[j][x]);
			}
			mi = min(mi, res);
		}
	}
	cout << mi << endl;
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

D. X-Sum

题意：给定一个矩阵，每个位置有一个值，你可以在某个位置(x,y)放置一个棋子，棋子取得的值为四个斜对角方向的所有值（如图），问这个值最大是多少。

image

题解：没什么好思考的，直接暴力枚举

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n, m, mp[500][500];
void solve()
{
	ll ans = 0, k, res;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			cin >> mp[i][j];
		}
	}
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			res = mp[i][j], k = 1;
			while (i - k >= 1 && j - k >= 1)
			{
				res += mp[i - k][j - k];
				k++;
			}
			k = 1;
			while (i + k <= n && j + k <= m)
			{
				res += mp[i + k][j + k];
				k++;
			}
			k = 1;
			while (i + k <= n && j - k >= 1)
			{
				res += mp[i + k][j - k];
				k++;
			}
			k = 1;
			while (i - k >= 1 && j + k <= m)
			{
				res += mp[i - k][j + k];
				k++;
			}
			ans = max(ans, res);
		}
	}
	cout << ans << endl;
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

E. Eating Queries

题意：每个糖果有个甜度，多组询问达到k个甜度至少要吃多少个糖果。

题解：对甜度降序排序，求一下前缀和，然后二分即可。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
bool cmp(ll x, ll y) { return x > y; }
ll n, m, a[N], sum[N];
void solve()
{
	ll k;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
	}
	sort(a + 1, a + n + 1, cmp);
	for (int i = 1; i <= n; i++)
	{
		sum[i] = sum[i - 1] + a[i];
	}
	while (m--)
	{
		cin >> k;
		if (sum[n] >= k)
			cout << lower_bound(sum + 1, sum + n + 1, k) - sum << endl;
		else
			cout << -1 << endl;
	}
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

F. Longest Strike

题意：给定一个数组，求最长的连续的片段且每个数的个数大于k。

题解：map记录个数，去重后循环一遍，按连续片段枚举，记录答案即可,留意一下细节。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n, a[N];
void solve()
{
	pair<ll, ll> cnt;
	map<ll, ll> p;
	set<ll> st;
	ll k;
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i];
		p[a[i]] ++;
	}
	sort(a + 1, a + n + 1);
	int r = unique(a + 1, a + n + 1) - a;
	cnt.first = -1;
	for (int i = 1; i < r; i++)
	{
		if (st.count(a[i]) || p[a[i]] < k) continue;
		int j = 0;
		while(p[a[i] + j] >= k)
		{
			st.insert(a[i] + j);
			j++;
		}
		if (j > cnt.second)
		{
			cnt.first = i;
			cnt.second = j;
		}
	}
	if (cnt.first != -1)
	{
		cout << a[cnt.first] << " " << a[cnt.first] + cnt.second - 1 << endl;
	}
	else
	{
		cout << -1 << endl;
	}
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

G. White-Black Balanced Subtrees

题意：给定一个树，每个节点是黑色或者白色，问有多少个子树黑色节点数量和白色节点数量一样。

题解：拓扑排序，根据入度从下往上dfs，每次判断一下黑色节点的数量和白色节点的数量是否相同即可。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n, m, rd[4010], f[4010];
string s;
vector<ll> v[4010];
pair<ll, ll> c[4010];
void dfs()
{
	for (int p = 1; p <= n; p++)
	{
		for (int i = 1; i <= n; i++)
		{
			if (rd[i] == 0 && f[i] == 0)
			{
				f[i] = 1;
				if (c[i].first == c[i].second)
				{
					m++;//存储答案
				}
				//更新父节点的值
				for (int j = 0; j < v[i].size(); j++)
				{
					c[v[i][j]].first += c[i].first;
					c[v[i][j]].second += c[i].second;
					rd[v[i][j]] --;
				}
			}
		}
	}
}
void solve()
{
	memset(rd, 0, sizeof rd);
	memset(f, 0, sizeof f);
	memset(c, 0, sizeof c);
	m = 0;
	ll ans = 0, k;
	cin >> n;
	for (int i = 1; i <= n; i++) v[i].clear();
	for (int i = 1; i < n; i++)
	{
		cin >> k;
		v[i + 1].push_back(k);
		rd[k] ++;
	}
	cin >> s;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'W')
		{
			c[i + 1].first++;
		}
		else
		{
			c[i + 1].second++;
		}
	}
	dfs();
	cout << m << endl;
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

H1. Maximum Crossings (Easy Version)

题意：从1到n每个点都与下面另一个点存在一条边，求交点个数。

image

题解：考虑一下存在交点的情况。对于两条线段（x1, y1）、(x2, y2),存在交点的情况即x2 >= x1 && y2 <= y1 或者 x2 <= x1 && y2 >= y1。对于每条线段x是单调递增的，即x[n] > x[n - 1]恒成立，那么对于每一个x[n]只需要判断前面有多少线段满足y[n] <= y[n - 1]即可。H1范围比较小可以直接暴力来做。我是每次枚举线段时按y值排序，这样就能二分直接找到满足条件的个数，想着一次性把H1和H2过了，但是还是过不了H2，白搞。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10;
ll n;
pair<ll, ll> a[200010];
void solve()
{
	vector<ll> v;
	ll ans = 0, pos;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i].second;
		a[i].first = i;
	}
	for (int i = 1; i <= n; i++)
	{
		if (i != 1)
		{
			pos = lower_bound(v.begin(), v.end(), a[i].second) - v.begin();
			if (pos < v.size() && v[pos] >= a[i].second) ans += v.size() - pos;
		}
		v.push_back(a[i].second);
		sort(v.begin(), v.end());
	}
	cout << ans << endl;
}
int main()
{
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

H2. Maximum Crossings (Hard Version)

题意：从1到n每个点都与下面另一个点存在一条边，求交点个数。（n的范围从上题的1e3变成了2e5）

题解：其实把问题转化一下就简单了，我们先按y值排序后就是求前面有多少个x的值小于当前这个x，等价于求逆序对的问题，直接套求逆序对lowbit版本，就搞定了。

#include<bits/stdc++.h>
typedef long long int ll;
using namespace std;
const int N = 2e5 + 10；
bool cmp1(pair<ll, ll> x, pair<ll, ll> y) { return (x.second != y.second)? x.second < y.second : x.first > y.first; }
#define lowbit(x) x & -x
ll n, m, c[N];
pair<ll, ll> a[200010];
void modify(ll x, ll d) {
	for (int i = x; i <= n; i += lowbit(i)) c[i] += d;
}
ll getsum(ll x) {
	ll sum = 0;
	for (int i = x; i >= 1; i -= lowbit(i)) sum += c[i];
	return sum;
}
void solve()
{
	memset(c, 0, sizeof c);
	vector<ll> v;
	ll ans = 0;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> a[i].second;
		a[i].first = i;
	}
	sort(a + 1, a + n + 1, cmp1);
	for (int i = 1; i <= n; i++)
	{
		v.push_back(a[i].first);
	}
	for (int i = 0; i < v.size(); i++) {
		ans += getsum(n) - getsum(v[i]);
		modify(v[i], 1);
	}
	cout << ans << endl;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll t;
	cin >> t;
	while (t--)
	{
		solve();
	}
	return 0;
}

标签：return,790,H2,题解,ll,long,int,while,solve
From： https://www.cnblogs.com/wockcow/p/16918561.html

相关文章

  • 题解 LGP2607【[ZJOI2008] 骑士】
    problem基环树森林带权最大独立集。\(n\leq10^6\)。solution0这里先解释一下基环树森林，它就是一个\(n\)个点\(n\)条边的森林，同时是一个荒漠。我们拿出其中一棵连......
  • Codeforces Round #835 (Div.4) A-G题解
    原题链接：https://codeforces.com/contest/1744A.MediumNumber题意：给定三个数，求中间那个数（倒数第二小or倒数第二大）。题解：直接用数组存，sort一下输出中间的数即可。#in......
  • 题解 LGP7489【「Stoi2031」手写的从前】
    problem令\(f_0(S)=\dfrac{\sigma(S)}{\pi(S)}\)，\(f_k(S)=\sum\limits_{T\subseteqS}f_{k-1}(T)\)。其中\(\sigma(S)=\sum\limits_{x\inS}x\)为\(S\)中所有元素......
  • 【题解】P2303 [SDOI2012] Longge 的问题
    【题解】P2303[SDOI2012]Longge的问题题目链接求\(\displaystyle\sum_{i=1}^n\gcd(i,n)\)将这个柿子展开变复杂，得到\[\displaystyle\sum_{i=1}^{n}\sum_{d\mid......
  • P2819 图的m着色问题 C++ 详细题解
    题目背景给定无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。图......
  • P1002 过河卒 详细题解 搜索回溯+递归 [NOIP2002 普及组]
    题目描述棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方......
  • Could not get a resource from the pool 问题解决
    Couldnotgetaresourcefromthepool问题解决今天测试项目的时候，界面提示Couldnotgetaresourcefromthepool 报错信息。登录后台，查询对应的java报错日志报......
  • 奇怪的主席树题 题解
    前言前置知识：可持久化线段树，字符串hash，线段树二分。Description给你一棵\(n\)个点以\(1\)为根节点的树，每一个节点都代表一个\(m\)个字符的字符串。每一个节点......
  • YACS 2022年11月月赛 乙组 T1 数对统计 题解
    好久没更了，闲话一句，我的初赛成绩只有$71.5$，$76$才能进$NOIP$，所以就更一篇吧首先先考虑暴力算法，枚举两个数，设这两个数为$x$和$y$，如果$f[x][y]=false$，那就标记为$t......
  • Vscode/Sublime C++ 打印中文乱码问题解决
    #include<iostream>usingnamespacestd;#ifdef_WIN32#include<windows.h>#endifintmain(){#ifdef_WIN32//控制台显示乱码纠正SetConsoleOutp......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99