有人能帮我看看是哪里错了么？ 跟我的一样的问题，把sum改成long long int 就可以
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct Interval { int L; int U; }; uint64_t add_interval(const vector<int> &vec, int begin, int end) { uint64_t sum = 0; for (int i = begin; i <= end; ++i) sum += vec[i]; return sum; } int main() { int T; cin >> T; for (int z = 0; z < T; ++z) { int n, m; cin >> n >> m; vector<int> vec(n); for (auto &i : vec) cin >> i; vector<Interval> ivec(m); for (auto &i : ivec) cin >> i.L >> i.U; vector<int> count; for (int add_incr = 0; add_incr < vec.size(); ++add_incr) for (int i = 0; i + add_incr < vec.size(); ++i) count.push_back(add_interval(vec, i, i + add_incr)); sort(count.begin(), count.end()); cout << "case #" << z << ":" << endl; for (const auto &i : ivec) cout << add_interval(count, i.L - 1, i.U - 1) << endl; } return 0; }
粗略看下数据范围，1000^2 级别个 100 以内的数相加得到 1e8 级别的数据共 1000^2 个，再求和得到的数据范围在 1e14 左右。这个超出了 int32_t 的范围，但是对 int64_t 而言绰绰有余。
int32_t
int64_t
这题是一道典型的前缀和习题吧。前缀和 pre_sum[i] 指的是数组 arr 在 0..i 区间里（老规矩，左闭右开）元素的和。C++ 标准库 <numeric> 中提供了这个函数 partial_sum（在标准里叫作「部分和」）。这其实就是记录下和，空间换时间的思想，不是很难，但是挺有意思的。
pre_sum[i]
arr
0..i
<numeric>
partial_sum
#include "bits/stdc++.h" using namespace std; using u64 = uint64_t; int main() { u64 t; cin >> t; for (u64 query = 0; query < t; ++query) { cout << "case #" << query << ":\n"; u64 n, m; cin >> n >> m; vector<u64> orig_arr(n); for (auto &i : orig_arr) { cin >> i; } vector<u64> orig_pre_sum(n + 1); orig_pre_sum[0] = 0; partial_sum(begin(orig_arr), end(orig_arr), next(begin(orig_pre_sum))); vector<u64> new_arr; new_arr.reserve(n * (n + 1) / 2); for (u64 i = 0; i < n; ++i) { for (u64 j = i + 1; j <= n; ++j) { new_arr.push_back(orig_pre_sum[j] - orig_pre_sum[i]); } } sort(new_arr.begin(), new_arr.end()); vector<u64> new_pre_sum(new_arr.size() + 1); new_pre_sum[0] = 0; partial_sum(begin(new_arr), end(new_arr), next(begin(new_pre_sum))); for (u64 i = 0; i < m; ++i) { u64 lo, hi; cin >> lo >> hi; cout << new_pre_sum[hi] - new_pre_sum[lo - 1] << '\n'; } } }
有人能帮我看看是哪里错了么？ 计算结果int无法正确表示
有人能帮我看看是哪里错了么？
int cmp(const voida,const voidb) { return (int)a-(int)b; } void slove(inta,ints,int n) { int i,j=0,k; for(i=0;i<n;i++) { s[j]=a[i],j++; for(k=i+1;k<n;k++) { s[j]=s[j-1]+a[k]; j++; } } qsort(s,j,sizeof(s[0]),cmp); // for(i=0;i<j;i++)printf(“%d “,s[i]);printf(“\n”); } int main() { int t,cas; int m,n,i,a[1001],l[32],u[32],s[500501]; int sum,j; scanf(“%d”,&cas); for(t=0;t<cas;t++) { scanf(“%d%d”,&n,&m); for(i=0;i<n;i++) { scanf(“%d”,&a[i]); } for(i=0;i<m;i++) { scanf(“%d%d”,&l[i],&u[i]); } printf(“case #%d:\n”,t); slove(a,s,n); for(i=0;i<m;i++) { sum=0; for(j=l[i]-1;j<u[i];j++) sum+=s[j]; printf(“%d\n”,sum); } } return 0; }
有人能帮我看看是哪里错了么？
跟我的一样的问题，把sum改成long long int 就可以
粗略看下数据范围，1000^2 级别个 100 以内的数相加得到 1e8 级别的数据共 1000^2 个，再求和得到的数据范围在 1e14 左右。这个超出了
int32_t的范围，但是对int64_t而言绰绰有余。这题是一道典型的前缀和习题吧。前缀和
pre_sum[i]指的是数组arr在0..i区间里（老规矩，左闭右开）元素的和。C++ 标准库<numeric>中提供了这个函数partial_sum（在标准里叫作「部分和」）。这其实就是记录下和，空间换时间的思想，不是很难，但是挺有意思的。有人能帮我看看是哪里错了么？
计算结果int无法正确表示
有人能帮我看看是哪里错了么？
include
include
int cmp(const voida,const voidb)
{
return (int)a-(int)b;
}
void slove(inta,ints,int n)
{
int i,j=0,k;
for(i=0;i<n;i++)
{
s[j]=a[i],j++;
for(k=i+1;k<n;k++)
{
s[j]=s[j-1]+a[k];
j++;
}
}
qsort(s,j,sizeof(s[0]),cmp);
// for(i=0;i<j;i++)printf(“%d “,s[i]);printf(“\n”);
}
int main()
{
int t,cas;
int m,n,i,a[1001],l[32],u[32],s[500501];
int sum,j;
scanf(“%d”,&cas);
for(t=0;t<cas;t++)
{
scanf(“%d%d”,&n,&m);
for(i=0;i<n;i++)
{
scanf(“%d”,&a[i]);
}
for(i=0;i<m;i++)
{
scanf(“%d%d”,&l[i],&u[i]);
}
printf(“case #%d:\n”,t);
slove(a,s,n);
for(i=0;i<m;i++)
{
sum=0;
for(j=l[i]-1;j<u[i];j++)
sum+=s[j];
printf(“%d\n”,sum);
}
}
return 0;
}