题目:
求两个一元多项式的和。
输入格式:
输入分2行,每行分别先给出多项式非零项的个数,再以指数递降方式输入一个多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。
输出格式:
输出分1行,分别以指数递降方式输出和多项式非零项的系数和指数。数字间以空格分隔,但结尾不能有多余空格。零多项式应输出0 0。
输入样例:
1 2
| 4 3 4 -5 2 6 1 -2 0 3 5 20 -7 4 3 1
|
输出样例:
思路:
求两个一元多项式的和,首先我们可先想这多项式要怎么表示,根据它的特点:由多个”系数+指数”项加减法而来,我们不妨利用一个map来表示一个多项式,将指数作为key,系数作为val,这样做两个多项式加法的时候,直接让同一key的val做加法就好了。代码如下:
代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| #include <bits/stdc++.h>
using namespace std;
int main() { map<int,int,greater<int>> res; int N; cin>>N; for(int i=0;i<N;i++) { int c,e; cin>>c>>e; res[e]=c; } cin>>N; for(int i=0;i<N;i++) { int c,e; cin>>c>>e; res[e]+=c; if(res[e]==0) { res.erase(e); } } if(res.size()==0) { cout<<"0 0"<<endl; return 0; } for(auto it=res.begin();it!=res.end();it++) { if(it!=res.begin()) { putchar(' '); } cout<<it->second<<" "<<it->first; } }
|