题解 P9714 「QFOI R1」摸摸

· · 题解

Solution

考虑分别观察两个操作。

观察操作 2 ，因为 a 数组初始值为 0 ，所以 a 实际上是经过变换的 t 相加得到的。

这是我们再观察操作 1 ，很容易想到 a 其实就是几个正序 t 和几个逆序 t 的加和。

这里我们注意，至少有一次正序 t ，毕竟 a 是从 t 加过来的。

故题目转化为：是否可以通过任意个正序 t 和任意个逆序 t 相加得到 b 。

因为 n 很小，所以我们用不超过的 O(n^2) 暴力判断即可。

程序中我们用 b[1] 和 t[1] 的商来确定正序和逆序个数的范围。

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <map>
using namespace std;
const int N = 2005;
const int M = 100005;
#define ll long long
const int INF = 0x3f3f3f3f;
const int mod = 1000000007;
int T;
int n;
int t[N], b[N];
bool check(int a1, int a2) {
    for (int i=2; i<=n; i++)
        if (t[i] * a1 + t[n - i + 1] * a2 != b[i])
            return 0;
    return 1;
}//判断是否t=b
int main() {
    scanf("%d", &T);
    int cnt; bool flag;
    while (T--) {
        flag = 0;
        scanf("%d", &n);
        for (int i=1; i<=n; i++)
            scanf("%d", &t[i]);
        for (int i=1; i<=n; i++)
            scanf("%d", &b[i]);
        for (int i=1; i<=b[1]/t[1]; i++) {//枚举正逆序t个数
            if ((b[1] - t[1] * i) % t[n]) continue;//取不到b[1]，显然不可
            if (check(i, (b[1] - t[1] * i) / t[n])) {
                printf("Yes\n");
                flag = 1;
                break;
            }
        }
        if (!flag) printf("No\n");
    }
    return 0;
}