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

---

参考的大佬的题解

A - Select Three Sticks （800）

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

#include

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

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

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;
}

D Slime Escape （1800）

#include

using namespace std;

#define int long long 

const int N = 2e5 + 10;

int T;
int n, k;
int a[N], sum_l, sum_r, sum;
int pre[N], pro[N];
int ll, rr;  //实际遍历的范围 
int min_l, min_r;

void to_l(int l){  //向左扩展 
	ll = l - 1;
	sum_l = a[l - 1];
	min_l = min(0ll, a[l - 1]); 
	while(ll > 1 && sum_l < 0){
		sum_l += a[ -- ll];
		min_l = min(sum_l, min_l);
	}
} 

void to_r(int r){
	rr = r + 1;
	sum_r = a[r + 1];
	min_r = min(0ll, a[r + 1]);
	while(rr < n && sum_r < 0){
		sum_r += a[ ++ rr];
		min_r = min(sum_r, min_r);
	}
}

void solve()
{
		cin>>n>>k;
//		ll = rr = 0;  //能扩展到的范围 
//		min_l = 0;
//		min_r = 0;
//		sum_l = 0;
//		sum_r = 0;
//		sum = 0;
		
		for(int i = 0; i <= n + 1; i ++ ){
			pre[i] = 0;
			pro[i] = 0;
			a[i] = 0;
		}
		
		for(int i = 1; i <= n; i ++ ) cin>>a[i];
		
		for(int i = 1; i <= n; i ++ ){
			pre[i] = min(0ll, pre[i - 1] + a[i]);
		}
		for(int i = n; i >= 1; i -- ){
			pro[i] = min(0ll, pro[i + 1] + a[i]);
		}
		
		int l = k;  //实际扩展到的范围 
		int r = k;
		sum = a[k];
		to_l(k), to_r(k);
		
		while(l != 1 && r != n){
			if(pre[l - 1] + sum >= 0 || pro[r + 1] + sum >= 0){
				cout<<"YES"<<endl;
				return ;
			}
			if(sum_l >= 0 && sum + min_l >= 0){
				sum += sum_l;
				l = ll;
				to_l(l);
			}
			else if(sum_r >= 0 && sum + min_r >= 0){
				sum += sum_r;
				r = rr;
				to_r(r); 
			}
			else{
				cout<<"NO"<<endl;
				return ;
			}
		}
		cout<<"YES"<<endl;	
}

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

---

纯补题，1200的没写出来，1800补的有点勉强，继续加油吧