摸摸 官方题解

· · 题解

这里是官方题解。

记数列 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;
}