#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,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$$$.
Consider changing $$$s_2$$$ by $$$1$$$,then $$$p_{2n}$$$ will change $$$n-1$$$.
For each suitable $$$s_2$$$,we can calculate the whole array,and check if it’s a permutation in $$$O(n)$$$.
#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=1010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n,m;
int t[N];
int a[N][N],b[N][N],c[N][N];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
c[i][j]=(a[i][j]^b[i][j]);
t[0]=t[1]=0;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
t[(i+j)&1]^=c[i][j];
if(n==3&&m==3&&(c[1][2]||c[2][1]||c[2][3]||c[3][2])) printf("NO\n");
else if(n==3&&m==4&&(c[2][1]||c[2][4])) printf("NO\n");
else if(n==4&&m==3&&(c[1][2]||c[4][2])) printf("NO\n");
else printf("%s\n",(t[0]||t[1])?"NO":"YES");
}
return 0;
}
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$$$.
If you don't know, it means you haven't read #11 F's editorial
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}$$$.
#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,flg;
int a[N],fre[N];
vector<int> G[N],ch[N];
void DFS(int x,int pr)
{
for(int i=0;i<G[x].size();i++)
{
int y=G[x][i];
if(y==pr) continue;
ch[x].push_back(y);
DFS(y,x);
}
if(x==1) return ;
if(ch[x].size()==0) fre[x]=0;
else if(ch[x].size()==1)
{
fre[x]=0;
if(a[ch[x][0]]&&fre[ch[x][0]]) a[x]^=1;
else if(a[ch[x][0]]&&(!fre[ch[x][0]])) flg=0;
}
else if(ch[x].size()==2)
{
if(fre[ch[x][0]]||fre[ch[x][1]])
{
a[x]^=(a[ch[x][0]]^a[ch[x][1]]);
if(fre[ch[x][0]]&&fre[ch[x][1]]) fre[x]=1;
else
{
fre[x]=0;
if(a[ch[x][0]]&&a[ch[x][1]]) a[x]^=1,a[pr]^=1;
else if(a[ch[x][0]]&&(!fre[ch[x][0]])) a[x]^=1,a[pr]^=1;
else if(a[ch[x][1]]&&(!fre[ch[x][1]])) a[x]^=1,a[pr]^=1;
}
}
else
{
fre[x]=0;
if(a[ch[x][0]]^a[ch[x][1]]) flg=0;
else a[x]^=a[ch[x][0]],a[pr]^=a[ch[x][0]];
}
}
else
{
int tagf=0,taga=0;
for(int i=0;i<ch[x].size();i++) tagf|=fre[ch[x][i]],taga^=a[ch[x][i]];
if((!tagf)&&taga) flg=0;
else fre[x]=1,a[x]^=taga;
}
}
void check1()
{
int taga=0;
for(int i=0;i<ch[1].size();i++) if((!fre[ch[1][i]])&&a[ch[1][i]]) flg=0;
for(int i=0;i<ch[1].size();i++) taga^=a[ch[1][i]];
if(taga^a[1]) flg=0;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) G[i].clear(),ch[i].clear();
for(int i=1;i<n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
flg=1;
DFS(1,0);
check1();
printf("%s\n",flg?"YES":"NO");
}
return 0;
}
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.
We can do flip $$$x,fa[x],son[x][1],son[x][2]$$$,flip $$$x,fa[x],son[x][2],son[x][3]$$$ and flip $$$x,fa[x],son[x][1],son[x][3]$$$ to only flip $$$x,fa[x]$$$.
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)$$$.
For $$$k>2,dp[j]-a[j+1]+(a[j+k]|...|a[i]) \leq dp[j]-a[j+1]+(a[j+2]|...|a[i])$$$
We can see adding some 'illegal' transfers will not make the solution bigger.
This has prepared us for solving F2(solution2).
#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=110;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n;
int a[N],pre[N];
ll dp[N];
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
for(int i=0;i<N;i++) dp[i]=pre[i]=0;
for(int i=1;i<=n;i++)
{
int cur=0;
scanf("%d",&a[i%N]);
pre[i%N]=(pre[(i-1+N)%N]|a[i%N]);
dp[i%N]=pre[i%N];
for(int j=i;j>=max(3,i-60);j--)
{
cur|=a[j%N];
dp[i%N]=max(dp[i%N],dp[(j-2+N)%N]-a[(j-1+N)%N]+cur);
}
}
printf("%I64d\n",dp[n%N]);
}
return 0;
}
You need to observation that the length of consecutive segments will not exceed $$$60$$$.
Consider $$$a[L...R]$$$ $$$(R-L+1>60)$$$ ,there $$$>30$$$ such index $$$k$$$ satisfy $$$(a[k]|a[k+1]|...|a[R])=(a[k+1]|...|a[R])$$$;
Now let's consider such $$$>30$$$ such index $$$k$$$.
If $$$(a[L]|a[L+1]|...a[k-1])=(a[L]|a[L+1]|...a[k-1]|a[k])$$$ also holds,make partision $$$[a[L],...a[k-1]]$$$ ||| $$$[a[k]]$$$ ||| $$$[a[k+1],...a[R]]$$$ is better.
Otherwise we can infer $$$(a[L]|a[L+1]|...a[k-1])!=(a[L]|a[L+1]|...a[k-1]|a[k])$$$;
But there $$$>30$$$ such index $$$k$$$,contradiction.
Then we can use a scrolling array for DP.
