2024牛客寒假算法基础集训营1 D数组成鸡

原题链接：D-数组成鸡_2024牛客寒假算法基础集训营1 (nowcoder.com)

题目大意：给一个数组，数组长度为n，每一次操作是让数组的每一个数一起加一或者减一，可以多次操作，多次询问给定一个m问数组的乘积是否可以等于m?

n的范围是[2,1e5],m的范围是[-1e9,1e9]，数组中每个数的范围是[-1e9,1e9]，询问次数的范围是[1,5e5]。

思路：可以观察到m的范围是(-1e9,1e9)，那么需要考虑的数并不是非常多。可以考虑数组里面不同的数字，最多是1*-1*2*-2*3*-3*4*-4*5*-5*6*-6*7*-7*8*-8=1625702400>1e9。所以最多只有16个不同的数据在数组里。可以用map来存数据，如果map的大小超过了16，那么数组无论如何操作，它们的乘积满足范围的只有0。

那么对于map大小小于等于16的数据。我们应该如何处理？

如果数组里面只有二个数，那么这二个数可以操作的范围是多少？这二个数据必须有一个保持在（-31623，31623）之间，因为31623*31623>1e9，如果一个数是1，那么另一个数可以是绝对值小于等于1e9的任意数，如果一个数是31623，那么另一个数的范围一定是（-31623，31623）。如果是三个数呢？那么范围就是（-1001，1001）之间，因为1001*1001*1001>1e9。必须保证有一个数在这之间。

那么思路就很明确了，枚举每一个数组里面的数，让它到它对应的范围里面，就可以的到操作数，然后去更新其他的数。如果有0，那么就跳出循环，并且不保存，如果乘积大于1e9，跳出循环并且不保存。

代码：

#pragma GCC optimize(2)//o2优化
#include<bits/stdc++.h>
#define endl '\n' 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pii;
const int N=1e6+10;
int main()
{
    ios::sync_with_stdio(NULL);
    cin.tie(0),cout.tie(0);
    ll n,q;cin>>n>>q;
    map<ll,ll>p,op;//p来记录数组中不同数据的个数，op来表示这个数据是否可以为数组的乘积.
    op[0]=1;//0一定可以
    for(int i=0;i<n;i++)
    {
        ll a;cin>>a;
        p[a]++;
    }
    vector<pii> k;
    for(auto x:p)k.push_back(x);//存下不同的数，减少循环的次数
    if(p.size()<=16)
    {
        ll M=pow(1e9,1.0/n)+1;//可以直接写4e4，4e4为最大的情况的近似。加1为了防止出现精度问题，不加也能过，不知道是卡不了还是没想卡。
        for(int i=0;i<k.size();i++)
        {
            for(int j=-M;j<=M;j++)
            {
                bool lll=0;
                ll sum=1;
                ll cz=j-k[i].first;//让这个数据到范围的操作数。
                for(auto [x,y]:p)
                {
                    ll v=x+cz;//因为数组所有的数要一起操作，其他的数也要操作相同的次数
                    if(!v)//如果操作过程中，有一个数据为0，那么整个数组的乘积都是0，直接跳出去，记录不加入op
                    {
                        lll=1;
                        break;
                    }
                    for(int i=0;i<y;i++)
                    {
                        if(abs(sum)>1e9)break;
                        sum=sum*v;
                    }
                    //if(abs(sum)>1e9)break;
                }
                if(!lll&&abs(sum)<=1e9)op[sum]=1;
            }
        }
    }
    while(q--)
    {
        ll a;
        cin>>a;
        if(op[a])cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}