:D

一开始只想到用 dp[i][j] 记录第 i 个月拥有 j 钱时能达到的最大 h，但很明显存不下 :D 但其实输入限制已经提示得很明显了，下标应该是 $h_i$ ，存达到这个值的最小金额

但拥有的钱每个月都在变化，所以没想到怎么存钱 :D 果然还是得多搞钱 :D

OP 注册 7min 拿下 lv3 😸

我擦，乜 bug，點解我毋知

我就感觉到快

@aibot 请将这句话翻译为普通话

m0rsun 说 "我擦，乜 bug，點解我毋知" 的普通话翻译是 "我去，什么 bug，为什么我不知道"。

想法有了但写不出来是最难受的，得狠狠学习 C++ 语法，

蹲更新 😺

OP 给我说他在突击 C++，起码要把

• 16 The string Class and the Standard Template Library
• 17 Input, Output, and Files

的前半部分标准输入输出看了

学习。

P1147 ，two pointers，注意到是在纯正整数数列中寻找，故右指针右移必然会增加和，左指针右移必然会减少和

P1102

用一个 map 收集了所有出现的数和出现次数，因为要找所有 a - b = c，所以只需要遍历大于 c 的数，然后看能不能找到 b 就行。所以复杂度应该是线性的

但是题目说 100% 的数据都小于 $2^{30}$ ，不知道为什么用 int 存不下，有一个点没过，换成 long long 才过。

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

typedef long long ll;

void solve() {
    ll n, c;
    cin >> n >> c;

    ll ans = 0;
    map<ll, ll> count;
    for (ll i = 0; i < n; i++) {
        ll ni;
        cin >> ni;
        if (count.find(ni) != count.end()) {
            count[ni]++;
        } else {
            count[ni] = 1;
        }
    }

    for (auto const &pair : count) {
        auto found = count.find(pair.first - c);
        // cout << "pair  " << pair.first << " " << pair.second << endl;
        // cout << "found " << found->first << " " << found->second << endl;
        if (pair.first > c && found != count.end()) {
            ans += pair.second * found->second;
        }
    }

    cout << ans << endl;
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

不是线性的，map 的插入查找复杂度都是 logn。
另：这个题也可以排序后双指针，总时间复杂度是一样的，留给 OP 思考

P1022

惊天巨坑 🤯 0 / -1 会输出 -0

是因为浮点数与 two's complement 整数不同，同时可以表示 +0 和 -0

本题是模拟题，每次读一个字符，并根据字符类型来处理。

#include <iostream>
#include <cstdio>

using namespace std;

void solve() {
    char x = '\0';
    double a = .0;
    double c = .0;
    // convert to 'a * x = c'

    int left = 1; // -1 for right of the equal sign
    bool coefficient = false; // is coefficient of unknown
    char read_c; // current character read
    int scalar = 0;
    int sign = 1; // -1 for negative

    while (cin.get(read_c) && read_c != '\n') {
        if (read_c >= 'a' && read_c <= 'z') {
            if (x == '\0') x = read_c;
            coefficient = true;

        } else if (read_c >= '0' && read_c <= '9') {
            scalar = 10 * scalar + (read_c - '0');
            // cout << "scalar " << scalar << endl;
        } else /* + - = */ {
            if (coefficient) {
                if (scalar == 0) scalar = 1;
                a += left * sign * scalar;
                // cout << "a " << a << endl;
            } else {
                c += (-left) * sign * scalar;
                // cout << "c " << c << endl;
            }

            // reset
            scalar = 0;
            coefficient = false;
            sign = 1;
            
            if (read_c == '-') sign = -1;
            else if (read_c == '=') left = -1;

            // cout << "sign " << sign << endl;
        }
    }

    // cout << left << scalar << sign << endl;
    // handle last block of input
    if (coefficient) {
        if (scalar == 0) scalar = 1;
        a += left * sign * scalar;
        // cout << "a " << a << endl;
    } else {
        c += (-left) * sign * scalar;
        // cout << "c " << c << endl; 
    }

    if (c / a == 0) printf("%c=0.000\n", x);
    else printf("%c=%.3f\n", x, c / a);
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

严查康米

[P1023 [NOIP2000 普及组] 税收与补贴问题](https://www.luogu.com.cn/problem/P1023)

可以看出在某一价位下的利润是

$w = sales \times (price - cost + subsidy)$

其中的变量只有 $subsidy$ ，所以

$w = sales \times subsidy + c$.

每个价位都有这么一条直线，需要找的就是最小的 $subsidy$ 取值，使得政府指导价下的 w 最大。

观察到比政府指导价 $s_g$ 小的价格下，销量一定更大，所以函数增长率更大。比 $s_g$ 大的价格下，销量一定更小，所以函数增长率更小。

这样，目标就比较明确了：

• 找到斜率更小的函数中交点横坐标的最大值 m
• 找到斜率更大的函数中交点横坐标的最小值 M
• 如果 $M \lt m$ 则无解，否则 m 就是解

这是什么导致的 🤯

注释掉 72 行后得到的 max_m 输出是 3.3333，加上 72 行之后得到的 max_m 输出是 2.22507e-308

而且这个输出语句是在第 70 行，在造成影响的语句的上面 🤯

过了。对于中间没有提供的数据也要一个一个插值，这点题目没说清楚

#include <iostream>
#include <cfloat>
#include <climits>
#include <map>
#include <cmath>

using namespace std;

typedef long long ll;

const string no_solution = "NO SOLUTION";

void solve() {
    int expected;
    cin >> expected;
    int sales_at_expected = 0;

    double min_M = DBL_MAX;
    double max_m = -DBL_MAX;

    map<int, double> input;

    // w = sales * subsidy + c
    // c = sales * (price - cost)
    int cost;
    double sales_at_cost;
    cin >> cost >> sales_at_cost;
    input[cost] = sales_at_cost;
    
    int last = cost; // for inserting value
    int p = 0, s = 0;
    int max_p = INT_MIN;
    double max_p_s = -DBL_MAX;
    while (cin >> p >> s && p != -1) {
        max_p = max(p, max_p);
        input[p] = s;

        // insert value
        if (p - last > 1) {
            double last_s = input[last];
            double slope = double(s - last_s) / double(p - last);
            for (int j = last + 1; j < p; j++) {
                input[j] = (last_s += slope);
                // cout << input[j] << " ";
            }
            // cout << endl;
        }
        last = p;
        // cout << p << " " << s << endl;
    }

    // calculate unknown
    max_p_s = input[max_p];
    // cout << max_p << endl;
    // cout << max_p_s << endl;
    int decrement;
    cin >> decrement;
    while ((max_p_s -= decrement) >= 0) {
        // cout << max_p + 1 << " " << max_p_s << endl;
        input[++max_p] = max_p_s;
    }

    sales_at_expected = input[expected];

    // calculate intersections
    ll c_expected = sales_at_expected * (expected - cost);
    for (const auto &pair : input) {
        auto &pi = pair.first;
        auto &si = pair.second;
        // cout << pi << " " << si << endl;

        ll ci = (pi - cost) * si;
        if (abs(si - sales_at_expected) < 1e-5) continue;
        double subsidy = double(c_expected - ci) / double(si - sales_at_expected);
        
        // cout << "subsidy " << subsidy << endl;

        if (pi < expected && subsidy < min_M) min_M = subsidy;
        else if (pi > expected && subsidy > max_m) max_m = subsidy;
    }

    // find result
    // cout << max_m << " " << min_M << endl;
    ll ans_min = ceil(max_m);
    ll ans_max = floor(min_M);
    // cout << ans_min << " " << ans_max << endl; 
    if (ans_min > ans_max) cout << no_solution << endl;
    else {
        // find minimum absolute value
        if (ans_min <= 0 && ans_max >= 0) cout << 0 << endl;
        else if (ans_min >= 0) cout << ans_min << endl;
        else cout << ans_max << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

[P1037 [NOIP2002 普及组] 产生数](https://www.luogu.com.cn/problem/P1037)

终于过了，改了几乎大半天的一道题。主要的坑点在：经过一次变幻后的数可能可以进行二次变换，所以要对 0-9 每个数都进行一次深搜，找到每种数可能的变换情况，然后就是统计原数字每个数有几种，乘起来就行

在确定了 ans 将会达到 $2^{100}$ 级别后，本来想用 __int128_t 来存储，但是发现这种 C 标准里没有，只存在于 gcc 实现中的类型并没有得到很好的支持。于是实现了一个 BigInt 类型来存储。

#include <iostream>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;

void DFS(const int num, const int (&table)[10][10], int &variant_count, bool (&visited)[10]);

inline void flatten(vector<int> &one) {
    const int len = one.size();
    for (int i = 0; i < len; i++) {
        if (one[i] >= 10) {
            one[i + 1] += one[i] / 10;
            one[i] %= 10;
        }
    }
}

inline void multiply_by(vector<int> &one, int other) {
    for (int &i : one) {
        i *= other;
    }
    flatten(one);
};


void solve() {
    int count[10] = { 0 };
    char input;
    while (cin.get(input) && input != ' ') {
        count[input - '0']++;
    }

    int k;
    cin >> k;

    int table[10][10];
    memset(table, -1, 10 * 10 * sizeof (int));

    for (int i = 0; i < k; i++) {
        int left, right;
        cin >> left >> right;

        int j = -1;
        while (table[left][++j] != -1);
        table[left][j] = right;
    }

    // search for variants for each number
    int variants[10];
    for (int i = 0; i < 10; i++) {
        variants[i] = 1;
    }

    for (int i = 0; i < 10; i++) {
        bool visited[10] = { false };
        visited[i] = true;
        DFS(i, table, variants[i], visited);
    }

    // long long ans = 1;
    // for (int i = 0; i < 10; i++) {
    //     int &left = count[i];
    //     while (left > 0) {
    //         ans *= variants[i];
    //         left--;
    //     }
    // }

    // big integer multiplication
    vector<int> ans(130);
    ans[0] = 1;
    // cout << ans.size() << endl;
    for (int i = 0; i < 10; i++) {
        int &left = count[i];
        while (left > 0) {
            multiply_by(ans, variants[i]);
            left--;
        }
    }

    // adjust decimal big integer
    // flatten(ans);

    // print ans
    int i = 130;
    while (ans[--i] == 0);
    for (; i >= 0; i--) {
        cout << ans[i];
    }
    cout << endl;
}

void DFS(const int num, const int (&table)[10][10], int &variant_count, bool (&visited)[10]) {
    auto &list = table[num];
    int j = -1;
    while (list[++j] != -1) {
        auto &to_visit = list[j];
        if (!visited[to_visit]) {
            visited[to_visit] = true;
            variant_count++;
            DFS(to_visit, table, variant_count, visited);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

[P1045 [NOIP2003 普及组] 麦森数](P1045 [NOIP 2003 普及组] 麦森数

最简单的一集，一发过了。给一个二进制数，让求十进制的位数（开几个对数）和十进制后 500 位（高精度整数算几次压位乘法）

#include <iostream>
#include <cmath>
#include <vector>

using namespace std;

const double log2_10 = log2(10);

void flatten(vector<int> &one) {
    for (int i = 0; i < 500; i++) {
        if (one[i] >= 10) {
            one[i + 1] += one[i] / 10;
            one[i] %= 10;
        }
    }
}

void multiply_by(vector<int> &one, const int num) {
    for (int &i : one) {
        i *= num;
    }
    flatten(one);
}

void solve() {
    int p;
    cin >> p;

    int digits = int(double(p) / log2_10) + 1;
    cout << digits << endl;

    vector<int> output(505);
    output[0] = 1;

    // convert binary to decimal
    while (p >= 9) {
        // cout << p << endl;
        multiply_by(output, 512);
        p -= 9;
    }

    if (p > 0) {
        multiply_by(output, 1 << p);
    }

    output[0] -= 1;
    int j = -1;
    while (output[++j] < 0) {
        output[j] += 10;
        output[j + 1] -= 1;
    }

    // output answer
    for (int i = 10; i > 0; i--) {
        for (int j = i * 50 - 1; j >= i * 50 - 50; j--) {
            cout << output[j];
        }
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

[P1056 [NOIP2008 普及组] 排座椅](https://www.luogu.com.cn/problem/P1056)

没注意到答案要求从小到大输出和读取数据的循环里把行和列搞反卡了一小下。比较简单。

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

using namespace std;

void solve() {
    int m, n, k, l, d;
    cin >> m >> n >> k >> l >> d;

    vector<int> rows(m);
    vector<int> cols(n);

    for (int i = 0; i < d; i++) {
        int xi, yi, pi, qi;
        cin >> xi >> yi >> pi >> qi;

        if (xi == pi) {
            cols[min(yi, qi)]++;
        } else if (yi == qi) {
            rows[min(xi, pi)]++;
        }
    }

    priority_queue< pair<int, int> > pq_rows;
    priority_queue< pair<int, int> > pq_cols;

    for (int i = 1; i < m; i++) {
        pq_rows.push({rows[i], i});
    }

    for (int i = 1; i < n; i++) {
        pq_cols.push({cols[i], i});
    }

    priority_queue< int, vector<int>, greater<int> > pq_row_out;
    priority_queue< int, vector<int>, greater<int> > pq_col_out;

    pair<int, int> top;
    for (int i = 0; i < k; i++) {
        top = pq_rows.top();
        pq_row_out.push(top.second);
        pq_rows.pop();
    }

    for (int i = 0; i < l; i++) {
        top = pq_cols.top();
        pq_col_out.push(top.second);
        pq_cols.pop();
    }

    int first;
    first = pq_row_out.top();
    cout << first;
    pq_row_out.pop();
    while (!pq_row_out.empty()) {
        first = pq_row_out.top();
        cout << " " << first;
        pq_row_out.pop();
    }
    cout << endl;

    first = pq_col_out.top();
    cout << first;
    pq_col_out.pop();
    while (!pq_col_out.empty()) {
        first = pq_col_out.top();
        cout << " " << first;
        pq_col_out.pop();
    }
    cout << endl;
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

[P1057 [NOIP2008 普及组] 传球游戏](https://www.luogu.com.cn/problem/P1057)

比较容易能想到广搜，然后发现重叠子问题，选用动态规划。

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

void solve() {
    int n, m;
    cin >> n >> m;

    int dp[31][31]; // i times, j number of student, value number of methods
    memset(dp, 0, 31 * 31 * sizeof (int));
    dp[0][1] = 1;
    
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (dp[i - 1][j] > 0) {
                dp[i][(j + n - 2) % n + 1] += dp[i - 1][j];
                dp[i][j % n + 1] += dp[i - 1][j];
            }
        }
    }

    cout << dp[m][1] << endl;
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

OP 通宵了吗 😿
高精度没性能要求可以直接上 Python，省去打板子时间

OP 应该没通宵，python 也行吧，但是对 python 不太熟

写到 5am 不算通宵吗

[P1058 [NOIP2008 普及组] 立体图](https://www.luogu.com.cn/problem/P1058)

画 3D ascii art，比较有意思，只要注意到遮挡关系之后按顺序画上去就行了

#include <iostream>
#include <vector>

using namespace std;

inline void draw_box_at(const int i, const int j, vector< vector<char> > &dest);

void solve() {
    int m, n;
    cin >> m >> n;

    // canvas size
    int k = 0;
    int l = 4 * n + 1 + 2 * m;

    vector< vector<int> > input(m, vector<int>(n));
    for (int i = 0; i < m; i++) {
        int highest_int_row = 0;
        for (int j = 0; j < n; j++) {
            cin >> input[i][j];
            highest_int_row = max(highest_int_row, input[i][j]);
        }
        k = max(k, 3 * highest_int_row + 1 + 2 * (m - i));
    }

    // cout << k << " " << l << endl;

    // draw from top to bottom, from right to left, and from front to back
    vector< vector<char> > output(k, vector<char>(l, '.'));
    for (int i = m - 1; i >= 0; i--) {
        // cout << "i " << i << endl;
        for (int j = n - 1; j >= 0; j--) {
            // cout << "j " << j << endl;
            for (int z = input[i][j]; z > 0; z--) {
                // cout << "z " << z << endl;
                draw_box_at((m - i - 1) * 2 + (z - 1) * 3, j * 4 + (m - i - 1) * 2, output);
            }
        }
    }

    for (int i = k - 1; i >= 0; i--) {
        for (char c : output[i]) cout << c;
        cout << endl;
    }
}

void draw_box_at(const int x, const int y, vector< vector<char> > &dest) {
    // row 0
    if (dest[x][y] == '.') dest[x][y] = '+';
    for (int i = 1; i <= 3; i++) {
        if (dest[x][y + i] == '.') dest[x][y + i] = '-';
    }
    if (dest[x][y + 4] == '.') dest[x][y + 4] = '+';

    // row 1
    if (dest[x + 1][y] == '.') dest[x + 1][y] = '|';
    for (int i = 1; i <= 3; i++) {
        if (dest[x + 1][y + i] == '.') dest[x + 1][y + i] = ' ';
    }
    if (dest[x + 1][y + 4] == '.') dest[x + 1][y + 4] = '|';
    if (dest[x + 1][y + 5] == '.') dest[x + 1][y + 5] = '/';

    // row 2
    if (dest[x + 2][y] == '.') dest[x + 2][y] = '|';
    for (int i = 1; i <= 3; i++) {
        if (dest[x + 2][y + i] == '.') dest[x + 2][y + i] = ' ';
    }
    if (dest[x + 2][y + 4] == '.') dest[x + 2][y + 4] = '|';
    if (dest[x + 2][y + 5] == '.') dest[x + 2][y + 5] = ' ';
    if (dest[x + 2][y + 6] == '.') dest[x + 2][y + 6] = '+';

    // row 3
    if (dest[x + 3][y] == '.') dest[x + 3][y] = '+';
    for (int i = 1; i <= 3; i++) {
        if (dest[x + 3][y + i] == '.') dest[x + 3][y + i] = '-';
    }
    if (dest[x + 3][y + 4] == '.') dest[x + 3][y + 4] = '+';
    if (dest[x + 3][y + 5] == '.') dest[x + 3][y + 5] = ' ';
    if (dest[x + 3][y + 6] == '.') dest[x + 3][y + 6] = '|';

    // row 4
    if (dest[x + 4][y + 1] == '.') dest[x + 4][y + 1] = '/';
    for (int i = 2; i <= 4; i++) {
        if (dest[x + 4][y + i] == '.') dest[x + 4][y + i] = ' ';
    }
    if (dest[x + 4][y + 5] == '.') dest[x + 4][y + 5] = '/';
    if (dest[x + 4][y + 6] == '.') dest[x + 4][y + 6] = '|';

    // row 5
    if (dest[x + 5][y + 2] == '.') dest[x + 5][y + 2] = '+';
    for (int i = 3; i <= 5; i++) {
        if (dest[x + 5][y + i] == '.') dest[x + 5][y + i] = '-';
    }
    if (dest[x + 5][y + 6] == '.') dest[x + 5][y + 6] = '+';
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

......+---+---+...+---+
..+---+  /   /|../   /|
./   /|-+---+ |.+---+ |
+---+ |/   /| +-|   | +
|   | +---+ |/+---+ |/|
|   |/   /| +/   /|-+ |
+---+---+ |/+---+ |/| +
|   |   | +-|   | + |/.
|   |   |/  |   |/| +..
+---+---+---+---+ |/...
|   |   |   |   | +....
|   |   |   |   |/.....
+---+---+---+---+......

比较早期的题目，现在可能不会出这种了，越来越偏向数学

[P1061 [NOIP2006 普及组] Jam 的计数法](https://www.luogu.com.cn/problem/P1061)

排列组合题，让找下一个排列。只要找到下一个序号就行了。

测试文件的换行是 CRLF，代码里只用了一个 cin.get() 来丢掉换行导致第一次提交全爆。

#include <iostream>
#include <vector>

using namespace std;

void solve() {
    int s, t, w;
    cin >> s >> t >> w;

    // discard '\r' if on windows!
    // cin.get();

    // discard '\n'
    cin.get();

    vector<int> input(w);
    for (int i = 0; i < w; i++) {
        input[i] = cin.get() - 'a' + 1;
    }

    // index    0, 1, 2, 3, 4
    // bdfij -> 2, 4, 6, 9, 10
    // max      6, 7, 8, 9, 10

    for (int i = 0; i < 5; i++) {
        // find last number less than max
        int j = w - 1;
        while (input[j] == t - w + 1 + j) j--;
        if (j < 0) return;

        input[j]++; // increment
        // rearrange all numbers after it
        for (j++; j < w; j++) {
            input[j] = input[j - 1] + 1;
        }

        // output result
        for (int num : input) {
            cout << char(num - 1 + 'a');
        }
        cout << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

虽然没过，但好在没有 WA，说明 coding 能力提升了

[P1095 [NOIP2007 普及组] 守望者的逃离](https://www.luogu.com.cn/problem/P1095)

#include <iostream>
#include <queue>
#include <map>

using namespace std;

typedef long long ll;

const string yes = "Yes";
const string no = "No";

void solve() {
    ll m, s, t;
    cin >> m >> s >> t;

    auto one = new map<ll, ll>;
    auto other = new map<ll, ll>;
    one->insert({ m, 0 });

    for (int time = 1; time <= t; time++) {
        for (auto &pair : *one) {
            // run on foot
            if (other->find(pair.first) == other->end() || (*other)[pair.first] < pair.second + 17) {
                (*other)[pair.first] = pair.second + 17;

                if ((*other)[pair.first] >= s) {
                    cout << yes << endl;
                    cout << time << endl;
                    delete one;
                    delete other;
                    return;
                }
            }

            // use magic
            if (pair.first >= 10 && (other->find(pair.first - 10) == other->end() || (*other)[pair.first - 10] < pair.second + 60)) {
                (*other)[pair.first - 10] = pair.second + 60;

                if ((*other)[pair.first - 10] >= s) {
                    cout << yes << endl;
                    cout << time << endl;
                    delete one;
                    delete other;
                    return;
                }
            }

            // recover magic
            if (other->find(pair.first + 4) == other->end() || (*other)[pair.first + 4] < pair.second) {
                (*other)[pair.first + 4] = pair.second;
            }
        }

        delete one;
        one = other;
        other = new map<ll, ll>;
    }

    ll max_dist = 0;
    for (auto &pair : *one) {
        max_dist = max(max_dist, pair.second);
    }

    cout << no << endl;
    cout << max_dist << endl;
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

由于拿 map 存的 dp 信息，复杂度应该是 $\sim TM log{M}$ ，其中 $1 \le T \le 3 \times 10^5, 0 \le M \le 10^3$ 。如果能把复杂度降低到 $\sim TM$ 就好了。

但是需要考虑用什么存储来实现高效查询。

虽然 TLE 了，但 256 mb 空间就用了 2 mb，得想办法 trade-off 一下

大受震撼

如果能证明出最多恢复一次的话，那确实就不用规划什么了，先用完所有的魔法，剩下的全用跑的

怎么突然搞起算法来了（虽然我最近也想搞）

初始魔力值、需要几次休息能获得一次魔法、相对速度、使用后变化为什么情况：

由于步行速度是 $17 m/s$ ，只要等效速度大于 17 这次魔法的积攒和使用就是有效的。

对于初始魔力为 X0, X1 的情况，如果选择恢复 n 次魔力（不是休息 n 次），等效速度为：

对于初始魔力为 X2, X3 的情况，如果选择恢复 n 次魔力（不是休息 n 次），等效速度为：

X4-X9 都会在一次蓄力 + 释放后转化到 X0-X3。

草，是不是证明失败了

没有找到这个人发的题解或证明，所以认为他在放屁

不懂呢，OP 是交大附中初三的萌新喵，开始做算法是觉得比较有意思

本题的贪心性质：能闪现的时候闪现一定比跑更快，如果闪了之后的总里程比跑的要快了，下一秒就在闪的基础上接着闪或跑，否则就在各自的基础上继续。

OP 一开始没用贪心的原因是觉得，闪了之后会消耗魔力，这样就影响了后续的选择。但是！其实每次消耗 10 点魔力的话，参考上面的表格，是不会影响下一次需要回复的魔力量的，所以是可以贪心。但是如果每次消耗的不是 10 的倍数的话就确实会产生影响了

#include <iostream>

using namespace std;

typedef long long ll;

const string yes = "Yes";
const string no = "No";

void solve() {
    ll m, s, t;
    cin >> m >> s >> t;

    ll dist_run = 0, dist_magic = 0;
    for (int now = 1; now <= t; now++) {
        if (m >= 10) {
            dist_magic += 60;
            m -= 10;
        } else {
            m += 4;
        }

        dist_run = max(dist_magic, dist_run + 17);

        if (dist_run >= s || dist_magic >= s) {
            cout << yes << endl;
            cout << now << endl;
            return;
        }
    }

    cout << no << endl;
    cout << max(dist_run, dist_magic) << endl;
}

int main() {
    ios::sync_with_stdio(false);

    solve();

    return 0;
}

算法导论上对 Huffman 编码的贪心性质的证明有点难懂，看了好久

证明一般不要求掌握 ()

初中可能没学反证法，可以先理解这个

大概看明白了。

greedy choice property 证的是如果每次选择最小的两个节点 merge 的话，最终的 cost 最小

optimal substructure property 证的是如果 merge 前不是 optimal 的，那么 merge 后的也一定不是 optimal

但是证明过程和用的语言有点绕，让我证肯定证不出来

[P1199 [NOIP2010 普及组] 三国游戏](https://www.luogu.com.cn/problem/P1199)

其实看证明是因为这道题的贪心一直没证出来，瞪了一天了。

现在是觉得只要每次 Alice 都选择当前表格中最大值的 cell 所在行就行，如果次大的 cell 在本行，那 Alice 就能赢。

但还没看出来是怎么判输