【题解and标准程序】2025 SYNU 十二月周赛Round I (Div 3) 暨 CEIT 算法集训队蓝桥杯选拔赛

写在最前面，题目的设计完全按照蓝桥杯的形式来，难度也与蓝桥杯省赛相似，而且是OI赛制，因此本场比赛没有出特别难的题 (,w,)

A. 成见与大山

我们可以通过不断地除以2和模2来获取每个数二进制下的位数，也可以使用位运算右移和和位与来操作。复杂度 $O(n \log n)$

using i64 = long long;
void solve()
{
    cin.tie(0) -> sync_with_stdio(0);
    i64 x;
    cin >> x;
    int cnt = 0;
    for(int i = 62; i >= 0; i ++)
    {
        cnt += (x & 1ll);
        x >>= 1;
    }
    cout << cnt << '\n';
}

当然，一种更快的方法是使用bitset容器。

using i64 = long long;
void solve()
{
    cin.tie(0) -> sync_with_stdio(0);
    i64 x;
    cin >> x;
    cout << bitset<64>(x).count() << '\n';
}

B. 相切

可以通过解三角形将小半圆的半径表示出来，然后直接带入做差即可。

$$S = \frac{\pi R^2}{2} - \frac{\pi {(\sqrt{R^2-(\frac{L}{2})^2})}^2}{2}$$

化简一下就能得到：

$$S = \frac{\pi L^2}{8}$$

注意保留小数精度即可。

#include"bits/stdc++.h"
using namespace std;
int main(){
    int x;
    scanf("%d",&x);
    printf("%.10lf",((x*x*1.0)/4.0)*acos(-1)/2.0);
    return 0;
}

C. 协乐

题意很简单，对1~n的每个数，求出他的因数个数，然后求和。

但是需要注意的是，$n$ 的范围达到了1e12，因此假设对每个数进行质因数分解，最多只能通过50%的测试点。

int divide(int x)
{
    int res = 1;
    for(int i = 2; i <= n / i; i ++)
    {
        int t = 1;
        while(x % i == 0) x /= i, t ++;
        res *= t;
    }
    if(x > 1)
    {
        res *= 2;
    }
    return res;
}

void solve()
{
    long long ans = 0;
    for(int i = 1; i <= n; i ++)
    {
        ans += divide(i);
    }
    cout << ans << '\n';
}

我们考虑贡献法，原题要求x的所有因数，我们可以反求 $y$ 是哪些数的因数，那么 $y$ 的贡献就是这些数的个数，很显然，这是一个求 $y$ 在 $n$ 的范围内有多少倍数的问题，答案就是 $\lfloor \frac{n}{y} \rfloor$。

那么答案转化成了求解：

$$\sum_{i=1}^n \lfloor \frac{n}{i} \rfloor$$

这个式子可以用整数分块优化到 $O(\sqrt n)$，因此可以通过。

#include "bits/stdc++.h"
#define endl '\n'
using i64 = long long;
using namespace std;

int main(){
    i64 n;
    cin>>n;
    i64 ans=0;
    for(i64 i = 1, j; i <= n; i = j + 1){
        j = n / (n / i);
        ans += (j - i + 1ll) * (n / i);
    }
    cout<<ans<<endl;
    return 0;
}

D. 数组构造

本题一共提供2种做法。

方法1：正向构造

一个很显然的观点是，最大值一定是起点，因为如果 $a_q$ 要被构造出来，需要存在一个端点 $a_p$ 使得 $a_q \le a_p$。

找到起点 $p$ 后，我们可以考虑维护左右端点 $L$ 和 $R$，根据上面的构造条件，我们构造的过程一定是保证端点从大到小构造。可以考虑将起点左右两端的所有数以 $(value, position)$ 的结构存入大根堆。

每次弹出一个堆顶 $(v, p)$，会出现2种情况：

• $p \not \in [L, R]$，这说明 $p$ 是下一个需要构造的端点，因此可以考虑暴力拓展一个端点到 $p$ （如果p > R 就暴力把R拓展到p，并且R经过的位置也顺便构造了，p < L 同理），由于堆保证了端点的递减性质，而且每次只有一个端点会移动，另一个端点一定会是大于等于未构造出的位置。
• $p \in [L,R]$，则说明p一定在上面拓展的时候被构造出了，直接跳过即可。

这样的复杂度是 $O(n \log n)$。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    
    // 找到一个最大值作为起始位置
    int max_val = 0;
    int start_pos = 1;
    for (int i = 1; i <= n; i++) {
        if (a[i] > max_val) {
            max_val = a[i];
            start_pos = i;
        }
    }
    
    cout << start_pos << " " << max_val << "\n";
    
    // 使用优先队列处理剩余的位置
    priority_queue<pair<int, int>> pq;
    for (int i = 1; i < start_pos; i++) {
        pq.push({a[i], i});
    }
    for (int i = start_pos + 1; i <= n; i++) {
        pq.push({a[i], i});
    }
    
    int left_bound = start_pos;
    int right_bound = start_pos;
    
    while (!pq.empty()) {
        auto [val, pos] = pq.top();
        pq.pop();
        
        // 如果该位置已经在当前范围内，跳过
        if (pos >= left_bound && pos <= right_bound) {
            continue;
        }
        
        if (pos < left_bound) {
            // 向左扩展
            for (int i = left_bound - 1; i >= pos; i--) {
                cout << "L " << a[i] << "\n";
            }
            left_bound = pos;
        } else {
            // 向右扩展
            for (int i = right_bound + 1; i <= pos; i++) {
                cout << "R " << a[i] << "\n";
            }
            right_bound = pos;
        }
    }
    
    return 0;
}

方法2：考虑反向构造

仍然引用上面的定理，因为如果 $a_q$ 要被构造出来，需要存在一个端点 $a_p$ 使得 $a_q \le a_p$。

我们可以考虑把数组看成一个收缩的过程。对于当前端点 $a_L, a_R$，其中一定是有一个被另外一个构造出来的，于是考虑比较 $a_L$ 和 $a_R$ 的大小，如果 $a_R \le a_L$ 则说明 $a_R$ 是由 $a_L$ 构造出来的，因此可以用一个栈记录这个过程，把这个操作压入栈内，此时 $R$ 向内移动一步。反之也是一样的道理。

最终一定只剩下一个位置，这就是起点，输出这个起点，然后再依次弹出栈内的操作即可。

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int l = 1, r = n;
    stack<pair<char, int>> stk;
    while(l < r)
    {
    	if(a[r] <= a[l])
    		stk.push({'R', a[r--]});
    	else
    		stk.push({'L', a[l++]});
    }
    cout << r << ' ' << a[r] << '\n';
    while(stk.size())
    {
    	auto [x, y] = stk.top();
    	stk.pop();
    	cout << x << ' ' << y << '\n';
    }
    return 0;
}

这样的复杂度是 $O(n)$。