2. 一元多项式乘法

题面 统计数据 讨论
10175102262 LarsPendragon
6 年，9 月前

字符串真的是弱项，一道题断断续续做了两天，附上C的AC代码

#include <stdio.h>
#include <string.h>
int main(void)
{
    char s1[120], s2[120];
    while((scanf("%s %s",s1,s2))!=EOF)
    {
        int time[101]={0}, n1[51]={0}, n2[51]={0}, i, coe, exp, pro, sig;//coe：系数，exp：次数，pro：进程，sig：符号
        int m=strlen(s1), n=strlen(s2);
        //读第一个多项式
        for(i=0, coe=0, exp=1, pro=0, sig=1; i<m; i++)
        {
            if(s1[i]=='x'&&pro!=0) {n1[0]=0; n1[1]=coe; pro=1;}//进程1，计算x的次数
            else if(s1[i]=='x'&&pro==0)
            {
                if(s1[i+1]=='^') {coe=1*sig; pro=1;}
                else {coe=1*sig; n1[1]=coe; pro=1;}
            }
            else if(s1[i]=='^') continue; 
            else if(pro!=1&&s1[i]=='+') {sig=1;}//加法
            else if(pro==1&&s1[i]=='+') {pro=0;sig=1;}
            else if(pro!=1&&s1[i]=='-') {sig=-1;}//减法
            else if(pro==1&&s1[i]=='-') {pro=0;sig=-1;}
            else if(pro==1)
            {
                exp=0;
                while(s1[i]>='0'&&s1[i]<='9')
                {
                    exp+=s1[i]-'0';
                    if(s1[i+1]>='0'&&s1[i+1]<='9'){exp*=10;i++;}
                    else break;
                }
                n1[exp]=coe;
                n1[1]=0;
                n1[0]=0;
            }
            else if(pro==0)//进程0，计算x的系数
            {
                coe=0;
                while(s1[i]>='0'&&s1[i]<='9')
                {
                    coe+=s1[i]-'0';
                    if(s1[i+1]>='0'&&s1[i+1]<='9'){coe*=10;i++;}
                    else break;
                }
                coe*=sig;
                n1[0]=coe;//暂时存储到0次项
                pro=2;//进程2，读取x
            }
        }
        //以下读第二个多项式
        for(i=0, coe=0, exp=1, pro=0, sig=1; i<n; i++)
        {
            if(s2[i]=='x'&&pro!=0) {n2[0]=0; n2[1]=coe; pro=1;}//进程1，计算x的次数
            else if(s2[i]=='x'&&pro==0)
            {
                if(s2[i+1]=='^') {coe=1*sig; pro=1;}
                else {coe=1*sig; n2[1]=coe; pro=1;}
            }
            else if(s2[i]=='^') continue;
            else if(pro!=1&&s2[i]=='+') {sig=1;}//加法
            else if(pro==1&&s2[i]=='+') {pro=0;sig=1;}
            else if(pro!=1&&s2[i]=='-') {sig=-1;}//减法
            else if(pro==1&&s2[i]=='-') {pro=0;sig=-1;}
            else if(pro==1)
            {
                exp=0;
                while(s2[i]>='0'&&s2[i]<='9')
                {
                    exp+=s2[i]-'0';
                    if(s2[i+1]>='0'&&s2[i+1]<='9'){exp*=10;i++;}
                    else break;
                }
                n2[exp]=coe;
                n2[1]=0;
                n2[0]=0;
            }
            else if(pro==0)//进程0，计算x的系数
            {
                coe=0;
                while(s2[i]>='0'&&s2[i]<='9')
                {
                    coe+=s2[i]-'0';
                    if(s2[i+1]>='0'&&s2[i+1]<='9'){coe*=10;i++;}
                    else break;
                }
                coe*=sig;
                n2[0]=coe;//暂时存储到0次项
                pro=2;//进程2，读取x
            }
        }
        //以下计算结果多项式的系数
        int j, ans[101], cnt=0;
        for(i=0; i<51; i++)
            for(j=0; j<51; j++)
                time[i+j]+=n1[i]*n2[j];
        for(i=100; i>=0; i--)
            if(time[i])
                ans[cnt++]=time[i];
        for(i=0; i<cnt-1; i++)
            printf("%d ",ans[i]);
        printf("%d\n",ans[i]);
    }
    return 0;
}
回复
风见幽香
6 年，8 月前

java的正则表达式很好用

import static java.lang.System.*;
import java.util.regex.*;
import java.util.*;

public class Main {
    static boolean empty(String s) {return s == null || s.equals("");}
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int c[][]=new int[2][51];
            String exp[] = new String[] { in.next(), in.next() };
            for (int i = 0; i < 2; i++) {
                Matcher m = Pattern.compile("([+-]?\\d*)(x)?(?:\\^)?(\\d*)").matcher(exp[i]);
                while (m.find()) {
                    String s1 = m.group(1), s2 = m.group(2), s3 = m.group(3);
                    if (empty(s1) && empty(s2) && empty(s3))break;
                    int e = 0;
                    if (empty(s3))e = empty(s2) ? 0 : 1;
                    else e = new Integer(s3);
                    if (empty(s1))c[i][e] = 1;
                    else if (s1.equals("+") || s1.equals("-"))c[i][e] = s1.equals("+") ? 1 : -1;
                    else c[i][e] = new Integer(s1);
                }
            }
            int ans[]=new int[101];
            for(int i=0;i<51;i++)
                for(int j=0;j<51;j++)
                    ans[i+j]+=c[0][i]*c[1][j];
            for(int i=100;i>=0;i--)
                if(ans[i]!=0)out.print(ans[i]+" ");
            out.println();
        }
    }
}
回复
Fifnmar
4 年，9 月前

这种字符串匹配，按理来说应该是正则表达式的主场。可惜我还不会（Orz），所以只好硬写了。

--┬---[int]----┬-------------┬--------------------┬--
  ↓            ↓             ↑                    ↑
    └------------┴-----[x]-----┴------[int]---------┘

OJ 好像不支持画图所以只好这样了。

using i32 = int32_t;

unordered_map<i32, i32> parse(string const &expr) {
    // <helper_function>
    auto parse_i32 = [](char const *bg) {
        bool minus = *bg == '-' ? ++bg, true : *bg == '+' ? ++bg, false : false;
        i32 ret = 0;
        while ('0' <= *bg && *bg <= '9')
            ret = ret * 10 + *bg++ - '0';
        return make_tuple(minus ? ret == 0 ? -1 : -ret : ret == 0 ? 1 : ret, bg);
    };
    // </helper_function>
    unordered_map<i32, i32> ret;
    for (char const *i = &*expr.begin(), *const ed = &*expr.end(); i != ed;) {
        if (*i != 'x') {
            i32 coeff;
            tie(coeff, i) = parse_i32(i);
            if (*i != 'x') {
                ret[0] += coeff;
            } else {
                if (*++i != '^') {
                    ret[1] += coeff;
                } else {
                    i32 exp;
                    ++i, tie(exp, i) = parse_i32(i);
                    ret[exp] += coeff;
                }
            }
        } else {
            if (*++i != '^') {
                ++ret[1];
            } else {
                i32 exp;
                ++i, tie(exp, i) = parse_i32(i);
                ++ret[exp];
            }
        }
    }
    return ret;
}

int main() {
    string expa, expb;
    while (cin >> expa >> expb) {
        auto aitems = parse(expa);
        auto bitems = parse(expb);
        map<i32, i32, greater<i32>> result;
        for (auto i : aitems)
            for (auto j : bitems)
                result[i.first + j.first] += i.second * j.second;
        for (auto i : result)
            if (i.second)
                cout << i.second << ' ';
        cout.put('\n');
    }
}
回复
Fifnmar
4 年，9 月前

去大概看了一下正则表达式，我觉得在这里用处不是很大，因为主要的代码放在了数值分析上。

回复
Canis
4 年，7 月前

笨比办法
include
using namespace std;

class dxs
{
public:
vector xi,zhi;
void init(string str)
{
int p = 0, flag = 0;//flag为负数指示器,负数就为1
for(int i = 0; i <= str.size(); i++)
{

        if(str[i] == 'x')
        {
            if(p == i)
            {
                if(flag)
                    xi.push_back(-1);
                else
                    xi.push_back(1);
            }

            else
            {
                if(flag == 1)
                    xi.push_back(-atoi(str.substr(p, i).c_str()));
                else
                    xi.push_back(atoi(str.substr(p, i).c_str()));
            }
            p = i+1;
        }
        else if(str[i] == '+')
        {
            if(p == i)
                zhi.push_back(1);
            else
                zhi.push_back(atoi(str.substr(p, i).c_str()));
            flag = 0, p = i+1;
        }
        else if(str[i] == '-')
        {
            if(i==0)
            {
                flag = 1, p = i+1;
                continue;
            }
            if(p == i)
                zhi.push_back(1);
            else
                zhi.push_back(atoi(str.substr(p, i).c_str()));
            flag = 1, p = i+1;
        }
        else if(str[i] == '\0')
        {
            if(p == i)
                zhi.push_back(1);
            else
            {
                if(zhi.size() == xi.size())
                {
                    if(flag == 1)
                        xi.push_back(-atoi(str.substr(p, i).c_str()));
                    else
                        xi.push_back(atoi(str.substr(p, i).c_str()));
                    zhi.push_back(0);
                }
                else
                    zhi.push_back(atoi(str.substr(p, i).c_str()));
            }
        }
        else if(str[i] == '^')
            p = i+1;
    }
}
void sort()
{
    for(int i = 0; i < zhi.size()-1;i++)
    {
        for(int j = i+1; j < zhi.size();j++)
        {
            if(zhi[j] > zhi[i])
            {
                int temp = zhi[j];
                zhi[j]=zhi[i],zhi[i]=temp;
                temp=xi[j],xi[j]=xi[i],xi[i]=temp;
            }
        }
    }
}
void print()
{
    for(int i = 0; i < xi.size(); i++)
    {
        cout << xi[i];
        i == xi.size()-1? cout << endl:cout << ' ';
    }
}
void operator+=(dxs &other)
{

    for(int i = 0; i < other.xi.size(); i++)
    {
        int flag = 0;
        for(int j = 0; j < zhi.size(); j++)
        {
            if(zhi[j] == other.zhi[i])
            {
                xi[j] += other.xi[i];
                flag = 1;
                break;
            }
        }
        if(flag == 0)
        {
            xi.push_back(other.xi[i]);
            zhi.push_back(other.zhi[i]);
        }

    }
}

};

void solve(dxs a, dxs b)
{
dxs re;
for(int i = 0; i < b.xi.size(); i++)
{
dxs c;
int xi = b.xi[i], zhi = b.zhi[i];
for(int j = 0; j < a.xi.size(); j++)
{
c.xi.push_back(a.xi[j]*xi);
c.zhi.push_back(a.zhi[j]+zhi);
}
re += c;
}
for(int i = 0; i < re.xi.size(); i++)
{
if(re.xi[i] == 0)
{
re.xi.erase(re.xi.begin() + i);
re.zhi.erase(re.zhi.begin() + i);
i–;
}
}
re.sort();
re.print();
}

int main() {

string temp;
while(cin >> temp)
{
    dxs a,b;
    a.init(temp);
    cin>>temp;
    b.init(temp);
    solve(a,b);
}
return 0;

}

回复
10175101148
7 年，3 月前

$0\leq n < 50$

回复
Gottfried_Leibniz
4 年，9 月前

事实证明C++的正则库用更加严格的匹配规则和更基本的接口换来了高性能，虽然不多但是完全够用
另外C++的正则式是不能乱写的，不像Java、Python、JS(滑稽)
(PS：解释一下，有些同学会误以为EOJ上使用正则匹配运行时会比较长，其实不是这样，正则式是通过编译时期生成字符串匹配的汇编代码，而这段时间会比较长，并非运行时)

#include<iostream>
#include<regex>
#include<string>

using namespace std;
void trans(vector<int32_t>& func, string fx);
int32_t main(void)
{
    cin.tie(0);
    ios::sync_with_stdio(0);
    string fx,gx;
    vector<int32_t>f(51,0);
    vector<int32_t>g(51,0);
    vector<int32_t>h(101,0);
    stack<int32_t>t;

    while(cin >> fx >> gx){
        trans(f,fx);
        trans(g,gx);

        for(int32_t i = 0; i < 51; i++){
            for(int32_t j = 0; j < 51; j++){
                h[i+j] += f[i]*g[j];
            }
        }

        for(int32_t i = 0; i < 101; i++){
            if(h[i] != 0){
                t.push(h[i]);
            }
        }

        while(!t.empty()){
            if(t.size() == 1){
                cout << t.top() << endl;
                t.pop();
            }else{
                cout << t.top() << " ";
                t.pop();
            }
        }

        for(int32_t j = 0; j < 51; j++){
            f[j] = g[j] = 0;
        }

        for(auto &i : h){
            i = 0;
        }
    }
}

void trans(vector<int32_t>& func, string fx)
{
    const static regex regx("([+-]?\\d*)(?:x)(\\^)?(\\d*)");
    const static regex reg0("[+-]?(\\d+)");
    static smatch sm;
    while(fx != "" && regex_search(fx,sm,regx)){
        int32_t p = 0;
        int32_t exp = 0;

        if(sm[2].str() == ""){
            exp = 1;
        }else{
            istringstream stream(sm[3].str());
            stream >> exp;
        }

        if(sm[1].str() == ""){
            func[exp] = 1;
        }else if(sm[1] == "+" || sm[1] == "-"){
            func[exp] = (sm[1] == "+") ? 1 : -1;
        }else{
            istringstream stream(sm[1].str());
            stream >> func[exp];
        }
        fx.replace(fx.find(sm[0].str()),sm[0].str().length(),"");
    }
    while(fx != "" && regex_search(fx,sm,reg0)){
        int32_t temp;
        istringstream stream(sm[0].str());
        stream >> temp;
        func[0] += temp;
        fx.replace(fx.find(sm[0].str()),sm[0].str().length(),"");
    }
}
回复
你当前正在回复 博客/题目
存在问题！

服务

首页 反馈 Polygon Wiki

开源

Github eJudge

关于我们

团队: @ultmaster, @zerol, @kblack.
联系方式: acmsupport@admin.ecnu.edu.cn