A. Candies

题目要求寻找一个正整数 $x$，使得对于某个 $k > 1$，满足等比数列之和 $x + 2x + 4x + \dots + 2^{k-1}x = n$。根据等比数列求和公式，该式可简化为 $x(2^k - 1) = n$。因此，我们只需要枚举 $k$（从 2 开始），检查 $n$ 是否能被 $2^k - 1$ 整除即可。

#include <iostream>

using namespace std;

void solve() {
    long long n;
    cin >> n;
    for (int k = 2; k < 31; ++k) {
        long long denominator = (1LL << k) - 1;
        if (n % denominator == 0) {
            cout << n / denominator << endl;
            break;
        }
    }
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B. Balanced Array

构造一个长度为 $n$ 的数组，要求前 $n/2$ 个元素为偶数，后 $n/2$ 个元素为奇数，且两部分和相等。 由于偶数之和必为偶数，若 $n/2$ 为奇数，则后半部分（$n/2$ 个奇数）的和必为奇数，两者不可能相等。因此只有当 $n/2$ 为偶数时才存在解。构造时，前 $n/2$ 个数取 $2, 4, 6, \dots$，后 $n/2$ 个数的前 $n/2-1$ 个取 $1, 3, 5, \dots$，最后一个数通过差值补齐。

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int n;
    cin >> n;
    int m = n / 2;
    if (m % 2 != 0) {
        cout << "NO" << endl;
        return;
    }
    cout << "YES" << endl;
    vector<long long> res;
    long long even_sum = 0;
    for (int i = 1; i <= m; ++i) {
        res.push_back(i * 2);
        even_sum += i * 2;
    }
    long long odd_sum = 0;
    for (int i = 1; i < m; ++i) {
        res.push_back(i * 2 - 1);
        odd_sum += (i * 2 - 1);
    }
    res.push_back(even_sum - odd_sum);
    for (int i = 0; i < n; ++i) {
        cout << res[i] << (i == n - 1 ? "" : " ");
    }
    cout << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C. Alternating Subsequence

给定一个序列，求其最长的正负交替子序列的最大和。 贪心策略：由于要保证长度最长，我们必须在每一段连续的正数或连续的负数中各取一个。为了使和最大，每一段中应选取那个值最大的数。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool has_same_sign(long long a, long long b) {
    return (a > 0 && b > 0) || (a < 0 && b < 0);
}

void solve() {
    int n;
    cin >> n;
    vector<long long> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    long long total_sum = 0;
    for (int i = 0; i < n; ++i) {
        long long current_val = a[i];
        int j = i;
        while (j < n && has_same_sign(a[i], a[j])) {
            current_val = max(current_val, a[j]);
            j++;
        }
        total_sum += current_val;
        i = j - 1;
    }
    cout << total_sum << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D. Constant Palindrome Sum

给定长度为 $n$ 的数组，元素范围在 $[1, k]$。需要通过修改最少的元素，使得所有对 $(a_i, a_{n-i+1})$ 的和都等于某个常数 $x$。 对于每一对 $(a, b)$，设 $S = a + b$： 1. 和为 $S$：修改 0 次。 2. 和在 $[\min(a, b) + 1, \max(a, b) + k]$ 范围内：最少修改 1 次。 3. 其他范围（$[2, 2k]$ 且不在上述区间）：修改 2 次。 使用差分数组记录每个可能的 $x$ 值所需的修改次数，最后求前缀和找到最小值。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    
    vector<int> diff(2 * k + 2, 0);
    for (int i = 0; i < n / 2; ++i) {
        int u = a[i], v = a[n - i - 1];
        int sum_val = u + v;
        
        // 默认所有位置都需要修改 2 次
        diff[2] += 2;
        diff[2 * k + 1] -= 2;
        
        // 修改 1 次的区间：[min(u,v)+1, max(u,v)+k]
        int L = min(u, v) + 1;
        int R = max(u, v) + k;
        diff[L] -= 1;
        diff[R + 1] += 1;
        
        // 修改 0 次的点：u+v
        diff[sum_val] -= 1;
        diff[sum_val + 1] += 1;
    }
    
    int min_ops = n;
    int current_ops = 0;
    for (int i = 2; i <= 2 * k; ++i) {
        current_ops += diff[i];
        min_ops = min(min_ops, current_ops);
    }
    cout << min_ops << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

E. Weights Distributing

给定带权无向图，求从 $a \to b \to c$ 的最短路径总权值。边权可以任意分配。 路径可以看作 $(b \to x) + (x \to a) + (x \to c)$。其中 $b \to x$ 段被走过了两次。 为了使总权值最小，应将最小的一组边权分配给 $b \to x$ 段，次小的一组边权分配给其余段。 方案： 1. 通过 BFS 计算 $a, b, c$ 到所有点 $i$ 的最短距离 $da[i], db[i], dc[i]$。 2. 对给定的边权进行排序并计算前缀和。 3. 枚举中间点 $x$，总权值为 $prefix[db[i]] + prefix[da[i] + db[i] + dc[i]]$。

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

const long long INF = 1e18;

void get_dist(int start, int n, vector<int>& d, const vector<vector<int>>& adj) {
    fill(d.begin(), d.end(), -1);
    d[start] = 0;
    queue<int> q;
    q.push(start);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (d[v] == -1) {
                d[v] = d[u] + 1;
                q.push(v);
            }
        }
    }
}

void solve() {
    int n, m, a, b, c;
    cin >> n >> m >> a >> b >> c;
    vector<long long> p(m);
    for (int i = 0; i < m; ++i) cin >> p[i];
    sort(p.begin(), p.end());
    
    vector<long long> pref(m + 1, 0);
    for (int i = 0; i < m; ++i) pref[i + 1] = pref[i] + p[i];
    
    vector<vector<int>> adj(n + 1);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    vector<int> da(n + 1), db(n + 1), dc(n + 1);
    get_dist(a, n, da, adj);
    get_dist(b, n, db, adj);
    get_dist(c, n, dc, adj);
    
    long long ans = INF;
    for (int i = 1; i <= n; ++i) {
        if (da[i] + db[i] + dc[i] > m) continue;
        ans = min(ans, pref[db[i]] + pref[da[i] + db[i] + dc[i]]);
    }
    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}