【2018ACM/ICPC网络赛】沈阳赛区

这次网络赛没有打。生病了去医院了。。尴尬。晚上回来才看了题补简单题。

K Supreme Number

题目链接：https://nanti.jisuanke.com/t/31452

题意：输入一个整数n（其实可以当成字符串，因为很长啊。），求满足不超过n的supreme number。这个supreme number的定义是，这个字符串的子串都是质数。比如。137就是，但是19就不是。

题解：找规律。我先开始题没看懂，没懂子串也要为素数。后面才看到。然后在纸上枚举了一下可能出现的情况。发现大于4位数之后的只有317可以满足。所以打表列举即可。

代码：

 #include<iostream>

 #include<vector>

 #include<cstdio>

 #include<cstring>

 #include<queue>

 #include<cmath>

 using namespace std;

 typedef long long ll;

 const int N =1e8+;

 const int mod = 1e9+;

 int T;

 int sp[] = {,,,,,

 ,,,,,,,,,

 ,,,,

 ,,};

 int change(string s){

     int num = ;

     for( int i =  ;i < s.size(); i++){

         num = num *  + s[i] - '';

     }

     return num;

 }

 int main(){

     cin>>T;

     int t = ;

      while(T--){

          string s;

          cin>>s;

          int len = s.size();

          if(len >= ){

              printf("Case #%d: 317\n",t++);

          }

          else{

              int num = change(s);

              for(int i =  ; i <= ;i++){

                  if(num == sp[i]){

                      printf("Case #%d: %d\n",t++,sp[i]);

                      break;

                  }

                  else if(num < sp[i]){

                      printf("Case #%d: %d\n",t++,sp[i-]);

                      break;

                  }

              }

          }

     }

     return ;

 }

巴特西

【2018ACM/ICPC网络赛】沈阳赛区

最新文章

热门文章