#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 \gt 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 \gt 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})$$$.
When we skip duplicate, it wont affect the answer.
Why we must skip max number?
If array was 0,1,2,3,4,...max, we will choose max, and mex will decrease by 1. Its optimal.
Else if we will choose max, it wont affect the answer.
max value among those indices mentioned in editorial?
yes, "Otherwise, skip the maximum number." i wanted to proof why its right.
In Problem B my solution is same with tutorial. And unfortunately test cases are hidden.
EDIT: I found my mistake
Why test cases are hidden?
if there are some duplicate in indixes, and repeats in whole table, u need to choose it
wuhudsm Can You Open Hidden TestCases For Upsolving?
Sorry, it is not possible to show test data in all gym contests
209959878 can someone pls point out the mistake.pls..
Checker comment wrong output format Expected integer, but "4e+009" found