因為準備期末考試，漏了半個多月的cf沒有打，現在回來補補，順便找一下手感（好久沒打，都生疏了QAQ）

A. Regular Bracket Sequence

題目傳送門：

A. Regular Bracket Sequence

思路：

只有一對括號‘（）’，剩下的全部都是問號，每個問號都有可能是‘（’或者是‘）’，問能不能使所有的括號匹配，
最開始沒有看到只有一對括號的那個條件，還寫復雜了，

AC Code

#include <bits/stdc++.h>
using namespace std;
string s;
int main()
{
   int t;
   cin>>t;
   while(t--)
   {
       cin>>s;
       int n=s.size();
       if(n&1||s[0]==')'||s[n-1]=='(')
        cout<<"NO"<<endl;
        else 
        cout<<"YES"<<endl;
   }
   return 0;
}

B. Red and Blue

題目傳送門：

B. Red and Blue

思路：

因為r陣列和b陣列中的元素在a陣列中的相對位置并沒有改變，所以另r陣列的最大前綴和為X，b陣列的最大前綴和為Y，那么答案便是max（ X , Y , X + Y ），

AC Code

#include<bits/stdc++.h>
using namespace std;
int n,m;
int r[200],b[200];
int f1[200],f2[200];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        memset(f1,0,sizeof(f1));
        memset(f2,0,sizeof(f2));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&r[i]);
        scanf("%d",&m);
        for(int i=1;i<=m;i++)
            scanf("%d",&b[i]);
        int maxr=-1e5,maxb=-1e5;
        for(int i=1;i<=n;i++)
        {
            f1[i]=f1[i-1]+r[i];
            maxr=max(maxr,f1[i]);
        }
        for(int i=1;i<=m;i++)
        {
            f2[i]=f2[i-1]+b[i];
            maxb=max(maxb,f2[i]);
        }
        int res=0;
        res=max(maxr,maxb);
        res=max(res,maxr+maxb);
        res=max(res,0);
        printf("%d\n",res);
    }
    //system("pause");
    return 0;
}

C. Building a Fence

題目傳送門：

C. Building a Fence

思路：

第一個柵欄和最后一個柵欄的位置是肯定的，求出每個柵欄的起點區間，然后與前一個柵欄相比較有沒有公共邊即可，如果2~n-1個柵欄都滿足，那么不要忘記和最后一個確定的柵欄相比較，

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int h[N];
int top[N],low[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&h[i]);
        top[1]=h[1],low[1]=h[1];
        top[n]=h[n],low[n]=h[n];
        int flag=0;
        for(int i=2;i<n;i++)
        {
            top[i]=h[i]+k-1;//最高的起點
            low[i]=h[i];   //最低的起點
            top[i]=min(top[i],top[i-1]+k-1);
            low[i]=max(low[i],low[i-1]-k+1);
            if(low[i]>=top[i-1]+k||top[i]<=low[i-1]-k)
            {
                flag=1;
                break;
            }
        }
        if(low[n]>=top[n-1]+k||top[n]<=low[n-1]-k) flag=1;
        if(flag==1) printf("NO\n");
        else printf("YES\n");
    }
    //system("pause");
    return 0;
}

D. Ceil Divisions（構造）

題目傳送門：

D. Ceil Divisions

思路：

我們發現一個比n小的數除以n向上取整之后都為1，但是這樣最后會留下一個n無法處理，于是我們就想著n該怎么處理，我最開始想到的是不斷除以2，但是看到資料范圍和最大的運算元，這樣想顯然是不對的，看到這個運算元，那么感覺最可能的是開平方，然后我們觀察（n^1/2,n) ,我們發現n除以兩次前者即為1，而且2e5不斷開平方為200000 448 22 5 3 2，顯然操作的次數是滿足題目要求的，

AC Code

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int h[N];
int top[N],low[N];
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
            scanf("%d",&h[i]);
        top[1]=h[1],low[1]=h[1];
        top[n]=h[n],low[n]=h[n];
        int flag=0;
        for(int i=2;i<n;i++)
        {
            top[i]=h[i]+k-1;//最高的起點
            low[i]=h[i];   //最低的起點
            top[i]=min(top[i],top[i-1]+k-1);
            low[i]=max(low[i],low[i-1]-k+1);
            if(low[i]>=top[i-1]+k||top[i]<=low[i-1]-k)
            {
                flag=1;
                break;
            }
        }
        if(low[n]>=top[n-1]+k||top[n]<=low[n-1]-k) flag=1;
        if(flag==1) printf("NO\n");
        else printf("YES\n");
    }
    //system("pause");
    return 0;
}