{"topic":{"id":12644,"title":"算法做题记录","slug":"topic","categoryId":11,"createdAt":"2024-05-21 13:47:41.07097","bumpedAt":"2024-05-30 18:39:25.892596","views":1191,"postsCount":47,"highestPostNumber":48,"likeCount":31,"closed":false,"pinned":false,"pinnedGlobally":false,"pinnedAt":null,"pinnedUntil":null,"isBanner":false,"excerpt":":D","deletedAt":null,"isAnonymous":false,"category":{"id":11,"name":"深入交流","slug":"distilled","color":"c01c28"},"author":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif"},"tags":[]},"posts":[{"id":33957,"postNumber":1,"raw":":D","cooked":"

\n","createdAt":"2024-05-21 13:47:41.156679","updatedAt":"2024-05-21 13:47:41.156679","replyToPostNumber":null,"replyCount":0,"likeCount":3,"wordCount":1,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":3,"users":[{"id":601,"username":"m0rsun","name":null},{"id":1929,"username":"Quit","name":"Qwen"},{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":33958,"postNumber":2,"raw":"![image|690x434](/uploads/image/ce/32/ce32e014745208dfcbf42218e02bd4c095164169849f70f8d0e811833b1035e4.avif)\n\n一开始只想到用 `dp[i][j]` 记录第 `i` 个月拥有 `j` 钱时能达到的最大 `h`，但很明显存不下 :D 但其实输入限制已经提示得很明显了，下标应该是 $h_i$ ，存达到这个值的最小金额\n\n但拥有的钱每个月都在变化，所以没想到怎么存钱 :D 果然还是得多搞钱 :D","cooked":"

$\"image\"$

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

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

\n","createdAt":"2024-05-21 13:51:16.174389","updatedAt":"2024-05-21 13:54:12.112474","replyToPostNumber":null,"replyCount":0,"likeCount":2,"wordCount":102,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"🐈️","count":1,"users":[{"id":601,"username":"m0rsun","name":null}],"hasReacted":false},{"reaction":"❤️","count":2,"users":[{"id":601,"username":"m0rsun","name":null},{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":33960,"postNumber":3,"raw":"OP 注册 7min 拿下 lv3 :grinning_cat_with_closed_eyes:","cooked":"

OP 注册 7min 拿下 lv3 😸

\n","createdAt":"2024-05-21 14:15:05.792597","updatedAt":"2024-05-21 14:15:05.792597","replyToPostNumber":null,"replyCount":2,"likeCount":0,"wordCount":8,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":601,"username":"m0rsun","name":null,"avatarUrl":"/uploads/image/37/7f/377f4ae853850691ab959270f01d52509ee07caf808041ddb0ab22488a0e9f85.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":33961,"postNumber":4,"raw":"我擦，乜 bug，點解我毋知 :a_grinning_face_with_sweat:","cooked":"

我擦，乜 bug，點解我毋知 $\":a_grinning_face_with_sweat:\"$

\n","createdAt":"2024-05-21 14:17:36.91653","updatedAt":"2024-07-19 03:24:39.313731","replyToPostNumber":3,"replyCount":1,"likeCount":1,"wordCount":11,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"wave_gif","count":1,"users":[{"id":1941,"username":"john","name":"John"}],"hasReacted":false},{"reaction":"❤️","count":1,"users":[{"id":1941,"username":"john","name":"John"}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4668,"username":"IO","name":null,"avatarUrl":"/uploads/image/86/f2/86f267c0aaa73835a999b7cc3a7e7a701605574eda9a2c2a56f5ddbbba64d1a9.avif","admin":true,"moderator":false,"signatureRaw":"","signatureCooked":null}},{"id":33962,"postNumber":5,"raw":"我就感觉到快","cooked":"

我就感觉到快

\n","createdAt":"2024-05-21 14:17:50.615881","updatedAt":"2024-05-21 14:17:50.615881","replyToPostNumber":3,"replyCount":0,"likeCount":2,"wordCount":6,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"🤗️","count":1,"users":[{"id":601,"username":"m0rsun","name":null}],"hasReacted":false},{"reaction":"❤️","count":2,"users":[{"id":601,"username":"m0rsun","name":null},{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":33963,"postNumber":6,"raw":"@aibot 请将这句话翻译为普通话","cooked":"

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

\n","createdAt":"2024-05-21 14:18:26.587187","updatedAt":"2024-05-21 14:18:26.587187","replyToPostNumber":4,"replyCount":1,"likeCount":0,"wordCount":12,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":601,"username":"m0rsun","name":null,"avatarUrl":"/uploads/image/37/7f/377f4ae853850691ab959270f01d52509ee07caf808041ddb0ab22488a0e9f85.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":33964,"postNumber":7,"raw":"m0rsun 说 \"我擦，乜 bug，點解我毋知\" 的普通话翻译是 \"我去，什么 bug，为什么我不知道\"。","cooked":"

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

\n","createdAt":"2024-05-21 14:18:29.947426","updatedAt":"2024-05-21 14:18:29.947426","replyToPostNumber":6,"replyCount":0,"likeCount":5,"wordCount":36,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"👍️","count":3,"users":[{"id":1929,"username":"Quit","name":"Qwen"},{"id":1941,"username":"john","name":"John"},{"id":3003,"username":"welldown","name":"Jerry"}],"hasReacted":false},{"reaction":"❤️","count":5,"users":[{"id":31,"username":"TsuinoSora","name":null},{"id":1929,"username":"Quit","name":"Qwen"},{"id":1941,"username":"john","name":"John"},{"id":3003,"username":"welldown","name":"Jerry"},{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":-4,"username":"aibot_old","name":"小AI同學","avatarUrl":"/uploads/image/02/1b/021bb0b0848388a911ae795dde7c8e5b3f1962316b2d88853208172cd0e89de2.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":33980,"postNumber":8,"raw":"想法有了但写不出来是最难受的，得狠狠学习 C++ 语法，","cooked":"

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

\n","createdAt":"2024-05-21 16:29:43.914119","updatedAt":"2024-05-21 16:29:43.914119","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":24,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34280,"postNumber":9,"raw":"蹲更新 :grinning_cat:","cooked":"

蹲更新 😺

\n","createdAt":"2024-05-24 17:17:34.068784","updatedAt":"2024-05-24 17:17:34.068784","replyToPostNumber":null,"replyCount":1,"likeCount":1,"wordCount":4,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":6205,"username":"uika_winwing","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":601,"username":"m0rsun","name":null,"avatarUrl":"/uploads/image/37/7f/377f4ae853850691ab959270f01d52509ee07caf808041ddb0ab22488a0e9f85.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":34300,"postNumber":10,"raw":"OP 给我说他在突击 C++，起码要把\n\n- 16 The `string` Class and the Standard Template Library\n- 17 Input, Output, and Files \n\n的前半部分标准输入输出看了","cooked":"

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

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

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

\n","createdAt":"2024-05-25 06:35:12.843377","updatedAt":"2024-10-25 11:20:57.843545","replyToPostNumber":9,"replyCount":0,"likeCount":1,"wordCount":42,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":601,"username":"m0rsun","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":6205,"username":"uika_winwing","name":null,"avatarUrl":"/uploads/image/76/3b/763b1e5ad8a424c4450bb26cea5ae532e7b1cd9da926ac5d99215d7123bf6002.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34320,"postNumber":11,"raw":"学习。\n\n[P1147](https://www.luogu.com.cn/problem/P1147) ，two pointers，注意到是在纯正整数数列中寻找，故右指针右移必然会增加和，左指针右移必然会减少和","cooked":"

学习。

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

\n","createdAt":"2024-05-25 19:19:04.633786","updatedAt":"2024-05-25 19:19:04.633786","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":45,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":601,"username":"m0rsun","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34343,"postNumber":12,"raw":"[P1102](https://www.luogu.com.cn/problem/P1102)\n\n用一个 map 收集了所有出现的数和出现次数，因为要找所有 a - b = c，所以只需要遍历大于 c 的数，然后看能不能找到 b 就行。所以复杂度应该是线性的\n\n但是题目说 100% 的数据都小于 $2^{30}$ ，不知道为什么用 int 存不下，有一个点没过，换成 long long 才过。\n\n```c++\n#include \n#include \n#include \n\nusing namespace std;\n\ntypedef long long ll;\n\nvoid solve() {\n ll n, c;\n cin >> n >> c;\n\n ll ans = 0;\n map count;\n for (ll i = 0; i < n; i++) {\n ll ni;\n cin >> ni;\n if (count.find(ni) != count.end()) {\n count[ni]++;\n } else {\n count[ni] = 1;\n }\n }\n\n for (auto const &pair : count) {\n auto found = count.find(pair.first - c);\n // cout << \"pair \" << pair.first << \" \" << pair.second << endl;\n // cout << \"found \" << found->first << \" \" << found->second << endl;\n if (pair.first > c && found != count.end()) {\n ans += pair.second * found->second;\n }\n }\n\n cout << ans << endl;\n}\n\nint main() {\n ios::sync_with_stdio(false);\n\n solve();\n\n return 0;\n}\n```","cooked":"

P1102

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

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

#include <iostream>\n#include <map>\n#include <algorithm>\n\nusing namespace std;\n\ntypedef long long ll;\n\nvoid solve() {\n    ll n, c;\n    cin >> n >> c;\n\n    ll ans = 0;\n    map<ll, ll> count;\n    for (ll i = 0; i < n; i++) {\n        ll ni;\n        cin >> ni;\n        if (count.find(ni) != count.end()) {\n            count[ni]++;\n        } else {\n            count[ni] = 1;\n        }\n    }\n\n    for (auto const &pair : count) {\n        auto found = count.find(pair.first - c);\n        // cout << \"pair  \" << pair.first << \" \" << pair.second << endl;\n        // cout << \"found \" << found->first << \" \" << found->second << endl;\n        if (pair.first > c && found != count.end()) {\n            ans += pair.second * found->second;\n        }\n    }\n\n    cout << ans << endl;\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n\n    solve();\n\n    return 0;\n}\n

\n","createdAt":"2024-05-26 07:03:52.447844","updatedAt":"2024-05-26 07:05:01.012561","replyToPostNumber":null,"replyCount":1,"likeCount":1,"wordCount":240,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":601,"username":"m0rsun","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34371,"postNumber":13,"raw":"不是线性的，map 的插入查找复杂度都是 logn。\n另：这个题也可以排序后双指针，总时间复杂度是一样的，留给 OP 思考","cooked":"

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

\n","createdAt":"2024-05-26 13:02:50.560986","updatedAt":"2024-05-26 13:02:50.560986","replyToPostNumber":12,"replyCount":0,"likeCount":1,"wordCount":48,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":4648,"username":"nonsuch","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":601,"username":"m0rsun","name":null,"avatarUrl":"/uploads/image/37/7f/377f4ae853850691ab959270f01d52509ee07caf808041ddb0ab22488a0e9f85.avif","admin":false,"moderator":true,"signatureRaw":null,"signatureCooked":null}},{"id":34372,"postNumber":14,"raw":"[P1022](https://www.luogu.com.cn/problem/P1022)\n\n![image|459x500](/uploads/image/72/ea/72ea3710537515cb56cb9694941b4217995daf62e3d556de8d295b53cebc6f96.avif)\n\n惊天巨坑 :exploding_head: `0 / -1` 会输出 `-0`\n\n是因为浮点数与 two's complement 整数不同，同时可以表示 +0 和 -0\n\n本题是模拟题，每次读一个字符，并根据字符类型来处理。\n\n```cpp\n#include \n#include \n\nusing namespace std;\n\nvoid solve() {\n char x = '\\0';\n double a = .0;\n double c = .0;\n // convert to 'a * x = c'\n\n int left = 1; // -1 for right of the equal sign\n bool coefficient = false; // is coefficient of unknown\n char read_c; // current character read\n int scalar = 0;\n int sign = 1; // -1 for negative\n\n while (cin.get(read_c) && read_c != '\\n') {\n if (read_c >= 'a' && read_c <= 'z') {\n if (x == '\\0') x = read_c;\n coefficient = true;\n\n } else if (read_c >= '0' && read_c <= '9') {\n scalar = 10 * scalar + (read_c - '0');\n // cout << \"scalar \" << scalar << endl;\n } else /* + - = */ {\n if (coefficient) {\n if (scalar == 0) scalar = 1;\n a += left * sign * scalar;\n // cout << \"a \" << a << endl;\n } else {\n c += (-left) * sign * scalar;\n // cout << \"c \" << c << endl;\n }\n\n // reset\n scalar = 0;\n coefficient = false;\n sign = 1;\n \n if (read_c == '-') sign = -1;\n else if (read_c == '=') left = -1;\n\n // cout << \"sign \" << sign << endl;\n }\n }\n\n // cout << left << scalar << sign << endl;\n // handle last block of input\n if (coefficient) {\n if (scalar == 0) scalar = 1;\n a += left * sign * scalar;\n // cout << \"a \" << a << endl;\n } else {\n c += (-left) * sign * scalar;\n // cout << \"c \" << c << endl; \n }\n\n if (c / a == 0) printf(\"%c=0.000\\n\", x);\n else printf(\"%c=%.3f\\n\", x, c / a);\n}\n\nint main() {\n ios::sync_with_stdio(false);\n\n solve();\n\n return 0;\n}\n```","cooked":"

P1022

$\"image\"$

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

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

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

#include <iostream>\n#include <cstdio>\n\nusing namespace std;\n\nvoid solve() {\n    char x = '\\0';\n    double a = .0;\n    double c = .0;\n    // convert to 'a * x = c'\n\n    int left = 1; // -1 for right of the equal sign\n    bool coefficient = false; // is coefficient of unknown\n    char read_c; // current character read\n    int scalar = 0;\n    int sign = 1; // -1 for negative\n\n    while (cin.get(read_c) && read_c != '\\n') {\n        if (read_c >= 'a' && read_c <= 'z') {\n            if (x == '\\0') x = read_c;\n            coefficient = true;\n\n        } else if (read_c >= '0' && read_c <= '9') {\n            scalar = 10 * scalar + (read_c - '0');\n            // cout << \"scalar \" << scalar << endl;\n        } else /* + - = */ {\n            if (coefficient) {\n                if (scalar == 0) scalar = 1;\n                a += left * sign * scalar;\n                // cout << \"a \" << a << endl;\n            } else {\n                c += (-left) * sign * scalar;\n                // cout << \"c \" << c << endl;\n            }\n\n            // reset\n            scalar = 0;\n            coefficient = false;\n            sign = 1;\n            \n            if (read_c == '-') sign = -1;\n            else if (read_c == '=') left = -1;\n\n            // cout << \"sign \" << sign << endl;\n        }\n    }\n\n    // cout << left << scalar << sign << endl;\n    // handle last block of input\n    if (coefficient) {\n        if (scalar == 0) scalar = 1;\n        a += left * sign * scalar;\n        // cout << \"a \" << a << endl;\n    } else {\n        c += (-left) * sign * scalar;\n        // cout << \"c \" << c << endl; \n    }\n\n    if (c / a == 0) printf(\"%c=0.000\\n\", x);\n    else printf(\"%c=%.3f\\n\", x, c / a);\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n\n    solve();\n\n    return 0;\n}\n

\n","createdAt":"2024-05-26 13:21:05.74677","updatedAt":"2024-05-26 13:35:19.958402","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":365,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":601,"username":"m0rsun","name":null}],"hasReacted":false}],"wiki":false,"version":2,"publicVersion":2,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34373,"postNumber":15,"raw":"![image|690x303](/uploads/image/3f/e6/3fe650828a35b4b2367f7f3e9e333d4e3be602a565011f92ea458c62db6860ca.avif)\n\n严查康米","cooked":"

$\"image\"$

严查康米

\n","createdAt":"2024-05-26 13:29:56.305898","updatedAt":"2024-05-26 13:29:56.305898","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":5,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34374,"postNumber":16,"raw":"# [P1023 [NOIP2000 普及组] 税收与补贴问题](https://www.luogu.com.cn/problem/P1023)\n\n可以看出在某一价位下的利润是\n\n$w = sales \\times (price - cost + subsidy)$\n\n其中的变量只有 $subsidy$ ，所以\n\n$w = sales \\times subsidy + c$.\n\n每个价位都有这么一条直线，需要找的就是最小的 $subsidy$ 取值，使得政府指导价下的 w 最大。\n\n观察到比政府指导价 $s_g$ 小的价格下，销量一定更大，所以函数增长率更大。比 $s_g$ 大的价格下，销量一定更小，所以函数增长率更小。\n\n这样，目标就比较明确了：\n\n- 找到斜率更小的函数中交点横坐标的最大值 m\n- 找到斜率更大的函数中交点横坐标的最小值 M\n- 如果 $M < m$ 则无解，否则 m 就是解","cooked":"

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 就是解

\n","createdAt":"2024-05-26 14:12:47.697397","updatedAt":"2024-05-26 14:12:47.697397","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":223,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34382,"postNumber":17,"raw":"![image|690x412](/uploads/image/b1/d5/b1d5a10c5fc4778bec59359a97a3f86457ac473aaf5c810517366504c70e892c.avif)\n\n这是什么导致的 :exploding_head:\n\n注释掉 72 行后得到的 `max_m` 输出是 3.3333，加上 72 行之后得到的 `max_m` 输出是 2.22507e-308\n\n而且这个输出语句是在第 70 行，在造成影响的语句的上面 :exploding_head:","cooked":"

$\"image\"$

这是什么导致的 🤯

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

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

\n","createdAt":"2024-05-26 16:32:51.574489","updatedAt":"2024-05-26 16:33:44.892461","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":63,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34462,"postNumber":18,"raw":"过了。对于中间没有提供的数据也要一个一个插值，这点题目没说清楚\n\n```cpp\n#include \n#include \n#include \n#include \n#include \n\nusing namespace std;\n\ntypedef long long ll;\n\nconst string no_solution = \"NO SOLUTION\";\n\nvoid solve() {\n int expected;\n cin >> expected;\n int sales_at_expected = 0;\n\n double min_M = DBL_MAX;\n double max_m = -DBL_MAX;\n\n map input;\n\n // w = sales * subsidy + c\n // c = sales * (price - cost)\n int cost;\n double sales_at_cost;\n cin >> cost >> sales_at_cost;\n input[cost] = sales_at_cost;\n \n int last = cost; // for inserting value\n int p = 0, s = 0;\n int max_p = INT_MIN;\n double max_p_s = -DBL_MAX;\n while (cin >> p >> s && p != -1) {\n max_p = max(p, max_p);\n input[p] = s;\n\n // insert value\n if (p - last > 1) {\n double last_s = input[last];\n double slope = double(s - last_s) / double(p - last);\n for (int j = last + 1; j < p; j++) {\n input[j] = (last_s += slope);\n // cout << input[j] << \" \";\n }\n // cout << endl;\n }\n last = p;\n // cout << p << \" \" << s << endl;\n }\n\n // calculate unknown\n max_p_s = input[max_p];\n // cout << max_p << endl;\n // cout << max_p_s << endl;\n int decrement;\n cin >> decrement;\n while ((max_p_s -= decrement) >= 0) {\n // cout << max_p + 1 << \" \" << max_p_s << endl;\n input[++max_p] = max_p_s;\n }\n\n sales_at_expected = input[expected];\n\n // calculate intersections\n ll c_expected = sales_at_expected * (expected - cost);\n for (const auto &pair : input) {\n auto &pi = pair.first;\n auto &si = pair.second;\n // cout << pi << \" \" << si << endl;\n\n ll ci = (pi - cost) * si;\n if (abs(si - sales_at_expected) < 1e-5) continue;\n double subsidy = double(c_expected - ci) / double(si - sales_at_expected);\n \n // cout << \"subsidy \" << subsidy << endl;\n\n if (pi < expected && subsidy < min_M) min_M = subsidy;\n else if (pi > expected && subsidy > max_m) max_m = subsidy;\n }\n\n // find result\n // cout << max_m << \" \" << min_M << endl;\n ll ans_min = ceil(max_m);\n ll ans_max = floor(min_M);\n // cout << ans_min << \" \" << ans_max << endl; \n if (ans_min > ans_max) cout << no_solution << endl;\n else {\n // find minimum absolute value\n if (ans_min <= 0 && ans_max >= 0) cout << 0 << endl;\n else if (ans_min >= 0) cout << ans_min << endl;\n else cout << ans_max << endl;\n }\n}\n\nint main() {\n ios::sync_with_stdio(false);\n\n solve();\n\n return 0;\n}\n```","cooked":"

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

#include <iostream>\n#include <cfloat>\n#include <climits>\n#include <map>\n#include <cmath>\n\nusing namespace std;\n\ntypedef long long ll;\n\nconst string no_solution = \"NO SOLUTION\";\n\nvoid solve() {\n    int expected;\n    cin >> expected;\n    int sales_at_expected = 0;\n\n    double min_M = DBL_MAX;\n    double max_m = -DBL_MAX;\n\n    map<int, double> input;\n\n    // w = sales * subsidy + c\n    // c = sales * (price - cost)\n    int cost;\n    double sales_at_cost;\n    cin >> cost >> sales_at_cost;\n    input[cost] = sales_at_cost;\n    \n    int last = cost; // for inserting value\n    int p = 0, s = 0;\n    int max_p = INT_MIN;\n    double max_p_s = -DBL_MAX;\n    while (cin >> p >> s && p != -1) {\n        max_p = max(p, max_p);\n        input[p] = s;\n\n        // insert value\n        if (p - last > 1) {\n            double last_s = input[last];\n            double slope = double(s - last_s) / double(p - last);\n            for (int j = last + 1; j < p; j++) {\n                input[j] = (last_s += slope);\n                // cout << input[j] << \" \";\n            }\n            // cout << endl;\n        }\n        last = p;\n        // cout << p << \" \" << s << endl;\n    }\n\n    // calculate unknown\n    max_p_s = input[max_p];\n    // cout << max_p << endl;\n    // cout << max_p_s << endl;\n    int decrement;\n    cin >> decrement;\n    while ((max_p_s -= decrement) >= 0) {\n        // cout << max_p + 1 << \" \" << max_p_s << endl;\n        input[++max_p] = max_p_s;\n    }\n\n    sales_at_expected = input[expected];\n\n    // calculate intersections\n    ll c_expected = sales_at_expected * (expected - cost);\n    for (const auto &pair : input) {\n        auto &pi = pair.first;\n        auto &si = pair.second;\n        // cout << pi << \" \" << si << endl;\n\n        ll ci = (pi - cost) * si;\n        if (abs(si - sales_at_expected) < 1e-5) continue;\n        double subsidy = double(c_expected - ci) / double(si - sales_at_expected);\n        \n        // cout << \"subsidy \" << subsidy << endl;\n\n        if (pi < expected && subsidy < min_M) min_M = subsidy;\n        else if (pi > expected && subsidy > max_m) max_m = subsidy;\n    }\n\n    // find result\n    // cout << max_m << \" \" << min_M << endl;\n    ll ans_min = ceil(max_m);\n    ll ans_max = floor(min_M);\n    // cout << ans_min << \" \" << ans_max << endl; \n    if (ans_min > ans_max) cout << no_solution << endl;\n    else {\n        // find minimum absolute value\n        if (ans_min <= 0 && ans_max >= 0) cout << 0 << endl;\n        else if (ans_min >= 0) cout << ans_min << endl;\n        else cout << ans_max << endl;\n    }\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n\n    solve();\n\n    return 0;\n}\n

\n","createdAt":"2024-05-27 09:02:55.696104","updatedAt":"2024-05-27 09:02:55.696104","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":450,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34491,"postNumber":19,"raw":"# [P1037 [NOIP2002 普及组] 产生数](https://www.luogu.com.cn/problem/P1037)\n\n终于过了，改了几乎大半天的一道题。主要的坑点在：经过一次变幻后的数可能可以进行二次变换，所以要对 0-9 每个数都进行一次深搜，找到每种数可能的变换情况，然后就是统计原数字每个数有几种，乘起来就行\n\n在确定了 `ans` 将会达到 $2^{100}$ 级别后，本来想用 `__int128_t` 来存储，但是发现这种 C 标准里没有，只存在于 gcc 实现中的类型并没有得到很好的支持。于是实现了一个 `BigInt` 类型来存储。\n\n```cpp\n#include \n#include \n#include \n#include \n\nusing namespace std;\n\nvoid DFS(const int num, const int (&table)[10][10], int &variant_count, bool (&visited)[10]);\n\ninline void flatten(vector &one) {\n const int len = one.size();\n for (int i = 0; i < len; i++) {\n if (one[i] >= 10) {\n one[i + 1] += one[i] / 10;\n one[i] %= 10;\n }\n }\n}\n\ninline void multiply_by(vector &one, int other) {\n for (int &i : one) {\n i *= other;\n }\n flatten(one);\n};\n\n\nvoid solve() {\n int count[10] = { 0 };\n char input;\n while (cin.get(input) && input != ' ') {\n count[input - '0']++;\n }\n\n int k;\n cin >> k;\n\n int table[10][10];\n memset(table, -1, 10 * 10 * sizeof (int));\n\n for (int i = 0; i < k; i++) {\n int left, right;\n cin >> left >> right;\n\n int j = -1;\n while (table[left][++j] != -1);\n table[left][j] = right;\n }\n\n // search for variants for each number\n int variants[10];\n for (int i = 0; i < 10; i++) {\n variants[i] = 1;\n }\n\n for (int i = 0; i < 10; i++) {\n bool visited[10] = { false };\n visited[i] = true;\n DFS(i, table, variants[i], visited);\n }\n\n // long long ans = 1;\n // for (int i = 0; i < 10; i++) {\n // int &left = count[i];\n // while (left > 0) {\n // ans *= variants[i];\n // left--;\n // }\n // }\n\n // big integer multiplication\n vector ans(130);\n ans[0] = 1;\n // cout << ans.size() << endl;\n for (int i = 0; i < 10; i++) {\n int &left = count[i];\n while (left > 0) {\n multiply_by(ans, variants[i]);\n left--;\n }\n }\n\n // adjust decimal big integer\n // flatten(ans);\n\n // print ans\n int i = 130;\n while (ans[--i] == 0);\n for (; i >= 0; i--) {\n cout << ans[i];\n }\n cout << endl;\n}\n\nvoid DFS(const int num, const int (&table)[10][10], int &variant_count, bool (&visited)[10]) {\n auto &list = table[num];\n int j = -1;\n while (list[++j] != -1) {\n auto &to_visit = list[j];\n if (!visited[to_visit]) {\n visited[to_visit] = true;\n variant_count++;\n DFS(to_visit, table, variant_count, visited);\n }\n }\n}\n\nint main() {\n ios::sync_with_stdio(false);\n\n solve();\n\n return 0;\n}\n\n```","cooked":"

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

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

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

#include <iostream>\n#include <cstring>\n#include <vector>\n#include <cmath>\n\nusing namespace std;\n\nvoid DFS(const int num, const int (&table)[10][10], int &variant_count, bool (&visited)[10]);\n\ninline void flatten(vector<int> &one) {\n    const int len = one.size();\n    for (int i = 0; i < len; i++) {\n        if (one[i] >= 10) {\n            one[i + 1] += one[i] / 10;\n            one[i] %= 10;\n        }\n    }\n}\n\ninline void multiply_by(vector<int> &one, int other) {\n    for (int &i : one) {\n        i *= other;\n    }\n    flatten(one);\n};\n\n\nvoid solve() {\n    int count[10] = { 0 };\n    char input;\n    while (cin.get(input) && input != ' ') {\n        count[input - '0']++;\n    }\n\n    int k;\n    cin >> k;\n\n    int table[10][10];\n    memset(table, -1, 10 * 10 * sizeof (int));\n\n    for (int i = 0; i < k; i++) {\n        int left, right;\n        cin >> left >> right;\n\n        int j = -1;\n        while (table[left][++j] != -1);\n        table[left][j] = right;\n    }\n\n    // search for variants for each number\n    int variants[10];\n    for (int i = 0; i < 10; i++) {\n        variants[i] = 1;\n    }\n\n    for (int i = 0; i < 10; i++) {\n        bool visited[10] = { false };\n        visited[i] = true;\n        DFS(i, table, variants[i], visited);\n    }\n\n    // long long ans = 1;\n    // for (int i = 0; i < 10; i++) {\n    //     int &left = count[i];\n    //     while (left > 0) {\n    //         ans *= variants[i];\n    //         left--;\n    //     }\n    // }\n\n    // big integer multiplication\n    vector<int> ans(130);\n    ans[0] = 1;\n    // cout << ans.size() << endl;\n    for (int i = 0; i < 10; i++) {\n        int &left = count[i];\n        while (left > 0) {\n            multiply_by(ans, variants[i]);\n            left--;\n        }\n    }\n\n    // adjust decimal big integer\n    // flatten(ans);\n\n    // print ans\n    int i = 130;\n    while (ans[--i] == 0);\n    for (; i >= 0; i--) {\n        cout << ans[i];\n    }\n    cout << endl;\n}\n\nvoid DFS(const int num, const int (&table)[10][10], int &variant_count, bool (&visited)[10]) {\n    auto &list = table[num];\n    int j = -1;\n    while (list[++j] != -1) {\n        auto &to_visit = list[j];\n        if (!visited[to_visit]) {\n            visited[to_visit] = true;\n            variant_count++;\n            DFS(to_visit, table, variant_count, visited);\n        }\n    }\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n\n    solve();\n\n    return 0;\n}\n\n

\n","createdAt":"2024-05-27 19:02:45.688599","updatedAt":"2024-05-27 19:02:45.688599","replyToPostNumber":null,"replyCount":0,"likeCount":1,"wordCount":534,"liked":false,"bookmarked":false,"polls":[],"reactions":[{"reaction":"❤️","count":1,"users":[{"id":4668,"username":"IO","name":null}],"hasReacted":false}],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}},{"id":34493,"postNumber":20,"raw":"# [P1045 [NOIP2003 普及组] 麦森数](https://www.luogu.com.cn/problem/P1045#submit)\n\n最简单的一集，一发过了。给一个二进制数，让求十进制的位数（开几个对数）和十进制后 500 位（高精度整数算几次压位乘法）\n\n```cpp\n#include \n#include \n#include \n\nusing namespace std;\n\nconst double log2_10 = log2(10);\n\nvoid flatten(vector &one) {\n for (int i = 0; i < 500; i++) {\n if (one[i] >= 10) {\n one[i + 1] += one[i] / 10;\n one[i] %= 10;\n }\n }\n}\n\nvoid multiply_by(vector &one, const int num) {\n for (int &i : one) {\n i *= num;\n }\n flatten(one);\n}\n\nvoid solve() {\n int p;\n cin >> p;\n\n int digits = int(double(p) / log2_10) + 1;\n cout << digits << endl;\n\n vector output(505);\n output[0] = 1;\n\n // convert binary to decimal\n while (p >= 9) {\n // cout << p << endl;\n multiply_by(output, 512);\n p -= 9;\n }\n\n if (p > 0) {\n multiply_by(output, 1 << p);\n }\n\n output[0] -= 1;\n int j = -1;\n while (output[++j] < 0) {\n output[j] += 10;\n output[j + 1] -= 1;\n }\n\n // output answer\n for (int i = 10; i > 0; i--) {\n for (int j = i * 50 - 1; j >= i * 50 - 50; j--) {\n cout << output[j];\n }\n cout << endl;\n }\n}\n\nint main() {\n ios::sync_with_stdio(false);\n\n solve();\n\n return 0;\n}\n```","cooked":"

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

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

#include <iostream>\n#include <cmath>\n#include <vector>\n\nusing namespace std;\n\nconst double log2_10 = log2(10);\n\nvoid flatten(vector<int> &one) {\n    for (int i = 0; i < 500; i++) {\n        if (one[i] >= 10) {\n            one[i + 1] += one[i] / 10;\n            one[i] %= 10;\n        }\n    }\n}\n\nvoid multiply_by(vector<int> &one, const int num) {\n    for (int &i : one) {\n        i *= num;\n    }\n    flatten(one);\n}\n\nvoid solve() {\n    int p;\n    cin >> p;\n\n    int digits = int(double(p) / log2_10) + 1;\n    cout << digits << endl;\n\n    vector<int> output(505);\n    output[0] = 1;\n\n    // convert binary to decimal\n    while (p >= 9) {\n        // cout << p << endl;\n        multiply_by(output, 512);\n        p -= 9;\n    }\n\n    if (p > 0) {\n        multiply_by(output, 1 << p);\n    }\n\n    output[0] -= 1;\n    int j = -1;\n    while (output[++j] < 0) {\n        output[j] += 10;\n        output[j + 1] -= 1;\n    }\n\n    // output answer\n    for (int i = 10; i > 0; i--) {\n        for (int j = i * 50 - 1; j >= i * 50 - 50; j--) {\n            cout << output[j];\n        }\n        cout << endl;\n    }\n}\n\nint main() {\n    ios::sync_with_stdio(false);\n\n    solve();\n\n    return 0;\n}\n

\n","createdAt":"2024-05-27 20:11:38.300508","updatedAt":"2024-05-27 20:11:38.300508","replyToPostNumber":null,"replyCount":0,"likeCount":0,"wordCount":261,"liked":false,"bookmarked":false,"polls":[],"reactions":[],"wiki":false,"version":1,"publicVersion":1,"deletedAt":null,"isAnonymous":false,"user":{"id":4648,"username":"nonsuch","name":null,"avatarUrl":"/uploads/image/e0/1a/e01a94ce578d11e72d80c156cd492926e5060c3cac94c7134e40f07ffe4c3e76.avif","admin":false,"moderator":false,"signatureRaw":null,"signatureCooked":null}}],"hasMore":true,"lastReadPostNumber":18,"hasUrlPostNumber":true}