打卡信奥刷题（3077）用C++实现信奥题 P7023 [NWRRC 2017] Equal Numbers

P7023 [NWRRC 2017] Equal Numbers

题目描述

给定一个包含n nn个整数a 1 , … , a n a_{1}, \ldots, a_{n}a1​,…,an​的列表。你可以执行以下操作：选择某个a i a_{i}ai​并将其乘以任意正整数。

你的任务是计算在进行k kk次操作后列表中可能出现的不同整数的最小数量，要求对所有0 ≤ k ≤ n 0 \le k \le n0≤k≤n都进行计算。

输入格式

输入的第一行包含一个整数n ( 1 ≤ n ≤ 3 × 10 5 ) n (1 \le n \le 3 \times 10^{5})n(1≤n≤3×105)。输入的第二行包含n nn个整数a i ( 1 ≤ a i ≤ 10 6 ) a_{i} (1 \le a_{i} \le 10^{6})ai​(1≤ai​≤106)。

输出格式

输出一行包含n + 1 n + 1n+1个整数。第i ii个整数应为在进行i − 1 i - 1i−1次操作后列表中可能的不同整数的最小数量。

输入输出样例 #1

输入 #1

6 3 4 1 2 1 2

输出 #1

4 4 3 3 2 2 1

说明/提示

时间限制：3 秒，内存限制：512 MB。

题面翻译由 ChatGPT-4o 提供。

C++实现

#include<bits/stdc++.h>usingnamespacestd;constintN=2e6+5;inta[N],cnt[N],vis[N],sum[N],n,m,k,x,y,b[N],c[N],d[N],T,len;intmain(){ios::sync_with_stdio(0);cin.tie(0);cin>>n;for(inti=1;i<=n;i++){cin>>d[i];vis[d[i]]++;//输入并记录每个数的出现次数}sort(d+1,d+1+n);for(inti=1;i<=n;i++){if(d[i]!=d[i-1]){a[++m]=d[i];c[m]=vis[d[i]];}}for(inti=1;i<=m;i++){for(intj=a[i]*2;j<=1e6;j+=a[i]){if(vis[j]){b[++len]=vis[a[i]];break;}}}sort(c+1,c+1+m);sort(b+1,b+1+len);//记得排序，毕竟选越小的越优for(inti=1;i<=n;i++){sum[i]=sum[i-1]+c[i];cnt[i]=cnt[i-1]+b[i];//前缀和优化}intx=0,y=0;for(inti=0;i<=n;i++){while(x+1<=m&&sum[x+1]<=i)++x;while(y+1<=len&&cnt[y+1]<=i)++y;cout<<(m-max(x-1,y))<<' ';}cout<<'\n';return0;}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容