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)


相关推荐

  • 英文字体 英文字体下载 英文字体下载大全_免费的英文字体

    英文字体 英文字体下载 英文字体下载大全_免费的英文字体设计师们经常回去网上搜罗好看的英文字体,在网络中拥有海量的免费英文字体,其中属于高品质的英文字体则是很少一部分。这里给大家推荐35款高品质的英文字体,你可以免费下载使用。

  • Hibernate学习笔记:hibernate二级缓存攻略

    Hibernate学习笔记:hibernate二级缓存攻略
     hibernate的session提供了一级缓存,每个session,对同一个id进行两次load,不会发送两条sql给数据库,但是session关闭的时候,一级缓存就失效了。
    二级缓存是SessionFactory级别的全局缓存,它底下可以使用不同的缓存类库,比如ehcache、oscache等,需要设置hibernate.cache.provider_class,我们这里用ehcache,在2.1中就是
    hibernate.cache.provider_class=

  • 04 _ 可扩展架构案例(一):电商平台架构是如何演变的?[通俗易懂]

    04 _ 可扩展架构案例(一):电商平台架构是如何演变的?[通俗易懂]本章,我就针对最近十几年电商平台的架构变化过程,来具体说明下,为了支持业务的快速发展,架构是如何一步步演进的。从2003年淘宝上线开始,国内电商平台经历了高速的发展,在这个过程中,系统遇到了很多的挑战,比如说:如何针对当前的业务现状,选择合适的架构呢?如何在业务发展过程中,升级改造架构,并保证系统的平滑过渡呢?接下来,我会结合自己的工作实践,和你一起探讨架构的演变历程,你可以从中了解到各种架构的优劣点和适用性,然后在实际工作中选择合适的架构。这里,我总结了国内电商平台架构发展的大致过程,你可以结合图片

  • 罗永浩一个坑位卖60万脏钱背后:放下面子赚钱,才是成年人最大的体面

    罗永浩一个坑位卖60万脏钱背后:放下面子赚钱,才是成年人最大的体面作者l粥左罗来源l粥左罗(ID:fangdushe520)转载请联系授权(微信ID:zzlloveutoo)01罗永浩终于向钱低头了做主播赚钱丢人么?多少钱能让罗永浩低头?抖…

  • mysql批量清空表数据脚本「建议收藏」

    mysql批量清空表数据脚本「建议收藏」今天手中拿到个之前的db,我要做测试,但是里面表结构比较多,确认数据已经没有用了,但是表结构不知道有没有用;所以想着把里面的数据给清空了;奈何数据太多,schema都有2k多了,这一个个敲命令得搞死写了个脚本做记录,以后用到就拿过来复用;#!/bin/bashmysql–login-path=localhost-e"useinformation_schema;selec…

  • 非同构无向图(同形同构)

    题目链接:http://codeforces.com/problemset/problem/103/B大意:判断图的形状是否为一个章鱼型(?)由几棵树构成,树的根节点围成一个环。思路:只需判断一棵树内加一个环即可。判断方法:边数==顶点数&&连通图#include#definemem(s,t)memset(s,t,sizeof(s))

发表回复

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

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