当前位置：首页 > news >正文

Codeforces Round #822 (Div. 2) 补题（A、B、C）

news 来源：原创 2024/5/19 20:21:34

Codeforces Round #822 Div. 2

- A - Select Three Sticks （800）
- B - Bright, Nice, Brilliant （800）
- C - Removing Smallest Multiples （1200）
- D Slime Escape

参考的大佬的题解

A - Select Three Sticks （800）

简单思维，一看数据范围直接三重循环（要是省赛有这么松的数据范围就好了）

#include<bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 1e5 + 10;

int n, T;
int a[N];

signed main()
{
	cin>>T;
	while(T -- ){
		cin>>n;
		int ans = 1e9;
		map<int, int>mp;
		int f = 0;   
		for(int i = 1; i <= n; i ++ ){
			cin>>a[i];
			mp[a[i]] ++ ;
			f = max(f, mp[a[i]]);
		}
		
		if(f >= 3){
			cout<<0<<endl;
		}
		else{
			for(int i = 1; i <= n; i ++ ){
				for(int j = 1; j <= n; j ++ ){
					for(int k = 1; k <= n; k ++ ){
						if(i != j && j != k && k != i){
							ans = min(ans, abs(a[i] - a[j]) + abs(a[k] - a[i]));
						}
					}
				}
			}
			cout<<ans<<endl;
		}
	}
	return 0;
}

B - Bright, Nice, Brilliant （800）

简单思维，要认清能到达一个房间的房间都有那些，之后发现只有塔的两侧亮了才符合要求

#include<bits/stdc++.h>

using namespace std;

const int N = 610;

int n, m;
int a[N][N];
int T;

int main()
{
	cin>>T;
	while(T -- ){
		cin>>n;
		for(int i = 1; i <= n; i ++ ){
			for(int j = 1; j <= i; j ++ ){
				if(j == 1) a[i][j] = 1;
				else if(j == i) a[i][j] = 1;
				else{
					a[i][j] = 0;
				}
			}
		}
		
		for(int i = 1; i <= n; i ++ ){
			for(int j = 1; j <= i; j ++ ){
				cout<<a[i][j]<<' ';
			}
			cout<<endl;
		}
	}
	return 0;
}

C - Removing Smallest Multiples （1200）

自己想了个解法没有写出来，缘由是一些数没有覆盖到，果然功力还是差些火候，还是大佬的写法妙啊
请添加图片描述

#include<bits/stdc++.h>

using namespace std;

#define int long long 

const int N = 1e6 + 10;

int n, m;
int a[N];
int T;
bool del[N], p[N];
string str;

void solve(){
	int ans = 0;  //记录答案
	cin>>n;
	cin>>str;
	
	for(int i = 0; i <= n; i ++ ){
		del[i] = false;
		p[i] = false;
	}
	
	for(int i = 0; i < n; i ++ ){
		if(str[i] == '0') del[i + 1] = true;
		else p[i + 1] = true;
	}

	for(int i = 1; i <= n; i ++ ){
		for(int j = i; j <= n; j += i){
			if(del[j]){  //如果这个数可以删 
				ans += i;  //累加答案  
				del[j] = false;  //标记这个数已经删过了，不能再删 
			} 
			else{  //到这里有两种情况，一种是这个数j不应该删，但i的最小公倍数还没删，循环还可以继续向上找i的可以删的最小公倍数 
				   //另一种是这个数不应该删，i的再向上的最小公倍数不能再用i花费，就可以进入到下面的if中 
				if(p[j]) break;
			}
		}
	}
	cout<<ans<<endl;
}

signed main()
{
	cin>>T;
	while(T -- ){
		solve(); 
	}
	return 0;
}