CF1242C Sum Balance

题意

有 \(k\) 个盒子，每个盒子里面有 \(n_i\) 个绝对值小于 \(10^9\) 的数（所有数互不相同）。

要求从每个盒子里拿出刚好一个元素，将其放入任意的一个盒子当中（可以是自己），并且每一个盒子只会新放入一个元素。

问你是否有可能让每一个盒子里的数的和都相等，并给出方案。

题解

首先我们可以发现，每一个盒子都只会拿出一个，得到一个，也就是说每个盒子里的元素个数是不变的。

设拿走的元素是 \(x\) ，放进来的是 \(y\) 。

我们要改变一个盒子的元素之和，就只能靠 \(y-x\) 来改变。

而题目里保证不会有重复出现的数。所以对于每一个盒子，如果你拿走的 \(x\) 固定，那么想要有解的话，它对应的 \(y\) 也应该是固定的。

并且因为元素不会删除或者添加，所以所有元素之和是不变的，也就是，我们要让每一个盒子的和最终变成的那个数 \(Goal\) 是固定不变的。

所以说对于每一个数都可能存在一对 \(x\to y\) 的对应关系。

我们就可以很容易的想到，可以利用有向图来维护这样的关系。

简单来说，对于每一个数字 \(x\)，我们让他变成一个图上的节点，

并令他连向一个数 \(y\) 对应的节点，满足 \(x\) 所在的盒子的元素和加上 \(y-x\) 能等于 \(Goal\)。

如果不存在这样的节点 \(y\) ，我们令他连向一个实际上不存在的点 \(nil\) ，表示没法找到一个可以满足条件的 \(y\)。

很明显，因为数是互不相同的，所以每一个点的出度一定为 \(1\)。

当然，连完边之后是可以出现自环的（比如下面的样例）

手搓一下样例：

除去和 \(nil\) 相连的节点，你会发现，这实际上是一个内向树森林。

再观察一下输出：

你会很容易发现，答案是由刚好包含每个盒子里的某一个元素的多个环组成的。

就是说，每一个盒子里有且仅有一个节点在这些环上。

因为如果关系构成一个环，那么证明环上的节点能够相互使对方的盒子当中的元素之和等于 \(Goal\)。

所以，我们就只需要找到几个能满足条件的环就行了。

发现题目给的 \(k\) 是 \(\le 15\) 的。

并且我们需要的是每个盒子里只有一个元素在这些环上。

所以我们可以考虑状压 DP 。

因为盒子只有 \(15\) 个，所以环也最多只有 \(15\) 个。

用一个二进制数来表示你当前已经满足条件的盒子的状态。

我们设 \(f_{msk}\) 表示当你处理到的盒子的状态是 \(msk\) 的时候的方案（注意是方案，所以我们直接利用 vector 记录即可）。

然后我们对于一个不满足条件，也就是二进制下有至少一位不是 \(1\) 的状态 \(msk\) ，我们考虑去找它的补集。

具体来说，我们枚举另外的一个状态 \(msk^\prime\) ，看 \(\complement_{msk}\) 是不是 \(msk^\prime\) 的子集即可。

如果有重复出现同一个盒子里的不同元素，我们就需要排除掉枚举出来的状态 \(msk^\prime\)。

最后对 \(f_{2^k-1}\) 排个序输出就好了。

Code:


#include
using namespace std;

#define int long long
#define ld long double
#define pii pair
#define fr first
#define sc second
#define pb push_back
#define mk make_pair

constexpr int boxsi=20;
constexpr int stasi=(1<<16);
int k,n[boxsi];
int Sum=0,sum[boxsi],Goal;
// bitsetvis;
bool vis[stasi];
vectorf[stasi];
unordered_maprec;
setS,Fr; 

signed main(){
    auto comp=[&](pii a,pii b)->bool{ return rec[a.fr]int{ return x+Goal-sum[rec[x]];};
    scanf("%lld",&k);
    for(register int i=1;i<=k;++i){
        scanf("%lld",&n[i]);
        for(register int j=1,rmp;j<=n[i];++j){
            scanf("%lld",&rmp);
            rec[rmp]=i,Sum+=rmp,sum[i]+=rmp;
        }
    }
    Goal=Sum/k;
    if(Sum%k) return puts("No"),0; //明显无解，直接特判。
    for(auto x:rec){
        register int i=x.fr;
        while(rec.find(i)!=rec.end() && S.find(i)==S.end() && Fr.find(i)==Fr.end()){
            Fr.insert(i),i=Go(i);
        }
        bool fa=false;
        if(Fr.find(i)!=Fr.end()){
            vectorlep;
            register int j=i,msk=0;
            do{int to=Go(i);
               lep.pb(mk(to,rec[i]));
               if(msk&(1<<(rec[i]-1))) fa=true;
               msk^=(1<<(rec[i]-1)),i=to;
            }while(i!=j);
            if(!fa && !vis[msk]) f[msk]=lep,vis[msk]=true;
        }
        for(auto y:Fr) S.insert(y);
        Fr.clear();
    }
    for(register int msk=1;msk<(1<0;i=(i-1)&msk){
                if(vis[i] && vis[msk-i]){
                    vis[msk]=true;
                    for(auto x:f[i]) f[msk].pb(x);
                    for(auto x:f[msk-i]) f[msk].pb(x);
                    break;
                }
            }
        }
    }
    if(!vis[(1<ans=f[(1<


						
							

						
							
							
			Type-题解Cate-图论Cate-动态规划Algor-状压DP

CF1242C Sum Balance

题意

题解

相关

标签