数组成鸡

题目描述

小鸡有一个由整数组成的数组，小鸡可以对这个数组进行任意次（可以不进行）全数组每个数加一或全数组每个数减一的操作。

现在，小鸡想让你回答 $Q$ 次询问，每次询问给出一个整数 $M$，你需要回答任意次（可以不操作）操作后是否可以使得给定数组的乘积等于给出的整数 $M$。

输入描述:

第一行输入两个正整数 $n$，$Q$ ($2 \leq n \leq10^5$, $1 \leq Q \leq 5 \times 10^5$)，表示数组长度与询问次数。

第二行输入 $n$ 个空格分隔的整数 $a_i$ ($-10^9 \leq a_i \leq 10^9$)，表示数组中的元素。

接下来 $Q$ 个空格分隔的整数 $M$ ($−10^9 \leq M \leq 10^9$)，表示询问的数字。

输出描述:

对于每个 $M$，请你输出一行 "Yes" 或 "No"（不含引号）表示是否可以令全数组的乘积等于给定 $M$。

示例1

输入

4 9
1 -1 3 5
-75 19305 123 1 0 15 -15 1919810 114514

输出

No
Yes
No
No
Yes
No
Yes
No
No

解题思路

  由于询问的 $|M|$ 最大为 $10^9 < 2^{30}$，所以如果操作后 $a$ 中绝对值大于 $1$ 的元素数量至少为 $30$ 时，$\left| \prod{a_i} \right| \geq 2^{30} > |M|$。为此如果 $n \geq 30$，我们只能将某些数变成 $1$ 或 $-1$，然后再判断所有数乘积的绝对值是否不超过 $10^9$，如果不超过则把乘积结果存到 std::set 中。如果 $n < 30$，则需要保证操作后最小的两个元素的绝对值不能同时大于 $\sqrt{10^9}$，因此只需暴力枚举操作次数 $-\sqrt{10^9} \sim \sqrt{10^9}$，如果所有数乘积的绝对值不超过 $10^9$则存到 std::set 中。最后询问只需判断 $M$ 是否在集合中即可。下面给出具体做法。

  如果 $n \geq 30$，用 $c_x$ 来表示初始 $a$ 中元素 $x$ 数量，枚举每一种数 $a_i$（即重复的只枚举 $1$ 次），先通过加 $-a_i + 1$ 次 $1$ 把 $a_i$ 变成 $1$（元素 $a_i - 2$ 会变成 $-1$）。如果 $n - c_{a_i} - c_{a_i-2} < 30$，则检查操作后 $a$ 的乘积的绝对值是否不超过 $10^9$。同理把 $a_i$ 变成 $-1$。其中检查的部分是暴力枚举，时间复杂度为 $O(n)$，但实际上检查的次数非常少（最多应该只有一次），因为如果要满足 $n - c_x - c_{x-2} < 30$，意味着 $c_x + c_{x-2} > n - 30$，此时整个 $a$ 中基本都是元素 $x$ 或 $x-2$。

  如果 $n \geq 30$，对 $a$ 排序，分别枚举 $a_0 \in [-\sqrt{10^9}, \sqrt{10^9}]$ 和 $a_1 \in [-\sqrt{10^9}, \sqrt{10^9}]$ 的情况，即分别加 $-a_0 + i$ 次 $1$ 和加 $-a_1 + i$ 次 $1$，$i \in [-\sqrt{10^9}, \sqrt{10^9}]$。计算量大概是 $30 \times \sqrt{10^9}$ 级别。

  AC 代码如下：

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 2e5 + 10;

int n, m;
int a[N];
set<int> st({0});

void get(int x) {
    LL t = 1;
    for (int i = 0; i < n; i++) {
        t *= (a[i] + x);
        if (abs(t) > LL(1e9)) return;
    }
    st.insert(t);
}

int main() {
    scanf("%d %d", &n, &m);
    map<int, int> mp;
    for (int i = 0; i < n; i++) {
        scanf("%d", a + i);
        mp[a[i]]++;
    }
    sort(a, a + n);
    if (n >= 30) {
        for (int i = 0; i < n; i++) {
            if (!i || a[i] != a[i - 1]) {
                if (n - mp[a[i]] - mp[a[i] - 2] < 30) get(-a[i] + 1);
                if (n - mp[a[i]] - mp[a[i] + 2] < 30) get(-a[i] - 1);
            }
        }
    }
    else {
        for (int i = -31622; i <= 31622; i++) {
            get(-a[0] + i);
            get(-a[1] + i);
        }
    }
    while (m--) {
        int x;
        scanf("%d", &x);
        printf("%s\n", st.count(x) ? "Yes" : "No");
    }
    
    return 0;
}

参考资料

  【出题人讲题】2024牛客寒假算法基础集训营1 题解：https://www.bilibili.com/video/BV1Ry421a7pW/

  2024牛客寒假算法基础集训营1（全部题目详解）：https://www.bilibili.com/video/BV1Ty421a7vN/