当前位置:网站首页>Editorial of codeworks round 735 (Div. 2)

Editorial of codeworks round 735 (Div. 2)

2021-07-31 17:53:41 mrclr

delivery


A,B,C,D Answer key .

The game was a smash ,A I even thought about 40 minute ;B The problem has been fooled around ; In the last ten minutes D,WA In the end, I didn't expect \(n=1\) The situation of , How come there are always various meal operations recently .

Before the game, I said I would raise points , As a result, it really rose by one point ……

A Cherry

this A The problem is bullying a fool like me , Everyone else has finished three questions , I just think it's OK to take two adjacent ones directly ……
The reason is , There must be no two segments in a long interval , Immediate selection \((a_l, a_{l+1},\cdots, a_r)\) You might as well choose \((a_l,a_{l+1},\cdots,a_{r-1})\) and \((a_{l+1},\cdots, a_{r-1}, a_r)\). It can be concluded by enumerating whether the position of the maximum and minimum values is at the left and right endpoints .

So the answer is \(max\{a_i *a_{i-1} \}(1\leqslant i < n)\).
The code is not sent .



B Cobb

This question is placed in B Pure mentality ,C,D It's much simpler than that . The main reason is that the idea of this question has not been met before , An idea of optimizing the enumeration range through the maximum value .

First look at the back \(k * (a_i | a_j)\), His maximum is \(k* 2n\)( such as \(n= 8\), that \(8 | 7 = 15\), So the maximum is not \(n\)), Then the maximum value of the whole equation must not be less than \(n*(n-1)-2kn\), namely \(f(n, n - 1)\).

So for any one \(f(i, j)\), At least to meet \(i * j > n * (n-1)-2kn\), So we're enumerating \(j\) When , Need to meet \(i > \frac{n(n-2k-1)}{j}\) And \(i < j\), And the time complexity is \(O(nk)\) Of . Because when \(j=n\) when ,\(n-2k-1 < i < n\); And when \(j<n\) when ,\(i\) The left boundary of the range will become larger , The right boundary will become smaller , So the enumeration interval must not exceed \(2k\), So time complexity \(O(kn)\).

The above ideas have been able to pass this question , But it can also be optimized : Look at the formula above , When \(j \leqslant n - 2k - 1\) when , Yes \(i \geqslant n\), So we just enumerate \([n-2k, n]\) All of the \(j\) that will do , So the time complexity is \(O(k^2)\) Of course. .

Main code :

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.

Then my fooling idea is to enumerate from \(1\) To \(n\) All of the \(j\), Reuse \(j\) front \(k\) individual \(i\) To update the answer …… Although it can not completely cover the enumeration interval of the problem solution , But it seems hard to get stuck .



C Mikasa

The topic is to find the smallest nonnegative integer \(x\), send \(x\) Not in the \(n \ \ \textrm{XOR} \ \ 0, n \ \ \textrm{XOR} \ \ 1,\cdots, n \ \ \textrm{XOR} \ \ m\) It appears that .

let me put it another way , Is to find the smallest \(x\), Satisfy \(n \ \ \textrm{XOR} \ \ x > m\)( The solution to the problem is \(\geqslant m + 1\), But it's all the same ).

So let's go from high to high , Make \(n\) This one is \(b_1\),\(m\) This one is \(b_2\), Then discuss it according to the situation :

If \(b_1=b_2=1\), that \(x\) This one can only fill in \(0\);
If \(b_1=0,b_2=1\), Then you must fill in \(1\);
If \(b_1=1,b_2=0\), Fill in \(0\) The result has been greater than \(m\) 了 , sign out ;
If \(b_1=b_2=0\), Similarly, fill in \(0\).

But this may eventually make \(n \ \ \textrm{XOR} \ \ x = m\), So we have to find the lowest \(i\), Satisfy \(n,m\) Of the \(i\) All places are \(0\), take \(x\) Change this one to \(1\), And the low bit is cleared .

Main code :

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)  // Zero low 
				{
					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

this D It's even simpler .

Let's start with a length of 5 String of aaaaa,a There is 5 Time ,aa There is 4 Time ,aa There is 3 Time …… That is, parity alternates , And for aaaa, You'll find his parity alternating with aaaaa Just the opposite , And strange + accidentally = p. , Then the problem is solved : If \(n\) For the even , We can construct something like aaaaabaaaa This string ; If \(n\) It's odd , Add a c that will do .

Then don't forget to judge \(n=1\) The situation of , It's about me ……

Main code :

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 Didn't see , Not even .
 
 
 
 

版权声明
本文为[mrclr]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/07/20210731175236372g.html