问题 2111: 连环阵

题目链接：https://www.dotcpp.com/oj/problem2111.html
题目来源：C语言网

题目描述
   杰洛特主动出击狂猎的老巢，然而在此之前，他遇到了一个女术士，杰洛特想要女术士助自己一臂之力，她却出了一个难题给杰洛特，只有答对了才能与他同行
  女术士给杰洛特一个四位数的素数，要求他说出这个四位数的数字的另外两个四位素数(从小到达输出)，要求：
  1.这个三个四位数组成等差数列
  2.这三组数字的构成相同(即每个四位数都是其他数字的一种排列)
输入
  多组数据输入
     每次一个整数
输出
  输出这三个数字，如果没有达成条件的三个数字，则输出"No"
样例输入
  4817
  1232
样例输出
  1487 4817 8147
  No

  首先是题目的问题，此题并没有保证输入的四位数是素数(坑死…)；对于这个题目我先预处理出来每个数是否是素数(埃式筛法)，对于 $n$ 先找出所有的排列( next_permutation() )，将其存入一个素数的数列当中(这里有一个坑点，有前导零的数字不算是四位素数…)，首先判断 $n$ 是否为素数，如果不是直接输入 $No$，如果是素数就按照 $n$ 在左边，中间和右边分别取枚举，如果存在满足条件的数列则输出，否则输出 $No$

#include<bits/stdc++.h> using namespace std;const int maxn=1e5+10; bool is_prime[maxn]; int a[maxn],prime[maxn];void isPrime(){for(int i=2;i<=maxn;i++) is_prime[i]=true;is_prime[0]=is_prime[1]=true;for(int i=2;i<=sqrt(maxn);i++){if(is_prime[i]){for(int j=i*i;j<=maxn;j+=i)is_prime[j]=false;}} }int main(){isPrime();/*string str="1222";do{cout<<str<<endl;}while(next_permutation(str.begin(),str.end()));*/int n;while(~scanf("%d",&n)){/*for(int i=1000;i<=9999;i++){//if(is_prime[i]) n=i;//else continue;n=i;cout<<n<<" : ";*/int x=n,cnt=0;while(x){a[cnt++]=x%10;x/=10;}sort(a,a+4); cnt=0;do{int temp=a[0]*1000+a[1]*100+a[2]*10+a[3];if(is_prime[temp]&&temp>=1000) prime[cnt++]=temp;}while(next_permutation(a,a+4));//for(int i=0;i<cnt;i++) cout<<prime[i]<<" "; cout<<endl;//3种情况，n在左边，n在中间，n在右边if(!is_prime[n]) puts("No");else{int inx=lower_bound(prime,prime+cnt,n)-prime;//n的位置int a=0,b=0,c=0; for(int i=0;i<inx;i++){//<n的情况 if(binary_search(prime,prime+cnt,n+n-prime[i])){//n在中间 a=prime[i]; b=n; c=n+n-prime[i];break;}if(binary_search(prime,prime+cnt,(n+prime[i])/2)){//n在右边a=prime[i]; b=(n+prime[i])/2; c=n;break; }} for(int i=inx+1;i<cnt;i++){//>n的情况if(binary_search(prime,prime+cnt,n-(prime[i]-n))){//n在中间a=n-(prime[i]-n); b=n; c=prime[i];break; } if(binary_search(prime,prime+cnt,(n+prime[i])/2)){//n在左边a=n; b=(n+prime[i])/2; c=prime[i];break; }}if(a&&b&&c) printf("%d %d %d\n",a,b,c);else puts("No");}//}//}return 0; }

总结

以上是生活随笔为你收集整理的问题 2111: 连环阵的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。