# Editorial of codeworks round 735 (Div. 2)

2021-07-31 17:53:41 mrclr

delivery

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 .

https://chowdera.com/2021/07/20210731175236372g.html