题解：P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方
P11643题解
- 可以发现每次操作就是对一个子数组加上或减去一个 回文 的先递减、后递增的另一个数组。
- 针对上面的结论，先考虑只操作一次。为方便，操作前全部数字为
1 ，且先考虑加法。我们把操作前后的差值\Delta 也列举出来。
| 操作前 | 1 | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|
| 操作后 | 4 | 3 | 2 | 2 | 3 | 4 |
| 3 | 2 | 1 | 1 | 2 | 3 |
特别地，数组 1 1 操作后为 2 2，都是加上了
例如，对于刚才表格的操作，我们也可以看成是：
| 操作前 | 1 | 1 | 1 | 1 | 1 | 1 |
|---|---|---|---|---|---|---|
| 第一次操作 | 4 | 4 | 4 | 4 | 4 | 4 |
| 第二次操作 | 4 | 3 | 3 | 3 | 3 | 4 |
| 第三次操作 | 4 | 3 | 2 | 2 | 3 | 4 |
所以，我们可以把一次“集体加”的操作看成是全部加上，然后中间在单独减。每个“大”操作都可以拆分成若干个 1 1 操作。
我们也可以把这个单独的操作反过来！
对于差值：
| 3 | 2 | 1 | 1 | 2 | 3 |
|---|
第一个 3 是操作前的数组加上的，现在我们让它“减回来”。由于刚才说了，操作可以看成是两个数单独做加一减一操作，所以我们让第二个数字 2 减去
我们看看这个表格：
| 3 | 2 | 1 | 1 | 2 | 3 | |
|---|---|---|---|---|---|---|
| 1和2 | 0 | -1 | 1 | 1 | 2 | 3 |
| 2和3 | 0 | 0 | 2 | 1 | 2 | 3 |
| 3和4 | 0 | 0 | 0 | -1 | 2 | 3 |
| 4和5 | 0 | 0 | 0 | 0 | 3 | 3 |
| 5和6 | 0 | 0 | 0 | 0 | 0 | 0 |
最终这个“差值”数组全部都为
相反，如果最终不为
代码
#include <bits/stdc++.h>
using namespace std;
long long a[100010], b[100010], delta[100010];
int main()
{
int t; cin >> t;
while (t--)
{
int n; cin >> n;
for (int i=1; i<=n; i++) cin >> a[i];
for (int i=1; i<=n; i++) cin >> b[i];
for (int i=1; i<=n; i++) delta[i] = b[i] - a[i];
for (int i=1; i<n; i++) delta[i+1] -= delta[i];
if (delta[n]) cout << "No\n";
else cout << "Yes\n";
}
}