【USACO 1.5.3】特殊な質量肋骨

タイトル

略

ぶんせき

これは構造問題で、生成+テストはできるはずですが、もっといいでしょう.8桁に達するので、打表には向いていません.直接判断も多くありません.この数は少ないですが、poおじいさんは言ったようです.の最初の数に注意

コード#コード#

#include
#include
#include
#include
#include
using namespace std;
const int maxn=12;
int n,a[maxn];
bool _isp(int x)
{
    int to=sqrt(x+1);
    if(x==1)
        return 0;
    for(int i=2;i<=to;i++)
    {
        if(!(x%i))
            return 0;
    }
    return 1;
}
void run(int k,int x)// k ， x 
{
    if(k>n)
    {
        printf("%d
",x);
        return;
    }
    if(k==1)
    {
        for(int i=1;i<=9;i++)
        {
            int nx=x*10+i;
            if(_isp(nx))
                run(k+1,nx);
        }   
    }
    else
    {
        for(int i=0;i<=9;i++)
        {
            int nx=x*10+i;
            if(_isp(nx))
                run(k+1,nx);
        }   
    }

}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d",&n);
    run(1,0);
    return 0;
}

コードは難しくありません.考えは簡単です.これが構造問題であることを知っています.
商品を受け取る

収穫する

遡及アルゴリズムの位置パラメータはどのように定義するかを考慮し、反復が深まらない場合はいっそkを使います.習慣的にiをループするので、もちろん覚えておくか、stepを使うのもいいようです.

遡及アルゴリズムの利点は、動的列挙の過程で、生成-テストよりも多くの指数

を制約、予測することができることである.

答えの範囲推定に注意し、適切な方法を選択すると、大きな範囲に見える可能性がありますが、わずかな答えしかありません.
(私は数えていると思います)