2025秋季提高组模拟赛4 做题随笔——套卷题解

2025秋季提高组模拟赛4——做题随笔/套卷题解

文章目录

2025秋季提高组模拟赛4——做题随笔/套卷题解
- 做题感受
- T1 有趣树
- - 题意简述
  - 赛时想法
  - 正解
  - 参考代码
  - 调试心得
  - - 1. 直径中心的正确判定（点 vs 边）
    - 2. 两次 DFS 求直径的返回值与路径构造
  - 小结
- T2点针式打印机
- - 题意简述
  - 赛时想法
  - 参考代码
  - 小结
- T3 最大独立集
- - 题意简述
  - 赛时想法
- 附录
- - T1相关推论证明
  - T3题目相关“翻译”
  - - 诱导子图（Induced Subgraph）
    - - 与普通子图的区别
      - 举个例子
    - 最大独立集（Maximum Independent Set）
    - - 1. 独立集（Independent Set）
      - 2. 最大独立集
      - 3. 与“极大独立集”的区别
      - 4. 温馨提示
      - NP-hard
      - 1. 先理解 P 和 NP
        
        2. NP-hard 的定义
        
        3. 最大独立集是 NP-hard

注：文章持续更新中，敬请期待

做题感受

不得不说，这确实是套好题。囊括了树、矩阵、图论、哈希……但愣是没一道线性题。不过这样一来，补题和写题解对我来说就显得尤为重要~ 因为这些知识点我都不熟

话不多说，直接

start

$s t a r t$ !

T1 有趣树

题意简述

给你一棵包含

(

≤

)

n (1 \\le n \\le 2e5)

$n (1 \leq n \leq 2 e 5)$ 个节点的无根树，没有边权。两点之间的距离为她们的简单路径¹。

给予你一种操作：在不改变原先点之间的连边的情况下，依次添加若干个点进入这棵树(可以不加)，使之成为一棵新的树。

现在问：至少需要添加几个点才能使当前的树拥有多条直径？

赛时想法

完蛋，是树的重心！我不会写！但应该不难写吧……我先推一下先——好像可行。

嗯，有规律，对于一般数据答案至多为

$1$ ，小于节点数

$4$ 的特判一下……欸！树上DP？(当时现推的直径找法假了，所以以为可以树上DP)

好，样例过了；好！大样例过了；好！！手搓特殊数据也过了！这不AC不礼貌了……

蛤。不出意外，

$W A$

80pts

$80 pt s$ 。（主要是因为题目没有多组测试数据导致数据太水了，面向答案编程有

$60$ 分，敲一个

n^2BFS

$n^{2} B F S$ 暴搜也有

$80$ 分）

好吧……

在这里插入图片描述

正解

好吧咱们再重温一遍树的直径：

从无根树任一点出发跑一遍DFS找到最远的(一个)点

以这个点为根找深度最深的点确定直径

跟上哈。好，现在来分析题目：

首先有以下特殊情况：

剩下的答案就为

$0$ 或

$1$ 了²。

那为了解决问题我们现在要做的就是——看是否能再找一条直径。

这里要说一条很“阴暗”的推论：一棵树上的所有直径必然相交于她们的"中点"(严格长度/2，对于奇数/偶数长的直径，中点可以是节点/边)。

这个点也就是树的中心。相关证明附在最后

——欢迎回来。

好那么现在我们已经知道了所有直径交于中点。接下来再找一条直径（或查询是否有更多直径）就很简单了。

在确定第一条直径时递归还原出路径(及直径)，然后折半找到树的中心。

接下来再进行一次DFS：从中点出发搜索，当递归深度等于直径的一半时计数。若计数大于

$2$ (除原先两条半径外另有新的一条半径)，则说明有多条直径，答案为

$0$ ，反之为

$1$ 。

多提一嘴：若直径长度为偶数，则树的“中点”是一条边，这时从边的两端分别向两侧各DFS一次，统计总计数再判定即可。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int o = 2e5 + 22; // 最大节点数 + 一点余量

int n; // 节点数
vector<int> g[o]; // 邻接表存树

int fa[o] = {0}; // 父节点数组，用于记录从起点s出发的路径
int dep[o] = {0}; // 深度数组，记录从起点s到各节点的距离

// 从节点 u 出发（不经过父节点 prt），找到能到达的最远节点
// 返回值：pair<最远距离, 最远节点编号>
pair<int,int> dfs1(int u, int prt)
{
pair<int,int> ans = {0, u}; // 初始：距离0，节点自己
for(auto v : g[u])
{
if(v == prt) continue; // 不走回头路
pair<int,int> k = dfs1(v, u);
k.first++; // 经过边 u-v，距离+1
if(k.first >= ans.first) // 更新更远的节点
ans = k;
}
return ans;
}

// 从节点 u 出发（不经过父节点 prt），记录每个节点的父节点和深度
// 用于后续从直径端点 s 开始构造路径
void pth(int u, int prt)
{
fa[u] = prt;
for(auto v : g[u])
{
if(v == prt) continue;
dep[v] = dep[u] + 1; // 子节点深度 = 当前深度 + 1
pth(v, u);
}
}

// 从节点 u 出发（不经过父节点 prt，也不经过禁节点 ban），
// 统计深度恰好为 tar 的节点个数，结果累加到 cnt
void count_dep(int u, int prt, int deep, int tar, int ban, int &cnt)
{
if(deep == tar) // 到达目标深度
{
cnt++;
return;
}
for(auto v : g[u])
{
if(v == prt || v == ban) continue; // 不走回头路，也不进入禁节点
count_dep(v, u, deep + 1, tar, ban, cnt);
}
}

signed main()
{
// freopen("tree.in", "r", stdin);
// freopen("tree.out", "w", stdout);

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

cin >> n;

// 特殊情况特判（画图即可得出）
if(n == 1) { cout << "3\\n"; return 0; }
if(n == 2) { cout << "2\\n"; return 0; }

// 读入 n-1 条边，建树
for(int i = 1; i < n; i++)
{
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}

// 第一次 DFS：从任意点 1 出发，找到最远点 s（直径的一个端点）
pair<int,int> b = dfs1(1, –1);
int s = b.second;

// 从 s 出发，记录父节点和深度
dep[s] = 0;
pth(s, –1);

// 找到离 s 最远的点 t（直径的另一个端点）
int t = s;
for(int i = 1; i <= n; i++)
if(dep[i] > dep[t]) t = i;
int D = dep[t]; // 直径长度（边数）

// 从 t 回溯到 s，构造直径路径 path（s -> … -> t）
vector<int> path;
int u = t;
while(u != s)
{
path.push_back(u);
u = fa[u];
}
path.push_back(s);
reverse(path.begin(), path.end()); // 现在 path[0]=s, path[D]=t

int ans = 1; // 默认需要增加 1 个节点（直径唯一时）

if(D % 2 == 0)
{
// 直径长度为偶数：中心是一个点
int r = D / 2;
int mid = path[r]; // 中心点
int cnt = 0;
// 统计从中心点出发，距离为 r 的节点个数
count_dep(mid, 0, 0, r, 0, cnt);
if(cnt > 2) ans = 0; // 超过 2 个分支，说明有多条直径
}
else
{
// 直径长度为奇数：中心是一条边 (u, v)
int r = D / 2; // 向下取整
int u = path[r]; // 中心边左侧节点
int v = path[r + 1]; // 中心边右侧节点
int cnt_u = 0, cnt_v = 0;
// 分别在 u 侧和 v 侧统计距离为 r 的节点个数（禁止跨越中心边）
count_dep(u, v, 0, r, v, cnt_u);
count_dep(v, u, 0, r, u, cnt_v);
if(cnt_u * cnt_v > 1) ans = 0; // 两侧乘积大于 1，说明有多条直径
}

cout << ans << "\\n";
return 0;
}

/*
3
1 2
2 3
输出 1

4
1 2
2 3
2 4
输出 0

8
1 2
1 3
2 5
2 4
5 7
3 6
6 8
输出 1

5
1 2
2 3
3 4
4 5
输出 1
*/

调试心得

1. 直径中心的正确判定（点 vs 边）

直径长度为偶数时，中心是一个点；为奇数时，中心是一条边。
所有直径都共享同一个中心，必须根据奇偶性分别处理：
- 偶数：从中心点出发，统计距离为半径的节点数，若 >2 则有多条直径。
- 奇数：从中心边两侧分别统计距离为半径的节点数，若乘积 >1 则有多条直径。
错误做法：选度数最大的点或从直径端点出发统计最长链，都无法准确判断直径条数。

2. 两次 DFS 求直径的返回值与路径构造

第一次 DFS 必须返回最远节点的编号（而不仅是距离），否则后续无法从该端点出发。
第二次 DFS 需要记录每个节点的父节点和深度，以便从最远点回溯构造直径路径。
路径构造时注意顺序：从端点回溯到起点后要 reverse，确保 path[0] 是起点，path[D] 是终点。
中心定位依赖路径索引：偶数取 path[D/2]，奇数取 path[D/2] 和 path[D/2+1]。

小结

多亏了这道题，不然一直到2026年S组复赛前我都不会去学树的直径的。

T2点针式打印机

题意简述

一台针式打印机有一个打孔模板，是一个

(

≤

500

)

n×m(1 \\le n,m \\le 500)

$n \times m (1 \leq n, m \leq 500)$ 的矩阵，包含’0’和’1’，'1’表示模版该位置上有针，'0’则没有。

现需要在耗材上打印出对应的“图案”，耗材是一个

(

≤

500

)

a×b(1 \\le a,b \\le 500)

$a \times b (1 \leq a, b \leq 500)$ 的矩阵，同样含’0’和’1’，'1’表示这个位置需要一个孔，'0’则不需要。

你可以通过移动模版的位置多次按压模板在耗材上打孔实现目标。但是需要注意：

模版和耗材均不可旋转；

耗材打孔后会露出底板，之后该位置就不能再次被打孔，否则机器将损坏视作失败；

模版上的’1’不能超出耗材边界，否则机器将损坏视作失败；

对于

(

≤

)

T(1 \\le T \\le 5)

$T (1 \leq T \leq 5)$ 组测试数据，判断并输出"Yes"或"No"表示每组数据中的任务是否能实现。

另外，保证所有测试数据中’1’的个数小于等于

5e6

$5 e 6$ 。

赛时想法

别乐了，这题我A了！

怎么说？

对于模版而言，记录横向便利第一个’1’出现的位置，然后后面遍历到的’1’统统改为相对于前一个’1’的坐标偏移量，之后嘛……

还是便利目标耗材，一旦遍历到’1’就按照偏移量一次打孔。如果每次打孔将’1’改成’0’，如果出现超出耗材或者不该打孔的情况，就直接判否。

愉快AC~

正确性？因为按照我们的逻辑当在耗材上遍历到一个’1’时，在她前面的’1’已经被打过孔变成’0’了，所以只能从她开始让模版第一根针打孔，再把后面的若干个’1’也打了，如果后续有非法情况就只能算它倒霉，漏了一个针眼导致不能实现既定目标，就直接跳出循环了。

参考代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int o = 1e5 + 22;

char u[1002][1002]; // 点针盘矩阵（a 行 b 列）
char v[1002][1002]; // 目标内容矩阵（n 行 m 列）

signed main()
{
// freopen("printer.in", "r", stdin);
// freopen("printer.out", "w", stdout);

ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int T;
cin >> T;
while (T—)
{
int a, b, n, m;
cin >> a >> b >> n >> m;

// stp 存储点针盘中所有 '1' 的位置信息
// 第一个元素是第一个 '1' 的绝对坐标 (i, j)
// 后续元素是每个 '1' 相对于上一个 '1' 的偏移量 (dx, dy)
vector<pair<int,int>> stp;
pair<int,int> lst = {0, 0}; // 上一个 '1' 的坐标

// 读入点针盘
for (int i = 1; i <= a; i++)
{
for (int j = 1; j <= b; j++)
{
cin >> u[i][j];
if (u[i][j] == '1')
{
if (!stp.size())
{
// 第一个 '1'，记录绝对坐标
stp.push_back({i, j});
lst = {i, j};
}
else
{
// 后续 '1'，记录相对于上一个 '1' 的偏移
stp.push_back({i – lst.first, j – lst.second});
lst = {i, j};
}
}
}
}
int len = stp.size(); // 点针盘中针的数量

// 读入目标内容，并统计 '1' 的总数
int sum = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> v[i][j];
if (v[i][j] == '1') sum++;
}
}

int fg = 0; // 标记是否已经输出过 "No"

// 遍历目标矩阵，寻找第一个 '1' 作为匹配的起点
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (v[i][j] == '1')
{
int x = i, y = j;
v[x][y] = '0'; // 暂时移除这个点
sum—;

// 根据点针盘的偏移，依次检查其他针的位置
for (int k = 1; k < len; k++)
{
x += stp[k].first;
y += stp[k].second;

// 越界或该位置没有 '1'，说明匹配失败
if (x < 1 || x > n || y < 1 || y > m || v[x][y] == '0')
{
cout << "No\\n";
fg = 1;
break;
}

v[x][y] = '0'; // 移除匹配的点
sum—;
}
if (fg) break; // 匹配失败，跳出所有循环

// 如果所有 '1' 都被恰好匹配完
if (!sum)
{
cout << "Yes\\n";
continue; // 继续内层循环，但此时已无 '1'，会自然结束
}
}
}
if (fg) break;
}
}

return 0;
}

/*
2
4 2 3 4
10
01
10
00
1100
0110
1100

2 2 2 2
11
11
01
10

Yes
No

1
4 2 3 4
10
01
10
00
1100
0110
1100
*/

小结

开始看到这道题的时候给我吓坏了，以为是什么从来都没有见过的高深算法。因为题目的时间复杂度实在是非常吃紧，一个二维矩阵的题目除了DP之外我实在想不出什么能在

(

)

O(nlogn)

$O (n l o g n)$ 内解决这个问题的好办法。但是这题用DP有太牵强了，模版里每有一个’1’就要用方程转移一次，还要考虑乱七八糟的非法情况。后来是在想暴力的时候突发奇想用偏移量，结果小贪心一手、时间复杂度一推。耶！正解不出来了吗。

T3 最大独立集

题意简述

出题人终于“小气”了一回，只给你一张至多包含

$26$ 个点的无权无向图

$G$ ，没有重边或自环。

虽然但是，要你求得东西很变态：

——“对于

$G$ 的点集的每一个子集及这个子点集内部之间的连边所共同组成的子图~~（华夏文字博大精深）~~，请求解出该诱导子图(前面那一长串说的就是这个)的最大独立集的大小，——并且，对于这些独立集的大小之和。”

你这次可能真的需要更好的观感

你——回来啦……

赛时想法

天哪，这是什么东西！每个诱导子图、最大独立集、大小之和……我真的会做吗？

不过出题人的好意我还是要好好领会一下，

2^{26}

$2^{26}$ ≈

6e7

$6 e 7$ ，刚刚好爆

512

512MB

$512 M B$ 下的long long。不过int能开

1e7

$1 e 7$ ，介于这个秀珍数据范围完全可以用状压DP。

但是……怎么转移呢？完啦，时间不够！我还是回去检查吧~

附录

T1相关推论证明

设树

$T$ 的直径长度为

$D$ （边数）。取一条直径

$P$ ，端点为

a, b

$a, b$ 。

若

$D$ 为偶数，令

$c$ 为

$P$ 的正中间那个点；

若

$D$ 为奇数，令

$c$ 为

$P$ 正中间那条边的中点（我们可以把这条边看作一个“中心边”）。

我们证明：任意另一条直径

$Q$ 也经过

$c$ 。

假设存在另一条直径

$Q$ ，端点为

x, y

$x, y$ ，且

$Q$ 不经过

$c$ 。

因为树中任意两条路径相交，

$Q$ 与

$P$ 必有公共部分。设它们的交集为路径

$R$ ，且

$R$ 完全位于

$P$ 的一侧（因为

$Q$ 不经过

$c$ ）。不妨设

$R$ 在

$a$ 到

$c$ 这一段上。

设

$R$ 的两个端点为

u, v

$u, v$ ，其中

$u$ 靠近

$a$ ，

$v$ 靠近

$c$ 。由于

$Q$ 是简单路径，

$Q$ 从

$u$ 和

$v$ 分别向两侧延伸，设

$Q$ 的端点为

$x$ （与

$u$ 相连）和

$y$ （与

$v$ 相连）。

于是：

∣

−

∣

−

∣

−

∣

−

∣

(

因为

是直径

)

|x-y| = |x-u| + |u-v| + |v-y| = D \\quad (\\text{因为 } Q \\text{ 是直径})

$∣ x - y ∣ = ∣ x - u ∣ + ∣ u - v ∣ + ∣ v - y ∣ = D (因为 Q 是直径)$

而直径

$P$ 的长度：

∣

−

∣

−

∣

−

∣

−

∣

|a-b| = |a-u| + |u-v| + |v-b| = D

$∣ a - b ∣ = ∣ a - u ∣ + ∣ u - v ∣ + ∣ v - b ∣ = D$

比较两式，得到：

∣

−

∣

−

∣

−

∣

−

∣

|x-u| + |v-y| = |a-u| + |v-b|

$∣ x - u ∣ + ∣ v - y ∣ = ∣ a - u ∣ + ∣ v - b ∣$

注意，

∣

−

∣

|x-u|

$∣ x - u ∣$ 和

∣

−

∣

|a-u|

$∣ a - u ∣$ 是从

$u$ 出发的两条不同分支的长度；

∣

−

∣

|v-y|

$∣ v - y ∣$ 和

∣

−

∣

|v-b|

$∣ v - b ∣$ 是从

$v$ 出发的两条不同分支的长度。

如果

∣

−

∣

−

∣

|x-u| > |a-u|

$∣ x - u ∣ > ∣ a - u ∣$ ，那么

∣

−

∣

−

∣

−

∣

−

∣

|x-y| > |a-u| + |u-v| + |v-b| = D

$∣ x - y ∣ > ∣ a - u ∣ + ∣ u - v ∣ + ∣ v - b ∣ = D$ ，矛盾。所以必须有

∣

−

∣

≤

∣

−

∣

|x-u| \\le |a-u|

$∣ x - u ∣ \leq ∣ a - u ∣$ 。同理

∣

−

∣

≤

∣

−

∣

|v-y| \\le |v-b|

$∣ v - y ∣ \leq ∣ v - b ∣$ 。

但上面等式要求两边相等，因此只能取等号：

∣

−

∣

−

∣

−

∣

−

∣

|x-u| = |a-u|, \\quad |v-y| = |v-b|

$∣ x - u ∣ = ∣ a - u ∣, ∣ v - y ∣ = ∣ v - b ∣$

现在考虑从

$x$ 到

$b$ 的距离：

∣

−

∣

−

∣

−

∣

−

∣

−

∣

−

∣

−

∣

|x-b| = |x-u| + |u-v| + |v-b| = |a-u| + |u-v| + |v-b| = D

$∣ x - b ∣ = ∣ x - u ∣ + ∣ u - v ∣ + ∣ v - b ∣ = ∣ a - u ∣ + ∣ u - v ∣ + ∣ v - b ∣ = D$

所以

$x$ 到

$b$ 也是一条直径，且它经过

$c$ （因为

$v$ 到

$b$ 的路径经过

$c$ ）。

同理，从

$y$ 到

$a$ 的距离也是

$D$ ，也是一条直径。

但这样一来，

$x$ 到

$b$ 和

$x$ 到

$y$ 都是长度为

$D$ 的直径，它们从

$x$ 出发，在

$u$ 处分叉。由于

$x$ 到

$b$ 经过

$c$ ，而

$x$ 到

$y$ 不经过

$c$ ，这会导致从

$y$ 到

$b$ 的距离超过

$D$ ，与直径定义矛盾（具体计算：

∣

−

∣

−

∣

−

∣

−

∣

−

∣

−

∣

−

∣

|y-b| = |y-v| + |v-u| + |u-x| + |x-u| + |u-v| + |v-b|

$∣ y - b ∣ = ∣ y - v ∣ + ∣ v - u ∣ + ∣ u - x ∣ + ∣ x - u ∣ + ∣ u - v ∣ + ∣ v - b ∣$ 之类，会超过

$D$ ）。因此假设不成立。

所以，不存在不经过中心

$c$ 的直径。所有直径都经过

$c$ 。

结论：树的所有直径都共享同一个中心（点或边）。这个中心就是直径的中点。

证毕

T3题目相关“翻译”

诱导子图（Induced Subgraph）

诱导子图（Induced Subgraph）是图论中的一个概念，定义如下：

给定一个图

(

)

G=(V,E)

$G = (V, E)$ ，选择它的一个顶点子集

⊆

S \\subseteq V

$S \subseteq V$ 。由

$S$ 诱导出的子图

[

]

G[S]

$G [S]$ 包含：

顶点集：就是
边集：原图

形式化地：

[

]

(

)

{

(

)

∈

∣

∈

且

∈

}

G[S] = (S, E_S), \\quad E_S = \\{\\, (u,v) \\in E \\mid u \\in S \\text{ 且 } v \\in S \\,\\}

$G [S] = (S, E_{S}), E_{S} = {(u, v) \in E ∣ u \in S 且 v \in S}$

也就是说，诱导子图完全由顶点子集决定：只要选定了顶点，所有两端都在这个子集里的边都必须保留，不能随意删减。

与普通子图的区别

普通子图：可以任意选择顶点子集和边子集，不要求保留所有两端在顶点子集中的边。
诱导子图：只由顶点子集决定，边集是“强制”包含所有两端在该顶点子集中的原边。

所以诱导子图是普通子图的一种特殊情况。

举个例子

原图

$G$ 有顶点

1,2,3

$1, 2, 3$ ，边为

(

)

(1,2)

$(1, 2)$ 和

(

)

(1,3)

$(1, 3)$ 。

选择顶点子集 $S=\\{1,2,3\\} S={1,2,3}，诱导子图 G [ S ] G[S] G[S] 包含所有顶点和所有边。$
选择 $S=\\{1,2\\} S={1,2}，诱导子图 G [ S ] G[S] G[S] 包含顶点 1 , 2 1,2 1,2，以及边 ( 1 , 2 ) (1,2) (1,2)。边 ( 1 , 3 ) (1,3) (1,3) 不包含，因为 3 3 3 不在 S S S 中。$
选择 $S=\\{2,3\\} S={2,3}，诱导子图 G [ S ] G[S] G[S] 包含顶点 2 , 3 2,3 2,3，但没有边，因为原图中 2 2 2 和 3 3 3 之间没有边。$

返回传送门

最大独立集（Maximum Independent Set）

最大独立集（Maximum Independent Set）是图论中的一个经典概念。

1. 独立集（Independent Set）

给定一个图

(

)

G=(V,E)

$G = (V, E)$ ，一个独立集是顶点集

$V$ 的一个子集

$S$ ，满足：

$S$ 中任意两个顶点之间都没有边。

换句话说，独立集中的顶点两两互不相邻。

例如，对于三角形（三个顶点两两相连），任意两个顶点都不构成独立集，因为它们之间有边；但每个单独的顶点构成一个独立集。

2. 最大独立集

最大独立集就是图

$G$ 的所有独立集中，包含顶点数最多的那个独立集。

最大独立集的大小称为图的独立数，通常记作 $\\alpha(G) α(G)。$
注意：最大独立集可能不唯一，但大小是唯一的。

3. 与“极大独立集”的区别

极大独立集（Maximal Independent Set）：不能再加入任何顶点而仍然保持独立性的独立集。也就是说，对于不在集合中的任意顶点，它至少与集合中某个顶点相邻。
最大独立集（Maximum Independent Set）：所有独立集中顶点数最多的那个。

极大独立集不一定是最大独立集。例如，一条长度为

$3$ 的路径（

$4$ 个顶点：

−

1-2-3-4

$1 - 2 - 3 - 4$ ），集合

{

}

\\{2,4\\}

${2, 4}$ 是极大独立集，但不是最大独立集；最大独立集是

{

}

\\{1,3\\}

${1, 3}$ 或

{

}

\\{2,4\\}

${2, 4}$ ，大小都是

$2$ 。

4. 温馨提示

求解最大独立集是 NP-hard 问题：

（如果你好奇心没那么重，建议你不要继续看下去，把它理解为很难的问题就行了）

……

好吧，

NP-hard

NP-hard 是计算复杂性理论中的一个概念，用来描述“至少和 NP 中最难的问题一样难”的问题。

1. 先理解 P 和 NP

P 问题：可以在多项式时间内解决的问题。例如：排序、最短路。
NP 问题：可以在多项式时间内验证一个解是否正确的问题。例如：给定一个图和一个顶点集合，问它是不是独立集，这很容易验证；但找出最大的独立集很难。

显然

⊆

P \\subseteq NP

$P \subseteq N P$ ，但

P=NP

$P = N P$ 是否成立至今未解。

2. NP-hard 的定义

一个问题

$H$ 是 NP-hard 的，如果：

对于所有 NP 问题

$L$ ，都存在一个多项式时间的归约，把

$L$ 转化为

$H$ 。

也就是说，只要你能多项式时间解决

$H$ ，就能多项式时间解决所有 NP 问题。因此

$H$ 至少和 NP 中最难的问题一样难。

注意：

NP-hard 问题不一定属于 NP。它可能根本无法在多项式时间内验证解。
如果一个问题既是 NP-hard，又属于 NP，那么它叫 NP-complete（NP 完全）。

3. 最大独立集是 NP-hard

判定版本：给定图
优化版本：求最大独立集的大小。这是 NP-hard 的。

所以最大独立集没有已知的多项式时间算法。对于一般图，通常只能用指数级算法（如状压 DP、分支限界等。哎呀，好像剧透了）。

……小馋猫！(推把眼镜)

现在总满意了吧？(后面也没了)

不经过重复边或重复点的路径 ↩︎

解释一下，这里是因为一棵树至少有一条直径，最坏情况在这条直径倒数第二个点下方接一个儿子就可以了 ↩︎

2025秋季提高组模拟赛4——做题随笔/套卷题解

文章目录

做题感受

T1 有趣树

题意简述

赛时想法

正解

参考代码

调试心得

1. 直径中心的正确判定（点 vs 边）

2. 两次 DFS 求直径的返回值与路径构造

小结

T2点针式打印机

题意简述

赛时想法

参考代码

小结

T3 最大独立集

题意简述

赛时想法

附录

T1相关推论证明

T3题目相关“翻译”

诱导子图（Induced Subgraph）

与普通子图的区别

举个例子

最大独立集（Maximum Independent Set）

1. 独立集（Independent Set）

2. 最大独立集

3. 与“极大独立集”的区别

4. 温馨提示

NP-hard

1. 先理解 P 和 NP

2. NP-hard 的定义

3. 最大独立集是 NP-hard

相关推荐

评论 抢沙发

评论前必须登录！

热门标签

置顶推荐

热门文章

最新文章

评论抢沙发