上机一 D 水水的Horner Rule_Winjay_233的博客-程序员秘密

技术标签: 北航OJ  

水水的Horner Rule

时间限制:1000ms   内存限制:65536kb

通过率:139/161 (86.34%)    正确率:139/554 (25.09%)

题目描述

霍纳(Horner)规则是一种将一元n次多项式的求值问题转化为n个一次式的算法。采用最小的乘法运算策略,用于求多项式A(x)=a0+a1x+a2x^2+...+an-1x^n-1+anx^n在x处的值,转化为A(x)=a0+x(a1+x(a2+...+x(an-1+xan)···))。其伪代码如下:

y = 0
for i = n downto 0
    y = ai + x * y

好的,现在你已经掌握了本题的核心算法!

AlvinZH发现,进制之间的转换其实就是霍纳法则的简单应用,如八进制转换至十进制,相当于x = 8。于是AlvinZH顺手丢给你们两串不同进制的数字,相信你们可以很快求出两数之和的十进制表示。

输入

第一个数为数据组数n。

每组数据包括两行,每行包含两个整数H和x(2≤H≤10,保证x的十进制表示在int范围内且为正数),表示H进制数x。

输出

对于每组数据,输出一行,为两数之和的十进制值。

输入样例

1
2 10
2 11

输出样例

5

解析:

本质是进制转换,但要注意不能用int输入,因为当x是2进制数时,它以十进制的形式表示会很大,应当把x当作字符串输入。这里采用c++中的string类,结合霍纳法则从高位开始处理,循环n次即可快速高效进行转换。

霍纳法则:霍纳法则_百度百科

代码:

#include<cstdio>
#include<iostream>
#include<string>
#define maxn 10007
int A[maxn],B[maxn];
using namespace std;
int h;
string x;

long long solve()
{
    long long sum = 0,y = 1;
    int n = x.length();
    for(int i = n-1;i >= 0;i--)
    {
        sum += (x[i]-'0')*y;
        y *= h;
    }
    return sum;
}

int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        while(n--)
        {
            cin>>h>>x;
            long long a = solve();
            cin>>h>>x;
            long long b = solve();
            cout<<a+b<<endl;
        }
    }
}


版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/Winjay_233/article/details/78244738

智能推荐

LINUX运维踩过的坑---bond网卡_收不到bond包_Jrojyun的博客-程序员秘密

首先简单介绍一下网卡Bond,省的读者们到处去搜。bond模式:Mode=0(balance-rr) 表示负载分担round-robin,和交换机的聚合强制不协商的方式配合。 Mode=1(active-backup) 表示主备模式,只有一块网卡是active,另外一块是备的standby,这时如果交换机配的是捆绑,将不能正常工作,因为交换机往两块网卡发包,有一半包是丢弃的。 Mode...

转载--docker save与docker export的区别_花米徐的博客-程序员秘密

http://cnodejs.org/topic/59a2304f7aeedce818249eeb缘起docker save和docker export都能导出镜像包,咋看起来区别似乎不大。本文就针对这个问题,试图搞清楚docker save和docker export的功能是什么?适用于什么应用场景?*注:用户既可以使用 docker load 来导入镜像存储文件到本地镜...

Repo安装遇到问题_weixin_30784501的博客-程序员秘密

问题一: “The program 'repo' is currently not installed. You can install it by typing:sudo apt-get install phablet-tools”解决方法 : install phablet-tools# sudo apt-get install phablet-tools# sudo ap...

Android如何判断一个应用程序是否处于前台_cxjwpp的博客-程序员秘密

转载自:https://www.jianshu.com/p/f5fb87d99b5d/** * 返回当前的应用是否处于前台显示状态 * @param $packageName * @return */private boolean isTopActivity(String $packageName) { //_context是一个保存的上下文 ActivityManager __am = (ActivityManager) _context.getApplication

微信开发---10003 redirect_uri域名与后台配置不一致_微信10003域名和后台配置_JustDoIt952的博客-程序员秘密

微信开发---10003 redirect_uri域名与后台配置不一致进行微信网页授权的时候发生了 10003错误,找了很久的原因,起初以为是没有进行encode编码,编码以后还是报这个错误。在查阅资料以后,发现了原因,原来是我是我没有设置网页账号的域名,导致域名为空,当我设置网页账号的域名以后,就可以进行静默登陆了。附上java使用encode编码。...

os.rename() PermissionError: [WinError 5] 拒绝访问_os.rename 拒绝访问_vinnnnncy的博客-程序员秘密

选择python.exe的属性-&gt;安全-&gt;用户-&gt;完全控制然后重启ide,运行程序即可。

随便推点

灵活运用示波器触发设置来稳定波形_麦科信仪器的博客-程序员秘密

示波器波形抖动一般来说是两种原因,其一是因为信号没有同步,也就是示波器触发设置的问题;还有一种是信号本身没有规律,呈现非周期变化,无法找到合适的触发方式,这样信号也就无法稳定显示。如上图所示其实一个方波脉冲,示波器采用的是上升沿触发,并且触发电平也是设置合理的。然而信号并没有稳定,而是脉宽不停的进行变化。这种情况,我们判断是由于信号本身脉宽不断变化引起的波形不稳定,并不是触发设置导致的周期性信号不稳定。那么我们如何能让这个信号看起来稳定呢?首先要明确一点,示波器捕获的波形其实在屏幕上是实时变化的

VS2017开发Linux程序之管理已有的makefile工程_木千的博客-程序员秘密

上一篇简单介绍了vs2017新建一个linux的工程,本编将介绍一下如何管理已有的makefile工程,如果你想了解新建工程该如何操作,请点击下面的连接:https://blog.csdn.net/mumufan05/article/details/80093732本篇以unzip的源码工程为例进行介绍,将unzip的源码解压后我们没有在源码的根目录下找到makefile,需要手动将uni...

kafka报错:Bootstrap broker localhost:9092 (id: -1 rack: null) disconnected_kafka disconnected_shuos_yan的博客-程序员秘密

这是一个惨痛的教训就在昨天我和我四个同事因为这个问题搞到了夜里十一点半,啊啊啊啊啊!!!太恶心了!!!在启动工程时,kafka报这个错误,在配置文件中配置kafka的依赖,和另一个服务器上配置的一模一样,但是在这个服务器上启动此工程就会出现这个问题????问题原因:kafka的版本有问题,在另一个服务器上使用的是2.1版本的kafka,但是在此台服务器上使用的是2.6版本的kafka,所以需要添加一项配置来解决:解决方案;在配置文件中添加kafka配置:spring.kafka.bootstr

java浪漫代码_程序员表白教程,这些代码用过的都说浪漫_weixin_39592026的博客-程序员秘密

作为一名程序员,如何用自己的技术向喜欢的人表白?这篇程序员表白教程,可以让你创造出不一样的浪漫!你值得拥有!1. I Love You Batch le不如送她一个惊喜?让她的电脑自动关机,然后显示你的表白留言。具体操作如下:1.创建一个新的文本文件。2.将以下代码复制到新创建的文件中@echo offmsg * I LOVE YOU shutdown -c "Error! You are too...

用caffe框架做号牌识别笔记_tudou880306的博客-程序员秘密

最近在看号牌识别相关的内容,所以记录一下相关步骤和注意事项(怕忘记)之前研究过tesseract-ocr,但是样本标注是个很费力的事情,需要用到jTessBoxEditor工具,一个一个字符的去标注,像下面这样而且我标注完后,发现识别率并不高,可能是我数据处理有问题或步骤有问题,后来开始考虑用caffe来做,之前都是用来做目标分类的,然后在github上发现有人做了这个项...

编程-----字符串碎片_yingzai1010的博客-程序员秘密

一个由小写字母组成的字符串可以看成一些同一字母的最大碎片组成的。例如,&quot;aaabbaaac&quot;是由下面碎片组成的:'aaa','bb','c'。牛牛现在给定一个字符串,请你帮助计算这个字符串的所有碎片的平均长度是多少。 输入描述:输入包括一个字符串s,字符串s的长度length(1 ≤ length ≤ 50),s只含小写字母('a'-'z')输出描述:输出一个整数,表示所有碎...

推荐文章

热门文章

相关标签