位位運算 方法記錄

• 2022 年 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;
}