GESP-C++六级 题库
完全二叉树可以用数组存储数据。
完全二叉树比较平衡,因此可以从1开始编号作为根,后续每个节点i,其左右两个孩子的下标为2i,和2i+1。
深度优先搜索(DFS,Depth First Search的简写)属于图算法,其过程是对每一个可能的分支路径深入到不能再深入为止,而且每个节点只能访问一次。( )(2023年12月C++六级)
二叉搜索树可以是空树(没有任何节点)或者单节点树(只有一个节点),或者多节点。如果是多节点,则左节点的值小于父节点的值,右节点的值大于父节点的值,由此推理,右节点树的值都大于根节点的值,左节点树的值都小于根节点的值。( )(2023年12月C++六级)
路径覆盖
题目描述
给定一棵有 n 个结点的有根树 T ,结点依次以 1,2, …, n 编号,根结点编号为1。初始时 T 中的结点均为白色。你需要将 T 中的若干个结点染为黑色,使得所有叶子到根的路径上至少有一个黑色结点。将结点 i 染为黑色需要代价 ci ,你需要在满足以上条件的情况下,最小化染色代价之和。 叶子是指 T 中没有子结点的结点。
输入格式
第一行,一个正整数 n ,表示结点数量。 第二行, n−1 个正整数 f2, f3, …, fn ,其中 fi 表示结点 i 的父结点的编号,保证 fi<i 第三行, n 个正整数 c1, c2, …, cn,其中 ci 表示将结点 i 染为黑色所需的代价。
输出格式
一行,一个整数,表示在满足所有叶子到根的路径上至少有一个黑色结点的前提下,染色代价之和的最小值。
样例
输入样例1
输出样例1
输入样例2
输出样例2
数据范围
对于 40% 的测试点,保证 2 ≤n ≤16
对于另外 20% 的测试点,保证 fi=i-1 对于所有测试点,保证 2 ≤n ≤10^5, 1 ≤ci ≤10^9
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 1e5 + 5;
int n;
int f[N], c[N], cnt[N];
long long ans[N];
vector<int> son[N];
int main() {
scanf("%d", &n);
for (int i = 2; i <= n; i++) {
scanf("%d", &f[i]);
son[f[i]].push_back(i);
cnt[f[i]]++;
}
for (int i = 1; i <= n; i++)
scanf("%d", &c[i]);
for (int i = n; i >= 1; i--) {
ans[i] = c[i];
long long sum = 0;
for (int v : son[i]) {
sum += ans[v];
}
ans[i] = min(ans[i], sum);
}
printf("%lld\n", ans[1]);
return 0;
}最大因数
时间限制:1 s,内存限制:512 MB
【问题描述】
给定一棵有 10^9 个结点的有根树,这些结点依次以 1、2、……、10^9编号,根结点的编号为 1。
对于编号为 k(2 <= k <= 10^9)的结点,其父结点的编号为 k 的因数中除 k 以外最大的因数。
现在有 q 组询问,第 i(1<= i <= q)组询问给定 xi、yi,请你求出编号分别为 xi、yi 的两个结点在这棵树上的距离。
两个结点之间的距离是连接这两个结点的简单路径所包含的边数。
【输入描述】
第一行,一个正整数 q,表示询问组数。
接下来 q 行,每行两个正整数 xi、yi,表示询问结点的编号。
【输出描述】
输出共 q 行,每行一个整数,表示结点 xi、yi 之间的距离。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于60%的测试点,保证 1 <= xi、yi <= 1000。
对于所有测试点,保证 1 <= q <= 1000,1 <= xi、yi <= 10^9。
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 50;
int a[N], cnta, b[N], cntb;
int f[N], t, q;
void factorize(int x, int a[], int &cnt) {
a[0] = x;
t = 0;
for (int i = 2; i * i <= x; i++)
while (x % i == 0) {
f[++t] = i;
x /= i;
}
if (x > 1)
f[++t] = x;
for (int i = 1; i <= t; i++)
a[i] = a[i - 1] / f[i];
cnt = t;
}
int main() {
cin >> q;
while (q--) {
int x, y;
cin >> x >> y;
factorize(x, a, cnta);
factorize(y, b, cntb);
int px = 0, py = 0;
while (a[px] != b[py]) {
if (a[px] > b[py])
px++;
else
py++;
}
cout << px + py << endl;
}
return 0;
}树上漫步
时间限制:1 s,内存限制:512 MB
【问题描述】
小 A 有一棵 n 个结点的树,这些结点依次以 1、2、……、n标号。
小 A 想在这棵树上漫步。具体来说,小 A 会从树上的某个结点出发,每一步可以移动到与当前结点相邻的结点,并且小 A 只会在偶数步(可以是零步)后结束漫步。
现在小 A 想知道,对于树上的每个结点,从这个结点出发开始漫步,经过偶数步能结束漫步的结点有多少个(可以经过重复的节点)。
【输入描述】
第一行,一个正整数 n。
接下来 n - 1 行,每行两个整数 ui、vi,表示树上有一条连接结点 ui 和结点 vi 的边。
【输出描述】
一行, n 个整数,第 i 个整数表示从结点 i 出发开始漫步,能结束漫步的结点数量。
【样例输入1】
【样例输出1】
【样例输入2】
【样例输出2】
【数据范围】
对于 20% 的测试点,保证 1<=n<=1000。
对于所有测试点,保证 1<=n<=200000。
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
const int E = N << 1;
int n;
int h[N], to[E], nx[E], et;
int cnt[N], bel[N];
void ae(int u, int v) {
et++;
to[et] = v;
nx[et] = h[u];
h[u] = et;
}
void dfs(int u, int c, int f) {
bel[u] = c;
cnt[c]++;
for (int i = h[u]; i; i = nx[i])
if (to[i] != f)
dfs(to[i], c ^ 1, u);
}
int main() {
scanf("%d", &n);
for (int i = 1; i < n; i++) {
int u, v;
scanf("%d%d", &u, &v);
ae(u, v);
ae(v, u);
}
dfs(1, 0, 0);
for (int i = 1; i <= n; i++)
printf("%d%c", cnt[bel[i]], " \n"[i == n]);
return 0;
}树上游走
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含无穷节点的二叉树(即每个节点都有左儿子节点和右儿子节点;除根节点外,每个节点都有父节点),其中根节点的编号为 1,对于节点 i ,其左儿子的编号为 2×i,右儿子的编号为 2×i+1。
小杨会从节点 s 开始在二叉树上移动,每次移动为以下三种移动方式的任意一种:
第1种移动方式: 如果当前节点存在父亲节点,向上移动到当前节点的父亲节点,否则不移动;
第2种移动方式: 移动到当前节点的左儿子;
第3种移动方式: 移动到当前节点的右儿子。
小杨想知道移动 n 次后自己所处的节点编号。数据保证最后的所处的节点编号不超过 1012。
输入格式
第一行包含一个正整数 n,s,代表移动次数和初始节点编号。
第二行包含一个长度为 n 且仅包含大写字母 U,L,R 的字符串,代表每次移动的方式,其中 U 代表第1种移动方式,L 代表第2种移动方式,R代表第3种移动方式。
输出格式
输出一个正整数,代表最后所处的节点编号。
输入样例
输出样例
样例解释
小杨的移动路线为 2-1-3-7。

对于全部数据,保证有 1≤n≤106,1≤s≤1012。
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll INF = 1e12;
int n;
stack<char> st;
string c;
ll s;
int main(){
cin >> n >> s >> c;
for(int i = 0; i < n; i ++){
if(c[i] == 'U'){
if(s == 1) continue;
if(st.size()){
st.pop();
continue;
}
s >>= 1;
}else if(c[i] == 'L'){
if((s << 1) > INF){
st.push('L');
continue;
}
s = s << 1;
}else{
if((s << 1 | 1) > INF){
st.push('R');
continue;
}
s = s << 1 | 1;
}
}
cout << s << "\n";
return 0;
}二叉树
时间限制:1.0 s
内存限制:512.0 MB
题面描述
小杨有一棵包含n个节点的二叉树,且根节点的编号为1。这棵二叉树任意一个节点要么是白色,要么是黑色。之后小杨会对这棵二叉树进行q次操作,每次小杨会选择一个节点,将以这个节点为根的子树内所有节点的颜色反转,即黑色变成白色,白色变成黑色。
小杨想知道q次操作全部完成之后每个节点的颜色。
输入格式
第一行一个正整数n,表示二叉树的节点数量。
第二行n−1个正整数,第i(1≤i≤n−1) 个数表示编号为i+1 的节点的父亲节点编号,数据保证是一棵二叉树。
第三行一个长度为n的01 串,从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。
第四行一个正整数q,表示操作次数。
接下来q行每行一个正整数ai(1≤ai≤n),表示第i次操作选择的节点编号。
输出格式
输出一行一个长度为n的01 串,表示q次操作全部完成之后每个节点的颜色。从左到右第i(1≤i≤n) 位如果为0,表示编号为i的节点颜色为白色,否则为黑色。
输入样例
输出样例
样例解释
第一次操作后,节点颜色为:011010
第二次操作后,节点颜色为:000000
第三次操作后,节点颜色为:010000
数据范围

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
int n;
int son[N][2];
int f[N],col[N],sum[N];
void dfs(int x,int now){
now+=sum[x];
if(now&1)col[x]^=1;
for(int i=0;i<2;i++){
if(son[x][i]!=-1)dfs(son[x][i],now);
}
}
int main(){
cin>>n;
memset(son,-1,sizeof son);
for(int i=2;i<=n;i++){
cin>>f[i];
for(int j=0;j<2;j++){
if(son[f[i]][j]==-1){
son[f[i]][j]=i;
break;
}
}
}
string s;
cin>>s;
for(int i=1;i<=n;i++){
col[i]=s[i-1]-'0';
}
int q;
cin>>q;
while(q--){
int x;
cin>>x;
sum[x]+=1;
}
dfs(1,0);
for(int i=1;i<=n;i++){
cout<<col[i];
}
cout<<"\n";
}①比较朴素的思路为建树,每次操作时执行DFS,将操作的结果处理,最终输出每个节点颜色,极端情况下每次操作遍历整棵树的话,复杂度O(nq),只能解决40%的数据。
②考虑到程序只要最终结果,因此中间结果没必要完全求得,取反操作的周期为2,具有奇偶性,因此每次操作X时,将X的位置打个标记,表示其将影响X下方的每个节点翻转一次,当所有操作标记完,执行DFS,从root=1出发,统计到达每个节点X时的标记的数量cnt,如果cnt为奇数,则改点颜色取反,否则保持原来颜色。这样只需要O(n+q)的复杂度。