GESP-C++七级 题库
学习小组
时间限制:1.0 s
内存限制:512.0 MB

输入样例 1
输出样例 1
输入样例 2
输出样例 2

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 305;
int n;
int c[N], a[N];
int f[N][N];
int ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
sort(c + 1, c + n + 1);
for (int i = n; i >= 1; i--)
for (int j = 1; j <= n; j++)
for (int k = i; k <= n; k++) {
int diff = 0;
if (i > 1)
diff = c[n - j + 1] - c[j];
f[j][k] = max(f[j][k], f[j - 1][k - i] + a[i] + diff);
if (k == n)
ans = max(ans, f[j][k]);
}
printf("%d\n", ans);
return 0;
}金币收集



#include <algorithm>
#include <cstdio>
using namespace std;
const int INF = 2e9;
const int N = 100005;
int n;
int x[N], t[N];
int p[N], f[N];
int mx;
// 排序规则:先按x升序,x相同则按t升序
bool cmp(int a, int b) {
if (x[a] != x[b])
return x[a] < x[b];
return t[a] < t[b];
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d%d", &x[i], &t[i]);
t[i] -= x[i]; // 转换为 t' = t - x
p[i] = i; // 下标数组,用于排序
f[i] = INF;
}
// 按x从小到大排序所有点
sort(p + 1, p + n + 1, cmp);
mx = 0;
f[0] = 0;
for (int i = 1; i <= n; ++i) {
int val = t[p[i]];
if (val < 0) continue; // 负数直接无法选取
// 二分查找最大长度r,满足 f[r] <= val
int l = 0, r = mx;
while (l < r) {
int mid = (l + r) / 2 + 1;
if (val < f[mid])
r = mid - 1;
else
l = mid;
}
// 可以拼出长度 r+1 的子序列
mx = max(mx, r + 1);
if (val < f[r + 1]) {
f[r + 1] = val;
}
}
printf("%d\n", mx);
return 0;
}区间乘积
时间限制: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>数量。
输入样例
输出样例
样例解释
满足条件的 <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~],可以使用类似桶排的方式统计。
交流问题
问题描述
来自2所学校A校、B校的N名同学相聚在一起相互交流,方便起见,我们把这些同学从1至N编号。他们共进行了M次交流,第i次交流中,编号为ui,vi的同学相互探讨了他们感兴趣的话题,并结交成为了新的朋友。
由于这次交流会的目的是促进两校友谊,因此只有不同学校的同学之间会交流,同校同学并不会相互交流。
作为 A 校顾问,你对 B 校的规模非常感兴趣,你希望求出 B 校至少有几名同学、至多有几名同学。
输入描述
第一行两个正整数N,M,表示同学的人数,交流的次数。
接下来M行,每行两个正整数ui,vi,表示一次交流。
题目保证输入合法,即交流一定是跨校开展的。
输出描述
输出一行两个整数,用单个空格隔开,分别表示 B 校至少有几名同学、至多有几名同学。
特别提醒
在常规程序中,输入、输出时提供提示是好习惯。但在本场考试中,由于系统限定,请不要在输入、输出中附带任何提示信息。
样例输入 1
样例输出 1
样例输入 2
样例输出 2
数据规模
对于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;
}商品交易
时间限制: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
样例输出 1
样例解释 1
可以先找2号商人,花2-1=1元的差价以及1元手续费换得商品1,再找4号商人,花4-2=2元的差价以及1元手续费换得商品 。总计花费1+1+2+1=5元。
样例输入 2
样例输出 2
样例解释 2
可以找2号商人,直接换得商品2的同时,赚取100-4=96元差价,再支付1元手续费,净赚95元。
也可以先找0号商人换取商品1,再找1号商人换取商品2,不过这样只能赚94元。
样例输入 3
样例输出 3
数据规模
对于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;
}试题名称:纸牌游戏
时间限制: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
样例输出 1
样例解释 1
你可以第1轮出 0,并在第2,3轮保持不变,如此输掉第1,2轮,但在第3轮中取胜,获得2×10=20分;随后,你可以在第4轮中以扣1分为代价改出 1,并在第4轮中取得胜利,获得2×100=200分。如此,你可以获得最高的总分20+200-1=219 。
样例输入 2
样例输出 2
数据规模
对于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;
}