CF1242C Sum Balance

一、题目

点此看题

二、解法

我们可以确定最后每一个盒子的和是多少，把所有数加起来得到$sum$，目标就是$ave=sum/n$

如果我们从每一个盒子里抽出来一个数，那么拿进去的这个数是确定的（数互不相同），我们把这个看作边，那么我们找到环就表示这些盒子之间形成了轮换合法的关系。然后答案是由多个这种关系组成的，所以设$dp[i]$为状态$i$已经可以了吗？子集枚举就行了，时间复杂度$O(3^n)$

所以难写的一批

#include <cstdio> #include <algorithm> #include <vector> #include <stack> #include <map> using namespace std; const int M = 100005; #define int 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,k,tot,sum,m[20],a[20][5005],s[20]; int og[1<<15],dp[1<<15],pre[1<<15],ans[20][2]; int cnt,Index,in[M],b[M],c[M],f[M],dfn[M],low[M]; map<int,int> mp;stack<int> sta;vector<int> vc[M]; struct edge { int v,next; }e[M]; void add(int u,int v) { e[++tot]=edge{v,f[u]},f[u]=tot; } void dfs(int u) { dfn[u]=low[u]=++Index; in[u]=1;sta.push(u); for(int i=f[u];i;i=e[i].next) { int v=e[i].v; if(!dfn[v]) { dfs(v); low[u]=min(low[u],low[v]); } else if(in[v]) low[u]=min(low[u],dfn[v]); } if(low[u]==dfn[u]) { int v,st=0,fuck=1;cnt++; do { v=sta.top();sta.pop(); if(st&(1<<c[v]-1)) fuck=0; vc[cnt].push_back(v); st|=(1<<c[v]-1); }while(u!=v); if(fuck && vc[cnt].size()>1) og[st]=cnt,dp[st]=1; } } void nmsl(int s) { if(og[s]) { for(int i=0;i<vc[og[s]].size();i++) { int j=(i+1)%vc[og[s]].size(); int u=vc[og[s]][i],v=vc[og[s]][j]; ans[c[u]][0]=b[u];ans[c[u]][1]=c[v]; } return ; } if(!pre[s]) return ; nmsl(s^pre[s]); nmsl(pre[s]); } signed main() { n=read(); for(int i=1;i<=n;i++) { m[i]=read(); for(int j=1;j<=m[i];j++) { a[i][j]=read(); b[++k]=a[i][j]; s[i]+=a[i][j];sum+=a[i][j]; } } if(sum%n) { puts("No"); return 0; } sum/=n; sort(b+1,b+1+k); for(int i=1;i<=n;i++) for(int j=1;j<=m[i];j++) { int t=lower_bound(b+1,b+1+k,a[i][j])-b; mp[a[i][j]]=t;c[t]=i; } for(int i=1;i<=n;i++) { if(s[i]==sum) { dp[1<<i-1]=1; ans[i][0]=a[i][1];ans[i][1]=i; } for(int j=1;j<=m[i];j++) { int x=mp[a[i][j]+sum-s[i]]; if(x && c[x]!=i) add(mp[a[i][j]],x); } } for(int i=1;i<=k;i++) if(!low[i]) dfs(i); for(int i=1;i<(1<<n);i++) { if(dp[i]) continue ; for(int j=i;j;j=(j-1)&i) if(dp[j] && dp[i^j]) dp[i]=1,pre[i]=j; } if(!dp[(1<<n)-1]) { puts("No"); return 0; } puts("Yes"); nmsl((1<<n)-1); for(int i=1;i<=n;i++) printf("%lld %lld\n",ans[i][0],ans[i][1]); } /* av=sum+y-x; y=x+av-sum; */