TheForces Round #16 (2^4-Forces) Editorial

Правка en24, от wuhudsm, 2023-06-12 12:47:03

A

code
Solution

If $$$n$$$ is a perfect square number, we find that the square dyeing scheme is always optimal.The answer is $$$4\sqrt{n}$$$.

Otherwise,if $$$n-\lfloor \sqrt{n} \rfloor ^2 \leq \lfloor \sqrt{n} \rfloor$$$,the answer is $$$4\lfloor \sqrt{n} \rfloor+2$$$.Otherwise the answer is $$$4\lfloor \sqrt{n} \rfloor+4$$$.

B

#include<bits/stdc++.h>
#define ll long long int
using namespace std;
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int t; cin >> t;
	while(t--) {
		int n; cin >> n;
		std::vector<vector<int>> v(2);
		std::vector<int> cnt(2*n + 10);
		for(int i = 0; i < 2; i++) {
			v[i].resize(n);
			for(int &u:v[i]) {
				cin >> u;
				cnt[u]++;
			}	
		}
		int mex = 0;
		while(cnt[mex]) mex++;
		int ans = mex * (n&1);
		for(int i = 0; i < n; i++) {
			int val = v[1 ^ (i%2)][i];
			if(!(n&1)) {
				int cur_mex;
				if(val > mex || cnt[val] > 1) cur_mex = mex;
				else cur_mex = val;
				ans = max(ans, cur_mex); 
			}
		}
		cout << ans << "\n";
	}
}

If $$$n$$$ is odd,we can traverse all cells, which is a simple situation.

If $$$n$$$ is even,we can skip one of $$$(1,2) (1,4) (1,6)...(1,n),(2,1),(2,3),(2,5)...(2,n-1)$$$.If there is a duplicate number, skip it. Otherwise, skip the maximum number.

C

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
int  T,n,k;
int  a[N],pre1[N],tot1[N];
char s[N];

void init()
{
	pre1[n+1]=tot1[n+1]=0;
	for(int i=n;i;i--)
	{
		if(a[i])
		{
			pre1[i]=pre1[i+1]+1;
			tot1[i]=tot1[i+1]+1;
		}
		else
		{
			pre1[i]=0;
			tot1[i]=tot1[i+1];
		}
	}
}

int check(int idx,int c1)
{
	return (pre1[idx]<c1)||(pre1[idx]==c1&&tot1[idx]==c1);
}

void solve1()
{
	int c0=(n+k)/2,c1=c0-k;
	for(int i=1;i<=n;i++)
	{
		if(a[i])
		{
			c1--;
			printf("1");	
		}
		else
		{
			if(c0&&check(i+1,c1))
			{
				c0--;
				printf("0");	
			}
			else
			{
				c1--;
				printf("1");
				for(int i=1;i<=c0;i++) printf("0");
				for(int i=1;i<=c1;i++) printf("1");
				break;
			}
		}
	}
	printf("\n");
}

void solve2()
{
	int c0=0,c1=0;
	if(k>0)
	{
		c0=k;
		c0++,c1++;	
		while(c0+c1<=n) c0++,c1++;	
	}
	else
	{
		c1=-k;
		while(c0+c1<=n) c0++,c1++;	
	}
	printf("1");
	c1--;
	for(int i=1;i<=c0;i++) printf("0");
	for(int i=1;i<=c1;i++) printf("1");
	printf("\n");
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	scanf("%d%d%s",&n,&k,s);
    	for(int i=1;i<=n;i++) a[i]=s[i-1]-'0';
    	init();
    	if(n==1&&a[1]==0&&k==1)
    	{
	    	printf("0\n");
	    	continue;
	    }
    	if((n+k)&1) solve2();
    	else
		{
	    	int c0=(n+k)/2,c1=c0-k;
			if(c0<0||c1<0) solve2();
			else
			{
				if(check(1,c1)) solve1();
				else solve2();
			}
	    }
	}
	
	return 0;
}

First,be careful when $$$y=0$$$ and $$$k=1$$$ :)

Consider the answer with a length greater than $$$n$$$, which is always $$$10...01...1$$$.The construction is not hard.

What about the answer with length $$$n$$$?

Consider setting numbers from the highest bit to the lowest bit and current bit is $$$i$$$.If $$$y_i=1$$$,we must set $$$x_i=1$$$.Otherwise($$$y_i=0$$$),we either do set $$$x_i=0$$$ and go to the lower bit,or do set $$$x_i=1$$$, $$$x_{i+1}x_{i+2}...x_n=0...01...1$$$ and break.

For $$$y_i=0$$$,when can we do set $$$x_i=0$$$ and go to the lower bit?The condition is $$$re1>pre1_{i+1}$$$ or $$$re1==pre1_{i+1}$$$ and $$$pre1_{i+1}==tot1_{i+1}$$$.$$$re1$$$ is the current remaining number of $$$1's$$$,$$$pre1_{i+1}$$$ is the length of the continuous $$$1$$$ prefix of $$$y_{i+1}y_{i+2}...y_n$$$,and $$$tot1_{i+1}$$$ is the total of $$$1$$$ of $$$y_{i+1}y_{i+2}...y_n$$$.

D

include<bits/stdc++.h>

define ll long long int

using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { int n, x; cin >> n >> x; int fst = -1; int val = 0; for(int i = 29; i >= 0; i--) { int a = (x >> i)&1; if(!a) { fst = i; break; } val ^= (1 << i); } if(fst + 2 >= n) { cout << x; for(int i = 2; i <= n; i++) { val ^= (1 << (fst — i + 2)); cout << " " << val; } cout << "\n"; } else cout << "-1\n"; } }

Note $$$maxdif(x,y)=max(k)(bit(x,k)!=bit(y,k))$$$.

It can be proved that $$$maxdif(a[i],a[i+1])$$$ is strictly decreasing.

Why?

Consider $$$b_i$$$,$$$k=max(j)(bit(b_i,j)=1)$$$.What about $$$b_{i+1}$$$?First,$$$bit_{j>k}(b_{i+1},j)=0$$$(otherwise,it contradicts the strict decrease of $$$b$$$).Then $$$bit(b_{i+1},k)$$$ must be $$$0$$$.Otherwise,we get $$$bit(a_i,k)!=bit(a_{i+1},k)$$$ and $$$bit(a_{i+1},k)!=bit(a_{i+2},k)$$$,which contradicts the strict increase of $$$a$$$.

Based on the above conclusion, we can make the optimal construction.

Note $$$x=(1...10???)_2$$$,construct $$$a=[(1...10???)_2,(1...110...0)_2,(1...111...0)_2,...,(1...111...1)_2]$$$.

E

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db; 
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
const int LOGN=28;
const ll  TMD=0;
const ll  INF=2147483647;
ll  T,n,m,c;
ll  a[N][N];
ll  dp[N][N];

void init()
{
	scanf("%I64d%I64d%I64d",&n,&m,&c);
	for(int i=1;i<=n;i++)
    	for(int j=1;j<=m;j++)
    		scanf("%I64d",&a[i][j]);
}

void DP()
{
	for(int i=1;i<=n;i++)
	{
		ll maxl[N]={0},maxr[N]={0},left[N]={0},right[N]={0};
		for(int j=1;j<=m;j++) maxl[j]=max(0LL,a[i][j]-2*c+maxl[j-1]);
		for(int j=m;j>=1;j--) maxr[j]=max(0LL,a[i][j]-2*c+maxr[j+1]);
		for(int j=1;j<=m;j++) left[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxl[j-1],left[j-1]+a[i][j]-c);
		for(int j=m;j>=1;j--) right[j]=max(max(0LL,dp[i-1][j]-c)+a[i][j]+maxr[j+1],right[j+1]+a[i][j]-c);
		for(int j=1;j<=m;j++) dp[i][j]=max(left[j]+maxr[j+1],right[j]+maxl[j-1]);
	}
	ll ans=-INF;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			ans=max(ans,dp[i][j]);
	printf("%I64d\n",ans);
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
    	init();
    	DP();
	}
	
	return 0;
}

Consider DP.

Note $$$dp_{i,j}$$$ as the maximum score we can get at the end of $$$(i,j)$$$.

Note $$$lmax_{i,j}=max(0,max_(1 \leq k \leq j)((a_{i,k}-2c)+...+(a_{i,j}-2c)))$$$ and $$$rmax$$$ similarly.

Now consider which cell we go from to $$$(i,j)$$$.There are four situations.

$$$1.$$$ We just start at $$$(i,j)$$$.The answer is $$$a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$2.(i-1,j) \rightarrow (i,j)$$$.The answer is $$$dp_{i-1,j}-c+a_{i,j}+lmax_{i,j-1}+rmax_{i,j+1}$$$;

$$$3.(i,j-1) \rightarrow (i,j)$$$.The answer is $$$left_{i-1,j}-c+a_{i,j}+rmax_{i,j+1}$$$;

$$$4.(i,j+1) \rightarrow (i,j)$$$.The answer is $$$right_{i+1,j}-c+a_{i,j}+lmax_{i,j-1}$$$.

$$$left_{i,j}=max(max(0,dp_{i-1,j}-c)+a_{i,j}+lmax_{i,j-1},left_{i,j-1}-c+a_{i,j})$$$,and $$$right_{i,j}$$$ similarly.

$$$dp_{i,j}$$$ is the maximum value of the answers for the four situations mentioned above.And the final answer is $$$max(dp_{i,j})$$$.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en28 Английский wuhudsm 2023-06-12 12:50:20 2 Tiny change: ' summary="Solution">\' -> ' summary="solution">\'
en27 Английский wuhudsm 2023-06-12 12:50:02 0 (published)
en26 Английский wuhudsm 2023-06-12 12:49:49 36
en25 Английский wuhudsm 2023-06-12 12:49:00 124
en24 Английский wuhudsm 2023-06-12 12:47:03 176 (saved to drafts)
en23 Английский wuhudsm 2023-06-12 12:45:30 3132 (published)
en22 Английский wuhudsm 2023-06-12 12:39:25 6811
en21 Английский wuhudsm 2023-06-12 12:35:46 2800
en20 Английский wuhudsm 2023-06-12 12:32:57 11
en19 Английский wuhudsm 2023-06-12 12:31:48 313 (saved to drafts)
en18 Английский wuhudsm 2023-06-12 12:10:19 2 Tiny change: 'r $y_i=0$,then can we' -> 'r $y_i=0$,when can we'
en17 Английский wuhudsm 2023-06-12 12:07:37 0 (published)
en16 Английский wuhudsm 2023-06-12 12:07:05 131
en15 Английский wuhudsm 2023-06-12 12:05:19 112 Tiny change: 'ons.\n\n$1$. We just s' -> 'ons.\n\n$1.$ We just s'
en14 Английский wuhudsm 2023-06-12 12:01:25 52
en13 Английский wuhudsm 2023-06-12 11:59:55 586
en12 Английский wuhudsm 2023-06-12 11:46:44 9
en11 Английский wuhudsm 2023-06-12 11:45:41 250
en10 Английский wuhudsm 2023-06-12 11:40:37 181
en9 Английский wuhudsm 2023-06-12 11:37:38 13
en8 Английский wuhudsm 2023-06-12 11:36:08 785
en7 Английский wuhudsm 2023-06-12 11:20:08 243
en6 Английский wuhudsm 2023-06-11 19:49:05 56
en5 Английский wuhudsm 2023-06-11 19:48:24 28
en4 Английский wuhudsm 2023-06-11 19:47:49 100
en3 Английский wuhudsm 2023-06-11 19:46:05 45
en2 Английский wuhudsm 2023-06-11 19:44:08 121
en1 Английский wuhudsm 2023-06-11 19:40:02 646 Initial revision (saved to drafts)