#include <bits/stdc++.h>
using namespace std;

#define int long long

void test_case() {
	int n; cin >> n;
	int a = floor(sqrt(n));
	int b = (n + a - 1) / a;
	cout << a * 2 + b * 2 << '\n';
}

int32_t main() {
	ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--) test_case();
}

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$$$.

#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.

#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$$$.

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.

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]$$$.

#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})$$$.