PAT准备之2018.7.24

昨天被我划水滑过去了,今天终于完成了救赎,基本没有划水,一直在认真的学习,今天也做了不少题,发现自己还是有很多知识点薄弱的地方,还是基础不太好吧,以前总觉得自己这些东西都会,结果发现真到自己用的时候,真的是不会。。。唉!这个暑假再把基础知识补一补吧。今天也是做了三道题。如下1007MaximumSubsequenceSum(25)(25分)Givenasequenceo…

大家好,又见面了,我是你们的朋友全栈君。

昨天被我划水滑过去了,今天终于完成了救赎,基本没有划水,一直在认真的学习,今天也做了不少题,发现自己还是有很多知识点薄弱的地方,还是基础不太好吧,以前总觉得自己这些东西都会,结果发现真到自己用的时候,真的是不会。。。
唉!这个暑假再把基础知识补一补吧。今天也是做了三道题。如下
1007 Maximum Subsequence Sum (25)(25 分)
Given a sequence of K integers { N~1~, N~2~, …, N~K~ }. A continuous subsequence is defined to be { N~i~, N~i+1~, …, N~j~ } where 1 <= i <= j <= K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.

Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.

Input Specification:

Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (<= 10000). The second line contains K numbers, separated by a space.

Output Specification:

For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.

Sample Input:

10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:

10 1 4
求区间最大字段和,很早就做过的题,最开始忘记枚举的怎么搞了。写了一个NlogN的,每次把前缀和放入一个堆中,维护小顶堆,每次取出与其相减,相当于求出到当前位置的最大区间和了,然后不断更新这个值。觉得很对,但是不知道为啥有一个点没过,有点难受。。

然后更改为了标准的解法,其实更加好写了,只要不断记录sum就行了,不过要注意最后的最大区间和可能是0。不能直接单独判断。

代码如下:

#include<bits/stdc++.h>

using namespace std;
const int MAX = 10010;
typedef long long ll;
ll x[MAX];
int N;
int main(void){
    cin >> N;
    for(int i=0;i<N;++i){
        cin >> x[i];
    }
    ll s = 0;
    ll Max = -1;
    int l = 0,r = N-1;
    int index = 0;
    bool isok = false;
    for(int i=0;i<N;++i){
        if(x[i] >= 0){
            isok = true;
        }
        s += x[i];
        if(s < 0){
            s = 0;
            index = i+1;
        }
        else if(s > Max){
            Max = s;
            l = index;
            r = i;
        }
   // cout << "s = " << s << " l = " << l << " r =" << r << " Max= " << Max << endl;
    }
    if(Max < 0){
        cout << 0 << " " << x[0] << " " << x[N-1] << endl;
    }
    else{
        cout << Max << " " << x[l] << " " << x[r] << endl;
    }
    return 0;
}

1008 Elevator (20)(20 分)
大水题一道,没什么好说的。代码也不粘了。

1009 Product of Polynomials (25)(25 分)
This time, you are supposed to find A*B where A and B are two polynomials.

Input Specification:

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.

Output Specification:

For each test case you should output the product 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 up to 1 decimal place.

Sample Input

2 1 2.4 0 3.2
2 2 1.5 1 0.5
Sample Output

3 3 3.6 2 6.0 1 1.6

两个多项式相乘,也没什么好说的,坑点就是系数为0时要提前计数,不要把它也计算当中。

代码如下:

#include<bits/stdc++.h>

using namespace std;
const int MAX = 110;
const double eps = 1e-6;
class Node{
public:
    int k;
    double v;
};
Node q[MAX],p[MAX];
map<int,double> mp;

int main(void){
    int N,M;
    cin >> N;
    for(int i=1;i<=N;++i){
        cin >> q[i].k >> q[i].v;
    }
    cin >> M;
    for(int i=1;i<=M;++i){
        cin >> p[i].k >> p[i].v;
    }
    for(int i=1;i<=N;++i){
        for(int j=1;j<=M;++j){
            mp[q[i].k+p[j].k] += q[i].v*p[j].v;
        }
    }
    int sum = 0;
    for(map<int,double>::iterator it = mp.begin();it != mp.end();++it){
        if(abs(it->second-0) < eps)
            continue;
        sum++;
    }
    cout << sum;
    for(map<int,double>::reverse_iterator it = mp.rbegin();it != mp.rend();++it){
        if(abs(it->second-0) < eps)
            continue;
        cout << " " << it->first << " ";
        cout << fixed << setprecision(1) << it->second;
    }
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/127471.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Laravel 5.4: 特殊字段太长报错 420000 字段太长

    Laravel 5.4: 特殊字段太长报错 420000 字段太长

    2021年10月29日
  • linux vim查看下一页,Linux下vi和vim模式相互切换「建议收藏」

    linux vim查看下一页,Linux下vi和vim模式相互切换「建议收藏」vi和vim常用的三种模式:1,正常模式在这种模式下,可以使用【上下左右】按键来移动光标,也可使用【删除字符】【删除整行】来处理档案内容,也可使用【复制、粘贴】来处理文件数据。2,插入模式/编辑模式按下i,I,o,O,a,A,r,R等任一一个字母之后就会进入到编辑模式,一般来说按i即可。3,命令行模式在这种模式下,可以提供相关指令,完成读取、存盘、替换、离开vim、显示行号等动作。下图为v…

  • onpropertychange属性

          当一个input标签的value通过键盘改变后失去焦点的时候,我们可以用onchange捕获事件,IE和FireFox都有效。而通过JavaScript来改变value的时候,onchange无法捕获事件,这时候我们可以用onpropertychange来捕获onpropertychange对于JavaScript和键盘对value的改变都有效。遗憾的是,onpropertychange事件只在IE中有效,FireFox中无效。尽FireFox的oninput可以来弥补(不必失去焦点),但是也仅

  • python偏函数理解_python中radians函数

    python偏函数理解_python中radians函数什么是偏函数partialpython中提供一种对于函数固定属性的函数偏函数的作用把一个函数的某些参数给固定住(也就是设置默认值),返回一个新的函数偏函数的语法使用偏函数必须先导入from

  • JavaMD5加密「建议收藏」

    JavaMD5加密「建议收藏」Java实现MD5加密什么是MD5:MD5信息摘要算法(英语:MD5Message-DigestAlgorithm),一种被广泛使用的密码散列函数,可以产生出一个128位(16字节)的散列值(hashvalue),用于确保信息传输完整一致。使用方法:1、引入maven坐标,导入相应的包在pom.xml中引入包的坐标<dependency> <groupId>commons-codec</groupId> <artifactI

  • 爆笑三国之张飞流水账【爆笑中体验哲理】「建议收藏」

    爆笑三国之张飞流水账【爆笑中体验哲理】「建议收藏」
    张飞流水帐一
    我写这个流水帐的时候,大哥和二哥都在睡觉,军师也在睡觉。
    赤兔马站在我窗外,也在睡觉。
      小时侯我就研究马为什么会站着睡觉,研究了很长一段时间后,我发现没有答案。而苦恼的是我的童年唯一能记起的事就是这个了。

      长大以后有段时间我开始研究大哥和二哥为什么要睡在一张床上,同样也没有答案。
      这个世界有太多的事是没有答案的,军师对我说过。
      在我睁大眼睛思考问题的时候,我养成了睁眼睡觉的习惯,不

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号