Educational Codeforces Round 114

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;
	
}
上一篇:数据结构与算法-生成链表本地环境及合并两个有序链表


下一篇:21. 合并两个有序链表 Java版