不说了，经典赛后过题，此次一定给出A-D。
A. Replacing Elements
题意
给出一个长度n数组。在一次操作中，你可以取任意三个不同的坐标i、j、k。使得 a_i+a_j=a_k ,这个操作可以进行任意次，问是否能让数组中的所有数小于d。
题解
遍历数组，找出两个最小的数的同时判断数组中所有数是否超过d。if（（数组中所有数原本就没有超过d）||（两个最小的数之和小于等于d））就是yes。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
int min1=imax,min2=imax;
int n,d,s,fla=0;
cin>>n>>d;
for(int i=0;i<n;i++){
cin>>s;
if(s>d)fla=1;
if(min1>s){
if(min2>min1)min2=min1;
min1=s;
}
else if(min2>s){
if(min1>min2)min1=min2;
min2=s;
}
}
if(min1+min2<=d||fla==0){
cout<<"YES"<<endl;
}
else{
cout<<"NO"<<endl;
}
}
}
B. String LCM
题意
就是两个字符串a、b公共最短子串的lcm，如果没有公共最短子串输出-1。
题解
使用两个字符串长度的lcm，分别用a和b拼接成两个字符串，如果两个相等就输出，不等就说明没有公共子串。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
string a,b,a1="",b1="";
cin>>a;
cin>>b;
int re=lcm(a.size(),b.size());
string res="";
while(a1.size()!=re){
a1+=a;
}
while(b1.size()!=re){
b1+=b;
}
int f=0;
for(int i=0;i<re;i++){
if(a1[i]!=b1[i]){
cout<<-1<<endl;
f=1;
break;
}
}
if(f==0) cout<<a1<<endl;
}
}
C. No More Inversions
题意
给出两个数字n和k，其中n是a数组长度，a数组规律是1，2，3….k,k-1,k-2,…..,k-(n-k)。
inversion关系就是i<j&&a_i>a_j。
我们要构建一个新数组b，规律为b[i]=p[a[i]]，b数组中inversion关系元素个数不能超过a，同时b的字典序也要最大。
输出数组p。
题解
我们观察以下规律：
a：1 2 3 2
b：1 3 2 3
p: 1 3 2
a：1 2 3 2 1
b：3 2 1 2 3
p: 3 2 1
a: 1 2 3 4 3
b: 1 2 4 3 4
p: 1 2 4 3
a：1 2 3 4 5 6 5 4
b：1 2 3 6 5 4 5 6
p: 1 2 3 6 5 4
我们可以发现，p的前n-(n-k)-1个数是1,2,3,4,……，后面的数是把后面几项倒过来。
我是通过找规律的方式过的，但是仔细想想还是能想出道理。
a数组的后2*(n-k)+1项是对称的，根据b[i]=p[a[i]]，所以b数组的后半段也是对称的，为了不超过a数组中inversion关系的个数，我们只能对a数组的后2*(n-k)项进行修改。同时，为了保证字典序最大，b数组后半段规律就是k,k-1,k-2….k-(n-k）……k-1,k-2。
有了a和b，据此我们就能求出p。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
int n,k;
cin>>n>>k;
int j=0;
for(int i=1;i<=k;i++){
if(i<k-(n-k)) cout<<i<<" ";
else {
cout<<k-j<<" ";
j++;
}
}
cout<<endl;
}
}
D. Program
题意
x的初始值为0，遇到+就加1，遇到-就减一。问去掉[l,r]区间内的运算，在运算过程中能得到几个值？
题解
这道题乍一看像是线段树一类区间维护的题，实际上仔细看看不是。
我们可以模拟一遍x，存到数组中，x增减一定是连续的，在未去掉某个区间的时候，就是最大值和最小值的差再+1（还有0）。
在删除一个区间后，被分解为了前后两段，两段中间的操作过程我们可以忽略，只计算出对x的增减即可。然后我们求出前缀最大值、最小值和后缀最大值、最小值，前缀最大值就是、最小值对应前一个区间，后缀最大值、最小值对应后面的区间，我们用后缀最大值、最小值分别减去删除区间的增减，就得到了删除后后面区间的最大值和最小值，然后和前一个区间取max、min，求出整体最大值和最小值，相减加一，就得到结果了。
例如，对于第二个样例：
x的值：0 1 0 1 2
前缀最大值：0 1 1 1 2
前缀最小值：0 0 0 0 0
后缀最大值：2 2 2 2 2
后缀最小值：0 0 0 1 2
删除区间[2,3]，在1处前缀最大值、最小值为1，0。在4处后缀最大值、最小值为2，2。删除区间的增减为0（x[3]-x[1]），所以整体最大值为2，最小值为0，结果为3。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define imax 0x3f3f3f3f
#define lmax 0x3f3f3f3f3f3f3f3f
struct node{
int top;
int bottom;
int num;
/*bool operator < (node a){
if(h!=a.h)
return h < a.h;
return w < a.w;
}
*/
};
int main(void)
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
int _;
cin>>_;
while(_--){
int n,m;
cin>>n>>m;
char c;
int num=0;
vector<node> s;
node nod;
nod.top=0;
nod.bottom=0;
nod.num=0;
s.push_back(nod);
for(int i=1;i<=n;i++){
cin>>c;
if(c=='+')num++;
else num--;
nod.num=num;
if(num>s[i-1].top) nod.top=num;
else nod.top=s[i-1].top;
if(num<s[i-1].bottom) nod.bottom=num;
else nod.bottom=s[i-1].bottom;
s.push_back(nod);
}
node s2[n+1];
nod.top=s.back().num;
nod.bottom=s.back().num;
nod.num=0;
s2[n]=nod;
for(int i=n-1;i>=0;i--){
nod.top=max(s[i].num,s2[i+1].top);
nod.bottom=min(s[i].num,s2[i+1].bottom);
nod.num=0;
s2[i]=nod;
}
int a,b;
for(int i=0;i<m;i++){
cin>>a>>b;
int top=s[a-1].top;
int bottom=s[a-1].bottom;
//cout<<top<<" "<<bottom<<endl;
if(b==n){
cout<<top-bottom+1<<endl;
continue;
}
int top2=s2[b+1].top-(s[b].num-s[a-1].num);
int bottom2=s2[b+1].bottom-(s[b].num-s[a-1].num);
//cout<<top2<<" "<<bottom2<<endl;
cout<<max(top,top2)-min(bottom,bottom2)+1<<endl;
}
}
}
