题解 | #宙天#
宙天
https://ac.nowcoder.com/acm/contest/120563/A
这是关于B，J题的个人想法
B
直接暴力枚举所有数对，核心逻辑是：
- 对每组测试数据，读入数组；
- 用双重循环遍历所有“位置不同的元素对”（ j 从 0 到 n-1 ， p 从 j+1 到 n-1 ）；
- 对每个数对，调用 gcd 函数判断最大公约数是否大于 1，若找到第一个满足条件的数对则输出并终止循环；
- 若遍历完所有数对都没找到，则输出 -1 。
代码展示
#include<vector>
using namespace std;
long long gcd(long long a, long long b){
a=llabs(a);
b=llabs(b);
while (b != 0) {
long long temp=a%b;
a=b;
b=temp;
}
return a;
}
bool AC(long long a,long long b){
return gcd(a,b)>1;
}
int main(){
int T;
cin>>T;
for(int i=1; i<=T;i++) {
int n;
cin>>n;
vector<long long> a(n);
for(int m = 0; m < n; m++) {
cin>>a[m];
}
bool found=false;
for (int j=0;j<n; j++) {
if (found) break;
for (int p=j+1;p<n;p++) {
if (AC(a[j], a[p])) {
cout << a[j] << " " << a[p] << endl;
found = true;
break;
}
}
}
if (!found) {
cout << -1 << endl;
}
}
return 0;
}
J
预处理完全二叉树每一层的节点数和层的最大节点编号，然后通过查询节点编号所在的层，直接返回该层的节点数
- 预处理层信息（ ve 的构建） 完全二叉树的层具有以下性质：
- 第 d 层（深度为 d ）的理论最大节点数是 2^d （根深度为 0，第 0 层节点数为 2^0=1 ，第 1 层为 2^1=2 ，以此类推）；
- 最后一层的节点数可能不足 2^d （因为完全二叉树最后一层节点集中在左侧）。
通过循环预处理每一层的信息：
- t 初始为 1 （第 0 层的理论最大节点数 2^0 ），每次循环 t <<= 1 （即 t = t \times 2 ，对应下一层的理论最大节点数）；
- 每一层的实际节点数是 min(n, t) （如果剩余节点数 n 超过当前层的理论最大节点数 t ，则该层节点数为 t ；否则为剩余节点数 n ）；
- 每一层的最大节点编号是 t * 2 - 1 （例如：第 0 层最大编号是 1 \times 2 -1 =1 ；第 1 层最大编号是 2 \times 2 -1=3 ；第 2 层是 4 \times 2 -1=7 ，以此类推，这是完全二叉树层的最大节点编号规律）；
- 将每一层的「实际节点数」和「层最大编号」存入 ve ，同时 n -= t 减少剩余节点数，直到 n 为 0。
- 处理查
对于每个查询节点 x ：
- 遍历 ve 中的每一层，判断 x 是否小于等于当前层的「最大节点编号」；
- 若满足，则当前层的「实际节点数」就是与 x 同深度的节点数，输出该值并终止循环。
代码展示
using namespace std;
int main(){
int T;
cin >> T;
while(T--){
long long n = 0ll;
int q;
cin >> n >> q;
vector<array<long long, 2>> ve;
for(long long t = 1ll; n > 0; t <<= 1){
ve.push_back({min(n, t), t * 2 - 1});
n -= t;
}
while(q--){
long long x = 0ll;
cin >> x;
for(int i = 0; i < ve.size(); i++){
long long l = ve[i][0];
long long r = ve[i][1];
if(x <= r){
cout << l << endl;
break;
}
}
}
}
}