[C++知识库] Codeforces Round #773 (Div. 2)（A-C）（multiset应用）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> C++知识库 -> Codeforces Round #773 (Div. 2)（A-C）（multiset应用） -> 正文阅读

[C++知识库]Codeforces Round #773 (Div. 2)（A-C）（multiset应用）

Problem - A - Codeforces

当所有点的y坐标都不一样的时候，可以满足题意，当有两个点的y坐标相同时，如果另一个点y坐标在其上方则满足题意，否则不满足，输出两个点之间的距离

AC代码：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast")
// #include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <numeric>
#include <functional>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
// using i64 = long long;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
typedef long long i64;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	vector<pair<int, int>> a(5);
	for (int i = 1; i <= 3; i++) {
		cin >> a[i].first >> a[i].second;
	}
	if (a[1].second == a[2].second) {
		if (a[3].second < a[1].second) {
			cout << max(a[1].first, a[2].first) - min(a[1].first, a[2].first) << endl;
		}
		else {
			cout << 0 << endl;
		}
	}
	else if (a[1].second == a[3].second) {
		if (a[2].second < a[1].second) {
			cout << max(a[1].first, a[3].first) - min(a[1].first, a[3].first) << endl;
		}
		else {
			cout << 0 << endl;
		}
	}
	else if (a[2].second == a[3].second) {
		if (a[1].second < a[2].second) {
			cout << max(a[2].first, a[3].first) - min(a[2].first, a[3].first) << endl;
		}
		else {
			cout << 0 << endl;
		}
	}
	else {
		cout << 0 << endl;
	}
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

Problem - B - Codeforces

当某个数出现次数是1的时候，只要往外拿结果不变，只有当某个数出现次数大于1，当它往外拿的时候，对应的个数就会+1

AC代码：

/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/
// #pragma GCC optimize(2)
// #pragma GCC optimize(3)
// #pragma GCC optimize("Ofast")
// #include<bits/stdc++.h>
#include <iostream>
#include <cstdio>
#include <queue>
#include <deque>
#include <stack>
#include <string>
#include <cstring>
#include <numeric>
#include <functional>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <cmath>
#include <iomanip>
using namespace std;
// using i64 = long long;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
typedef long long i64;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}

void solve() {
	int n;
	cin >> n;
	map<int, int> mp;
	for (int i = 0; i < n; i++) {
		int x;
		cin >> x;
		mp[x]++;
	}
	int cnt = mp.size();
	for (int i = 1; i <= n; i++) {
		cout << max(i, cnt) << " \n"[i == n];
	}
	return;
}
int main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}
/*

*/

Problem - C - Codeforces

multiset应用，c++语言中，multiset是<set>库中一个非常有用的类型，它可以看成一个序列，插入一个数，删除一个数都能够在O(logn)的时间内完成，而且他能时刻保证序列中的数是有序的，而且序列中可以存在重复的数。该题把题意读懂就好了，根据贪心，先对序列进行从小到大排序，这样前面的数*x后一定会得到后面的数，就不用再回来浪费时间了

AC代码：

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
// #include <iostream>
// #include <cstdio>
// #include <queue>
// #include <deque>
// #include <stack>
// #include <string>
// #include <cstring>
// #include <numeric>
// #include <functional>
// #include <cstdlib>
// #include <vector>
// #include <set>
// #include <map>
// #include <algorithm>
// #include <cmath>
// #include <iomanip>
using namespace std;
// using i64 = long long;
#define lowbit(x) ((x) & -(x))
#define endl '\n'
#define IOS1 ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
#define IOS2 ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
typedef vector<int> vi;
typedef vector<long long> vll;
typedef vector<char> vc;
typedef long long ll;
typedef long long i64;
template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
template<class T>
T power1(T a, int b) {
	T res = 1;
	for (; b; b >>= 1, a = a * a) {
		if (b & 1) {
			res = res * a;
		}
	}
	return res;
}
template<class T>
T power2(T a, int b, T c) {
	T res = 1;
	for (; b; b >>= 1, a = a * a % c) {
		if (b & 1) {
			res = res * a % c;
		}
	}
	return res;
}
template <typename T>
T Myabs(T a) {
	return a >= 0 ? a : -a;
}
template <typename T>
inline void read(T& x)
{
	x = 0; int f = 1; char ch = getchar();
	while (!isdigit(ch)) { if (ch == '-') f = -1; ch = getchar(); }
	while (isdigit(ch)) { x = x * 10 + ch - '0', ch = getchar(); }
	x *= f;
}
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
// const int mod = 998244353;
const double PI = acos(-1.0);
const double eps = 1e-6;
inline int sgn(double x) {
	return x < -eps ? -1 : x > eps;
}
/*
Tips:
   1.int? long long?
   2.don't submit wrong answer
   3.figure out logic first, then start writing please
   4.know about the range
   5.check if you have to input t or not
   6.modulo of negative numbers is not a%b, it is a%b + abs(b)
*/

void solve() {
	int n, x;
	cin >> n >> x;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	multiset<int> s;
	sort(a.begin(), a.end());
	for (auto v : a) {
		if (v % x == 0 && s.find(v / x) != s.end()) {
			s.erase(s.find(v / x));
		}
		else {
			s.insert(v);
		}
	}
	cout << s.size() << endl;
	return;
}
signed main() {
	IOS1;
	//IOS2;
	int __t = 1;
	cin >> __t;
	for (int _t = 1; _t <= __t; _t++) {
		solve();
	}
	return 0;
}

multiset: