526互联

Codeforces Round 918 (Div4）刷题

发布时间 2023-12-31 01:27:46作者: 哲远甄骏
title: Codeforces Round 918 (Div.4)刷题
type: "tags"

Codeforces Round 918 (Div. 4)

A.Odd One Out

// Problem: A. Odd One Out
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/A
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Date:2023-12-28 22:46:47
// Author:hblgzsx
// 借鉴思路：自己
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>


void solve(){
	int a, b, c;
	std::cin >> a >> b >> c;
	if(a == b) std::cout << c << "\n";
	else if(a == c) std::cout << b << "\n";
	else std::cout << a << "\n";
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t = 1; std::cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

B.Not Quite Latin Square

// Problem: B. Not Quite Latin Square
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Date:2023-12-28 22:49:19
// Author:hblgzsx
// 借鉴思路：自己
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>


void solve(){
	int n; std::cin >> n;
	while(n--){
		std::string s;
		for(int i = 0; i < 3; i++){
			std::cin >> s;
			std::vector<int> a(3);
			bool flag = false;
			for(int j = 0; j< 3; j++){
				if(s[j] == '?'){
					flag = true;
				}
				else a[s[j] - 'A'] = 1;
			}
			
			if(flag){
				for(int j = 0; j < 3; j++){
					if(!a[j]){
						std::cout << char(j + 'A') << "\n";
					}
				}
			}
		}
	}
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t = 1;
	while(t--){
		solve();
	}
	return 0;
}

C.Can I Square?

// Problem: C. Can I Square?
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/C
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Date:2023-12-28 22:58:38
// Author:hblgzsx
// 借鉴思路：自己
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
// std::map<long long,int> mp;
// void init(){
	// for(int i = 0; i <= 1e7 + 10; i++){
		// mp[i * i] = 1;
	// }
// }

bool check(long long x){
	long long l = 0, r = 1e9;
	while(l + 1 < r){
		long long mid = (l + r) / 2;
		if(mid * mid <= x) l = mid;
		else{
			r = mid;
		}
	}
	
	// std::cout << l << "\n";
	return (l * l) == x;
	
}
void solve(){
	int n; std::cin >> n;
	std::vector<int> a(n);
	long long sum = 0;
	for(auto &x : a) std::cin >> x, sum += x;
	
	if(check(sum)){
		std::cout << "YES\n";
	}else{
		std::cout << "NO\n";
	}
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t = 1; std::cin >> t;
	// init();
	while(t--){
		solve();
	}
	return 0;
}

D.Unnatural Language Processing

// Problem: D. Unnatural Language Processing
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/D
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Date:2023-12-28 23:13:49
// Author:hblgzsx
// 借鉴思路：自己
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>


void solve(){
	int n; std::cin >> n;
	std::string s; std::cin >> s;
	std::vector<bool> st(5);
	st[0] = 1;
	st[4] = 1;
	//1, 2, 3, 0, 4
	// 01, 010;
	std::string t;
	for(int i = 0; i < n; i++){
		if(i + 3 < n && st[s[i + 3] - 'a'] == 0){
			t += s[i++];
			t += s[i++];
			t += s[i];
			t += '.';
		}
		else if(i + 3 == n){
			t += s[i++];
			t += s[i++];
			t += s[i];
		}
		else if(i + 2 == n){
			t += s[i++];
			t += s[i];
		}
		else{
			t += s[i++];
			t += s[i];
			t += '.';
		}
	}
	std::cout << t << "\n";
}
int main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t = 1; std::cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

E.Romantic Glasses

// Problem: E. Romantic Glasses
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// Date:2023-12-28 23:56:07
// Author:hblgzsx
// 借鉴思路：自己
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
const int N = 2e5 + 10;
// int a[N];
std::vector<int> a(N, 0);
void solve(){
	int n; std::cin >> n;	
	// std::vector<int> a(N, 0);害人不浅
	for(int i = 0; i < n; i++){
		int x; std::cin >> x;
		if(i % 2) x = -x;
		a[i + 1] = a[i] + x;
	}
	//0也要加进去
	std::sort(a.begin(), a.begin() + n + 1);
	for(int i = 0; i < n; i++){
		if(a[i] == a[i + 1]) {
			// puts("YES");
			std::cout << "YES\n";
			return;
		}
	}
	std::cout << "NO\n";
}
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t = 1; std::cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

F.Greetings

// Problem: F. Greetings
// Contest: Codeforces - Codeforces Round 918 (Div. 4)
// URL: https://codeforces.com/contest/1915/problem/F
// Memory Limit: 256 MB
// Time Limit: 5000 ms
// Date:2023-12-29 02:03:20
// Author:hblgzsx
// 借鉴思路：自己
// 
// Powered by CP Editor (https://cpeditor.org)

#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
using PII = std::pair<int,int>;
const int N = 2e5 + 10;	
std::vector<int> t(N);
std::vector<PII> a(N), b(N);
std::vector<int> c(N);
int cnt = 0;
int n;


struct Fenwick
{
	int tree[N]{0};
	// Fenwick(int n = 0): tree(n){}
	
	int lowbit(int x)
	{
		return x & -x;
	}
	void add(int x, int v)
	{
		for(x; x <= N; x += lowbit(x))
		{
			tree[x] += v;
		}
	}
	int sum(int x)
	{
		int ans = 0;
		for(x; x > 0; x-= lowbit(x))
		{
			ans += tree[x];
		}
		return ans;
	}
	
	int rangeSum(int l, int r)
	{
		return sum(r) - sum(l);
	}
	
};

//语法语法，auto a数值传参，auto& a引用地址传参
// 全局可以不传参了。
void solve3(auto &a,int l, int r){
	if(l >= r) return;
	int mid = l + r >> 1;
	solve3(a, l, mid);
	solve3(a, mid + 1, r);
	
	int k = 0, i = l, j = mid + 1;
	while(i <= mid && j <= r){
		if(a[i].y > a[j].y){
			cnt += mid - i + 1;
			t[k++] = a[j++].y;
		}
		else{
			t[k++] = a[i++].y;
		}
	}
	
	while(i <= mid) t[k++] = a[i++].y;
	while(j <= r) t[k++] = a[j++].y;
	for(int i = l, j = 0; i <= r; i++) a[i].y = t[j++];
	
}

void solve1(){
	for(int i = 1; i <= n; i++) b[i] = {a[i].y, i};
	std::sort(b.begin() + 1, b.begin() + n + 1);
	std::vector<int> c(N);
	for(int i = 1; i <= n; i++) c[b[i].y] = i;
	// Fenwick BIT(N); vector<int> 局部声明非常浪费时间
	Fenwick BIT;
	int res = 0;
	for(int i = 1; i <= n; i++)
	{
		BIT.add(c[i], 1);
		res += i - BIT.sum(c[i]);
	}
	std::cout << res << "\n";
}
void solve2(){
	for(int i = 1; i <= n; i++) b[i] = {a[i].y, i};
	std::sort(b.begin() + 1, b.begin() + n + 1);
	for(int i = 1; i <= n; i++) c[b[i].y] = i;
	Fenwick BIT;
	int res = 0;
	for(int i = n; i ; i--)
	{
		BIT.add(c[i], 1);
		res += BIT.sum(c[i] - 1);
	}
	std::cout << res << "\n";
}


void solve(){
	std::cin >> n;
	for(int i = 1; i <= n; i++){
		std::cin >> a[i].x >> a[i].y;
	}
	sort(a.begin() + 1, a.begin() + n + 1);
	
	
	
	
	
	// 方法1
	// 离散化 + 树状数组1
	// solve1();
	
	// 方法2
	// 离散化 + 树状数组2
	solve2();
	
	// 方法3
	// cnt = 0;
	// 归并排序
	// solve3(a, 1, n);
	// std::cout << cnt << "\n";
}
signed main(){
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	int t = 1; std::cin >> t;
	while(t--){
		solve();
	}
	return 0;
}

G.Bicycles（待补）