Блог пользователя Please_do_not_play_me

Автор Please_do_not_play_me, история, 3 года назад, По-английски

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;
}

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

since less than 1600 rated created blog so downvote coming

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

666