【GDOI2018 Day1】密码锁题解

【GDOI2018 Day1】密码锁

Description

在这里插入图片描述

Input

在这里插入图片描述

Output

在这里插入图片描述

Sample Input

Sample Input1
4 3
1 2 1 0

Sample Input2
11 8
1 2 3 4 5 0 5 4 3 2 1

Sample Input3
20 100
30 91 15 72 61 41 10 37 98 41 94 80 26 96 10 88 59 5 84 14

Sample Output

Sample Output1
2

Sample Output2
8

Sample Output3
313

Data Constraint

在这里插入图片描述

题解

考场这题我打了100行的暴力，记忆化搜索加剪枝 ~~（鬼知道我怎么做得到的）~~
这题乍一看似乎没什么思路，但我们换个方向来想，如果把(n)个数在模(m)的意义下差分一下（再最后补一个(a[n+1])与(a[n])）差分，那么如果我们想要把(a)数组全部变成0，也就相当于把差分数组（假设是(cf[i])）全部变成0
然后我们又知道，在差分数组修改一段区间([l,r])时（假设是加1），是将(cf[l]+1,cf[r+1]-1)，然后减1就是反过来将(cf[l]-1,cf[r+1]+1)，又因为本题的(cf[i])是在模(m)的意义下的，所以一个(cf[i])加到(m)或者减到0的结果都是0
于是想法就很显然了，将差分数组排序，前半段的显然减到0更优，后半段的显然加到(m)更优，所以我们可以维护(cf[i])的前缀和(sum1[i])，维护(m-cf[i])的前缀和(sum2[i])，然后枚举分割加和减的点，如果这个点的前缀和这个点下一个点和后缀和相同，那么也就是说前半段减和后半段加可以抵消，将所有差分数组在模(m)意义下修改到0，那么这个点的前缀和或者这个点下一个点的后缀和即为答案

CODE

#include<cstdio>
#include<string>
#include<algorithm>
#define max(a,b) (((a)>(b))?(a):(b))
#define min(a,b) (((a)<(b))?(a):(b))
#define R register int
#define N 1000005
#define ll long long
using namespace std;
ll n,m,a[N],cf[N],sum1[N],sum2[N];
inline void read(ll &x)
{
	x=0;ll f=1;char ch=getchar();
	while (!isdigit(ch)) {if (ch=='-') f=-1;ch=getchar();}
	while (isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();x*=f;
}
int main()
{
	freopen("lock.in","r",stdin);
	freopen("lock.out","w",stdout);
	read(n);read(m);
	for (R i=1;i<=n;++i)
		read(a[i]),cf[i]=(a[i]-a[i-1]+m)%m;
	cf[n+1]=(a[n+1]-a[n]+m)%m;
	sort(cf+1,cf+n+2);
	for (R i=1;i<=n+1;++i)
		sum1[i]=sum1[i-1]+cf[i];
	for (R i=n+1;i;--i)
	{
		sum2[i]=sum2[i+1]+m-cf[i];
		if (sum2[i]==sum1[i-1]) {printf("%lld
",sum2[i]);return 0;}
	}
	return 0;
}