本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-05-02 21:39:39
题解思路：
无解情况：
所有的价值和不是 $k$ 的倍数那么他就无解。
我们发现每个合法都是一个环。
那么我们就可以用二进制表示。
然后我们就看这些二进制能否构成全一串就可以了。
具体怎么做：
首先判断是否有解，即他们的价值和 $\mod k = 0$。
预处理环。
状压 dp $\longrightarrow$ 二进制全 $1$。
AC CODE:
#include <cstring>
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
ll sum[15];
vector <int> a[15];
map <ll , pair <int , int>> mp;
bool vis[1 << 15] , dp[1 << 15];
vector <pair <pair<int , int> , int>> mark[1 << 15];
int pre[1 << 15];
pair <int , int> ans[15];
int main() {
int k;
scanf ("%d" , &k);
ll v = 0;
for (int i = 0; i < k; ++ i) {
int n;
scanf ("%d" , &n);
a[i].resize (n);
for (int j = 0; j < n; ++ j) {
scanf ("%d" , &a[i][j]);
sum[i] += a[i][j];\/\/sum[i]第i组的和
mp[a[i][j]] = {i , j};\/\/i组j个
}
v += sum[i];\/\/总和
}
if (v % k != 0) return puts("No") , 0;\/\/无解
v \/= k;\/\/分成k个小段，每段的和
for (int i = 0; i < k; ++ i) {\/\/预处理环
for (int j = 0; j < a[i].size(); ++ j) {
ll cur = a[i][j];\/\/枚举a[i][j]，复杂度15×5000
int now = 0;\/\/现在的状态
bool ok = true;
vector <pair<pair <int , int> , int>>b;
while (1) {
int y = mp[cur].first;\/\/用map记录
cur = v - sum[y] + cur;\/\/他对应的值：sum[i]+a[i][j]+?=v,我们已知：sum[i],v,
if (!mp.count(cur)) {
ok = false;
break;
}
auto x = mp[cur];
if (now & (1 << x.first)) {
ok = false;
break;
}
now |= (1 << x.first);
b.push_back ({{x.first , x.second} , y});
if (x.first == i) {\/\/一直往前找，又回到了期点，有环
if (x.second != j) ok = false;
break;
}
}
if (ok) {
vis[now] = true;
mark[now] = b;
}
}
}
dp[0] = 1;
for (int s = 0; s < (1 << k); ++ s) {\/\/枚举子集，状压DP
for (int ns = s; ns; ns = (ns - 1) & s)
if (vis[ns] && dp[s ^ ns]) {
dp[s] = 1;
pre[s] = ns;
break;
}
}
if (!dp[(1 << k) - 1]) return puts("No") , 0;\/\/没有全1那么也无解
int s = 1 << k;
-- s;
while (s) {
for (auto &x : mark[pre[s]]) {
ans[x.first.first] = {a[x.first.first][x.first.second] , x.second};
}
s ^= pre[s];
}
puts("Yes");
for (int i = 0; i < k; ++ i)
printf ("%d %d\n" , ans[i].first , ans[i].second + 1);
return 0;
}
码字不易，求赞！
鲁ICP备2025150228号