P1199 [NOIP2010 普及组] 三国游戏

过了！

我发现这个表格中每一行的最大值都绝对不会被任何一方拿到，所以 Alice 只要能拿到每一行的第二大的值中的最大的那个，就一定会赢，不存在会输的情况。

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;

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

    vector<ll> largest(n);
    vector<ll> second_largest(n);

    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            ll input;
            cin >> input;

            if (input > largest[i]) {
                second_largest[i] = largest[i];
                largest[i] = input;
            } else if (input > second_largest[i]) {
                second_largest[i] = input;
            }

            if (input > largest[j]) {
                second_largest[j] = largest[j];
                largest[j] = input;
            } else if (input > second_largest[j]) {
                second_largest[j] = input;
            }
        }
    }

    ll second_max = 0;
    for (ll sl : second_largest) {
        second_max = max(second_max, sl);
    }

    cout << "1" << endl;
    cout << second_max << endl;
}

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

    solve();

    return 0;
}

特别开心的一集

DP 是拓扑排序这个没想出来，明天再看看

毕竟 recurrence 和 induction 是天作之合嘛

P1199 [NOIP2010 普及组] 三国游戏

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

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

但还没看出来是怎么判输

大概看明白了。

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

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

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

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

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

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;
}

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

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

初始魔力值	需要几次休息可多获得一次魔法	相当于什么速度 (m/s)	使用后变成什么情况
X0	3	15	(X+1)2
X1	3	15	(X+1)3
X2	2	20	(X+1)0
X3	2	20	(X+1)1
X4	2	20	(X+1)2
X5	2	20	(X+1)3
X6	1	30	(X+1)0
X7	1	30	(X+1)1
X8	1	30	(X+1)2
X9	1	30	(X+1)3

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

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

$
v = \begin{cases}
{60n \over {n \over 2} \times (4 + 3)} = 17.14 m/s, n = 2k\
{60n \over {{n-1} \over 2} \times (4 + 3) + 4} \lt 17.14 m/s, n = 2k + 1
\end{cases}
$

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

$
v = \begin{cases}
{60n \over {n \over 2} \times (3 + 4)} = 17.14 m/s, n = 2k\
{60n \over {{n-1} \over 2} \times (3 + 4) + 3} \lt 17.14 m/s, n = 2k + 1
\end{cases}
$

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

草，是不是证明失败了

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

大受震撼

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

P1095 [NOIP2007 普及组] 守望者的逃离

#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 一下

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

P1061 [NOIP2006 普及组] Jam 的计数法

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

测试文件的换行是 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;
}

P1058 [NOIP2008 普及组] 立体图

画 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;
}

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

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

P1057 [NOIP2008 普及组] 传球游戏

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

#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;
}

P1056 [NOIP2008 普及组] 排座椅

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

#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;
}

P1045 [NOIP2003 普及组] 麦森数

最简单的一集，一发过了。给一个二进制数，让求十进制的位数（开几个对数）和十进制后 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;
}

P1037 [NOIP2002 普及组] 产生数

终于过了，改了几乎大半天的一道题。主要的坑点在：经过一次变幻后的数可能可以进行二次变换，所以要对 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;
}

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

#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;
}

所以编译器优化之后，对于未定义变量会随便取一个值，然后同一次运行只内每次取的也能不一样么

应该是这个问题，我再看看

所有变量都已初始化，但没用

if (si - sales_at_expected < 1e-5) continue;

修改了防除 0 措施，现在检测一个 epsilon 范围，但与本问题无关

我看什么

-O2 优化过后的汇编是真看不懂吧，，

OP 觉得这真得可能是一个优化问题。因为：

• gdb 运行一定会得到正确结果
• 不指定优化等级 g++ -Wall -g -o p1023 p1023.cpp 的时候（默认使用 -O0）也一定会得到正确结果
• 但是当指定了 -O2 或 -O3 后就会时不时出错
• 又试了一下指定 -O1 发现每次都一定会得到错误结果

不对，但朋友在 Ubuntu 上用 g++ filename.cpp -o filename.o 编译的，一样会跑飞

这不是算法的问题啊 😰 不知道是系统还是编译器的问题

什么，李大夫能帮忙诊断一下吗

OP 又一次发现：在命令行执行会出错的 build，用 GDB 执行一定会得到正确答案

OP 拿 g++ 又编译了一次，本来想多尝试几次 GDB 抓个现行，但现在又复现不出来错误结果了。

OP 感到十分困惑，希望能得到解答

OP 的测试环境是 Fedora 40 + zsh shell + g++ 14.1.1：

又拿 clang 编译了一遍：

将 source 发给朋友在 Ubuntu 上测试得到了同样的结果：

错误答案 1 是 max_m = DBL_MIN 导致的，而正确答案 4 是 max_m 被成功更新为 3.33333 得出的。

本 source code 并不是原题目的正确解答，只能通过 2/4 个测试，但是这是因为 OP 读题读漏了一点，在修改的过程中发现本问题。

这个变量定义在这个地方：

以下是 source 和测试用例：

#include <iostream>
#include <cfloat>
#include <map>

using namespace std;

typedef long long ll;

const string no_solution = "NO SOLUTION";

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

    double min_M = DBL_MAX;
    double max_m = DBL_MIN;

    map<int, int> input;

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

        if (p == expected) {
            sales_at_expected = s;
        }

        input[p] = s;
        // 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;
        ll ci = (pi - cost) * si;
        if (si - sales_at_expected == 0) 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 = ll(max_m + 1.0);
    // ll ans_max = ll(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;
    // }

    ll ans = ll(max_m + 1.0);

    if (ans > min_M) cout << no_solution << endl;
    else cout << ans << endl;
}

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

    solve();

    return 0;
}

31
28 130
30 120
31 110
-1  -1
15

这是什么导致的 🤯

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

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

P1023 [NOIP2000 普及组] 税收与补贴问题

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

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

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

$w = sales \times subsidy + c$.

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

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

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

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

严查康米

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;
}

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;
}

学习。

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

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

我就感觉到快

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

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