Opening a blog for the first time!

Revision en1, by Please_do_not_play_me, 2021-01-26 17:24:30

Write down the solution of yesterday's Div3.G question.

G.Strange Beauty = The topic is to require a maximum set so that the numbers directly multiply with each other.Sorting does not affect the results.Let's let $$${f_i}$$$ represent the number of sets with the largest number in i.

Then an obvious state transition equation:$$${f_i=f_j+num_i}$$$.In which num_i represents the number of i.

The next step is to consider the problem of transferring time.Obviously I can only be transferred by the factor of i.Notice that the data size is only 2e5.We might as well preprocess all the factors with an Ehrlich sieve.Then carry out dp.

The time complexity is $$${O(nlognlogn)}$$$.

code:

#include <bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int a[N];
vector<int>v[N];
void init()
{
    for(int i=1;i<=2e5;i++)
    {
        for(int j=i;j<=2e5;j+=i)
        {
            v[j].push_back(i);
        }
    }
}

int main()
{
    int T;scanf("%d",&T);
    init();
    while(T--)
    {
        unordered_map<int,int>p,f;
        int n;scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);p[a[i]]++;
        }int ans=0;sort(a+1,a+1+n);
        int cnt=unique(a+1,a+1+n)-a-1;
        for(int i=1;i<=cnt;i++)
        {
            f[a[i]]=p[a[i]];
            for(int j:v[a[i]])
            {
                if(a[i]!=j) f[a[i]]=max(f[a[i]],f[j]+p[a[i]]);    
            }ans=max(f[a[i]],ans);
        }
        printf("%d\n",n-ans);
    }
    return 0;
}

Tags blog

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Please_do_not_play_me 2021-01-26 17:28:54 5
en2 English Please_do_not_play_me 2021-01-26 17:26:56 6
en1 English Please_do_not_play_me 2021-01-26 17:24:30 1589 Initial revision (published)