A. Regular Bracket Sequences
一道找规律的题,但还是给我整懵逼了,感觉比第二题还难,还是靠队友抬了一手才过的
#include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int n;
cin >> n;
for(int i = 1; i <= n; i++)
{
int j = i, k = i, l = n - i;
while(j--) cout << '(';
while(k--) cout << ')';
while(l--) cout << "()";
cout << endl;
}
}
return 0;
}
B. Combinatorics Homework
一道思维题,我们只需找到最小的相邻的字母对数,和最大的相邻的字母的对数,然后判断给定的m是否在这区间里面即可
最大的十分好求,直接分3块连续的区域:a + b + c - 3
最小的,只要最大的减去其他2个在减1:t1 - t2 - t3 - 1,t1为最大的
#include <iostream>
using namespace std;
int main()
{
int T;
cin >> T;
while(T--)
{
int a, b, c, m;
cin >> a >> b >> c >> m;
int t1 = max(max(a, b), c);
int t2 = min(min(a, b), c);
int t3 = a + b + c - t1 - t2;
int minn = max(t1 - t3 - t2 - 1, 0);
int maxn = a + b + c - 3;
if(m >= minn && m <= maxn) puts("YES");
else puts("NO");
}
return 0;
}
C. Slay the Dragon
算法:二分 + 排序
这道题当时也没做出来,然后早上起来补题时,发现少考虑了几种情况,然后就2个小时一直在完善情况,最后终于就给过了,因为这情况太多,不好书写,详情请看代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 2e5 + 10;
int n, m;
LL a[N];
LL s[N];
int main()
{
cin >> n;
LL sum = 0;
for(int i = 1; i <= n; i++)
{
scanf("%lld", &a[i]);
sum += a[i];
}
sort(a + 1, a + n + 1);
cin >> m;
while(m--)
{
LL x, y;
scanf("%lld%lld", &x, &y);
int l1 = 1, r1 = n;
while(l1 < r1)
{
int mid =l1 + r1 >> 1;
if(x <= a[mid]) r1 = mid;
else l1 = mid + 1;
}
int l2 = 1, r2 = n;
while(l2 < r2)
{
int mid = l2 + r2 + 1 >> 1;
if(x >= a[mid]) l2 = mid;
else r2 = mid - 1;
}
if(sum >= x + y)
{
if(a[l2] >= x) printf("%lld\n", max(y - sum + a[l2], 0LL));
else if(a[l1] <= x) printf("%lld\n", x - a[l1]);
else
printf("%lld\n", min(max(y - sum + a[l1],0LL), x - a[l2]));
}
else
{
if(a[l2] >= x)
printf("%lld\n", y + a[l2] - sum);
else if(a[l1] <= x) printf("%lld\n", max(x - a[l1], x + y - sum));
else
printf("%lld\n", min(max(x - a[l2], x + y - sum), y - sum + a[l1]));
}
}
return 0;
}