Codeforces Round ＃809 Editorial(A,B,C)

A. Another String Minimization Problem

The question ： You have a length of n Sequence a1,a2,...,an, from 1 To m Between integers , You also have a string s, from m Characters B form . You need to do the following n Operations .

In the i Time （1≤i≤n） In operation , Do you use A Replace s Of the ai Or （m+1-ai） Characters , You can replace characters in any position multiple times .
Find out after these operations , The smallest musical string you can get .

If and only if x and y Different first position , character string x There is a letter in the alphabet more than y The corresponding letter in is earlier , Then the string x A string smaller than the same length in the dictionary y.

Ideas ： Deal with it from the beginning as required , Give priority to those in the front , If the position in front is already A 了 , Then turn the one at the back into A.

Code ：

#include <iostream>
 
using namespace std;
 
const int N = 60;
 
int t, n, m, a[N];
char c[N];
 
int main()
{
	cin >> t;
	while(t -- )
	{
		cin >> n >> m;
		for(int i = 1; i <= m; i ++ ) c[i] = 'B';
		for(int i = 1; i <= n; i ++ ) cin >> a[i];
		
		for(int i = 1; i <= n; i ++ )
		{
			int x1 = a[i], x2 = m + 1 - a[i];
			int x3 = min(x1, x2), x4 = max(x1, x2);
			if(c[x3] != 'A') c[x3] = 'A';
			else c[x4] = 'A';
		}
		for(int i = 1; i <= m; i ++ ) cout << c[i];
		cout << endl;
	}
	return 0;
}

B. Making Towers 

The question ： You have one by n A sequence of color blocks . The first i The color of the blocks is ci, yes 1 To n An integer between . You will place building blocks on an infinite coordinate grid in the following way .
first , You put a piece 1 Put it in （0,0） It's about .
about 2≤i≤n, If the first （i-1） Blocks are placed in position （x,y）, So the first i Blocks can be placed in position （x+1,y）、（x-1,y）、（x,y+1） One of （ But it cannot be placed in position （x,y-1））, As long as no block has been placed in this position before .
A tower is made of s Composed of blocks , These blocks are placed in (x,y),(x,y+1),...,(x,y+s-1) Location , For a location （x,y） And integer s. The color is r The tower of is a tower , All of them have r The color of the .
From 1 To n Every color of r, Solve the following problems independently .

Find out what can be formed by placing blocks according to rules r The maximum size of the color tower .

Ideas ： We can find out , If two wooden blocks of the same color are to be placed next to each other , Then these two towers must be separated by an even number of other blocks or no other number in the middle , Only in this way can it be placed right next to each other . Then you can find , The problem is to find the sequence with the same color , And the subscript parity of two adjacent numbers is different . We don't need a double loop to enumerate all from ai The maximum length at the beginning , Because we consider ai hinder aj and ak,j < k, here ai It can be followed by aj and ak, If the optimal solution is ak, Then we can transform the optimal solution into a connection aj, because aj and ak It can be connected to ai Back , So at this time aj and ak The subscripts of are the same , that ak The sequence of the later optimal solution can also be connected to aj Back , So we don't need a double cycle , But greedy to find aj, If aj and ai Parity is different , Then choose aj, Then at this time j As the end, continue to find .

The code is as follows ： 

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

int t, f[N][2], color[N], n;

int main()
{
	scanf("%d", &t);
	while(t -- )
	{
		scanf("%d", &n);
		for(int i = 1; i <= n; i ++ ) scanf("%d", &color[i]);
		for(int i = 1; i <= n; i ++ ) f[i][0] = f[i][1] = 0;
		
		for(int i = 1; i <= n; i ++ )
		{
			f[color[i]][i & 1] = f[color[i]][(i & 1) ^ 1] + 1;
		//	printf("f[%d][%d] = f[%d][%d] + 1 = %d\n", color[i], i & 1, color[i], (i & 1) ^ 1, f[color[i]][i & 1]);
		}
		for(int i = 1; i <= n; i ++ )
		cout << max(f[i][1], f[i][0]) << ' ';			// I'm not sure whether it ends odd or even , So take max Simplify the procedure  
		cout << endl;
	}
	return 0;
}

C. Qpwoeirut And The City

The question ：Qpwoeirut Have begun to learn architecture , And ambitiously decided to transform his city .

Qpwoeirut The city of can be described as a row n building , Among them the first i building （1≤i≤n） The height of the building is hi layer . You can assume that the height of each floor in this problem is equal . therefore , If and only if architecture i Number of floors hi Larger than building j Number of floors hj when , Architecture i It's better than architecture j high .

If i Building No i-1 Building and i+1 Building is high （ And there are ）, that i Building is cool . Please note that , The first 1 Donghedi n No building can be cool .

In order to transform the city ,Qpwoeirut We need to maximize the number of cool buildings . To do this ,Qpwoeirut Additional floors can be built on top of any building , To make it higher . Be careful , He cannot demolish the existing floor .

Because building new floors is expensive ,Qpwoeirut Hope to minimize the number of floors he built . find Qpwoeirut The minimum number of floors to be built , To maximize the number of cool buildings .

Input：

6
3
2 1 2
5
1 2 1 4 3
6
3 1 4 5 5 2
8
4 2 1 3 5 3 6 1
6
1 10 1 1 10 1
8
1 10 11 1 10 11 10 1

Output:

2
0
3
3
0
4

Ideas ： Odd numbers are certain , It's from 2 Start with an interval of get The difference between . Even numbers are uncertain , such as

4 2 1 3 5 3 6 1

4 2 1 3 5 3 6 1

4 2 1 3 5 3 6 1

4 2 1 3 5 3 6 1

Easy to find , For even numbers , It has a free space for one , This leads to the last position being moved back one bit , Get the sequence 2

In the sequence 2 Move the penultimate number back on the basis of 1 position , Get the sequence 3…………, Until you move the first position back 1 position . So we have to deal with O(n) Time , Sequence 2 Is in the sequence 1 On the basis of , The last one is different , So subtract the value added by the last digit , And then add the value of the last bit movement . Get the sequence 3 Number of blocks required , By analogy , Can be in O(n) Find out all the situations in the time , And then use ans Take the maximum to save .

The code is as follows ：

#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
const int N = 100100;

int t, n;
ll a[N];

ll get(int i) 
{
  return max(0ll, max(a[i - 1], a[i + 1]) - a[i] + 1);
}

int main() 
{
	scanf("%d", &t);
	while (t--) 
	{
		scanf("%d", &n);
    	for (int i = 1; i <= n; i++) cin >> a[i];
		if (n & 1) 
		{
			
    		ll ans = 0;
    		for (int i = 2; i < n; i += 2)
   		 	ans += get(i);
		
   		 	cout << ans << endl;
    		continue;
   		}

 	    ll tot = 0;
 	    for (int i = 2; i < n; i += 2)
 	    tot += get(i);
	
	    ll ans = tot;
  	    for (int i = n - 1; i > 1; i -= 2) 
	    {
    		tot -= get(i - 1);
    		tot += get(i);
    		ans = min(ans, tot);
        }

   		cout << ans << endl;
    }
}