当前位置：网站首页>1002 A+B for Polynomials
1002 A+B for Polynomials
2022-08-11 08:52:00 【老顽固也可爱】
1002 A+B for Polynomials
1、大致题意
一定要理解题意！！样例中每行代表一个多项式，每行的第一个数代表该多项式有几项，然后每两个数字分别代表第几项以及它对应的系数。左后将给出的两个多项式相加。
2、基本思路
很自然的想到了用 map来做，key 是次数，value 是系数，想偷懒不用自己管理这个数组，但后面遇到了三个坑。
3、解题过程
3.1 map的相关操作
既然选择用 STL偷懒大法，就一定要记住其中的相关操作，这道题里面主要用到了以下两个。
3.1.1 判断 map的 key 中的值有没有出现过
3.1.1.1 count()函数
count函数用于统计key值在map中出现的次数，map的key不允许重复， 存在返回1，不存在返回0
map.count(key)==0
3.1.1.2 find函数
如果key存在，则find返回key对应的迭代器，如果key不存在， 则find返回尾后迭代器.end()
map.find(key)==map.end()
3.1.2 使得 map按照一定规则排序
这道题里主要是为了使多项式可以降序排列。
3.1.2.1 map按key排序
3.1.2.1.1 map默认按照 key 从小到大排序
map<string,int> hash;
等价于 map<string,int, less<string>> hash;
其他的格式自己推即可，有的编译器会不允许 less<string>>的两个 >>连在一起，记得分开
map<int,double,greater<int> >ma;
3.1.2.1.2 map默认按照 key 从小到大排序
map<string,int, greater<string> > hash;
3.1.2.2 map按value排序
很可惜，按 value 值排序没有直接的方法。
但我们可以把 map 存到 vector 中，再对 vector 进行自定义排序，因为 vector 是可以借助 cmp随意排序的，所以这里以 value 值从小到大排序为例
3.1.2.2.1 写法一
定义 vector的 cmp函数
bool cmp(pair<string,int> a, pair<string, int> b) {
return a.second < b.second;
}
把 map存到 vector中进行排序
map<string,int> m;
m["you"] = 2;
m["we"] = 3;
m["they"] = 1;
vector<pair<string,int> > vec(m.begin(),m.end());
sort(vec.begin(),vec.end(),cmp);
3.1.2.2.2 写法二
遍历 map，把键值对取出来放到一个vector<vector<int>> tmp里面，然后对 tmp排序
vector<vector<int>> tmp;
for (auto x : hash) tmp.push_back({
x.first, x.second});
sort(tmp.begin(), tmp.end(), [](vector<int> a, vector<int> b){
return a[1] > b[1];});
3.1.2.2.3 示例代码
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
using namespace std;
bool cmp(pair<string,int> a, pair<string, int> b) {
return a.second < b.second;
}
int main() {
map<string,int> m;
m["you"] = 2;
m["we"] = 3;
m["they"] = 1;
vector<pair<string,int> > vec(m.begin(),m.end());
sort(vec.begin(),vec.end(),cmp);
cout << "Map 存到 vector 后按 value 从小到大排序" << endl;
for (auto x : vec) cout << x.first << " " << x.second << endl;
return 0;
}
3.1.1.3 第一份代码
#include<iostream>
#include<map>
#include<cmath>
using namespace std;
int K;
map<int,double,greater<int> >ma;
int main() {
ma.clear();
cin>>K;
int a,minn=99999999;
double b;
for(int i=0; i<K; i++) {
cin>>a>>b;
if(ma.count(a)==0) {
ma[a]=b;
minn=min(a,minn);
} else {
ma[a]+=b;
}
}
cin>>K;
for(int i=0; i<K; i++) {
cin>>a>>b;
if(ma.count(a)==0) {
ma[a]=b;
minn=min(a,minn);
} else {
ma[a]+=b;
}
}
cout<<ma.size()<<" ";
for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
if(it->first!=minn) {
cout<<it->first<<" "<<it->second<<" ";
} else {
cout<<it->first<<" "<<it->second<<endl;
}
}
return 0;
}
第一份代码得了15分，对了第一个和第三个用例。
3.2 小数点位数问题
提交完就马上反应过来，没有把 多项式的系数 变成1位小数
3.2.1 I/O的格数处理
不得不讲到一个头文件 #include<iomanip>。
其中 io代表输入输出，manip是 manipulator（操纵器）的缩写（在c++上只能通过输入缩写才有效）。主要是对 cin，cout之类的一些操纵运算子，比如 setfill，setw，setbase，setprecision等等。它是 I/O流控制头文件，就像 C 里面的格式化输出一样。以下是一些常见的控制函数的介绍：
| 控 制 符 | 作 用 |
|---|---|
dec | 设置整数为十进制，相当于"%d" |
hex | 设置整数为十六进制，相当于"%X" |
oct | 设置整数为八进制，相当于"%o" |
setbase(n) | 设置整数为n进制(n=8,10,16) |
setfill(n) | 设置字符填充，n可以是字符常或字符变量 |
setprecision(n) | 设置浮点数的有效数字为n位 |
setw(n) | 设置字段宽度为n位 |
setiosflags(ios::fixed) | 设置浮点数以固定的小数位数显示 |
setiosflags(ios::scientific) | 设置浮点数以科学计数法表示 |
setiosflags(ios::left) | 输出左对齐 |
setiosflags(ios::right) | 输出右对齐 |
setiosflags(ios::skipws) | 忽略前导空格 |
setiosflags(ios::uppercase) | 在以科学计数法输出E与十六进制输出X以大写输出，否则小写。 |
setiosflags(ios::showpos) | 输出正数时显示"+"号 |
setiosflags(ios::showpoint) | 强制显示小数点 |
resetiosflags() | 终止已经设置的输出格式状态，在括号中应指定内容 |
3.2.1 提高二分
在这道题里主要在输出的部分需要注意。
for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
cout<<" "<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second;
}
代码修改之后
#include<iostream>
#include<map>
#include<cmath>
#include<iomanip>
using namespace std;
int K;
map<int,double,greater<int> >ma;
int main() {
ma.clear();
int a,minn=99999999;
double b;
cin>>K;
for(int i=0; i<K; i++) {
cin>>a>>b;
if(ma.count(a)==0) {
ma[a]=b;
minn=min(a,minn);
} else {
ma[a]+=b;
}
}
cin>>K;
for(int i=0; i<K; i++) {
cin>>a>>b;
if(ma.count(a)==0) {
ma[a]=b;
minn=min(a,minn);
} else {
ma[a]+=b;
}
}
if((int)ma.size()==0) {
cout<<0<<endl;
} else {
cout<<ma.size()<<" ";
for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
if(it->first!=minn) {
cout<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second<<" ";
} else {
cout<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second<<endl;
}
}
}
return 0;
}
提高了两分
成功增加了两分。
3.3 本题的天坑
还有一个坑在于如果你输入的用例是
1 1 -1
1 1 1
按照上一份代码，系数为零也会输出，同时多项式的数量也不对，导致错误。
#include<iostream>
#include<map>
#include<cmath>
#include<iomanip>
using namespace std;
int K;
map<int,double,greater<int> >ma;
int main() {
// while(1) {
ma.clear();
int a;
double b;
cin>>K;
for(int i=0; i<K; i++) {
cin>>a>>b;
if(ma.count(a)==0&&b!=0) {
ma[a]=b;
} else {
ma[a]+=b;
}
}
cin>>K;
for(int i=0; i<K; i++) {
cin>>a>>b;
if(ma.count(a)==0&&b!=0) {
ma[a]=b;
} else {
ma[a]+=b;
}
}
for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
if(it->second==0){
ma.erase(it);
}
}
if((int)ma.size()==0) {
cout<<0<<endl;
} else {
cout<<ma.size();
for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
cout<<" "<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second;
}
cout<<endl;
}
// }
return 0;
}
出现段错误，又是 .size()、.end()函数上的问题，在 1001 中遇到过。
3.4 AC代码
#include<iostream>
#include<map>
#include<cmath>
#include<iomanip>
using namespace std;
int K;
map<int,double,greater<int> >ma;
int main() {
ma.clear();
int a;
double b;
cin>>K;
for(int i=0; i<K; i++) {
cin>>a>>b;
if(ma.count(a)==0&&b!=0) {
ma[a]=b;
} else {
ma[a]+=b;
}
}
cin>>K;
for(int i=0; i<K; i++) {
cin>>a>>b;
if(ma.count(a)==0&&b!=0) {
ma[a]=b;
} else {
ma[a]+=b;
}
}
for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end();) {
if(it->second==0){
ma.erase(it++);
}else{
++it;
}
}
if(ma.empty()) {
cout<<0<<endl;
} else {
cout<<ma.size();
for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
cout<<" "<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second;
}
cout<<endl;
}
return 0;
}
边栏推荐
- UNITY gameobject代码中setacvtive(false)与面板中直接去掉勾 效果不一样
- Detailed Explanation of the Level 5 Test Center of the Chinese Institute of Electronics (1)-string type string
- Features of LoRa Chips
- Filesystem Hierarchy Standard
- JUC Concurrent Programming
- Design of Cluster Gateway in Game Server
- 剑指offer专项突击版第26天
- 一根网线两台电脑传输文件
- 企业服务器主机加固现状分析
- Birth of the Go language
猜你喜欢
企业服务器主机加固现状分析
基于 VIVADO 的 AM 调制解调（3）仿真验证
tensorflow 基础操作1(tensor 基本属性 ， 维度变换，数学运算)
excel将数据按某一列值分组并绘制分组折线图
OAuth Client默认配置加载
关于架构的认知
js将table生成excel文件并去除表格中的多余tr（js去除表格中空的tr标签）
The no-code platform helps Zhongshan Hospital build an "intelligent management system" to realize smart medical care
机器学习（三）多项式回归
mysql数据查询因为查询的时间跨度过大导致cup爆满应该怎么办
随机推荐
《价值》读书与投资
Kotlin算法入门求完全数
Linux，Redis中IOException: 远程主机强迫关闭了一个现有的连接。解决方法
剑指offer专项突击版第26天
专题讲座8 字符串(一) 学习心得
2022年值得关注的NFT发展趋势
Nuget can't find the package problem
Filesystem Hierarchy Standard
框架外的PHP读取.env文件（php5.6、7.3可用版）
Inventorying Four Entry-Level SSL Certificates
VoLTE基础自学系列 | 3GPP规范解读之Rx接口（上集）
Detailed Explanation of the Level 5 Test Center of the Chinese Institute of Electronics (1)-string type string
opengauss创建用户权限问题
基于 VIVADO 的 AM 调制解调（3）仿真验证
redis模拟面试
UNITY gameobject代码中setacvtive(false)与面板中直接去掉勾 效果不一样
[C语言] sscanf如何实现sscanf_s?
Getting Started with Kotlin Algorithm to Calculate the Number of Daffodils
Nuget找不到包的问题处理
基于 VIVADO 的 AM 调制解调（2）工程实现