首页 › 题库 › GESP编程能力等级认证 › 3 图的定义及遍历

GESP-C++七级 题库

共 80 道题 ,第 4 / 4 页 · 按题型筛选,点「查看答案」核对解析
章节 3 图的定义及遍历 清除
61 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

非连通图不能使用广度优先搜索算法进行遍历。

A
对
B
错
答案与解析
正确答案:错

非连通图需要进行多次广度优先搜索算法。

题目详情
62 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

动态规划有递推实现和递归实现,对于很多问题,通过记录子问题的解,两种实现的时间复杂度是相同的。

A
对
B
错
答案与解析
正确答案:对

使用递归算法并记录子问题的解就是动态规划中的记忆化搜索,和递推算法实现动态规划的时间复杂度一致

题目详情
63 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

一棵有 个节点的完全二叉树,则树的深度为[log2(N)]+1。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
64 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

要求出简单有向图中从顶点 A 到顶点 B 的最短路径,在深度优先搜索和广度优先搜索中选择,广度优先更适合。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
65 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

动态规划有递推实现和递归实现,有时两种实现的时间复杂度不同。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
66 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

假设一棵完全二叉树共有 个节点,则树的深度为log(N)+1。(   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
67 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

简单有向图有 n 个顶点和 e 条弧,可以用邻接矩阵或邻接表来存储,二者求节点 u 的度的时间复杂度一样。(   )

A
对
B
错
答案与解析
正确答案:错
这道题暂未补解析。
题目详情
68 判断题 偏易 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

广度优先搜索(BFS)能够判断图是否连通。(   )

A
对
B
错
答案与解析
正确答案:对
这道题暂未补解析。
题目详情
69 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

城市规划

题目描述

A 国有n座城市,城市之间由m条双向道路连接,任意一座城市均可经过若干条双向道路到达另一座城市。城市依次以1,2....,n编号。第i(1≤i≤m)条双向道路连接城市ui与城市vi。

对于城市u和城市v而言,它们之间的连通度d(u,v)定义为从城市u出发到达城市 所需经过的双向道路的最少条数。由于道路是双向的,可以知道连通度满足d(u,v)=d(v,u),特殊地有d(u,u)=0。

现在 A 国正在规划城市建设方案。城市u的建设难度为它到其它城市的最大连通度。请你求出建设难度最小的城市,如果有多个满足条件的城市,则选取其中编号最小的城市。形式化地,你需要求出使得max1≤i≤nd(u,i)最小的u,若存在多个可能的u则选取其中最小的。

输入格式

第一行,两个正整数n,m,表示 A 国的城市数量与双向道路数量。

接下来m行,每行两个整数ui,vi,表示一条连接城市ui与城市vi的双向道路。

输出格式

输出一行,一个整数,表示建设难度最小的城市编号。如果有多个满足条件的城市,则选取其中编号最小的城市。

输入样例 1

3 3
1 2
1 3
2 3

输出样例 1

1

输入样例 2

4 4
1 2
2 3
3 4
2 4

输出样例 2

2

数据范围

对于40的测试点,保证1≤n≤300 。

对于所有测试点,保证1≤n≤2000,1≤m≤2000,1≤ui,vi≤n。

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

const int N = 2005;
int n, m;
vector<int> e[N];
int d[N], mx[N], q[N];

void bfs(int u) {
    for (int i = 1; i <= n; i++)
        d[i] = n + 1;
    d[u] = 0;
    q[1] = u;
    int ql = 1, qr = 1;
    while (ql <= qr) {
        int x = q[ql++];
        for (auto y : e[x])
            if (d[x] + 1 < d[y]) {
                d[y] = d[x] + 1;
                q[++qr] = y;
            }
    }
    mx[u] = d[q[qr]];
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        bfs(i);
        if (mx[i] < mx[ans])
            ans = i;
    }
    printf("%d\n", ans);
    return 0;
}
题目详情
70 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

连通图

答案与解析
参考答案
#include <algorithm>
#include <cstdio>
using namespace std;

const int N = 100005;
int n, m;
int f[N];
int ans;

// 带路径压缩的并查集查找
int getf(int u) {
    if (!f[u]) 
        return u;
    return f[u] = getf(f[u]);
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        int fu = getf(u);
        int fv = getf(v);
        if (fu != fv) {
            f[fu] = fv;
        }
    }
    // 统计连通块数量:根节点数量
    ans = 0;
    for (int i = 1; i <= n; ++i) {
        if (getf(i) == i)
            ans++;
    }
    // 连通块数-1 = 最少需要添加的边(生成树边数)
    printf("%d\n", ans - 1);
    return 0;
}
题目详情
71 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

线图

时间限制:1 s,内存限制:512 MB

【问题描述】

给定由 n 个结点与 m 条边构成的简单无向图 G,结点依次以 1、2、……、n 编号。简单无向图意味着 G 中不包含重边与自环。G 的线图 L(G) 通过以下方式构建:

(1)初始时线图 L(G) 为空。

(2)对于无向图 G 中的一条边,在线图 L(G) 中加入与之对应的一个结点。

(3)对于无向图 G 中两条不同的边 (u1, v1)、(u2, v2),若存在 G 中的结点同时连接这两条边(即 u1, v1之一与 u2, v2之一相同),则在线图 L(G) 中加入一条无向边,连接  (u1, v1)、(u2, v2) 在线图中对应的结点。

请你求出线图 L(G) 中所包含的无向边的数量。

【输入描述】

第一行,两个正整数 n、m,分别表示无向图 G 中的结点数与边数。

接下来 m 行,每行两个正整数 ui、vi,表示 G 中连接 ui、vi 的一条无向边。

【输出描述】

输出共一行,一个整数,表示线图 L(G) 中所包含的无向边的数量。

【样例输入1】

5 4
1 2
2 3
3 1
4 5

【样例输出1】

3

【样例输入2】

5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

【样例输出2】

30

【样例解释1】

【数据范围】

对于60%测试点,保证 1 <= n、m <= 500。

对于所有测试点,保证 1 <= n、m <= 100000。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
int n, m, deg[N];
long long ans;
int main() {
    cin >> n >> m;
    while (m--) {
        int u, v;
        cin >> u >> v;
        deg[u]++;
        deg[v]++;
    }
    for (int i = 1; i <= n; i++)
        ans += 1ll * deg[i] * (deg[i] - 1) / 2;
    cout << ans;
    return 0;
}
题目详情
72 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

调味平衡

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 准备了 n 种食材用来制作料理,这些食材依次以 1、2、……、n 编号,第 i 种食材的酸度为 ai,甜度为 bi。

对于每种食材,小 A 可以选择将其放入料理,或者不放入料理。料理的酸度 A 为放入食材的酸度之和,甜度 B 为放入食材的甜度之和。如果料理的酸度与甜度相等,那么料理的调味是平衡的。

过于清淡的料理并不好吃,因此小 A 想在满足料理调味平衡的前提下,合理选择食材,最大化料理的酸度与甜度之和。

你能帮他求出在调味平衡的前提下,料理酸度与甜度之和的最大值吗?

【输入描述】

第一行,一个正整数 n,表示食材种类数量。

接下来 n 行,每行两个正整数 ai、bi,表示食材的酸度与甜度。

【输出描述】

输出共一行,一个整数,表示在调味平衡的前提下,料理酸度与甜度之和的最大值。

【样例输入1】

3
1 2
2 4
3 2

【样例输出1】

8

【样例输入2】

5
1 1
2 3
6 1
8 2
5 7

【样例输出2】

2

【数据范围】

对于40%的测试点,保证 1 <= n <= 10,1 <= ai、bi <= 10。

对于另外20%的测试点,保证 1 <= n <= 50,1 <= ai、bi <= 10。

对于所有测试点,保证 1 <= n <= 100,1 <= ai、bi <= 500。

答案与解析
参考答案
#include <iostream>
using namespace std;
const int N = 105;
const int C = 505;
const int D = N * C * 2;
int n, f[D];
int main() {
    cin >> n;
    for (int i = 0; i < D; i++)
        f[i] = -1e9;
    f[N * C] = 0;
    while (n--) {
        int a, b;
        cin >> a >> b;
        int x = a + b, y = a - b;
        if (y <= 0) {
            for (int i = -y; i < D; i++)
                f[i + y] = max(f[i + y], f[i] + x);
        } else {
            for (int i = D - y - 1; i; i--)
                f[i + y] = max(f[i + y], f[i] + x);
        }
    }
    cout << f[N * C] << endl;
    return 0;
}
题目详情
73 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

图上移动

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 有一张包含 个n 结点与 m 条边的无向图,结点以 1、2、……、n 标号。

小 A 会从图上选择一个结点作为起点,每一步移动到某个与当前小 A 所在结点相邻的结点。

对于每个结点 i(1<=i<=n),小 A 想知道从结点 i 出发恰好移动步1、2、……、k 之后,小 A 可能位于哪些结点。

由于满足条件的结点可能有很多,你只需要求出这些结点的数量。

【输入描述】

第一行,三个正整数 n、m、k,分别表示无向图的结点数与边数,最多移动的步数。

接下来 m 行,每行两个正整数 ui、vi,表示图中的一条连接结点 ui 与 vi 的无向边。

【输出描述】

共 n 行,第 i 行(1<=i<=n )包含 k 个整数,第 j 个整数( 1<=j<=k)表示从结点 i 出发恰好移动 j 步之后可能位于的结点数量。

【样例输入1】

4 4 3
1 2
1 3
2 3
3 4

【样例输出1】

2 4 4
2 4 4
3 3 4
1 3 3

【数据范围】

对于 20% 的测试点,保证 k=1。

对于另外 20% 的测试点,保证 1<=n<=50,1<=m<=50 。

对于所有测试点,保证 1<=n<=500,1<=m<=500 ,1<=k<=20 ,1<=ui、vi<=n 。

答案与解析
参考答案
#include <cstdio>
using namespace std;
const int K = 25;
const int N = 505;
const int E = N << 1;
int n, m, k;
int h[N], to[E], nx[E], et;
int f[K][N][N];
void ae(int u, int v) {
    et++;
    to[et] = v;
    nx[et] = h[u];
    h[u] = et;
}
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        ae(u, v);
        ae(v, u);
    }
    for (int i = 1; i <= n; i++)
        f[0][i][i] = 1;
    for (int t = 1; t <= k; t++)
        for (int x = 1; x <= n; x++)
            for (int y = 1; y <= n; y++)
                if (f[t - 1][x][y])
                    for (int i = h[y]; i; i = nx[i])
                        f[t][x][to[i]] = 1;
    for (int i = 1; i <= n; i++) {
        for (int t = 1; t <= k; t++) {
            int ans = 0;
            for (int j = 1; j <= n; j++)
                ans += f[t][i][j];
            printf("%d%c", ans, " \n"[t == k]);
        }
    }
    return 0;
}
题目详情
74 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

等价消除

时间限制:1 s,内存限制:512 MB

【问题描述】

小 A 有一个仅包含小写英文字母的字符串 。

对于一个字符串,如果能通过每次删去其中两个相同字符的方式,将这个字符串变为空串,那么称这个字符串是可以被等价消除的。

小 A 想知道 S 有多少子串是可以被等价消除的。

一个字符串 S' 是 S 的子串,当且仅当删去 S 的某个可以为空的前缀和某个可以为空的后缀之后,可以得到 S'。

【输入描述】

第一行,一个正整数 |S|,表示字符串 S 的长度。

第二行,一个仅包含小写英文字母的字符串 S。

【输出描述】

一行,一个整数,表示答案。

【样例输入1】

7
aaaaabb

【样例输出1】

9

【样例输入2】

9
babacabab

【样例输出2】

2

【数据范围】

对于 20% 的测试点,保证 S 中仅包含 a 和 b 两种字符。

对于另外 20% 的测试点,保证 1<=|S|<=2000。

对于所有测试点,保证 1<=|S|<=200000。

答案与解析
参考答案
#include <cstdio>
#include <map>
using namespace std;
const int N = 2e5 + 5;
int n;
char s[N];
map <int, int> m;
long long ans;
int main() {
    scanf("%d", &n);
    scanf("%s", s + 1);
    int v = 0;
    m[v]++;
    for (int i = 1; i <= n; i++) {
        v ^= 1 << (s[i] - 'a');
        ans += m[v];
        m[v]++;
    }
    printf("%lld\n", ans);
    return 0;
}
题目详情
75 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

武器购买

时间限制:1.0 s

内存限制:512.0 MB

题面描述

商店里有 n 个武器,第 i 个武器的强度为 pi,花费为 ci。

小杨想要购买一些武器,满足这些武器的总强度不小于 P ,总花费不超过 Q ,小杨想知道是否存在满足条件的购买方案,如果有,最少花费又是多少。

输入格式

第一行包含一个正整数 t ,代表测试数据组数。

对于每组测试数据,第一行包含三个正整数 n,P,Q,含义如题面所示。

之后 n 行,每行包含两个正整数 pi,ci,代表武器的强度和花费。

输出格式

对于每组测试数据,如果存在满足条件的购买方案,输出最少花费,否则输出 -1。


输入样例

3
3 2 3
1 2
1 2
2 3
3 3 4
1 2
1 2
2 3
3 1000 1000
1 2
1 2
2 3

输出样例

3
-1
-1

对于全部数据,保证有 1≤t≤10,1≤n≤100,1≤pi,ci,P,Q≤5×104。

答案与解析
参考答案
#include <bits/stdc++.h>
using namespace std;

#define ll long long
ll dp[50010];
ll solve(int n, int P, int Q, vector<pair<int, int>>& weapons) {
	dp[0] = 0;
	
	for (auto& weapon : weapons) {
		int p = weapon.first;
		int c = weapon.second;
		for (int j = Q; j >= c; --j) {
			if (dp[j - c]>=0) {
				dp[j] = max(dp[j], dp[j - c] + p);
			}
		}
	}
	for (int j = 0; j <= Q; ++j) {
		if (dp[j] >= P) {
			return j;
		}
	}
	
	return -1;
}

int main() {
	int t;
	cin>>t;
	while(t--){
		int n, P, Q;
		cin >> n >> P >> Q;
		memset(dp,-0x3f,sizeof dp);
		vector<pair<int, int> > weapons(n);
		for (int i = 0; i < n; ++i) {
			cin >> weapons[i].first >> weapons[i].second;
		}
		cout << solve(n, P, Q, weapons) << "\n";
	}
	return 0;
}
题目详情
76 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

燃烧

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含 n 个节点的树,其中节点的编号从 1 到 n 。节点 i 的权值为 ai。

小杨可以选择一个初始节点引燃,每个燃烧的节点会将其相邻节点中权值严格小于自身权值的节点也引燃,火焰会在节点间扩散直到不会有新的节点被引燃。

小杨想知道在合理选择初始节点的情况下,最多可以燃烧多少个节点。

输入格式

第一行包含一个正整数 n ,代表节点数量。

第二行包含 n 个正整数 a1,a2,...,an,代表节点权值。

之后 n−1 行,每行包含两个正整数 ui,vi,代表存在一条连接节点 ui和 vi的边。

输出格式

输出一个正整数,代表最多燃烧的节点个数。


输入样例

5
6 2 3 4 5
1 2
2 3
2 5
1 4

输出样例

3

对于全部数据,保证有 1≤n≤105,1≤ai≤106。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int a[N];
int sum[N];
int down[N];
vector<int> g[N];
void dfs_down(int x,int fa){
	down[x]=1;
	for(int i:g[x]){
		if(i!=fa){
			dfs_down(i,x);
			if(a[x]>a[i]){
				down[x]+=down[i];
			}
		}
	}
}
void dfs_sum(int x,int fa){
	if(a[x]>a[fa]){
		sum[x]+=sum[fa]+down[fa];
	}
	for(int i:g[x]){
		if(i!=fa){
			dfs_sum(i,x);
		}
	}
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs_down(1,0);
	dfs_sum(1,0);
	int mx = 0;
	for(int i=1;i<=n;i++){
		mx = max(mx,sum[i]+down[i]);
	}
	cout<<mx<<"\n";
}
题目详情
77 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

小杨寻宝

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含 n 个节点的树,树上的一些节点放置有宝物。

小杨可以任意选择一个节点作为起点并在树上移动,但是小杨只能经过每条边至多一次,当小杨经过一条边后,这条边就会消失。小杨每经过一个放置有宝物的节点就会取得该宝物。

小杨想请你帮他判断自己能否成功取得所有宝物。

输入格式

第一行包含一个正整数 t ,代表测试用例组数。

接下来是 t 组测试用例。对于每组测试用例,一共 n+1 行。

第一行包含一个正整数 n ,代表树的节点数。

第二行包含 n 个非负整数a1,a2,...,an,其中如果 ai=1,则节点 i 放置有宝物,若ai=0,则节点 i 没有宝物。

之后 n−1 行,每行包含两个正整数xi,yi,代表存在一条连接节点xi和yi的边。

输出格式

对于每组测试数据,如果小杨能成功取得所有宝物,输出 Yes,否则输出 No。


输入样例

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

输出样例

Yes
No

对于第一组测试用例,小杨从节点 2 出发,按照2−1−3−4 的顺序即可成功取得所有宝物。

对于全部数据,保证有1≤t≤10,1≤n≤105,0≤ai≤1,且保证树上一定有至少一个节点放置有宝物。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int col[N],dep[N],has[N];
void dfs(int x,int fa){
	dep[x]=dep[fa]+1;
	for(auto i:g[x]){
		if(i!=fa){
			dfs(i,x);
		}
	}
}
bool dfs2(int x,int fa){
	for(auto i:g[x]){
		if(i!=fa){
			auto res = dfs2(i,x);
			if(res==false)return false;
			if(has[i]||col[i])has[x]++;
		}
	}
	if(has[x]>1)return false;
	return true;
}
int main(){
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		for(int i=1;i<=n;i++){
			dep[i]=0;g[i].clear();
			cin>>col[i];
		}
		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,0);
		int mx=0,pos=0;
		for(int i=1;i<=n;i++){
			has[i]=0;
			if(col[i]){
				if(dep[i]>mx){
					mx=dep[i];
					pos=i;
				}
			}
		}
		bool res= dfs2(pos,0);
		if(res)cout<<"Yes\n";
		else cout<<"No\n";
	}
}

通过题意初步可以想到以每一个点作为起点进行搜索,再搜索过程中记录搜到的ai=1的点,搜索结束后比较和1的总数是否相同。由于数据范围较大,因此明显会超时。

由于每个节点只能走一次,所以可以从最深的宝物开始收集可以确保小杨在返回时不会重复经过已经消失的边(因为边会在经过一次后消失)。然后从这个节点回到根节点,如果是1那么就标记走了一次,如果这里被标记两次那么肯定是不满足题目要求。

题目详情
78 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

矩阵移动

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个有一个 n×m 的矩阵,仅包含 01? 三种字符。矩阵的行从上到下编号依次为1,2,...,n,列从左到右编号依次为1,2,...,m 编号。小杨开始在矩阵的左上角(1,1),小杨只能向下或者向右移动,最终到达右下角(n,m)时停止,在移动的过程中每经过一个字符 1 得分会增加一分(包括起点和终点),经过其它字符则分数不变。小杨的初始分数为 0 分。

小杨可以将矩阵中不超过 x 个字符 ? 变为字符 1。小杨在修改矩阵后,会以最优的策略从左上角移动到右下角。他想知道自己最多能获得多少分。

输入格式

第一行包含一个正整数 t ,代表测试用例组数。

接下来是 t 组测试用例。对于每组测试用例,一共 n+1 行。

第一行包含三个正整数n,m,x,含义如题面所示。

之后 n 行,每行包含一个长度为 m 且仅包含 01? 三种字符的字符串。

输出格式

对于每组测试用例,输出一行一个整数,代表最优策略下小杨的得分最多是多少。


输入样例

2
3 3 1
000
111
01?
3 3 1
000
?0?
01?

输出样例

4
2

对于第二组测试用例,将(1,1)或者 (3,3)变成 1 均是最优策略。

对于全部数据,保证有1≤t≤10,1≤n,m≤500,1≤x≤300,同时保证所有测试用例 n×m 的总和不超过 2.5×105。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 505;
int dp[N][1005];
char a[N][N];
int n, m, x;
int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		scanf("%d%d%d", &n, &m, &x);
		for(int i = 1; i <= m; i++) for(int j = 0; j <= x; j++) dp[i][j] = 0;
		for(int i = 1; i <= n; i++) scanf("%s", a[i] + 1);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				for(int k = x; k>=0; k--){
					if(a[i][j] == '1')
						dp[j][k] = max(dp[j][k], dp[j - 1][k]) + 1;
					if(a[i][j] == '0')
						dp[j][k] = max(dp[j][k], dp[j - 1][k]);
					if(a[i][j] == '?') {
						if(!k) dp[j][k] = max(dp[j][k], dp[j - 1][k]);
						else dp[j][k] = max(max(dp[j][k], dp[j - 1][k]), max(dp[j][k
						- 1], dp[j - 1][k - 1]) + 1);
					}
				}
			}
		}
		int ans = 0;
		for(int k = 0; k <= x; k++) ans = max(ans, dp[m][k]);
		printf("%d\n", ans);
	}
}

如果不考虑x,问题转换成为从(1,1)到(n,m)只能向下或者向右移动最多拿到多少个1。对于矩阵中的任意一点(i,j)只可能从(i-1,j)或者(i,j-1)移动过来。

状态设计:dp[i][j]表示到达位置(i,j)时可以获得的最大分数。

不难得到状态转移方程dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + (a[i][j] == ‘1’?1:0)。

考了加入x,还是只能向下或者向右移动,之前只有1对结果有贡献,现在?也对结果有贡献。由于x的限制,?不能无限制的修改成1,所以需要记录修改次数。设计状态时增加一维表示修改次数。

状态设计:dp[i][j][k]表示到达位置(i,j)时,已经修改了k个字符所能获得的最大分数。

如果a[i][j]是0或者1,正常转移,和不考虑x时的转移过程一致,如果a[i][j]是?,先考虑当前有没有修改次数,如果没有当前阶段拿到和1和上一阶段比较求最大值,如果有修改次数,,需要看之前修改转移的值是多少,求最大值。

当a[i][j] == 1时,dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k])+1,

当a[i][j] == 0时,dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

当a[i][j] == ?时,如果没有修改次数,dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

如果有修改次数,再考虑改或不改。

若修改当前节点为1,则有dp[i][j][k]=max(dp[i-1][j][k-1],dp[i][j-1][k-1])+1,

若不修改,则有dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]),

取以上情况的最大值即可,同时需要考虑,若k==x,则不可增加修改次数。

可以观察到每一行的计算只依赖于上一行的信息,第一维可以优化,故可以使用滚动数组对数组进行降维。

题目详情
79 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

黑白翻转

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一棵包含 n 个节点的树,这棵树上的任意一个节点要么是白色,要么是黑色。小杨认为一棵树是美丽树当且仅当在删除所有白色节点之后,剩余节点仍然组成一棵树。

小杨每次操作可以选择一个白色节点将它的颜色变为黑色,他想知道自己最少要执行多少次操作可以使得这棵树变为美丽树。

输入格式

第一行包含一个正整数n,代表树的节点数。

第二行包含 n 个非负整数a1,a2,...,an,其中如果 ai=0,则节点 i的颜色为白色,否则为黑色。

之后 n−1 行,每行包含两个正整数xi,yi,代表存在一条连接节点xi和yi的边。

输出格式

输出一个整数,代表最少执行的操作次数。


输入样例

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

输出样例

2

样例解释

将节点 1 和 3 变为黑色即可使这棵树变为美丽树,此时删除白色节点 5,剩余黑色节点仍然组成一棵树。

数据范围

对于全部数据,保证有1≤n≤105,0≤ai≤1。

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
vector<int> g[N];
int col[N],num[N];
int ans,sum;
void calc(int x,int fa){
	num[x]+=col[x];
	for(auto i:g[x]){
		if(i!=fa){
			calc(i,x);
			num[x]+=num[i];
		}
	}
}
void dfs(int x,int fa){
	int fl=0;
	if(num[x]!=sum&&num[x]!=0)fl=1;
	for(auto i:g[x]){
		if(i!=fa){
			dfs(i,x);
			if(num[i]!=0&&num[i]!=num[x]-col[x]){
				fl=1;
			}
		}
	}
	if(fl==1&&col[x]!=1)ans++;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>col[i];
		sum+=col[i];
	}
	for(int i=1;i<n;i++){
		int u,v;
		cin>>u>>v;
		g[u].push_back(v);
		g[v].push_back(u);
	}
	calc(1,0);
	dfs(1,0);
	cout<<ans<<"\n";
}

我们考虑一个树的哪些节点删除后,依然为一棵树。显然是所有叶子节点。在把所有叶子节点删去后,新的树的叶子节点依然可以继续删除。以此类推。也就是说,对于一个白点u,如果以u为根的子树中不存在黑点的话,那么这个白点就可以被删除,否则该白点需要被染为黑点,只需要一遍深度优先搜索,最终答案为n-黑色节点数量-以u为根的子树中不存在黑点的节点数量。还有一个特殊情况,即根节点也可能可以删除,解决方法是钦定一个黑色节点为根。

题目详情
80 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 3.1 图的概念

俄罗斯方块

题面描述

小杨同学用不同种类的俄罗斯方块填满了一个大小为n×m的网格图。

网格图由n×m个带颜色方块构成。小杨同学现在将这个网格图交给了你,请你计算出网格图中俄罗斯方块的种类数。

如果两个同色方块是四连通(即上下左右四个相邻的位置)的,则称两个同色方块直接连通;若两个同色方块同时与另一个同色方块直接或间接连通,则称两个同色方块间接连通。一个俄罗斯方块由一个方块和所有与其直接或间接连通的同色方块组成。定义两个俄罗斯方块的种类相同当且仅当通过平移其中一个俄罗斯方块可以和另一个俄罗斯方块重合;如果两个俄罗斯方块颜色不同,仍然视为同一种俄罗斯方块。

例如,在如下情况中,方块1和方块2是同一种俄罗斯方块,而方块1和方块3不是同一种俄罗斯方块。

输入格式

第一行包含两个正整数n,m,表示网格图的大小。

对于之后n行,第i行包含m个正整数ai1,ai2,...,aim,表示该行m个方块的颜色。

输出格式

输出一个非负整数,表示俄罗斯方块的种类数。


样例输入

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

样例输出

7

样例解释

数据范围

答案与解析
参考答案
#include <cstdio>
#include <algorithm>
#include <map>
using namespace std;
const int N = 505;
int n, m;
int val[N][N];
int vis[N][N];
int xmin, xmax, ymin, ymax;
int posx[N * N], posy[N * N], cnt;
int idx[N * N];
bool isend[3 * N * N];
map <int, int> ch[3 * N * N];
int root, ncnt;
int ans;
void dfs(int x, int y, int c)
{
	if (x < 1 || x > n || y < 1 || y > m)
		return;
	if (vis[x][y])
		return;
	if (val[x][y] != c)
		return;
	vis[x][y] = 1;
	xmin = min(xmin, x), xmax = max(xmax, x);
	ymin = min(ymin, y), ymax = max(ymax, y);
	posx[++cnt] = x;
	posy[cnt] = y;
	dfs(x - 1, y, c);
	dfs(x + 1, y, c);
	dfs(x, y - 1, c);
	dfs(x, y + 1, c);
}
void go(int &n, int v)
{
	if (!ch[n].count(v))
		ch[n][v] = ++ncnt;
	n = ch[n][v];
	return;
}
void work(int x, int y)
{
	cnt = 0;
	xmin = n, xmax = 1;
	ymin = m, ymax = 1;
	dfs(x, y, val[x][y]);
	for (int i = 1; i <= cnt; i++)
		idx[i] = (posx[i] - xmin) * (ymax - ymin + 1) + (posy[i] - ymin);
	sort(idx + 1, idx + cnt + 1);
	int cur = root;
	int lascnt = ncnt;
	go(cur, xmax - xmin + 1);
	go(cur, ymax - ymin + 1);
	for (int i = 1; i <= cnt; i++)
		go(cur, idx[i]);
	ans += (! isend[cur]);
	isend[cur] = 1;
}
int main()
{
	root = ++ncnt;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			scanf("%d", &val[i][j]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (!vis[i][j])
				work(i, j);
	printf("%d\n", ans);
	return 0;
}
题目详情