One question per day on July 13, 2020 (structure)

I hope I can analyze a valuable question carefully , Instead of writing a few lines of thought as before 、 Put code , I hope I can understand the idea of a class of problems through a problem

F. Equate Multisets
difficulty ：1700
The question ： Given two repeatable sets of elements , aggregate B You can multiply the elements in the set by 2 Or divide by 2( Rounding down ) To get and set A The same set . The number of operations is unlimited , Output YES or NO.
Ideas ： The preliminary determination is a structural problem , We need to use the knowledge of number theory , Then start thinking .
First of all, you can't sort , because A、B The correspondence of elements in two sets is irregular , So turn to the nature of numbers .
1.A The number in cannot be modified ,A Medium odd numbers cannot pass B Middle number *2 obtain , Only through /2 obtain ;
2.A There may be even numbers in *2 perhaps /2 obtain , the B Uncertainty in number selection and operation
3.A Even numbers in can be divided by 2 Get an odd number , if B The middle number can be passed /2 After construction and deformation, it is odd A Same set , It satisfies the meaning of the question .

The key to this question ： take A The numbers in are divided by 2 Construct a set of odd numbers .
AC Code ： Changed the code thinking , use map, Because the key can reach 1e9 Power , use unordered_map()

#include<bits/stdc++.h>

using namespace std;
const int N=1e6+5;
unordered_map<int,int>mp;
int n,a[N],b[N];
bool flag;
int main()
{
    
    int t;cin>>t;
    while(t--)
    {
    
        mp.clear();
        flag=0;
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        for(int i=1;i<=n;i++)
        {
    
            while(a[i]%2==0&&a[i])
                a[i]/=2;
            mp[a[i]]+=1;
        }
        for(int i=1;i<=n;i++)
        {
    
           while(b[i])
           {
    
               if(b[i]%2&&mp[b[i]])
               {
    
                   mp[b[i]]--;
                   break;
               }
               else
                    b[i]/=2;
           }
        }
        for(int i=1;i<=n;i++)
            if(mp[a[i]])
            {
    
                flag=1;break;
            }
        if(flag)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
}

Code ：( There is something wrong with this code , The same way of thinking , Different ways of implementation , For a long time , Didn't find out , In the 7261 There is something wrong with the group sample , I can't see the wrong example )

#include<bits/stdc++.h>

using namespace std;
const int N=1e6+5;
int n,a[N],b[N],c[N];
bool vis[N],flag;
int main()
{
    
    int t;cin>>t;
    while(t--)
    {
    
        memset(vis,0,sizeof vis);
        cin>>n;
        for(int i=1;i<=n;i++)
            cin>>a[i];
        for(int i=1;i<=n;i++)
            cin>>b[i];
        for(int i=1;i<=n;i++)
        {
    
            if(a[i]%2)
                c[i]=a[i];
            else
            {
    
                c[i]=a[i];
                while(c[i]%2==0&&c[i]) c[i]/=2;
            }
        }
        sort(c+1,c+n+1);
        flag=0;
        for(int i=1;i<=n;i++)
        {
    
            while(b[i])
            {
    
                if(b[i]%2)
                {
    
                    int k=lower_bound(c+1,c+n+1,b[i])-c;
                    while(vis[k])   k++;
                    if(!vis[k]&&b[i]==c[k])
                    {
    
                        vis[k]=1;
                        break;
                    }
                }
                b[i]/=2;
            }
            if(b[i]==0)
            {
    
                flag=1;break;
            }
        }
        if(flag)
            cout<<"NO"<<endl;
        else
            cout<<"YES"<<endl;
    }
}