Educational Codeforces Round 102
一. A.Replacing Elements
（1）题意：
给你一个数组，可以选择其中三个不同位置的数i,j,k,使得a[i] = a[j] + a[k]，问能不能经过0次或者多次操作使得数组里面的数都小于等于d
（2）题解：
能够使数组在任何时候都小于等于d的话，要么是存在两个数相加都不超过d，就可以使得任何一个数都 = 这两个数相加，要么就是所有数都已经不超过d，直接满足条件
（3）代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,a[1000];
void solve(){
int n,d,flag = 0;
cin>>n>>d;
for(int i = 1; i <= n; i++){
cin>>a[i];
if(a[i] > d) flag = 1;
}
if(!flag) {
puts("YES");
return ;
}
sort(a+1,a+1+n);
if(a[1] + a[2] <= d) puts("YES");
else
puts("NO");
}
int main(){
cin>>t;
while(t--)
solve();
return 0;
}
二. B.String LCM
（1）题意：
给你两个只由a,b构成的字符串，求出他们的最小倍串，例如aa，aaa的最小倍串就是aaaaaa
（2）题解：
我们可以根据给出的两个字符串来凑出最小倍串，因为是ab*2的规则是 = abab，所以当出现该构造最小倍串的位置上的两个字符串的字符不一致时，就说明凑不出来。比如说s[i] != t[i] 时，就说明不存在最小倍串，且这构造过程最多进行s.size() * t.size() / gcd(s,t)次操作。
（3）代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
void solve(){
string s,t,ans;
cin>>s>>t;
int l1 = 0,l2 = 0;
for(int i = 1; i <= 400; i++){ //字符串的长度不超过20，为了图方便就直接写400
if(s[l1] != t[l2]){
puts("-1");
return ;
}
ans += s[l1];
l1 = (l1+1)%s.size();
l2 = (l2+1)%t.size();
if(l1 == 0 && l2 == 0){
cout<<ans<<endl;
return ;
}
}
}
int main(){
cin>>t;
while(t--)
solve();
return 0;
}
三. C. No More Inversions
（1）题意：
给你一个a数组：1，2，3…k，k-1…k - (n-k)，当i < j 且 a[i] > a[j] 时就是一个逆序对
设定b[i] = p[a[i]]，p数组内的元素为1，2，3… k，可以任意排列p数组内的元素，求出一个排列使得b数组的字典序最大且b数组中的逆序对总数不超过a数组中的逆序对总数
（2）题解：
当你多写几组数据之后，例如(5,3),(6,4),(8,5)就会得到他们的共同点
a数组中的逆序总数是固定的——(n-k) * (n-k)个，而且出现两次的元素会呈现中心对称，那么b数组中也是同样的情况，把p数组中最大的元素向前移动n-k位，在b数组中会关于第k位元素对称，最大值与其他值会产生(n-k) * 2-1个逆序对，这时有n-k-1个数也会产生的x个逆序对就恰好 = (n-k) * (n-k)，不管如何在p数组中排列这剩下n - k - 1个数，都会中心对称，产生同样数量的逆序对。
所以n-k就代表最大元素前移多少位，前1 ~ 2k-n-1个数升序排列，后2k-n ~ k个数降序排列。
（3）代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t;
void solve(){
int n,k;
cin>>n>>k;
int p = n - k;
for(int i = 1; i < k - p; i++)
cout<<i<<" ";
for(int i = p; i >= 0; i--){
cout<<k<<" ";
k--;
}
cout<<endl;
}
int main(){
cin>>t;
while(t--)
solve();
return 0;
}
四. D. Program
（1）题意：
‘-’代表减1，‘+’代表加1，给定一串加减号，有m次查询，每次查询给定一个区间，问去掉这个区间后，剩下的加减号在不改变原次序的情况下会产生多少个不同的数，初始化为0
（2）题解：
可以根据+1，-1来做前缀和，然后利用树状数组来做区间查询，因为每次给定的被减区间将整个区间划分成了两半，所以其结果为max(前段的最大值，后段的最大值) - min(前段的最小值，后段的最小值) + 1。
注意每次最开始初始化了x的值为0，所以求前段最大值(/最小值)时都要和0在做一次比较，然后后段的最大值(/最小值)要减去给定被减区间的值
（3）代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int t,n,m,b[200005],c[200005],sum[200005];
int lowbit(int x){
return x & (-x);
}
void build1(int id,int val){
b[id] = val;
for(int i = 1; i < lowbit(id); i++){
b[id] = max(b[id],b[id-i]);
}
}
int query1(int l,int r){
int ans = sum[r];
while(r >= l){
ans = max(sum[r],ans);
r--;
for(;r - l >= lowbit(r); r -= lowbit(r))
ans = max(b[r],ans);
}
//cout<<"ans = "<<ans<<endl;
return ans;
}
void build2(int id,int val){
c[id] = val;
for(int i = 1; i < lowbit(id); i++){
c[id] = min(c[id],c[id-i]);
}
}
int query2(int l,int r){
int ans = sum[r];
while(r >= l){
ans = min(sum[r],ans);
r--;
for(;r - l >= lowbit(r); r -= lowbit(r))
ans = min(c[r],ans);
}
return ans;
}
void solve(){
cin>>n>>m;
memset(b,0,sizeof(b));
memset(c,0,sizeof(c));
memset(sum,0,sizeof(sum));
for(int i = 1; i <= n; i++){
char x;
int a;
cin>>x;
a = (x == '+'? 1 : -1);
sum[i] = sum[i-1] + a;
build1(i,sum[i]);
build2(i,sum[i]);
}
for(int i = 1; i <= m; i++){
int l,r;
cin>>l>>r;
int x = sum[r] - sum[l-1];
int max1 = max(max(0,query1(1,l-1)),query1(r+1,n) - x);
int min1 = min(min(0,query2(1,l-1)),query2(r+1,n) - x);
cout<<max1 - min1 + 1<<endl;
}
}
int main(){
cin>>t;
while(t--)
solve();
return 0;
}