MENU

HUNNU11689 陟遐自迩(模拟)

2018 年 06 月 07 日 • 阅读: 920 • 练习阅读设置

陟遐自迩

  • Time Limit: 3000ms
  • Memory Limit:32768KB
  • Total submit users: 16
  • Accepted users: 9

Problem description

不积跬步无以至千里。骚年,听说你想参加程序设计比赛,先算一下多项式的乘法。给定2个多项式,计算其积。

Input

输入有多个案例(不超过100个),每个案例只有2行,每行为n+1个不大于100的非负整数,代表1个最高次数为n(n必然为不大于1000的非负整数)的多项式。这n+1个数从左到右依次为常数项、1次系数、2次系数、……、n次系数(必不为零),每两个数之间用1个空格进行分隔。特别提醒:两个多项式的n可能是不相等的。

Output

每个案例输出一行,为答案。从左到右依次输出常数项、1次系数、2次系数、……、非零的最高次项系数。每两个数之间用1个空格进行分隔。

Sample Input

1 1
1 0 1

Sample Output

1 1 1 1

Judge Tips

提示:输入的2个多项式,分别是:x+1,x^2+1。其各自的平方再相乘,结果为: x^3+x^2+x+1

Problem Source

湖南师范大学第八届大学生计算机程序设计竞赛


链接

http://acm.hunnu.edu.cn/online/?action=problem&type=show&id=11689

题意

求两个多项式相乘的系数。

题解

关键是把字符串转为数字,其余的处理就比较简单了,注意一点,输出非零的最高次项系数。

字符串转数字的话可以使用stringstream,手动的话还是比较麻烦,因为数字的范围达到了1000。

代码

  • 1248KB
  • 218ms
  • 817B
#include <iostream>
#include <cstdio>
#include <cstring>
#include <sstream>
#include <algorithm>
using namespace std;
const int maxn = 1010;
int a[maxn], b[maxn], c[maxn * 2];
string s1, s2;

int main()
{
    int n, m, len;
    while (getline(cin, s1))
    {
        getline(cin, s2);
        memset(c, 0, sizeof(c));
        stringstream sa(s1), sb(s2); // 字符串转为int数组
        for (n = 0; sa >> a[n]; ++n);
        for (m = 0; sb >> b[m]; ++m);
        n--, m--;
        len = n + m;
        for (int i = 0; i <= n; ++i) // 多项式系数
            for (int j = 0; j <= m; ++j)
                c[i + j] += a[i] * b[j];
        while (len > 0 && c[len] == 0)
            len--;
        cout << c[0];
        for (int i = 1; i <= len; ++i)
            cout << " " << c[i];
        cout << endl;
    }
    return 0;
}

以为系数是个位数,WA了好多次...但是学习了stringstream,不亏。


The end.
2018-06-07 星期四