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

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		if(n%6==1)
		{
			for(int i=1;i<n/6;i++) printf("0");
			printf("8\n");
			continue;
		}
		for(int i=1;i<=n/6;i++) printf("0");
		if(n%6==2) printf("1\n");
		else if(n%6==3) printf("7\n");
		else if(n%6==4) printf("4\n");
		else if(n%6==5) printf("2\n");
		else printf("\n");
	}
	
	return 0;
}

If $$$n=6k$$$,print $$$0...0$$$;

If $$$n=6k+1$$$,print $$$0...08$$$;

If $$$n=6k+2$$$,print $$$0...01$$$;

If $$$n=6k+3$$$,print $$$0...07$$$;

If $$$n=6k+4$$$,print $$$0...04$$$;

If $$$n=6k+5$$$,print $$$0...05$$$;

If $$$n=6k+6$$$,print $$$0...09$$$.

#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];

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&k);
		for(int i=1;i<=k;i++) a[i]=0;
		for(int i=1;i<=k;i++)
		{
			if(n<2) break;
			a[i]=1;
			n-=2; 
		} 
		for(int i=k;i;i--)
		{
			if(a[i])
			{
				if(n>=4) a[i]=9,n-=4;
				else if(n>=1) a[i]=7,n--;
				else break;
			}
		}
		for(int i=k;i;i--) if(a[i]) printf("%d",a[i]);
		printf("\n");
	}
	
	return 0;
}

First,maximize number of digits — fill each digit with $$$'1'$$$.

Then starting from the highest bit,consider maximizing the current digit — consider changing the current bit to $$$'9'$$$. If no enough matchsticks, consider $$$'7'$$$.

Luckily,you find $$$[1,2n,2,2n-1,...,n,n+1]$$$ works :)

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

int main()
{
	//freopen("test.in","r",stdin);
	srand(1);
	
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
	    for(int i=1,j=2*n;i<=n;i++,j--) printf("%d %d ",i,j);
	    printf("\n");
	}
	

	return 0;
}

#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,x;

int check(vector<int> v)
{
	sort(v.begin(),v.end());
	for(int i=1;i<=n*2;i++) if(v[i]!=i) return 0;
	return 1;
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d",&n,&x);
		ll S=(ll)n*(2*n+1),a=2*n+1,b,flg=0;
		for(int i=x;i<=x;i++)
		{
			for(int j=1;j<=2*n;j++)
			{
				if((S-i-j)%(n-1)) continue;
				b=(S-i-j)/(n-1); 
				vector<int> v;
				v.push_back(0);
				v.push_back(i);
				for(int i=2;i<n*2;i++)
				{
					if(i&1) v.push_back(b-v.back());
					else    v.push_back(a-v.back());
				} 
				v.push_back(j);
				if(check(v))
				{
					for(int k=1;k<=n*2;k++) printf("%d%c",v[k],k==n*2?'\n':' ');
					flg=1;
					break;
				}
			} 
		} 
		if(!flg) printf("-1\n");
	}
	
	return 0;
}

Note $$$s_1=p_1+p_2=p_3+p_4=...=p_{2n-1}+p_{2n},s_2=p_2+p_3=p_4+p_5=...=p_{2n-2}+p_{2n-1}$$$.

We can easily get $$$s_1=2n+1$$$.

Consider fix $$$s_2$$$,we can get:$$$p_{2n}=n*s_1-p_1-(n-1)s_2$$$.Since $$$1\leq p_{2n} \leq 2n$$$, we found that there are no more than $$$3$$$ suitable $$$s_2$$$.

For each suitable $$$s_2$$$,we can calculate the whole array,and check if it’s a permutation in $$$O(n)$$$.

Consider a $$$3*3$$$ matrix,we can do something like:

$$$000$$$

$$$000$$$

$$$000$$$

$$$->$$$

$$$100$$$

$$$010$$$

$$$101$$$

$$$->$$$

$$$101$$$

$$$000$$$

$$$000$$$

Consider we can only flip $$$a_{x,y},a_{x,y+2}$$$ and $$$a_{x,y},a_{x+2,y}$$$,what about the answer?

Note $$$x_0=a_{1,1}⊕a_{1,3}⊕...,x_1=a_{1,2}⊕a_{1,4}⊕...$$$,the answer is $$$YES$$$ if and only if the $$$x_0=x_1=0$$$.

Let's go back to the original problem.The only difference is there are some unaccessable elements.Just do special judgment.

If $$$n=3,m=3$$$,unaccessable elements are $$$a_{1,2},a_{2,1},a_{2,3},a_{3,2}$$$;

If $$$n=3,m=4$$$,unaccessable elements are $$$a_{2,1},a_{2,4}$$$;

If $$$n=4,m=3$$$,unaccessable elements are $$$a_{1,2},a_{4,2}$$$.

Define free nodes $$$x$$$ — $$$free[x]=1$$$ means we can freely flip $$$x,fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0;

Define $$$col[x]$$$ — the value when node $$$x$$$ does not affect $$$fa[x]$$$,on the premise that we change all the descendant nodes(exclude itself) of $$$x$$$ to 0.Later on, we can see that this value is unique.

We update the values of $$$free[x],col[x]$$$ from bottom to top.

Case $$$1$$$:$$$x$$$ has $$$0$$$ son nodes.It's easy to get $$$free[x]=0,col[x]=a[x]$$$.

Case $$$2$$$:$$$x$$$ has $$$1$$$ son nodes.

We get $$$free[x]=0$$$.

If $$$col[son[x][0]]=0$$$,we don't need to flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]$$$;

If $$$col[son[x][0]]=1$$$ and $$$free[son[x][0]]=0$$$,no solution.Otherwise we must flip $$$son[x][0]$$$ and $$$x$$$,$$$col[x]=a[x]⊕1$$$;

Case $$$3$$$:$$$x$$$ has $$$>2$$$ son nodes.

Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$x$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[x][i]$$$,no solution.

If we can change all the descendant nodes(exclude itself) of $$$x$$$ to 0,$$$x$$$ is always a free node.

Let's calculate $$$col[x]$$$.If $$$tagc=1$$$,we must flip $$$x$$$ and a free node,so $$$col[x]=a[x]⊕1$$$.If $$$tagc=0$$$,$$$col[x]=a[x]⊕0$$$.

Case $$$4$$$:$$$x$$$ has $$$2$$$ son nodes.

If $$$son[x][1],son[x][2]$$$ are both not free nod:

• if $$$col[son[x][1]]⊕col[son[x][2]]=1$$$,no solution;

• if $$$col[son[x][1]]=col[son[x][2]]=0$$$,$$$free[x]=0,col[x]=a[x]$$$;

• if $$$col[son[x][1]]=col[son[x][2]]=1$$$,$$$free[x]=0,col[x]=a[x]⊕1$$$,and flip $$$a[fa[x]]$$$;

If $$$son[x][1],son[x][2]$$$ are both free node,$$$free[x]=1,col[x]=a[x]⊕col[son[x][1]]⊕col[son[x][2]]$$$.

Otherwise,do similar casework :)

Finally(I promise),let's check the answer,for all son nodes of node $$$1$$$:

Note $$$tagc$$$ as the xor value of col values of all child nodes of $$$1$$$.If $$$tagc=1$$$ and there're no free nodes in $$$son[1][i]$$$,no solution.

Otherwise,we should check $$$a[1]⊕tagc$$$.The answer is $$$YES$$$ if and only if $$$a[1]⊕tagc=0$$$.

Obviously,the length of a continuous segment with a negative contribution is $$$1$$$.

We can write a $$$O(n^2)$$$ DP:

$$$dp[i]=max(dp[j]-a[j+1]+a[j+2]|...|a[i])$$$

Then we notice there're at most $$$O(log maxa)$$$ different values in $$$a[j]|...|a[i]$$$ $$$(j<i)$$$.It's a classic conclution.

For a fix $$$a[j]|...|a[i]$$$ $$$=t$$$,we get $$$dp[i]=max(dp[j]-a[j+1])+t$$$.Since the value range of $$$j$$$ is continuous,we can use a segment tree to maintain it.It's $$$O(n log^2 n)$$$.

In fact,use prefix maximum value is enough.Note $$$premax[i]=max(dp[1]-a[2],...,dp[i]-a[i+1])$$$,$$$dp[i]=premax[j]+t$$$.It's $$$O(n log n)$$$.

This has prepared us for solving F2(solution2).

You need to observation that the length of consecutive segments will not exceed $$$60$$$.

Then we can use a scrolling array for DP.