欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识！
您现在的位置是： 首页

Codeforces Round #615 (Div. 3)

程序员文章站 2022-05-12 23:31:33
...

A

给定四个数 a,b,c,n ,求能不能找到一种方法使得如下等式成立

>fase<
{a+A=b+B=c+CA+B+C=nA≥0B≥0C≥0 \begin{cases} a + A = b + B = c + C\\ A+B+C = n\\ A \geq 0\\ B\geq0\\ C\geq0\\ \end{cases}

数据范围: 1≤a,b,c,n≤1081\leq a, b,c,n\leq10^8

Tutorial: 直接找到abc中最大的数, 然后分n使得a和b和c相等, 然后看剩下的是不是三的倍数

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
#define _rep(n, a, b) for (int n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (int n = (a); n >= (b); --n)
#define _for(n, a, b) for (int n = (a); n < (b); ++n)
#define _rof(n, a, b) for (int n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll maxn = 50 + 5;
int n, m;

signed main()
{
	int t;
	cin >> t;
	_rep(i, 1, t)
	{
		vector<int> a(3);
		cin >> a[0] >> a[1] >> a[2];
		sort(all(a));
		int must = a[2] * 2 - a[0] - a[1];
		int n;
		cin >> n;
		n -= must;
		if (n < 0 || n % 3 != 0)
			cout << "NO" << endl;
		else
			cout << "YES" << endl;
	}
}

B

>fase<

在第一象限内有n个点, 你从原点出发, 每次只能向上走或者向右走, 现要求以任意的顺序访问所有的点, 然后输出每一步的命令, 反之输出no

数据范围 n≤1000n \leq 1000

Tutorial: 初步观察得到所有不行的情况都存在两个点形成的直线的斜率是负数, 于是就可以O(n2)O(n^2)枚举所有的端点判断是能走完, 如果可以走完, 那自然先按照x排序, 然后统一先走右边再走上面;

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
#define _rep(n, a, b) for (int n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (int n = (a); n >= (b); --n)
#define _for(n, a, b) for (int n = (a); n < (b); ++n)
#define _rof(n, a, b) for (int n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll maxn = 50 + 5;
int n, m;

signed main()
{
	int t;
	cin >> t;
	_rep(cas, 1, t)
	{
		int n;
		cin >> n;
		vector<pair<int, int>> q(n);
		for(auto &i:q){
			cin >> i.first >> i.second;
		}
		bool okay = 1;
		_for(i, 0, q.size()){
			_for(j, i+1, q.size()){
				okay &= (((q[i].first - q[j].first) * (q[i].second - q[j].second)) >= 0);
			}
		}
		if(!okay){
			cout << "NO" << endl;
			continue;

		}
		sort(all(q));
		string res;
		pair<int, int> last(0, 0);
		_for(i, 0, q.size()){
			int r = q[i].first - last.first;
			int u = q[i].second	- last.second;
			while(r){
				res += "R";
				r--;
			}
			while(u){
				res += "U";
				u--;
			}
			last = q[i];
		}
		cout << "YES" << endl;
		cout << res << endl;
	}
}

C

>fase<

给定一个数n,n, 问你是否能找到三个不同的数a,b,c,a, b, c,使得

{2≤a,b,ca∗b∗c=n \begin{cases} 2\leq a, b, c\\ a*b*c = n\\ \end{cases}

Tutorial 先用O(n)O(\sqrt{n})找到所有n的因子, 然后暴力判断这些因子中有没有可以分解并且满足条件的答案

多层循环不要想当然用break, goto 才是正道

#include <bits/stdc++.h>
#include <bits/extc++.h>


using namespace std;
#define _rep(n, a, b) for (int n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (int n = (a); n >= (b); --n)
#define _for(n, a, b) for (int n = (a); n < (b); ++n)
#define _rof(n, a, b) for (int n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll maxn = 50 + 5;
int n, m;

signed main()
{
	int t;
	cin >> t;
	_rep(cas, 1, t)
	{
		ll n;
		cin >> n;
		vector<ll> candidates;
		ll ans1, ans2, ans3;
		for (ll i = 2; i * i <= n; i++)
		{
			if (n % i == 0) {
				candidates.emplace_back(i);
				candidates.emplace_back(n / i);
			}
		}
		bool okay = 0;
		for (auto i : candidates) {
			for (ll j = 2; j * j <= i; j++) {
				if (i % j == 0) {


					ans1 = i / j;
					ans2 = j;
					ans3 = n / i;
					if (ans1 != ans2 && ans2 != ans3 && ans1 != ans3 && ans1 * ans2 * ans3 == n) {
						okay = 1;
						goto here;
					}
				}
			}
		}
		here:
		if (okay) {
			cout << "YES" << endl;
			cout << ans1 << " " << ans2 << " " << ans3 << endl;
		}
		else {
			cout << "NO" << endl;
		}
	}
}

D

>fase<

给你一个空的序列, 有q个询问, 每个询问会给你一个数, 并加在序列里面, 你可以把给你的数加上任意倍数的x, 然后输出这个空序列的最小非负整数 , 每次询问输出当前最小的非负整数

数据范围: x≤4×105x \leq 4\times 10^5

Tutorial : 初步观察, 只用维护目前序列中存在的数模上x的个数的数组cnt, 然后在查询该数组中最小的数是m, 是第n个,则答案为 mx+n, 想到是用个平衡树, 结果没写对, 这里用的set动态维护的, 每次增加一个数就找到原来的数据, 然后erase它, 再添加一个新的

本来想到用的, 以为还要用find来定位, 没想到set的自带erase函数有定位的作用, 而且复杂度是log级别的

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
#define _rep(n, a, b) for (int n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (int n = (a); n >= (b); --n)
#define _for(n, a, b) for (int n = (a); n < (b); ++n)
#define _rof(n, a, b) for (int n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll maxn = 50 + 5;
int n, m;

signed main()
{
	int n, q;
	cin >> n >> q;
	vector<int> cnt(q);
	set<pair<int, int>> vals;
	_for(i, 0, q)
	{
		vals.insert(make_pair(0, i));
	}
	_rep(i, 1, n)
	{
		int tmp;
		cin >> tmp;
		tmp %= q;
		vals.erase(make_pair(cnt[tmp], tmp));
		++cnt[tmp];
		vals.insert(make_pair(cnt[tmp], tmp));
		cout << vals.begin()->first * q + vals.begin()->second << endl;
	}
}

E

>fase<

给定一个n×mn\times m的矩阵, 其中填有(1,2,3,⋯ ,n×m)元素(1, 2, 3, \cdots,n\times m)元素, 现有两种操作

  • 将其中任意修改其中的某一个元素
  • 将某一列向上平移一个单位, 最上面的移到最下面

现问最少用多少步, 使得该矩阵变成下图模式:

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-y3X5AE9i-1579972989856)(https://s2.ax1x.com/2020/01/26/1ez9t1.png)]

数据范围: 1≤n,m≤2×105,n×m≤2×1051\leq n, m\leq 2\times10^5, n\times m\leq 2\times10^5

初步观察, 列和列之间是没有关系的, 可以单独算每一列的贡献, 之前做过类似的旋转的问题, 处理方法是把两块儿相同的模式串连起来, 然后进行比对, 针对每个位置比对 然后tle,正确的方法应该是定义一个same[i], 代表将当前列向上平移i个单位后有多少个元素是相同的, 而且每个元素的目标位置都可追溯, 这样mini=1n(n−same[i])min_{i=1}^{n}(n-same[i])就是当前列最小的贡献

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
#define _rep(n, a, b) for (int n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (int n = (a); n >= (b); --n)
#define _for(n, a, b) for (int n = (a); n < (b); ++n)
#define _rof(n, a, b) for (int n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll maxn = 50 + 5;
int n, m;
vector<vector<int>> mat;
int solve(vector<int> & raw, int col){
	vector<int> same(n, 0);
	_rep(i, 1, n){
		if(raw[i] % m != col%m || raw[i] > n*m || raw[i] < col)continue;
		int k = (raw[i] - col) / m + 1;
		same[(i - k + n)%n]++;
	}
	int ret = n;
	_for(i, 0, n){
		ret = min(ret, n - same[i] + i);
	}
	return ret;
}
signed main()
{
	cin >> n >> m;
	mat.assign(m + 1, vector<int>(n + 1, 0));
	_rep(i, 1, n)
	{
		_rep(j, 1, m)
		{
			cin >> mat[j][i];
		}
	}
	int ans = 0;

	_rep(i, 1, m)
	{
		ans += solve(mat[i], i);
	}
	cout << ans << endl;
}

F

给定一棵数, 让你在树中找到三个顶点使得连接这三个顶点的简单路径的边的集合最大

>fase<

数据范围 3≤n≤2×1053\leq n\leq 2\times 10^5

先从任意一个顶点开始搜索, 搜到距离该顶点最远的顶点, 肯定是一条直径的端点, 然后从该端点bfs, 搜到到其他所有点的距离, 再找那个最远的, 然后这个就是直径了, 然后枚举另一个端点使得贡献最大

#include <bits/stdc++.h>
#include <bits/extc++.h>

using namespace std;
#define _rep(n, a, b) for (int n = (a); n <= (b); ++n)
#define _rev(n, a, b) for (int n = (a); n >= (b); --n)
#define _for(n, a, b) for (int n = (a); n < (b); ++n)
#define _rof(n, a, b) for (int n = (a); n > (b); --n)
#define oo 0x3f3f3f3f3f3f
#define ll long long
#define db double
#define eps 1e-8
#define bin(x) cout << bitset<10>(x) << endl;
#define what_is(x) cerr << #x << " is " << x << endl
#define met(a, b) memset(a, b, sizeof(a))
#define all(x) x.begin(), x.end()
#define pii pair<ll, ll>
const ll mod = 1e9 + 7;
const ll maxn = 4e5 + 10;
int n, m; 
struct node
{
	int to, nxt;
} way[maxn];
bool vis[maxn];
int cnt, head[maxn];
void addedge(int from, int to){
	way[++cnt].to = to;
	way[cnt].nxt = head[from];
	head[from] = cnt;
}
int d[maxn];
int bfs(int s){
	int ret = 0;
	queue<int> q;
	met(d, 0);
	met(vis, 0);
	q.push(s);
	while(not q.empty()){
		int cur = q.front();
		q.pop();
		vis[cur] = 1;
		for(int i = head[cur];i;i = way[i].nxt){
			int to = way[i].to;
			if(vis[to])continue;
			ret = to;
			d[to] = d[cur]+1;
			q.push(to);
		}
	}
	return ret;
}
vector<int> from1, from2;
signed main(){
	cin >> n;
	int ans, pos1, pos2, pos3;
	_rep(i, 1, n-1){
		int u, v;
		cin >> u >> v;
		addedge(u, v), addedge(v, u);
	}
	pos1 = bfs(1);
	pos2 = bfs(pos1);
	from1.assign(n+1, 0), from2.assign(n+1, 0);
	_rep(i, 1, n)
		from1[i] = d[i];
	bfs(pos2);
	_rep(i, 1, n)
		from2[i] = d[i];
	int mx = 0;
	_rep(i, 1, n){
		if(i == pos1 || i == pos2)continue;
		if(mx < from1[i] + from2[i]){
			pos3 = i;
			mx = from1[i] + from2[i];
		}
	}
	ans = mx + from1[pos2];
	cout << ans /2 << endl;
	cout << pos1 << " " << pos2 << " " << pos3 << endl;
	

}
}
	pos1 = bfs(1);
	pos2 = bfs(pos1);
	from1.assign(n+1, 0), from2.assign(n+1, 0);
	_rep(i, 1, n)
		from1[i] = d[i];
	bfs(pos2);
	_rep(i, 1, n)
		from2[i] = d[i];
	int mx = 0;
	_rep(i, 1, n){
		if(i == pos1 || i == pos2)continue;
		if(mx < from1[i] + from2[i]){
			pos3 = i;
			mx = from1[i] + from2[i];
		}
	}
	ans = mx + from1[pos2];
	cout << ans /2 << endl;
	cout << pos1 << " " << pos2 << " " << pos3 << endl;
	

}
相关标签： 好题 比赛题解

上一篇： 20200411 T2 画画（数边框涂色正方形个数）

下一篇： 普通文件与迅雷、旋风、快车、RayFile的下载地址转换算法

推荐阅读