Educational Codeforces Round 102 (Rated for Div. 2)A~D题解

发布于 2021-01-30  7 次阅读


A. Replacing Elements

题意:

给你n个数,操作:你可以选择其中三个数,将选择的三个数中的任意一个数变成另外两数的和,你可以执行任意次上述操作,求使得数组中所有的数均不大于d

思路:

首先判断是否有数大于d,有则判断数组中最小的两个数的和是否不大于d

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, d, a[N];
void solve(){
   cin>>n>>d;
   cin>>a[1]>>a[2];
   int mi1=mymin(a[1],a[2]), mi2=mymax(a[1],a[2]);
   int flag=0;
   if(a[1]>d || a[2]>d) flag=1;
   for(int i=3; i<=n; i++){
      cin>>a[i];
      if(a[i]>d) flag=1;
      if(a[i]<mi1)      mi2=mi1, mi1=a[i];
      else if(a[i]<mi2) mi2=a[i];
   } 
   if(!flag || mi1+mi2<=d) cout<<"YES"<<endl;
   else cout<<"NO"<<endl;
   return ;
}
signed main(){
   int T;
   cin>>T;
   while(T--) solve();
   return 0;
}

B. String LCM

题意:

给你两个字符串a和b,求他们的lcm(最小公倍数)的字符串c

思路:

首先可得字符串c的长度为 LCM(lena,lenb)/lenb (假设字符串a长度更长)
即字符串c为lenc个字符串b,先构建出字符串c
再循环去验证匹配字符串a即可

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}

string s, t;
void solve(){
	cin>>s>>t;
	int len1=(int)s.size();
	int len2=(int)t.size();
	if(len1<len2){
		swap(s,t);
		swap(len1,len2);
	}
	int len=lcm(len1,len2)/len2;
	string ans="";
	for(int i=1; i<=len; i++){
		ans+=t;
	}
	bool flag=true;
	int i=0;
	while(i<(int)ans.size()){
		for(int j=0; j<len1; j++){
			if(ans[i]!=s[j]){
				flag=false;
				break;
			}
			i++;
		}
		if(!flag) break;
	}
	if(flag) 	cout<<ans<<endl;
	else 		cout<<"-1"<<endl;
	return ;
}
signed main(){
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

C. No More Inversions

题意:

给你两个数n和k,可得一个数组a为1~k~k-(n-k),求相同逆序数且字典序最小的数组b。

思路:

逆序数相同即为后半部分相同数相同,字典序最大即前半部分从1开始排序

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, k;
void solve(){
	cin>>n>>k;
	for(int i=1; i<2*k-n; i++) cout<<i<<" ";
	for(int i=k; i>=2*k-n; i--) 	cout<<i<<" ";
	cout<<endl;
	return ;
}
signed main(){
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

D. Program

题意:

您将得到一个包含n条指令的程序。 最初,将单个变量x分配为0。之后,指令分为两种类型:
x增加1;
x减少1。
您会收到以下格式的m查询:
查询l ~ r ,如果忽略了第l个和第r个(含)之间的所有指令,而x分配了多少个不同的值?

思路:

忽略l~r后即为查询1~l-1,r+1到n条指令导致x被分配的不同的值的个数,x的值个数显然为这两段中最大值减去最小值+1,因为这段中每个值都至少出现一遍。
所以考虑使用前缀和和后缀和分别维护从前开始和从后开始的最大值和最小值即可。

AC Code:

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<math.h>
using namespace std;
#define endl '\n'
#define INF 0x3f3f3f3f
// #define int long long
#define debug(a) cout<<#a<<"="<<a<<endl;
typedef long long ll;
const double PI=acos(-1.0);
const double e=exp(1.0);
const int M=1e9+7;
const int N=2e5+7;
inline int mymax(int x,int y){return x>y?x:y;}
inline int mymin(int x,int y){return x<y?x:y;}
int n, m, l, r;
char s[N];
int pre[N], pre_mi[N], pre_mx[N], suf_mi[N], suf_mx[N];
void solve(){
	cin>>n>>m;
	cin>>s+1;
	for(int i=1; i<=n; i++){
		pre[i]=pre[i-1]+(s[i]=='+'?1:-1);
		pre_mi[i]=mymin(pre_mi[i-1],pre[i]);
		pre_mx[i]=mymax(pre_mx[i-1],pre[i]);
	}
	suf_mi[n+1]=suf_mx[n+1]=0;
	for(int i=n; i>=1; i--){
		suf_mi[i]=mymin(0,suf_mi[i+1]+(s[i]=='+'?1:-1));
		suf_mx[i]=mymax(0,suf_mx[i+1]+(s[i]=='+'?1:-1));
	}
	for(int i=1; i<=m; i++){
		cin>>l>>r;
		cout<<mymax(pre_mx[l-1], suf_mx[r+1]+pre[l-1])-mymin(pre_mi[l-1], suf_mi[r+1]+pre[l-1])+1<<endl;
	}
	return ;
}
signed main(){
	int T;
	cin>>T;
	while(T--) solve();
	return 0;
}

平平无奇的在校大学生