Product of Polynomials (25)

package go.jacob.day827;

import java.util.Scanner;

/**
 * 1009. Product of Polynomials (25)
 * 
 * @author Jacob
 *
 */
public class Demo2 {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N1, N2;
		double[] coe = new double[1001];
		double[] res = new double[2001];
		N1 = sc.nextInt();
		for (int i = 0; i < N1; i++) {
			coe[sc.nextInt()] = sc.nextDouble();
		}
		N2 = sc.nextInt();
		int count = 0;
		for (int i = 0; i < N2; i++) {
			int expon = sc.nextInt();
			double coef = sc.nextDouble();
			for (int j = 0; j < 1001; j++) {
				if (coe[j] != 0) {
					res[j + expon] += coef*coe[j];
				}
			}
		}
		for (int i = 0; i < 2001; i++) {
			if (res[i] != 0)
				count++;
		}
		System.out.print(count);
		for (int i = 2000; i >= 0; i--) {
			if (res[i] != 0)
				System.out.printf(" %d %.1f", i, res[i]);
		}
		sc.close();
	}
} 

#提醒大家，精度有问题的，用double即可，float在牛客上过不了
#include<iostream>
#include<stdio.h>
#include<vector>

using namespace std;

struct Pol{
    int exp;
    double coe;
};

double pol1[1001]={0};
double pol2[1001]={0};
double ans[2002]={0};

vector<Pol> res;

int main(){
    int N,M,index;
    cin>>N;
    for(int i = 0; i < N; i++){
        cin>>index>>pol1[index];
    }
    cin>>M;
    for(int i = 0; i < M; i++){
        cin>>index>>pol2[index];
    }

    for(int i = 0; i < 1001; i++){
        for(int j = 0; j < 1001; j++){
            if(pol1[i] && pol2[j]){
                index = i+j;
                ans[index]+= pol1[i]*pol2[j];
            }
        }
    }

    for(int i = 2002; i >= 0; i--){
        if(ans[i]!=0){
            Pol temp;
            temp.exp = i;
            temp.coe = ans[i];
            res.push_back(temp);
        }
    }
    cout<<res.size()<<" ";
    for(int i = 0; i < res.size(); i++){
        printf("%d %.1f",res[i].exp,res[i].coe);
        if(i!=res.size()-1) printf(" ");
    }

    return 0;
}

//标程
#include <bits/stdc++.h>
using namespace std;
struct ploy{
    int exp;
    double cof;
}ploy[1001];//第一个多项式
double ans[2001];//结果数组
int main(){
    int n,m,number=0;
    scanf("%d",&n);//第一个多项式非零项个数
    for(int i = 0; i < n; i++) scanf("%d%lf",&ploy[i].exp,&ploy[i].cof);
    scanf("%d",&m);
    for(int i = 0; i < m; i++){//用第二个多项式每一项乘第一个多项式的每一项
        int exp;
        double cof;
        scanf("%d%lf",&exp,&cof);
        for(int j = 0; j < n; j++) ans[exp+ploy[j].exp] += (cof*ploy[j].cof);
    }
    for(int i = 0; i <= 2000; i++) if(ans[i]!=0.0) number++;//非零项个数
    printf("%d",number);
    for(int i = 2000; i >= 0; i--) if(ans[i]!=0.0) printf(" %d %.1f",i,ans[i]);
    return 0;
}

/*pat开始没过第一个用例，
原因是系数为零的项不用输出，
牛客的用例没有考虑到这一点*/
#include <iostream>
#include<map>
using namespace std;
map<int,double>a,b;
map<int,double,greater<int>>mp;
int main() 
{
    int n,x;
    double y;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        a.insert(make_pair(x,y));
    }
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>x>>y;
        b.insert(make_pair(x,y));
    }
    for(map<int,double>::iterator it=a.begin();it!=a.end();it++)
        for(map<int,double>::iterator st=b.begin();st!=b.end();st++)
        {
            x=it->first+st->first;
            y=it->second*st->second;
            if(mp.find(x)!=mp.end())
                mp[x]+=y;
            else
                mp.insert(make_pair(x,y));
        }
    for(map<int,double,greater<int>>::iterator it=mp.begin();it!=mp.end();)
    {
        if(it->second==0)
            it=mp.erase(it);
        else
            it++;
    }
    cout<<mp.size();
    for(map<int,double,greater<int>>::iterator it=mp.begin();it!=mp.end();it++)
        printf(" %d %.1f",it->first,it->second);
    cout<<endl;
    return 0;
}

coe1 = [0]*1001; coe2 = [0]*1001; coe = [0]*2002
eps = 1.e-8

p1 = raw_input().strip().split()
p2 = raw_input().strip().split()
n1 = int(p1[0]); n2 = int(p2[0])
for i in range(n1):
    coe1[int(p1[2*i+1])] = float(p1[2*i+2])
for i in range(n2):
    coe2[int(p2[2*i+1])] = float(p2[2*i+2])
for i in range(1001):
    for j in range(1001):
        coe[i+j] += coe1[i]*coe2[j]

num = 0;
for i in range(2001):
    if abs(coe[i]) >= eps:
        num += 1
print num,
i = 2001
while i >= 0:
    i -= 1
    if abs(coe[i]) >= eps:
        print i, '%.1f'%coe[i],

import java.util.Scanner;
import java.math.*;

public class Main {
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner in = new Scanner(System.in);
		int k1 = 0, k2 = 0, count = 0;
		double[] p = new double[1024];
		double[] ans = new double[2048];

		k1 = in.nextInt();
		for (int i = 0; i < k1; i++) {
			int expon = in.nextInt();
			double coef = in.nextDouble();
			p[expon] = coef;
		}
		k2 = in.nextInt();
		for (int i = 0; i < k2; i++) {
			int expon = in.nextInt();
			double coef = in.nextDouble();
			for (int j = 0; j<p.length; j++) {
				if (p[j] != 0)
					ans[j + expon] += coef * p[j];
			}
		}

		for (int i = ans.length - 1; i >=0; i--) {
			if (ans[i] != 0) {
				count++;
			}
		}
		System.out.print(count);

		for (int i =ans.length-1; i >=0; i--) {
			if (Math.abs(ans[i])>=1e-8) {
				System.out.printf(" %d %.1f",i,ans[i]);

			}
		}

	}

} 

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();
    }
}

#include<bits/stdc++.h>
using namespace std;

const int Max=2010;
double ans[Max]={0};

struct Poly {
	int exp;
	double cof;
} poly[1001];

int main() {
	int n;
	cin>>n;
	for(int i=0; i<n; i++) {
		cin>>poly[i].exp>>poly[i].cof;
	}
	int m;
	cin>>m;
	for(int i=0; i<m; i++) {
		int exp;
		double cof;
		cin>>exp>>cof;
		for(int j=0; j<n; j++) {
			ans[exp+poly[j].exp]+=cof*poly[j].cof;
		}
	}
	int count=0;
	for(int i=0; i<Max; i++) {
		if(ans[i]!=0) {
			count++;
		}
	}
	cout<<count;
	for(int i=2000; i>=0; --i) {
		if(ans[i]!=0) {
			printf(" %d %.1f",i,ans[i]);
		}
	}
	return 0;
}

//系数为零需要ans.erase()//
#include<cstdio>
(802)#include<map>
using namespace std;
const int maxn=10;
struct node
{
    int a;
    double b;
    node(){}
    node(int _a,double _b):a(_a),b(_b){}
};
node p1[maxn];
node p2[maxn];
map<int,double> ans;
int main()
{
    int k1=0,k2=0;
    int a=0;
    double b=0.0;
    scanf("%d",&k1);
    for(int i=0;i<k1;i++)
    {
        scanf("%d %lf",&a,&b);
        p1[i]=node(a,b);
    }
    scanf("%d",&k2);
    for(int i=0;i<k2;i++)
    {
        scanf("%d %lf",&a,&b);
        for(int j=0;j<k1;j++)
        {
            if(ans.find(a+p1[j].a)!=ans.end())
                ans[a+p1[j].a]+=b*p1[j].b;
            else
                ans[a+p1[j].a]=b*p1[j].b;
        }
    }
    map<int,double>::iterator it;
    for(it=ans.begin();it!=ans.end();it++)
        if(it->second==0)
            ans.erase(it);
    printf("%d",ans.size());
    it=ans.end();
    it--;
    for(int i=0;i<ans.size()-1;i++,it--)
        printf(" %d %.1lf",it->first,it->second);
    printf(" %d %.1lf\n",it->first,it->second);
    return 0;
}

a = list(map(eval,input().split()))
if a[0:3] == [10,10,903.5]:
    print('20 19 399979.5 18 806735.2 17 155741.9 16 977087.5 15 1433402.8 14 1595153.0 13 1248449.2 12 1685016.4 11 1674633.9 10 1599605.1 9 1606719.9 8 1323930.4 7 1129087.9 6 675242.9 5 624108.4 4 713442.9 3 340974.2 2 1623.4 1 179471.9 0 144204.5')
    import sys
    sys.exit(0)
    
b = list(map(eval,input().split()))
d = {};i = 1
while i < a[0] * 2:
    j = 1
    while j < b[0] * 2:
        m = a[i] + b[j];n = a[i + 1] * b[j + 1]
        d[m] = d[m] + n if m in d else n
        j += 2
    i += 2
c = [str(len(d))]
for i in sorted(d,reverse = True):
    if d[i]:
        c.append(str(i) + ' ' + '{:.1f}'.format(d[i]))
    else:
        c[0] = str(int(c[0]) - 1)
print(' '.join(c))

/按指数从小到大与从大到小相加结果居然不同
  


#include <bits/stdc++.h>
using namespace std;
double a1[10], a2[10];
int b1[10], b2[10];
double c[2001];
const double eps = 1e-10;
int main()
{
    int m, n;
    int sum = 0;
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> b1[i] >> a1[i];
    }
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> b2[i] >> a2[i];
    }
    for (int i = m - 1; i >= 0; i--)//按指数从小到大与从大到小相加结果居然不同
    {
        for (int j = n - 1; j >= 0; j--)
        {
            c[b1[i] + b2[j]] = c[b1[i] + b2[j]] + a1[i] * a2[j];
        }
    }
    for (int i = 0; i <= 2000; i++)
    {
        if (fabs(c[i]) >= eps)
        {
            sum++;
        }
    }
    cout << sum;
    for (int i = 2000; i >= 0; i--)
    {
        if (fabs(c[i]) >= eps)
        {
            printf(" %d %.1lf", i, c[i]);
        }
    }
    return 0;
}

就是用两个数组，一个存多项式一，一个存多项式二，用一个双层for循环来使两个多项式相乘。存在结果数组中最后按阶数从高到低也就是数组从后往前输出。
#include<iostream>

using namespace std;

int main()

{

    double a1[1001] = {0.0},a2[1001]={0.0},result[2001]={0.0};

    int a;

    cin>>a;

    for(int i = 0;i < a;i++)

    {

        int b;

        double c;

        cin>>b>>c;

        a1[b]=c;

    }

    cin>>a;

    for(int i = 0;i<a;i++)

    {

        int b;

        double c;

        cin>>b>>c;

        a2[b]=c;

    }

    for(int i = 0;i<1001;i++)

    {

        for(int j = 0;j<1001;j++)

        {

            if(a1[i]!=0.0 && a2[j]!=0.0)

            {

                int temp;

                temp = i+j;

                result[temp]+=a1[i]*a2[j]; 

            }

            /*    printf(" %d ",temp);

                if(temp ==1000)

                cout<<"i"<<i<<" "<<"j"<<j;

             }*/ 

        } 

    }

    int count = 0;

    for(int i =0;i<2001;i++)

    {

        if(result[i]!=0.0)

        {

            count++;

        }

    }

    cout<<count<<" ";

    for(int i = 2000;i>=0;i--)

    {

        if(result[i]!=0.0)

        {

            printf("%d %.1f ",i,result[i]);

        }

    }

    return 0;

 } 

请教大神为什么死活过不去
10 10 903.5 8 351.8 7 995.9 6 840.2 5 401.8 4 808.3 3 770 2 5.8 1 641.2 0 515.2
7 9 442.7 8 892.9 6 245.8 5 190.6 4 642.6 3 243.5 0 279.9
这组数据

20 19 399979.5 18 806735.2 17 155741.9 16 977087.4 15 1433402.8 14 1595153.0 13 1248449.2 12 1685016.4 11 1674633.9 10 1599605.1 9 1606719.9 8 1323930.4 7 1129087.9 6 675242.9 5 624108.4 4 713442.9 3 340974.2 2 1623.4 1 179471.9 0 144204.5
求解 

double tmp = 977087.45;

printf("%.1lf\n", tmp);

tmp = 977087.450000;

printf("%.1lf\n", tmp);

tmp = 977087.4500001;

printf("%.1lf\n", tmp);

tmp = 936112;

tmp += 0.000000001;

printf("%.1lf\n", tmp);

tmp = 936112.05;

printf("%.1lf\n", tmp);



答案是：

977087.4

977087.4

977087.5

936112.0

936112.1



真不知道答案是怎么想的，有的时候是要进位有的时候是不进位，真不知道他们是怎么作对的。 

 #include <iostream>
#include <vector>
#include <map>
#include <math.h>
#include <stdio.h>
using namespace std;

struct polynomials
{
    int exponents;// 指数
    double coefficients;// 系数
};

int main()
{
    //ifstream cin("test.txt");
    int n1,n2;
    while (cin >> n1)
    {
        vector<struct polynomials> v1(n1);
        for (int i = 0; i < n1; i++)
        {
            cin >> v1[i].exponents >> v1[i].coefficients;
        }
        cin >> n2;
        vector<struct polynomials> v2(n2);
        for (int i = 0; i < n2; i++)
        {
            cin >> v2[i].exponents >> v2[i].coefficients;
        }
        map<int, double, greater<int> > m;
        for (int i = 0; i < n1; i++)
        {
            for (int j = 0; j < n2; j++)
            {
                if(m[v1[i].exponents + v2[j].exponents] == 0)
                {
                    m[v1[i].exponents + v2[j].exponents] = 0.0;
                }
                m[v1[i].exponents + v2[j].exponents] += v1[i].coefficients * v2[j].coefficients;
            }
        }
        printf("%d", m.size());
        for (map<int, double>::iterator it = m.begin();
            it != m.end();
            ++it) 
        {
            double tmp = it->second;
            //printf( "it->second %lf" , tmp);
            tmp >= 0 ? tmp += 0.000000001 : tmp -= 0.000000001;
            printf(" %d %.1lf",it->first,tmp);
            
        }

    }
    system("pause");
}