A题（贪心）Regular Bracket Sequence

题意：括号匹配问题，给定序列，含一个 ‘（ ’ 一个 ’ ）‘ 其他是问号，问号可以是左括号也可以是右括号，问能否构成 合法括号表达式

判断合法表达式，就是遇到左括号，进栈，遇到右括号，检验，出栈，最后最后栈是否空

关键在右括号

为了使右括号检验正确，贪心，前 s/2-1 个 ? 用 ( 代替 , 其他 ? 用 ) 代替

那么 只需要判断奇偶，第一个不是‘ ) ’ 最后一个不是 ’ ( ‘

#include <bits/stdc++.h>
using namespace std;
int main() {
    int t;
    cin>>t;
    while(t--){
        char a[200];
        cin>>a+1;
        int len=strlen(a)-1;
        if(len%2==0&&a[1]!=')'&&a[len]!='(')cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

B题（前缀和）Red and Blue

f(a)=a₁+a₂+……+a_x=r₁+r₂+……+r_m +b₁+b₂+……+b_n （m，n可以为0）

分别求r数组和b数组前缀和最大的值（还要跟0比），相加得ans

#include<bits/stdc++.h>
#define rep(i,m,n)  for(int i=m;i<=n;i++)
using namespace std;
int a[200],b[200];
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n;
        int cnt1[200]={0};
        int cnt2[200]={0};
        int max1=0,max2=0;
        rep(i,1,n){
            scanf("%d",&a[i]);
            cnt1[i]=cnt1[i-1]+a[i];
            max1=max(max1,cnt1[i]);
        }
        cin>>m;
        rep(i,1,m){
            scanf("%d",&b[i]);
            cnt2[i]=cnt2[i-1]+b[i];
            max2=max(max2,cnt2[i]);
        }
        cout<<max1+max2<<endl;
    }
    return 0;
}

C题（DP）Building a Fence

状态：从左往右修，修到左边的第 i 块，这一块的底端的范围是[ l，r ] ，这一块底端选取区间内值，都存在着 左边总共i-1块的高度的一种方案 使得满足题目要求。

状态转移：i-1 ——> i [ l_i-1 , r_i-1 ] ——> [max( h_i , l_i-1 - (k -1)) , min( h_i +k -1 , r_i-1 +k -1 )]

（如果 l_i > r_i 则说明无解）

最后 l_n <= r_n 且 l_n == h_n 则输出yes 否则no

#include <bits/stdc++.h>
#define ll long long
#define rep(i,m,n)   for(int i=m;i<=n;i++)
using namespace std;
const int maxn=3e5;
ll h[maxn];
int main() {
    int t;
    cin>>t;
    while(t--){
        int n,k,flag=1;
        cin>>n>>k;
        rep(i,1,n){
            scanf("%lld",&h[i]);
        }
        ll le=h[1],ri=h[1];
        rep(i,2,n){
            le=max(h[i],le-(k-1));
            ri=min(h[i]+k-1,ri+k-1);
            if(le>ri){flag=0;break;}
        }
        if(le!=h[n])flag=0;
        if(flag)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

D题 Ceil Divisions

题意：现有a数组a_i =i ,即 1,2,3，，，，，n，一步操作就是任选x，y（注x!=y）a_x=a_x/a_y 向上取整

目标是用不超过n+5步操作 使得a数组变成由 n-1个1， 1个2组成

解一：开方 递归

每一次选取（ ⌈ \lceil ⌈ x \sqrt{x} x ​ ⌉ \rceil ⌉，x ] , 先对所有（ ⌈ \lceil ⌈ x \sqrt{x} x ​ ⌉ \rceil ⌉，x ）范围内的数m， 选 m,x进行一步操作，那么m变为1

然后 选x, ⌈ \lceil ⌈ x \sqrt{x} x ​ ⌉ \rceil ⌉ 进行一步操作，得到一个数。选这个数和 ⌈ \lceil ⌈ x \sqrt{x} x ​ ⌉ \rceil ⌉ 进行一步操作，得到1

这个过程中，操作次数=区间长度+1

如果n=2³²，操作次数=2³² +3 ,故用以上方法，操作次数<=n+3

#include <bits/stdc++.h>
using namespace std;
#define rep(i,m,n)    for(int i=m;i<=n;i++)
#define fi first
#define se second
vector<pair<int,int>>vec;
int main() {
    ios::sync_with_stdio(false);
    int t;
    cin>>t;
    while(t--){
        vec.clear();
        int n;
        cin>>n;
        int st=ceil(sqrt(n));
        while(n>2){
            rep(i,st+1,n-1){
                vec.push_back({i,n});
            }
            vec.push_back({n,st});
            vec.push_back({n,st});
            n=st;
            st=ceil(sqrt(n));
        }
        cout<<vec.size()<<'\n';
        for(auto i:vec)cout<<i.first<<" "<<i.second<<'\n';
    }
    return 0;
}

解二：特殊值8

除了1,2,8，n 对其他每个值x 选x,n进行一步操作

然后 选n,8进行一步操作，循环，直至n变为1

然后 选8,2进行三步操作，8变为1

总的步数=n+5

选取16代替8也一样，总步数n+5

#include <bits/stdc++.h>

using namespace std;
#define rep(i, m, n)    for(int i=m;i<=n;i++)
#define fi first
#define se second
vector<pair<int, int>> vec;

int main() {
    ios::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        vec.clear();//清空
        int n;
        cin >> n;
        if (n > 8) {
            rep(i, 3, n - 1)
                if (i != 8)
                    vec.push_back({i, n});

            int tem = n;
            while (tem != 1) {
                vec.push_back({n, 8});
                tem = ceil(tem / 8.0);
            }

            tem = 8;
            while (tem != 1) {
                vec.push_back({8, 2});
                tem = ceil(tem / 2.0);
            }
        } else {
            rep(i, 3, n - 1) { vec.push_back({i, n}); }

            int tem = n;
            while (tem != 1) {
                vec.push_back({n, 2});
                tem = ceil(tem / 2.0);//注意要转化成double
            }
        }

        cout << vec.size() << '\n';
        for (auto i:vec)cout << i.first << " " << i.second << '\n';
    }
    return 0;
}