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

张开发
• 2026/4/9 22:31:07 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

打卡信奥刷题（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 1n1个整数。第i ii个整数应为在进行i − 1 i - 1i−1次操作后列表中可能的不同整数的最小数量。输入输出样例 #1输入 #16 3 4 1 2 1 2输出 #14 4 3 3 2 2 1说明/提示时间限制3 秒内存限制512 MB。题面翻译由 ChatGPT-4o 提供。C实现#includebits/stdc.husingnamespacestd;constintN2e65;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);cinn;for(inti1;in;i){cind[i];vis[d[i]];//输入并记录每个数的出现次数}sort(d1,d1n);for(inti1;in;i){if(d[i]!d[i-1]){a[m]d[i];c[m]vis[d[i]];}}for(inti1;im;i){for(intja[i]*2;j1e6;ja[i]){if(vis[j]){b[len]vis[a[i]];break;}}}sort(c1,c1m);sort(b1,b1len);//记得排序毕竟选越小的越优for(inti1;in;i){sum[i]sum[i-1]c[i];cnt[i]cnt[i-1]b[i];//前缀和优化}intx0,y0;for(inti0;in;i){while(x1msum[x1]i)x;while(y1lencnt[y1]i)y;cout(m-max(x-1,y)) ;}cout\n;return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容

更多文章