Description
给出一个初始序列 $a$ 和一个目标序列 $b$，你可以对 $a$ 中的除去第一个和最后一个点之外的任意一个点 $i$ ，让 $a_i$ 变成 $a_{i-1}+a_{i+1}-a_i$ 。问是否能够通过若干次操作使得 a 变成 b
序列长度 $n \leq 10^5$
Solution
我觉得这个题应该放在 A
考虑一个序列 : a|b|c
对 b 进行操作：a|a+c-b|c
他的差分序列原来是：a-b | b-c
现在变成了：b-c | a-b
所以一次操作相当于是把差分数组里的相邻两个数给交换了位置
所以只用判断目标序列的差分数组排序后是否等于初始序列的差分数组
还有第一个数相不相等（比赛的时候没考虑这个 wa 了一发…）
时间复杂度瓶颈在排序（或者说判断相同）
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| #include <bits/stdc++.h>
using namespace std;
const int N = 100100;
int n, a[N], b[N];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= n; i++) scanf("%d", &b[i]);
if(a[1] != b[1]) { printf("No\n"); return 0; }
for(int i = 1; i < n; i++) a[i] = a[i + 1] - a[i];
for(int i = 1; i < n; i++) b[i] = b[i + 1] - b[i];
sort(a + 1, a + n), sort(b + 1, b + n);
for(int i = 1; i < n; i++)
if(a[i] != b[i]) {
printf("No\n");
return 0;
}
printf("Yes\n");
return 0;
}
|