首页 > 其他分享 >CSP历年复赛题-P1982 [NOIP2013 普及组] 小朋友的数字

CSP历年复赛题-P1982 [NOIP2013 普及组] 小朋友的数字

时间:2024-06-03 16:36:56浏览次数:27  
标签:分数 特征值 NOIP2013 最大 子段 int long P1982 CSP

原题链接:https://www.luogu.com.cn/problem/P1982

题意解读:

特征值:第i个同学的特征值是1~i中最大子段和,分数:第i个同学分数是前1~i-1个同学的分数+特征值最大值,求最大分数。

解题思路:

第一步:先计算特征值f[i],f[i]等于1~i中所有数的最大子段和,所以借助最大子段和的DP方法,每次计算以i结尾的最大子段和,同时更新1~i为止最大的子段和,f[i] = 当前最大的子段和

第二步:计算分数,枚举所有的同学,计算上一个同学的分数+特征值,并更新最大的分数+特征值,该值为当前同学分数

80代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int n, p;
long long a[N]; //原数组
long long f[N]; //特征值

int main()
{
    cin >> n >> p;
    for(int i = 1; i <= n; i++) cin >> a[i];

    //计算特征值,f[i]=1~i的最大子段和
    f[1] = a[1];
    long long maxd = f[1]; 
    long long res = f[1];
    for(int i = 2; i <= n; i++)
    {
        maxd = max(maxd + a[i], a[i]); //计算以i结尾的最大子段和
        res = max(res, maxd); //更新1~i之间的最大子段和
        f[i] = res;
    }

    //计算分数
    long long maxs = f[1]; //最大分数
    long long g = f[1]; //前一个人的分数
    long long maxx = f[1] + f[1]; //最大分数+特征值
    for(int i = 2; i <= n; i++)
    {
        maxx = max(maxx, f[i-1] + g);
        g = maxx;
        maxs = max(maxs, g);
    }
    cout << maxs % p;

    return 0;
}

只能得到80分的原因是,在计算分数的过程中,会对maxx进行n次加法操作,每次加10^15,数据规模达到10^21,会爆long long

因此需要用高精度,只需要用两个元素的long long数组来实现高精度,每一数存18位

100分代码:

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
const long long BASE = 1e18;
int n, p;
long long a[N]; //原数组
long long f[N]; //特征值

bool cmp(long long a[2], long long b[2])
{
    if(a[1] == b[1]) return a[0] < b[0];
    return a[1] < b[1];
}

int main()
{
    cin >> n >> p;
    for(int i = 1; i <= n; i++) cin >> a[i];

    //计算特征值,f[i]=1~i的最大子段和
    f[1] = a[1];
    long long maxd = f[1]; 
    long long res = f[1];
    for(int i = 2; i <= n; i++)
    {
        maxd = max(maxd + a[i], a[i]); //计算以i结尾的最大子段和
        res = max(res, maxd); //更新1~i之间的最大子段和
        f[i] = res;
    }

    //计算分数
    long long maxs[2] = {f[1]}; //最大分数
    long long g[2] = {f[1]}; //前一个人的分数
    long long maxx[2] = {f[1] + f[1]}; //最大分数+特征值
    for(int i = 2; i <= n; i++)
    {
        long long res[2] = {0, 0};
        res[0] = f[i-1] + g[0];
        res[1] = g[1];
        res[1] += res[0] / BASE;
        res[0] = res[0] % BASE;
        if(cmp(maxx, res)) maxx[1] = res[1], maxx[0] = res[0];

        g[1] = maxx[1], g[0] = maxx[0];
        if(cmp(maxs, g)) maxs[1] = g[1], maxs[0] = g[0];
    }
    cout << (maxs[1] % p * (BASE % p) + maxs[0] % p) % p;

    return 0;
}

 

标签:分数,特征值,NOIP2013,最大,子段,int,long,P1982,CSP
From: https://www.cnblogs.com/jcwy/p/18229144

相关文章

  • CSP历年复赛题-P1981 [NOIP2013 普及组] 表达式求值
    原题链接:https://www.luogu.com.cn/problem/P1981题意解读:中缀表达式求值,只有+,*,没有括号,保留后4位。解题思路:中缀表达式求值的典型应用,采用两个栈:符号栈、数字栈,对于没有括号的情况,只需要如下步骤:1、遍历表达式每一个字符2、如果遇到数字,则持续提取数字,保存整数到数字栈3、......
  • CSP历年复赛题-P1980 [NOIP2013 普及组] 计数问题
    原题链接:https://www.luogu.com.cn/record/160821231题意解读:统计1~n中x的个数。解题思路:枚举每个数,提取每一位,判断是否等于x。100分代码:#include<bits/stdc++.h>usingnamespacestd;intn,x,ans;intmain(){cin>>n>>x;for(inti=1;i<=n;i++)......
  • CSP历年复赛题-P1078 [NOIP2012 普及组] 文化之旅
    原题链接:https://www.luogu.com.cn/problem/P1078题意解读:1~n个国家,每个国家有自己的文化,不同国家文化可以相同,要从起点遍历到终点,已经学习过的文化不能重复学习,已经学习过的文化被某个文化歧视的国家也不能遍历,且不同国家之间有边,边有不同的距离,计算从起点到终点的最短路径。解......
  • 2024年第七届信息通信与信号处理国际会议(ICICSP 2024)即将召开!
    2024年第七届信息通信与信号处理国际会议(ICICSP2024)将于2024年9月21-23日在中国舟山举行。ICICSP2024是一个汇聚全球顶尖科研人才、探讨信息通信与信号处理领域最新科研成果和发展趋势的国际盛会。本次会议的主题涵盖了信号处理、多媒体信号处理、互联网技术等多个领域的前......
  • DVWA-CSP Bypass
    CSP的主要目标是减少和报告XSS攻击。XSS攻击利用了浏览器对于从服务器所获取的内容的信任。恶意脚本在受害者的浏览器中得以运行,因为浏览器信任其内容来源,即使有的时候这些脚本并非来自于它本该来的地方。CSP通过指定有效域——即浏览器认可的可执行脚本的有效来源—......
  • CSP历年复赛题-P1075 [NOIP2012 普及组] 质因数分解
    原题链接:https://www.luogu.com.cn/problem/P1075题意解读:求n的两个素因子中较大的一个。解题思路:数论的简单题,关键在于要知道一定有一个素因子不超过sqrt(n),而另一个素因子必然大于或等于sqrt(n),这样才能减少枚举时间。100分代码:#include<bits/stdc++.h>usingnamespaces......
  • WEB安全:Content Security Policy (CSP) 详解
    ContentSecurityPolicy(CSP)是一种强大的网页安全机制,用于防止跨站脚本(XSS)和其他注入攻击。通过设置一系列的内容安全策略,CSP可以限制网页可以加载的资源,从而保护用户数据和网站的安全性。什么是XSS攻击?跨站脚本攻击(XSS)是一种常见的安全漏洞,攻击者通过注......
  • CSP历年复赛题-P1310 [NOIP2011 普及组] 表达式的值
    原题链接:https://www.luogu.com.cn/problem/P1310题意解读:+代表按位或运算,*代表按位与运算,给定一个没有填数字的表达式,要求结果为0的数字方案数。解题思路:下面一步一步,由浅入深的来解决本题思路一(20分做法):观察得知,20%的数据,只有10个符号,且没有括号,也就是对应数字最多11个,可以......
  • CSP历年复赛题-P1308 [NOIP2011 普及组] 统计单词数
    原题链接:https://www.luogu.com.cn/problem/P1308题意解读:给定单词a,文本b,在b中找a的个数,并找a第一次出现的位置,注意b中任何位置可能含有多个连续空格。解题思路:通过双指针找b中每一个单词的首、尾位置i,j,与a进行一一比较即可。注意1:比较时不考虑大小写,可以统一转成小写字符tolo......
  • CSP历年复赛题-P1199 [NOIP2010 普及组] 三国游戏
    原题链接:https://www.luogu.com.cn/problem/P1199题意解读:人机轮流选将,电脑策略就是破坏可能和人已选能组成最大默契值的将,问人是否必胜,求出站的一对武将的默契值。解题思路:贪心题通常比较难以下手,经过分析,人肯定不可能选到每一行的最大默契值,因为电脑会破坏;进一步思考,那人能......