CF2028A - Alice's Adventures in "Chess"

本题是一道基础的模拟题。核心思路是模拟角色的移动轨迹，由于地图和步数限制，最多模拟 100 个完整周期即可判断是否能到达目标点。通过优化变量命名和循环结构，使代码逻辑更加清晰。

#include <iostream>
#include <string>

using namespace std;

void solve_chess() {
    int moves_count, target_x, target_y;
    cin >> moves_count >> target_x >> target_y;
    string directions;
    cin >> directions;
    
    int current_x = 0, current_y = 0;
    
    for (int cycle = 0; cycle < 100; ++cycle) {
        for (char dir : directions) {
            if (current_x == target_x && current_y == target_y) {
                cout << "YES\n";
                return;
            }
            if (dir == 'W') current_x--;
            else if (dir == 'E') current_x++;
            else if (dir == 'N') current_y++;
            else if (dir == 'S') current_y--;
        }
    }
    
    if (current_x == target_x && current_y == target_y) {
        cout << "YES\n";
    } else {
        cout << "NO\n";
    }
}

CF2028B - Alice's Adventures in Permuting

本题考察数学推导与边界条件处理。通过分析步长和起始值对最终排列的影响，可以直接通过数学公式计算出剩余元素的数量。重写后的代码增强了条件分支的可读性。

#include <iostream>

using namespace std;
using ll = long long;

void solve_permuting() {
    ll total_elements, step, start_value;
    cin >> total_elements >> step >> start_value;
    
    if (step == 0) {
        if (start_value <= total_elements - 3) {
            cout << -1 << "\n";
        } else {
            cout << (start_value < total_elements ? total_elements - 1 : total_elements) << "\n";
        }
        return;
    }
    
    ll remaining = total_elements;
    if (start_value < total_elements) {
        remaining -= (total_elements - 1 - start_value) / step + 1;
    }
    cout << remaining << "\n";
}

CF2028C - Alice's Adventures in Cutting Cake

利用前缀和结合双指针来确定左右边界。通过预处理每个分割点的最小左侧边界和最大右侧边界，最后枚举中间部分计算最大和。代码中使用了更具描述性的数组名称以提升可维护性。

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

using namespace std;
using ll = long long;

void solve_cake() {
    int n, m;
    ll min_value;
    cin >> n >> m >> min_value;
    
    vector<ll> prefix_sum(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        ll val;
        cin >> val;
        prefix_sum[i] = prefix_sum[i - 1] + val;
    }
    
    vector<int> left_bound(m + 1, 0);
    vector<int> right_bound(m + 1, n + 1);
    
    for (int i = 1; i <= m; ++i) {
        int pos = left_bound[i - 1];
        while (pos <= n && prefix_sum[pos] - prefix_sum[left_bound[i - 1]] < min_value) {
            pos++;
        }
        if (pos > n) {
            cout << -1 << "\n";
            return;
        }
        left_bound[i] = pos;
    }
    
    right_bound[0] = n + 1;
    for (int i = 1; i <= m; ++i) {
        int pos = right_bound[i - 1];
        while (pos >= 1 && prefix_sum[right_bound[i - 1] - 1] - prefix_sum[pos - 1] < min_value) {
            pos--;
        }
        right_bound[i] = pos;
    }
    
    ll max_middle_sum = 0;
    for (int i = 0; i <= m; ++i) {
        if (right_bound[i] - 1 >= left_bound[m - i]) {
            max_middle_sum = max(max_middle_sum, prefix_sum[right_bound[i] - 1] - prefix_sum[left_bound[m - i]]);
        }
    }
    
    cout << max_middle_sum << "\n";
}

CF2028D - Alice's Adventures in Cards

贪心策略结合数据结构。使用 std::set 维护前缀最大值，从而快速找到可以转移的状态。通过记录前驱节点来还原操作路径。重构后的代码使用了结构体来封装卡牌信息，提升了代码的模块化程度。

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

using namespace std;

struct CardInfo {
    int value, index;
    bool operator<(const CardInfo& other) const {
        if (value != other.value) return value < other.value;
        return index < other.index;
    }
};

void solve_cards() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1), c(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    for (int i = 1; i <= n; ++i) cin >> c[i];
    
    set<CardInfo> set_a, set_b, set_c;
    vector<pair<int, int>> prev_node(n + 1, {0, 0});
    
    auto add_to_sets = [&](int idx) {
        set_a.insert({a[idx], idx});
        set_b.insert({b[idx], idx});
        set_c.insert({c[idx], idx});
    };
    
    add_to_sets(1);
    for (int i = 2; i <= n; ++i) {
        auto max_a = *set_a.rbegin();
        if (max_a.value > a[i]) {
            prev_node[i] = {max_a.index, 1};
            add_to_sets(i);
            continue;
        }
        auto max_b = *set_b.rbegin();
        if (max_b.value > b[i]) {
            prev_node[i] = {max_b.index, 2};
            add_to_sets(i);
            continue;
        }
        auto max_c = *set_c.rbegin();
        if (max_c.value > c[i]) {
            prev_node[i] = {max_c.index, 3};
            add_to_sets(i);
            continue;
        }
    }
    
    if (prev_node[n].first == 0) {
        cout << "NO\n";
        return;
    }
    
    vector<pair<char, int>> operations;
    int curr = n;
    while (curr != 1) {
        char type = (prev_node[curr].second == 1) ? 'q' : (prev_node[curr].second == 2 ? 'k' : 'j');
        operations.push_back({type, curr});
        curr = prev_node[curr].first;
    }
    
    reverse(operations.begin(), operations.end());
    cout << "YES\n";
    cout << operations.size() << "\n";
    for (auto& op : operations) {
        cout << op.first << " " << op.second << "\n";
    }
}

CF2028E - Alice's Adventures in the Rabbit Hole

树形 DP 与概率结合。通过两次 DFS（向下和向上）计算每个节点的期望概率。重写时摒弃了手写链表，改用 std::vector 构建邻接表，并优化了模逆元的计算逻辑，使状态转移方程的实现更加直观。

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 998244353;

long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long inv(long long n) {
    return power(n, MOD - 2);
}

const long long INV2 = inv(2);

int n;
vector<vector<int>> adj;
vector<int> depth, heavy_child;
vector<long long> dp_down_f, dp_down_g, final_ans;

void dfs_down(int u, int parent) {
    heavy_child[u] = -1;
    for (int v : adj[u]) {
        if (v == parent) continue;
        dfs_down(v, u);
        if (heavy_child[u] == -1 || depth[v] < depth[heavy_child[u]]) {
            heavy_child[u] = v;
        }
    }
    
    if (heavy_child[u] == -1) {
        depth[u] = 0;
        dp_down_f[u] = dp_down_g[u] = 0;
    } else if (u != 1) {
        int v = heavy_child[u];
        depth[u] = depth[v] + 1;
        long long denom = (1 - dp_down_f[v] * INV2 % MOD + MOD) % MOD;
        long long inv_denom = inv(denom);
        
        dp_down_f[u] = INV2 * inv_denom % MOD;
        dp_down_g[u] = dp_down_g[v] * INV2 % MOD * inv_denom % MOD;
    }
}

void dfs_up(int u, int parent) {
    for (int v : adj[u]) {
        if (v == parent) continue;
        final_ans[v] = (dp_down_f[v] * final_ans[u] % MOD + dp_down_g[v]) % MOD;
        dfs_up(v, u);
    }
}

void solve_rabbit() {
    cin >> n;
    adj.assign(n + 1, vector<int>());
    depth.assign(n + 1, 0);
    heavy_child.assign(n + 1, -1);
    dp_down_f.assign(n + 1, 0);
    dp_down_g.assign(n + 1, 0);
    final_ans.assign(n + 1, 0);
    
    for (int i = 0; i < n - 1; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    dfs_down(1, 0);
    final_ans[1] = 1;
    dfs_up(1, 0);
    
    for (int i = 1; i <= n; ++i) {
        cout << final_ans[i] << (i == n ? "" : " ");
    }
    cout << "\n";
}

CF2028F - Alice's Adventures in Addition

动态规划结合 Bitset 优化。通过将连续的 1 合并为块，并利用 Bitset 加速状态转移，大幅降低了时间复杂度。代码重构中优化了块的处理逻辑和 Bitset 的位移操作，确保了在大数据量下的高效运行。

#include <iostream>
#include <vector>
#include <bitset>

using namespace std;

const int MAXM = 10005;
const int BLOCK_SIZE = 105;

void solve_addition() {
    int n, target;
    cin >> n >> target;
    
    vector<int> raw_vals(n);
    for (int i = 0; i < n; ++i) cin >> raw_vals[i];
    
    vector<pair<int, int>> blocks;
    for (int val : raw_vals) {
        if (val == 1 && !blocks.empty() && blocks.back().first == 1) {
            blocks.back().second++;
        } else {
            blocks.push_back({val, 1});
        }
    }
    
    if (!blocks.empty() && blocks.back().first == 1 && blocks.back().second > 1) {
        blocks.back().second--;
        blocks.push_back({1, 1});
    }
    
    int num_blocks = blocks.size();
    vector<int> block_id(num_blocks);
    for (int i = 0; i < num_blocks; ++i) block_id[i] = i % BLOCK_SIZE;
    
    bitset<MAXM> reachable_total, current_reachable;
    vector<bitset<MAXM>> block_dp(BLOCK_SIZE);
    
    block_dp[block_id[0]][0] = 1;
    reachable_total[0] = 1;
    
    for (int i = 1; i < num_blocks; ++i) {
        if (blocks[i].first == 0) current_reachable = reachable_total;
        
        block_dp[block_id[i]].reset();
        block_dp[block_id[i]] |= current_reachable;
        
        long long prod = 1;
        for (int j = i; j >= 1; --j) {
            prod *= blocks[j].first;
            if (prod >= MAXM) break;
            block_dp[block_id[i]] |= (block_dp[block_id[j - 1]] << prod);
            if (prod == 0) break;
        }
        
        if (blocks[i].first == 1) {
            bitset<MAXM> temp = block_dp[block_id[i]];
            for (int k = 1; k < blocks[i].second; ++k) {
                block_dp[block_id[i]] |= (temp << k);
            }
        }
        
        reachable_total |= block_dp[block_id[i]];
    }
    
    cout << (block_dp[block_id[num_blocks - 1]][target] ? "YES" : "NO") << "\n";
}