位运算指令压缩（Codeforces 879C）

给定n个位运算指令（与、或、异或），需压缩为不超过5个等效指令。核心思路：通过全0和全1二进制数（0和1023）模拟运算，推断最终操作组合。

#include <iostream>
using namespace std;

int main() {
    int n, op_val;
    char op_type[3];
    cin >> n;
    int zero_state = 0, all_one_state = 1023;
    
    while(n--) {
        scanf("%s%d", op_type, &op_val);
        if(op_type[0] == '^') {
            zero_state ^= op_val;
            all_one_state ^= op_val;
        } 
        else if(op_type[0] == '&') {
            zero_state &= op_val;
            all_one_state &= op_val;
        } 
        else {
            zero_state |= op_val;
            all_one_state |= op_val;
        }
    }
    
    int AND = 0, OR = 0, XOR = 0;
    int bit_mask = 1;
    for(int i = 0; i < 10; ++i) {
        int low_bit = zero_state & 1;
        int high_bit = all_one_state & 1;
        
        if(low_bit == 0) {
            if(high_bit == 1) AND |= bit_mask;
        } 
        else {
            if(high_bit == 0) {
                XOR |= bit_mask;
                AND |= bit_mask;
            } 
            else {
                OR |= bit_mask;
                AND |= bit_mask;
            }
        }
        zero_state >>= 1;
        all_one_state >>= 1;
        bit_mask <<= 1;
    }
    printf("3\n& %d\n| %d\n^ %d\n", AND, OR, XOR);
    return 0;
}

加油路径规划（Codeforces 864C）

车辆在长a的道路往返k次，油箱容量b，距起点f处有加油站。求最少加油次数。模拟行驶过程并检测油量临界点。

#include <iostream>
using namespace std;

int main() {
    long total_dist, capacity, station_pos, trips;
    cin >> total_dist >> capacity >> station_pos >> trips;
    long fuel = capacity, refuels = 0;
    
    for(int i = 1; i <= trips; ++i) {
        if(i % 2 == 1) { // 去程
            if(fuel < station_pos) { 
                cout << -1 << endl; 
                return 0; 
            }
            fuel -= station_pos;
            
            if(i == trips) { 
                if(fuel < total_dist - station_pos) {
                    if(capacity < total_dist - station_pos) {
                        cout << -1 << endl;
                        return 0;
                    }
                    refuels++;
                }
            } 
            else {
                if(fuel < 2 * (total_dist - station_pos)) {
                    refuels++;
                    fuel = capacity;
                }
                fuel -= (total_dist - station_pos);
            }
        } 
        else { // 返程
            if(fuel < total_dist - station_pos) {
                cout << -1 << endl;
                return 0;
            }
            fuel -= (total_dist - station_pos);
            
            if(i == trips) {
                if(fuel < station_pos) refuels++;
            } 
            else {
                if(fuel < 2 * station_pos) {
                    refuels++;
                    fuel = capacity;
                }
                fuel -= station_pos;
            }
        }
    }
    cout << refuels << endl;
    return 0;
}

火灾救援背包问题（Codeforces 864E）

抢救n件物品，每件有耗时t、销毁时间d、价值p。求最大可救价值及物品序列。采用动态规划记录决策路径。

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

struct Item {
    int time, deadline, value, id;
};

bool cmp(Item x, Item y) { 
    return x.deadline < y.deadline; 
}

int main() {
    int n, max_time = 0;
    cin >> n;
    Item items[105];
    for(int i = 1; i <= n; ++i) {
        cin >> items[i].time >> items[i].deadline >> items[i].value;
        items[i].id = i;
        max_time = max(max_time, items[i].deadline);
    }
    sort(items + 1, items + n + 1, cmp);
    
    int dp[105][2005] = {0};
    bool selected[105][2005] = {0};
    
    for(int i = 1; i <= n; ++i) {
        for(int j = 0; j <= max_time; ++j) {
            dp[i][j] = dp[i-1][j];
            if(j >= items[i].time && j < items[i].deadline) {
                int new_val = dp[i-1][j - items[i].time] + items[i].value;
                if(new_val > dp[i][j]) {
                    dp[i][j] = new_val;
                    selected[i][j] = true;
                }
            }
        }
    }
    
    int max_val = 0, end_time = 0;
    for(int t = 0; t <= max_time; ++t) {
        if(dp[n][t] > max_val) {
            max_val = dp[n][t];
            end_time = t;
        }
    }
    
    vector<int> path;
    for(int i = n; i >= 1; --i) {
        if(selected[i][end_time]) {
            path.push_back(items[i].id);
            end_time -= items[i].time;
        }
    }
    reverse(path.begin(), path.end());
    
    cout << max_val << "\n" << path.size() << "\n";
    for(int id : path) cout << id << " ";
    return 0;
}