P1982 [NOIP2013 普及组] 小朋友的数字

· · 题解

本blog包含：

告别高精__int128

啊？我当年居然没抄题解吗？？？

前言写得又臭又长写给谁看啊

题目链接

通过记录

前言：

太离谱了！！！2022.10.9集训期间考试考了这道题，我读错了题，爆零了。然后考完重新读题，感觉做不起了，机房好多大佬也在讨论是写__int128好还是高精好。然后我打算看洛谷题解。结果：

WTM在2018年就AC了这道题，还是一遍过！！！

这不对吧，4年前我才刚刚学OI啊。虽然说是普及组的题，也不可能一遍过吧。

然后我就去翻了洛谷现存的16篇题解，没有一个一样，甚至没有一个相像！

我当场去搜索CSDN，WOW，居然也没有像的。

然后我就开始把当年的码改成我现在的码风。结果惊讶的发现：

1.当年不会快读甚至不会scanf，于是写的cin，cout（是的，过得了洛谷过不了加强数据）。 2.不会define，全篇long long老老实实写的。

3.一个用来判断、标记变量名直接取名pd，以为判断（这个习惯现在都还没改，经常命名为bj（标记）,pd（判断），hf（合法））。

4.当年不熟悉bool（真的是刚学OI），上面说的那个pd都是用的int存的。

结论：我没抄题解，而且刚学OI的2018年的我薄纱现在的我！！！

我加了快读 register O2，手写max，甚至最优解挤进了第一页！！

去重第15合影留念

WTF

题目描述

  有 n 个小朋友，每人给定一个数。每人一个特殊值，第一个的就是那个给定数，其他的则是在他之前的（包括自己）连续几个小朋友“给定数”的和最大的那个“和”。

  然后每个小朋友有一个分数，第一个小朋友的分数就是给定数也是特殊值。之后每个小朋友的分数是在他之前（不含自己）的所有小朋友中，那些小朋友特殊值+分数最大的那个，就是他的分数了。

WTF好绕好绕

算法思路

  很明显，本题分为两个部分：1.计算特殊值。2.计算分数。

  先说简单的。当我们记录完特殊值之后，求分数直接走一个记一个最大值就行了。一个分数最大，一个“分数+特殊值”最大。

  那么怎么求特殊值。首先暴力好像，就是挨个算。但明显这个就是个前缀维护就好，很容易想到。

  对啊，就一个前缀，去维护这个“最大给定数和”，连着的正数就加进去，完了记个maxn方便记录特殊值，解决了啊。有什么难的？？？

特殊处理

难点在这里：

  在普及组时，最经典的就是被卡int。于是也有“十年OI一场空，不开long long见祖宗”的说法。现在我们机房基本上都会写个define 一个long long。

  但这题就喜剧了，他不仅卡int，long long他还刚好存不下！！

  选择1：涉及到ans，和的，选择用__int128来存储。

  选择2：你了不起，你清高，你普及组写高精。

  选择3：一个一个记，从上一个转移，既然是一个一个转移（贪心捏），那我就边存边模嘿嘿。取模之后的判断大小正确性？反正数据范围说单个数都是小于 1e9 的，那我就等到大于 1e9 了我再取模，捏嘿。（我当年是怎么整出这么骚的想法的啊）

代码实现

这篇2018年的漏洞百出的代码，我自己都差点没看懂

#pragma GCC optimize(2)//抢别人家评测机最优解用的O2
#include<bits/stdc++.h>
using namespace std;

#define int long long//祖宗：嗨害嗨
#define ri register int//大爷来卡常啊

int a[1000001][4];//分别存储：特殊值，给定数，贪的分数
//我也不知道我当年为什么非要开成二维数组，开四个一维不好吗？

inline int rd()//过强化数据必备
{
    int a=0,f=1;
    char c=getchar();
    for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=-1;
    for(; c>='0'&&c<='9'; c=getchar()) a=(a<<1)+(a<<3)+c-'0';
    return a*f;
}

inline int Max(int a,int b){if(a>b)return a;else return b;}
//卡常一下又何妨
signed main() 
{
    int n,p,maxn;
    n=rd(),p=rd();

    int x;
    x=rd();
    a[1][1]=x;
    a[1][0]=x;

    maxn=x;
    for(ri i=2;i<=n;i++) //计算特殊值
    {
        x=rd();

        if(a[i-1][1]>0)
            a[i][1]=a[i-1][1]+x;//之前是正数就加了
        else 
            a[i][1]=x;//负数？那就从现在开始

        a[i][0]=Max(maxn,a[i][1]);//维护前缀最大和

        maxn=a[i][0];
    }

    int pd=0;//正确的，这里应该开bool
    a[1][2]=a[1][0];
    a[2][2]=2*a[1][0];

    if(a[2][2]>=a[1][2])
        pd=1;//毕竟从下面是第三位开始，那这里判一下第二位

    for(ri i=3;i<=n;i++) 
    {
        if(a[i-1][0]<0)
            a[i][2]=a[i-1][2];//正数就给我贪过来
        else 
        {
            a[i][2]=a[i-1][2]+a[i-1][0];//特殊值加上来的干活

            if(a[i][2]>a[1][2]) 
                pd=1;

            if(a[i][2]>1000000000)//究极防爆盾
                a[i][2]%=p;
        }
    }

    if(pd==1)
        printf("%lld\n",a[n][2]%p);//上面可不一定取了模的，最后确保一下
    else
        printf("%lld\n",a[1][2]%p);

    return 0;
}