跳至正文

USACO 1.5.3 SuperPrime Rib

  • OI路程

  这一题刚开始我是打算把所有的数都遍历一次,如当n=4时,就把1000~9999全部遍历,然后以此判断,但很快发现会超时,也可能是想起来以前刷的时候这个方法就是超时的,后来仔细想了一下,需要深搜!前遍历最高位,然后依次到个位,额,文字解释不清楚,用代码解释吧:

  问题出现了一些,但是因为是把程序的思路改了一两次,所以我就不好写哪里是错误了:
/
LANG: C
ID: yylogoo2
PROG: sprime
/
#include <math.h>
#include <stdio.h>
int n;

int isprime(int num)
{
        int i, li;
        if(num == 1){
                return 0;
        }
        if(num == 2 || num == 3 || num == 5 || num == 7 || num == 11 ||
                        num == 13){
                return 1;
        }
        if(num % 2 == 0 || num % 3 == 0 || num % 5 == 0 ||
                        num % 7 == 0 || num % 11 == 0 || num % 13 == 0){
                return 0;
        }
        li = sqrt(num);
        for(i = 17; i <= li; i += 2){
                if(num % i == 0){
                        return 0;
                }
        }
        return 1;
}

int tmp = 0;

void srch(int now)
{
        int i;
        if(now == n){
                printf("%d\n", tmp);
                return ;
        }
        tmp *= 10;
        tmp -= 1;
        for(i = 1; i <= 9; i += 2){
                
                tmp += 2;
                if(isprime(tmp)){
                        srch(now + 1);
                }
        }
        tmp /= 10;
}

int count[6] = {2357};

int main(void)
{
        int i;
        freopen("sprime.in""r"stdin);
        freopen("sprime.out""w"stdout);
        scanf("%d", &n);
        for(i = 0; i < 4; i++){
                tmp = count[i];
                srch(1);
        }
        return 0;
}

发表评论

您的电子邮箱地址不会被公开。