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=)