[sicily]1002. Anti-prime Sequences

男娘i 2022-07-24 04:06 84阅读 0赞

![这里写图片描述][20160512100028444]

题目解析：注意在判断一个d anti-prime sequence时，需要判断连续2,3…,d个数字的和是否都是一个合数！

解题思路  
深度搜索：从第一个数字开始，不断向序列中加入新的数字，判断加入的数字是否能够组成一个d-anti-prime sequence。如果可以则继续增加新元素，否则弹出这个元素，尝试加入下一个数字。

主要的解题思路已经知道可以采用深度搜索了，但是还需要解决一个问题，就是如何判断一个数字是不是素数。

假设给定的数字是a，最简单的方法就是使用一个循环，判断a是否能够被2到a-1这些数字整除。如果可以那a就是一个合数，否则a是一个素数。

bool isPrime(int num) {
    
        if (num <= 1) return false;
    
        for (int i = 2; i < num; ++i) //a prime is not divisible by integers between 2 and sqrt root of it
        {
            if(num % i == 0)
                return false;
        }
        return true;
    }

改进一下的方法就是：根据对称原则，i不需要增加到a，只需要判断a能够被从2到sqrt(a)的数整除就可以了。

bool isPrime(int num) {
    
        if (num <= 1) return false;
    
        for (int i = 2; i <= sqrt(num); ++i) //a prime is not divisible by integers between 2 and sqrt root of it
        {
            if(num % i == 0)
                return false;
        }
        return true;
    }

但是使用这种方法，每次都需要重新判断，非常耗时。考虑使用一个数组存储对应的数字是否是合数。并且考虑一下性质：(1) 一个大于2的偶数肯定不是素数 (2) 一个数的大于1的倍数肯定也不是素数。 所以可以得到一下改进方法：

void initPrimeList() 
    {
        memset(primeList, true, sizeof(primeList)); 
        primeList[0] = primeList[1] = false;
    
        // even is not a prime
        // multiple of a number is also not a prime
        // a prime is not divisible by integers between 2 and sqrt root of it,now N = 10000, so i <= 100
        for (int i = 2; i <= 100; ++i)
        {
            if(primeList[i]) {
                for(int j = 2; i*j <= N; j++)
                    primeList[i*j] = false;
            }
        }
    }

整合上述方法，得到最终的结果

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int N =  10000;
    
    bool finishFlag;
    bool compositeList[N];
    bool visited[1100];
    int antiSequence[1100];
    int n, m, d;
    
    
    void initcompositeList() 
    {
        memset(compositeList, false, sizeof(compositeList)); 
        compositeList[0] = compositeList[1] = true;
    
        // even is not a prime
        // multiple of a number is also not a prime
        // a prime is not divisible by integers between 2 and sqrt root of it,now N = 10000, so i <= 100
        for (int i = 2; i <= 100; ++i)
        {
            if(!compositeList[i]) {
                for(int j = 2; i*j <= N; j++)
                    compositeList[i*j] = true;
            }
        }
    }
    
    
    //juege whether the d-number is a prime
    bool isAllComposite(int index) {
    
        int sum = antiSequence[index];
        for (int i = index - 1; i > -1 && i > index - d; i--)
        {
            sum += antiSequence[i];
            if (!compositeList[sum])
                return false;
        }
        return true;
    }
    
    /*
     @param: depth: how many elements have been in the anti-prime sequence
    */
    void dfs(int depth) 
    {
    
        if(depth == m - n + 1) { 
            finishFlag = true;
            return;
        }
    
        for(int i = n; i <= m; ++i)
        {
            if(!visited[i])
            {
                antiSequence[depth] = i; //add i into a sequence
                if(isAllComposite(depth)) 
                { 
                    visited[i] = true;
                    dfs(depth + 1);
                    if(finishFlag)  return; //find a anti-prime sequence
                    visited[i] = false; // add i cannot form a anti-prime sequence, pop it
                }
            }
        }
    }
    
    
    int main() {
    
        initcompositeList();
    
        while(cin >> n >> m >> d && n != 0)
        {
            memset(visited, false, sizeof(visited));
            memset(antiSequence, 0, sizeof(antiSequence));
            finishFlag = false;
    
            dfs(0);
    
            if(finishFlag) {
                for (int i = 0; i < m-n; ++i)
                {
                    cout << antiSequence[i] << ",";
                }
                cout << antiSequence[m-n] << endl;
            } else
                cout << "No anti-prime sequence exists." << endl;
        }
        return 0;
    }

这种方法的运行结果为：0.6sec 324 KB。花费的时间太多，有人提出了在dfs卡时的方法：当dfs搜索达到了一定深度，则认为无法形成一个anti-prime sequence。经过手动测试之后，发现深度超过15000就可以AC。

#include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int N =  10000;
    
    bool compositeList[N];
    bool visited[1100];
    int antiSequence[1100];
    int n, m, d;
    int count; //reduce dfs search depth to fast return 
    
    void initcompositeList() 
    {
        memset(compositeList, false, sizeof(compositeList)); 
        compositeList[0] = compositeList[1] = true;
    
        // even is not a prime
        // multiple of a number is also not a prime
        // a prime is not divisible by integers between 2 and sqrt root of it,now N = 10000, so i <= 100
        for (int i = 2; i <= 100; ++i)
        {
            if(!compositeList[i]) {
                for(int j = 2; i*j <= N; j++)
                    compositeList[i*j] = true;
            }
        }
    }
    
    
    //juege whether the d-number is a prime
    bool isAllComposite(int index) {
    
        int sum = antiSequence[index];
        for (int i = index - 1; i > -1 && i > index - d; i--)
        {
            sum += antiSequence[i];
            if (!compositeList[sum])
                return false;
        }
        return true;
    }
    
    /*
     @param: depth: how many elements have been in the anti-prime sequence
    */
    bool dfs(int depth) 
    {
        count ++;
        if (count > 1500) 
            return false;
    
        if(depth == m - n + 1) 
            return true;
    
        for(int i = n; i <= m; ++i)
        {
            if(!visited[i])
            {
                antiSequence[depth] = i; //add i into a sequence
                if(isAllComposite(depth)) 
                { 
                    visited[i] = true;
                    if (dfs(depth + 1))
                        return true; //find a anti-prime sequence
                    visited[i] = false; // add i cannot form a anti-prime sequence, pop it
                }
            }
        }
        return false;
    }
    
    
    int main() {
    
        initcompositeList();
    
        while(cin >> n >> m >> d && n != 0)
        {
            memset(visited, false, sizeof(visited));
            memset(antiSequence, 0, sizeof(antiSequence));
            count = 0;
    
            if(dfs(0)) {
                for (int i = 0; i < m-n; ++i)
                {
                    cout << antiSequence[i] << ",";
                }
                cout << antiSequence[m-n] << endl;
            } else
                cout << "No anti-prime sequence exists." << endl;
        }
        return 0;
    }

运行结果为：0sec 324 KB

[20160512100028444]: /images/20220722/1d80f296c93a4a7a8050f5b62767f093.png