c++ - 为什么我的代码在 SPOJ 上因数字总和问题出现段错误?
问题描述
当我针对这个问题在 spoj 上提交 dp 问题的解决方案时,我总是遇到段错误。但我的解决方案适用于其他平台,如 Visual Studio 和 Ideone。我不知道为什么我会收到这个错误,你能帮忙吗?
我的代码:
#include <iostream>
#include <cmath>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <iomanip>
#include <assert.h>
#include <vector>
#include <cstring>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <set>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <climits>
#include <cctype>
#include <bitset>
#include <numeric>
#include <array>
#include <tuple>
#include <stdexcept>
#include <utility>
#include <functional>
#include <locale>
#define mp make_pair
#define pb push_back
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define sz size()
#define len length()
#define vi vector<int>
#define vll vector<ll>
#define vs vector<string>
#define all(v) ((v).begin()), ((v).end())
#define mms(Arr, Value) memset(Arr, Value, sizeof(Arr))
#define printl(ans) cout << ans << endl
#define vpii vector<pair<int, int> >
#define vpll vector<pair<ll, ll> >
#define pll pair<ll, ll>
#define re return
#define fri(x,n) for(int i = x ; i < n ; ++i)
#define frj(x,n) for(int j = x ; j < n ; ++j)
typedef long long int ll;
const int oo = INT_MAX;
const ll OO = 1e18;
using namespace std;
ll GCD(ll a, ll b) { return((!b) ? a : GCD(b, a % b)); }
ll LCM(ll a, ll b) { return a / (GCD(a, b)) * b; }
bool isPrime(ll n) {
if (n == 2)re 1;
if (n < 2 || n % 2 == 0)re 0;
for (ll i = 3; i * i <= n; i += 2)
if (n % i == 0)re 0;
re 1;
}
// take it as string
string a, b;
int ar[11];
ll dp[11][100][2]; // if max input is 1e9, so max pos is 10 and max sum of a one number is 9*9.. did not put a dimension for n as it is constant for all states
ll fun(int pos, ll sum, int flag, int n) {
if (pos > n) re dp[pos][sum][flag] = sum;
if (dp[pos][sum][flag] != -1) re dp[pos][sum][flag];
// if flag is 0 then this state is limited by ar[pos] value.
int limit = 9;
if (flag == 0) limit = ar[pos];
// determine next state: put next flag not limited (1) when curr flag is not limited (1) OR i is still under (smaller than) limit
// put next flag limited (0) when curr flag is limited AND i equals the limit .. you can NOT put OR as : the flag of curr state may be limited but the next state
// would be limited only if i==limit, as if i<limit the next state is always free whether flag is 1 or 0.
// if i==limit, the next state would only be limited if flag is 0. as if curr flag was free so limit of curr state was 9 and now i is 9, the next state can not be limited because flag is 1 even if i==limit.. so you must put them both !flag , i==limit and you must put AND
ll res = 0;
fri(0, limit + 1) {
if (!flag && i == limit)
res += fun(pos + 1, sum + i, 0, n); // limited
else
res += fun(pos + 1, sum + i, 1, n); // free
}
re dp[pos][sum][flag] = res;
}
int NumDigitSum(string s) {
// takes the num as string and return the sum of its digits
int sum = 0;
fri(0, s.sz) {
sum += s[i] - '0';
}
re sum;
}
int main() {
IO;
cin >> a >> b;
while (a != "-1") {
mms(dp, -1);
// ar is one indexed
fri(1, a.sz + 1) {
ar[i] = a[i - 1] - '0'; // convert to int
}
ll aans = fun(1, 0, 0, a.sz);
mms(dp, -1);
// ar is one indexed
fri(1, b.sz + 1) {
ar[i] = b[i - 1] - '0'; // convert to int
}
ll bans = fun(1, 0, 0, b.sz);
cout << bans - aans + NumDigitSum(a) << endl;
cin >> a >> b;
}
return 0;
}
解决方案
好吧,这种用勺子喂食是非常不鼓励的,但我来了:
#include <iostream>
#include <string>
//number of headers = 3
//no use of using namespace std;
int main() {
int n = 100;
long sum = 0;
for (int i = 1; i <= n; i++) {
std::string num_as_string = std::to_string(i);
for(const auto& digit_as_char : num_as_string) {
sum = sum + digit_as_char - '0';
}
}
std::cout << sum;
return 0;
}
注意代码中的一些内容:
- 它简短而简洁
- 它使用标准字符串库来分隔数字,这比自定义逻辑要好得多
- 它的可读性很强,不会让任何人紧张
推荐阅读
- java - 为什么我的 Java 文件中的 Python exec 脚本返回一个空的 InputStream?
- java - SQLite:从日期获取周数
- android - 如何更改我的活动开始的顺序?
- python - 为 debian 打包时覆盖 python 参数
- java - java新手:得到意外的输出
- c# - RestSharp C# JsonDeserializer to List 将对象属性值设为空
- javascript - 您将如何比较两个数组并在两个数组之间进行过滤?
- c# - 从抽象类字段继承的类被神秘地覆盖
- javascript - Formik 测试错误:初始化 React 时定义了“document”全局,但不再定义
- mongodb - Mongoose findOneAndUpdate:更新对象数组中的一个对象