PAT甲级 1009 Product of Polynomials (25 分)

1009 Product of Polynomials (25 分) PAT甲级训练，由于题目格式问题就不复制了= =很难受，只给出输入输出和题目大意 这是题目的地址 Sample Input:

2 1 2.4 0 3.2 2 2 1.5 1 0.5

Sample Output:

3 3 3.6 2 6.0 1 1.6

题目大意： 给两行数 每行都是多项式 格式为：

n个数 系数1 值1 系数2 值2 … 系数n 值n

类似于这样的2行 让你输出相乘后一共有多少个从大到小排序的系数和对应的非0的值 也就是说如果值是0 那么就跳过（巨大天坑 ） 我这次写了两版代码，第一版是用结构体指针做的（只是为了试试new，放弃使用malloc了 ）第二版掌握了一下黑科技find函数和结构体符号重载

先看比较完美的第二版吧！

#include <bits/stdc++.h> const int maxn=5e5+10; const int mod=1e9+7; #define INF 2147483647 #define PI atan(1)*4 #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define pb push_back #define ss(a) scanf("%s",&a) #define sc(a) scanf("%d",&a) #define scc(a,b) scanf("d",&a,&b) #define sccc(a,b,c) scanf("d%d",&a,&b,&c) using namespace std; typedef struct node Node; struct node { int base;//系数 double val;//值 //重载==符号，让find函数查找时只判断系数 bool operator ==(const int & pos) { return(this->base==pos); } }; //定义比较函数，按系数从大到小排 int cmp(node s1,node s2) { return (s1.base)>(s2.base); } vector <node> v1,v2,v3; vector<Node>::iterator it; int n,a,b,t; //定义可复用的input 函数，传引用进行操作 void input(vector <node> & v) { cin>>n; while(n--) { Node x; cin>>x.base>>x.val; v.push_back(x); } } int main() { input(v1); input(v2); int m1=v1.size(); int m2=v2.size(); int re=0; for(int i=0;i<m1;i++) { for(int j=0;j<m2;j++) { Node x; x.base=v1[i].base+v2[j].base;//系数相加 x.val=v1[i].val*v2[j].val;//值相乘 //用find函数查找是否存在，抛弃for循环，增加代码可读性 it=find(v3.begin(),v3.end(),x.base); if(it!=v3.end()) { //distance函数计算两个指针之间的距离，如果直接相减那么你得用it去减掉begin(),因为要内存地址大的减小的... v3[distance(v3.begin(),it)].val+=x.val; //判断v2是否有值是0的存在,因为一旦等于0了后面乘什么都是0了...（裂开不是吗）删掉它就行 if(v3[distance(v3.begin(),it)].val==0.0)v3.erase(it); } else { //这里是判断v1是否有值是0，从源头扼死！！！（虽然题目样例并没有v1里面等于0的情况） if(x.val!=0.0) v3.push_back(x); } } } int tt=v3.size(); sort(v3.begin(),v3.end(),cmp);//排序 cout<<tt; for(int i=0;i<tt;i++) { if(v3[i].val!=0.0)printf(" %d %.1f",v3[i].base,v3[i].val); } return 0; }

第二版相比于第一版：

用结构体替换了结构体指针，让代码可读性更好了。把for循环换成了效率更好、而且使用方便（可惜要重载符号 ）的find，这个find不是vector自带的方法，而是algorithm头文件里面带的函数。会调用对象的 “ == ”符号，如果找到了就返回对应位置的迭代器，没找到就返回对象的尾指针（尾指针是整个对象内存地址的后一位，所以它其实是个野指针。。很危险。。）因为结构体指针就算你重载了符号也无法用find查找vector，毕竟你存的是指针…重载的是结构体，和我指针有什么关系（你抓鲁迅和我周树人有什么关系 ）用了黑科技distance函数，因为distance会直接返回两个指针的距离，你也就不用判断内存地址谁靠前了。否则就必须用这里找到的迭代器(it)去减vetcor头了(v3.begin())。详细可以去看我的lower_bound详解 解释了指针减指针是返回啥，这是地址超链接 最后稍微演习了一些传地址函数 （其实比赛里面没啥用，就是看着帅 ）

那么再贴一下之前用结构体指针做的垃圾代码（各种for循环，难看的要死）

#include <bits/stdc++.h> const int maxn=5e5+10; const int mod=1e9+7; #define INF 2147483647 #define PI atan(1)*4 #define ll long long #define CL(a,b) memset(a,b,sizeof(a)) #define pb push_back #define ss(a) scanf("%s",&a) #define sc(a) scanf("%d",&a) #define scc(a,b) scanf("d",&a,&b) #define sccc(a,b,c) scanf("d%d",&a,&b,&c) using namespace std; typedef struct node * Node; struct node { int base; double val; }; int cmp(Node s1,Node s2) { return (s1->base)>(s2->base); } vector <Node> v1; vector <Node> v2; vector <Node> v3; int n,a,b,t; int main() { cin>>n; while(n--) { Node x=new node; cin>>x->base>>x->val; v1.push_back(x); } cin>>n; while(n--) { Node x=new node; cin>>x->base>>x->val; v2.push_back(x); } int m1=v1.size(); int m2=v2.size(); int re=0; for(int i=0;i<m1;i++) { for(int j=0;j<m2;j++) { Node x=new node; x->base=v1[i]->base+v2[j]->base; x->val=v1[i]->val*v2[j]->val; int flag=1; for(int k=0;k<v3.size();k++) { if((v3[k]->base)==(x->base)) { (v3[k]->val)+=(x->val); flag=0; break; } } if(flag)v3.push_back(x); } } for(int k=0;k<v3.size();k++) if(v3[k]->val==0.0)re++; sort(v3.begin(),v3.end(),cmp); cout<<v3.size()-re; int tt=v3.size(); for(int i=0;i<tt;i++) { if(v3[i]->val!=0.0)printf(" %d %.1f",v3[i]->base,v3[i]->val); } return 0; }