C++部分作业代码

数据结构与算法部分

题目见https://github.com/NJU-ymhui/NJUSE-2024Cpp-problems

滑动窗口：最短子数组

字符串处理: 密钥格式化

哈希：字母频率统计, 电子表

二分：方程的解, 原料采购, 卡片游戏

最短路径：外卖骑手

搜索：外卖骑手, 消灭星星

贪心：采购日志, 校园祭打卡, 不重叠时间段

技巧：不重叠时间段, 卡片游戏

C++库：电子表

暴力(可解不超时)：卡片游戏

快速幂：矩阵快速幂

最短子数组

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

int main() {
    int n, target = 0;
    vector<int> arr;
    cin >> n;
    arr.resize(n, 0);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    cin >> target;
    int length = n; // 子数组长度
    int left = 0, right = 0; // 滑动窗口的左右边界
    int sum = 0, idx = 2 * n; // 子数组和, 下标和
    bool found = false;
    for (right = 0; right < n; right++) { // 向右扩张窗口
        sum += arr[right];
        while (sum >= target) {
            found = true;
            if (length > right - left + 1) {
                idx = left + right;
                length = right - left + 1;
            } else if (length == right - left + 1) {
                idx = min(idx, left + right);
            }
            if (left == right) {
                cout << left; // 都重合了肯定满足长度最小，第一次出现也是下标和最小的
                return 0;
            }
            sum -= arr[left++]; // 收缩窗口
        }
    }
    if (found) {
        cout << idx;
        return 0;
    }
    cout << 0;
}

密钥格式化

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

signed main() {
    string raw_key = "";
    int k = 0;
    cin >> raw_key >> k;
    string key = "";
    int n = 0;
    for (auto c : raw_key) {
        if (c == '-') {
            n++;
            continue;
        }
        if (isalpha(c)) {
            c = toupper(c); // 统一转大写
        }
        key += c;
    }
    int ptr = 0; // 指向旧密钥
    string format_key = "";
    // 格式化之后不一定还是n + 1组
    int group = 1, sz = key.size();
    while (ptr < sz) {
        if (group != 1) {
            format_key += "-";
        }
        if (group == k) {
            int left = sz - ptr; // left 保证在这里ptr不会越界
            if (left == 0) {
                cout << "INVALID" << endl;
                return 0;
            }
            int k_th = left % k;
            if (k_th == 0) {
                k_th = k;
            }
            while (k_th) {
                char c = key[ptr];
                format_key += c;
                ptr++; // 上面保证了ptr不会越界因此此处不需要检验
                k_th--;
            }
        } else {
            int sze = k;
            bool digit = false, alpha = false;
            while (sze && ptr < sz) {
                char c = key[ptr];
                if (isalpha(c)) {
                    alpha = true;
                } else {
                    digit = true;
                }
                format_key += c;
                sze--;
                ptr++;
            }
            if (sze || !digit || !alpha) {
                cout << "INVALID" << endl;
                return 0;
            }
        }
        group++;
    }
    cout << format_key;
}

字母频率统计

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

int main() {
    map<char, int> table; 
    for (char a = 'a'; a <= 'z'; a++) {
        table[a] = 0;
    }
    int q;
    cin >> q;
    bool empty = true;
    for (int i = 0; i < q; i++) {
        string cmd;
        cin >> cmd;
        if (cmd == "add") {
            empty = false;
            string word;
            cin >> word;
            for (auto c : word) {
                table[c]++;
            }
        } else {
            if (empty) {
                cout << "" << endl;
                continue;
            }
            int mm = 0;
            for (auto p : table) {
                if (mm < p.second) {
                    mm = p.second;
                }
            }
            string ans = "";
            for (auto p : table) {
                if (mm == p.second) {
                    ans += p.first;
                }
            }
            sort(ans.begin(), ans.end());
            cout << ans << endl;
        }
    }
}

方程的解

#include <bits/stdc++.h>
using namespace std;
double a, b;
double f(double x) {
    return exp(x) - a * x - b;
}

int main() {
    cin >> a >> b;
    double epsilon = 1e-7;
    double left = epsilon, right = 10 - epsilon;
    while (fabs(right - left) > epsilon) {
        double mid = (right + left) / 2;
        if (f(left) * f(mid) > 0) {
            left = mid;
        } else if (f(left) * f(mid) < 0) {
            right = mid;
        } else {
            printf("%.6f", mid);
            return 0;
        }
    }
    printf("%.6f", (right + left) / 2);
}

电子表

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

int get_month(string month) {
    if (month == "January") {
        return 0;
    } else if (month == "February") {
        return 1;
    } else if (month == "March") {
        return 2;
    } else if (month == "April") {
        return 3;
    } else if (month == "May") {
        return 4;
    } else if (month == "June") {
        return 5;
    } else if (month == "July") {
        return 6;
    } else if (month == "August") {
        return 7;
    } else if (month == "September") {
        return 8;
    } else if (month == "October") {
        return 9;
    } else if (month == "November") {
        return 10;
    } else if (month == "December") {
        return 11;
    }
    return -1;
}

int main() {
    string beijing = "2024-09-16T00:00:00", e_clock = "2024-09-01T22:20:00";
    istringstream m1(beijing), m2(e_clock);
    tm tm1 = {}, tm2 = {};
    m1 >> get_time(&tm1, "%Y-%m-%dT%H:%M:%S");
    m2 >> get_time(&tm2, "%Y-%m-%dT%H:%M:%S");
    time_t beijing_std = mktime(&tm1), beijing_clock = mktime(&tm2);
    string clock_time;
    int year, day, hour, minute, sec;
    string month;
    cin >> year >> month >> day >> hour >> minute >> sec;
    tm tm_clock = {};
    tm_clock.tm_year = year - 1900;
    tm_clock.tm_mon = get_month(month);
    tm_clock.tm_mday = day;
    tm_clock.tm_hour = hour;
    tm_clock.tm_min = minute;
    tm_clock.tm_sec = sec;
    time_t clock_unix = mktime(&tm_clock);
    time_t gap = clock_unix - beijing_clock;
    if (gap > 0)
        gap = gap * 60 / 59;
    else {
        if (gap * 60 / 59 * 59 == gap * 60) {
            gap = gap * 60 / 59;
        } else {
            gap = gap * 60 / 59 - 1; // 实际上不足1秒，但是数值上向0截断了，还回去
        }
    }
    time_t current_unix = beijing_std + gap;
    // 准备从unix时间戳转化为标准时间
    tm* current = localtime(&current_unix); // 这里用localtime还是gmtime是一样的
    cout << put_time(current, "%Y-%m-%dT%H:%M:%S") << endl; // 输出格式化的标准时间
};

外卖骑手

#include <bits/stdc++.h>
#define MAX (INT_MAX - (1 << 16))
#pragma GCC optimize ("Ofast")
using namespace std;

int ans = MAX;
int n, m;
vector<vector<int>> dist;
vector<pair<int, int>> positions;
vector<bool> flags; // 标记是否可以送餐
vector<bool> finish;

void dfs(int current, int cost) {
    if (cost >= ans) {
        return; // 剪枝
    }
    bool all = true;
    for (int i = 0; i < n; i++) {
        if (!finish[i]) {
            all = false;
        }
    }
    if (all) {
        if (ans > cost) {
            ans = cost;
        }
        return;
    }
    for (int i = 0; i < n; i++) {
        if (finish[i]) {
            continue;
        }
        if (!flags[i]) {
            // 没有取餐，尝试取餐
            flags[i] = true;
            dfs(positions[i].first, cost + dist[current][positions[i].first]);
            flags[i] = false;
        } else if (flags[i]) {
            // 送餐
            finish[i] = true;
            dfs(positions[i].second, cost + dist[current][positions[i].second]);
            finish[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    // cout << MAX << endl;
    dist.resize(m, vector<int>(m, 0));
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < m; j++) {
            cin >> dist[i][j];
            if (dist[i][j] == -1) {
                dist[i][j] = MAX;
            }
        }
    }
    positions.resize(n, pair(0, 0));
    for (int i = 0; i < n; i++) {
        cin >> positions[i].first >> positions[i].second;
        positions[i].first--;
        positions[i].second--;
    }
    
    // use floyed
    // floyed算法别记错了，最外层是循环迭代的次数，不是最内层，写反了迭代顺序会出问题导致最短路不一定对
    for (int k = 0; k < m; k++) {
        // 迭代轮数
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < m; j++) {
                if (dist[i][k] != MAX && dist[k][j] != MAX) {
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }
    flags.resize(n, false);
    finish.resize(n, false);
    
    dfs(0, 0);
    cout << ans << endl;   
}

采购日志

#include <bits/stdc++.h>
#pragma GCC optimize ("Ofast")
using namespace std;

int mmax[1000005] = {0};

int logs_id[1000005], logs_prc[1000005];
string logs_cmd[1000005];


int main() {
    int n, m; // n种商品，m条日志
    cin >> n >> m;
    string line;
    for (int i = 0; i < m; i++) {
        string token;
        int id, prc;
        cin >> token >> id >> prc;
        logs_cmd[i] = token, logs_id[i] = id, logs_prc[i] = prc;
        
    }
    long long ans = 0;
    // 倒序遍历日志，期望获得最大值, 注意前面买后面卖，动态规划 + 贪心
    // 遍历时记录价格更新最大值，到购买的时候直接判断取0和大 - 成本中的较大值来获取这次购买可以获得的利润
    for (int i = m - 1; i >= 0; i--) {
        int id = logs_id[i], prc = logs_prc[i];
        // 维护更新最大价格
        if (mmax[id - 1] < prc) {
            mmax[id - 1] = prc;
        }
        if (logs_cmd[i] == "buy") {
            // 购买时直接可以计算出利润，因为记录了这个时间点之后价格的最高峰
            ans += mmax[id - 1] - prc;
        }    
    }
    cout << ans;
}

消灭星星

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

int game[2005][2005] = {0};
bool visited[2005][2005] = {false};
int n, m;

void dfs(int cur_x, int cur_y, int key) {
    if (cur_x >= n || cur_x < 0 || cur_y >= m || cur_y < 0 || visited[cur_x][cur_y]) {
        return;
    }
    visited[cur_x][cur_y] = true; // 不加这个会导致StackOverflow然后运行异常
    if (game[cur_x][cur_y] == key) {
        game[cur_x][cur_y] = 0;
    } else {
        return; // 不是这个符号消除就终止了，不能再递归搜索了
    }
    dfs(cur_x - 1, cur_y, key);
    dfs(cur_x + 1, cur_y, key);
    dfs(cur_x, cur_y - 1, key);
    dfs(cur_x, cur_y + 1, key);
}

void print() {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cout << game[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            cin >> game[i][j];
        }
    }
    int x, y;
    cin >> x >> y;
    x--, y--;
    dfs(x, y, game[x][y]);
    // 按照之前做双指针题目的思路，维护两个指针，一个指向当前填充位置，一个从下往上遍历每一列
    // 只有遇到非0数才在填充指针位置处填入该非0数，并更新填充指针；最后剩余位置填0
    for (int i = 0; i < m; i++) {
        int fill = n - 1;
        for (int j = n - 1; j >= 0; --j) {
            if (game[j][i] != 0) {
                game[fill--][i] = game[j][i];
            }
        }
        while (fill >= 0) {
            game[fill--][i] = 0;
        }
    }
    
    print();
}

校园祭打卡

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

int main() {
    vector<pair<int, int>> positions;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        pair<int, int> input;
        cin >> input.first >> input.second; // first起始位置，end终止位置
        positions.push_back(input);
    }
    // 可能按结束位置排序更好做
    sort(positions.begin(), positions.end(), [](auto a, auto b) {
       return a.first < b.first; 
    });
    // 处于前一节点的结束位置之前的一定不会超过后者的结束位置，且若后者的起始位置在前者结束之前
    // 则自己位置一定也在后者之中
    // 所以尽可能向前走
    int pos = 0, i = 0, ans = 0;
    while (i < n) {
        if (pos + 27 < positions[i].first) {
            pos += 27;
            ans++;
        } else {
            int emax = min(positions[i].second, pos + 27); // 最远可达位置
            while (i < n && positions[i].first <= emax) {
                if (emax > positions[i].second) {
                    // 为了一次性打更多卡且避免回头（贪心），停下来时必须把之前经过的摊位都打了，因此如果某个摊位更靠前（小于emax），则更新
                    emax = positions[i].second;
                }
                i++;
                pos = emax; // 记得更新位置
            }
            // 不能再走了，停下来打卡
            ans++;
        }
    }
    cout << ans << "T" << endl;
}

原料采购

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

bool can_buy(const vector<int>& fund, int price, double target, double k) {
    double have = 0;
    int left = 0; // 剩余资金 
    for (auto money : fund) {
        left += money % price;
        have += money / price;
    }
    have += left / (price - k);
    return have >= target;
}

int main() {
    int n;
    double target, k;
    cin >> n >> target >> k; // 0 < k <= 1
    vector<int> fund(n);
    for (int i = 0; i < n; i++) {
        cin >> fund[i];
    }
    int left = 2, right = 10000000, mid = right;
    while (left <= right) {
        if (can_buy(fund, mid, target, k)) {
            // 可以买得下
            left = mid + 1;
        } else {
            right = mid - 1;
        }
        mid = left + (right - left) / 2;
    } 
    if (!can_buy(fund, mid, target, k)) {
        mid--; // 防止迭代过程中多加了1
    }
    if (mid < 2) {
        cout << -1;
    } else {
        cout << mid;
    }
}

卡片游戏

暴力 $O(n^2)$

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

int main() {
    int n, k;
    cin >> n >> k;
    vector<pair<int, int>> cards(n); 
    vector<int> copy(n);
    for (int i = 0; i < n; i++) {
        cin >> cards[i].second;
        cards[i].first = i;
        copy[i] = cards[i].second;
    }
    sort(cards.begin(), cards.end(), [](const auto a, const auto b) {
        return a.second < b.second;
    }); // 对其中一组进行排序，方便按顺序从小到大获得所有能获取的合法分数
    int take = 0; // 取得的卡片数
    for (int i = 0; i < n; i++) {
        // O(n^2)
        int score = cards[i].second; // 当前准备获取的分数
        // 下面再遍历一遍卡片组，尽可能取得所有比score小的卡片，且一定拿score
        // 由于本题n最大才1000，不算大，所以O(n^2)遍历两遍的暴力做法应该不会超时
        // 不能连续取，记录上一次拿的下标，为了能拿第一个(0), 初始化为-2
        int last = -2;
        take = 1; // 必拿score
        int score_idx = cards[i].first;
        for (int j = 0; j < n; j++) {
            if (
                copy[j] <= score && j - 1 != last && j != score_idx && j - 1 != score_idx && j + 1 != score_idx // 保证score前后的都不取
            ) {
                take++;
                last = j;
            }
        }
        if (take >= k) {
            cout << score << endl;
            return 0;
        }
    }
}

二分优化 $O(n\log(n))$

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

bool judge(vector<int> cards, int score, int k) {
    // 遍历一遍，O(n)
    // 尽可能多拿，但不拿相邻的，为了可能拿第一个，初始化上一次拿的为-2
    int last = -2, cnt = 0;
    for (int i = 0; i < cards.size(); i++) {
        if (cards[i] <= score && i - 1 != last) {
            last = i;
            cnt++;
        }
        if (cnt >= k) {
            return true;
        }
    }
    return cnt >= k;
}

int main() {
    int n, k;
    cin >> n >> k;
    vector<int> cards(n);
    for (int i = 0; i < n; i++) {
        cin >> cards[i];
    }
    int left = *min_element(cards.begin(), cards.end()), right = *max_element(cards.begin(), cards.end());
    int res = right;
    while (left <= right) {
        // 二分循环O(logn)，judge O(n) 共O(nlogn)
        int mid = left + (right - left) / 2;
        if (judge(cards, mid, k)) {
            // mid分数的卡片可以在k个卡片的条件下满足，尝试更小的分数（最小得分）
            right = mid - 1;
            res = mid;
        } else {
            left = mid + 1; // 分数太小了，无法满足，大一些
        }
    }
    cout << res << endl;
}

不重叠时间段

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

int main() {
    int n;
    cin >> n;
    int ans = 0;
    vector<string> times;
    string input;
    pair<int, int> start(0, 5), end(6, 11);
    for (int i = 0; i < n; i++) {
        cin >> input;
        times.push_back(input);
    }
    function<bool(string, string)> cmp = [end](auto a, auto b) -> bool {
        return a.substr(end.first, end.second) < b.substr(end.first, end.second);
    };
    sort(times.begin(), times.end(), cmp);
    string current = times[0];
    for (int i = 1; i < n; i++) {
        // 如果开始时间早于当前时间的结束时间，则移除，否则更新其为当前时间
        if (times[i].substr(start.first, start.second) < current.substr(end.first, end.second)) {
            // remove
            ans++;
        } else {
            // 不重叠
            current = times[i];
        }
    }
    cout << ans << endl;
}

模拟部分

BF解释器

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

int main() {
    string cmd;
    getline(cin, cmd);
    uint8_t buffer[1005] = {0}; // 记得初始化！
    int ptr = 0;
    unordered_map<int, int> l2r, r2l;
    vector<int> s;
    for (int i = 0; i < cmd.size(); i++) {
        char c = cmd[i];
        if (c == '[') {
            s.push_back(i);
        } else if (c == ']') {
            int bk = s.back();
            l2r[bk] = i;
            r2l[i] = bk;
            s.pop_back();
        }
    }
    for (int i = 0; i < cmd.size(); i++) {
        char c = cmd[i];
        if (c == '>') {
            ptr++;
        } else if (c == '<' && ptr > 0) {
            ptr--;
        } else if (c == '+') {
            buffer[ptr]++;
        } else if (c == '-') {
            buffer[ptr]--;
        } else if (c == ',') {
            char c;
            c = getchar();
            if (c == EOF) {
                buffer[ptr] = 0;
            } else {
                buffer[ptr] = c;
            }
        } else if (c == '.') {
            cout << buffer[ptr];
        } else if (c == '[') {
            if (buffer[ptr] == 0) {
                i = l2r[i]; // 之后会自动i++
            }
        } else if (c == ']') {
            if (buffer[ptr] != 0) {
                i = r2l[i];
            }
        }
    }
}

沙威玛

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

unordered_map<string, int> inventory;

int main() {
    inventory["Chicken"] = 0;
    inventory["Lettuce"] = 0;
    inventory["Tomato"] = 0;
    inventory["Cheese"] = 0;
    inventory["Onion"] = 0;
    inventory["Sauce"] = 0;
    
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        string cmd, material;
        cin >> cmd;
        if (cmd == "Stock") {
            cin >> material;
            int quantity;
            cin >> quantity;
            inventory[material] += quantity;
            cout << "Stocked " << material << " with " << quantity << " units" << endl;
        } else if (cmd == "Inventory") {
            cout << "=== Inventory ===" << endl;
            cout << "Chicken: " << inventory["Chicken"] << endl;
            cout << "Lettuce: " << inventory["Lettuce"] << endl;
            cout << "Tomato: " << inventory["Tomato"] << endl;
            cout << "Cheese: " << inventory["Cheese"] << endl;
            cout << "Onion: " << inventory["Onion"] << endl;
            cout << "Sauce: " << inventory["Sauce"] << endl;
            cout << "=================" << endl;
        } else {
            // Order
            string id;
            cin >> id;
            string line;
            getline(cin, line);
            istringstream stream(line);
            int quantity;
            map<string, int> tmp; // 存放需要的材料
            bool enough = true;
            while (stream >> material) {
                stream >> quantity;
                if (quantity > inventory[material]) {
                    enough = false;
                }
                tmp[material] = quantity;
            }
            if (enough) {
                cout << "Order " << id << " completed" << endl;
                for (auto p : tmp) {
                    inventory[p.first] -= p.second;
                }
            } else {
                cout << "Order " << id << " failed: missing ";
                bool first = true;
                for (auto p : tmp) {
                    if (inventory[p.first] < p.second) {
                        if (!first) {
                            cout << ", ";
                        } else {
                            first = false;
                        }
                        cout << p.first << " " << p.second - inventory[p.first];
                    }
                }
                cout << endl;
            }
        }
    }
    
    return 0;
}

角色管理

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

class Role {
public:
    double base_strength = 0;
    double base_mana = 0;
    double base_agility = 0;
    int id;
    int level = 0;
    bool equip = false;
    
    Role(int i) {
        id = i;
        base_agility = 0;
        base_mana = 0;
        base_strength = 0;
        level = 0;
    }
    
    virtual double getPower() {
        return 0;
    }
    
    virtual void upgrade() {
    }
    
    virtual void equipWith(string tool, double p) {
    }
    
    virtual double getStrength() {
        return base_strength;
    }
    
    virtual double getMana() {
        return base_mana;
    }
    
    virtual double getAgility() {
        return base_agility;
    }
};

class Warrior: public Role {
public:
    double weapon_strength = 0;
    Warrior(int id): Role(id) {
       weapon_strength = 0; 
    }
    
    double getStrength() override {
        return base_strength + weapon_strength;
    }
    
    double getPower() override {
        return (base_strength + weapon_strength) * 1.5 + base_mana * 0.5 + base_agility * 0.8;
    }
    
    void upgrade() override {
        if (level >= 5){
            cout << "Character C" << id << " is already at max level" << endl;
            return;
        }
        level++;
        base_strength *= 1.1;
    }
    
    void equipWith(string tool, double p) override {
        if (tool != "weapon") {
            return;
        }
        equip = true;
        weapon_strength = p;
    }
};

class Mage: public Role {
public:
    double staff_power = 0;
    Mage(int id): Role(id) {
        staff_power = 0;
    }
    
    double getMana() override {
        return base_mana + 2 * staff_power;
    }
    
    double getPower() override {
        return (base_mana + 2 * staff_power) * 2 + base_strength * 0.6 + base_agility * 0.7;
    }
    
    void upgrade() override {
        if (level >= 5){
            cout << "Character C" << id << " is already at max level" << endl;
            return;
        }
        level++;
        base_mana *= 1.2;
    }
    
    void equipWith(string tool, double p) override {
        if (tool != "staff") {
            return;
        }
        equip = true;
        staff_power = p;
    }
};

class Rogue: public Role {
public:
    double stealth_bonus = 0;
    Rogue(int id): Role(id) {
        stealth_bonus = 0;
    }
    
    double getAgility() override {
        return base_agility + stealth_bonus;
    }
    
    double getPower() override {
        return (base_agility + stealth_bonus) * 1.8 + base_strength * 0.6 + base_mana * 0.4;
    }
    
    void upgrade() override {
        if (level >= 5){
            cout << "Character C" << id << " is already at max level" << endl;
            return;
        }
        level++;
        base_agility *= 1.15;
    }
    
    void equipWith(string tool, double p) override {
        if (tool != "cloak") {
            return;
        }
        equip = true;
        stealth_bonus = p;
    }
};


class Team {
public:
    int id;
    Team* manager;
    vector<Role*> rolesById; // Id升序
    vector<Role*> rolesByPower; // 战力降序
    Team(int i) {
        id = i;
    }
    
    void add(Role* role) {
        rolesById.push_back(role);
        int i = rolesById.size() - 1;
        while (i > 0 && rolesById[i]->id < rolesById[i - 1]->id) {
            Role* tmp = rolesById[i - 1];
            rolesById[i - 1] = rolesById[i];
            rolesById[i] = tmp;
            i--;
        }
        rolesByPower.push_back(role);
        i = rolesByPower.size() - 1;
        while (i > 0 && (rolesByPower[i]->getPower() > rolesByPower[i - 1]->getPower() || (rolesByPower[i]->getPower() == rolesByPower[i - 1]->getPower() && rolesByPower[i]->id < rolesByPower[i - 1]->id))) {
            Role* tmp = rolesByPower[i - 1];
            rolesByPower[i - 1] = rolesByPower[i];
            rolesByPower[i] = tmp;
            i--;
        }
    }
    
    void printById() {
        for (Role* role : rolesById) {
            cout << "C" << role->id << " strength " << role->getStrength() << " mana " << role->getMana() << " agility " << role->getAgility() << endl;
        }
    }
    
    void printByPower() {
        // sort 
        for (int i = 0; i < rolesByPower.size(); i++) {
            for (int j = 0; j < rolesByPower.size() - i - 1; j++) {
                if (rolesByPower[j]->getPower() < rolesByPower[j + 1]->getPower() || (rolesByPower[j]->getPower() == rolesByPower[j + 1]->getPower() && rolesByPower[j]->id > rolesByPower[j + 1]->id)) {
                    Role* tmp = rolesByPower[j];
                    rolesByPower[j] = rolesByPower[j + 1];
                    rolesByPower[j + 1] = tmp;
                }
            }
        }
        
        for (Role* role : rolesByPower) {
            cout << "C" << role->id << " strength " << role->getStrength() << " mana " << role->getMana() << " agility " << role->getAgility() << endl;
        }
    }
    
    void showPower() {
        // 总是按id升序
        for (Role* role : rolesById) {
            cout << "C" << role->id << " power: " << role->getPower() << endl;
        }
    }
    
    Role* findById(int id) {
        for (Role* role : rolesById) {
            if (role->id == id) {
                return role;
            }
        }
        return nullptr;
    }
    
    Role* findById(string c) {
        int id = stoi(c.substr(1));
        return findById(id);
    }
    
    void modify(string attri, double val) {
        if (attri == "base_strength") {
            for (Role* role : rolesById) {
                role->base_strength = val;
                // manager->modify(role);
            }
        } else if (attri == "base_mana") {
            for (Role* role : rolesById) {
                role->base_mana = val;
                // manager->modify(role);
            }
        } else {
            for (Role* role : rolesById) {
                role->base_agility = val;
                // manager->modify(role);
            }
        }
    }
    
    void modify(Role* role) {
        int index = 0;
        for (int i = 0; i < rolesByPower.size(); i++) {
            if (role->id == rolesByPower[i]->id) {
                index = i;
                break;
            }
        }
        while (index > 0 && (rolesByPower[index]->getPower() > rolesByPower[index - 1]->getPower() || (rolesByPower[index]->getPower() == rolesByPower[index - 1]->getPower() && rolesByPower[index]->id < rolesByPower[index - 1]->id))) {
            Role* tmp = rolesByPower[index];
            rolesByPower[index] = rolesByPower[index - 1];
            rolesByPower[index - 1] = tmp;
            index--;
        }
        while (index < rolesByPower.size() - 1 && (rolesByPower[index]->getPower() < rolesByPower[index + 1]->getPower() || (rolesByPower[index]->getPower() == rolesByPower[index + 1]->getPower() && rolesByPower[index]->id > rolesByPower[index + 1]->id))) {
            Role* tmp = rolesByPower[index];
            rolesByPower[index] = rolesByPower[index + 1];
            rolesByPower[index + 1] = tmp;
            index++;
        }
    }
};

Team* manager = new Team(-1); // 管理全局的角色
vector<Team*> teams;

void parseLine(string line) {
    istringstream stream(line);
    string word;
    string tool;
    stream >> word;
    int id;
    double val;
    string num = "";
    Role* role, *r1, *r2;
    Team* team;
    string c1, c2;
    switch(word[0]) {
        case 'A':
            // Add
            stream >> word; // 职业
            if (word == "Warrior") {
                stream >> word;
                id = stoi(word.substr(1));
                role = new Warrior(id);
                manager->add(role);
            } else if (word == "Mage") {
                stream >> word;
                id = stoi(word.substr(1));
                role = new Mage(id);
                manager->add(role);
            } else {
                stream >> word;
                id = stoi(word.substr(1));
                role = new Rogue(id);
                manager->add(role);
            }
            break;
        case 'S':
            // Set
            stream >> word;
            id = stoi(word.substr(1));
            role = manager->findById(id);
            stream >> word;
            stream >> num;
            val = stof(num);
            if (word == "base_strength") {
                role->base_strength = val;
            } else if (word == "base_agility") {
                role->base_agility = val;
            } else {
                role->base_mana = val;
            }
            // manager->modify(role);
            break;
        case 'E':
            // equip
            stream >> word; // C_id
            id = stoi(word.substr(1));
            role = manager->findById(id);
            if (role->equip) {
                cout << "Character " << word <<  " already has equipment" << endl;
                break;
            }
            stream >> word;
            tool = word;
            stream >> word;
            val = stof(word);
            role->equipWith(tool, val);
            // manager->modify(role);
            break;
        case 'L':
            // List
            stream >> word;
            if (word == "Normal") {
                manager->printById();
            } else {
                manager->printByPower();
            }
            break;
        case 'U':
            stream >> word;
            id = stoi(word.substr(1));
            role = manager->findById(id);
            role->upgrade();
            // manager->modify(role);
            break;
        case 'P':
            manager->showPower();
            break;
        case 'B':
            // battle
            stream >> c1;
            stream >> c2;
            r1 = manager->findById(c1), r2 = manager->findById(c2);
            if (r1->getPower() >= r2->getPower() * 1.1) {
                cout << "C" << r1->id << " wins" << endl;
            } else if (r2->getPower() >= r1->getPower() * 1.1) {
                cout << "C" << r2->id << " wins" << endl;
            } else {
                cout << "Draw" << endl;
            }
            break;
        case 'M':
            stream >> word;
            id = stoi(word.substr(1));
            for (Team* t : teams) {
                if (t->id == id) {
                    team = t;
                    break;
                }
            }
            stream >> word;
            stream >> num;
            val = stof(num);
            team->modify(word, val);
            break;
        case 'T':
            stream >> word;
            id = stoi(word.substr(1));
            Team* newT = new Team(id);
            newT->manager = manager;
            while (stream >> word) {
                role = manager->findById(word);
                newT->add(role);
                teams.push_back(newT);
            }
            break;
    }
}

int main() {
    int n;
    cin >> n;
    string line;
    getline(cin, line);
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        parseLine(line);
    }
}

矩阵快速幂

# define ll long long 
# define VAL 1000000007ll
# include <iostream>
using namespace std;

class Matrix {
public:
    ll data[10][10] = {0};
    int size;
    Matrix(int n) {
        size = n;
    }
    
    Matrix operator*(const Matrix& other) const {
        Matrix m(size);
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                ll res = 0;
                for (int k = 0; k < size; k++){
                    res += ((data[i][k] % VAL) * (other.data[k][j] % VAL));
                    res %= VAL;
                }
                m.data[i][j] = res;
            }
        }
        return m;
    }
    
    void eye() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size; j++) {
                if (i == j) {
                    data[i][j] = 1;
                } else {
                    data[i][j] = 0;
                }
            }
        }
    }
};

int main() {
    int n, p;
    cin >> n >> p;
    Matrix m(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> m.data[i][j];
        }
    }
    Matrix ans(n);
    ans.eye();
    while (p) {
        if (p & 1) {
            ans = ans * m;
        }
        m = m * m;
        p >>= 1;
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << ans.data[i][j] << " ";
        }
        cout << endl;
    }
}

树上寻宝

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

struct TreeNode {
    int val;
    vector<TreeNode*> children;
    TreeNode() {}
    TreeNode(int x) : val(x) {}
};

class Strategy {
public:
    Strategy() {}
    
    virtual int excute(TreeNode* root) {
        return 0;
    }
    
    virtual int visit(TreeNode* root) {
        return 0;
    }
};

class Wang: public Strategy {
private:
    int p = 0;
public:
    Wang(int cond) {
        p = cond;
    }
    
    int excute(TreeNode* root) override {
        if (root->val <= p) {
            return 0;
        }
        return visit(root);
    }
    
    int visit(TreeNode* root) override {
        // dfs
        int res = root->val;
        for (TreeNode* child : root->children) {
            if (child->val > p) {
                res += visit(child);
            }
        }
        return res;
    }
};

class Hu: public Strategy {
private:
    int q = 0, k = 0;
public:
    Hu(int _q, int _k) {
        q = _q;
        k = _k;
    } 
    
    int excute(TreeNode* root) override {
        return visit(root);
    }
    
    int visit(TreeNode* root) override {
        int res = root->val;
        for (TreeNode* child : root->children) {
            if (root->val + child->val > k && child->val > q) {
                res += visit(child);
            }
        }
        return res;
    }
};

class Xie: public Strategy {
public:
    Xie(){}
    
    int excute(TreeNode* root) override {
        return visit(root);
    }
    
    int visit(TreeNode* root) override {
        int res = root->val;
        for (TreeNode* child : root->children) {
            if (child->val % 2 == 0) {
                res += visit(child);
            }
        }
        return res;
    }
};

int main() {
    int n, p, q, k;
    cin >> n >> p >> q >> k;
    vector<TreeNode*> trees;
    trees.push_back(nullptr); // 占位
    for (int i = 0; i < n; i++) {
        trees.push_back(new TreeNode());
    }
    for (int i = 0; i < n - 1; i++) {
        int father, son;
        cin >> father >> son;
        trees[father]->children.push_back(trees[son]);
    }
    for (int i = 1; i <= n; i++) {
        int val;
        cin >> val;
        trees[i]->val = val;
    }
    // 1号根节点
    Strategy* strategy = new Wang(p);
    cout << strategy->excute(trees[1]);
    strategy = new Hu(q, k);
    cout << " " << strategy->excute(trees[1]);
    strategy = new Xie();
    cout << " " << strategy->excute(trees[1]);
}

沙威玛商店评价系统

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

class History {
public:
    double food_rating;
    double svc_rating;
    double env_rating;
    string date;
    int version;
    History* next = nullptr;
    History* prev = nullptr;
    History(double f, double s, double e, string da, int v):
    food_rating(f), svc_rating(s), env_rating(e), date(da), version(v) {}
};

class Custom {
public:
    Custom(int d): id(d), head(new History(-1, -1, -1, "", 0)), version(1), latest(nullptr) {} 
    int id;
    int version;
    History* head, *latest;
    
    History* createNewHistory() {
        if (latest == nullptr) {
            latest = new History(0, 0, 0, "", version);
            version++;
            head->next = latest;
            latest->prev = head;
            return latest;
        } else {
            latest->next = new History(latest->food_rating, latest->svc_rating, latest->env_rating, latest->date, version++);
            latest->next->prev = latest;
            return latest->next;
        }
        // 此函数调用完毕一定一定记得更新latest为返回值
    } 
};

class Manager {
public:
    vector<Custom*> customs;
    
    Custom* add(int id) {
        Custom* cus = new Custom(id);
        customs.push_back(cus);
        return cus;
    }
    
    void insert(int id, double food, double svc, double env, string date) {
        Custom* cus = add(id);
        History* init = cus->createNewHistory();
        init->food_rating = food, init->svc_rating = svc, init->env_rating = env, init->date = date;
        cus->latest = init;
    }
    
    bool modify(int id, double food, double svc, double env, string date) {
        auto it = find_if(customs.begin(), customs.end(), [&id](const Custom* tmp) {
           return tmp->id == id;
        });
        if (it == customs.end()) {
            return false;
        }
        History* his = (*it)->createNewHistory();
        if (food != -1) {
            his->food_rating = food;
        }
        if (svc != -1) {
            his->svc_rating = svc;
        }
        if (env != -1) {
            his->env_rating = env;
        }
        his->date = date;
        (*it)->latest = his; // 记得对应前面所说的更新
        return true;
    }
    
    bool del(int id) {
        auto it = find_if(customs.begin(), customs.end(), [&id](const Custom* tmp) {
           return tmp->id == id;
        });
        if (it == customs.end()) {
            return false;
        }
        customs.erase(remove(customs.begin(), customs.end(), *it));
        return true;
    }
    
    void showHistory(int id, string dim) {
        cout << "History:" << endl;
        auto it = find_if(customs.begin(), customs.end(), [&id](const Custom* tmp) {
          return tmp->id == id;
        }); // 数据保证能找到
        // dim ?
        History* ptr = (*it)->latest;
        while (ptr != (*it)->head) {
            cout << "Version " << ptr->version << ": ";
            if (dim == "") {
                cout << "Food Rating " << ptr->food_rating << " Service Rating " << ptr->svc_rating << " Environment Rating " << ptr->env_rating << " Timestamp " << ptr->date << endl;
            } else {
                if (dim == "food") {
                    cout << "Food Rating " << ptr->food_rating;
                } else if (dim == "service") {
                    cout << "Service Rating " << ptr->svc_rating;
                } else if (dim == "environment") {
                    cout << "Environment Rating " << ptr->env_rating;
                }
                cout << " Timestamp " << ptr->date << endl;
            }
            ptr = ptr->prev;
        }
    }
    
    void display(string dim) {
        sort(customs.begin(), customs.end(), [](const auto& a, const auto& b) {
            return a->latest->date > b->latest->date; 
        });
        if (dim != "") {
            for (const auto cus : customs) {
                History* ptr = cus->latest;
                cout << "Customer ID " << cus->id;
                if (dim == "food") {
                    cout << " Food Rating " << ptr->food_rating;
                } else if (dim == "service") {
                    cout << " Service Rating " << ptr->svc_rating;
                } else if (dim == "environment") {
                    cout << " Environment Rating " << ptr->env_rating;
                }
                cout << " Timestamp " << ptr->date << endl;
            }
        } else {
            for (const auto cus : customs) {
                History* ptr = cus->latest;
                cout << "Customer ID " << cus->id << " Food Rating " << ptr->food_rating << " Service Rating " << ptr->svc_rating << " Environment Rating " << ptr->env_rating << " Timestamp " << ptr->date << endl;
            }
        }
    }
    
    void query(double food_lower, double food_upper, double svc_lower, double svc_upper, double env_lower, double env_upper) {
        // 顾客id降序
        sort(customs.begin(), customs.end(), [](const auto& a, const auto& b) {
           return a->id > b->id; 
        });
        for (const auto& cus : customs) {
            History* cu = cus->latest;
            if (cu->food_rating >= food_lower && cu->food_rating <= food_upper && cu->svc_rating >= svc_lower && cu->svc_rating <= svc_upper && cu->env_rating >= env_lower && cu->env_rating <= env_upper) {
                // legal, output information which is latest
                History* ptr = cus->latest;
                cout << "Customer ID " << cus->id << " Food Rating " << ptr->food_rating << " Service Rating " << ptr->svc_rating << " Environment Rating " << ptr->env_rating << " Timestamp " << ptr->date << endl;
            }
        }
    }
};

void parse(Manager* manager, string line) {
    istringstream stream(line);
    string token, date;
    int id;
    stream >> token;
    if (token == "insert") {
        stream >> id;
        double food, svc, env;
        stream >> food >> svc >> env >> date >> token;
        date = date + " " + token; // 拼接出完整时间
        manager->insert(id, food, svc, env, date);
        cout << "Review inserted successfully" << endl;
    } else if (token == "modify") {
        stream >> id;
        double food = -1, svc = -1, env = -1;
        while (stream >> token && !(token[0] >= '0' && token[0] <= '9')) {
            if (token == "food") {
                stream >> food;
            } else if (token == "service") {
                stream >> svc;
            } else if (token == "environment") {
                stream >> env;
            }
        }
        stream >> date; // date放的时分，token现在是年月日
        date = token + " " + date;
        if (manager->modify(id, food, svc, env, date)) {
            cout << "Modification successful" << endl;
        } else {
            cout << "Customer ID not found, modification failed" << endl;
        }
    } else if (token == "delete") {
        stream >> id;
        if (manager->del(id)) {
            cout << "Deletion successful" << endl;
        } else {
            cout << "Customer ID not found, deletion failed" << endl;
        }
    } else if (token == "history") {
        string dim;
        stream >> id;
        if (!(stream >> dim)) {
            dim = "";
        }
        manager->showHistory(id, dim);
    } else if (token == "range_query") {
        // TODO
        double food_lower = 1.0, food_upper = 5.0, svc_lower = 1.0, svc_upper = 5.0, env_lower = 1.0, env_upper = 5.0;
        double tmp;
        double *addr[] = {&food_lower, &food_upper, &svc_lower, &svc_upper, &env_lower, &env_upper};
        int i = 0;
        while (stream >> tmp) {
            *(addr[i++]) = tmp;
        }
        manager->query(food_lower, food_upper, svc_lower, svc_upper, env_lower, env_upper);
    } else if (token == "display") {
        string dim;
        if (!(stream >> dim)) {
            dim = "";
        }
        manager->display(dim);
    } else {
        assert(0);
    }
}

int main() {
    int n;
    cin >> n;
    Manager* manager = new Manager();
    string line;
    getline(cin, line);
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        parse(manager, line);
    }
}

铺木地板

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

int length(string fl) {
    return fl.size() / 2;
}

class FloorManager {
public:
    vector<string> floors;
    string res = "";
    int mmax = INT_MIN;
    
    void add(string hex_floor) {
        hex_floor = hex_floor.substr(2);
        floors.push_back(hex_floor);
    }
    
    void del(string hex_floor) {
        hex_floor = hex_floor.substr(2);
        // 从木板vector中移除特定的木板
        floors.erase(remove(floors.begin(), floors.end(), hex_floor));
    }
    
    void execute() {
        res = ""; // 清空上一次的结果
        // 先找到木板当中的最大值，以此为标准进行排列
        mmax = INT_MIN;
        for (const auto a : floors) {
            if (length(a) > mmax) {
                mmax = length(a);
            }
        }
        // res的每一个元素代表铺木地板的每一行
        int current_len = 0;
        string current = "";
        
        for (const auto f : floors) {
            // 开始铺木地板
            if (length(f) + current_len <= mmax) {
                // 还可以在一行里
                current += f;
                current_len += length(f);
            } else {
                // 不能在同一行里了
                while (current_len < mmax) {
                    current += "CC"; // 使用普通木地板填充
                    current_len++;
                }
                res += current;
                current = "" + f, current_len = length(f);
            }
        }
        // 对齐最后一次的结果
        while (current_len < mmax) {
            current += "CC";
            current_len++;
        }
        res += current;
    }
    
    void print() {
        execute(); // 铺木地板
        for (int i = 0; i < res.size(); i += 2 * mmax) {
            string tmp = res.substr(i, 2 * mmax); // mmax是概念上的长度，但实际长度是两倍
            // 注意C++的substr第二个参数不是结束位置，是子串长度
            cout << "0x" << tmp << endl;
        }
    }
    
    void print(int start, int len) {
        execute();
        cout << "0x";
        if (start >= length(res)) {
            while (len--) {
                cout << "CC";
            }
            cout << endl;
            return;
        }
        
        string ans = res.substr(2 * start, 2 * len); // len也是概念上的长度，实际长度是两倍
        while (length(ans) < len) {
            ans += "CC";
        }
        cout << ans << endl;
    }
};

FloorManager* manager;
void parse_line(string line) {
    istringstream stream(line);
    string token;
    stream >> token;
    if (token == "add") {
        stream >> token;
        manager->add(token);
    } else if (token == "del") {
        stream >> token;
        manager->del(token);
    } else if (token == "print") {
        int start;
        if (stream >> start) {
            int len;
            stream >> len;
            manager->print(start, len);
        } else {
            manager->print();
        }
    }
}

int main() {
    manager = new FloorManager();
    int n;
    cin >> n;
    string line;
    getline(cin, line);
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        // 分析输入的命令行
        parse_line(line);
    }
}

sort命令

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

void Print(vector<string> ss) {
    for (string s : ss) {
        cout << s << endl;
    }
}

int main() {
    int n, c;
    string line;
    vector<string> inputs;
    cin >> n;
    getline(cin, line);
    for (int i = 0; i < n; i++) {
        getline(cin, line);
        inputs.push_back(line);
    }
    // 读入命令
    cin >> c;
    vector<string> cmds;
    getline(cin, line);
    for (int i = 0; i < c; i++) {
        getline(cin, line);
        if (line[0] == '-') {
            sort(inputs.begin(), inputs.end(), [](string a, string b) {
               return a < b; 
            });
            Print(inputs);
        } else if (line[0] == 'n') {
            sort(inputs.begin(), inputs.end(), [](string a, string b) {
                return stoi(a) < stoi(b);
            });
            Print(inputs);
        } else if (line[0] == 'r') {
            sort(inputs.begin(), inputs.end(), [](string a, string b) {
               return a > b; 
            });
            Print(inputs);
        } else if (line[0] == 'i') {
            sort(inputs.begin(), inputs.end(), [](string a, string b) {
               for (int k = 0; k < a.size() && k < b.size(); k++) {
                   if (tolower(a[k]) < tolower(b[k])) {
                       return true;
                   } else if (tolower(a[k] > tolower(b[k]))) {
                       return false;
                   }
               }
               if (a.size() > b.size()) {
                   return false;
               } else if (a.size() < b.size()) {
                   return true;
               }
               return a < b;
            });
            Print(inputs);
        } else if (line[0] == 'd') {
            sort(inputs.begin(), inputs.end(), [](string a, string b) {
               int l = 0, r = 0;
               while (l < a.size() && r < b.size()) {
                   while (l < a.size() && ispunct(a[l])) {
                       l++;
                   }
                   while (r < b.size() && ispunct(b[r])) {
                       r++;
                   }
                   if (a[l] < b[r]) {
                       return true;
                   } else if (a[l] > b[r]) {
                       return false;
                   }
                   l++, r++;
               }
               if (l >= a.size() && r >= b.size()) {
                   return true;
               }
               if (l < a.size()) {
                   return false;
               } 
               if (r < a.size()) {
                   return true;
               }
              return true;
            });
            Print(inputs);
        }
    }
}

植物大战僵尸

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

class User {
public:
    int hp = 0;
    int atk = 0;
    int speed = 0;
    int row = 0, col = 0;
    
    User(int h): hp(h) {}
    
    virtual int alive() {
        return hp > 0;
    }
    virtual bool is_plant() {
        return false;
    }
    virtual bool is_zombie() {
        return false;
    }
    
};

class Zombie: public User {
public:
  Zombie(int h, int a, int s, int x, int y): User(h) {
      atk = a;
      speed = s;
      row = x;
      col = y;
  }
  bool is_zombie() override {
      return true && alive();
  }
};

class Plant: public User {
public:
    Plant(int h): User(h) {}
    virtual bool is_pea() {
        return false;
    }
    virtual bool is_nut() {
        return false;
    }
    virtual bool is_potato() {
        return false;
    }
    bool is_plant() override {
        return true && alive();
    }
};

class Pea: public Plant {
public:
    Pea(int h, int a): Plant(h) {
        atk = a;
    }
    bool is_pea() override {
        return true && alive();
    }
};

class Nut: public Plant {
public:
    Nut(int h): Plant(h) {}
    bool is_nut() override {
        return true && alive();
    }
};

class Potato: public Plant {
public:
    bool sleep = true;
    Potato(int a): Plant(10) {
        atk = a;
    }
    bool is_potato() override {
        return true && alive();
    }
};

class Game {
public:
    vector<vector<vector<User*>>> plate;
    vector<Plant*> plants;
    vector<Zombie*> zombies;
    int plant_cnt = 0, zombie_cnt = 0;
    
    Game() {
        plate.resize(5, vector<vector<User*>>(10));
    }
    
    void add_plant(Plant* p, int row, int col) {
        plants.push_back(p);
        plate[row][col].push_back(p);
        plant_cnt++;
    }
    
    void add_zombie(Zombie* z, int row, int col) {
        zombies.push_back(z);
        plate[row][col].push_back(z);
        zombie_cnt++;
    }
    
    int finish() {
        if (zombie_cnt == 0) {
            return 1; // 植物胜利
        } else {
            for (auto z : zombies) {
                if (z->col < 0) {
                    return 0; // 僵尸胜利
                }
            }
        }
        return -1; // 继续
    }
    
    void plant_attack() {
        for (int i = 0; i < 5; i++) {
            for (int j = 0; j < 9; j++) {
                vector<User*> ps = plate[i][j];
                for (auto a : ps) {
                    if (!a->alive() || a->is_zombie()) {
                        continue;
                    }
                    Plant* plant = static_cast<Plant*>(a);
                    if (plant->is_pea()) {
                        // 豌豆射手
                        int z_idx = -1; // 前方僵尸的位置
                        for (int k = j; k < 10 && z_idx == -1; k++) {
                            vector<User*> us = plate[i][k];
                            for (auto a : us) {
                                if (a->alive() && a->is_zombie()) {
                                    z_idx = k;
                                    break;
                                }
                            }
                        }
                        if (z_idx != -1) {
                            // 攻击
                            vector<User*> us = plate[i][z_idx];
                            for (auto a : us) {
                                if (a->alive() && a->is_zombie()) {
                                    a->hp -= plant->atk;
                                    if (!a->alive()) {
                                        zombie_cnt--;
                                    }
                                }
                            }
                        }
                    } else if (plant->is_potato()) {
                        Potato* potato = static_cast<Potato*>(plant);
                        if (!potato->sleep) {
                            for (int r = max(0, i - 1); r <= min(4, i + 1); r++) {
                                for (int c = max(0, j - 1); c <= min(9, j + 1); c++) {
                                    vector<User*> us = plate[r][c];
                                    for (auto a : us) {
                                        if (a->alive() && a->is_zombie()) {
                                            a->hp -= plant->atk;
                                            if (!a->alive()) {
                                                zombie_cnt--;
                                            }
                                        }
                                    }
                                }
                            }
                            plant_cnt--; //地雷必死
                        }
                    }
                }
            }
        }
    }
    
    void zombie_move() {
        for (auto z : zombies) {
            int old_row = z->row, old_col = z->col;
            if (z->alive() && z->col >= 0) {
                int speed = z->speed;
                bool block = false;
                while (speed && !block) {
                    vector<User*> tmp = plate[z->row][z->col];
                    // 判断是否有植物阻挡
                    for (auto p : tmp) {
                        if (p->alive() && p->is_plant()) {
                            if (static_cast<Plant*>(p)->is_potato()) {
                                static_cast<Potato*>(p)->sleep = false;
                            } else {
                                block = true;
                                break;
                            }
                        }
                    }
                    if (block) {
                        break;
                    }
                    speed--;
                    z->col--;
                    if (z->col < 0) {
                        break;
                    }
                }
                // 最后停下的位置可能触发土豆地雷
                if (z->col >= 0) {
                    vector<User*> tmp = plate[z->row][z->col];
                    // 判断是否有植物阻挡
                    for (auto p : tmp) {
                        if (p->alive() && p->is_plant()) {
                            if (static_cast<Plant*>(p)->is_potato()) {
                                static_cast<Potato*>(p)->sleep = false;
                            }
                        }
                    }
                    plate[old_row][old_col].erase(remove(plate[old_row][old_col].begin(), plate[old_row][old_col].end(), z));
                    plate[z->row][z->col].push_back(z);
                }
            }
        }
    }
    
    void zombie_attack() {
        for (auto z : zombies) {
            if (z->alive() && z->col >= 0) {
                vector<User*> tmp = plate[z->row][z->col];
                for (auto p : tmp) {
                    if (p->alive() && p->is_plant()) {
                        if (!static_cast<Plant*>(p)->is_potato()) {
                            p->hp -= z->atk; // 攻击
                            if (!p->alive()) {
                                plant_cnt--;
                            }
                        }
                    }
                }
            }
        }
    }
    int turn = 1;
    void print() {
        cout << turn++ << " " << plant_cnt << " " << zombie_cnt << endl;
    }
    
    void play() {
        do {
            plant_attack();
            zombie_move();
            zombie_attack();
            print();
        } while (finish() == -1);
        if (finish() == 1) {
            cout << "plants win" << endl;
        } else {
            cout << "zombies win" << endl;
        }
    }
};

int main() {
    Game* game = new Game();
    int pcnt, zcnt;
    cin >> pcnt >> zcnt;
    while(pcnt--) {
        string cmd;
        cin >> cmd;
        int hp, atk, x, y;
        if (cmd == "pea") {
            cin >> hp >> atk >> x >> y;
            Pea* pea = new Pea(hp, atk);
            game->add_plant(pea, x, y);
        } else if (cmd == "nut") {
            cin >> hp >> x >> y;
            Nut* nut = new Nut(hp);
            game->add_plant(nut, x, y);
        } else {
            cin >> atk >> x >> y;
            Potato* potato = new Potato(atk);
            game->add_plant(potato, x, y);
        }
    }
    while (zcnt--) {
        int hp, atk, speed, x;
        int y = 9;
        cin >> hp >> atk >> speed >> x;
        Zombie* zombie = new Zombie(hp, atk, speed, x, y);
        game->add_zombie(zombie, x, y);
    }
    game->play();
}