HEOI2014 南园满地堆轻絮

wjh15101051's space

卧薪尝胆，厚积薄发。

HEOI2014 南园满地堆轻絮

Date: Tue Sep 25 16:04:54 CST 2018

In Category: NoCategory

Description：

给一个长为 $n$ 的数列，改动一些位置使得数列单调不降，最小化单个位置改变量的最大值。

$1\leqslant n \leqslant 5\times 10^6$

Solution：

答案其实就是差最大的逆序对的差的二分之一。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,sa,sb,sc,sd,a1,mod;

int f(int x){return (1ll * sa * x % mod * x % mod * x % mod + 1ll * sb * x % mod * x % mod + 1ll * sc * x % mod + sd) % mod;}

int main()

{

	scanf("%d%d%d%d%d%d%d",&n,&sa,&sb,&sc,&sd,&a1,&mod);

	int maxrev = 0;

	int maxv = a1;

	int pre = a1,ppre = 0;

	int cur = 0;

	for(int i = 2;i <= n;++i)

	{

		cur = (f(pre) + f(ppre)) % mod;

		maxrev = max(maxrev,maxv - cur);

		maxv = max(maxv,cur);

		ppre = pre;pre = cur;

	}

	cout << (maxrev + 1) / 2 << endl;

	return 0;

}

In tag: 玄学

wjh15101051