Educational Codeforces Round 102 (Rated for Div. 2)
A. Replacing Elements
做法：
水题，直接判断数组是否都小于(d)，如果都小于(d)，那么(YES)，否则判断最小的和次小的相加小于(d)，如果小于那么(YES)，否则(NO)。
代码：
不贴了^^_
B. String LCM
做法：
要满足(LCM（s，t）)要找s和t的最小循环节(st)，找到后循环循环节(（s/st） imes（t/st）)次后，就是(LCM（s，t）)，如果找不到(st)，就为(-1)
代码：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=3e5+7;
int t;
string s,d;
int main(){
cin>>t;
while(t--){
cin>>s;
cin>>d;
if(s.size()<d.size()){
swap(s,d);
}
int ok=0;
string a="",ans;
int ans1=0,ans2=0;
for(int i=0;i<d.size();i++){
a+=d[i];
int flag1=0,flag2=0,cnt1=0,cnt2=0;
string ha="";
for(int j=1;j<=20;j++){
ha+=a;
if(ha==s){
flag1=1;
cnt1=j;
break;
}
}
ha="";
for(int j=1;j<=20;j++){
ha+=a;
if(ha==d){
flag2=1;
cnt2=j;
break;
}
}
if(flag1==1&&flag2==1){
ans=a;
ans1=cnt1;
ans2=cnt2;
ok=1;
}
}
if(ok==1){
for(int i=1;i<=ans1*ans2;i++){
cout<<ans;
}
cout<<endl;
}else{
cout<<"-1"<<endl;
}
}
}
C. No More Inversions
做法：
观察我们可以发现a和变化后的b都是关于在第k位不完全对称的，a排列的逆序对的产生也是在超过的k位后产生的，也就是说我们构造b的话，构造b的前k位的逆序对与a的后k位的逆序对相等，即有n-k个排列逆序的，最后保证字典序大。
举个例子：(n=5,k=3)。
(a=[1,2,3,2,1])。考虑a后k个的逆序对要和构造的(b)前(k)个的逆序对相等。那么(b=[3,2,1,2,3])。则(p=[3,2,1])。
代码:
#include <iostream>
using namespace std;
int t;
int n,k;
int main(){
cin>>t;
while(t--){
cin>>n>>k;
int cnt=n-k;
cnt=k-cnt;
for(int i=1;i<=cnt-1;i++){
cout<<i<<" ";
}
for(int i=k;i>=cnt;i--){
cout<<i<<" ";
}
cout<<endl;
}
}
D. Program
做法：
将+抽象位+1，-抽象位-1，数组a记录前缀和，要求数的个数，就是在(l-r)的(Max-Min+1)，用线段树RMQ处理区间最大值和最小值问题。
代码：
#include <iostream>
#define lch 2*k
#define rch 2*k+1
#define mid (l+r)/2
using namespace std;
const int N=2e5+7;
int t;
int n,m,a[N],Max,Min,maxn[4*N],minn[4*N];
void init(int k,int l,int r){
if(l>=r){
maxn[k]=minn[k]=a[l];
return;
}
init(lch,l,mid);
init(rch,mid+1,r);
maxn[k]=max(maxn[lch],maxn[rch]);
minn[k]=min(minn[lch],minn[rch]);
}
void qry(int k,int l,int r,int ql,int qr,int val){
if(ql>qr){
return;
}
if(ql<=l&&r<=qr){
Max=max(Max,maxn[k]+val);
Min=min(Min,minn[k]+val);
return ;
}
if(ql<=mid) qry(lch,l,mid,ql,qr,val);
if(mid+1<=qr) qry(rch,mid+1,r,ql,qr,val);
return;
}
int main(){
cin>>t;
while(t--){
cin>>n>>m;
for(int i=1;i<=n;i++){
char ch;
cin>>ch;
if(ch=='+'){
a[i]=a[i-1]+1;
}else{
a[i]=a[i-1]-1;
}
}
init(1,1,n);
while(m--){
int ql,qr;
cin>>ql>>qr;
Max=-1e9,Min=1e9;
qry(1,1,n,1,ql-1,0);
qry(1,1,n,qr+1,n,-(a[qr]-a[ql-1]));
Min=min(0,Min);
Max=max(0,Max);
cout<<Max-Min+1<<endl;
}
}
}