小朋友的数字 方法记录

时间:2022-10-09 18:04:45

原题链接

题目描述

\(n\) 个小朋友排成一列。每个小朋友手上都有一个数字,这个数字可正可负。规定每个小朋友的特征值等于排在他前面(包括他本人)的小朋友中连续若干个(最少有一个)小朋友手上的数字之和的最大值。

作为这些小朋友的老师,你需要给每个小朋友一个分数,分数是这样规定的:第一个小朋友的分数是他的特征值,其它小朋友的分数为排在他前面的所有小朋友中(不包括他本人),小朋友分数加上其特征值的最大值。

请计算所有小朋友分数的最大值,输出时保持最大值的符号,将其绝对值对 \(p\) 取模后输出。

输入格式

第一行包含两个正整数 \(n,p\),之间用一个空格隔开。

第二行包含 \(n\) 个数,每两个整数之间用一个空格隔开,表示每个小朋友手上的数字。

输出格式

一个整数,表示最大分数对 \(p\) 取模的结果。

样例 #1

样例输入 #1

5 997
1 2 3 4 5

样例输出 #1

21

样例 #2

样例输入 #2

5 7
-1 -1 -1 -1 -1

样例输出 #2

-1

提示

【样例解释 #1】

小朋友的特征值分别为 \(1,3,6,10,15\),分数分别为 $ 1,2,5,11,21$,最大值 \(21\)\(997\) 的模是 \(21\)

【样例解释 #2】

小朋友的特征值分别为 \(-1,-1,-1,-1,-1\),分数分别为\(-1,-2,-2,-2,-2\),最大值 \(-1\)\(7\) 的模为 \(-1\),输出 \(-1\)

【数据范围】

对于 \(50\%\) 的数据,\(1 \le n \le 1000\)\(1 \le p \le 1000\),所有数字的绝对值不超过 \(1000\)

对于 \(100\%\) 的数据,\(1 \le n \le {10}^6\)\(1 \le p \le {10}^9\),其他数字的绝对值均不超过 \({10}^9\)

题解

我们首先来分析小朋友的三个指标:手里的数,特征值,分数。

手里的数:即我们输入的长度为\(n\)的序列;

特征值:从第一个小朋友到当前小朋友的 手上的数最大子段和

分数:当前小朋友前面的小朋友中 小朋友特征值和分数的和 的最大值(第一个小朋友的分数等于其特征值)。

这个问题可以拆分成两个子问题。

一、求每个小朋友对应的最大子段和

最大子段和模板题

最大子段和的核心思想

1.第一个数是一个有效子段。

2.如果 一个数加上上一个有效子段 的结果 大于 这个数,那么 这个数属于上一个有效子段。

3.如果 一个数加上上一个有效子段 的结果 小于 这个数,那么 这个数成为一个新的有效子段。

	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&hand);//hand是输入的手里的数 
		if(i==1) tmp[i]=hand;//tmp[]记录子段 
		else tmp[i]=maxx(hand,tmp[i-1]+hand);//取hand是第3种情况,取tmp[i-1]+hand是第2种情况 
		sub=maxx(sub,tmp[i]);//sub是第i个小朋友对应的最大子段和(特征值) 
		stu[i].spl=sub;
	}

注意

sub=maxx(sub,tmp[i]);
stu[i].spl=sub;

不能写成

stu[i].spl=maxx(stu[i].spl,tmp[i]);

\(sub\)后续还会用到,所以需要持久地保存下来。

二、线性统计所有小朋友分数的最大值

第一个小朋友的分数就是其特征值。

第二个小朋友前面只有一个小朋友,所以第二个小朋友的分数就是第一个小朋友分数和特征值之和。

……

记录当前小朋友的分数为\(x\),那么下一个小朋友的分数就是 \(x\)、下一个小朋友与\(x\)的和 的最大值。、

stu[1].sco=stu[1].spl;
	x=stu[1].sco+stu[1].spl;
	ans=stu[1].sco;
	for(int i=2;i<=n;i++)
	{
		stu[i].sco=x;
		x=maxx(x,stu[i].spl+stu[i].sco);
		ans=maxx(ans,stu[i].sco);
	}

考虑到数据范围导致运算时会出现超过\(long long\)的值,所以可以使用__128来声明参与运算的变量,注意输入输出不能用__128。

AC代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const __int128 N=1000005;
const __int128 inf=2147483647;
ll n,p,hand;
__int128 x,ans;
struct student
{
	__int128 spl,sco;
}stu[N];
__int128 tmp[N];
__int128 maxx(__int128 a,__int128 b)
{
	return a>b?a:b;
}
__int128 sub=-inf;
ll final;
signed main()
{
	//freopen("number.in","r",stdin);
	//freopen("number.out","w",stdout);
	scanf("%lld%lld",&n,&p);
	for(int i=1;i<=n;i++)
	{
		scanf("%lld",&hand);//hand是输入的手里的数 
		if(i==1) tmp[i]=hand;//tmp[]记录子段 
		else tmp[i]=maxx(hand,tmp[i-1]+hand);//取hand是第3种情况,取tmp[i-1]+hand是第2种情况 
		sub=maxx(sub,tmp[i]);//sub是第i个小朋友对应的最大子段和(特征值) 
		stu[i].spl=sub;
	}
	stu[1].sco=stu[1].spl;
	x=stu[1].sco+stu[1].spl;
	ans=stu[1].sco;
	for(int i=2;i<=n;i++)
	{
		stu[i].sco=x;
		x=maxx(x,stu[i].spl+stu[i].sco);
		ans=maxx(ans,stu[i].sco);
	}
	if(ans>=0)
	{
		ans=ans%p;
		final=ans;
		printf("%lld",final);
	}
	else
	{
		ans=-ans;
		ans=ans%p;
		final=ans;
		printf("-%lld",final);
	}
	return 0;
}