Educational Codeforces Round 161 (Rated for Div. 2)

A. Tricky Template

思维有点难转过来，而且当时在C也能匹配c这卡了很久

#include<bits/stdc++.h>
using namespace std;
void solve(){
	int n;
	cin>>n;
	string a,b,c;
	cin>>a>>b>>c;
	int cnt=0;
	int f=0;
	for(int i=0;i<n;i++){
		if(a[i]!=c[i]&&b[i]!=c[i])f=1;
	}
	if(f){
		cout<<"YES\n";
	}else{
		cout<<"NO\n";
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
} 

B. Forming Triangles

两种情况

#include<bits/stdc++.h>
#define  int long long
using namespace std;
const int N=3e5+10;
void solve(){
	int n;
	cin>>n;
	map<int,int>mp;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		mp[x]++;
	}
	int ans=0;
	int sum=0;
	for(auto c:mp){
		int x=c.second;
		if(x>=2)sum+=(x*(x-1))/2;
	}
	for(auto c:mp){
		int x=c.second;
		int u=c.first;
		if(x>=3){
			ans+=(x*(x-1)*(x-2))/6;
		}
		sum-=(x*(x-1))/2;
		ans+=x*sum;
	}
	cout<<ans<<"\n";
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
} 

C. Closest Cities 前缀和

一开始脑子抽了把需要

和

分开来讨论了，于是用了结构体，但是其实这两个都是花费问题，所以用数组前缀和，到时候直接查就行了

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
int a[N],l[N],r[N];
void solve(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n-1;i++){
		if(i==1||a[i+1]-a[i]<a[i]-a[i-1])r[i]=1;
		else r[i]=a[i+1]-a[i];
	}
	for(int i=n;i>=2;i--){
		if(i==n||a[i]-a[i-1]<a[i+1]-a[i])l[i]=1;
		else l[i]=abs(a[i-1]-a[i]);
	}
	for(int i=1;i<=n;i++)r[i]+=r[i-1];
	for(int i=n;i>=1;i--)l[i]+=l[i+1];
	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		int x,y;
		cin>>x>>y;
		if(x<y){
			cout<<r[y-1]-r[x-1]<<"\n";
		}else{
			cout<<l[y+1]-l[x+1]<<"\n";
		}
	}
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
}