一、题目
二、解法
首先思考这题怎么修改，因为有用的位只有 \(\tt lowbit\)，我们会把 \(\tt lowbit\) 小的 \(b\) 异或上 \(\tt lowbit\) 大的 \(a\) 达到让总和减少的目的，明白这一点之后就可以做没有元素同时在 \(A,B\) 中出现这个部分分了。
特殊情况是 \(a=b\) 可以减少的量是 \(lowbit(a)\)，你可能会想讨论但这东西影响确实太大了，难做。
换个思路，考虑现在问题的本质其实是一个带权匹配模型，而且只有两种边：\(a=b\) 减少 \(lowbit(a)\)；\(lowbit(a)>lowbit(b)\) 减少 \(lowbit(a)-lowbit(b)\)
不知道你发现了吗，本题的边权值只和 \(lowbit(x)\) 有关，而只有 \(30\) 种不同的 \(lowbit\)，这启示我们可以按 \(lowbit\) 划分等价类，还是原来费用流的图，我们把容量修改一下就可以随便跑了。
三、总结
划分等价类真是重要的思想，原来它不只可以应用到 \(dp\) 上。我觉得它的本质是观察代价和什么量有关，然后找变量之间的平行关系，能达到优化复杂度的目的。
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
using namespace std;
const int M = 1200005;
const int N = 105;
const int inf = 0x3f3f3f3f;
#define ll long long
int read()
{
int x=0,f=1;char c;
while((c=getchar())<‘0‘ || c>‘9‘) {if(c==‘-‘) f=-1;}
while(c>=‘0‘ && c<=‘9‘) {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,k,ca[N],cb[N],cc[N];ll dis[N],ans;
int tot,S,T,f[N],pre[N],lst[N],flow[N],in[N];
map<int,int> mp1,mp2;
struct edge
{
int v,c,f,next;
}e[N*N];
void add(int u,int v,int c,int fl)
{
e[++tot]=edge{v,c,fl,f[u]},f[u]=tot;
e[++tot]=edge{u,-c,0,f[v]},f[v]=tot;
}
int bfs()
{
queue<int> q;
for(int i=0;i<=T;i++) dis[i]=-1e18;
flow[S]=inf;pre[S]=lst[S]=dis[S]=0;
q.push(S);in[S]=1;
while(!q.empty())
{
int u=q.front();q.pop();in[u]=0;
for(int i=f[u];i;i=e[i].next)
{
int v=e[i].v,c=e[i].c;
if(dis[v]<dis[u]+c && e[i].f>0)
{
dis[v]=dis[u]+c;
lst[v]=i;pre[v]=u;
flow[v]=min(e[i].f,flow[u]);
if(!in[v]) q.push(v),in[v]=1;
}
}
}
return flow[T]>0;
}
void EK()
{
while(bfs() && k)
{
if(dis[T]<=0) break;
int t=min(k,flow[T]);
ans-=dis[T]*t;
k-=t;
int zy=T;
while(zy!=S)
{
e[lst[zy]].f-=flow[T];
e[lst[zy]^1].f+=flow[T];
zy=pre[zy];
}
}
printf("%lld\n",ans);
}
int lowbit(int x) {return x&(-x);}
int id(int x) {return (int)log2(lowbit(x));}
int main()
{
n=read();tot=1;
for(int i=1;i<=n;i++)
{
int x=read();
if(x==0) continue;
ca[id(x)]++;
ans+=lowbit(x);
mp2[x]++;
}
m=read();S=70;T=71;
for(int i=1;i<=m;i++)
{
int x=read();
if(x==0) continue;
cb[id(x)]++;
mp1[x]++;
}
k=read();
for(auto x:mp1)
cc[id(x.first)]+=min(x.second,mp2[x.first]);
for(int i=0;i<32;i++)
{
add(S,i,0,ca[i]);
add(i+32,T,0,cb[i]);
for(int j=0;j<i;j++)
add(i,j+32,(1<<i)-(1<<j),inf);
add(i,i+32,1<<i,cc[i]);
}
EK();
}