#创作计划 GESP6月 7级编程题讲解
2026-06-30 20:17:54
发布于：北京
欢迎大家~里面讲的还算细致！
@AC君 求加精
T1 染色（非官方解法）-- 洛谷试验通过
题目：
小杨同学有一张包含 个结点的无向图 ， 中的结点依次以 编号。
小杨同学发现 中每个结点的度数都是 。显然 中恰好有 条边。
小杨同学想为 中的结点染色，使得任意一条边两端的结点都有不同的颜色。
小杨同学想知道最少需要多少种颜色才能在满足条件的前提下为 染色。
本题包含多组数据。
第一行，一个正整数 ，表示数据组数。
对于每组数据：
第一行，一个正整数 ，表示无向图 中的结点数。
接下来 行，每行两个正整数 ，表示一条连接结点 与 的无向边，整数之间以空格分隔。
保证 中没有重边与自环。
对于每组数据：输出一行，一个整数，表示在满足条件的前提下为 染色需要的最少颜色数。
对于 的测试点，保证 ， 指每个输入中多组数据的 的总和。
对于所有测试点，保证 ，，。保证 中没有重边与自环。
题目大意：
给定一个 个结点的无向图
图 中恰好有 条边
先要为 图进行染色，使得图中任意被同一条边连接的 个结点都能被染上不同的颜色
求：最少需要多少种颜色才能将图 染成符合染色要求的图？
解题思路：（大拆小，小组大）
part1 无向图组成分析
题目中说每个点度数都为 ，所以这个无向图一定是由一个个“环”组成的
可能有人不知道为什么是这样：因为题目中说了保证 中无重边和自环，也就是说，一个节点的度数 一定连接另外 个结点。那如果每个结点都连接另外 个结点，则一定成为若干个环
实在不行画个图：
就像这样，不难发现，无论有多少个结点，都会成为若干个环
无向图中结点 的度数指：与结点 直接相连的边的总条数
part2 环上色方案分析
那既然我们已经探究出了“环”，那就在“环”上深入研究吧
我们思考两种可能
- 第一种：有一个 个结点的环：
这种情况下，我们只需要 种颜色即可
下面是可能的一种方案：
- 第二种：有一个 个结点的环：
这种情况下，我们需要 种颜色
下面是可能的一种方案：
之所以不能用 种颜色涂完，是因为无论怎样，总会有一个点（）被孤立
所以我们可以猜测一个基本规律： 对任意无向简单图，若图内存在任意一条顶点数量为奇数的环，那么不存在仅 类颜色、使相邻顶点颜色互不相同的着色方案，完成合法着色至少需要 种颜色；若图中所有环的顶点数量均为偶数，则仅两种颜色即可实现合法着色。
part3 判断方案分析
从环结点数量入手不好分析，所以我们换种思路
我们可以先假设当前这个环是可以用两种颜色染完的
然后我们发现最关键的特征“两种颜色”，天然形成二分图结构
那这道题就演化成了：在一张无向图上进行二分图染色
对于每个环的染色过程中：
- 如果当前节点已经被染色，跳过该节点
- 如果当前节点未被染色，则将其染成其两侧某一节点的相反颜色
- 染色结束之后，如果发现某一节点与其两侧任意一节点颜色相同，则整体需要 种颜色，否则 种颜色即可
part4 代码关键部分实现方案分析
分 个部分
第一部分：二分图染色
这部分就很简单了，基本属于板子题稍微改一点点
定义 color 数组，记录每个顶点的颜色
对于第 个顶点：
代表第 个结点未上色
代表第 个结点上色成颜色1
代表第 个结点上色成与颜色1相反的颜色
最终：对于所有结点 ，一旦有某个顶点 （ 与 相连）的 ，则直接返回 false，若所有结点遍历完毕后都通过，则返回true
这部分的核心代码：
void bfs(int st) {
queue<int> q;
q.push(st);
color[st] = 0;
while (!q.empty() && !has_odd) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.push(v);
} else if (color[v] == color[u]) {
has_odd = true;
return;
}
}
}
}
第二部分：初始化+遍历所有连通环
这部分就不用说了吧……最基础的知识
洛谷亲测AC代码
#include <bits/stdc++.h>
using namespace std;
const int N = 111111;
vector<int> g[N];
int color[N];
bool has_odd;
int n;
void bfs(int st) {
queue<int> q;
q.push(st);
color[st] = 0;
while (!q.empty() && has_odd == false) {
int u = q.front();
q.pop();
for (int v : g[u]) {
if (color[v] == -1) {
color[v] = color[u] ^ 1;
q.push(v);
} else if (color[v] == color[u]) {
has_odd = true;
return;
}
}
}
}
int main() {
int t;
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; ++i) {
g[i].clear();
}
memset(color, -1, sizeof(color));
has_odd = false;
for (int i = 1; i <= n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; ++i) {
if (color[i] == -1 && has_odd == false) {
bfs(i);
}
}
cout << (has_odd?"3\n" : "2\n");
}
return 0;
}
复杂度
时间复杂度：
空间复杂度：
T2 消消乐（尝试往官方解法上靠）-- 洛谷亲测通过
题目：
给定一个由个整数构成的数组。每次你可以对数组进行以下操作，直到数组变为空：
- 指定中的一个元素，获得该元素两侧相邻元素之和的分数，并将该元素从中删去。
特别地，如果相邻元素不存在则该元素的该侧值视为。例如，对于可以进行以下操作： - 指定元素，获得分数，删去后；
- 指定元素，获得分数，删去后；
- 指定元素，获得分数，删去后变为空。
请问你能获得的分数总和最大是多少？
第一行，一个正整数，表示数组长度。
第二行，个非负整数，表示数组中的整数。
输出一行，一个整数，表示能获得的最大分数总和。
对于的测试点，保证，。
对于所有测试点，保证，。
题目大意：
给定长度为 的数组 ，重复进行删除操作直到数组中无数字为止。
每次删除 时，可获得的分数为 ，两数中任意一数不存在则加分为
求删除完毕元素后能获得的最大分数总和
解题思路：(以终为始、数学推导）
part1 核心特征分析
如果一段闭区间 中最后一个删除的元素的下标是
则代表：
- 在删除代表 的那一项之前，所有在区间 和 的元素应该全部删干净了
- 在删除 的那一刻，左边的元素为 ，右边的元素为 ，所以删除 时，得分一定是
- 因此
part2 模型匹配分析
既然有“区间”和“最高分”的概念，直接匹配区间dp
part3 区间dp定义分析
这个不用说了，直接定义dp数组，其中 代表将数组下标范围 内元素全部删除能获得的最大分数
part4 初始化与边界条件分析
当 ，也就是说只有一个数字的时候，删那一项对于区间来说左右无元素，因此
其他元素默认初始值都为 （你要是想赋值成极小值我也不反对）
part5 状态转移方程分析
由于上面已经说过了总分数的计算规则（part1讲的），所以很容易看出
f[l][r] = max(f[l][r], f[l][k - 1] + f[k + 1][r] + a[l - 1] + a[r + 1]);
part6 答案分析
也是区间dp的老伙伴，直接输出
part7 易错点
洛谷亲测AC代码
#include <bits/stdc++.h>
using namespace std;
#define int long long
int n;
int a[110];
int f[110][110];
signed main() {
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int len = 1; len <= n; len++) {
for (int l = 1; l + len - 1 <= n; l++) {
int r = l + len - 1;
for (int k = l; k <= r; k++) {
f[l][r] = max(f[l][r], f[l][k - 1] + f[k + 1][r] + a[l - 1] + a[r + 1]);
}
}
}
cout << f[1][n] << endl;
return 0;
}
复杂度
时间复杂度：
空间复杂度：
有啥不对的，直接喷！
欢迎各位大佬指点！
祝点赞的：吉星高照、鸿运当头、时来运转、福运绵长、天随人愿、诸事顺遂、否极泰来、福星临门、好运连连、百事大吉、得天独厚、逢凶化吉、天赐良机、福至心灵、顺风顺水、祥瑞常伴、喜从天降、瑞气盈门、万事亨通、洪福齐天、吉人天相、一路坦途、承天之佑、佳运相伴、多福多喜、青云直上、金榜题名、独占鳌头、学业精进、才高八斗、蟾宫折桂、学有所成、笔底生花、博文广识、登科及第、勤学致远、才思泉涌、学业大成、拔萃出群、满腹经纶
鹏程万里、前程似锦、独占魁首、研精覃思、厚积薄发、一举夺魁、笃学有成、学海扬帆、才学兼备、妙笔生花
财源广进、金玉满堂、富贵盈门、日进斗金、财运亨通、堆金积玉、腰缠万贯、财星高照、招财进宝、富贵荣华
黄金万两、生财有道、财禄双全、广纳财源、富贵常临、金银满库、钱途无量、利达三江、丰财聚宝、财气冲天
福禄双全、福财双至、运旺财兴、登科纳财、才富兼备、顺运生财、及第兴家、福盈财满、鸿财大展、祥财永驻
求学顺遂、财源滚滚、福运双收、才旺财丰、逢考必过、千金在握、天赐富贵、勤学聚财、万事生金、及第纳福
有帮助，赞一个