Hướng dẫn giải của STR10: Tổng các số
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Trong xâu S, các số nguyên là các dãy chữ số liên tiếp. Cần tính tổng của tất cả các số này. Tổng có thể rất lớn (S dài tối đa 255 ký tự) nên phải tính bằng xâu chữ số, không dùng kiểu số thường.
Sub 1: Cộng dồn bằng phép cộng xâu — ~O(n^2)~
Tách từng số trong S rồi cộng vào tổng bằng hàm cộng hai xâu chữ số (cộng từng cặp chữ số có nhớ). Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
// Cộng hai số nguyên không âm biểu diễn bằng xâu chữ số (tránh tràn số)
string addStr(const string &a, const string &b) {
string r;
int i = (int)a.size() - 1, j = (int)b.size() - 1, c = 0;
while (i >= 0 || j >= 0 || c) {
int s = c;
if (i >= 0) s += a[i--] - '0';
if (j >= 0) s += b[j--] - '0';
r.push_back(char('0' + s % 10));
c = s / 10;
}
reverse(r.begin(), r.end());
// bỏ số 0 đứng đầu
size_t p = r.find_first_not_of('0');
if (p == string::npos) return "0";
return r.substr(p);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
getline(cin, s);
// Vét cạn: tách từng số (dãy chữ số liên tiếp) rồi cộng dồn vào tổng bằng phép cộng xâu
string total = "0", cur;
for (char c : s) {
if (c >= '0' && c <= '9') {
cur.push_back(c);
} else {
if (!cur.empty()) total = addStr(total, cur);
cur.clear();
}
}
if (!cur.empty()) total = addStr(total, cur);
cout << total << "\n";
return 0;
}
Sub 2: Cộng theo cột — ~O(n)~
Với mỗi số có độ dài L, chữ số thứ k tính từ phải được cộng vào cột k. Sau khi duyệt hết S, lan truyền số nhớ từ cột thấp lên cột cao rồi bỏ số 0 đứng đầu. Cách này chỉ cần một lượt duyệt. Đạt 20/20 test.
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
getline(cin, s);
// Cộng theo cột: col[k] là tổng các chữ số ở vị trí thứ k tính từ phải của mọi số
// S dài tối đa 255 nên tổng chữ số không vượt quá 255 * 9
vector<long long> col(1000, 0);
int len = 0; // độ dài của số đang đọc
for (int i = 0; i <= (int)s.size(); i++) {
char c = (i < (int)s.size()) ? s[i] : ' ';
if (c >= '0' && c <= '9') {
len++;
} else {
// kết thúc một số có độ dài len, các chữ số của nó nằm ngay trước vị trí i
for (int k = 0; k < len; k++)
col[k] += s[i - 1 - k] - '0';
len = 0;
}
}
// Lan truyền nhớ
string res;
long long carry = 0;
for (size_t k = 0; k < col.size(); k++) {
long long v = col[k] + carry;
res.push_back(char('0' + v % 10));
carry = v / 10;
}
// Đảo ngược và bỏ số 0 đứng đầu
reverse(res.begin(), res.end());
size_t p = res.find_first_not_of('0');
if (p == string::npos) cout << 0 << "\n";
else cout << res.substr(p) << "\n";
return 0;
}
Bình luận