突然想起来好久没刷数据结构了,然后打开了PTA……
做到一道好像做过的题,都写到树了链表还是没写上来……
不写题还是不行……
题目
代码
#include<bits/stdc++.h>
using namespace std;
void inputMultinomial(int n,int a[]) //输入多项式
{
for(int i=0;i<n;i++)
cin >> a[i];
}
bool printList(map<int,int,greater<int>> a) //公共打印函数
{
map<int,int>::iterator it=a.begin();
bool flag=false;
if(it->second!=0)
{
cout << it->second << " " << it->first;
flag=true;
}
for(++it;it!=a.end();it++)
{
if(it->second!=0)
{
cout << " " << it->second << " " << it->first;
flag=true;
}
}
return flag;
}
void printMul(map<int,int,greater<int>> a) //这两个plus和mul的打印可以合并,再加一个标志变量就行
{
map<int,int>::iterator it=a.begin();
if(!a.empty()&&printList(a))
cout << endl;
else cout << "0 0" << endl;
}
void printPlus(map<int,int,greater<int>> a)
{
map<int,int>::iterator it=a.begin();
if(!a.empty()&&printList(a))
return;
else cout << "0 0";
}
int main()
{
int a;
cin >> a;
int arrA[2*a];
inputMultinomial(2*a,arrA);
int b;
cin >> b;
int arrB[2*b];
inputMultinomial(2*b,arrB);
map<int,int,greater<int>> mul; //第三个参数标明key的排序
map<int,int,greater<int>> plus;
for(int i=0;i<2*a-1;i+=2)
{
for(int j=0;j<2*b-1;j+=2)
{
mul[arrA[i+1]+arrB[j+1]]+=arrA[i]*arrB[j];
}
}
// TODO:计算加法
for(int i=0;i<2*a-1;i+=2)
plus[arrA[i+1]]+=arrA[i];
for(int i=0;i<2*b-1;i+=2)
plus[arrB[i+1]]+=arrB[i];
//打印乘法
printMul(mul);
//打印加法
printPlus(plus);
}
对于积,用数组不好做(因为是指数处有重复),则可以用字典试
这里补充一个知识点:关于map的第三个参数
- map默认按键从小到大排序,即
map<string,int>
等价于map<string,int,std::less<int>>
- 若要从大到小排序则需传入函数greater,即:
map<string,int,greater<string>>
- 也可以自己定义比较函数
bool compFunc(const string& a, const string& b)
{
return a.compare(b) > 0;
}
map <string, int, decltype(compFunc)*> mapWord3;
//注意*号的存在。比较操作类型必须为函数指针类型