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