GESP-C++八级 题库
使用 math.h 或 cmath 头文件中的余弦函数,表达式 cos(60) 的结果类型为 double 、值约为 0.5 。
cos函数接受的角度参数是以弧度为单位的。因此,如果要用角度(如60度)作为参数,需要先将其转换为弧度。在C或C++中,可以使用M_PI(在math.h或cmath中定义)来表示π,从而将60度转换为弧度,即60 * M_PI / 180。
诚实国公民只说实话,说谎国公民只说谎话。你来到一处分岔口,一条通往诚实国,一条通往说谎国,但不知是哪一条通往哪里。正在为难之际,走来两位路人,他们都自称是诚实国公民,都说对方是说谎国公民。你想去说谎国,可以这样问其中一位路人:“我要去说谎国,如果我去问另一个路人,他会指向哪一条路?”。
说谎的人回答的是去诚实国的路,诚实的人回答的是去诚实国的路,故而分辨出来。
ABCDE五个小朋友,排成一队跑步,其中AB两人必须排在一起,一共有48种排法。
排列组合捆绑法。AB在一起,看成1个人,AB和BA共2中情况,所以是排队是:2*A(4,4)=48。
已知 double 类型的变量 a 和 b ,则执行语句 a = a + b; b = a - b; a = a - b; 后,变量 a 和 b 的值会互换。
a和b是double类型,加减会造成精度的损失,导致2个变量值不能互换。
一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个,再放回袋子,这样进行3次后,可能的颜色顺序有8种。
为解决哈希函数冲突,可以使用不同的哈希函数为每个表项各建立一个子哈希表,用来管理该表项的所有冲突元素。这些子哈希表一定不会发生冲突。
子哈希表仍然可能产生冲突。
已知 int 类型的变量 a 和 b ,则执行语句 a, b = b, a; 后,变量 a 和 b 的值会互换。( )
一个袋子中有3个完全相同的红色小球、2个完全相同的蓝色小球。每次从中取出1个,再放回袋子,这样进行3次后,可能的颜色顺序有7种。( )
猫和老鼠
时间限制:1.0 s
内存限制:512.0 MB
题目描述
猫和老鼠所在的庄园可以视为一张由n个点和m条带权无向边构成的连通图。结点依次以1,2,...,n编号,结点i(1≤i≤n)有价值为ci的奶酪。在m条带权无向边中,第i(1≤i≤m)条无向边连接结点ui与结点vi,边权wi表示猫和老鼠通过这条边所需的时间。
猫窝位于结点a,老鼠洞位于结点b。对于老鼠而言,结点u是安全的当且仅当:
老鼠能规划一条从结点u出发逃往老鼠洞的路径,使得对于路径上任意结点x(包括结点u与老鼠洞)都有:
猫从猫窝出发到结点x的最短时间严格大于老鼠从结点u沿这条路径前往结点x所需的时间。
老鼠在拿取安全结点的奶酪时不存在被猫抓住的可能,但在拿取不是安全结点的奶酪时则不一定。为了确保万无一失,老鼠决定只拿取安全结点放置的奶酪。请你计算老鼠所能拿到的奶酪价值之和。
输入格式
第一行,两个正整数n,m,分别表示图的结点数与边数。
第二行,两个正整数a,b,分别表示猫窝的结点编号,以及老鼠洞的结点编号。
第三行,n个正整数c1,c2,...,cn,表示各个结点的奶酪价值。
接下来 行中的第i行(1≤x≤m)包含三个正整数ui,vi,wi,表示图中连接结点ui与结点vi的边,边权为wi。
输出格式
输出一行,一个整数,表示老鼠所能拿到的奶酪价值之和。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围
对于40的测试点,保证1≤n≤500,1≤m≤500。
对于所有测试点,保证1≤n≤105,1≤m≤105,1≤a,b≤n且a≠b,1≤ui,vi≤n,1≤wi≤109。
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + 5;
const long long oo = 1e18;
int n, m;
int a, b;
int c[N];
vector<pair<int, int>> e[N];
long long dis[N];
priority_queue<pair<long long, int>> q;
long long ans;
int main() {
scanf("%d%d", &n, &m);
scanf("%d%d", &a, &b);
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = 1; i <= m; i++) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
e[u].emplace_back(make_pair(v, w));
e[v].emplace_back(make_pair(u, w));
}
for (int i = 1; i <= n; i++)
dis[i] = oo;
dis[b] = 0;
q.push(make_pair(-dis[b], b));
while (!q.empty()) {
auto p = q.top();
q.pop();
if (dis[p.second] != -p.first)
continue;
int u = p.second;
for (auto r : e[u]) {
int v = r.first, w = r.second;
if (dis[v] > dis[u] + w) {
dis[v] = dis[u] + w;
q.push(make_pair(-dis[v], v));
}
}
}
for (int i = 1; i <= n; i++)
if (dis[i] < dis[a])
ans += c[i];
printf("%lld\n", ans);
return 0;
}宝石项链
时间限制:1.0 s
内存限制:512.0 MB
题目描述
小 A 有一串包含n枚宝石的宝石项链,这些宝石按照在项链中的顺序依次以1,2,...,n编号,第n枚宝石与第1枚宝石相邻。项链由m种宝石组成,其中第i枚宝石种类为ti。
小 A 想将宝石项链分给他的好朋友们。具体而言,小 A 会将项链划分为若干连续段,并且需要保证每段都包含全部种宝石。请帮小 A 计算在满足条件的前提下,宝石项链最多可以划分为多少段。
输入格式
第一行,两个正整数n,m,分别表示宝石项链中的宝石的数量与种类数。
第二行,n个正整数ti,t2,...,tn,表示每枚宝石的种类。
输出格式
输出一行,一个整数,表示宝石项链最多可以划分的段数。
输入样例 1
输出样例 1
输入样例 2
输出样例 2
数据范围

#include <cstdio>
#include <algorithm>
using namespace std;
const int L = 20;
const int N = 2e5 + 5;
const int oo = 1e9;
int n, m;
int t[N], jump[L][N];
int cnt[N], tot;
int ans;
int go(int u) {
int cnt = 0, ans = 0;
for (int i = L - 1; i >= 0; i--)
if (cnt + jump[i][u] <= n) {
cnt += jump[i][u];
ans += 1 << i;
u = (u + jump[i][u] - 1) % n + 1;
}
return ans;
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d", &t[i]);
t[i + n] = t[i];
}
for (int i = 1, r = 0; i <= n; i++) {
while (tot < m) {
r++;
if (!cnt[t[r]]++)
tot++;
}
jump[0][i] = r - i + 1;
if (!--cnt[t[i]])
tot--;
}
for (int i = 1; i < L; i++)
for (int j = 1; j <= n; j++) {
int tar = (j + jump[i - 1][j] - 1) % n + 1;
jump[i][j] = min(jump[i - 1][j] + jump[i - 1][tar], oo);
}
for (int i = 1; i <= n; i++)
ans = max(ans, go(i));
printf("%d\n", ans);
return 0;
}最短距离



#include <algorithm>
#include <cstdio>
using namespace std;
const int N = 100005;
int n, p, q;
int a, b;
int ans;
// 欧几里得求最大公约数
int gcd(int a, int b) {
if (!a || !b)
return a + b;
return gcd(b, a % b);
}
int main() {
scanf("%d%d%d", &n, &p, &q);
while (n--) {
scanf("%d%d", &a, &b);
if (a == b) {
ans = 0;
} else if (a == 1 || b == 1) {
ans = p;
} else {
// 两种拆分方案:各自单独处理
ans = min(p + p, q + q);
if (gcd(a, b) == 1) {
// 互质,可以合并处理花费p
ans = min(ans, p);
} else {
// 不互质,合并处理花费q
ans = min(ans, q);
}
}
printf("%d\n", ans);
}
return 0;
}树上旅行
时间限制:1 s,内存限制:512 MB
【问题描述】
给定一棵有 n 个结点的有根树,结点依次以 1、2、……、n 编号,其中根结点的编号为 1。
小 A 计划在这棵有根树上进行 q 次旅行。在第 i 次旅行中,小 A 首先会选定结点 si 作为起点,并移动若干次。移动分为以下两种:
(1)移动至当前结点的父结点。特殊地,如果当前位于根结点,则不进行移动。
(2)移动至当前结点的所有子结点中编号最小的结点。特殊地,如果当前位于叶子结点,则不进行移动。
由于移动次数可能很大,对于第 i 次旅行,旅行中的移动将以 ki 个不为零的整数构成的序列 ai,1、ai,2、……、ai,k 表示。
对于 ai,j,若 ai,j > 0 则代表进行 ai,j 次第一种移动;若 ai,j < 0 则代表进行 ai,j 次第二种移动。根据给出的序列从左至右完成所有移动后,小 A 所在的结点即是旅行的终点。
给定每次旅行的起点与移动序列,请你求出旅行终点的结点编号。
【输入描述】
第一行,两个正整数 n、q,分别表示有根树的结点数量,以及旅行次数。
第二行,n -1 个整数 p2、p3、……、pn,其中 pi 表示结点 i 的父结点编号。
接下来 2q 行中的第 2i - 1行(1<=i<=q )包含两个正整数 si、ki,分别表示第 i 次旅行的起点编号,以及移动序列的长度。
第 2i 行包含 k 个整数 ai,1、ai,2、……、ai,k,表示移动序列。
【输出描述】
输出共 q 行,第 i 行包含一个整数,表示第 i 次旅行终点的结点编号。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】

对于所有测试点,保证 1 <= n <= 10^5,1 <= q <= 2×10^4,1 <= pi、si <= n,ki >= 1,且Σki <= 10^5,1<=|ai,j|<=n。
#include <iostream>
using namespace std;
const int N = 1e5 + 5;
const int L = 18;
int n, q;
int h[N], nx[N];
int par[L][N], son[L][N];
void dfs(int u) {
for (int i = 1; i < L; i++)
par[i][u] = par[i - 1][par[i - 1][u]];
son[0][u] = u;
for (int i = h[u]; i; i = nx[i]) {
dfs(i);
if (son[0][u] == u || i < son[0][u])
son[0][u] = i;
}
for (int i = 1; i < L; i++)
son[i][u] = son[i - 1][son[i - 1][u]];
}
int move(int go[L][N], int u, int step) {
for (int i = 0; i < L; i++)
if ((step >> i) & 1)
u = go[i][u];
return u;
}
int main() {
cin >> n >> q;
for (int i = 2; i <= n; i++) {
cin >> par[0][i];
nx[i] = h[par[0][i]];
h[par[0][i]] = i;
}
par[0][1] = 1;
dfs(1);
while (q--) {
int s, k;
cin >> s >> k;
while (k--) {
int a;
cin >> a;
if (a < 0)
s = move(son, s, -a);
else
s = move(par, s, a);
}
cout << s << endl;
}
return 0;
}