[loj2850]无进位加法

（似乎漏了一个数据范围，cf上的题面中还有$\sum L\le 3\cdot 10^{5}$）

考虑$a_{i}=2^{k_{i}}$时（不妨$k_{1}\ge k_{2}\ge ...\ge k_{n}$），记$\sum_{i=1}^{n}b_{i}$的最高位为$L_{b}$，则有$L_{b}=\max_{i=1}^{n}(k_{i}+i-1)$

证明：大于等于$2^{k_{i}}$的$b_{i}$至少要$i$个，因此该值即为下限；取$b_{i}=2^{L_{b}-i+1}\ge 2^{k_{i}}$，因此一定可行

利用上面的这个结论，我们开始考虑正解

如果令$k_{i}$表示$a_{i}$最高的二进制位，那么$2^{k_{i}}\le a_{i}<2^{k_{i}+1}$，取$a'_{i}=2^{k_{i}+1}$，设此时$\sum_{i=1}^{n}b_{i}$的最高为$L_{b}+1$，$a_{i}$减小$b_{i}$不增，因此答案中$\sum_{i=1}^{n}b_{i}$的最高位不超过$L_{b}+1$

令$t=\min_{k_{i}+i=L_{b}}i$，考虑答案（$\sum_{i=1}^{n}b_{i}$）的第$[k_{t},L_{b}+1]$位（共$t+1$位），必然存在$t$位为1（每一个1最多消除一个$a_{i}$，而存在$t$个$a_{i}$最高位大于等于$k_{t}$）

又因为$\forall 1\le i<t,k_{i}+i-1<L_{b}$，即通过这$t$位1中最高的$t-1$位（即使是$L_{b}-i+1$）一定可以，同时也必然会删除$a_{1},a_{2},...,a_{t-1}$

由于$[k_{t},L_{b}+1]$中第$t$个1（从高到低）必然是$k_{t}+1$位或第$k_{t}$位（也有可能都选），判定当第$k_{t}+1$位为0时能否删除$a_{t},a_{t+1},...,a_{n}$，对结果分类讨论：

1.若可以，即最低位可以为$k_{t}$，必然贪心选择令第$[k_{t},L_{b}]$位为1并剩下$a_{t}-2^{k_{t}}$

2.若不可以，则第$[k_{t}+1,L_{b}+1]$位都必须填1，之后将$a_{1},a_{2},..,a_{t}$都删除即可

考虑如何判定，可以再次调用本过程（递归），即在判定过程中顺便求出最小解（若有解，否则返回无解），因此对于第1种情况直接就可以退出，第2种仍要递归下去

时间复杂度很玄学，递归次数大概是$o(L)$的

对于每一次内部，用线段树来维护区间最大值，具体方法如下：

1.对于$i$可以通过插入/删除一个数时，对之后的位置+1或-1来实现

2.对于每一个$a_{i}$，剩余的一定是二进制下的一个后缀，那么将所有数每一个后缀（其实也只需要那一位上有1，否则跟上一个后缀相同）放在一起基数排序，至多为$o(\sum L)$个数

3.对于每一个$a_{i}$，要维护下一个1的位置（预处理）；对于线段树上，维护区间最大值，以及查询第一个最大值并将小于等于其的位置暴力插入，支持单点插入或删除

这样的复杂度再多一个log，总复杂度即为$o((\sum L)\log \sum L)$

  1 #include<bits/stdc++.h>

  2 using namespace std;

  3 #define N 300005

  4 #define oo 0x3f3f3f3f

  5 #define L (k<<1)

  6 #define R (L+1)

  7 #define mid (l+r>>1)

  8 vector<int>v[N];

  9 int n,m,la,rk[N],bit[N],nex[N],top[N],ans[N],f[N<<2],tag[N<<2];

 10 char s[N];

 11 bool cmp(int x,int y){

 12     return rk[x]>rk[y];

 13 }

 14 void upd(int k,int x){

 15     tag[k]+=x;

 16     f[k]+=x;

 17 }

 18 void down(int k){

 19     upd(L,tag[k]);

 20     upd(R,tag[k]);

 21     tag[k]=0;

 22 }

 23 void build(int k,int l,int r){

 24     if (l==r){

 25         f[k]=bit[l]-oo;

 26         return;

 27     }

 28     build(L,l,mid);

 29     build(R,mid+1,r);

 30     f[k]=max(f[L],f[R]);

 31 }

 32 void update(int k,int l,int r,int x,int y,int z){

 33     if ((l>y)||(x>r))return;

 34     if ((x<=l)&&(r<=y)){

 35         upd(k,z);

 36         return;

 37     }

 38     down(k);

 39     update(L,l,mid,x,y,z);

 40     update(R,mid+1,r,x,y,z);

 41     f[k]=max(f[L],f[R]);

 42 }

 43 void query(int k,int l,int r,int x,vector<int>&v){

 44     if (f[k]<0)return;

 45     if (l==r){

 46         v.push_back(l);

 47         return;

 48     }

 49     down(k);

 50     query(L,l,mid,x,v);

 51     if (f[L]!=x)query(R,mid+1,r,x,v);

 52 }

 53 void add(int k){

 54     update(1,1,m,k,k,oo);

 55     if (k<m)update(1,1,m,k+1,m,1);

 56 }

 57 void del(int k){

 58     update(1,1,m,k,k,-oo);

 59     if (k<m)update(1,1,m,k+1,m,-1);

 60 }

 61 bool dfs(int mx){

 62     int lb=f[1];

 63     if (lb<0)return 1;

 64     if (lb>mx)return 0;

 65     vector<int>v;

 66     query(1,1,m,lb,v);

 67     for(int i=0;i<v.size();i++)del(v[i]);

 68     int t=v.back();

 69     if (nex[t])add(nex[t]);

 70     if (dfs(bit[t]-1)){

 71         for(int i=bit[t];i<=lb;i++)ans[i]=1;

 72         return 1;

 73     }

 74     if (nex[t])del(nex[t]);

 75     if ((lb+1<=mx)&&(dfs(bit[t]))){

 76         for(int i=bit[t];i<=lb;i++)ans[i+1]=1;

 77         return 1;

 78     }

 79     for(int i=0;i<v.size();i++)add(v[i]);

 80     return 0;

 81 }

 82 int main(){

 83     scanf("%d",&n);

 84     for(int i=1;i<=n;i++){

 85         scanf("%s",s);

 86         int l=strlen(s);

 87         la=max(la,l);

 88         for(int j=0;j<l;j++)

 89             if (s[j]=='1'){

 90                 m++;

 91                 v[l-j-1].push_back(i);

 92             }

 93     }

 94     for(int i=1;i<=n;i++)rk[i]=m+1;

 95     int mm=m;

 96     for(int i=0;i<la;i++){

 97         sort(v[i].begin(),v[i].end(),cmp);

 98         for(int j=0;j<v[i].size();j++){

 99             bit[mm]=i;

100             rk[v[i][j]]=mm;

101             nex[mm]=top[v[i][j]];

102             top[v[i][j]]=mm--;

103         }

104     }

105     build(1,1,m);

106     for(int i=1;i<=n;i++)add(top[i]);

107     dfs(oo);

108     bool flag=0;

109     for(int i=n+la;i>=0;i--)

110         if ((flag)||(ans[i])){

111             flag=1;

112             printf("%d",ans[i]);

113         }

114 }

巴特西

[loj2850]无进位加法

最新文章

热门文章