当前位置：网站首页>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;
}
边栏推荐
猜你喜欢
随机推荐
Typescript基本类型---上篇
【实战系列】OpenApi设计规范
Has legal counsel become a tasteless product of law firms?
Openlayers 聚合图、权重聚合图以及聚合图点击事件
JUC Concurrent Programming
观察表情和面部，会发现他有焦虑和失眠的痕迹
设置Vagrant创建的虚拟机名称和内存
mysql数据查询因为查询的时间跨度过大导致cup爆满应该怎么办
jenkins简单使用
法律顾问成了律所鸡肋产品了吗？
Go 语言的诞生
《剑指offer》题解——week3（持续更新）
Getting Started with Kotlin Algorithms Calculating Prime Factors
eureka和consul的区别
Kotlin算法入门求回文数数算法优化二数字生成规则
redis模拟面试
无代码平台助力中山医院搭建“智慧化管理体系”，实现智慧医疗
Machine Learning Summary (2)
MySQL性能调优，必须掌握这一个工具！！！（1分钟系列）
Kotlin算法入门计算素数以及优化