A. 全体除2

题意简介

给定 N 个正整数。如果当前所有数都是偶数，就可以执行一次操作：每个数除以 2。问最多操作多少次。

思路分析

一个数能被连续除以 2 的次数，就是它因子中 2 的个数。

要让所有数同时能除，取所有数中 2 的因子个数的最小值即可。

时间复杂度：O(N · log ai)

C++ 代码

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    int ans = 1e9; // 初始化为很大的值，取最小用

    for (int i = 0; i < n; i++) {
        long long x;
        cin >> x;

        int cnt = 0; // 统计当前数能除以 2 多少次
        while (x % 2 == 0) {
            x /= 2;
            cnt++;
        }

        // 取所有数中的最小值
        if (cnt < ans) {
            ans = cnt;
        }
    }

    cout << ans << endl;
    return 0;
}

---

B. 强回文串

题意简介

给定一个长度为奇数的小写字符串 S，判断它是否为强回文串，需同时满足：

1. 整个字符串是回文串
2. 去掉最中间字符后，左半部分是回文串
3. 去掉最中间字符后，右半部分是回文串

思路分析

写一个辅助函数判断回文，依次检查三个条件即可。

时间复杂度：O(|S|)

C++ 代码

#include <iostream>
#include <string>
using namespace std;

// 判断字符串 s 的 [l, r] 区间是否为回文
bool isPal(string &s, int l, int r) {
    while (l < r) {
        if (s[l] != s[r]) {
            return false;
        }
        l++;
        r--;
    }
    return true;
}

int main() {
    int t;
    cin >> t;

    while (t--) {
        string s;
        cin >> s;

        int n = s.size();
        int mid = n / 2; // 中间字符的位置

        // 条件1: 整个字符串回文
        bool ok1 = isPal(s, 0, n - 1);
        // 条件2: 去掉中间后，左半部分回文
        bool ok2 = isPal(s, 0, mid - 1);
        // 条件3: 去掉中间后，右半部分回文
        bool ok3 = isPal(s, mid + 1, n - 1);

        if (ok1 && ok2 && ok3) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

---

C. 不同面积的长方形的种类

题意简介

有 n 根木棍，第 i 根长度为 ai。每次用 4 根木棍拼长方形（两两对边等长，正方形也算）。问能拼出多少种不同面积。

思路分析

关键观察：

• 拼长方形：选两种长度 a 和 b（a != b），每种至少 2 根 → 面积 a × b
• 拼正方形：一种长度 a 至少 4 根 → 面积 a × a
• 面积相同只算一种

算法步骤：

1. 统计每种长度出现次数 cnt[len]
2. 用标记数组记录哪些面积出现过
3. 枚举所有长度对 (a, b)，a <= b，标记面积 a × b

时间复杂度：O(V²)，其中 V = 5000

C++ 代码

#include <iostream>
using namespace std;

int cnt[5005];       // cnt[i] = 长度为 i 的木棍数量
bool used[25000005]; // used[v] = 面积 v 是否已出现

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        cnt[x]++;
    }

    int ans = 0;

    // 枚举所有长度对 (a, b)，其中 a <= b
    for (int a = 1; a <= 5000; a++) {
        // 长度 a 至少需要 2 根
        if (cnt[a] < 2) continue;

        for (int b = a; b <= 5000; b++) {
            // 长度 b 至少需要 2 根
            if (cnt[b] < 2) continue;

            // 如果 a == b，需要至少 4 根才能拼正方形
            if (a == b && cnt[a] < 4) continue;

            int area = a * b;
            if (!used[area]) {
                used[area] = true;
                ans++;
            }
        }
    }

    cout << ans << endl;
    return 0;
}

---

D. 霸王龙的进化之路

题意简介

有 n 项试炼，每项需要 1 天完成。每项试炼有期限 d（必须在第 d 天前完成）和声望 v。每天只能做一项，求最大总声望。

思路分析

经典贪心：按声望从大到小排序，优先安排高声望的任务。

对于每个任务，从它的截止日期 d 开始往前扫描，找到第一个空闲的天数安排上去。这样做的好处是：尽量把任务安排在靠后的天数，把前面的天数留给其他截止日期更早的任务。

为什么按声望降序贪心是正确的？

• 声望高的任务优先安排，保证不会因为被低声望任务占了位置而浪费
• 从截止日期往前找空闲天，是为了尽量不影响截止日期更早的其他任务

时间复杂度：O(n²)（排序 O(n log n)，每个任务最多扫描 n 天）

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;

// 试炼任务结构体
struct Task {
    int t; // 截止期限
    int v; // 声望值
};

Task s[200005];
int day[200005]; // day[i] 表示第 i 天安排的任务声望，0 表示空闲

// 按声望从大到小排序
bool cmp(Task &a, Task &b) {
    return a.v > b.v;
}

int main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> s[i].t >> s[i].v;
    }

    // 按声望降序排序，优先安排高声望任务
    sort(s + 1, s + 1 + n, cmp);

    for (int i = 1; i <= n; i++) {
        // 从截止日期往前找第一个空闲天
        for (int j = s[i].t; j >= 1; j--) {
            if (day[j] == 0) {
                day[j] = s[i].v; // 安排到第 j 天
                break;
            }
        }
    }

    // 统计所有已安排任务的声望总和
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += day[i];
    }

    cout << ans << endl;
    return 0;
}

---

E. 找数字 V2

题意简介

所有正整数拼成无限长串：12345678910111213141516...

多次询问：第 n 位是什么数字？

思路分析

二分 + 数位统计。

核心问题：从数字 1 写到数字 x，总共写了多少位？用 sum(x) 函数计算：

• 先算 x 是几位数 cnt
• 1 位数贡献 9 × 1 = 9 位，2 位数贡献 90 × 2 = 180 位……累加到 cnt-1 位
• 最后 cnt 位数贡献 cnt × (x - 10^(cnt-1) + 1) 位

有了 sum(x) 后，二分找最小的 ans 使得 sum(ans) >= n，说明第 n 位落在数字 ans 中。再减去 sum(ans-1) 得到在 ans 中的位置，转成字符串取对应字符即可。

时间复杂度：O(T × log² n)

C++ 代码

#include <iostream>
#include <cmath>
#include <string>
using namespace std;

const int N = 2e5 + 10;
long long b[20]; // b[i] = 10^(i-1)，即 i 位数的起始数字

// 计算从数字 1 写到数字 x 总共多少位
long long sum(long long x) {
    long long ti = x, cnt = 0;
    while (ti) {
        cnt++;
        ti /= 10;
    }

    long long ans = 0;
    // 累加 1位数、2位数... 到 (cnt-1)位数 的总位数
    for (long long i = 1; i < cnt; i++) {
        ans += i * (b[i + 1] - b[i]);
    }
    // 加上 cnt 位数的部分（从 10^(cnt-1) 到 x）
    ans += cnt * (x - b[cnt] + 1);
    return ans;
}

int main() {
    // 预处理 10 的幂次
    for (int i = 1; i < 20; i++) {
        b[i] = 1;
        for (int j = 1; j < i; j++) {
            b[i] *= 10;
        }
    }

    int t;
    cin >> t;

    while (t--) {
        long long n;
        cin >> n;

        // 二分找最小的 ans，使得 sum(ans) >= n
        long long l = 1, r = 1e9, ans = -1;
        while (l <= r) {
            long long mid = (l + r) / 2;
            if (sum(mid) >= n) {
                ans = mid;
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }

        // 减去 ans 之前所有数字的位数
        n -= sum(ans - 1);

        // 转成字符串取第 n 位
        string s = to_string(ans);
        cout << s[n - 1] << "\n";
    }

    return 0;
}

---

总结

A. 全体除2 — 模拟（⭐） 关键：统计每个数的因子 2 个数，取最小值

B. 强回文串 — 字符串（⭐⭐） 关键：写一个回文判断函数，调用三次

C. 不同面积的长方形 — 枚举（⭐⭐） 关键：计数 + 枚举长度对 + 标记数组去重

D. 霸王龙的进化之路 — 贪心（⭐⭐⭐） 关键：按声望降序排序 + 从截止日期往前找空闲天

E. 找数字 V2 — 二分 + 数位统计（⭐⭐⭐） 关键：二分定位数字 + sum(x) 函数计算 1~x 的总位数