好贷网好贷款

SDUT1482——二元多项式

发布时间:2016-12-4 7:50:20 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"SDUT1482——二元多项式",主要涉及到SDUT1482——二元多项式方面的内容,对于SDUT1482——二元多项式感兴趣的同学可以参考一下。

题目链接:  http://acm.sdut.edu.cn/sdutoj/showproblem.php?pid=1482&cid=1180   关键在于对字符串的操作。   两种情况:   ‘+’   此时要把x和y指数均相同的项的系数相加。若链表中不存在系数相同的,则按优先级顺序插入当前项。   ‘*’   把任意两项(不属于同一式子的两项)都要相乘。系数相乘,指数相加。      最后要考虑一下存在 0 的情况。      优先级关系。   x的指数越大优先级越高。   x的指数相同时,比较y。   常数优先级最低。   特例:x > x^ny^m   AC_code    1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <iostream> 5 #include <algorithm> 6 using namespace std; 7 char sen[1010]; 8 struct N 9 { 10 int x1,x2,y1,y2; 11 struct N *next; 12 } mark[1010]; 13 14 N *creat() 15 { 16 N *p = (struct N *)malloc(sizeof(struct N)); 17 p->next = NULL; 18 return p; 19 } 20 21 void insert_mul(N *head,N *p) 22 { 23 p->next = head->next; 24 head->next = p; 25 } 26 27 void insert_add(N *head,N *p) 28 { 29 N *q1 = head; 30 N *q2 = head->next; 31 while(q2 != NULL) 32 { 33 if(q2->x2 == p->x2 && q2->y2 == p->y2) 34 { 35 q2->x1 += p->x1; 36 return ; 37 } 38 if(p->x2 != 0 || p->y2 != 0) 39 { 40 41 if(q2->x2 < p->x2) 42 { 43 break; 44 } 45 else if(q2->x2 == p->x2) 46 { 47 if(p->y2 == 0) 48 break; 49 else if(q2->y2 < p->y2 && ( q2->y2 != 0 || (q2->x2 == 0 && q2->y2 == 0) ) ) 50 break; 51 } 52 } 53 q1 = q1->next; 54 q2 = q2->next; 55 } 56 p->next = q1->next; 57 q1->next = p; 58 } 59 60 int cal(char *s) 61 { 62 int ans,sum,l; 63 for(ans = 1,sum = 0,l = strlen(s) - 1; l >= 0; l--) 64 { 65 sum += ans*(s[l]-'0'); 66 ans *= 10; 67 } 68 return sum; 69 } 70 71 void check_number(char *s,char order,struct N *head) 72 { 73 char num[30]; 74 int mark,top; 75 int ans; 76 int i,l; 77 N *p = creat(); 78 p->x1 = 0; 79 p->x2 = 0; 80 p->y1 = 0; 81 p->y2 = 0; 82 for(mark = 1,ans = 1,i = 0,l = strlen(s),top = 0; i <= l; i++) 83 { 84 if(i != l && '0' <= s[i] && s[i] <= '9') 85 { 86 num[top++] = s[i]; 87 } 88 else 89 { 90 num[top] = '\0'; 91 92 if(top != 0) 93 { 94 if(mark == 1) 95 { 96 p->x1 = cal(num); 97 } 98 else if(mark == 2) 99 { 100 p->x2 = cal(num); 101 } 102 else if(mark == 3) 103 { 104 p->y1 = cal(num); 105 } 106 else if(mark == 4) 107 { 108 p->y2 = cal(num); 109 } 110 } 111 top = 0; 112 if(s[i] == 'y') 113 mark = 3; 114 else if(s[i] == '^') 115 mark++; 116 } 117 } 118 if(p->x2 == 0) 119 { 120 for(i = 0; i < l; i++) 121 { 122 if(s[i] == 'x') 123 { 124 p->x2 = 1; 125 break; 126 } 127 } 128 } 129 if(p->y2 == 0) 130 { 131 for(i = 0; i < l; i++) 132 { 133 if(s[i] == 'y') 134 { 135 p->y2 = 1; 136 break; 137 } 138 } 139 } 140 if(p->x1 == 0) 141 { 142 if(p->x2 != 0 || p->y2 != 0) 143 p->x1 = 1; 144 } 145 if(order == '+') 146 { 147 insert_add(head,p); 148 } 149 else insert_mul(head,p); 150 } 151 152 void analysis(char order,N *head) 153 { 154 int i,l,top; 155 char s[50]; 156 for(top = 0,i = 0,l = strlen(sen); i < l; i++) 157 { 158 if(sen[i] == '+') 159 { 160 s[top] = '\0'; 161 check_number(s,order,head); 162 top = 0; 163 } 164 else 165 { 166 s[top++] = sen[i]; 167 } 168 } 169 s[top] = '\0'; 170 check_number(s,order,head); 171 } 172 173 void output(N *head) 174 { 175 N *p = head->next; 176 bool mark = false; 177 if(p != NULL) 178 { 179 if(p->x2 == 0 && p->y2 == 0 && p->x1 != 0) 180 { 181 cout<<p->x1; 182 mark = true; 183 } 184 else if(p->x1 != 0) 185 { 186 mark = true; 187 if(p->x1 != 1) 188 { 189 cout<<p->x1; 190 } 191 if(p->x2 != 0) 192 { 193 cout<<'x'; 194 } 195 if(p->x2 > 1) 196 { 197 cout<<'^'<<p->x2; 198 } 199 if(p->y2 != 0) 200 { 201 cout<<'y'; 202 } 203 if(p->y2 > 1) 204 { 205 cout<<'^'<<p->y2; 206 } 207 } 208 } 209 else return ; 210 for(p = p->next ; p != NULL; p = p->next) 211 { 212 213 if(p->x2 == 0 && p->y2 == 0 && p->x1 != 0) 214 { 215 mark = true; 216 cout<<'+'; 217 cout<<p->x1; 218 } 219 else if(p->x1 != 0) 220 { 221 mark = true; 222 cout<<'+'; 223 if(p->x1 != 1) 224 { 225 cout<<p->x1; 226 } 227 if(p->x2 != 0) 228 { 229 cout<<'x'; 230 } 231 if(p->x2 > 1) 232 { 233 cout<<'^'<<p->x2; 234 } 235 if(p->y2 != 0) 236 { 237 cout<<'y'; 238 } 239 if(p->y2 > 1) 240 { 241 cout<<'^'<<p->y2; 242 } 243 } 244 } 245 if(mark == false) 246 cout<<0; 247 cout<<endl; 248 } 249 250 void multi(N *head[20],int n) 251 { 252 N *p,*q; 253 int i; 254 255 for(i = 1; i < n; i++) 256 { 257 head[n+i-1] = creat(); 258 259 if(i == 1) 260 { 261 p = head[0]->next; 262 } 263 else p = head[n+i-2]->next; 264 for(; p != NULL; p = p->next) 265 { 266 for(q = head[i]->next; q != NULL; q = q->next) 267 { 268 N *temp = creat(); 269 temp->x1 = q->x1 * p->x1; 270 temp->x2 = q->x2 + p->x2; 271 temp->y1 = 0; 272 temp->y2 = q->y2 + p->y2; 273 insert_add(head[n+i-1],temp); 274 } 275 } 276 } 277 output(head[n+i-2]); 278 } 279 280 int main() 281 { 282 int i,n; 283 char ch; 284 while(cin>>n && n) 285 { 286 N *head[20]; 287 for(i = 0; i < n; i++) 288 { 289 head[i] = creat(); 290 } 291 cin>>ch; 292 293 memset(mark,0,sizeof(mark)); 294 295 for(i = 0; i < n; i++) 296 { 297 cin>>sen; 298 if(ch == '*') 299 { 300 analysis(ch,head[i]); 301 } 302 else analysis(ch,head[0]); 303 } 304 305 if(ch == '+') 306 { 307 output(head[0]); 308 } 309 else if(ch == '*') 310 { 311 multi(head,n); 312 } 313 } 314 return 0; 315 } View Code  

上一篇:SDUT—2057 模拟题
下一篇:1.WaitForSingleObject 的用法

相关文章

相关评论