code forces 1176 D. Recover it!

概述原题链接：https://codeforces.com/contest/1176/problem/D 本文链接：https://www.cnblogs.com/blowhail/p/11146761.html 题目大意是 两个个数列 a , b 相同 ，如果 ai 是素数，那么b数列里添加上第ai个素数（2为第一个），如果不是素数，那么b数列里添加上ai的最大因子。现在给出添加完之后的b数列，求出

原题链接：https://codeforces.com/contest/1176/problem/D

本文链接：https://www.cnblogs.com/blowhail/p/11146761.html

题目大意是 两个个数列 a,b 相同 ，如果 ai 是素数，那么b数列里添加上第ai个素数（2为第一个），如果不是素数，那么b数列里添加上ai的最大因子。现在给出添加完之后的b数列，求出a数列。

大致思路： 先从大到小排序，然后判断是不是素数，如果是素数，那就遍历一遍，找到它是第几个素数，然后输出并记录下来。　　如果不是素数，就直接输出，再求出最大的因子记录下来。

写超时了好多次，修改了很多地方，可读性估计不太好

 

代码如下

#include <cstdio>#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <cmath>#define ll long long#define pi 3.1415926using namespace std;int primes[200006],a[400005],b[3000005],p2[3000005];
//这里primes数组按顺序记录素数，p2是 素数为1 非素数为0 
//a数组是存下输入的数列，b数组是记录每个数的个数bool cmp (int x,int y){    return x>y;}voID prime (int n){    int i,t,k,j;    primes[1]=2;    p2[2]=1;    int f,p=2;    for (i=3;i<=n;++i){        k=sqrt(i);        f=1;        for (t=2;t<=k;++t)            if(i%t==0)        {            f=0;            break;        }        if (f){            primes[p++]=i; //按顺序存            p2[i]=1;       //        }    }}int main (){    int i,m,n,l,j,p;    scanf("%d",&n);    j=2*n;    for(i=0;i<j;++i){        scanf("%d",&a[i]);        b[a[i]]++; //记录每个数个数    }    sort(a,a+j,cmp);    prime(a[0]);    int c=200000; //这里我用c来记录每次遍历素数的位置，然后下一次就直接从这个位置继续遍历（因为已经从大到小排序了）     for (i=0;i<j;++i)    {        if (b[a[i]]==0)             continue;        if (p2[a[i]]==1){                for (int h=c;h>=1;--h)                    if (primes[h]==a[i]){                        c=h;                        break;                        }

　　　　　    printf("%d ",c);

　　　　　　  b[ a[i] ]--;              b[c]--;       //b是记录每个数出现次数，每次遍历完都把找出来的数给减去        }        else        {            printf("%d ",a[i]);            for (int h=2;h<a[i];++h)                if (a[i]%h==0)            {                k=a[i]/h;                break;            }            b[a[i]]--;            b[k]--;        }    }    printf("\n");    return 0;}

@H_183_301@ 总结

以上是内存溢出为你收集整理的code forces 1176 D. Recover it!全部内容，希望文章能够帮你解决code forces 1176 D. Recover it!所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。