1002 A+B for Polynomials模拟,多项式相加
1002 A B for Polynomials
0、题目
This time, you are supposed to find A B A B A B where A A A and B B B are two polynomials.
Input Specification:
Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:
K N 1 a N 1 N 2 a N 2 . . . N K a N K K N_1 a_{N_1} N_2 a_{N_2} ... N_K a_{N_K} KN1aN1N2aN2...NKaNK
where K K K is the number of nonzero terms in the polynomial, N i N_i Ni and a N i a_{N_i} aNi ( i = 1 , 2 , ⋯ , K i=1,2,⋯,K i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1 ≤ K ≤ 10 1≤K≤10 1≤K≤10, 0 ≤ N K < ⋯ < N 2 < N 1 ≤ 1000 0≤N_K<⋯<N_2<N_1≤1000 0≤NK<⋯<N2<N1≤1000.
Output Specification:
For each test case you should output the sum of A A A and B B B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.
Sample Input:
2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output:
3 2 1.5 1 2.9 0 3.2
1、大致题意
一定要理解题意!!样例中每行代表一个多项式,每行的第一个数代表该多项式有几项,然后每两个数字分别代表第几项以及它对应的系数。左后将给出的两个多项式相加。
2、基本思路
很自然的想到了用 map
来做,key 是次数,value 是系数,想偷懒不用自己管理这个数组,但后面遇到了三个坑。
3、解题过程
3.1 map
的相关操作
既然选择用 STL
偷懒大法,就一定要记住其中的相关操作,在做这道题前我整理了map的重要操作,这道题里面主要用到了以下两个。
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.2 提高二分
在这道题里主要在输出的部分需要注意。
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 中遇到过。
首先,要是在vector中这样子写是没有问题的,例如:
for(vector<int>::iterator it = vecInt.begin(); it != vecInt.end();) {
if(*it == 0) {
it = vecInt.erase(it);
}
else {
it ;
}
}
从一个 vector 中删除值为 0 的元素,利用了 vector::erase 函数根据 iterator 删除某个元素时会返回下一个元素的 iterator 的性质:http://www.cplusplus.com/reference/vector/vector/erase/
但是 map 并不一样,C 98中 map::erase 并没有返回值为 iterator 的原型函数,那么 it=map.erase(it) 然后对 it 进行操作会发生什么呢?在执行 map.erase(it) 之后,it 这个 iterator 已经失效了,考虑C语言中一个失效释放了的指针,再次引用它会导致段错误,具体可以看http://www.cplusplus.com/reference/map/map/erase/ 上的说明。在循环中正确使用 map::erase 的方法如下:
for(map<int,int>::iterator it = mapInt.begin(); it != mapInt.end();) {
if(it->second == 0) {
mapInt.erase(it );
}
else {
it ;
}
}
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;
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhficjkc
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13