题目
D - Peaceful Teams
参考:
https://www.cnblogs.com/legendstane/p/freee-programming-contest-2023-atcoder-beginner-contest-abc-310-solution.html
https://blog.csdn.net/Muelsyse_/article/details/131747083
思路
方法1 dfs暴搜
- 由于数据范围极小, 所以直接暴力即可
- dfs的顺序依据: dfs每层将一个player进行分组选择
- 如何保证不重复枚举: 从小到大分配player, 新建小组时, 每组的第一个人一定是当前未分配组别的player中序号最小者, 这使得小组1~t中每个小组中player序号为升序, 且t个小组中的第一名player的序号也为升序;
- dfs每个player的选择: 选择加入现有的cnt个小组中的一个; 或新建第cnt+1个小组, 成为这个小组的第一个人;
方法2 bitmask枚举状态 + dp
- 注意到数据范围 N<10, 这样的范围即可暴力枚举
- 而这样的数据范围, 很适合通过二进制位来枚举状态; 且二进制位很适合表示集合状态(某个元素集合中有1 or 没有0);
- 注意: 这里也存在如何保证不重复枚举的问题(因为组间是没有顺序的), 这里保证了每个新的小组中, 包含未被分组的player中序号最小者;
总结
- 数据范围
- 分组方案的dfs方式
- bitmask表示集合, 进行分组枚举
- 如何保证分组方案不重复
代码
1. dfs 代码
// https://atcoder.jp/contests/abc310/tasks/abc310_d
// dfs暴搜 分组方案数
// dfs 依次考虑每个人 u=1~n 分到哪个组
// 当前共有cnt个组, 每个人可选择分到 1~cnt组 或者新建一个组
// 避免重复的方式: 从1到n的顺序考虑每个人, 如果建立新组, 也只能顺序建立第cnt+1个小组(并加入这个小组)
// 这样能够使得最终的t个小组的每组的第一个人(建立这个小组的人)的序号为升序,
// 且每组人数不为空;
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int N = 12;
bool st[N][N];
vector<int> team[N];
int cnt;
int n, t, m;
int ans;
// 考虑编号为u的player的分组情况
void dfs(int u)
{
if (cnt > t)
return; // 分组超过t无效
if (u > n) // 当u=1~n都分配完毕
{
if (cnt == t) // 恰好分了t组
{
bool flag = true; // 检查组内是否有冲突
for (int i = 1; i <= t; i++)
for (auto x : team[i])
for (auto y : team[i])
if (st[x][y]) flag = false;
if (flag) ans++;
}
return;
}
for (int i = 1; i <= cnt; i++) // 将第u个人分到已有的 1~cnt 组
{
team[i].push_back(u);
dfs(u + 1);
team[i].pop_back();
}
// 第u人新建一组(第cnt+1组)
team[++cnt].push_back(u);
dfs(u + 1);
team[cnt--].pop_back();
}
void solv()
{
cin >> n >> t >> m;
while (m--)
{
int a, b;
cin >> a >> b;
st[a][b] = st[b][a] = true;
}
dfs(1);
cout << ans << endl;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T = 1;
// cin >> T;
while (T--)
{
solv();
}
return 0;
}
2. bitmask表示集合 dp 代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL n, t, m, bad[20][20], badm[1100], dp[20][1100];
int main()
{
cin >> n >> t >> m;
for (int i = 0; i < m; i++)
{
int x, y;
cin >> x >> y;
bad[x - 1][y - 1] = bad[y - 1][x - 1] = 1; // 标记非法组合 (序号从0开始)
}
for (int i = 0; i < 1 << n; i++) // 遍历集合所有状态, 这里视为同一个小组中的组合
for (int j = 0; j < n; j++) // j, k 检查状态 i 中是否存在非法组合
for (int k = 0; k < n; k++)
if (j != k && (i & (1 << j)) && (i & (1 << k)) && bad[j][k]) // 标记非法状态为 1
badm[i] = 1;
dp[0][0] = 1; // 0 组, 总状态为 0, 方案为 1
for (int i = 0; i < t; i++) // 已有i组, 计算当i+1组建立时, 各状态下的方案时
for (int j = 0; j < 1 << n; j++) // 第i组状态
if (dp[i][j] && j != ((1 << n) - 1)) // 前i组, 总状态为j, 方案数不为0, 且总状态中人数未满
{
int tmp;
for (int k = 0; k < n; k++) // 找到在状态j种, 未分配的player的最小编号对应的bitmask -> tmp
if (!(j & (1 << k)))
{
tmp = 1 << k;
break;
}
for (int k = 0; k < 1 << n; k++) // 枚举 第i+1组 的状态
if (!(j & k) && (k & tmp) && !badm[k]) // 如果前i组状态j与第i+1组状态k没有冲突, k状态中包含tmp, 并且k不是非法状态
dp[i + 1][j | k] += dp[i][j]; // 注意, 由if中前两个条件, 可得的新组别k中, 最小序号为当前未选出的player中的最小序号, 这样可保证不重复枚举
}
cout << dp[t][(1 << n) - 1] << endl;
return 0;
}