Educational Codeforces Round 101 (Rated for Div. 2)

A - Regular Bracket Sequence

给定只含'(' ')' '?'的字符串,?可以替换成'('或')',问能否通过替换使得成为合法的括号序列,如(()),(()())。

完全想复杂了,一直在想?​怎么具体替换成括号,其实只需要特判一下就行。

  • 长度若为奇数,则一定不行。
  • 开头如果是')',则一定不行。
  • 结尾如果是'(',则一定不行。

B - Red and Blue

给定\(n+m\)个数\(a_1, a_2, \dots, a_{n + m}\),其中\(n\)个染成红色\(r_1, r_2, \dots, r_n\),\(m\)个染成蓝色\(b_1, b_2, \dots, b_m\),\(r_i,b_i\)顺序为在\(a\)中的相对顺序。

给定\(r_1, r_2, \dots, r_n,b_1, b_2, \dots, b_m\),要求最大化:

\[f(a) = \max(0, a_1, (a_1 + a_2), (a_1 + a_2 + a_3), \dots, (a_1 + a_2 + a_3 + \dots + a_{n + m})) \]

读题没读清楚,写到一半莫名其妙写成另外一个题了(大雾

要求最大化的是\(a\)中的某一个前缀,不是某一个连续子序列,而且答案不能是负数

把\(r_1, r_2, \dots, r_n\)的最大前缀和\(b_1, b_2, \dots, b_m\)最大前缀相加即可

因为\(r\)和\(b\)是按照在\(a\)中的相对位置,所以把他们两个的最大前缀排在最前面,剩下的随便排在后面即可

C - Building a Fence

有\(n\)个高度为\(k\)的栅栏,宽都是\(1\),地面的高度为\(h_i\),栅栏可以放在地面上,也可以浮空(最多浮空高度为\(k-1\)),第\(1\)个和第\(n\)个栅栏必须在地面上,问能不能使得每个栅栏之间都有边。

看完题之后感觉思路应该是计算出每个栅栏的区间,但是我竟然把每个栅栏能取值(无论合法与否)的区间求出来然后判断了..........

正确思路应该是从第一个区间开始往后退,每一个合法区间的下界和上界。

第一个栅栏最大为\(maxn_1=h[1]+k\),最小\(minn_1=h[1]\),第二个为\(minn_2=max(h[2],minn_1-k+1)\)第二项加\(1\)是因为至少要有长\(1\)的边,\(maxn_2=min(h[2]+2*k-1,maxn_1+k-1)\),第一项是浮空\(k-1\),第二项是和上一次最大值只有\(1\)的边

只需要判断一下中途会不会出现\(maxn_i<minn_i\),\(maxn-k<h[i]\),\(minn>h[i]+k-1\),然后看一下最后一个能不能在地面上即可

const int N = 2e5 + 2020;
int T, n, k, h[N]; 
int main()
{
	T = read();
	while(T--){
		n = read(), k = read();
		for(int i = 1; i <= n; ++i) h[i] = read();
		int maxn = 0, minn = 0;
		int flag = 1;
		for(int i = 1; i <= n; ++i){
			if(i == 1){
				maxn = h[1] + k;
				minn = h[1];
			}
			else {
				minn = max(h[i], minn - k + 1);
				maxn = min(h[i] + 2 * k - 1, maxn + k - 1); 
			}
			if(maxn < minn || minn > h[i] + k - 1 || maxn - k < h[i]){
				flag = 0;
				break;
			}
		}
		if(minn != h[n]) flag = 0;
		if(flag == 0) cout << "NO";
		else cout << "YES";
		puts("");
	}
	return 0;
}

D - Ceil Divisions

思维题

你有一个数组 \(1,2,3,4,....,n\)。每次可以选择\(x\)和\(y(x≠y)\),使得\(a_x = \left\lceil \frac{a_x}{a_y} \right\rceil\),你的目标是在不超过\(n+5\)步的情况下使数组由\(n-1个1\)和\(1\)个\(2\)组成。输出每一步

  • 方法一

容易发现,我们可以比较简单的把\([3,n)\)变成\(1\),只需要把他们都除以\(n\)(上取整)即可

此时只剩下\(1,2,1,...,n\),已经用了\(n-3\)步,现在我们要处理掉\(n\),只能\(n/2\),需要\(log_2n\)次,不符合题目步数限制。

我们可以考虑如何处理\(n\),注意到\(\sqrt{n}\)最多才\(5\)次,所以可以把\(\sqrt{n}\)求出来,单独放到一个集合\(b\)里面,对于\([3, n) \cap \complement_{\mathrm{U}} b\)直接除以\(n\),\(b\)中元素(注意除去\(2\))和前一个除两次变成\(1\),

  • 方法二

一个更简单的方法

首先通过\(i\)除以\(n\)的方法把\([3,n)\)变成\(1\)(注意不包括8),然后把\(n\)除以\(8\),把\(n\)变成\(1\),最后对\(8\)进行3次除以\(2\),把\(8\)变成\(1\)

一共需要:第一步\(n-4\)次+第二步\(6\)次(\(n_{max}=2e5<262144\))+第\(3\)步\(3\)次\(=n+5\)

参考代码非常不简洁

const int N = 2e5 + 15;
int T, n;
struct node{
	int x, y;
}ans[N];

int main()
{
	T = read();
	while(T--){
		n = read();
		if(n <= 8){
			int cnt = 0;
			if(n == 3){
				printf("2\n3 2\n3 2\n");
				continue;
			}
			for(int i = 3; i <= n - 1; ++i){
				ans[++cnt].x = i;
				ans[cnt].y = n;
			}
			int tmp = n;
			while(tmp != 1){
				tmp = ceil(tmp * 1.0 / 2.0);
				ans[++cnt].x = n;
				ans[cnt].y = 2;
			}
			cout << cnt << '\n';
			for(int i = 1; i <= cnt; ++i)
				printf("%d %d\n", ans[i].x, ans[i].y);
		}
		else{
			int cnt = 0;
			for(int i = 3; i <= n - 1; ++i){
				if(i == 8) continue;
				ans[++cnt].x = i;
				ans[cnt].y = n;
			}
			int tmp = n;
			while(tmp != 1){
				tmp = ceil(tmp * 1.0 / 8.0);
				ans[++cnt].x = n;
				ans[cnt].y = 8;
			}
			for(int i = 1; i <= 3; ++i){
				ans[++cnt].x = 8;
				ans[cnt].y = 2;
			}
			cout << cnt << '\n'; 
			for(int i = 1; i <= cnt; ++i)
				printf("%d %d\n", ans[i].x, ans[i].y);
		}
	}
	return 0;
}

上一篇:P2073 送花


下一篇:第十二关——2012提高组真题