文章目录
一.题目二.Solution三.CodeThanks！
一.题目
有
k
k
k个盒子, 第
i
i
i个盒子有
n
i
n_i
ni个数。保证所有数互不相同。从每个盒子各拿出一个数, 并按照某种顺序放回去(每个盒子恰好放入一个数)。判断是否能使操作后所有盒子内的数的和相同, 有解需要输出任意一个方案。
k
⩽
15
,
n
≤
5000
k\leqslant 15, n \leq 5000
k⩽15,n≤5000 传送门
二.Solution
这道题目很巧妙。 首先如果所有数的和分成k个集合的平均数不是整数，肯定不行，我们就是要把所有的集合内的数的和变成平均数。 然后我们可以看到每个数字想要被拿出来就必定只对应一个能拿进来的数，并且每个数字都是不同的，所以一个数字最多只对应一个能拿进来的数，据此可以建一个有向图，每个点的出度至多为1，然后找环即可，每个不相交的环合起来如果一共有n个点就找到了一个答案。 这里统计环的个数我是使用Tarjan来统计的，每个环用二进制来存，一个环如果所有的点都属于不同的集合那么就合法。 然后把这些找到的环合起来的工作就由状压DP来完成（具体看以下代码，有注释）：
for (int i
= 0; i
< (1 << k
); i
++){
for (int j
= ((i
- 1) & i
); j
; j
= ((j
- 1) & i
)){
if (F
[j
].size
() && F
[i
^ j
].size
()){
F
[i
] = F
[i
^ j
];
for (int k
= 0; k
< F
[j
].size(); k
++)
F
[i
].push_back
(F
[j
][k
]);
break;
}
}
}
最后记录答案也非常靠技术。为了答案的方便计算，我们由一个数指向可以换它的数，因为Tarjan存环是用栈，所以最后直接用存下来的一个点只想后面的一个点就是答案：
for (int i
= 0; i
< F
[(1 << k
) - 1].size(); i
++){
int tmp
= F
[(1 << k
) - 1][i
], j
;
for (j
= 0; j
< p
[tmp
].rood
.size() - 1; j
++){
int now1
= p
[tmp
].rood
[j
], now2
= p
[tmp
].rood
[j
+ 1];
fina
[bel
[now1
]].a
= val
[now1
], fina
[bel
[now1
]].b
= bel
[now2
];
}
int now1
= p
[tmp
].rood
[j
], now2
= p
[tmp
].rood
[0];
fina
[bel
[now1
]].a
= val
[now1
], fina
[bel
[now1
]].b
= bel
[now2
];
}
三.Code
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <stack>
#include <vector>
using namespace std
;
#define LL long long
#define K 20
#define M 5005
struct node
{
int cir
;
vector
<int> rood
;
}p
[M
* K
];
struct ans
{
int a
, b
;
}fina
[K
];
int k
, N
, val
[M
* K
], bel
[M
* K
], dfn
[M
* K
], low
[M
* K
], cnt
, num
;
LL tot
, s
[K
];
map
<LL
, int> mp
;
stack
<int> S
;
vector
<int> G
[M
* K
];
vector
<int> F
[(1 << 15)];
void Tarjan
(int x
){
dfn
[x
] = low
[x
] = ++ cnt
;
S
.push
(x
);
for (int i
= 0; i
< G
[x
].size(); i
++){
int tmp
= G
[x
][i
];
if (! dfn
[tmp
]){
Tarjan
(tmp
);
low
[x
] = min
(low
[x
], low
[tmp
]);
}
else{
low
[x
] = min
(dfn
[tmp
], low
[x
]);
}
}
if (dfn
[x
] == low
[x
]){
num
++;
int v
;
bool flag
= 0;
do{
v
= S
.top
();
S
.pop
();
if (p
[num
].cir
& (1 << (bel
[v
] - 1)))
flag
= 1;
p
[num
].rood
.push_back
(v
);
p
[num
].cir
|= (1 << (bel
[v
] - 1));
}while (v
!= x
);
if (flag
|| ! G
[x
].size() || (p
[num
].rood
.size
() == 1 && G
[x
][0] != x
)){
p
[num
].cir
= 0;
p
[num
].rood
.clear();
num
--;
return ;
}
if (! F
[p
[num
].cir
].size())
F
[p
[num
].cir
].push_back
(num
);
}
}
int main
(){
scanf
("%d", &k
);
for (int i
= 1; i
<= k
; i
++){
int n
;
scanf
("%d", &n
);
while (n
--){
N
++;
scanf
("%d", &val
[N
]);
bel
[N
] = i
;
s
[i
] += 1ll * val
[N
];
mp
[1ll * val
[N
]] = N
;
}
tot
+= s
[i
];
}
if (tot
% (LL
)k
!= 0){
printf
("No\n");
return 0;
}
tot
= tot
/ (LL
)k
;
for (int i
= 1; i
<= N
; i
++){
if (mp
[tot
- s
[bel
[i
]] + 1ll * val
[i
]]){
int u
= i
, v
= mp
[tot
- s
[bel
[i
]] + val
[i
]];
G
[u
].push_back
(v
);
}
}
for (int i
= 1; i
<= N
; i
++){
if (! dfn
[i
])
Tarjan
(i
);
}
for (int i
= 0; i
< (1 << k
); i
++){
for (int j
= ((i
- 1) & i
); j
; j
= ((j
- 1) & i
)){
if (F
[j
].size
() && F
[i
^ j
].size
()){
F
[i
] = F
[i
^ j
];
for (int k
= 0; k
< F
[j
].size(); k
++)
F
[i
].push_back
(F
[j
][k
]);
break;
}
}
}
if (F
[(1 << k
) - 1].size()){
for (int i
= 0; i
< F
[(1 << k
) - 1].size(); i
++){
int tmp
= F
[(1 << k
) - 1][i
], j
;
for (j
= 0; j
< p
[tmp
].rood
.size() - 1; j
++){
int now1
= p
[tmp
].rood
[j
], now2
= p
[tmp
].rood
[j
+ 1];
fina
[bel
[now1
]].a
= val
[now1
], fina
[bel
[now1
]].b
= bel
[now2
];
}
int now1
= p
[tmp
].rood
[j
], now2
= p
[tmp
].rood
[0];
fina
[bel
[now1
]].a
= val
[now1
], fina
[bel
[now1
]].b
= bel
[now2
];
}
printf
("Yes\n");
for (int i
= 1; i
<= k
; i
++)
printf
("%d %d\n", fina
[i
].a
, fina
[i
].b
);
}
else
printf
("No\n");
return 0;
}
Thanks！
