?

牛牛學括號

題目要求

• 每次操作必須刪除一個左括號和一個右括號，且刪除后序列仍需合法。
• 合法的括號序列要求每個右括號之前必須有對應的左括號。

分析

輸入的都是合法的括號，即左括號=右括號，可利用這一點去解題

注意：

• 中間取模是必要的，防止計算過程中溢出。
• 中間取模不影響結果正確性，因為模運算的性質保證了分步取模與最終取模等價。

代碼

#include<bits/stdc++.h>
using namespace std;
int main(){string s;cin>>s;int c=0;long long ans=1;//記錄方法總數，初始化答案為1int m=1e9+7; //模數，防止答案溢出for(int i=0;i<s.size();i++){if(s[i]=='(') c++;//記錄當前左括號的數量else{ans*=c; //此時，遇到了右括號，說明不能繼續往后遍歷，要開始為左括號匹配了c--; //剛才遍歷了幾個左括號，就說明后面有幾個右括號與之匹配ans%=m; //分段相乘，匹配完一個，左括號數量減一}}cout<<ans; //要在中間對ans取模，避免溢出return 0;
}

牛牛的朋友

題目要求

每只牛必須移動?X?個單位（向左或向右），目標是使移動后最左和最右牛的距離最小。

分析

牛群有兩種移動方向（這里只分析最優策略）

1. 同向移動
2. 雙向移動

對于雙向移動，我們需要將牛群分成兩部分：

• 前?i-1?頭牛：全部向右移動?+X。
• 后?n-i+1?頭牛：全部向左移動?-X。

我們需要計算這種分組下，移動后牛群的最左位置和最右位置。如圖所示：

注意

并不是所有情況下?maxp-minp?都會比初始值?res?小，一般情況下分割成兩部分雙向移動最左端和最右端距離會更近，但有時同向移動比雙向移動更近，通向移動后左右兩端的距離不變，因此，在這里用初始時兩端的距離來初始化res，如果采用分割的方式，會出現比res更小的值，則更新，否則就說明此時，同向更優，無需更新。

代碼

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;long long a[n];for(int i=0;i<n;i++) cin>>a[i];//存儲牛位置int x;cin>>x;int max1=-1e8,min1=1e8;for(int i=0;i<n;i++){if(a[i]>max1)max1=a[i];//先求出牛初始位置的最大距離，目的是用來初始化res,同時包含if(a[i]<min1)min1=a[i];//同向移動的情況}int res=0;res=max1-min1;sort(a,a+n);// 枚舉分割點i，將前i-1頭牛向右移動，其余向左移動for(int i=1;i<n;i++){  //數組是從0開始索引，但要分割成兩半部分，所以從1開始int max2=max(a[n-1]-x,a[i-1]+x);//求最右邊兩種情況的maxint min1=min(a[0]+x,a[i]-x);//求最左邊兩種情況的minif(res>max2-min1){res=max2-min1;//更新res}}cout<<res;return 0;
}

?

?