1295: 一元多项式乘法

  1 #define bug(x) cout<<#x<<" is "<<x<<endl
  2 #define IO std::ios::sync_with_stdio(0)
  3 #include<bits/stdc++.h>
  4 using namespace std;
  5 #define ll long long
  6 const int N=3e5+10;
  7 
  8 typedef struct LinkNode{
  9     int co;
 10     int ex;
 11     LinkNode *next;
 12 }LinkNode,*LinkList;
 13 
 14 void attach(int co,int ex,LinkNode *&r){
 15     LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
 16     p->co=co;
 17     p->ex=ex;
 18     p->next=NULL;
 19     r->next=p;
 20     r=p;
 21 }
 22 
 23 LinkList mutiply(LinkList L1,LinkList L2){
 24     LinkNode *front=(LinkNode *)malloc(sizeof(LinkNode));
 25     LinkNode *rear=front;
 26     front->next=NULL;
 27     LinkNode *r1=L1->next;
 28     LinkNode *r2=L2->next;
 29     while(r1){
 30         rear=front;
 31         while(r2){
 32             int co=r1->co*r2->co;
 33             int ex=r1->ex+r2->ex;
 34             while(rear->next&&ex>rear->next->ex){
 35                 rear=rear->next;
 36             }
 37             if(rear->next&&ex==rear->next->ex){
 38                 if(co+rear->co==0){
 39                     LinkNode *p=rear->next;
 40                     rear->next=p->next;
 41                     free(p);
 42                 }
 43                 else{
 44                     rear->next->co+=co;
 45                 }
 46             }
 47             else{
 48                 if(co!=0){
 49                     LinkNode *p=(LinkNode *)malloc(sizeof(LinkNode));
 50                     p->co=co;
 51                     p->ex=ex;
 52                     p->next=rear->next;
 53                     rear->next=p;
 54                     rear=rear->next;  
 55                 }
 56                          
 57             }
 58             r2=r2->next;
 59         }
 60         r1=r1->next;
 61         r2=L2->next;
 62         
 63     }
 64     return front;
 65 }
 66 struct node{
 67     int x,y;
 68 }a[N],b[N],c[N];
 69 bool cmp(node p,node q){
 70     return p.y<q.y;
 71 }
 72 int n,m;
 73 int main(){
 74     IO;
 75     LinkList L1,L2;
 76     L1=(LinkList)malloc(sizeof(LinkNode));
 77     L2=(LinkList)malloc(sizeof(LinkNode));
 78     L1->next=NULL;
 79     L2->next=NULL;
 80     LinkNode *r1=L1,*r2=L2;
 81     cin>>n;
 82     for(int i=1;i<=n;i++){
 83         cin>>a[i].x>>a[i].y;
 84     }
 85     sort(a+1,a+1+n,cmp);
 86     int n1=0,g1=0,n2=0,g2=0,g3=0;
 87     for(int i=1;i<=n;i++){
 88         if(i==n){
 89             a[++n1].y=a[i].y;
 90             a[n1].x=g1+a[i].x;
 91             break;
 92         }
 93         if(a[i+1].y==a[i].y){
 94             g1+=a[i].x;
 95         }
 96         else{
 97             a[++n1].y=a[i].y;
 98             a[n1].x=g1+a[i].x;
 99             g1=0;
100         }
101     }
102     for(int i=1;i<=n1;i++){
103         attach(a[i].x,a[i].y,r1);
104     }
105     cin>>m;
106     for(int i=1;i<=m;i++){
107         cin>>b[i].x>>b[i].y;
108     }
109     for(int i=1;i<=m;i++){
110         if(i==m){
111             b[++n2].y=b[i].y;
112             b[n2].x=g2+b[i].x;
113             break;
114         }
115         if (b[i+1].y==b[i].y){
116             g2+=b[i].x;
117         }
118         else{
119             b[++n2].y=b[i].y;
120             b[n2].x=g2+b[i].x;
121             g2=0;
122         }
123     }
124     for(int i=1;i<=n2;i++){
125         attach(b[i].x,b[i].y,r2);
126     }
127     LinkList L3=mutiply(L1,L2);
128     L3=L3->next;
129     int n3=0;
130     while(L3){
131         c[++n3].x=L3->co;
132         c[n3].y=L3->ex;
133         L3=L3->next;
134     }
135     sort(c+1,c+1+n3,cmp);
136 
137     int n4=0;
138 
139     for(int i=1;i<=n3;i++){
140         if(i==n3){
141             c[++n4].y=c[i].y;
142             c[n4].x=g3+c[i].x;
143             break;
144         }
145         if (c[i+1].y==c[i].y){
146             g3+=c[i].x;
147         }
148         else{
149             c[++n4].y=c[i].y;
150             c[n4].x=g3+c[i].x;
151             g3=0;
152         }
153     }
154     for(int i=n4;i>1;i--){
155         cout<<c[i].x<<" "<<c[i].y<<" ";
156     }
157     cout<<c[1].x<<" "<<c[1].y;
158 }
159 
160 /*
161 
162 3
163 1 3 2 2 4 3
164 3
165 1 7 2 6 3 5
166 
167 2
168 3 2
169 3 2
170 2
171 0 2
172 0 1
173 
174 */