2018 ICPC 沈阳网络赛预赛 Supreme Number（找规律）

【传送门】https://nanti.jisuanke.com/t/31452

【题目大意】：给定一个数字（最大可达10¹⁰⁰），现在要求不超过它的最大超级质数。超级质数定义：对于一个数，把它看成数字序列，如果它的所有子序列形成的数都是质数，那么它就是超级质数。

比如说3137，它的子序列有3,1,7,31,33,37,313,317,137.....由于有一个子序列是33它不是质数，所有3137不是超级质数。

【题解】注意，子序列和子串是不同的，子序列包含子串。子序列只要求相对顺序不变，而子串不仅仅要求顺序不变而且要求连续。比赛的时候因为这个WA了好几次。

（1）首先我们很容易知道，某个数它是超级质数，那么它所有位必须都是质数，也就是说，每一位上的数字只可能是1,2,3,5,7

（2）除了最高位可以是1,2,3,5,7，其余低位只能是1，3，7。因为2,5作低位必然有子序列不是质数。

（3）除了1后面还可以接1之外，其余数字后面都不能再接这个数字。比如3后面不能再接3，否则33不是质数。

（4）找出位数K = 1,2,3的所有满足条件的数，发现K = 4时，找不到4位数的超级质数。由于子序列不能是超级质数，那么4位以上的数不可能是超级质数。

【AC代码】

#include <queue>

#include <cstdio>

#include <string.h>

#include <cstdlib>

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int a1[] ={,,,,};

int a2[] = {,,,,,,,,};

int a3[] = {,,,,,};

int main(){

    ios::sync_with_stdio(false);

    int t;

    cin>>t;

    string s;

    int k=;

    while(t--)

    {

        cin>>s;

        cout<<"Case #"<<k++<<": ";

        int len = s.size();

        if(len == ){

            int num = atoi(s.c_str());

            for(int i=; i>=; i--){

                if(a1[i] <= num){

                    cout<<a1[i]<<endl;

                    break;

                }

            }

        }

        else if(len == ){

            int num = atoi(s.c_str());

            int flag = ;

            for(int i=; i>=; i--){

                if(a2[i] <= num){

                    flag = ;

                    cout<<a2[i]<<endl;

                    break;

                }

            }

            if(flag == ){

                cout<<<<endl;

            }

        }

        else if(len == ){

            int num = atoi(s.c_str());

            int flag = ;

            for(int i=; i>=; i--){

                if(a3[i] <= num){

                    flag = ;

                    cout<<a3[i]<<endl;

                    break;

                }

            }

            if(flag == ){

                cout<<<<endl;

            }

        }

        else if(len >= ){

            cout<<""<<endl;

        }

    }

    return ;

}

巴特西

2018 ICPC 沈阳网络赛预赛 Supreme Number（找规律）

最新文章

热门文章