Time Limit: 1000MS Memory Limit: 65536KB Submit Statistic Discuss Problem Description
给你多个二元多项式和一个操作符，让你输出操作符操作这些二元多项式之后的结果。 Input
首先输入二元多项式的个数n和操作符号（‘+’，‘*’）； 后面n行输入每一个多项式。 多组输入，当n=0的时候结束输入。 （n<5,二元多项式的长度小于1000，二元多项式都是由x，y，^,数字，’+’组成的） Output
输出操作之后的结果。 （输出的顺序按照：x^2>x>xy^2>xy>y^2>y>常数） Example Input
2 + 3x+4y^2+3xy+6x^10y^2+1 2x+6y 0 Example Output
6x^10y^2+5x+3xy+4y^2+6y+1 Hint
Author
zp
时间过得真的是很快，转眼之间，暑假集训就已经两个周了，每天都是忙忙碌碌的，但是，心里是很开心的。 有一种题目，在你的心里，是一直都有印象的，我会觉得，我能记它一辈子，dqds曾经告诉我，你绝对记不住，以后你还会遇见更多的题目，真的记不住的~ 其实，我很想说，我会记住的，可能就只记得他是一个什么类型的题目，也可能连类型都忘记了，但是，我就是知道~因为，我记住的或许不是题目本身，而是做这道题目的时候的心情，做题时的热情，很难想像，我以后会干什么，但是，这种青春时候的心情，真的是一辈子都不会忘记的！（我记得我说过，那一道题目，我会记一辈子，记得吗？！余弦，我记得） 我想说，这道题目，我也会记一辈子的，二元多项式~~~
AC代码： 有注释，一步步很好理解~
如果觉得烦琐，后面有没有注释的代码~
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; #define MAXN 12 struct node { int x;//存储x的指数 int y;//存储y的指数 int num;//存储系数 struct node *next;//指针域，指向下一个 }t[MAXN];//链表头结点 char str[12121];//输入的表达式 struct node * Creat()//初始化函数 { //定义一个链表的节点，初始化，并返回 struct node * p; p = new struct node; p->next = NULL; p->x = 0; p->y = 0; p->num = 0; return p; }; void Build(struct node * root)//建立链表 { struct node * p;//链表节点 int len , data, ans; p = Creat();//初始化 len = strlen(str);//表达式的长度 data = 0; ans = 1; for(int i=len-1;i>=0;i--)//从后向前遍历表达式 { if(str[i]>='0'&&str[i]<='9')//如果是数字的话，记录下来 { data = (str[i]-'0')*ans+data;//data是十进制的数（不是字符） ans *= 10;//表示现在是在哪位（个，十，百） } else if(str[i]=='x') { if(data)//如果data存在，也就是现在x是多少次方 p->x = data;//p->x存的是x的指数 else p->x = 1;//否则，后面没有数字（从后向前遍历），则，指数为1 data = 0;//清空data ans = 1;//指向各位 } else if(str[i]=='y') { if(data)//如果data存在，也就是现在y是多少次方 p->y = data;//p->y存的是y的指数 else p->y = 1;//否则，后面（从后向前遍历）没有数字，则，指数为1 data = 0;//清空data ans = 1;//指向各位 } else if(str[i]=='+')//出现加号的时候 { if(data)//如果后面（从后向前遍历）有数字，则为这个小的多项式系数 { p->num = data;//p->num存系数 } else if(p->x||p->y)//如果没有系数，并且，有x或y存在的话 { p->num = 1;//系数更新为1 } //逆序建立链表 p->next = root->next; root->next = p; //清空data，ans指向各位 data = 0; ans = 1; p = Creat();//定义并初始化p; } } //出循环之后，字符串的最前面，没有'+'，所以要再次建立 if(data)//如果data存在 { p->num = data;//就是多项式的系数 } else if(p->x||p->y)//如果x或者y存在 { p->num = 1;//系数为1 } //逆序建立链表 p->next = root->next; root->next = p; } void Link(struct node *Root, struct node * root)//两个链表相乘为一个链表 { struct node *p, *q, *temp, *t; temp = Creat();//定义并初始化一个新链表的头节点 p = Root->next;//p指针指向其中一个（下面说第一个）链表的起始点 while(p)//当第一个链表指针没有指向空时 { q=root->next;//q指向第二个链表的起始点 while(q)//当第二个链表指针没有指向空时 { t = Creat();//定义并初始化t t->num = p->num*q->num;//将两个多项式的系数相乘 //同底数幂相乘，底数不变，指数相加 t->x = p->x+q->x;//t->x表示x的指数 t->y = p->y+q->y;//t->y表示y的指数 //将此节点，给了新链表，逆序建立新链表 t->next=temp->next; temp->next = t; //循环继续 q = q->next; } p = p->next; } Root->next = temp->next;//将新链表给了旧链表的头结点 free(temp);//释放空间，将暂时存储新链表的空间释放 } void Sort(struct node * root)//合并多项式中重复的节点 { struct node *p, *q, *temp; p = root->next;//q指向链表的开始 while(p)//当p不为空时 { temp = p;//temp指向p q = p->next;//q指向p的下一个节点 while(q)//当q不为空时 { //如果x的指数，y的指数相等，并且，p的系数存在的话（排除空的情况） if(p->x==q->x&&p->y==q->y&&p->num) { p->num += q->num;//系数相加 temp->next = q->next;//将q节点删除 free(q);//释放空间 q = temp->next;//q指向下一个节点 } else if(p->num==0&&q->num==0)//否则，如果两个节点的系数全部为0 { p->x = 0;//清空节点 p->y = 0; temp->next = q->next; free(q);//释放q空间 q = temp->next; } else//否则的话，不能合并，指向移动 { temp = temp->next; q = q->next; } } p = p->next; } //***********接下来就是按照指数多少排序***********// p=root->next;//p指向链表的开始 while(p)//当p不等于空的时候 { q = p->next;//q指向p的下一个 while(q)//当q不为空的时候 { if(p->x<q->x)//如果p中x的指数小 { //将p, q交换（交换节点内的元素，不变动链表位置） swap(p->x, q->x); swap(p->num, q->num); swap(p->y, q->y); } else if(p->x==q->x&&p->x)//如果p中x的指数和q中y的指数相等，并且不为0 { //接下来比较y的指数大小（此种情况下，可能会没有y） if(q->y==0&&p->y!=0)//如果q中y的指数等于0并且p的指数不等于0 { //交换 swap(p->x, q->x); swap(p->num, q->num); swap(p->y, q->y); } else if(p->y<q->y&&p->y!=0)//否则，如果p中y的指数小于q中y的指数，并且p中y的指数不为0 { //交换 swap(p->x, q->x); swap(p->num, q->num); swap(p->y, q->y); } //当然，其他情况也有，但是不用交换，就忽略 } else if(p->x==q->x&&p->x==0)//如果p中x的指数和q中y的指数相等，并且为0 { //此时，y有指数，也可能为0 if(p->y<q->y) { //如果p中y的指数小，交换 swap(p->x, q->x); swap(p->num, q->num); swap(p->y, q->y); } } q = q->next; } p = p->next; } } void Output(struct node * root)//输出 { struct node * p; p = root->next;//链表的起始点 while(p) { if(p!=root->next)//在每一项，除了最后一项的后面输出‘+’ { printf("+"); } if(p->num)//如果有系数存在 { //若系数为1，并且没有x或者y的存在，不输出 if(p->num!=1||(p->x==0&&p->y==0)) printf("%d", p->num); } else//否则，输出0（没有系数，考虑0的情况） { printf("0"); p = p->next; continue;//继续 } if(p->x)//如果x指数存在 { printf("x");//输出x if(p->x!=1)//如果指数不是1 printf("^%d", p->x);//输出指数（否则，不用输出指数） } if(p->y)//如果y指数存在 { printf("y");//输出y if(p->y!=1)//如果指数不是1 { printf("^%d", p->y);//输出指数（否则，不用输出） } } p = p->next; } printf("\n"); } int main() { int n; char c[2]; while(~scanf("%d",&n)&&n)//0的时候结束 { scanf("%s",c); for(int i=0; i<=n; i++)//初始化，清空 { t[i].next=NULL; } for(int i=1; i<=n; i++) { scanf("%s",str);//输入多项式 Build(&t[i]);//建立链表 } if(c[0]=='+')//判断执行的是加法操作 { struct node *p; p=&t[0]; for(int i=1; i<=n; i++)//合并链表 { p->next=t[i].next;//每一个链表的头结点t[i] while(p->next) { p=p->next; } } } else if(c[0]=='*')//判断执行的是乘法操作 { t[0].next=t[1].next; for(int i=2; i<=n; i++) { Link(&t[0],&t[i]);//链表相乘 } } Sort(&t[0]);//合并链表 Output(&t[0]);//输出 } return 0; } /************************************************ 题目：二元多项式 难度：开始觉得很难，理解之后，觉得还行 目标：记住（一辈子）心情 备注：解释是用自己觉得好理解的语言，可能不规范 *************************************************/无注释：
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <algorithm> using namespace std; #define MAXN 12 struct node { int x; int y; int num; struct node *next; }t[MAXN]; char str[12121]; struct node * Creat() { struct node * p; p = new struct node; p->next = NULL; p->x = 0; p->y = 0; p->num = 0; return p; }; void Build(struct node * root) { struct node * p; int len , data, ans; p = Creat(); len = strlen(str); data = 0; ans = 1; for(int i=len-1;i>=0;i--) { if(str[i]>='0'&&str[i]<='9') { data = (str[i]-'0')*ans+data; ans *= 10; } else if(str[i]=='x') { if(data) p->x = data; else p->x = 1; data = 0; ans = 1; } else if(str[i]=='y') { if(data) p->y = data; else p->y = 1; data = 0; ans = 1; } else if(str[i]=='+') { if(data) { p->num = data; } else if(p->x||p->y) { p->num = 1; } p->next = root->next; root->next = p; data = 0; ans = 1; p = Creat(); } } if(data) { p->num = data; } else if(p->x||p->y) { p->num = 1; } p->next = root->next; root->next = p; } void Link(struct node *Root, struct node * root) { struct node *p, *q, *temp, *t; temp = Creat(); p = Root->next; while(p) { q=root->next; while(q) { t = Creat(); t->num = p->num*q->num; t->x = p->x+q->x; t->y = p->y+q->y; t->next=temp->next; temp->next = t; q = q->next; } p = p->next; } Root->next = temp->next; free(temp); } void Sort(struct node * root) { struct node *p, *q, *temp; p = root->next; while(p) { temp = p; q = p->next; while(q) { if(p->x==q->x&&p->y==q->y&&p->num) { p->num += q->num; temp->next = q->next; free(q); q = temp->next; } else if(p->num==0&&q->num==0) { p->x = 0; p->y = 0; temp->next = q->next; free(q); q = temp->next; } else { temp = temp->next; q = q->next; } } p = p->next; } p=root->next; while(p) { q = p->next; while(q) { if(p->x<q->x) { swap(p->x, q->x); swap(p->num, q->num); swap(p->y, q->y); } else if(p->x==q->x&&p->x) { if(q->y==0&&p->y!=0) { swap(p->x, q->x); swap(p->num, q->num); swap(p->y, q->y); } else if(p->y<q->y&&p->y!=0) { swap(p->x, q->x); swap(p->num, q->num); swap(p->y, q->y); } } else if(p->x==q->x&&p->x==0) { if(p->y<q->y) { swap(p->x, q->x); swap(p->num, q->num); swap(p->y, q->y); } } q = q->next; } p = p->next; } } void Output(struct node * root) { struct node * p; p = root->next; while(p) { if(p!=root->next) { printf("+"); } if(p->num) { if(p->num!=1||(p->x==0&&p->y==0)) printf("%d", p->num); } else { printf("0"); p = p->next; continue; } if(p->x) { printf("x"); if(p->x!=1) printf("^%d", p->x); } if(p->y) { printf("y"); if(p->y!=1) { printf("^%d", p->y); } } p = p->next; } printf("\n"); } int main() { int n; char c[2]; while(~scanf("%d",&n)&&n) { scanf("%s",c); for(int i=0; i<=n; i++) { t[i].next=NULL; } for(int i=1; i<=n; i++) { scanf("%s",str); Build(&t[i]); } if(c[0]=='+') { struct node *p; p=&t[0]; for(int i=1; i<=n; i++) { p->next=t[i].next; while(p->next) { p=p->next; } } } else if(c[0]=='*') { t[0].next=t[1].next; for(int i=2; i<=n; i++) { Link(&t[0],&t[i]); } } Sort(&t[0]); Output(&t[0]); } return 0; }