A.Regular Bracket Sequence
題解：
這個題目一開始WA了兩發的原因很玄學：沒有看出來他的
()
隻有一對…
那麼在
()
有且僅有一對的情況下，我們首先判斷目前字元串的長度是不是偶數，也就是判斷 l e n m o d 2 = = 0 len\mod 2 == 0 lenmod2==0，如果目前字元串的長度非偶，那麼就可以直接
say no
了，否則我們就讓前一半的
?
變成
(
，後一半變成
)
然後用一個
stack
就可以了
AC代碼
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<list>
#include<set>
#include<limits.h>
#define ll long long
#define INF 0x3f3f3f3f
#define inf -1e12
#define me(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define ull unsigned long long
#define ios std :: ios :: sync_with_stdio(false)
using namespace std;
const int maxn = 1e3 + 10;
int t;
string s;
stack<char> st;
int main()
{
ios;
cin >> t;
while(t--) {
cin >> s;
bool flag = 1;
int len = s.length();
if(len % 2 != 0) {
cout << "NO" << endl;
continue;
}
else {
int num = (len - 2) / 2,cnt = 0;
for(int i = 0;i < len;i++) {
if(s[i] == '?') {
if(++cnt > num) s[i] = ')';
else s[i] = '(';
}
else continue;
}
for(int i = 0;i < len;i++) {
if(s[i] == '(') st.push(s[i]);
else if(s[i] == ')') {
if(st.empty()) {
flag = 0;
break;
}
else st.pop();
}
}
if(flag == 0 || !st.empty()) cout << "NO" << endl;
else cout << "YES" << endl;
}
}
return 0;
}
B. Red and Blue
題解：
給出了兩個序列，讓我們不改變他們元素的相對順序的前提下合并兩個序列，新生成的序列
a
滿足： f ( a ) = m a x ( a 1 , a 1 + a 2 , . . . . . . , a 1 + a 2 + a 3 + . . . + a n + m ) f(a) = max(a_1,a_1 + a_2,......,a_1 + a_2 + a_3+...+a_{n + m}) f(a)=max(a1,a1+a2,......,a1+a2+a3+...+an+m)
那麼可以直接維護兩個序列的字首和最大值，然後放在一起就OK了
AC代碼
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<list>
#include<set>
#include<limits.h>
#define ll long long
#define INF 0x3f3f3f3f
#define inf -1e12
#define me(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define ull unsigned long long
#define ios std :: ios :: sync_with_stdio(false)
using namespace std;
const int maxn = 1e3 + 10;
int r[maxn],b[maxn];
int rm[maxn],bm[maxn];
int r_max,b_max;
int t,n,m;
void init()
{
r_max = 0;
b_max = 0;
me(rm,0);
me(bm,0);
me(r,0);
me(b,0);
}
int main()
{
ios;
cin >> t;
while(t--) {
init();
cin >> n;
for(int i = 1;i <= n;i++) cin >> r[i];
cin >> m;
for(int i = 1;i <= m;i++) cin >> b[i];
for(int i = 1;i <= n;i++) {
rm[i] = rm[i - 1] + r[i];
r_max = max(r_max,rm[i]);
}
for(int i = 1;i <= m;i++) {
bm[i] = bm[i - 1] + b[i];
b_max = max(b_max,bm[i]);
}
cout << r_max + b_max << endl;
}
return 0;
}
C.Building a Fence
題解：
首先我們規定好每一個栅欄可以修築的最大高度，然後對于第一個栅欄他肯定是隻能在
h
的高度上，也就是說它的高度範圍會被限定在 [ l , r ] , l = r = h [l,r],l = r = h [l,r],l=r=h上，那麼我們再通過第一個栅欄的高度範圍去确定第二個栅欄的範圍：
他需要滿足的條件是：第二個栅欄距地面的懸浮高度不能大于 k − 1 k - 1 k−1，同時他和前一個栅欄的公共邊長至少是1，那麼我們已知每一個栅欄的高度都相同為
k
，那麼滿足題意的第二個栅欄的高度範圍是： [ l − ( k − 1 ) , r + ( k − 1 ) ] [l - (k - 1),r + (k - 1)] [l−(k−1),r+(k−1)]這個可以畫圖了解。其次我們還要注意到，它距離地面的高度至少0，最大是 k − 1 k - 1 k−1，那麼我們需要再去進行一次比對： l 2 = m a x ( l − ( k − 1 ) , n ) l_2 = max(l - (k - 1),n) l2=max(l−(k−1),n)， r 2 = m i n ( n , r + ( k − 1 ) ) r_2 = min(n,r + (k - 1)) r2=min(n,r+(k−1))這樣子如果最後的結果是 l ⩽ r l \leqslant r l⩽r那就說明是可以滿足的，但是我們需要注意的一個點是：最後一個栅欄位置也是在地上，是以我們必須在處理最後一個栅欄的時候有一個特判，也就是說我們得出的這個 [ l , r ] [l,r] [l,r]的範圍必須包含了
h
，隻要最後判斷一下 r ⩽ n , l ⩾ n r \leqslant n , l \geqslant n r⩽n,l⩾n即可。
AC代碼：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<list>
#include<set>
#include<limits.h>
#define ll long long
#define INF 0x3f3f3f3f
#define inf -1e12
#define me(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define ull unsigned long long
#define ios std :: ios :: sync_with_stdio(false)
using namespace std;
const int maxn = 2e5 + 10;
ll h[maxn];
int t,k,n;
int main()
{
ios;
cin >> t;
while(t--) {
cin >> n >> k;
bool flag = 0;
for(int i = 1;i <= n;i++) cin >> h[i];
ll l = h[1],r = h[1];
for(int i = 2;i <= n;i++) {
ll t1 = l - (k - 1);
ll t2 = r + (k - 1);
t1 = max(t1,(ll)h[i]);
t2 = min(t2,(ll)(h[i] + k - 1));
if(t1 > t2) flag = 1;
l = t1;r = t2;
}
if(flag || l > h[n] || r < h[n]) cout << "NO" << endl; //?
else cout << "YES" << endl;
}
return 0;
}
D.Ceil Divisions
題解：
又是一道數學題
我們注意一下他說的這個 n + 5 n + 5 n+5是怎麼想的。
既然我們想讓這個序列中隻有一個2和 n − 1 n - 1 n−1個1，那麼我們首先想到的就是我們把現在序列裡有的這個1，2保持不動，這樣子我們隻需要去執行 n − 2 n - 2 n−2個數的操作，然後我們發現，隻要 x < y x < y x<y那麼最後得出的 a x = 1 a_x = 1 ax=1這時候操作的步數是最小的，于是我們就發現，如果我們用所有的數去和
n
配對，那麼我們就可以在 n − 3 n - 3 n−3步内把除了
n
以外的數全部變成1。但是問題就是
n
要怎麼處理。
我們肯定想到的是用 n \sqrt{n} n
來做，這樣最後我們隻需要兩步操作就可以讓
n
變為1，但是如果
n
本身不是一個完全平方數呢？那麼就讓 [ 2 , ( n − 1 ) ] [2,(n-1)] [2,(n−1)]中第一個平方大于他的數去和他配對，這樣子就一定可以在兩步之内實作換1，2e5的資料量最多進行5次開方就到2了，是以我們可以做的最多的變換次數就是 n − 2 + 5 = n + 3 < n + 5 n - 2 + 5 = n + 3 < n + 5 n−2+5=n+3<n+5是以我們這個思路是正确的。
AC代碼：
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<list>
#include<set>
#include<limits.h>
#define ll long long
#define INF 0x3f3f3f3f
#define inf -1e12
#define me(a,b) memset(a,b,sizeof(a))
#define PII pair<int,int>
#define ull unsigned long long
#define ios std :: ios :: sync_with_stdio(false)
using namespace std;
const int maxn = 2e5 + 10;
ll t,n;
int main()
{
ios;
cin >> t;
while(t--) {
cin >> n;
ll ans = n + 5; //我這裡直接用的n + 5其實也是一樣做的
cout << ans << endl;
for(ll i = n - 1;i > 1;i--) { //注意這裡要用long long
if((i - 1) * (i - 1) > n) {
cout << i << ' ' << n << endl;
ans --;
}
else if((i - 1) * (i - 1) <= n) {
cout << n << ' ' << i << endl << n << ' ' << i << endl;
n = i; //更換最大值
ans -= 2;
}
}
while(ans > 0) {
cout << 1 << ' ' << n << endl;
ans --;
}
}
return 0;
}
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)