Description
给定一副 \(k\) 张牌的麻将牌，求能「听」哪些牌。
对于所有数据，\(1\leq k\leq 2\times 10^5\)。
link：https://www.luogu.com.cn/problem/U321190
Solution
算法零
枚举「听」的牌，用状压 DP 或者贪心判断。
时间复杂度 \(\mathcal{O}(2^n\text{poly}(n))\) 或 \(\mathcal{O}(n^3)\)，期望得分 \(10\sim 20\)。
算法一
将牌放入桶内，计 \(a_i\) 为 \(i\) 的牌的个数。枚举「听」的牌，用 DP 判断是否能「听」。
在 DP 前，有一个性质：由于三组同样的「顺子」可以被重新划分为三组「刻子」，所以相同的「顺子」不会超过三组。
设 \(f_{i,j,k,0/1}\) 为用完 \(1\sim i\) 的牌，有 \(j\) 组以 \(i-2\) 开头的「顺子」，\(k\) 组 \(i-1\) 开头的「顺子」，有或无「雀头」（\(1\) 为有，\(0\) 为无）的情况是否可能。转移如下：
- 不分出「雀头」，则 \(f_{i+1,k,(a_{i+1}-j-k)\bmod3,0/1}\gets f_{i,j,k,0/1}\)
- 分出「雀头」，则 \(f_{i+1,k,(a_{i+1}-j-k-2)\bmod3,1}\gets f_{i,j,k,0}\)
时间复杂度 \(\mathcal{O}(n^2)\)，有着 \(18\) 的大常数。期望得分 \(50\)。
代码实现：
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
namespace Milkcat {
typedef long long LL;
typedef pair<LL, LL> pii;
const int N = 5e3 + 5;
int n, k, x, cnt[N], a[N], f[N][3][3][2];
vector<int> res;
bool check(int qwq) {
for (int i = 1; i <= n; i ++)
a[i] = cnt[i] + (i == qwq);
memset(f, 0, sizeof f), f[0][0][0][0] = 1;
for (int i = 0; i < n; i ++)
for (int j = 0; j < 3; j ++)
for (int k = 0; k < 3; k ++)
for (int p = 0; p < 2; p ++) {
if (!f[i][j][k][p]) continue;
if (a[i + 1] >= j + k) f[i + 1][k][(a[i + 1] - j - k) % 3][p] = 1;
if (!p && a[i + 1] >= j + k + 2) f[i + 1][k][(a[i + 1] - j - k - 2) % 3][1] = 1;
}
return f[n][0][0][1];
}
int main() {
cin >> n >> k;
for (int i = 1; i <= k; i ++)
cin >> x, cnt[x] ++;
for (int i = 1; i <= n; i ++)
if (check(i)) res.push_back(i);
if (res.empty()) puts("NO");
for (int v : res) cout << v << ' ';
return 0;
}
}
int main() {
int T = 1;
while (T --) Milkcat::main();
return 0;
}
算法二
这种 DP 似乎无法继续优化，我们发现复杂度瓶颈在枚举「听」的牌，考虑将它放入 DP 状态中。
于是，设 \(f_{i,j,k,0/1,t}\) 为用完 \(1\sim i\) 的牌，有 \(j\) 组以 \(i-2\) 开头的「顺子」，\(k\) 组 \(i-1\) 开头的「顺子」，有或无「雀头」（\(1\) 为有，\(0\) 为无）的情况下「听」\(t\) 是否可能。我们发现 DP 状态可以使用 bitset 优化。
为了辅助转移，我们设 \(g_{i,j,k,0/1}\) 为用完 \(1\sim i\) 的牌，有 \(j\) 组以 \(i-2\) 开头的「顺子」，\(k\) 组 \(i-1\) 开头的「顺子」，有或无「雀头」（\(1\) 为有，\(0\) 为无）的情况是否可能（算法一的 DP）。
\(g\) 的转移见算法一。
转移枚举 \(i\)，然后分三步：
- 转移 \(g\)。
- 转移条件同算法一，设 \(f_{x}\) 转移到 \(f_{y}\)，需要将 \(f_{y}\) 设为两者的并集。
- 加上一张点数为 \(i\) 的牌，转移条件仍然同算法一，但是是由 \(g\) 转移到 \(f\)，设 \(g_{i,j,k,l}\) 转移到 \(f\)，则令 \(f_{i,j,k,l,i}\gets1\)。
时间复杂度 \(\mathcal{O}(\dfrac{n^2}{w})\)，由于还是有 \(18\) 的常数，所以常数没有特别小。期望得分 \(80\)。
可能有点抽象，可以看代码理解。
代码实现：
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
namespace Milkcat {
typedef long long LL;
typedef pair<LL, LL> pii;
const int N = 1e4 + 5;
int n, k, x, a[N], g[N][3][3][2];
bitset<N> f[N][3][3][2];
vector<int> res;
int main() {
cin >> n >> k;
for (int i = 1; i <= k; i ++)
cin >> x, a[x] ++;
g[0][0][0][0] = 1;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < 3; j ++)
for (int k = 0; k < 3; k ++)
for (int p = 0; p < 2; p ++) {
if (!g[i][j][k][p]) continue;
if (a[i + 1] >= j + k) g[i + 1][k][(a[i + 1] - j - k) % 3][p] = 1;
if (!p && a[i + 1] >= j + k + 2) g[i + 1][k][(a[i + 1] - j - k - 2) % 3][1] = 1;
}
for (int j = 0; j < 3; j ++)
for (int k = 0; k < 3; k ++)
for (int p = 0; p < 2; p ++) {
if (!f[i][j][k][p].count()) continue;
if (a[i + 1] >= j + k) f[i + 1][k][(a[i + 1] - j - k) % 3][p] |= f[i][j][k][p];
if (!p && a[i + 1] >= j + k + 2) f[i + 1][k][(a[i + 1] - j - k - 2) % 3][1] |= f[i][j][k][p];
}
a[i + 1] ++;
for (int j = 0; j < 3; j ++)
for (int k = 0; k < 3; k ++)
for (int p = 0; p < 2; p ++) {
if (!g[i][j][k][p]) continue;
if (a[i + 1] >= j + k) f[i + 1][k][(a[i + 1] - j - k) % 3][p].set(i + 1);
if (!p && a[i + 1] >= j + k + 2) f[i + 1][k][(a[i + 1] - j - k - 2) % 3][1].set(i + 1);
}
}
if (!f[n][0][0][1].count()) puts("QAQ");
for (int i = 1; i <= n; i ++)
if (f[n][0][0][1][i]) cout << i << ' ';
return 0;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while (T --) Milkcat::main();
return 0;
}
算法三
发现算法二中的 bitset 形式简单，考虑优化。
发现 bitset 仅维护了三种操作：
- 单点赋值为 \(1\)。
- 两个
bitset按位或。 - 查询最终的一个
bitset。
将一个 DP 状态（即一个 bitset）看作一个点，将操作一挂在对应的点上，将操作二转移点与目标点间连一条边。由于 DP 的无后效性，所以建出来的图是 DAG。最后从最终状态出发，遍历能到达的点，处理操作一即可。
时间复杂度 \(\mathcal{O}(n)\)，还是有 \(18\) 的大常数。期望得分 \(100\)。
代码实现：
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
namespace Milkcat {
typedef long long LL;
typedef pair<LL, LL> pii;
const int N = 4e6 + 5;
int n, k, x, a[N], vis[N], g[N][3][3][2];
vector<int> res, G[N], C[N];
inline int id(int i, int j, int k, int p) { return i * 18 + j * 6 + k * 2 + p; }
void dfs(int u) {
for (int v : C[u]) vis[v] = 1;
for (int v : G[u]) dfs(v);
}
int main() {
cin >> n >> k;
for (int i = 1; i <= k; i ++)
cin >> x, a[x] ++;
g[0][0][0][0] = 1;
for (int i = 0; i < n; i ++) {
for (int j = 0; j < 3; j ++)
for (int k = 0; k < 3; k ++)
for (int p = 0; p < 2; p ++) {
if (!g[i][j][k][p]) continue;
if (a[i + 1] >= j + k) g[i + 1][k][(a[i + 1] - j - k) % 3][p] = 1;
if (!p && a[i + 1] >= j + k + 2) g[i + 1][k][(a[i + 1] - j - k - 2) % 3][1] = 1;
}
for (int j = 0; j < 3; j ++)
for (int k = 0; k < 3; k ++)
for (int p = 0; p < 2; p ++) {
int t = id(i, j, k, p);
if (a[i + 1] >= j + k) G[id(i + 1, k, (a[i + 1] - j - k) % 3, p)].push_back(t);
if (!p && a[i + 1] >= j + k + 2) G[id(i + 1, k, (a[i + 1] - j - k - 2) % 3, 1)].push_back(t);
}
a[i + 1] ++;
for (int j = 0; j < 3; j ++)
for (int k = 0; k < 3; k ++)
for (int p = 0; p < 2; p ++) {
if (!g[i][j][k][p]) continue;
if (a[i + 1] >= j + k) C[id(i + 1, k, (a[i + 1] - j - k) % 3, p)].push_back(i + 1);
if (!p && a[i + 1] >= j + k + 2) C[id(i + 1, k, (a[i + 1] - j - k - 2) % 3, 1)].push_back(i + 1);
}
}
dfs(id(n, 0, 0, 1));
for (int i = 1; i <= n; i ++)
if (vis[i]) res.push_back(i);
if (res.empty()) cout << "QAQ\n";
for (int v : res) cout << v << ' ';
return 0;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int T = 1;
while (T --) Milkcat::main();
return 0;
}