A. Replacing Elements

題意：一個陣列，可以用兩個不同的元素替換掉另外一個元素，不限次數，問，能否使得陣列中所有元素都不大于 d ，

思路：顯然，如果所有元素都不大于d，那就執行0次，成立，如果有元素大于d，那就得替換掉，顯然選擇最小的兩個元素進行替換，所以如果最小的兩個元素加起來大于d那就沒戲了，反之有解，

AC代碼：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+7;
const int mod = 1e9+7;
int t,n,m,k;
int a[N],b[N];
vector<int> v1,v2;
 
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        for(int i =0 ; i < n ; i ++) cin>>a[i];
        sort(a,a+n);
        int flag = 1;
        if(a[n-1] > k){
            flag = 0;
        }
        if(flag) {
            cout<<"YES"<<endl;
            continue;
        }
        if(a[0]+a[1] <= k){
            cout<<"YES"<<endl;
        }else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

B. String LCM

題意：兩個字串，定義字串的因子就是，字串中重復出現的子串，如“abab” 的因子就是“ab”和“abab”，現在要 求兩個字串的lcm， 也就是說，s1,s2，都是lcm的因子，

思路：第一眼沒有看到資料范圍，浪費了幾分鐘，資料范圍很小，可以直接列舉字串的因子 p，然后求在s1，s2 中出現的次數c1,c2，取lcm(c1,c2)，就是p在要求的字串的出現次數，

AC代碼：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+7;
const int mod = 1e9+7;
int t,n,m,k;
int a[N],b[N];
vector<int> v1,v2;
 
bool div(string s1,string p){
    //cout<<s1<<" "<<p<<endl;
    if(s1.size()%p.size() == 0){
        for(int i = 0 ; i < s1.size() ; i += p.size()){
            for(int j = 0 ; j < p.size() ; j ++){
                if(s1[i+j] != p[j]) return false;
 
            }
        }
        return true;
    }
    return false;
}
 
int getgcd(string s1,string s2){
    string tmp = "";
    int gcd = -1;
    for(int i = 0 ; i < s1.size() ; i ++){
        tmp += s1[i];
        if(div(s1,tmp) && div(s2,tmp)){
            gcd = i+1;
        }
    }
    return gcd;
}
int GCD(int a,int b){
    if(a < b) swap(a,b);
    return b == 0 ? a : GCD(b,a%b);
}
int lcm(int a,int b){
    return a/GCD(a,b)*b;
}
 
signed main(){
    cin>>t;
    while(t--){
        string s1,s2;
        cin>>s1>>s2;
        int g = getgcd(s1,s2);
        if(g == -1){
            cout<<-1<<endl;
        }else{
            string tmp = s1.substr(0,g);
            int lc = lcm(s1.size()/g,s2.size()/g);
            for(int i = 0 ; i < lc ; i ++){
                cout<<tmp;
            }
            cout<<endl;
        }
    }
    return 0;
}

C. No More Inversions

題意：難以描述，給定一個a陣列

a：1,2,3,…,k?1,k,k?1,k?2,…,k?(n?k) (k≤n<2k).

要找一個 p 排列（1-k 的排列），排列的定義可以自行百度，然后根據a陣列和p陣列，可以生成一個b陣列， 要求是，b陣列中的逆序對數量不大于a陣列中的逆序對數量，且字典序最大，b的生成規則是：以a陣列為p的索引，到p中取數放到b陣列中，即b[i] = p[ a[i] ]，有點繞，a陣列就是當下標用，如 a：[1,2,3,2]，那么生成的b陣列就是：

b：[ p[1],p[2],p[3],p[2] ] ，

思路：比賽的時候花了很久才看懂題意，然后懵逼了一會，然后開始找規律，然后發現了規律，a陣列中的逆序對就是 k ,之后的數，如[1,2,3,4,3,2]，就是[4,3,2]，這一部分，生成的b陣列的后半部分（左右對稱的部分）就是[p[2],p[3],p[4],p[3],p[2]]，可以發現，如果p陣列就是有序的，那么生成的就是 23432，逆序對數量一定是等于a陣列的，因為其實就是b陣列等于a陣列了，一模一樣，但是，如果p中這部分值是逆序的，那么生成的就是 43234，逆序對數量也等于a陣列！！，那么顯然逆序排列是字典序最大的，所以答案就是這個東西了！前面不對稱的部分不能改，改了逆序對就比a陣列更多，可以嘗試證明一下，

AC代碼：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+7;
const int mod = 1e9+7;
int t,n,m,k;
int a[N],b[N];
vector<int> v1,v2;
 
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        int res = n-k;		
        int tmp = k-res-1;
        for(int i = 1 ; i <= tmp ; i ++){
            cout<<i<<" ";
        }
        for(int i = k ; i > tmp ; i --){
            cout<<i<<" ";
        }
        cout<<endl;
    }
    return 0;
}

D. Program

題意：x，初始為0，兩種操作，’+’ 表示 x += 1，’-’ 表示 x -= 1，然后題目給出一系列操作，然后q個詢問 l,r，表示刪掉區間 [l-r]，之內的操作，剩下的操作，可以讓x變成多少不同的值，

8 4
-+--+--+
1 8
2 8
2 5
1 1
樣例解釋：
1.empty program — x was only equal to 0;
2."-" — x had values 0 and ?1;
3."---+" — x had values 0, ?1, ?2, ?3, ?2 — there are 4 distinct values among them;
4."+--+--+" — the distinct values are 1, 0, ?1, ?2.

思路：首先考慮在沒有洗掉的情況下，一系列操作程序中，能變成多少不同的值，x初始為0，隨著+±-的變化，會來回反復橫跳，那么兩個關鍵點就是最大值和最小值，這說明從最大值到最小值之間的數字，都是在操作程序中出現，所以只需要考慮一個區間內的操作產生的最大最小值，但是題目要刪掉，中間一段，剩下兩段，也就是要把兩段合并起來，畫個圖其實更好理解，紅色的是所有的操作，綠色的是要洗掉的操作，第二個曲線就是合并之后的x值變化曲線，由圖可知，后面那部分合并過來之后，起點就是前面那部分的終點！這就是關鍵點，然后前面那部分的區間的最大最小值和當前值都很好維護，難的是后面那部分怎么維護，后面那部分，從后往前維護，每到一個點，都認為這個點是零點，然后計算最大值最小值，因為是反著來，可以發現操作曲線是一個與 原操作 關于x軸對稱的曲線，所以最大值就是最小值，最小值就是最大值，然后最小值就是 當前點到最小值的距離，最大值就是 當前點到最大值的距離，之所以算距離，是因為，永遠認為當前點是0點，所以 距離 才是真正的最大最小值，

AC代碼：

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e6+7;
const int mod = 1e9+7;
int t,n,m,k;
int a[N],b[N];
int res[N];
vector<int> v1,v2;
struct node{
    int maxx,minn,now;
}seg[N],seg2[N];
 
signed main(){
    cin>>t;
    while(t--){
        cin>>n>>k;
        string s;
        cin>>s;
        int maxx = 0;
        int minn = 0;
        int now = 0;
        for(int i = 0 ; i < n ; i ++){	// 從前往后維護 前半部分
            if(s[i] == '-') now -= 1;
            if(s[i] == '+') now += 1;
            maxx = max(maxx,now);
            minn = min(minn,now);
            seg[i].maxx = maxx;
            seg[i].minn = minn;
            seg[i].now = now;
        }
        maxx = 0;
        minn = 0;
        now = 0;
        for(int i = n-1 ; i >= 0 ; i --){   // 從后往前維護 后半部分
            if(s[i] == '-') now -= 1;
            if(s[i] == '+') now += 1;
            maxx = max(maxx,now);    
            minn = min(minn,now);
            seg2[i].maxx = now-minn;
            seg2[i].minn = now-maxx;
            seg2[i].now = 0;
        }
        // 防止 越界
        seg[n].maxx = seg2[n].maxx = 0;
        seg[n].minn = seg2[n].minn = 0;
        for(int i = 0 ; i < k ; i ++){
            int x,y;
            cin>>x>>y;x--,y--;x--,y++;
            int maxx = 0;
            int minn = 0;
            // 合并兩個區間，計算最大值和最小值，因為前面可能為空，所以maxx，minn初始都為0，
            if(x >= 0){
                maxx = max(seg[x].maxx,seg[x].now+seg2[y].maxx);
                minn = min(seg[x].minn,seg[x].now+seg2[y].minn);
            }else{
                maxx = seg2[y].maxx;
                minn = seg2[y].minn;
            }
            res[i] = maxx-minn+1;
        }
        for(int i = 0 ; i < k ; i ++){
            cout<<res[i]<<endl;
        }
 
    }
    return 0;
}

E. Minimum Path

看完題目，還剩40多分鐘，選擇掛機，于是掛機了，