当前位置:网站首页>Editorial of Codeforces Round #735 (Div. 2) 部分题解

Editorial of Codeforces Round #735 (Div. 2) 部分题解

2021-07-31 17:52:38 mrclr

传送


A,B,C,D题解。

这场比赛打的稀碎,A题竟然想了40分钟;B题乱搞还过了;最后十几分钟开的D,WA到最后还是没想到\(n=1\)的情况,最近怎么总是各种下饭操作啊。

比赛前我说这场我必涨分,结果真就涨了一分……

A Cherry

这A题就欺负我这种呆瓜,别人都做完三道题了,我才觉得似乎直接取相邻两个就行……
其原因就在于,长区间一定没有两个段区间优,即选\((a_l, a_{l+1},\cdots, a_r)\)还不如选\((a_l,a_{l+1},\cdots,a_{r-1})\)和\((a_{l+1},\cdots, a_{r-1}, a_r)\).枚举最大最小值的位置是否在左右端点既可以得出结论。

所以答案就是\(max\{a_i *a_{i-1} \}(1\leqslant i < n)\).
代码不发了。



B Cobb

这题放在B纯属搞心态,C,D可比这要简单多了。主要是这题的思路以前没遇到过,一种通过最值优化枚举范围的思路。

首先看后面的\(k * (a_i | a_j)\),他的最大值是\(k* 2n\)(比如\(n= 8\),那么\(8 | 7 = 15\),所以最大值不是\(n\)),那么整个式子的最大值一定不小于\(n*(n-1)-2kn\),即\(f(n, n - 1)\).

那么对于任何一个\(f(i, j)\),至少要满足\(i * j > n * (n-1)-2kn\),因此我们在枚举\(j\)的时候,需要满足\(i > \frac{n(n-2k-1)}{j}\)且\(i < j\),而这个时间复杂度是\(O(nk)\)的。因为当\(j=n\)时,\(n-2k-1 < i < n\);而当\(j<n\)时,\(i\)的范围的左边界会变大,右边界会变小,所以枚举区间肯定不会超过\(2k\),因此时间复杂度\(O(kn)\).

上面的思路已经能过这题了,但还可以再优化:观察上面的式子,当\(j \leqslant n - 2k - 1\)时,有\(i \geqslant n\),所以我们只用枚举\([n-2k, n]\)的所有\(j\)即可,这样时间复杂度就是\(O(k^2)\)的了。

主要代码:

ll n, K, a[maxn];
l solve()
{
	ll ans = -INF;
	for(ll j = max(1LL, n - 2 * K); j <= n; ++j)
	    for(ll i = max(1LL, n * (n - 2 * K - 1) / j); i < j; ++i)
		  ans = max(ans, i * j - K * (a[i] | a[j]));
	return ans;
}

   
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.

然后我的乱搞思路是枚举从\(1\)到\(n\)的所有\(j\),再用\(j\)前面\(k\)个\(i\)去更新答案……虽然不能完全涵盖题解的枚举区间,但似乎也很难被卡掉。



C Mikasa

题目要说的是找到最小的非负整数\(x\),使\(x\)没有在\(n \ \ \textrm{XOR} \ \ 0, n \ \ \textrm{XOR} \ \ 1,\cdots, n \ \ \textrm{XOR} \ \ m\)中出现。

换句话说,就是找最小的\(x\),满足\(n \ \ \textrm{XOR} \ \ x > m\)(题解的做法是\(\geqslant m + 1\),不过都一样).

那么我们从高位比,令\(n\)的这一位为\(b_1\),\(m\)的这一位为\(b_2\),然后分情况讨论即可:

如果\(b_1=b_2=1\),那么\(x\)这一位只能填\(0\);
如果\(b_1=0,b_2=1\),那么必须填\(1\);
如果\(b_1=1,b_2=0\),此时填\(0\)结果已经大于\(m\)了,退出;
如果\(b_1=b_2=0\),同理填\(0\).

但这样最后可能会使\(n \ \ \textrm{XOR} \ \ x = m\),因此我们要找到最低位的\(i\),满足\(n,m\)的第\(i\)位都是\(0\),将\(x\)的这一位改成\(1\),并且低位清零即可。

主要代码:

const int N = 31;
In int solve(int n, int m)
{
	int p = 0;
	for(int i = N; i >= 0; --i)
	{
		int t1 = (n >> i) & 1, t2 = (m >> i) & 1;
		if(!t1 && t2) p |= (1 << i);
		else if(t1 &&!t2) break;
	}
	if((p ^ n) == m)
	{
		for(int i = 0; i <= N; ++i)
		{
			int t1 = (n >> i) & 1, t2 = (m >> i) & 1;
			if(!t1 && !t2)
			{
				p |= (1 << i);
				for(int j = 0; j < i; ++j)  //低位清零
				{
					p |= (1 << j);
					p ^= (1 << j);
				}
				return p;
			}
		}
	}
	return p;
}

   
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.
  • 10.
  • 11.
  • 12.
  • 13.
  • 14.
  • 15.
  • 16.
  • 17.
  • 18.
  • 19.
  • 20.
  • 21.
  • 22.
  • 23.
  • 24.
  • 25.
  • 26.
  • 27.
  • 28.
  • 29.


D Diane

这D就更简单了。

先想对于一个长度为5的串aaaaa,a出现了5次,aa出现了4次,aa出现了3次……即奇偶交替出现的,而对于aaaa,会发现他的奇偶交替出现跟aaaaa刚好相反,而奇+偶=奇,那么问题就解决了:如果\(n\)为偶数,我们就可以构造出类似aaaaabaaaa这样的串;如果\(n\)为奇数,在后面添加一个c即可。

然后别忘判断\(n=1\)的情况,说的就是我……

主要代码:

void solve(int n)
{
	int x = n >> 1;
	for(int i = 1; i <= x; ++i) putchar('a');
	if(n > 1) putchar('b');
	for(int i = 1; i < x; ++i) putchar('a');
	if(n & 1) putchar('c');
	puts("");
}

   
  • 1.
  • 2.
  • 3.
  • 4.
  • 5.
  • 6.
  • 7.
  • 8.
  • 9.


E没看,也不会。
 
 
 
 

版权声明
本文为[mrclr]所创,转载请带上原文链接,感谢
https://blog.51cto.com/u_15234622/3241732

随机推荐