题解：P13822 「Diligent-OI R2 B」白露为霜_奇偶性_数学归纳_算法竞赛C++

总感觉这个套路在哪见过。

考虑任意两对相邻的数差值都是 $1$，其实就相当于任意两对相邻的数奇偶性不同。奇偶性可以用对二取模来刻画，所以不妨令 $a_i\leftarrow a_i\mathrm{mod}2,b_i\leftarrow b_i\mathrm{mod}2$。

如果做题够多，可能会有一个感觉：输出 Yes 的条件可能是 $\forall 1\le i\le n,a_i\equiv b_i(\text{mod}2)$。

简单地证明一下：

• 必要条件证明（若可转换则奇偶性相同）：$\$
  因为 $a,b$ 都是折线，且每次修改只能修改一个数，所以修改后 $a$ 也依然为折线，即修改后每个 $a_i$ 的奇偶性不变。所以只有初始时 $a,b$ 奇偶性相同，才能保证 Yes。
• 充分条件证明（奇偶性相同时可以转换）：$\$
  考虑构造一种合法的操作方法。先从第一个元素开始调整：$a_1^{\prime }=b_1$；然后数学归纳：假设前 $k$ 个元素已经调整为 $b_1,\dots ,b_k$，则对于第 $k+1$ 个元素：$|a_k^{\prime }-a_{k+1}^{\prime }|=1\Rightarrow a_{k+1}^{\prime }=a_k^{\prime }\pm 1$，由于 $b_{k+1}$ 与 $b_k$ 奇偶性相反，且 $b_k=a_k^{\prime }$，总能找到合适的 $a_{k+1}^{\prime }$ 使其等于 $b_{k+1}$。

请注意：

1. 本题轻微卡常，建议使用更快的读入方式。
2. 别忘了特判当 $n=1$ 时答案始终为 Yes。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;void solve()
{int n; cin >> n;vector<int> a(n), b(n);generate(a.begin(), a.end(), [](){ int x; cin >> x; return x; });generate(b.begin(), b.end(), [](){ int x; cin >> x; return x; });if(n == 1){cout << "Yes\n"; return ;}for(int i = 0; i < n; i ++){if((a[i] & 1) != (b[i] & 1)){cout << "No\n"; return ;}}cout << "Yes\n";
}signed main()
{ios :: sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);int T; cin >> T;while(T --) solve();return 0;
}