复习了一下 STL, 写完才想起来可以用 map, 代码量 * 3,orz
提交时遇到一次 Presentation Error,OJ 的空格输出实在是太随性.
思路是分别对两组输入进行排序, 再通过 k1,k2 两个迭代器导入新的容器
注意:
容器为空时, begin() 与 end() 返回相同
容器为空与容器不为空时, begin() 返回不一致
需要进行操作的多项式中, 存在 0(即输入仅包含一个系数和一个负项数, 如: 9 -7) 和多组相同幂数的情况 (12 7 -7 5 3 17 23 4 15 10 -10 5 13 5 2 19 9 -7)
- vector<int> a, b;
- vector<int>::const_iterator k1, k2;
- if (a.begin() == a.end()) // 输出 1
- cout <<'1';
- else
- cout << '0';
- if (a.begin() == b.begin()) // 输出 1
- cout << '1';
- else
- cout << '0';
- k1 = a.begin();
- a.push_back(5);
- k2 = a.begin();
- if (k1 == k2) // 输出 0
- cout << '1';
- else
- cout << '0';
- View Code
- #include <iostream>
- #include <algorithm>
- #include <vector>
- using namespace std;
- class poly{ // 多项式类
- public:
- int coe; // 系数
- int item; // 项数
- poly(){}
- poly(int a, int b): coe(a), item(b){}
- friend bool operator <(const poly &, const poly &);
- friend poly operator + (const poly &, const poly &);
- };
- bool operator < (const poly &a, const poly &b){
- if (a.item> b.item)
- return true;
- else
- return false;
- }
- poly operator + (const poly &a, const poly &b){
- return poly(a.coe + b.coe, a.item);
- }
- void insert_num(vector<poly> &x){
- poly tmp;
- int a, b;
- while (cin>> a>> b){
- if (b <0)
- break;
- tmp.coe = a;
- tmp.item = b;
- x.push_back(tmp);
- }
- }
- int main(){
- int n;
- vector<poly> p1, p2, p3;
- vector<poly>::iterator k1, k2, k3;
- cin>> n;
- for (int i = 0; i <n; ++i){
- insert_num(p1);
- insert_num(p2);
- sort(p1.begin(), p1.end());
- sort(p2.begin(), p2.end());
- k1 = p1.begin();
- k2 = p2.begin();
- while (1){
- k3 = p3.end() - 1; // 请勿使用 p3.rbegin(), 对应 reverse_iterator
- if (k1 < p1.end() && k2 < p2.end()){
- if ((*k1).item < (*k2).item){
- if (!p3.empty() && (*k3).item == (*k2).item)
- (*k3) = (*k3) + (*k2);
- else
- p3.push_back(*k2);
- k2++;
- }
- else if ((*k1).item> (*k2).item){
- if (!p3.empty() && (*k3).item == (*k1).item)
- (*k3) = (*k3) + (*k1);
- else
- p3.push_back(*k1);
- k1++;
- }
- else{
- if (!p3.empty() && (*k3).item == (*k2).item)
- (*k3) = (*k3) + (*k2) + (*k1);
- else
- p3.push_back((*k1) + (*k2));
- k1++;
- k2++;
- }
- }
- else if (k1 < p1.end() && k2 == p2.end()){
- while (k1 < p1.end()){
- k3 = p3.end() - 1;
- if (!p3.empty() && (*k3).item == (*k1).item)
- (*k3) = (*k3) + (*k1);
- else
- p3.push_back(*k1);
- k1++;
- }
- }
- else if (k1 == p1.end() && k2 < p2.end()){
- while (k2 < p2.end()){
- k3 = p3.end() - 1;
- if (!p3.empty() && (*k3).item == (*k2).item)
- (*k3) = (*k3) + (*k2);
- else
- p3.push_back(*k2);
- k2++;
- }
- }
- else
- break;
- }
- for (k3 = p3.begin(); k3 < p3.end(); k3++){
- if ((*k3).coe != 0)
- cout << "[" << (*k3).coe << '' << (*k3).item <<" ] ";
- }
- cout << endl;
- p1.clear();
- p2.clear();
- p3.clear();
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3211816.html