P9714 「QFOI R1」摸摸题解

_Ink · 2023-10-05 19:21:17 · 个人记录

本题有 O(n) 做法。

前言：

赛时看到题的第一眼想法就是线性...以至于代码都码了一半才看到数据范围，额，似乎可以 O(n^2) 过？

赛后也反馈了这一问题，据出题人的说法是：这种做法是已知的，只不过考量到这是面对基础赛出的题目，所以不准备加强数据。所以这个线性做法就当是给各位加加餐了吧（

题解正题：

首先，这种一看就能用爆搜做的题，如果数据范围不支持你跑爆搜，那么其本身一定有着一些有趣的性质。

这种有趣的性质出现在了操作 1。操作 1 是让 t 数组倒序自加。很显然的是，t 数组倒序自加后，其本身就变成了一个“回文数组”。“回文数组”中，关于对称中心对称的两个数的值相等，换言之，对称的两个数的差值为 0。

以下我把“关于对称中心对称的两个数”简称为“对称的数”。

我们要差值为 0 这个条件有什么用呢？显然的是，在 t 变成一个“回文数组”后，此时不论你再怎么去执行操作 2，把 t 中的值加给 a，a 中对称的数的差值也不会变化了。

我们要让 a 变成 b，而 b 中是可能存在对称的数差值不为 0 的情况。由于 t 在成为“回文数组”后我们无法再改变对称的数的差值，所以我们在让 t 自加之前，就要用初始的 t 执行数次操作 2，使得 a 每组对称的数与 b 每组对称的数的差值一致。

仅有口述还是太苍白了，我们举个例子来体现一下：

n=5
t[]=1,1,1,2,3;  b[]=6,5,4,7,10
//dist 代表 t 对称的数的差值，disb 代表 b 对称的数的差值
dist[]=2,1; disb[]=4,2
//此时我们执行两次操作 2，就可以使 a 的每组差值与 b 相同。
a[]=2,2,2,4,6

上述例子我们能通过两次操作 2 使得 a 中最终的每组差值与 b 一致。如果我们做不到让其差值一致，答案显然是 NO。

如果能的话，我们便让 t 自加，再去判断是否能通过执行数次操作 2，让 a 和 b 一致。如果可以，则是 YES；不能，则答案依然是 NO。

//同上例
a[]=2,2,2,4,6;
//让 t 自增
t[]=4,3,2,3,4;
//执行 1 次操作 2
a[]=6,5,4,7,10; (==b[])
//YES

当然这里还是要提一嘴，执行 2 次及以上次数的操作 1 是没有意义的。在 t 成为“回文数组”再执行操作 1，本质上是把 t 自身翻了一倍。这完全可以通过多次执行操作 2 达到相同的作用。所以我们只执行一次操作 1。

知道了做法，剩下的本质上就是一些乘除取模运算的事了。显然的是，我们不用暴力地去枚举某个阶段操作 2 的次数，只需要合理运用取模运算来判断，利用乘除法来计算次数就可以了。

这种做法的瓶颈仅在于需要遍历数组。时间复杂度为 O(n)。如果还不懂怎么实现或者细节上有问题，那就看代码注释吧。

\text{Code:}

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 3005
#define endl '\n'
#define ll long long
using namespace std;

int n;
int b[maxn], t[maxn], a[maxn];

void run()
{
    cin >> n;
    for(int i = 1; i <= n; i ++) cin >> t[i];
    for(int i = 1; i <= n; i ++) cin >> b[i];

    int dist, disb;
    for(int i = 1; i <= n / 2; i ++) //不断寻找 b 与 t 的差值，直到找到一组不全为 0 的为止 
    {
        dist = t[i] - t[n - i + 1], disb = b[i] - b[n - i + 1];
        if(dist != 0 || disb != 0) break;
    }

    if(dist * disb < 0) {cout << "NO" << endl; return;} //两差值符号不同，那必然不行 
    if(dist == 0 && disb == 0) //找到最后差值都均为 0，说明 b 与 t 原本就中心对称 
    {
        int mul = b[1] / t[1]; 
        for(int i = 1; i <= n; i ++)
            if(t[i] * mul != b[i]) {cout << "NO" << endl; return;}
        cout << "YES" << endl; return;
    }
    if(dist != 0) 
    {
        if(disb % dist) {cout << "NO" << endl; return;} 
        int mul = disb / dist; //执行 mul 遍操作 1
        for(int i = 1; i <= n; i ++) a[i] = mul * t[i];
    }

    if(b[1] < a[1] || (b[1] - a[1]) % (t[1] + t[n])) {cout << "NO" << endl; return;}

    int mul2 = (b[1] - a[1]) / (t[1] + t[n]); 
   //t 自增后执行 mul2 便操作 1。这里用数组中的第一个数来计算 mul2 值
    for(int i = 1; i <= n; i ++) 
    {
        a[i] += mul2 * (t[i] + t[n - i + 1]);
        if(a[i] != b[i]) {cout << "NO" << endl; return;}
    }
    cout << "YES" << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int t = 1;
    cin >> t; 
    while(t --) run();

    return 0;
}

P9714 「QFOI R1」摸摸 题解

题解正题：

\text{Code:}

P9714 「QFOI R1」摸摸题解