4 月 30 日测试题解
T1 \({\color{green}{\text{100pts}}}\text{/100pts}\)
题意
一个无限长宽的棋盘，给出起点 \(s\) 和终点 \(t\)，行走方式是象棋中马的走法，问最少需要走多少步。
对于 \(100\%\) 的数据，\(|x_s|, |y_s|, |x_t|, |y_t| \le 10^7\)。
思路
\(\text{100pts}\)
首先，坐标其实并不重要，我们只需要取两点横纵坐标的差值即可，记横坐标差值为 \(\Delta x\)，同理纵坐标为 \(\Delta y\)。
直觉告诉我们，在 \(\Delta x\) 与 \(\Delta y\) 充分大的时候，可以贪心来使两点尽可能接近。于是我们有这样的一个想法：
- 当 \(\Delta x \neq 0\) 或 \(\Delta y \neq 0\) 时，重复以下流程：
- 当 \(\Delta x \le \Delta y\) 时，我们交换 \(\Delta x\) 与 \(\Delta y\)，从而保证 \(\Delta x\) 为两差值中的较大值；
- 令 \(\Delta x \leftarrow \operatorname{abs}(\Delta x - 2)\)，\(\Delta y \leftarrow \operatorname{abs}(\Delta y - 1)\)；
当然，直接这样贪心并不总是正确的。比如说最终有可能得到 \(\Delta x = 1\) 且 \(\Delta y = 0\) 从而进入死循环。
观察到只有在两差值充分小的情况下，才会出现不满足以上贪心算法的特例，于是我们可以采用小范围打表，大范围贪心的方法来做。
表要打多大呢？这个比较随意，只要不小于 5，应该都可以。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
constexpr int dis[][6] = {
{0, 3, 2, 3, 2, 3},
{3, 2, 1, 2, 3, 4},
{2, 1, 4, 3, 2, 3},
{3, 2, 3, 2, 3, 4},
{2, 3, 2, 3, 4, 3},
{3, 4, 3, 4, 3, 4}
};
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int xp, yp, xs, ys;
std::cin >> xp >> yp >> xs >> ys;
int dx = std::abs(xp - xs), dy = std::abs(yp - ys);
int ans = 0;
while (dx > 5 || dy > 5) {
if (dx > dy) {
std::swap(dx, dy);
}
dx -= 1, dy -= 2;
dx = std::abs(dx), dy = std::abs(dy);
ans++;
}
std::cout << ans + dis[dx][dy] << "\n";
return 0;
}
T2 \({\color{red}{\text{20pts}}}\text{/100pts}\)
题意
记任意一个 \(n\) 位十进制正整数 \(a = \overline{a_1 a_2 \ldots a_n}\)，能表示为 \(a\prod_{i = 1}^{n} a_i\) 的正整数被称为好的。
给出区间 \([A, B]\)，你要求出区间内好的数的数量。
对于 \(20\%\) 的数据，保证 \(A, B \le 1000\)；
对于 \(40\%\) 的数据，保证 \(A, B \le 10^6\)；
对于 \(100\%\) 的数据，保证 \(1 \le A, B \le 10^{18}\)。
思路
\(\text{20pts}\)
我们可以直接枚举 \(a\) 来算出对应的好数，再判断其是否位于区间内。时间复杂度 \(O(\max(A, B)\log_{10}\max(A,B))\)。
\(\text{40pts}\)
在暴力算法上随便剪剪枝，可以卡到这部分分数。
\(\text{100pts}\)
如此大的数据范围，正解我们当然是考虑数位 DP 了。
如果使用普通的数位 DP 的话，其时间复杂度其实并没有降低多少，仍然只能拿到 40% 的分数。
我们先来证明一个引理：
记 \(\operatorname{prod}(a) = \prod_{i = 1}^n a_i\)，则有 \(a > \operatorname{prod}(a)\)。
证明：
\(\forall i \in [1, n]\)，有 \(a_i \le 9 \lt 10\)。又 \(a = \overline{a_1 a_2 \ldots a_n} \ge \overline{a_1 \underbrace{0\cdots 0}_{n - 1}} = a_1 \times 10^n\)，而 \(\prod_{i = 2}^n a_i \lt 10^n\)，于是\(\operatorname{prod}(a) = \prod_{i = 1}^n \lt a_1 \times 10^n \le a\)，原命题得证。
那么对于原题的数据，为了保证 \(a\operatorname{prod}(a) \le B\)，我们就有 \(\operatorname{prod}(a) \le \sqrt B\)。于是数据范围成功的从 \(O(10^{18})\) 缩小至了 \(O(10^9)\)。
对于 10 以内的每个数字，由于质数的唯一分解定理，其一定可以被分解为 \(2^{p_0}3^{p_1}5^{p_2}7^{p_3}\) 的形式，这是因为 10 以内只有 2、3、5、7 这四个质数。而 \(\operatorname{prod}(a)\) 正是由 10 以内的数字的乘积所构成的。于是我们可以通过搜索或枚举的方式直接构造出 \(\sqrt{B}\) 以内的 \(\operatorname{prod}(a)\)。再用 \(A\) 与 \(B\) 分别去除 \(\operatorname{prod}(a)\)，就可以得到原数 \(a\) 的范围。再通过 2、3、5、7 这四个质因子的个数来做数位 DP，就可以确定 \(a\) 的数量。
同样使用数位 DP 的记忆化模板，我们定义状态 \(f_{pos,cur,top,rst}\)，其中 \(rst\) 为一个四元组，表示 2、3、5、7 这四个质因子各自的剩余个数，\(pos\) 为当前填的位数（从低到高），\(cur\) 为当前填出的数字，\(top\) 为当前位下一步应填 10 的多少次方（从高到低）。
递推式子比较显然就是了，这里就不给了。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
using i64u = unsigned long long;
using f80 = long double;
constexpr int factorCnt[][4] = {
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 1, 0, 0, 0 },
{ 0, 1, 0, 0 },
{ 2, 0, 0, 0 },
{ 0, 0, 1, 0 },
{ 1, 1, 0, 0 },
{ 0, 0, 0, 1 },
{ 3, 0, 0, 0 },
{ 0, 2, 0, 0 },
};
constexpr int factor[] = { 2, 3, 5, 7 };
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
i64 A, B;
std::cin >> A >> B;
std::vector f(19, std::vector(30, std::vector(19, std::vector(13, std::vector<i64>(11, -1)))));
std::array<int, 4> curCnt = { 0, 0, 0, 0 };
std::function<i64(int, i64, i64, i64, i64)> dfs =
[&](int pos, i64 lhs, i64 top, i64 l, i64 r) -> i64 {
i64 rhs = lhs + top - 1;
i64 &cur = f[pos][curCnt[0]][curCnt[1]][curCnt[2]][curCnt[3]];
top /= 10;
bool isLimited = !(lhs >= l && rhs <= r);
if (lhs > r || rhs < l) {
return 0;
} else if (pos == 18) {
return !curCnt[0] && !curCnt[1] && !curCnt[2] && !curCnt[3];
} else if (!isLimited && cur != -1) {
return cur;
}
i64 res = 0;
for (int d = (lhs != 0); d < 10; d++) {
bool flg = true;
for (int i = 0; i < 4; i++) {
if (factorCnt[d][i] <= curCnt[i]) {
continue;
}
flg = false;
break;
}
if (!flg) {
continue;
}
for (int i = 0; i < 4; i++) {
curCnt[i] -= factorCnt[d][i];
}
res += dfs(pos + 1, lhs + d * top, top, l, r);
// roll back changes
for (int i = 0; i < 4; i++) {
curCnt[i] += factorCnt[d][i];
}
}
if (!isLimited) {
cur = res;
}
return res;
};
std::function<i64(i64, int)> getNum = [&](i64 prod, int idx) -> i64 {
if (prod > 1e9 || prod * prod > B) {
return 0ll;
}
if (idx == 4) {
return dfs(0, 0, 1e18, (A + prod - 1) / prod, B / prod);
}
i64 res = 0;
// not multiply the current factor, go to the next one
res += getNum(prod, idx + 1);
// try to muliply the current factor
curCnt[idx]++;
res += getNum(prod * factor[idx], idx);
curCnt[idx]--;
return res;
};
std::cout << getNum(1, 0) << "\n";
return 0;
}
T3 \({\color{red}{\text{20pts}}}\text{/100pts}\)
题意
我们称一个正整数集 \(\mathbb{S}\) 为好的，如果 \(\forall i \in \mathbb{S}\)，有 \(2i \notin \mathbb{S} \land 3i \notin \mathbb{S}\)。
给出一个正整数 \(n\)，你需求出集合 \(\{1, 2, \ldots, n\}\) 的好的子集的个数对 \(10^9 + 1\) 取模后的值。
对于 \(30\%\) 的数据，\(n \le 20\)；
对于 \(60\%\) 的数据，\(n \le 1000\)；
对于 \(100\%\) 的数据，\(n \le 10^5\)。
思路
\(\text{20pts}\)
对于这部分数据，我们考虑二进制枚举，时间复杂度为 \(O(n^22^n)\)。
\(\text{60pts}\)
我不会这一部分。
\(\text{100pts}\)
正解为神秘构造 + 状压 DP。
对于每个正整数 \(i\)，我们可以构造一个矩阵，矩阵的第一行第一列元素为 \(i\)，其余所有元素，都是其左侧元素的 2 倍，上侧元素的 3 倍。这个矩阵为无穷矩阵，但为了保证矩阵中的每一项元素都不大于 \(n\)，这个矩阵并不完整。
举个例子，对于 1，我们构造出的矩阵如下：
\[\begin{pmatrix} 1 & 2 & 4 & 8 & \cdots \\ 3 & 6 & 12 & 24 & \cdots \\ 9 & 18 & 36 & 72 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \end{pmatrix} \]可以证明在这个矩阵中可以找出与构造矩阵的元 \(i\) 及其倍数有关的所有好的选取方法。
为了保证不重复计算，将出现在这个矩阵中的元素全部打上标记，再在 \([1, n]\) 的范围内继续以上操作。可以证明，这样的操作最终可以将 \([1, n]\) 的正整数划分为几个互不相交的集合。
由于题目中给出的 \(n \le 10^5\)，所以这个矩阵最多会有 18 列，11行。如此小的数据范围，我们不难想到状压 DP。约束条件就是，如果选择了位于 \((i, j)\) 的数，则与其四联通的数均不能被选。转移其实与P1879是一样的。
统计答案的时候是合并几个集合的值，因此需要用到乘法原理。记得到的集合为 \(\mathbb{S}\)，答案为 \(\prod_{i \in \mathbb{S}}i\)。
通过一些分析，可以得到时间复杂度为 \(O(n \log^2 n)\) 级别的。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
using i64u = unsigned long long;
using f80 = long double;
constexpr i64 MOD = 1e9 + 1;
std::vector<std::vector<int>> init(const int &num, const int &n, std::vector<bool> &used) {
std::vector<std::vector<int>> mat;
int curRow = num, cntRow = 0;
while (true) {
if (curRow > n) {
break;
}
mat.emplace_back(0);
int curCol = curRow;
while (true) {
if (curCol > n) {
break;
}
mat[cntRow].push_back(curCol);
used[curCol] = true;
curCol *= 2;
}
curRow *= 3;
cntRow++;
}
return mat;
}
i64 calc(const int &num, const std::vector<std::vector<int>> &mat) {
static constexpr int MAX = (1 << 18) - 1;
static std::bitset<MAX> table;
if (num == 1) {
for (int i = 0; i < table.size(); i++) {
table[i] = !((i << 1) & i);
}
}
std::vector f(mat.size(), std::vector<i64>());
for (int i = 0; i < f.size(); i++) {
f[i].resize(1 << mat[i].size());
}
for (int i = 0; i < f[0].size(); i++) {
f[0][i] = table[i];
}
for (int i = 1; i < f.size(); i++) {
for (int j = 0; j < f[i].size(); j++) {
if (!table[j]) {
continue;
}
for (int k = 0; k < f[i - 1].size(); k++) {
if (!table[k]) {
continue;
}
if ((k & j) == 0) {
(f[i][j] += f[i - 1][k]) %= MOD;
}
}
}
}
return std::accumulate(f[f.size() - 1].begin(), f[f.size() - 1].end(), 0ll);
}
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n;
std::cin >> n;
std::vector<bool> used(n + 1);
i64 ans = 1;
for (int i = 1; i <= n; i++) {
if (!used[i]) {
auto mat = init(i, n, used);
(ans *= calc(i, mat)) %= MOD;
}
}
std::cout << ans << "\n";
return 0;
}
T4 \({\color{red}{\text{15pts}}}\text{/100pts}\)
题意
给出 \(n\) 个点 \(m\) 条边的 DAG，你需要求出其最大独立集，并给出任意一组可行解。
\(n \le 200\)，\(m \le n^2\)。
思路
\(\text{100pts}\)
正解需要用到 Dilworth 定理：
偏序集能划分成的最少的全序集个数等于最大反链大小。
偏序关系可以简单理解为两元素可以相互比较大小。
DAG 上的反链满足对于任意两个链上的点 \(x\) 与 \(y\)，满足 \(x\) 与 \(y\) 不联通。那么将 DAG 抽象为偏序集，DAG 上的最大独立集就是该偏序集的最大反链大小。
DAG 上的每一条链都是一个全序集，即满足集合中任意两元素都满足偏序关系的集合。
而 Dilworth 定理体现在 DAG 中，即为最大反链大小等于最小可重链覆盖大小。这其实几乎是 Dilworth 定理在 OI 中的唯一应用了，因此，并不需要特意去了解偏序等集合论中的定义。
我们考虑求出该图的最小可重链覆盖大小。直接求最小可重链覆盖大小是不好做的，但是有一个结论：DAG 的最小可重链覆盖大小等于求出传递闭包的图之后的最小不可重链覆盖大小。于是先对原图求出传递闭包，这等同于将边集拓展为偏序集，而对于转化之后的问题，我们可以通过二分图匹配来解决。
将原图中的每个点 \(u\) 拆成两个点 \(u\) 与 \(u'\)，对于每一条边 \((u, v)\)，我们都在二分图中连边 \((u, v')\)，新图的最小不可重链覆盖大小就等于 \(n\) 减去二分图最大匹配数。
给一个比较简易的证明：在匹配开始前，我们认为图中的每个点独立，即每个点都为一条链。由于链的特殊性，这导致每个点入度与出度最多都为 1，这相当于原图中的一个点最多被匹配两次，而在构造出的二分图中，由于一个点被拆成了两个分别代表入与出的点，每个点最多就会被匹配一次。而一次成功的匹配 \((u, v')\) 就相当于原图中的一条边 \((u, v)\)，每连接一条边，链数就会减少一条，所以最大匹配就等于链数减少的最大值，那么用点数减了之后，就等于最小可重链覆盖大小。而事实上，不需要建出这张二分图，我们直接在原图中匹配也能取得一样的效果。
这样第一问就做完了，我们再来看第二问。
首先考虑把所有可能的点求出来。枚举每一个点，考虑把与其构成偏序的所有点删除（包括自身），若删除后原图中的最小不可重链覆盖大小减小了 1，则证明这个点是应该在被选取的链上的。
也给一个简易的证明：与一个点能够构成偏序的点集其实就是与这个点直接或间接联通的点，那么此时会出现两种情况：
- 这个偏序集构成原图的一条链；
- 这个偏序集既不是原图的一条链，也不是原图的反链。
在一条链中，我们最多只能选一个代表点，否则显然不优（把一条链拆成两条链还能优？）。因此当一个点对应的偏序集为一条链时，这个点一定是可能成为答案的，而且删去这条链，答案也一定会减 1。而当出现第二种情况时，我们可以把这个点对应的偏序集“拆”成几条链的形式，这样就成了第一种情况，明显更优，因此第二种是不优的。
然后再来找这个最大独立集。
我们知道每个偏序集中只能选一个点，于是考虑枚举每个可选点，如果它没有被染色的话，就把与其相关的可选点与它染成相同的颜色，最终每次染色第一个被选的点就可以构成一组答案。这貌似是一个很正确的贪心，但事实上它还有一点瑕疵，这样做最终得到的答案中的点数可能比我们求出来的答案要少。
解决方法就是枚举每一个点作为染色的起点即可，可证明这样一定能跑出一组答案（这个不是假的！）。
时间复杂度大概为 \(O(n^4)\)。
代码
\(\text{100pts}\)
#include <bits/stdc++.h>
using i64 = long long;
using i64u = unsigned long long;
using f80 = long double;
struct Graph {
static constexpr int INF = 1e9;
struct Edge {
int u, v, w;
Edge() : u(0), v(0), w(0) {}
Edge(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}
};
int n;
std::vector<Edge> edges;
std::vector<std::vector<int>> e;
std::vector<bool> vis, deleted;
std::vector<int> match;
std::vector<std::vector<bool>> reach;
Graph(int _n) : n(_n) {
e.resize(n);
vis.resize(n), deleted.resize(n);
match.resize(n);
reach.resize(n, std::vector<bool>(n));
return;
}
void add(int u, int v, int w = 0) {
edges.emplace_back(u, v, w);
e[u].push_back(edges.size() - 1);
reach[u][v] = true;
return;
}
void floyd() {
for (int k = 1; k < n; k++) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
if (reach[i][k] && reach[k][j]) {
reach[i][j] = true;
}
}
}
}
return;
}
bool dfs(int u) {
for (int v = 1; v < n; v++) {
// int v = edges[i].v;
if (!vis[v] && reach[u][v]) {
// std::cerr << u << " " << v << "\n";
if (deleted[v]) {
continue;
}
vis[v] = true;
if (!match[v] || dfs(match[v])) {
match[v] = u;
return true;
}
}
}
return false;
}
void resetDel() {
std::fill(deleted.begin(), deleted.end(), false);
return;
}
void del(int u) {
deleted[u] = true;
return;
}
int binaryMatching() {
int res = 0;
std::fill(match.begin(), match.end(), 0);
for (int i = 1; i < n; i++) {
if (deleted[i]) continue;
std::fill(vis.begin(), vis.end(), false);
if (dfs(i)) {
res++;
}
}
return res;
}
bool reachable(int i, int j) {
return reach[i][j] || reach[j][i] || i == j;
}
};
signed main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
Graph g(n + 1);
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
g.add(u, v);
}
g.floyd();
int match = n - g.binaryMatching();
std::cout << match << "\n";
std::vector<bool> onPath(n + 1);
for (int i = 1; i <= n; i++) {
g.resetDel();
int cnt = n;
for (int j = 1; j <= n; j++) {
if (g.reachable(i, j)) {
g.del(j);
cnt--;
}
}
onPath[i] = (cnt - g.binaryMatching() == match - 1);
}
for (int delta = 0; delta < n; delta++) {
int clk = 0;
std::vector<int> col(n + 1);
std::vector<bool> ans(n + 1, false);
for (int i = 1; i <= n; i++) {
if (onPath[(i + delta) % n] && !col[(i + delta) % n]) {
ans[(i + delta) % n] = true;
++clk;
for (int j = 1; j <= n; j++) {
if (g.reachable((i + delta) % n, j)) {
col[j] = clk;
}
}
}
}
int ansCnt = 0;
for (int i = 1; i <= n; i++) {
if (ans[i]) {
ansCnt++;
}
}
if (ansCnt == match) {
for (int i = 1; i <= n; i++) {
std::cout << ans[i];
}
std::cout << "\n";
break;
}
}
for (int i = 1; i <= n; i++) {
std::cout << onPath[i];
}
std::cout << "\n";
return 0;
}