一、题目描述

This time, you are supposed to find A×B where A and B are two polynomials.

Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: $K{N}_1{a}_{N_1}...N_k{a}_{N_k}$ where $K$ is the number of nonzero terms in the polynomial, $N_i$ and $a_{N_i}(i=1,2,...,K)$ are the exponents and coefficients, respectively. It is given that $1\le K\le 10,0\le N_K\le ...\le N_2\le N_1\le 1000$.

​​Output Specification:

For each test case you should output the product of A and B in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate up to 1 decimal place.

Sample Input:

2 1 2.4 0 3.2 2 2 1.5 1 0.5

Sample Output:

3 3 3.6 2 6.0 1 1.6

二、解题思路

这道题的大意就是计算两个多项式乘积，我们依然可以用数组来存储一个多项式的信息，考虑到这里有两个多项式，若分开输入，代码会比较冗长，所以这里选择用一个二维数组来表示这两个多项式，用一个一维数组ans表示最终的数组。为了避免访问到很多不存在的项，我们可以建立一个vector存放系数不为零的项对应的指数（也即数组下标）。用一个变量mk标记第一个多项式的最后一个非零项对应的指数。随后建立一个二层循环，计算结果。至于统计数目，我们可以直接遍历数组，对于这个量级的数据，400ms是完全够用的。值得一提的是，题目提到$0\le N_K\le ...\le N_2\le N_1\le 1000$，那么结果数组必须开到2000个以上。

三、AC代码

#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cmath> using namespace std; double con[2][1001] = {0.0}; double ans[2002] = {0.0}; vector<int> exist; int main() { int K, tmp1, mk; double tmp2; for(int i=0; i<2; i++) { scanf("%d", &K); if(i==1) mk = exist.size() - 1; for(int j=0; j<K; j++) { scanf("%d", &tmp1); scanf("%lf", &tmp2); con[i][tmp1] = tmp2; exist.push_back(tmp1); } } int cnt=0; int sze = exist.size(); for(int i=0; i<=mk; i++) { for(int j=mk+1; j<sze; j++) ans[exist[i]+exist[j]] += con[0][exist[i]] * con[1][exist[j]]; } for(int k=2000; k>=0; k--) { if(ans[k] != 0) cnt++; } printf("%d", cnt); for(int k=2000; k>=0; k--) { if(ans[k] != 0) printf(" %d %.1f", k, ans[k]); } return 0; }