1002 A+B for Polynomials

1、大致题意

一定要理解题意！！样例中每行代表一个多项式，每行的第一个数代表该多项式有几项，然后每两个数字分别代表第几项以及它对应的系数。左后将给出的两个多项式相加。

2、基本思路

很自然的想到了用 map来做，key 是次数，value 是系数，想偷懒不用自己管理这个数组，但后面遇到了三个坑。

3、解题过程

3.1 map的相关操作

既然选择用 STL偷懒大法，就一定要记住其中的相关操作，这道题里面主要用到了以下两个。

3.1.1 判断 map的 key 中的值有没有出现过

3.1.1.1 count()函数

count函数用于统计key值在map中出现的次数，map的key不允许重复， 存在返回1，不存在返回0

map.count(key)==0
1

3.1.1.2 find函数

如果key存在，则find返回key对应的迭代器，如果key不存在， 则find返回尾后迭代器.end()

map.find(key)==map.end()
1

3.1.2 使得 map按照一定规则排序

这道题里主要是为了使多项式可以降序排列。

3.1.2.1 map按key排序

3.1.2.1.1 map默认按照 key 从小到大排序

 map<string,int> hash;
 等价于 map<string,int, less<string>> hash;
1
2

其他的格式自己推即可，有的编译器会不允许 less>的两个 >>连在一起，记得分开

map<int,double,greater<int> >ma;
1

3.1.2.1.2 map默认按照 key 从小到大排序

map<string,int, greater<string> > hash;
1

3.1.2.2 map按value排序

很可惜，按 value 值排序没有直接的方法。

但我们可以把 map 存到 vector 中，再对 vector 进行自定义排序，因为 vector 是可以借助 cmp随意排序的，所以这里以 value 值从小到大排序为例

3.1.2.2.1 写法一

定义 vector的 cmp函数

bool cmp(pair<string,int> a, pair<string, int> b) {
    return a.second < b.second;
}
1
2
3

把 map存到 vector中进行排序

map<string,int> m;
m["you"] = 2;
m["we"] = 3;
m["they"] = 1;

vector<pair<string,int> > vec(m.begin(),m.end());
sort(vec.begin(),vec.end(),cmp);
1
2
3
4
5
6
7

3.1.2.2.2 写法二

遍历 map，把键值对取出来放到一个vector> tmp里面，然后对 tmp排序

vector<vector<int>> tmp;
for (auto x : hash) tmp.push_back({x.first, x.second});
sort(tmp.begin(), tmp.end(), [](vector<int> a, vector<int> b){return a[1] > b[1];});
1
2
3

3.1.2.2.3 示例代码

#include 
#include 
#include 
#include 
using namespace std;

bool cmp(pair<string,int> a, pair<string, int> b) {
    return a.second < b.second;
}

int main() {
    map<string,int> m;
    m["you"] = 2;
    m["we"] = 3;
    m["they"] = 1;
  
    vector<pair<string,int> > vec(m.begin(),m.end());
    sort(vec.begin(),vec.end(),cmp);
    
    cout << "Map 存到 vector 后按 value 从小到大排序" << endl;
    for (auto x : vec) cout << x.first << " " << x.second << endl;

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

3.1.1.3 第一份代码

#include
#include
#include
using namespace std;
int K;
map<int,double,greater<int> >ma;

int main() {
	ma.clear();
	cin>>K;
	int a,minn=99999999;
	double b;

	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma.count(a)==0) {
			ma[a]=b;
			minn=min(a,minn);
		} else {
			ma[a]+=b;
		}
	}
	cin>>K;
	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma.count(a)==0) {
			ma[a]=b;
			minn=min(a,minn);
		} else {
			ma[a]+=b;
		}
	}
	cout<<ma.size()<<" ";
	for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
		if(it->first!=minn) {
			cout<<it->first<<" "<<it->second<<" ";
		} else {
			cout<<it->first<<" "<<it->second<<endl;
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

第一份代码得了15分，对了第一个和第三个用例。

3.2 小数点位数问题

提交完就马上反应过来，没有把 多项式的系数 变成1位小数

3.2.1 I/O的格数处理

不得不讲到一个头文件 #include。

其中 io代表输入输出，manip是 manipulator（操纵器）的缩写（在c++上只能通过输入缩写才有效）。主要是对 cin，cout之类的一些操纵运算子，比如 setfill，setw，setbase，setprecision等等。它是 I/O流控制头文件，就像 C 里面的格式化输出一样。以下是一些常见的控制函数的介绍：

3.2.1 提高二分

在这道题里主要在输出的部分需要注意。

for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
    cout<<" "<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second;
}
1
2
3

代码修改之后

#include
#include
#include
#include
using namespace std;
int K;
map<int,double,greater<int> >ma;

int main() {
	ma.clear();
	int a,minn=99999999;
	double b;
	cin>>K;
	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma.count(a)==0) {
			ma[a]=b;
			minn=min(a,minn);
		} else {
			ma[a]+=b;
		}
	}
	cin>>K;
	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma.count(a)==0) {
			ma[a]=b;
			minn=min(a,minn);
		} else {
			ma[a]+=b;
		}
	}
	if((int)ma.size()==0) {
		cout<<0<<endl;
	} else {
		cout<<ma.size()<<" ";
		for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
			if(it->first!=minn) {
				cout<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second<<" ";
			} else {
				cout<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second<<endl;
			}
		}
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

提高了两分

成功增加了两分。

3.3 本题的天坑

还有一个坑在于如果你输入的用例是

1 1 -1
1 1 1
1
2

按照上一份代码，系数为零也会输出，同时多项式的数量也不对，导致错误。

#include
#include
#include
#include
using namespace std;
int K;
map<int,double,greater<int> >ma;

int main() {
//	while(1) {
	ma.clear();
	int a;
	double b;
	cin>>K;
	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma.count(a)==0&&b!=0) {
			ma[a]=b;
		} else {
			ma[a]+=b;
		}
	}
	cin>>K;
	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma.count(a)==0&&b!=0) {
			ma[a]=b;
		} else {
			ma[a]+=b;
		}
	}
	for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
		if(it->second==0){
			ma.erase(it);
		}
	}
	if((int)ma.size()==0) {
		cout<<0<<endl;
	} else {
		cout<<ma.size();
		for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
			cout<<" "<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second;
		}
		cout<<endl;
	}
//	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

出现段错误，又是 .size()、.end()函数上的问题，在 1001 中遇到过。

3.4 AC代码

#include
#include
#include
#include
using namespace std;
int K;
map<int,double,greater<int> >ma;

int main() {
	ma.clear();
	int a;
	double b;
	cin>>K;
	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma.count(a)==0&&b!=0) {
			ma[a]=b;
		} else {
			ma[a]+=b;
		}
	}
	cin>>K;
	for(int i=0; i<K; i++) {
		cin>>a>>b;
		if(ma.count(a)==0&&b!=0) {
			ma[a]=b;
		} else {
			ma[a]+=b;
		}
	}
	for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end();) {
		if(it->second==0){
			ma.erase(it++);
		}else{
			++it;
		}
	}
	if(ma.empty()) {
		cout<<0<<endl;
	} else {
		cout<<ma.size();
		for(map<int,double>::iterator it=ma.begin(); (it)!=ma.end(); it++) {
			cout<<" "<<it->first<<" "<<setiosflags(ios::fixed)<<setprecision(1)<<it->second;
		}
		cout<<endl;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48