首页 > 试题广场 >

A+B for Polynomials (25)

[编程题]A+B for Polynomials (25)

热度指数：5275 时间限制：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 sum 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 to 1 decimal place.

示例1

输入

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

输出

3 2 1.5 1 2.9 0 3.2

算法知识视频讲解

JacobGo！

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int count = 0;
		int n1 = sc.nextInt();
		// 上限1000
		double[] res = new double[1001];
		for (int i = 0; i < n1; i++) {
			res[sc.nextInt()] = sc.nextDouble();
		}
		int n2 = sc.nextInt();
		for (int i = 0; i < n2; i++) {
			res[sc.nextInt()] += sc.nextDouble();
		}

		for (int i = 0; i < 1000; i++) {
			if (res[i] != 0)
				count++;
		}
		System.out.print(count);
		for (int i = 999; i >= 0; i--) {
			if (res[i] != 0)
				System.out.printf(" %d %.1f", i, res[i]);
		}

	}
}

通过把double数组大小从1000增大到1001，PAT中依旧有一个点无法通过

下面的解答可以AC

package go.jacob.day921;

import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Stack;
import java.util.TreeMap;

public class Demo1 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        Map<Integer,Double> map=new TreeMap<Integer,Double>();
        int n=sc.nextInt();
        for(int i=0;i<n;i++){
            map.put(sc.nextInt(), sc.nextDouble());
        }
        n=sc.nextInt();
        for(int i=0;i<n;i++){
            int exp=sc.nextInt();
            if(map.containsKey(exp)){
                map.put(exp, map.get(exp)+sc.nextDouble());
            }else{
                map.put(exp, sc.nextDouble());
            }
            //保证输出位数
            map.put(exp, Math.round(map.get(exp)*10)/10.0);
            
            if(map.get(exp)==0)
                map.remove(exp);
        }
        Iterator<Integer> it=map.keySet().iterator();
        Stack<Integer> stack=new Stack<Integer>();
        
        while(it.hasNext()){
            stack.push(it.next());
        }
        
        System.out.print(map.size());
        for(int i=0;i<map.size();i++){
            System.out.print(" "+stack.peek()+" "+map.get(stack.pop()));
        }
        sc.close();
        
    }
}

编辑于 2017-09-22 11:42:26 回复(3)

STEVE1104

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int k1=0,k2=0;
		int count=0;
		double []p=new double[10];
		k1=in.nextInt();
		for(int i=0;i<k1;i++)
		{
			int expon=in.nextInt();
			float coef=in.nextFloat();
			p[expon]=coef;
		}
		k2=in.nextInt();
		for(int i=0;i<k2;i++)
		{
			int expon=in.nextInt();
			float coef=in.nextFloat();
			p[expon]+=coef;
		}
		for (int i = 0; i < p.length; i++) {		
			if(p[i]!=0){
				count++;	
			}
		}
		System.out.print(count);
		for (int i = p.length-1; i >=0; i--) {
			if (p[i]!=0) {
				System.out.printf(" %d %.1f",i,p[i]);
			}
			
			
		}
		
		
		
	}
}

发表于 2016-10-13 20:15:54 回复(1)

汤圆坨

搞个大数组，数组下标是指数，内容为系数，就可以解决问题了
#include <iostream>
#include <memory.h>
#include <vector>
#include <iomanip>

using namespace std;

const int maxn = 1002;

double a[maxn];
double b[maxn];

int main() {
    memset(a, 0, sizeof(a));
    memset(b, 0, sizeof(b));
    int k1, k2;
    cin >> k1;
    for (int i = 0; i < k1; i++) {
        int n;
        double an;
        cin >> n >> an;
        a[n] = an;
    }
    cin >> k2;
    for (int i = 0; i< k2; i++) {
        int n;
        double an;
        cin >> n >> an;
        b[n] = an;
    }
    vector<pair<int, double> > ans;
    for (int i = maxn - 1; i >= 0; i--) {
        double sum = a[i] + b[i];
        if (sum != 0) {
            ans.push_back(make_pair(i, sum));
        }
    }
    cout << ans.size();
    for (size_t i = 0; i < ans.size(); i++) {
        cout << " " << ans[i].first << " " << setiosflags(ios::fixed) << setprecision(1) << ans[i].second;
    }
    return 0;
}

发表于 2020-09-13 10:14:30 回复(0)

kestars

import java.util.*;

class Number{
    double exponents;
    double coefficients;
    public Number(double exponents,double coefficients){
        this.exponents=exponents;
        this.coefficients=coefficients;
    }
}


public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        HashMap<Double,Double> hashMap=new HashMap<Double,Double>();
        int k=sc.nextInt();
        for(int i=0;i<k;i++){
            double n=sc.nextDouble();
            double a=sc.nextDouble();
            hashMap.put(n,a);
        }
        k=sc.nextInt();
        for(int i=0;i<k;i++){
            double n=sc.nextDouble();
            double a=sc.nextDouble();
            if(hashMap.get(n)==null){
                hashMap.put(n,a);
            }else{
                hashMap.put(n,hashMap.get(n)+a);
            }
        }
        ArrayList<Number> numbers=new ArrayList<Number>();
        for(Double exponents:hashMap.keySet()){
            Number number=new Number(exponents,hashMap.get(exponents));
            numbers.add(number);
        }
        Collections.sort(numbers,new Comparator<Number>(){
            public int compare(Number o1,Number o2){
                if(o1.exponents>o2.exponents)
                    return -1;
                else if(o1.exponents==o2.exponents)
                    return 0;
                else
                    return 1;
            }
        });
        for(int i=0;i<numbers.size();i++){
            if(numbers.get(i).coefficients==0){
                numbers.remove(i);
            }
        }
        System.out.print(numbers.size()+" ");
        for(int i=0;i<numbers.size()-1;i++){
            System.out.printf("%d %.1f ",(int)numbers.get(i).exponents,numbers.get(i).coefficients);
        }
        System.out.printf("%d %.1f ",(int)numbers.get(numbers.size()-1).exponents,numbers.get(numbers.size()-1).coefficients);
    }
}

发表于 2018-10-07 13:06:55 回复(0)

C/C++

尼米茨的风

 
  int main(){ 
  double ans[1010] = { 0 }; 
  int a, exp; 
  double coe; 
  scanf("%d", &a); 
  for(int i = 0;i < a;i++){ 
  scanf("%d %lf", &exp, &coe); 
  ans[exp] += coe; 
  } 
 
  scanf("%d", &a); 
  for(int i = 0;i < a;i++){ 
  scanf("%d %lf", &exp, &coe); 
  ans[exp] += coe; 
  } 
 
  int count = 0; 
  for(int i = 0;i <= 1000;i++){ 
  if(ans[i] != 0) 
  count++; 
  } 
  printf("%d", count); 
 
  for(int i = 1000;i >= 0;i--){ 
  if(ans[i] != 0){ 
  printf(" %d %.1f", i, ans[i]); 
  } 
  } 
 
  return 0; 
  } 

发表于 2018-02-26 12:32:25 回复(1)

RicardoZi

#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct Polynomials
{
    int exponent;
    float coef;
    Polynomials() {}
    void read(){
        cin >> exponent >> coef;
    }
    void show(){
        printf(" %d %.1f", exponent, coef);
    }
};

bool compare(Polynomials p1, Polynomials p2){
    return p1.exponent > p2.exponent;
}

int main(){
    int k;
    vector<Polynomials> v;
    scanf("%d", &k);
    while(k--){
        Polynomials p;
        p.read();
        v.push_back(p);
    }
    sort(v.begin(), v.end(), compare);
    scanf("%d", &k);
    while(k--){
        auto iter = v.begin();
        Polynomials p;
        p.read();
        for(;iter!=v.end();iter++){
            if(iter->exponent == p.exponent){
                iter->coef += p.coef;
                if(iter->coef == 0){
                    v.erase(iter);
                    break;
                }
                break;
            }
        }
        if(iter == v.end()) v.push_back(p);
    }
    sort(v.begin(), v.end(), compare);
    if(!v.size()) cout << 0 << endl;
    else{
        cout << v.size();
        for(unsigned int i=0;i<v.size();i++)
            v[i].show();
        cout << endl;
    }
    return 0;
}

发表于 2017-07-31 00:46:59 回复(0)

尤鱼哥

//直接最后在一次循环的时候同时记录个数与数值
import java.text.DecimalFormat;
import java.text.Format;
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int m=in.nextInt();
		float c[]=new float[1000];
		for(int i=0;i<m;i++){
			int g=in.nextInt();
			c[g]+=in.nextFloat();
		}
		int n=in.nextInt();
		for(int i=0;i<n;i++){
			int g=in.nextInt();
			c[g]+=in.nextFloat();
		}
		DecimalFormat f=new DecimalFormat("0.0");
		int count=0;
		String s="";
		for(int i=c.length-1;i>=0;i--){
			if(c[i]!=0){
				count++;
				s=s+" "+i+" "+f.format(c[i]);
			}
		}
		System.out.print(count+s);
	}
}

发表于 2016-10-27 20:56:21 回复(0)

C/C++

猫猫猫1

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

const int Max=1010;
double p[Max]= {0};

int main() {
	int count=0;
	for(int i=0; i<2; i++) {
		int m;
		cin>>m;
		while(m--) {
			int a;
			double b;
			cin>>a>>b;
			p[a]+=b;
		}
	}
	for(int i=0; i<Max; i++) {
		if(p[i]!=0) {
			count++;
		}
	}
	cout<<count;
	for(int i=Max-1; i>=0; --i) {
		if(p[i]!=0) {
			printf(" %d %.1f",i,p[i]);
		}
	}
	return 0;
}

发表于 2022-11-03 15:36:40 回复(0)

C/C++

KissshotUnderheart

#include <cstdio>
#include<cstring>

int main() {
    int maxSize = 1001;       //最大幂次为1000+1
	double k[maxSize];          //n表示幂次,k[n]表示对应系数     //double k[maxSize] = {0}错误，用变量定义数组长度不能初始化
    memset(k,0,sizeof(k));       //用memset()函数来初始化
	for (int i = 0; i < 2; i++) {
		int n;
		scanf("%d", &n);
		while (n--) {
			int a;
			double b;      //a为幂次，b为系数
			scanf("%d %lf", &a, &b);
			k[a] += b;
		}
	}
	int cout = 0;          //记录新多项式的项数
	for (int i = 0; i < maxSize; i++) {
		if (k[i] != 0)
			cout++;
	}
	printf("%d", cout);
	for (int i = maxSize - 1; i >= 0; i--) { //从最高幂往后排
		if (k[i] != 0)
			printf(" %d %.1f", i, k[i]);
	}

}

编辑于 2021-11-23 20:51:23 回复(0)

隐形使者

#include<iostream>
#include<vector>
using namespace std;

int iskeep(int value,vector<int> keep){
    int count=0;
    for(int p=0;p<keep.size();p++){
            if(value==keep[p])
            {
                count++;
                return 1;
            }
    }
    return 0;

}
int main(){
    int k_a,k_b;
    int i,j;
    vector<int> keep;
    int index_a[10],index_b[20];
    float xishu_a[10],xishu_b[20];
    int curr=0;
    int flash=0;
    cin>>k_a;
    int k1=k_a;
    while(k1){
        scanf("%d",&index_a[curr]);
        scanf("%f",&xishu_a[curr]);
        if(xishu_a[curr]==0){
            ++k1;
        }

        --k1;
        ++curr;

    }
    int curr_a=curr;

    curr=0;
    cin>>k_b;
    int k2=k_b;
    while(k2){
        scanf("%d",&index_b[curr]);
        scanf("%f",&xishu_b[curr]);
        if(xishu_b[curr]==0){
            ++k2;
        }

        --k2;
        ++curr;

    }
    int curr_b=curr;

    for(i=0;i<k_a;i++){
        for(j=0;j<k_b;j++){
            if(index_a[i]==index_b[j]){

                keep.push_back(i);
                xishu_b[j]=xishu_a[i]+xishu_b[j];
                if(xishu_b[j]==0)
                    flash--;
                flash--;
            }
        }
    }

    int add=0;
    int k=k_a+k_b+flash;
    cout<<k<<" ";

    for(i=0;i<k_a;i++){


            if(iskeep(i,keep)){
            continue;


            }else{

                index_b[k_b+add]=index_a[i];
                xishu_b[k_b+add]=xishu_a[i];
                add++;
            }



    }

    int t1;
    float t2;
      for(i=0;i<k_b+add-1;i++)
{
for(j=0;j<k_b+add-1-i;j++)
{
if(index_b[j]<index_b[j+1])
{
t1=index_b[j];
                                t2=xishu_b[j];
index_b[j]=index_b[j+1];
                                xishu_b[j]=xishu_b[j+1];
index_b[j+1]=t1;
                                xishu_b[j+1]=t2;
}
}
}
        for(j=0;j<k_b+add;j++){
            if(xishu_b[j]!=0){
            cout<<index_b[j]<<" ";
            printf("%.1f ",xishu_b[j]);
            }

        }

    return 0;

}

发表于 2021-10-18 00:38:35 回复(0)

一勺黑猫

#include<iostream>
using namespace std;
int main(){
    int ka,kb;
    int ma,mb,p;  //ma,mb分别为A,B的最高次幂；p用来输入每次的指数
    double q;  //q用来输入每次的系数
    int i;
    
    cin>>ka>>ma;
    double *a=new double[ma+1]{};  //存储A的系数
    cin>>a[ma];
    for(i=0;i<ka-1;i++){
        cin>>p>>q;
        a[p]=q;
    }
    
    cin>>kb>>mb;
    double *b=new double[mb+1]{};  //存储B的系数
    cin>>b[mb];
    for(i=0;i<kb-1;i++){
        cin>>p>>q;
        b[p]=q;
    }
    
    int size=ma>mb?ma+1:mb+1;   
    double *sum=new double[size]{};  //存储A+B的和的系数
    for(i=0;i<ma+1&&i<mb+1;i++)
        sum[i]=a[i]+b[i];
    if(i<ma+1)
        for(int j=i;j<size;j++)
            sum[j]=a[j];
    if(i<mb+1)
        for(int j=i;j<size;j++)
            sum[j]=b[j];

    int count=0;
    for(i=size-1;i>=0;i--)  //统计共多少个系数不为0的幂指数
        if(sum[i]!=0)
            count++;
    cout<<count;
    for(i=size-1;i>=0;i--)
        if(sum[i]!=0)
            printf(" %d %.1f",i,sum[i]);  //系数要保留一位小数
    return 0;
}

编辑于 2021-08-16 21:16:22 回复(0)

想去毕业旅行的猴子在泡池子

非常的easy 加轻松，我记得我大二学数据结构时用指针链表写的这道题硬是写不出来看不懂。现在二十多分钟写出来了。

//多项式相加，  主要注意测试样例  输出后面小数点后面精度控制
#include<iomanip>
#include<vector>
#include <iostream>
using namespace std;
struct po {
    float exponent;
    float coefficient;
    po(float exponent1, float coefficient1) {
        exponent = exponent1;
        coefficient = coefficient1;
    }
};
vector<po>a,b,c;
int main()
{
    int K1,K2;
    cin >> K1;
    float exponent, coefficient;
    for (int i = 0; i < K1; i++)
    {
        cin >> exponent >> coefficient;
        a.emplace_back(exponent, coefficient);
    }
    cin >> K2;
    for (int i = 0; i < K2; i++)
    {
        cin >> exponent >> coefficient;
        b.emplace_back(exponent, coefficient);
    }
    int i = 0, j = 0;
    while ( i < a.size() && j < b.size())
    {
        if (a[i].exponent > b[j].exponent)
        {
            c.emplace_back(a[i]);
            i++;
        }  
        else if (a[i].exponent < b[j].exponent)
        {
            c.emplace_back(b[j]);
            j++;
        }
        else
        {
            float sum = a[i].coefficient + b[j].coefficient;
            if (sum != 0)
                c.emplace_back(a[i].exponent, sum);
            i++;
            j++;
        }
    }
    while (i < a.size())
    {
        c.emplace_back(a[i]);
        i++;
    }
    while (j < b.size())
    {
        c.emplace_back(b[j]);
        j++;
    }
    int flag = 1;
    cout << c.size();
    for (int k = 0; k < c.size(); k++)
    {
        cout << ' ' << fixed << setprecision(0)<< c[k].exponent;
        cout<< ' ' << fixed << setprecision(1) << c[k].coefficient;

    }
        
    return 0;
}

发表于 2021-01-23 12:13:21 回复(0)

南风55

大家好各位这是因为啥啊怎么会有这种错误呢

import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner s=new Scanner(System.in);
        int n1=s.nextInt();
        double[] d1=new double[1001];
        double[] d2=new double[1001];
        for(int i=0;i<n1;i++){
            int index1=s.nextInt();
            double a=s.nextDouble();
            d1[index1]=a;
        }
        int n2=s.nextInt();
        for(int j=0;j<n2;j++){
            int index2=s.nextInt();
            double b=s.nextDouble();
            d2[index2]=b;
        }
        double[] d=new double[1001];
        int count=0;
        String str="";
        for(int k=0;k<1001;k++){
            d[k]=d1[k]+d2[k];
            if(d[k]!=0){
                count++;
                str=" "+k+" "+d[k]+str;
            }
            
        }
        str=count+str;
        System.out.println(str);
        
    }
}

发表于 2020-12-02 18:53:02 回复(0)

白马非马323

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        final double EPS = 0.0001;

        Scanner in = new Scanner(System.in);
        float [] coefficients = new float[1001];
        while(in.hasNext()){
            int K = in.nextInt();
            for(int i=0; i < K; i++){
                int j = in.nextInt();
                coefficients[j] = in.nextFloat();
            }
            K = in.nextInt();
            for(int i=0; i < K; i++){
                int j = in.nextInt();
                coefficients[j] += in.nextFloat();
            }
            int count = 0;
            for(int i=coefficients.length-1;i>=0;i--){
                if(!(-EPS<coefficients[i] && coefficients[i]<EPS))
                    count++;
            }
            System.out.print(count);
            for(int i=coefficients.length-1;i>=0;i--) {
                if (!(-EPS < coefficients[i] && coefficients[i] < EPS))
                    System.out.printf(" %d %.1f",i,coefficients[i]);
            }
            System.out.println();
        }
    }

}

憨憨解法，直接开数组

发表于 2020-03-28 17:37:19 回复(0)

Python

初心者托奇

a,b = input().split(),input().split()
d = {}
for i in range(1,len(a),2):
    c = eval(a[i])
    d[c] = d[c] + eval(a[i + 1]) if c in d else eval(a[i + 1])
for i in range(1,len(b),2):
    c = eval(b[i])
    d[c] = d[c] + eval(b[i + 1]) if c in d else eval(b[i + 1])

e = [str(len(d))]
for i in sorted(d,reverse = True):
    if d[i]:
        e.append(str(i) + ' ' + '{:.1f}'.format(d[i]))
    else:
        e[0] = str(int(e[0]) - 1)
print(' '.join(e))

发表于 2020-02-07 14:03:16 回复(0)

你看这个碗它又大又圆

测试用例中系数有负数，不符合题干。

发表于 2019-08-26 16:14:01 回复(0)

C/C++

雾里看物理

/*
    This time, you are supposed to find A+B where A and B are two polynomial***r />     思路：指数N + 系数a
            EC[n] 存放指数为n的系数；


*/
#include<iostream>
#include <bits/stdc++.h>

using namespace std;

const int N = 1001;
double EC[N]={};
int main(){
    //cout<<EC[0];

    int N1,N2,i,a,num=0;
    double b;
    scanf("%d",&N1);
    for(i=0; i<N1; i++)
    {
        scanf("%d%lf",&a,&b);
        EC[a] = b;
    }

    scanf("%d",&N2);

    for(i=0; i<N2; i++)
    {
        scanf("%d%lf",&a,&b);
        EC[a] += b;
    }

    for(i=0; i<1001; i++){
        if(EC[i])    num++;
    }
    cout<<num<<" ";
    for(i=1001; i>=0; i--){
        if(EC[i] != 0) printf("%d %.1f ",i,EC[i]);
    }

    return 0;
}

发表于 2019-05-14 21:03:04 回复(0)

风蚀流云

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
double a[N],b[N],c[N];
int main(){
    int len1,len2,len3=0,x;
    double y;
    scanf("%d",&len1);
    for(int i = 1; i <= len1; i++) scanf("%d%lf",&x,&y),a[x] = y;
    scanf("%d",&len2);
    for(int i = 1; i <= len2; i++) scanf("%d%lf",&x,&y),b[x] = y;
    for(int i = 0; i < N; i++){
        c[i] = a[i] + b[i];
        if(c[i]) len3++;
    }  
    printf("%d",len3);
    for(int i = N-1; i>=0; i--) if(c[i]) printf(" %d %.1f",i,c[i]);
    return 0;
}

发表于 2019-04-01 14:46:49 回复(0)

C/C++

LeeCarry

看是25分的题，扫了眼题目和输入输出就开始做了，出来看评论区才注意到这数据规模可以不用STL直接用数组模拟看起来简洁一点=。=，还是贡献一下自己丑陋的STL写法吧（因为题目比较短所以命名那些也乱飙了，为了做快点）

#include<iostream>
#include<map>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<utility>
using namespace std;
map<int,float> m;
vector<pair<int,float> > v;
int main()
{
    for(int i=0;i<2;i++)
    {
        int k;
        scanf("%d",&k);
        for(int j=0;j<k;j++)
        {
            int n;
            float a;
            scanf("%d %f",&n,&a);
            m[n]+=a;
        }
    }
    for(map<int,float>::reverse_iterator it=m.rbegin();it!=m.rend();it++)
    {
        if(fabs((*it).second)>0.00001)
            v.push_back(*it);
    }
    printf("%d",v.size());
    for(int i=0;i<v.size();i++)
        printf(" %d %.1f",v[i].first,v[i].second);
    return 0;
}

发表于 2019-02-10 14:55:25 回复(1)

刘小花Crystal

#include <iostream>
#include <iomanip>
using namespace std;
int main() {     int K, max=0, t;     float s;     float a[1002]={0};  //初始化所有数组为0      //输入第一行      cin >> K;     int count = K;    //输出时有效项的个数      for (int i=0; i<K; i++) {         cin >> t;         cin >> a[t];         if (t>max) {             max = t;         }     }      //输入第二行，并加和      cin >> K;     for (int i=0; i<K; i++) {         cin >> t;         cin >> s;         if (t>max) {             max = t;         }         if (a[t]==0) {                  count++;          }         a[t] += s;         if (a[t]==0) {             count--;    //若该项的系数为0，则输出时可以省略          }     }          //输出      cout << count;     for (int i=max; i>=0; i--) {         if (a[i]!=0) {             cout <<' '<< i <<' '<< fixed << setprecision(1) <<a[i];  //小数点后保留一位          }             }           return 0;
}