GMOJ4788. 序列

发表于 | 更新于: | 分类于

Description

有一个包含 n 个整数的序列$A: A_1, A_2, \ldots, A_n$，还有一个包含 n 个整数的序列$B: B_1, B_2, \ldots, B_n$
在一次操作中，可以选择两个下标 i 和 j ($1 \leq i \leq j \leq n$)，然后把所有$A_i$到$A_n$之间的元素（包含），增加1之后模4。
现在求将$A$数组转换成$B$，至少要执行多少次操作。

Input

输入数据的第一行包含一个整数T表示数据组数。对于每组数据，第一行有一个整数，分别表示 n 。接下来两行，第一行包含 n 个数字$A_1, A_2, \ldots, A_n$，第二行包含 n 个数字$B_1, B_2, \ldots, B_n$

Output

对于每组数据，输出一行表示对应的答案。

Sample Input

1
5
2 1 3 0 3
2 2 0 1 0

Sample Output

1

Data Constraint

$1 \leq T \leq 10$
$0 \leq A_i，B_i \leq 3$
对于10%的数据满足，$n \leq 30$
对于30%的数据满足，$n \leq 100$
对于50%的数据满足，$n \leq 1000$
对于60%的数据满足，$n \leq 10000$
对于100%的数据满足，$n \leq 100000$

100%解法

转自扩展の灰，略作修改。
我们可以先考虑不存在Mod 4 的情况，假设$d_i=max(0，b_i-a_i)$
那么显然，对于一个位置 i ，我们需要将其操作$max(0，di)$次
考虑从1开始，我们设$f[i]$表示将1到 i 的 d 清零所需要的最小次数。
显然，$f[1]=d[1]$，$f[i]=f[i-1]+max(0，d[i]-d[i-1])$，这是一个差分的经典应用。
现在我们来考虑Mod 4的情况，由于有Mod 4 的影响，我们可以将一系列的$d[i]$变为$d[i]+4k$。
这样在一种情况下会减小答案。
若有$i<j$使得$d[i]-d[i-1]+4<d[j]-d[j-1]$，那么，我们就可以将整个$[i,j-1]$的d都加上4
这样答案就可以减少$(d[i]-d[i-1]+4-d[j]+d[j-1])$
实际上，我们只需要维护$d[i]-d[i-1]$ = -2和-3的个数即可。（-1+4=3，0+4=4显然都不可能）
每次都贪心地去取就可以。
记得如果贪心到$d[i]-d[i-1]=-3$而且$d[j]-d[j-1]
=2$时要把$d[i]-d[i-1] = -2$的个数加一，因为后面如果有k满足$d[k]-d[k-1]$=2或3的话把 j 用 k 替换掉是可以更优的。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int t, n, a[100010], num[4], ans = 0, b;
int main()
{
	scanf("%d", &t);
	while (t)
	{
		ans = 0;
		memset(num, 0, sizeof num);
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
		for (int i = 1; i <= n; i++)
			scanf("%d", &b), a[i] = (b - a[i] + 4) % 4;
		for (int i = n; i >= 1; i--) a[i] -= a[i - 1];
		for (int i = 1; i <= n; i++)
		{
			ans += max(a[i], 0);
			if (a[i] < 0) num[a[i] + 4]++;
			if (num[1] && a[i] > 1) num[1]--, num[a[i]]++, ans -= a[i] - 1;
			else if (num[2] && a[i] > 2) num[2]--, ans -= a[i] - 2;
		}
		printf("%d\n", ans);
		t--;
	}
	return 0;
}