自动搬运

查看原文

来自洛谷，原作者为

	rui_er 九万里风鹏正举

搬运于2025-08-24 22:51:05，当前版本为作者最后更新于2023-09-21 19:13:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这里是官方题解。

记数列 $a$ 的倒序为 $\bar{a}$，记两个数列 $a,b$ 对应元素相加得到的新数列为 $a+b$。操作一即为 $t\gets t+\bar{t}$，操作二即为 $a\gets a+t$。

考察一次操作一对 $t$ 的影响，此时 $t$ 变为 $[t_1+t_n,t_2+t_{n-1},\cdots,t_{n-1}+t_2,t_n+t_1]$，成为回文数列（即 $t=\bar{t}$）。此后再进行操作一是没有意义的，因为 $t+\bar{t}=t+t$，再进行一次操作一后进行操作二，等价于直接进行两次操作二。

至此，我们证明了操作一最多进行一次。

我们枚举在唯一一次操作一之前进行了几次操作二，可以得到此时的 $a$ 和 $t$，容易检查是否可能再进行若干次操作二，使得 $a=b$。

时间复杂度 $O(nw)$，其中 $w$ 为值域。

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x,y,z) for(int x=(y);x<=(z);x++)
#define per(x,y,z) for(int x=(y);x>=(z);x--)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do{freopen(s".in","r",stdin);freopen(s".out","w",stdout);}while(false)
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(x > y) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

const int N = 2e3+5;

int T, n, t[N], b[N], a[N], s[N];

int main() {
    for(scanf("%d", &T); T; T--) {
        scanf("%d", &n);
        rep(i, 1, n) scanf("%d", &t[i]);
        rep(i, 1, n) scanf("%d", &b[i]);
        rep(i, 1, n) a[i] = 0;
        rep(i, 1, n) s[i] = t[i] + t[n-i+1];
        bool ans = false;
        while(true) {
            bool valid = true;
            rep(i, 1, n) if(a[i] > b[i]) valid = false;
            if(!valid) break;
            if((b[1] - a[1]) % s[1] == 0) {
                int steps = (b[1] - a[1]) / s[1];
                bool ok = true;
                rep(i, 1, n) if(b[i] != a[i] + steps * s[i]) ok = false;
                if(ok == true) {ans = true; break;}
            }
            rep(i, 1, n) a[i] += t[i];
        }
        puts(ans ? "Yes" : "No");
    }
    return 0;
}