CF1242C Sum Balance

    科技2022-07-17  136

    一、题目

    点此看题

    二、解法

    我们可以确定最后每一个盒子的和是多少,把所有数加起来得到 s u m sum sum,目标就是 a v e = s u m / n ave=sum/n ave=sum/n

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

    所以难写的一批

    #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; */
    Processed: 0.010, SQL: 8