本题主要靠结论

12pt

爆搜

时间复杂度\(O(n^n)\)

36pt

\(f_{i,j}表示前i个数由状态j转移过来,a_i表示前缀和\)

\(So,f_{i,j}=f_{j,k}+(a_i-a_j)^2\ \ \ \ \ \ \ (a_j-a_k\leq a_i-a_j)\)

时间复杂度\(O(n^3)\)

64pt

我们发现，在\(i\)变大过程中，每个\(j\)对应的\(k\)也只会变大，所以用一个\(g_j\)表示当前\(j\)状态的\(k\)动到哪儿了,再配合后缀最小值均摊转移\(O(1)\)

时间复杂度\(O(n^2)\)

100pt

结论：当\(j\)一定时取\(k\)最大的,并且要合法。

证明

所以：\(f_i=min \{f_j+(a_i-a_j)^2\}\ \ \ \ \ \ \ \ \ \ (a_j-a_{g_j} \leq a_i-a_j)\)

我们把条件变换一下\(\Rightarrow\) \(2*a_j-a_{g_j}\leq a_i\),发现可以用单调队列优化

\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)

#include<cstdio>

#include<algorithm>

using namespace std;

# define Type template<typename T>

# define read read1<int>()

Type inline T read1()

{

	T t=0;

	bool ty=0;

	char k;

	do k=getchar(),(k=='-')&&(ty=1);while('0'>k||k>'9');

	do t=(t<<3)+(t<<1)+(k^'0'),k=getchar();while('0'<=k&&k<='9');

	return ty?-t:t;

}

# define fre(k) freopen(k".in","r",stdin);freopen(k".out","w",stdout)

# define ll long long

# define I128 __int128

int s,p[100001],l[100001],r[100001],g[40000001],q[40000001];

# define ret(n) (a[n]*2-a[g[n]])

ll a[40000002];

bool ty;

void into()

{

	s=read;ty=read;

	if(!ty)for(int i=0;i++^s;)a[i]=read;

	else

	{

		ll x=read,y=read,z=read;

		int now=0,b[2];

		b[0]=read,b[1]=read;

		int m=read;

		for(int i=0;i++^m;p[i]=read,l[i]=read,r[i]=read);

		for(int i=0;i++^s;)

		{

			while(p[now]<i)++now;

			if(i<=2)a[i]=b[i-1]%(r[now]-l[now]+1)+l[now];

			else

			{

				b[0]^=b[1]^=(b[0]=(y*b[0]+x*b[1]+z)%(1<<30))^=b[1];

				a[i]=b[1]%(r[now]-l[now]+1)+l[now];

			}

		}

	}

}

void work()

{

	int l=0,r=0;

	for(int i=0;i++^s;a[i]+=a[i-1]);

	for(int i=0;i++^s;)

	{

		while(l<r&&ret(q[l+1])<=a[i])++l;

		g[i]=q[l];

		while(l<r&&ret(q[r])>=ret(i))--r;

		q[++r]=i;

	}

	I128 ans=0;

	while(s)ans+=(I128)(a[s]-a[g[s]])*(a[s]-a[g[s]]),s=g[s];

	r=0;

	do

	{

		q[++r]=ans%10;

		ans=ans/10;

	}while(ans);

	do

	{

		printf("%d",q[r]);

	}while(--r);

}

int main()

{

	//fre("partition");

	into();

	work();

	return 0;

}

巴特西

Csp-s2019 划分

本题主要靠结论

12pt

爆搜

时间复杂度\(O(n^n)\)

36pt

\(f_{i,j}表示前i个数由状态j转移过来,a_i表示前缀和\)

时间复杂度\(O(n^3)\)

64pt

我们发现，在\(i\)变大过程中，每个\(j\)对应的\(k\)也只会变大，所以用一个\(g_j\)表示当前\(j\)状态的\(k\)动到哪儿了,再配合后缀最小值均摊转移\(O(1)\)

时间复杂度\(O(n^2)\)

100pt

证明

所以：\(f_i=min \{f_j+(a_i-a_j)^2\}\ \ \ \ \ \ \ \ \ \ (a_j-a_{g_j} \leq a_i-a_j)\)

我们把条件变换一下\(\Rightarrow\) \(2*a_j-a_{g_j}\leq a_i\),发现可以用单调队列优化

\(\mathfrak{Talk\ is\ cheap,show\ you\ the\ code.}\)

最新文章

热门文章