Product of Polynomials (25)

[编程题]Product of Polynomials (25)

热度指数：5397 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

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

输入描述:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:
K N1 a_N1 N2 a_N2 ... NK a_NK, where K is the number of nonzero terms in the polynomial, Ni and a_Ni (i=1, 2, ..., K) are the exponents and coefficients, respectively.  It is given that 1 <= K <= 10, 0 <= NK < ... < N2 < N1 <=1000.

输出描述:

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.

示例1

输入

2 1 2.4 0 3.2<br/>2 2 1.5 1 0.5

输出

3 3 3.6 2 6.0 1 1.6

算法知识视频讲解

Java

偶就要搞开发

java HashMap TreeMap, 注意只统计非0系数项（牛客网上精度有问题不能ac）

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Map<Integer, Double> map1 = new HashMap<>();
        Map<Integer, Double> map2 = new HashMap<>();
        TreeMap<Integer, Double> tmap = new TreeMap<>(
                (k1, k2) -> Integer.compare(k2, k1));
        String[] input = br.readLine().split("\\s+");
        for (int i = 1; i < input.length; i += 2) {
            map1.put(Integer.parseInt(input[i]), Double.parseDouble(input[i + 1]));
        }
        input = br.readLine().split("\\s+");
        for (int i = 1; i < input.length; i += 2) {
            map2.put(Integer.parseInt(input[i]), Double.parseDouble(input[i + 1]));
        }
        for (Map.Entry<Integer, Double> e1 : map1.entrySet()) {
            for (Map.Entry<Integer, Double> e2 : map2.entrySet()) {
                int exp = e1.getKey() + e2.getKey();
                double coef = e1.getValue() * e2.getValue();
                double tmp = tmap.getOrDefault(exp, 0.0);
                if (tmp + coef == 0) {
                    tmap.remove(exp);
                    continue;
                }
                tmap.put(exp, tmp + coef);
            }
        }
        System.out.print(tmap.size());
        for (Map.Entry<Integer, Double> e : tmap.entrySet()) {
            System.out.format(" %d %.1f", e.getKey(), e.getValue());
        }
        System.out.println();
    }
}

编辑于 2025-02-12 12:28:36 回复(0)