题解：P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方

P11643题解

可以发现每次操作就是对一个子数组加上或减去一个回文的先递减、后递增的另一个数组。
针对上面的结论，先考虑只操作一次。为方便，操作前全部数字为 $1$ ，且先考虑加法。我们把操作前后的差值 $\Delta$ 也列举出来。

操作前	1	1	1	1	1	1
操作后	4	3	2	2	3	4
$\Delta$	3	2	1	1	2	3

特别地，数组 1 1 操作后为 2 2，都是加上了

1

。这里有一个技巧：将大的操作转化为小的操作！

例如，对于刚才表格的操作，我们也可以看成是：

操作前	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 操作。

我们也可以把这个单独的操作反过来！

对于差值：

$\Delta$	3	2	1	1	2	3

第一个 3 是操作前的数组加上的，现在我们让它“减回来”。由于刚才说了，操作可以看成是两个数单独做加一减一操作，所以我们让第二个数字 2 减去

3

。

我们看看这个表格：

$\Delta$	2	1	1	2	3
1和2	-1	1	1	2	3
2和3	0	2	1	2	3
3和4	0	0	-1	2	3
4和5	0	0	0	3	3
5和6	0	0	0	0	0

最终这个“差值”数组全部都为

0

。这是因为我们可以将题目给定的操作“反着”进行一遍。

相反，如果最终不为

0

，则不能按照题目要求进行操作。

代码

CPP

#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";
    }
}

题解：P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方

文章操作

P11643题解

代码

相关推荐

评论

题解：P11643 【MX-X8-T2】「TAOI-3」终有一天，飞向水平线的彼方