D-Cleaning
codeforces696D
题意
题目意思大致是给你n堆石子,你的任务是判断是否能把所有石子清除。然后给你两种操作。
- 选两堆相邻的石子,同时数量减一
- 交换两个相邻石子堆的数量(只能用一次)
接下来我们都用这组样例来解释
$a=(21,19,16,30,16)$
首先我们想想如果不给你交换的权力,你能在$O(N)$时间判断yes or no吗?
可以发现$a[1]$要清0只能靠$a[2]$,当$a[1]$清0后剩下的序列又构成了前面的规律,最后只要看a[n]是否等于0即可。
for (int i = 1; i < n; i++) {
if (a[i + 1] >= a[i]) {
a[i + 1] -= a[i];
a[i] = 0;
} else {
is_valid = false;
break;
}
}
if(!a[n])
cout << "YES" << endl;
else
cout << "NO" << endl;
根据之前的规律我们可以构建一个$s$数组来看$a[i]$对$a[i+1]$的贡献。
$s[i]=a[i]-s[i-1]$
$s=(21,-2,18,12,4)$
可以看出来如果$s[i]<0$那么意味着$a[i+1]$是不够减剩下的$a[i]$的,这就会导致石子>0。
所以我们可以明显想到如果要让所有石子清0,需要满足以下条件:
- $s[i]>=0$
- $s[n]==0$
接着我们思考下当发生交换时,$s$数组的变化是怎么样的。
首先看$s$数组的构建:
$s[1]=a[1]$
$s[2]=a[2]-a[1]$
$s[3]=a[3]-a[2]+a[1]$
$s[4]=a[4]-a[3]+a[2]-a[1]$
$s[5]=a[5]-a[4]+a[3]-a[2]+a[1]$
假设我们交换$a[1]$和$a[2]$。$a[1]=21-2,a[2]=19+2$
$s[1]=a[1]-2$
$s[2]=a[2]-a[1]+4$
$s[3]=a[3]-a[2]+a[1]-4$
$s[4]=a[4]-a[3]+a[2]-a[1]+4$
$s[5]=a[5]-a[4]+a[3]-a[2]+a[1]-4$
可以看到除了交换那个数,其他都是随着奇数偶数交替的同个值。
回到之前所说的两个条件:
首先要让$s[n]==0$
也就是要找到一个交换能使后面的$s[n]-=s[n]$
这个其实很简单,和$n$同奇偶提供正贡献,和$n$异奇偶提供负贡献。
并且找到$abs(a[i+1]-a[i])==abs(s[n]/2)$就行了
第二个条件,假设找到的交换贡献使$s[i]$产生负数了也就是之前说的另一个条件$s[i]>=0$怎么办?那么我们只能在产生负贡献前和$n$之后找到满足的交换$(idx)$。
代码如下
for (int i = n; i > 1; i--) {//找idx
int tmp = s[i];
if (i % 2 == n % 2)
tmp -= s[n];
else
tmp += s[n];
if (tmp < 0) {
idx = i;
break;
}
}
for (int i = idx; i < n; i++) {
if (i % 2 == n % 2) {
if (a[i + 1] - a[i] == -s[n] / 2) {
if (s[i] - s[n] / 2 >= 0) {//注意是s[i]自身受到的贡献只有交换的贡献,也就是其他贡献的一半
swap(a[i], a[i + 1]);
break;
} //没把break括进去,卡了好久
}
} else {
if (a[i + 1] - a[i] == s[n] / 2) {
if (s[i] + s[n] / 2 >= 0) {
swap(a[i], a[i + 1]);
break;
}
}
}
}
最后在通过线性时间验证是否能清除所有石子即可。
完整代码如下:
/*
Problem Name:Cleaning
algorithm tag:constructive problem(构造题)
*/
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <unordered_map>
#include <vector>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int INF = 1e9;
typedef pair<int, int> pii;
const int N = 2e5 + 5;
int t;
int n;
int a[N];
int s[N];
int main()
{
cin >> t;
while (t--) {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
int last = 0;
for (int i = 1; i <= n; i++) {
s[i] = a[i] - last;
last = s[i];
}
int idx = 1;
for (int i = n; i > 1; i--) {
int tmp = s[i];
if (i % 2 == n % 2)
tmp -= s[n];
else
tmp += s[n];
if (tmp < 0) {
idx = i;
break;
}
}
for (int i = idx; i < n; i++) {
if (i % 2 == n % 2) {
if (a[i + 1] - a[i] == -s[n] / 2) {
if (s[i] - s[n] / 2 >= 0) {
swap(a[i], a[i + 1]);
break;
} //没把break括进去,卡了好久
}
} else {
if (a[i + 1] - a[i] == s[n] / 2) {
if (s[i] + s[n] / 2 >= 0) {
swap(a[i], a[i + 1]);
break;
}
}
}
}
bool is_valid = true;
for (int i = 1; i < n; i++) {
if (a[i + 1] >= a[i]) {
a[i + 1] -= a[i];
a[i] = 0;
} else {
is_valid = false;
break;
}
}
if (is_valid && !a[n])
cout << "YES" << endl;
else
cout << "NO" << endl;
}
}