PAT B1049
题目
给定一个正数数列，我们可以从中截取任意的连续的几个数，称为片段。例如，给定数列 { 0.1, 0.2, 0.3, 0.4 }，我们有 (0.1) (0.1, 0.2) (0.1, 0.2, 0.3) (0.1, 0.2, 0.3, 0.4) (0.2) (0.2, 0.3) (0.2, 0.3, 0.4) (0.3) (0.3, 0.4) (0.4) 这 10 个片段。
给定正整数数列，求出全部片段包含的所有的数之和。如本例中 10 个片段总和是 0.1 + 0.3 + 0.6 + 1.0 + 0.2 + 0.5 + 0.9 + 0.3 + 0.7 + 0.4 = 5.0。
输入格式：
输入第一行给出一个不超过 10^5 的正整数 N，表示数列中数的个数，第二行给出 N 个不超过 1.0 的正数，是数列中的数，其间以一个空格分隔。
输出格式：
在一行中输出该序列所有片段包含的数之和，精确到小数点后 2 位。
输入样例：
4
0.1 0.2 0.3 0.4
输出样例：
5.00
尝试：
我的第一眼感觉是一个子集问题，但是它又不是所有的子集，首先打印出所有的子集，根据出现的子集，判断所有子集中，哪些应该存在，哪些不应该存在。
#include <bits/stdc++.h>
using namespace std;
void subsets(vector<double>&arr,vector<double>&path,vector<vector<double> >&res,int k,int n) {
if (k == n) {
return;
}
path.push_back(arr[k]);
res.push_back(path);
subsets(arr, path, res, k + 1, n);
path.pop_back();
subsets(arr, path, res, k + 1, n);
}
int main() {
int n;
cin>>n;
vector<double>arr;
for (int i = 0; i <n ; ++i) {
double t;
cin>>t;
arr.push_back(t);
}
vector<double>path;
vector<vector<double> >res;
subsets(arr,path,res,0,n);
for (int i = 0; i < res.size(); ++i){
for (int j = 0; j <res[i].size() ; ++j) {
cout<<" ["<<res[i][j]<<"] ";
}
cout<<"\n";
}
return 0;
}
在输出里，我们需要的子集使用’#'标记
4
0.1 0.2 0.3 0.4
#[0.1]
#[0.1] [0.2]
#[0.1] [0.2] [0.3]
#[0.1] [0.2] [0.3] [0.4]
[0.1] [0.2] [0.4]
[0.1] [0.3]
[0.1] [0.3] [0.4]
[0.1] [0.4]
#[0.2]
#[0.2] [0.3]
#[0.2] [0.3] [0.4]
[0.2] [0.4]
#[0.3]
#[0.3] [0.4]
#[0.4]
找到了一个规律，如果path为空，你可以随便放入一个元素，如果不为空，你必须放入path刚放进去的元素的后一位元素（即如果path里最新放入的元素为num[i-1],你就只能放num[i],要么就不放）
这里放入元素还需要记录数组下标，所以我这里使用pair，你也可以自己设计一个结构体，或者直接使用数组当作结构体
#include <bits/stdc++.h>
using namespace std;
void
subsets(vector<double> &arr, vector<pair<int, double> > &path,
vector<vector<pair<int, double> > > &res, int k, int n) {
if (k == n) {
return;
}
//如果path为空直接放入
if (path.size() == 0) {
path.push_back(make_pair(k, arr[k]));
res.push_back(path);
subsets(arr, path, res, k + 1, n);
path.pop_back();
subsets(arr, path, res, k + 1, n);
} else {
//如果不为空
if (path[path.size() - 1].first == k - 1) {
path.push_back(make_pair(k, arr[k]));
res.push_back(path);
subsets(arr, path, res, k + 1, n);
path.pop_back();
subsets(arr, path, res, k + 1, n);
}
}
}
int main() {
int n;
cin >> n;
vector<double> arr;
for (int i = 0; i < n; ++i) {
double t;
cin >> t;
arr.push_back(t);
}
vector<pair<int, double> > path;
vector<vector<pair<int, double> > > res;
subsets(arr, path, res, 0, n);
for (int i = 0; i < res.size(); ++i) {
for (int j = 0; j < res[i].size(); ++j) {
cout << " [" << res[i][j].second << "] ";
}
cout << "\n";
}
return 0;
}
4
0.1 0.2 0.3 0.4
[0.1]
[0.1] [0.2]
[0.1] [0.2] [0.3]
[0.1] [0.2] [0.3] [0.4]
[0.2]
[0.2] [0.3]
[0.2] [0.3] [0.4]
[0.3]
[0.3] [0.4]
[0.4]
实现了选择子集功能
初步实现
#include <bits/stdc++.h>
using namespace std;
void
subsets(vector<double> &arr, vector<pair<int, double> > &path,
vector<vector<pair<int, double> > > &res, int k, int n) {
if (k == n) {
return;
}
//如果path为空直接放入
if (path.size() == 0) {
path.push_back(make_pair(k, arr[k]));
res.push_back(path);
subsets(arr, path, res, k + 1, n);
path.pop_back();
subsets(arr, path, res, k + 1, n);
} else {
//如果不为空
if (path[path.size() - 1].first == k - 1) {
path.push_back(make_pair(k, arr[k]));
res.push_back(path);
subsets(arr, path, res, k + 1, n);
path.pop_back();
subsets(arr, path, res, k + 1, n);
}
}
}
int main() {
int n;
cin >> n;
vector<double> arr;
for (int i = 0; i < n; ++i) {
double t;
cin >> t;
arr.push_back(t);
}
vector<pair<int, double> > path;
vector<vector<pair<int, double> > > res;
subsets(arr, path, res, 0, n);
double sum=0;
for (int i = 0; i < res.size(); ++i) {
for (int j = 0; j < res[i].size(); ++j) {
sum+=res[i][j].second;
}
}
std::printf("%.2f",sum);
return 0;
}
提交结果：
内存不够用，需要优化一下代码
初步优化
#include <bits/stdc++.h>
using namespace std;
double check(vector<double> arr, vector<int> path) {
double tmp = 0;
for (int i = 0; i < path.size(); ++i) {
tmp += arr[path[i]];
}
return tmp;
}
void
subsets(vector<double> &arr, vector<int> &path,
double &sum, int k, int n) {
if (k == n) {
return;
}
//如果path为空直接放入
if (path.size() == 0) {
path.push_back(k);
sum += arr[k];
subsets(arr, path, sum, k + 1, n);
path.pop_back();
subsets(arr, path, sum, k + 1, n);
} else {
//如果不为空
if (path[path.size() - 1] == k - 1) {
path.push_back(k);
sum += check(arr, path);
subsets(arr, path, sum, k + 1, n);
path.pop_back();
subsets(arr, path, sum, k + 1, n);
}
}
}
int main() {
int n;
cin >> n;
vector<double> arr;
for (int i = 0; i < n; ++i) {
double t;
cin >> t;
arr.push_back(t);
}
vector<int> path;
double sum = 0;
subsets(arr, path, sum, 0, n);
std::printf("%.2f", sum);
return 0;
}
提交结果：
这下内存没超，时间超了，还得优化，死磕了呀！！！
把数据结构都删掉再试试
#include <bits/stdc++.h>
using namespace std;
void
subsets(vector<double> &arr, int &last_index,
double &sum, double &path_sum, int k, int n) {
if (k == n) {
return;
}
//如果path为空直接放入
if (last_index == -1) {
last_index = k;
path_sum += arr[k];
sum += arr[k];
subsets(arr, last_index, sum, path_sum, k + 1, n);
last_index = -1;
path_sum -= arr[k];
subsets(arr, last_index, sum, path_sum, k + 1, n);
} else {
//如果不为空
if (last_index == k - 1) {
last_index = k;
path_sum += arr[k];
sum += path_sum;
subsets(arr, last_index, sum, path_sum, k + 1, n);
last_index = k - 1;
path_sum -= arr[k];
subsets(arr, last_index, sum, path_sum, k + 1, n);
}
}
}
int main() {
int n;
cin >> n;
vector<double> arr;
for (int i = 0; i < n; ++i) {
double t;
cin >> t;
arr.push_back(t);
}
double sum = 0;
double path_sum = 0;
int last_index = -1;
subsets(arr, last_index, sum, path_sum, 0, n);
std::printf("%.2f", sum);
return 0;
}
提交结果：
最后两个还是没过，超时，感觉自己好弱
再次优化
感觉这种搜索有点难过最后两个样例了，得输入的时候就处理数据，在O(n)内就把数据处理完,这样模拟的应该跑不了的，尝试下数学方法规律
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
double sum = 0;
for (int i = 0; i < n; ++i) {
double t;
cin >> t;
sum += t * (n - i) * (i + 1);//样例从左到右要加(4-i)*(i+1)次 比如用第一个元素从左到右一共用4次 只能向右边片段3次本身一次
//第二个元素前面使用从0开始到4结束使用第二个元素一共使用5次片段 本身用一次 一共六次
}
printf("%.2f", sum);
return 0;
}
提交结果：
没过，绷不住了
查了下，测试点2错误double的精度不够，易产生误差，数据量足够大误差就会被放大直至小数点后2位也不精确。
最终代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long double sum = 0.0;
for (int i = 0; i < n; ++i) {
double t;
cin >> t;
sum += t * (n - i) * (i + 1);//样例从左到右要加(4-i)*(i+1)次 比如用第一个元素从左到右一共用4次 只能向右边片段3次本身一次
//第二个元素前面使用从0开始到4结束使用第二个元素一共使用5次片段 本身用一次 一共六次
}
printf("%.2f",(double) sum);
return 0;
}
提交结果：
文章来源：https://www.toymoban.com/news/detail-431890.html
终于过了！！！ 慢慢加油吧！文章来源地址https://www.toymoban.com/news/detail-431890.html
到了这里，关于PAT B1049的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
