3 Likes
一开始只想到用 dp[i][j] 记录第 i 个月拥有 j 钱时能达到的最大 h，但很明显存不下 但其实输入限制已经提示得很明显了，下标应该是 h_i ，存达到这个值的最小金额
但拥有的钱每个月都在变化，所以没想到怎么存钱 果然还是得多搞钱
2 Likes
OP 注册 7min 拿下 lv3 
我擦，乜 bug，點解我毋知 
1 Like
我就感觉到快
2 Likes
@aibot 请将这句话翻译为普通话
m0rsun 说 “我擦，乜 bug，點解我毋知” 的普通话翻译是 “我去，什么 bug，为什么我不知道”。
5 Likes
想法有了但写不出来是最难受的，得狠狠学习 C++ 语法，
蹲更新 
1 Like
OP 给我说他在突击 C++，起码要把
- 16 The
stringClass and the Standard Template Library - 17 Input, Output, and Files
的前半部分标准输入输出看了
1 Like
学习。
P1147 ，two pointers，注意到是在纯正整数数列中寻找，故右指针右移必然会增加和，左指针右移必然会减少和
1 Like
用一个 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;
}
1 Like
不是线性的，map 的插入查找复杂度都是 logn。
另：这个题也可以排序后双指针，总时间复杂度是一样的，留给 OP 思考
1 Like
惊天巨坑 
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;
}
1 Like
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 就是解
这是什么导致的
注释掉 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 普及组] 产生数
终于过了，改了几乎大半天的一道题。主要的坑点在：经过一次变幻后的数可能可以进行二次变换，所以要对 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;
}
1 Like
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;
}