首页 › 题库 › GESP编程能力等级认证 › GESP-C++七级

GESP-C++七级 题库

共 270 道题 ,第 14 / 14 页 · 按题型筛选,点「查看答案」核对解析
261 简答题 偏难 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那么就标记走了一次,如果这里被标记两次那么肯定是不满足题目要求。

题目详情
262 简答题 偏难 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,则不可增加修改次数。

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

题目详情
263 简答题 偏难 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为根的子树中不存在黑点的节点数量。还有一个特殊情况,即根节点也可能可以删除,解决方法是钦定一个黑色节点为根。

题目详情
264 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

区间乘积

时间限制:1.0 s

内存限制:512.0 MB

题面描述

小杨有一个包含 n 个正整数的序列A=[a1,a2,...,an]。

小杨想知道有多少对<l,r>(1≤l≤r≤n) 满足al×al+1×...×ar为完全平方数。

一个正整数 x 为完全平方数当且仅当存在一个正整数 y 使得x=y×y。

输入格式

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

第二行包含 n 个正整数a1,a2,...,an,代表序列A。

输出格式

输出一个整数,代表满足要求的 <l,r>数量。


输入样例

5
3 2 4 3 2

输出样例

2

样例解释

满足条件的 <l,r> 有<3,3> 和<1,5>。

数据范围

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

答案与解析
参考答案
#include<bits/stdc++.h>
using namespace std;
map<int,int> mp;
const int N = 1e5+10;
int calc(int x) {
	int res = 0;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			while (x% i == 0){
				x/= i;
				res^=(1<<(i-1));
			}
		}
	}
	if (x != 1) {
		res^=(1<<(x-1));
	}
	return res;
}
int a[N];
int main(){
	int n;
	cin>>n;
	long long ans = 0;
	int pre = 0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		int res = calc(a[i]);
		pre^=res;
		if(pre==0)
			ans++;
		ans+=mp[pre];
		mp[pre]+=1;
	}
	cout<<ans<<"\n";
}

一段区间积的真实值很显然我们无法求出来,那么就要通过完全平方数的性质进行转化。我们有结论:一个数是完全平方数,当且仅当这个数质因数分解后,所有质因子的指数都为偶数。那么,判定一个数是否为完全平方数,可以等价于判定它的所有素因子的指数是否为偶数。注意到a[i]<=30,那么a[i]中质因子的个数只有2,3,5,7,11,13,17,19,23,29共10个,可以用十位的二进制数进行表示,若a[i]中含有奇数个第x个质因子,则让二进制表示的第x位为1,否则为0。设这个十位二进制数为b[i],则问题转变为找到[l,r]满足b[l]b[l+1]b[l+2]…b[r]=0,区间的xor和是满足做差的性质的,进一步转化为sum[r]^sum[l-1]=0(sum数组为b数组的xor前缀和),也就是找l和r,满足sum[r]=sum[l-1],这一步可以先统计出sumi等于某一定值k的数量cnt,根据乘法原理,最终答案为cnt*(cnt-1)/2,而k的取值范围为[0~],可以使用类似桶排的方式统计。

题目详情
265 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

交流问题

问题描述

来自2所学校A校、B校的N名同学相聚在一起相互交流,方便起见,我们把这些同学从1至N编号。他们共进行了M次交流,第i次交流中,编号为ui,vi的同学相互探讨了他们感兴趣的话题,并结交成为了新的朋友。

由于这次交流会的目的是促进两校友谊,因此只有不同学校的同学之间会交流,同校同学并不会相互交流。

作为 A 校顾问,你对 B 校的规模非常感兴趣,你希望求出 B 校至少有几名同学、至多有几名同学。

输入描述

第一行两个正整数N,M,表示同学的人数,交流的次数。

接下来M行,每行两个正整数ui,vi,表示一次交流。

题目保证输入合法,即交流一定是跨校开展的。

输出描述

输出一行两个整数,用单个空格隔开,分别表示 B 校至少有几名同学、至多有几名同学。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

4 3
1 2
2 3
4 2

样例输出 1

1 3

样例输入 2

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

样例输出 2

2 5

数据规模

对于30的测试点,保证N≤17,M≤50;

对于60的测试点,保证N≤500,M≤2000;

对于100的测试点,保证N≤105,M≤2×105。

答案与解析
参考答案
#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

void dfs(vector<vector<int>>& graph, int node, vector<int>& colors, int* color_cnt,
int curr_color) {
	colors[node] = curr_color;
	color_cnt[curr_color]++;
	for (int neighbor : graph[node]) {
		if (colors[neighbor] == -1) {
			dfs(graph, neighbor, colors, color_cnt, curr_color ^ 1);
		}
	}
}
pair<int, int> find_b_school_students(int N, vector<pair<int, int>>& connections) {
	vector<vector<int>> graph(N + 1);
	for (const auto& connection : connections) {
		graph[connection.first].push_back(connection.second);
		graph[connection.second].push_back(connection.first);
	}
	vector<int> colors(N + 1, -1);
	int min_ans = 0;
	for (int i = 1; i <= N; ++i) {
		if (colors[i] == -1) {
			int color_cnt[2] = {0, 0};
			dfs(graph, i, colors, color_cnt, 0);
			min_ans += min(color_cnt[0], color_cnt[1]);
		}
	}
	return make_pair(min_ans, N - min_ans);
}
int main() {
	int N, M;
	cin >> N >> M;
	vector<pair<int, int>> connections(M);
	for (int i = 0; i < M; ++i) {
		cin >> connections[i].first >> connections[i].second;
	}
	pair<int, int> b_students = find_b_school_students(N, connections);
	cout << b_students.first << " " << b_students.second << endl;
	return 0;
}
题目详情
266 简答题 偏难 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;
}
题目详情
267 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

商品交易

时间限制:1.0 s

内存限制:128.0 MB

问题描述

市场上共有N种商品,编号从0至N-1,其中,第i种商品价值vi元。

现在共有M个商人,编号从0至M-1。在第j个商人这,你可以使用第xj种商品交换第yj种商品。每个商人都会按照商品价值进行交易,具体来说,如果vxj>vyj,他将会付给你vyj-vxj元钱;否则,那么你需要付给商人vxj-vyj元钱。除此之外,每次交易商人还会收取1元作为手续费,不论交易商品的价值孰高孰低。

你现在拥有商品a,并希望通过一些交换来获得商品b。请问你至少要花费多少钱?(当然,这个最小花费也可能是负数,这表示你可以在完成目标的同时赚取一些钱。)

输入描述

第一行四个整数N,M,a,b,分别表示商品的数量、商人的数量、你持有的商品以及你希望获得的商品。保证0≤a,b<N,保证 a≠b。

第二行N个用单个空格隔开的正整数v0,v1,…,vN-1,依次表示每种商品的价值。保证1≤vi≤109。

接下来M行,每行两个整数xj,yj,表示第j个商人愿意使用第xj种商品交换第yj种商品。保证0≤xj,yj<N,保证xj≠yj。

输出描述

输出一行一个整数,表示最少的花费。特别地,如果无法通过交换换取商品b,请输出 No solution

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

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

样例输出 1

5

样例解释 1

可以先找2号商人,花2-1=1元的差价以及1元手续费换得商品1,再找4号商人,花4-2=2元的差价以及1元手续费换得商品 。总计花费1+1+2+1=5元。


样例输入 2

3 3 0 2
100 2 4
0 1
1 2
0 2

样例输出 2

-95

样例解释 2

可以找2号商人,直接换得商品2的同时,赚取100-4=96元差价,再支付1元手续费,净赚95元。

也可以先找0号商人换取商品1,再找1号商人换取商品2,不过这样只能赚94元。


样例输入 3

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

样例输出 3

No solution

数据规模

对于30%的测试点,保证N≤10,M≤20。

对于70%的测试点,保证N≤103,M≤104。

对于100%的测试点,保证N≤105,M≤2×105。

答案与解析
参考答案
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;
const int max_n = 1e5 + 10;
int n;
vector<int> edge[max_n];
int val[max_n];
int min_dist[max_n];
int queue[max_n], qh, qt;
void bfs(int src) {
  qh = qt = 0;
  memset(min_dist, 127, sizeof(min_dist));
  queue[++qt] = src;
  min_dist[src] = 0;
  while (qh < qt) {
    int u = queue[++qh];
    for (auto v : edge[u]) {
      if (min_dist[u] + 1 < min_dist[v]) {
        min_dist[v] = min_dist[u] + 1;
        queue[++qt] = v;
      }
    }
  }
}
int main() {
  int m, src, dst;
  ios::sync_with_stdio(false);
  cin >> n >> m >> src >> dst;
  for (int i = 0; i < n; ++i) {
    cin >> val[i];
  }
  for (int i = 0; i < m; ++i) {
    int x, y;
    cin >> x >> y;
    edge[x].push_back(y);
  }
  bfs(src);
  if (min_dist[dst] > n) {
    cout << "No solution\n";
  } else {
    cout << min_dist[dst] - val[src] + val[dst] << '\n';
  }
  return 0;
}
题目详情
268 简答题 偏难 GESP编程能力等级认证 ·GESP-C++七级 · 综合练习

试题名称:纸牌游戏

时间限制:1.0 s

内存限制:128.0 MB

问题描述

你和小杨在玩一个纸牌游戏。

你和小杨各有 3 张牌,分别是 0、1、2。你们要进行N轮游戏,每轮游戏双方都要出一张牌,并按 1 战胜 0,2 战胜1,0 战胜 2 的规则决出胜负。第i轮的胜者可以获得2ai分,败者不得分,如果双方出牌相同,则算平局,二人都可获得ai分(i=1,2,…,N )。

玩了一会后,你们觉得这样太过于单调,于是双方给自己制定了不同的新规则。小杨会在整局游戏开始前确定自己全部n轮的出牌,并将他的全部计划告诉你;而你从第 2 轮开始,要么继续出上一轮出的牌,要么记一次“换牌”。

游戏结束时,你换了t次牌,就要额外扣b1+…+bt分。

请计算出你最多能获得多少分。

输入描述

第一行一个整数N,表示游戏轮数。

第二行N个用单个空格隔开的非负整数a1,……,aN,意义见题目描述。

第三行N-1个用单个空格隔开的非负整数b1,…,bN-1,表示换牌的罚分,具体含义见题目描述。由于游戏进行N轮,所以你至多可以换N-1次牌。

第四行N个用单个空格隔开的整数c1,…,cN-1,依次表示小杨从第 轮至第 轮出的牌。保证ci∈0,1,2。

输出描述

一行一个整数,表示你最多获得的分数。

特别提醒

在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。


样例输入 1

4
1 2 10 100
1 100 1
1 1 2 0

样例输出 1

219

样例解释 1

你可以第1轮出 0,并在第2,3轮保持不变,如此输掉第1,2轮,但在第3轮中取胜,获得2×10=20分;随后,你可以在第4轮中以扣1分为代价改出 1,并在第4轮中取得胜利,获得2×100=200分。如此,你可以获得最高的总分20+200-1=219 。


样例输入 2

6
3 7 2 8 9 4
1 3 9 27 81
0 1 2 1 2 0

样例输出 2

56

数据规模

对于30%的测试点,保证N≤15。

对于60%的测试点,保证N≤100。

对于所有测试点,保证N≤1000;保证0≤ai,bi≤106。

答案与解析
参考答案
#include <cstring>
#include <iostream>
#include <vector>

using namespace std;
const int max_n = 1005;
int n;
int a[max_n], b[max_n], c[max_n];
int dp[3][max_n];
int result(int x, int y) {
  if (x == y + 1 || x == y - 2)
    return 2;
  if (x == y)
    return 1;
  return 0;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> a[i];
  for (int i = 1; i < n; ++i)
    cin >> b[i];
  for (int i = 1; i <= n; ++i)
    cin >> c[i];
  memset(dp, 128, sizeof(dp));
  for (int k = 0; k < 3; ++k) {
    dp[k][0] = result(k, c[1]) * a[1];
  }
  for (int i = 2; i <= n; ++i)
    for (int j = i - 1; j >= 0; --j)
      for (int k = 0; k < 3; ++k) {
        int curr_score = result(k, c[i]) * a[i];
        dp[k][j] = dp[k][j] + curr_score;
        if (j > 0) {
          for (int l = 0; l < 3; ++l) {
            dp[k][j] = max(dp[k][j], dp[l][j - 1] + curr_score - b[j]);
          }
        }
      }
  int ans = -2e9, x = 0;
  for (int j = 0; j < n; ++j)
    for (int k = 0; k < 3; ++k) {
      ans = max(ans, dp[k][j]);
    }
  cout << ans << '\n';
  return 0;
}
题目详情
269 简答题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

拆分

答案与解析
参考答案
#include <cstdio>
using namespace std;
typedef long long ll;
const int mod = 1000000000;

ll qpow(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        if (n == 2) {
            puts("2");
            continue;
        }
        if (n == 3) {
            puts("3");
            continue;
        }
        int r = n % 3;
        int q = n / 3;
        ll ans;
        if (r == 0) {
            ans = qpow(3, q);
        } else if (r == 1) {
            ans = qpow(3, q - 1) * 4 % mod;
        } else { // r == 2
            ans = qpow(3, q) * 2 % mod;
        }
        printf("%lld\n", ans);
    }
    return 0;
}
题目详情
270 简答题 适中 GESP编程能力等级认证 ·GESP-C++七级 · 未分类

物流网络

答案与解析
参考答案
#include <algorithm>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

struct Highway {
  int u, v;
  int fee, b;
  bool operator<(const Highway &other) const {
    return b < other.b;
  }
};

void solve() {
  int n, m;
  cin >> n >> m;
  vector<Highway> highways(m);
  for (int i = 0; i < m; i++) {
    cin >> highways[i].u >> highways[i].v >> highways[i].fee >> highways[i].b;
  }
  sort(highways.begin(), highways.end());

  vector<vector<pair<int, int>>> g(n + 1); // to, fee
  vector<ll> dp1(n + 1, INF);
  vector<ll> dpn(n + 1, INF);
  dp1[1] = 0;
  dpn[n] = 0;
  ll answer = INF;

  auto dijk = [&](int s, vector<ll>& dist) {
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> q;
    q.emplace(dist[s], s);
    while (!q.empty()) {
      auto [d, u] = q.top();
      q.pop();
      if (d > dist[u]) continue;
      for (auto [v, w] : g[u]) {
        if (dist[v] > d + w) {
          dist[v] = d + w;
          q.emplace(dist[v], v);
        }
      }
    }
  };

  for (auto &r : highways) {
    int u = r.u, v = r.v;
    int w = r.fee, bb = r.b;
    // 核心:这里 + bb!你原版漏掉了
    if (dp1[u] != INF && dpn[v] != INF)
      answer = min(answer, dp1[u] + dpn[v] + bb);
    if (dp1[v] != INF && dpn[u] != INF)
      answer = min(answer, dp1[v] + dpn[u] + bb);

    // 再加边进图
    g[u].emplace_back(v, w);
    g[v].emplace_back(u, w);
    // 重新跑Dijkstra更新最短路
    dijk(1, dp1);
    dijk(n, dpn);
  }

  if (answer == INF) cout << -1 << '\n';
  else cout << answer << '\n';
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
  return 0;
}
题目详情