免费的网站制作/磁力蜘蛛种子搜索

A

算法标签: 模拟

问题陈述

给你一个正整数 $N$ 和一个长度为 $N$ 的正整数序列 $A=(A_1,A_2,\dots ,A_N)$。

请判断 $A$ 是否是严格递增的，也就是说，$A_i<A_{i+1}$ 是否对每一个满足 $1\le i<N$ 的整数 $i$ 都成立

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int n;cin >> n;int last = 0;for (int i = 0; i < n; ++i) {int val;cin >> val;if (val <= last) {cout << "No" << "\n";return 0;}last = val;}cout << "Yes" << "\n";return 0;
}

---

B

算法标签: 模拟

问题陈述

概述：创建一个 $N\times N$ 模式，如下所示。

给你一个正整数 $N$。

考虑一个 $N\times N$ 网格。让 $(i,j)$ 表示从上往下第 $i$ 行，从左往右第 $j$ 列的单元格。最初，没有单元格被着色。

然后，依次对 $i=1,2,\dots ,N$ 执行以下操作：

• 让 $j=N+1-i$。
• 如果 $i\le j$，则在左上角单元格为 $(i,i)$、右下角单元格为 $(j,j)$ 的矩形区域填充黑色（如果 $i$ 为奇数），如果 $i$ 为偶数，则填充白色。如果某些单元格已经着色，则覆盖它们的颜色。
• 如果 $i>j$，则不做任何操作。

经过所有这些操作后，可以证明没有未着色的单元格。确定每个单元格的最终颜色。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>using namespace std;const int N = 55;int n;
char m[N][N];void draw(int i, int j, bool tag) {char c = tag ? '#' : '.';for (int k = i; k <= j; ++k) {for (int l = i; l <= j; ++l) {m[k][l] = c;}}
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 1; i <= (n + 1) / 2; ++i) {int j = n + 1 - i;if (i % 2) draw(i, j, true);else draw(i, j, false);}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cout << m[i][j];}cout << "\n";}return 0;
}

---

C

算法标签: 哈希表, 滑动窗口

问题陈述

给你一个正整数 $N$ 和一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\dots ,A_N)$。

请判断 $A$ 是否存在一个非空（连续）子数组，它有一个重复值，多次出现在 $A$ 中。如果存在这样的子数组，求最短的子数组的长度。

思路

如果存在当前元素$w[r]$, 更新答案并且收缩左侧窗口, 直到不存在当前元素$w[r]$, 也就是维护窗口中不存在重复元素

#include <iostream>
#include <algorithm>
#include <cstring>
#include <set>using namespace std;const int N = 2e5 + 10, INF = 0x3f3f3f3f;int n, w[N];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n;for (int i = 0; i < n; ++i) cin >> w[i];int l = 0;set<int> s;int res = INF;for (int r = 0; r < n; ++r) {while (s.count(w[r])) {res = min(res, r - l + 1);s.erase(w[l++]);}s.insert(w[r]);}cout << (res == INF ? -1 : res) << "\n";return 0;
}

---

D

算法标签: 模拟

问题陈述

有 $N$ 只标有 $1,2,\dots ,N$ 的鸽子和 $N$ 个标有 $1,2,\dots ,N$ 的鸽子窝。

最初，鸽子 $i$ $(1\le i\le N)$ 在巢 $i$ 中。

您将对这些鸽子进行 $Q$ 次操作。

操作有三种：

1. 类型 $1$：给你整数 $a$ 和 $b$ $(1\le a\le N,1\le b\le N)$。将鸽子 $a$ 从当前巢中取出，移到巢 $b$ 中。
2. 类型 $2$：给你整数 $a$ 和 $b$ $(1\le a<b\le N)$。将巢 $a$ 中的所有鸽子移动到巢 $b$，并将巢 $b$ 中的所有鸽子移动到巢 $a$。这两次移动是同时进行的。
3. 类型 $3$：给你一个整数 $a$ $(1\le a\le N)$。鸽子 $a$ 报告它目前所在巢的标签。

按照给出的操作顺序打印每个 类型 $3$ 操作的结果。

输入格式

• 第一行包含两个整数 $N$ 和 $Q$，分别表示鸽子和操作的数量。
• 接下来的 $Q$ 行，每行描述一个操作：
  • 对于类型 $1$ 操作，格式为 1 a b。
  • 对于类型 $2$ 操作，格式为 2 a b。
  • 对于类型 $3$ 操作，格式为 3 a。

输出格式

对于每个类型 $3$ 操作，输出鸽子 $a$ 当前所在的巢的标签。

思路

实现分析数据范围, 鸽子的数量$10^6$, 操作数量$10^5$, 实现$O(n^2)$以下时间复杂度
考虑为每一个位置确定一个门牌号, 交换两个鸽子笼是最消耗时间的, 但是交换门牌号很简单

上述是鸽子笼初始状态

上述是交换两个鸽子笼后, 也就是交换两个门牌号后的情况
设数组$p[i]$, 代表鸽子$i$所属鸽子笼编号, $pos[i]$代表门牌号$i$当前是哪个鸽子笼
考虑操作$1$, 鸽子$a$从当前鸽子笼中取出移动到鸽子笼$b$中, 因为交换的是门牌号, 因此需要知道每个笼子所属的门牌号是多少, 记为$num[i]$

第一个操作

• 首先找到巢$b$所在的门牌号
• 然后将鸽子$a$放入该鸽子笼中

第二个操作

• 找到两个笼子所属的门牌号
• 交换两个门牌号

第三个操作

• $p[a]$代表鸽子$a$所属的门牌号
• 输出当前门牌号对应的笼子编号

时间复杂度$O(M)$

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;const int N = 1e6 + 10;int n, m;
// 鸽子i所属门牌号, 门牌号i的笼子编号, 笼子i的门牌号
int p[N], pos[N], num[N];int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) p[i] = pos[i] = num[i] = i;while (m--) {int op;cin >> op;if (op == 1) {int a, b;cin >> a >> b;int num_b = num[b];p[a] = num_b;}else if (op == 2) {int a, b;cin >> a >> b;int num_a = num[a];int num_b = num[b];swap(num[a], num[b]);swap(pos[num_a], pos[num_b]);}else {int a;cin >> a;int num_a = p[a];cout << pos[num_a] << "\n";}}return 0;
}

---

E

算法标签: 最短路, 分层图

问题陈述

给你一个有向图，图中有 $N$ 个顶点和 $M$ 条边。 $i$ -th 边 $(1\le i\le M)$ 是一条从顶点 $u_i$ 到顶点 $v_i$ 的有向边。

最初，您位于顶点 $1$ 。您要重复以下操作直到到达顶点 $N$ ：

• 执行以下两个操作之一：
  • 从当前顶点沿一条有向边移动。这样做的代价是 $1$ 。更精确地说，如果你在顶点 $v$ ，选择一个顶点 $u$ ，使得有一条从 $v$ 到 $u$ 的有向边，然后移动到顶点 $u$ 。
  • 逆转所有边的方向这样做的代价是 $X$ 。更确切地说，如果且仅如果在此操作之前有一条从 $v$ 到 $u$ 的有向边，那么在此操作之后有一条从 $u$ 到 $v$ 的有向边。

可以保证，对于给定的图，重复这些操作可以从顶点 $1$ 到达顶点 $N$ 。

求到达顶点 $N$ 所需的最小总成本。

输入格式

• 第一行包含三个整数 $N$, $M$, $X$，分别表示顶点数、边数和逆转边的代价。
• 接下来的 $M$ 行，每行包含两个整数 $u_i$, $v_i$，表示一条从 $u_i$ 到 $v_i$ 的有向边。

输出格式

输出一个整数，表示从顶点 $1$ 到达顶点 $N$ 所需的最小总成本。

思路

下面一层图就是反转图, 从上一层到下一层的花费是$T$

注意目标节点之间转移花费是$0$

因为两次反转之后回到原图, 因此只需要建立两层即可, 时间复杂度$O(n\log m)$

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>using namespace std;typedef long long LL;
typedef pair<LL, int> PII;
const int N = (2e5 + 10) * 2, M = (2e5 + 10) * 4;int n, m, cost;
int head[N], edge_end[M], next_edge[M], w[M], edge_index;
LL d[N];
bool vis[N];void add(int u, int v, int val) {edge_end[edge_index] = v, next_edge[edge_index] = head[u], w[edge_index] = val, head[u] = edge_index++;
}void dijkstra() {priority_queue<PII, vector<PII>, greater<PII>> q;memset(d, 0x3f, sizeof d);d[1] = 0;q.push({0, 1});while (!q.empty()) {auto [dis, u] = q.top();q.pop();if (vis[u]) continue;vis[u] = true;for (int i = head[u]; ~i; i = next_edge[i]) {int ver = edge_end[i];if (d[u] + w[i] < d[ver]) {d[ver] = d[u] + w[i];q.push({d[ver], ver});}}}
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m >> cost;for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;add(u, v, 1);add(v + n, u + n, 1);}for (int i = 1; i <= n; ++i) {add(i, i + n, cost);add(i + n, i, cost);}dijkstra();LL res = 9e18;res = min({res, d[n], d[n + n]});cout << res << "\n";return 0;
}

---

F

算法标签: 贪心, 整数二分

问题陈述

高桥有 $2N$ 颗牙齿：上牙有 $N$ 颗，下牙有 $N$ 颗。
左起第 $i$ 颗上牙（$1\le i\le N$）的长度是 $U_i$，左起第 $i$ 颗下牙（$1\le i\le N$）的长度是 $D_i$。

如果同时满足以下两个条件，那么他的牙齿就可以说是 “合得很好”：

1. 存在一个整数 $H$，使得对于每个整数 $i$（$1\le i\le N$），$U_i+D_i=H$
2. 对于每个整数 $i$（$1\le i<N$），$|U_i-U_{i+1}|\le X$

他可以多次进行下面的运算：

• 支付 $1$ 日元使用磨齿机，选择一个长度为正数的牙齿，并将其长度减少 $1$。

不得使用其他方法改变牙齿的长度。
求为了使牙齿整齐排列，他至少需要支付的总金额。

思路

如果$H$确定, 那么花费确定

$$cost=\sum _{i=1}^N(U_i+D_i)-N\times H$$

因此花费最小化, 也就是$H$最大化, 问题转化为如何找到最大的$H$使得花费最小, 具有单调性

假设存在一个最大的$H$, 那么考虑$H-1$, 将$H$方案变为$H-1$的方案, 如何变化?

假设$H$下的方案为$U_i^{\prime }$和$D_i^{\prime }$, 需要将$U_i^{\prime }-1$或者$D_i^{\prime }-1$,
假设只变化$U_i^{\prime }$, 如果发现$U_i^{\prime }=0$, 将$D_i^{\prime }-1$, 也是符合情况的, 因此$H$是合法的, $H-1$必定是合法的,
因此$H$具有单调性, 一定存在一个最大的$H$, 使得花费最小

二分$H$判断是否能达到题目的两个条件

1. 是否存在序列$A_i$和$B_i$使得$A_i+B_i=H$
2. 对于每一个$A_i$, 是否有$|A_{i-1}-A_i|\le X$

设变化后的上牙长度为$U_i^{\prime }$, 那么由于只能变小, 因此$U_i^{\prime }\le U_i$, $H-U_i^{\prime }=D_i^{\prime }\le D_i$

因此有 max ⁡ { 0 , H − D i } ≤ U i ′ ≤ U i \max\left \{0, H - D_i \right \} \le U'_i \le U_i max{0,H−Di​}≤Ui′​≤Ui​, 也就是说, 对于每一个$i$, $U_i^{\prime }$最终的取值是都有个范围的, 设左边界为$l[i]$, 右边界为$r[i]$

因此问题转化为, 对于每个$l[i]\le U_i\le r[i]$, 是否存在一组数使得$|U_i-Ui-1|\le X$
, 也就是满足$U_{i-1}-X\le U_i\le U_{i-1}+X$, 同时满足上述两个不等式, 如果发现不满足说明无解

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;
const int N = 2e5 + 10;int n, m;
LL u[N], d[N];// 传入H
bool check(LL val) {LL l = max(0ll, val - d[1]);LL r = u[1];for (int i = 2; i <= n; ++i) {l = max({l - m, 0ll, val - d[i]});r = min(r + m, u[i]);if (l > r) return false;}return true;
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);LL l = 0, r = 2e9;LL sum = 0;cin >> n >> m;for (int i = 1; i <= n; ++i) {cin >> u[i] >> d[i];r = min(r, u[i] + d[i]);sum += u[i] + d[i];}LL res = 0;while (l < r) {LL mid = l + r + 1 >> 1;if (check(mid)) l = mid;else r = mid - 1;}res = l;cout << sum - n * res << "\n";return 0;
}

---

G

算法标签: $Steiner-Tree$, 斯坦纳树, 状态压缩$dp$

题目描述

给定正整数 $N$ 和 $K$，以及一个 $N\times N$ 的矩阵 $C=(C_{i,j})$（$1\le i,j\le N$）。保证 $C_{i,i}=0$ 且 $C_{i,j}=C_{j,i}$。

存在一个包含 $N$ 个顶点的带权完全图，顶点编号为 $1,2,\dots ,N$。对于满足 $i<j$ 的顶点对 $i,j$，连接顶点 $i$ 和 $j$ 的边的权重为 $C_{i,j}$。

给定 $Q$ 个查询。第 $i$ 个查询给出两个不同的整数 $s_i,t_i$（$K+1\le s_i,t_i\le N$），请对每个查询回答以下问题：

从该图中移除任意数量的边和顶点后，得到的连通子图若包含顶点 $1,2,\dots ,K,s_i,t_i$，则称其为良构子图。

良构子图的成本定义为子图中所有边的权重之和。

求良构子图的最小成本。

输入格式

输入通过标准输入给出，格式如下：

$N$ $K$
$C_{1,1}$ $C_{1,2}$ $\dots$ $C_{1,N}$
$C_{2,1}$ $C_{2,2}$ $\dots$ $C_{2,N}$
$⋮$
$C_{N,1}$ $C_{N,2}$ $\dots$ $C_{N,N}$
$Q$
$s_1$ $t_1$
$s_2$ $t_2$
$⋮$
$s_Q$ $t_Q$

输出格式

输出 $Q$ 行，第 $i$ 行对应第 $i$ 个查询的答案。

输入输出样例 #1

输入 #1

5 2
0 395 395 1 1
395 0 1 395 1
395 1 0 395 1
1 395 395 0 1
1 1 1 1 0
3
3 4
3 5
4 5

输出 #1

4
3
3

输入输出样例 #2

输入 #2

9 5
0 344670307 744280520 967824729 322288793 152036485 628902494 596982638 853214705
344670307 0 249168130 769431650 532405020 981520310 755031424 86416231 284114341
744280520 249168130 0 80707350 256358888 620411718 713892371 272961036 836365490
967824729 769431650 80707350 0 45539861 298766521 722757772 623807668 366719378
322288793 532405020 256358888 45539861 0 361324668 69837030 222135106 935147464
152036485 981520310 620411718 298766521 361324668 0 486834509 225447688 859904884
628902494 755031424 713892371 722757772 69837030 486834509 0 434140395 490910900
596982638 86416231 272961036 623807668 222135106 225447688 434140395 0 22078599
853214705 284114341 836365490 366719378 935147464 859904884 490910900 22078599 0
20
9 7
8 9
9 8
7 6
9 8
8 9
9 7
7 8
7 8
6 9
9 8
9 6
8 6
8 9
6 8
8 7
7 6
8 9
7 6
9 6

输出 #2

849002970
779165940
779165940
882119751
779165940
779165940
849002970
826924371
826924371
834361320
779165940
834361320
812282721
779165940
812282721
826924371
882119751
779165940
882119751
834361320

说明/提示

约束条件

• $3\le N\le 80$
• $1\le K\le \min (N-2,8)$
• $0\le C_{i,j}\le 10^9$（$1\le i,j\le N$ 且 $i\ne j$）
• $C_{i,j}=C_{j,i}$（$1\le i,j\le N$ 且 $i\ne j$）
• $C_{i,i}=0$（$1\le i\le N$）
• $1\le Q\le 5000$
• $K+1\le s_i,t_i\le N$（$1\le i\le Q$）
• $s_i\ne t_i$（$1\le i\le Q$）
• 输入均为整数

样例解释 1

• 第一个查询：最优方案保留顶点 $1,2,3,4,5$ 和边 $1-4,2-3,3-5,4-5$，成本为 $4$。
• 第二个查询：最优方案保留顶点 $1,2,3,5$ 和边 $1-5,2-3,3-5$，成本为 $3$。

思路

最小斯坦纳树
P6192 【模板】最小斯坦纳树

最小斯坦纳树: 给出图中任意点集$V$, 要求将$V$连通需要选择那些边, 并且使得这些边的权值之和最小

题目描述

给定一个包含 $n$ 个结点和 $m$ 条带权边的无向连通图 $G=(V,E)$。

再给定包含 $k$ 个结点的点集 $S$，选出 $G$ 的子图 $G^{\prime }=(V^{\prime },E^{\prime })$，使得：

1. $S\subseteq V^{\prime }$；

2. $G^{\prime }$ 为连通图；

3. $E^{\prime }$ 中所有边的权值和最小。

你只需要求出 $E^{\prime }$ 中所有边的权值和。

输入格式

第一行：三个整数 $n,m,k$，表示 $G$ 的结点数、边数和 $S$ 的大小。

接下来 $m$ 行：每行三个整数 $u,v,w$，表示编号为 $u,v$ 的点之间有一条权值为 $w$ 的无向边。

接下来一行：$k$ 个互不相同的正整数，表示 $S$ 的元素。

输出格式

第一行：一个整数，表示 $E^{\prime }$ 中边权和的最小值。

输入输出样例 #1

输入 #1

7 7 4
1 2 3
2 3 2
4 3 9
2 6 2
4 5 3
6 5 2
7 6 4
2 4 7 5

输出 #1

11

说明/提示

【样例解释】

样例中给出的图如下图所示，红色点为 $S$ 中的元素，红色边为 $E^{\prime }$ 的元素，此时 $E^{\prime }$ 中所有边的权值和为 $2+2+3+4=11$，达到最小值。

【数据范围】

对于 $100\%$ 的数据，$1\le n\le 100,1\le m\le 500,1\le k\le 10,1\le u,v\le n,1\le w\le 10^6$。

保证给出的无向图连通，但 可能 存在重边和自环。

---

最小斯坦纳树代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>using namespace std;typedef pair<int, int> PII;
const int N = 110, M = 1010, K = 12;
const int INF = 0x3f3f3f3f;int n, m, k;
int head[N], edge_end[M], next_edge[M], w[M], edge_index;
// f[i][s]表示以i为根节点的斯坦纳树包含点集s的最小代价
int f[N][1 << K];
bool vis[N];void add(int u, int v, int val)  {edge_end[edge_index] = v, next_edge[edge_index] = head[u], w[edge_index] = val, head[u] = edge_index++;
}void dijkstra(int s) {priority_queue<PII, vector<PII>, greater<PII>> q;memset(vis, false, sizeof vis);for (int i = 0; i < n; ++i) {if (f[i][s] != INF) q.push({f[i][s], i});}while (!q.empty()) {auto [dis, u] = q.top();q.pop();if (vis[u]) continue;vis[u] = true;for (int i = head[u]; ~i; i = next_edge[i]) {int ver = edge_end[i];int val = f[u][s] + w[i];if (val < f[ver][s]) {f[ver][s] = val;q.push({f[ver][s], ver});}}}
}int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);memset(head, -1, sizeof head);cin >> n >> m >> k;for (int i = 0; i < m; ++i) {int u, v, w;cin >> u >> v >> w;u--, v--;add(u, v, w);add(v, u, w);}memset(f, 0x3f, sizeof f);for (int i = 0; i < k; ++i) {int ver;cin >> ver;ver--;f[ver][1 << i] = 0;}for (int s = 1; s < 1 << k; ++s) {for (int son = s; son; son = (son - 1) & s) {for (int u = 0; u < n; ++u) {f[u][s] = min(f[u][s], f[u][son] + f[u][s ^ son]);}}dijkstra(s);}int ans = INF;for (int i = 0; i < n; ++i) ans = min(ans, f[i][(1 << k) - 1]);cout << ans << "\n";return 0;
}

对于本题, 只能状态压缩$dp$解决该问题, 假设一共$N$个点, 希望将$[1,k]$之间的点连通, 求最小花费
设计状态$f[i][s]$表示以$i$为根, 至少将点集$s$连通的最小代价, $s$是个二进制数

$i$可以不属于$s$, $s$是$[1,k]$的子集, $ans=\min \left\{f[u][2^k-1]\right\}$

如何进行状态转移?

• 分裂, 将集合分为两部分, f [ i ] [ s ] = min ⁡ { f [ i ] [ T ] + f [ i ] [ S ∣ T ] } f[i][s] = \min \left \{ f[i][T] + f[i][S | T] \right \} f[i][s]=min{f[i][T]+f[i][S∣T]}, 限制$T$, 转移是不带环的
• 换根, $f[u][s]=\min (f[u][s],f[i][s]+w[i][u])$, 转移是带环的, 无法直接计算

但是, 第二个转移方程非常类似于最短路算法, $f[u]=min(f[u],f[i]+w)$, 使用$Dijkstra$算法优化

因此首先用第一个转移方式计算子集对$s$的贡献, 然后再用第二个转移方式计算$s$之间的贡献
时间复杂度$O(n{3}^K+n^2{2}^K)$

对于本题来说, 不仅仅在求$[1,k]$的斯坦纳树, 还要加上两个点$s$和$t$, 不能直接进行暴力状态压缩$dp$, 在询问基础上进行预处理

首先考虑简单情况, 如果只有一组询问, 求的是$10$个点的斯坦纳树, 复杂度$O(3^{10})$, 如果要求 { 1 , 2 , 3 , . . . s , t } \left \{ 1, 2, 3, ... s, t \right \} {1,2,3,...s,t}的斯坦纳树, 等价于求 f [ t ] [ { 1 , 2 , 3 , . . . , s } ] f[t][\left \{ 1, 2, 3, ..., s \right \}] f[t][{1,2,3,...,s}], 总的时间复杂度$O(3^{9}N\times N)$

本题代码

#include <iostream>
#include <algorithm>
#include <cstring>using namespace std;typedef long long LL;
const int N = 80 + 10, M = 12;int n, m;
// f[i][j][k]代表以i为斯坦纳树的根节点, 当前处理的顶点为j, 并且包含集合k的最小代价
LL d[N][N], f[N][N][1 << M];
const LL INF = 4e18;int main() {ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {cin >> d[i][j];}}// Floyd预处理点与点之间的最短距离for (int k = 1; k <= n; ++k) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {d[i][j] = min(d[i][j], d[i][k] + d[k][j]);}}}// 初始化for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {for (int k = 0; k < 1 << (m + 1); ++k) {f[i][j][k] = INF;}}}for (int i = 1; i <= n; ++i) {for (int j = 1; j <= m; ++j) {f[i][j][1 << (j - 1)] = 0;}f[i][i][1 << m] = 0;}// 枚举所有点作为斯坦纳树根节点for (int s = 0; s < 1 << (m + 1); ++s) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {// 子集最当前集合贡献for (int son = s; son; son = (son - 1) & s) {f[i][j][s] = min(f[i][j][s], f[i][j][son] + f[i][j][s ^ son]);}}// 当前集合固定, 换根计算贡献for (int j = 1; j <= n; ++j) {for (int k = 1; k <= n; ++k) {f[i][j][s] = min(f[i][j][s], f[i][k][s] + d[k][j]);}}}}int op_num;cin >> op_num;while (op_num--) {int s, t;cin >> s >> t;LL res = f[s][t][(1 << (m + 1)) - 1];cout << res << "\n";}return 0;
}

警示后人之运算优先级

上面的是对的, 下面的会先运算$(m+1)-1$, 因为$<<$优先级较低