hdu 1979 DFS + 字典树剪枝

​​http://acm.hdu.edu.cn/showproblem.php?pid=1979​​

Fill the blanks

Time Limit: 3000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 373    Accepted Submission(s): 155

Problem Description

There is a matrix of 4*4, you should fill it with digits 0 – 9, and you should follow the rules in the following picture:

Input

No input.

Output

Print all the matrixs that fits the rules in the picture. 
And there is a blank line between the every two matrixs.

Sample Output

1193 1009 9221 3191

1193 1021 9029 3911 ……

9173 1559 3821 3391

Author

8600

Source

​​2008杭电集训队选拔赛​​

1000 --- 9999中有204个顺着和倒着读都是素数的数。

考虑的就是暴力dfs，然后最后再判断？超时。可以打表。

可以用字典树维护前缀，

每次都维护主对角线和副对角线的数字，还有四条列。然后如果不存在这样的前缀，直接剪掉就好。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL;
#define MY "H:/CodeBlocks/project/CompareTwoFile/DataMy.txt", "w", stdout
#define ANS "H:/CodeBlocks/project/CompareTwoFile/DataAns.txt", "w", stdout


#include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn=1e5+20;
bool prime[maxn];//这个用bool就够了，
bool check[maxn];
int goodprime[maxn];
char strprime[204 + 2][10];
int lenprime = 0;
struct node {
    int cnt;
    struct node * pNext[10];
} tree[maxn], *T;
int num;
struct node * create() {
    struct node * p = &tree[num++];
    for (int i = 0; i <= 9; ++i) {
        p->pNext[i] = NULL;
    }
    p->cnt = 1;
    return p;
}
void insert(struct node **T, int val) {
    struct node *p = *T;
    if (p == NULL) {
        *T = p = create();
    }
    char str[11] = {0};
    int lenstr = 0;
    while (val / 10 > 0) {
        str[++lenstr] = val % 10 + '0';
        val /= 10;
    }
    str[++lenstr] = val + '0';
    str[lenstr + 1] = '\0';
    strcpy(strprime[lenprime] + 1, str + 1);
//    printf("%s\n", str + 1);
    for (int i = 1; str[i]; ++i) {
        int id = str[i] - '0';
        if (p->pNext[id]) {
            p->pNext[id]->cnt++;
        } else p->pNext[id] = create();
        p = p->pNext[id];
    }
    return;
}
int find(struct node *T, int val) {
    struct node *p = T;
    if (!p) return 0;
    char str[11] = {0};
    int lenstr = 0;
    while (val / 10 > 0) {
        str[++lenstr] = val % 10 + '0';
        val /= 10;
    }
    str[++lenstr] = val + '0';
    str[lenstr + 1] = '\0';
    reverse(str + 1, str + 1 + lenstr);
//    printf("%s\n", str + 1);
    for (int i = 1; str[i]; ++i) {
        int id = str[i] - '0';
        if (!p->pNext[id]) return 0;
        p = p->pNext[id];
    }
    return p->cnt;
}
void init_prime() {
    for (int i = 2; i <= maxn - 20; i++) {
        if (!check[i]) { //说明i是质数
            prime[i] = true;
            for (int j = 2 * i; j <= maxn - 20; j += i) { //筛掉i的倍数
                check[j] = true; //那么j就没可能是质数了
                //book[j]=i; //表示j的最大质因数是i，不断更新。后面的质因数更大
                //用这个的时候，需要把2*i变成i，否则book[2]不行。
            }
        }
    }
    for (int i = 1000; i <= 9999; ++i) {
        int t = 0;
        int h = i;
        if (!prime[i]) continue;
        while (h / 10 > 0) {
            t = t * 10 + h % 10;
            h /= 10;
        }
        t = t * 10 + h;
        if (prime[t]) {
            goodprime[++lenprime] = i;
            insert(&T, t);
        }
    }
    return ;
}
int f[66];
bool book[204 + 20];
int ans;
bool tocheck(int toval[]) {
    for (int i = 1; i <= 4; ++i) {
        if (!find(T, toval[i])) return false;
    }
    return true;
}
void dfs(int cur, int valmain, int valother, int toval[]) {
    if (cur == 5) {
        ++ans;
        for (int i = 1; i <= 4; ++i) {
            printf("%d\n", goodprime[f[i]]);
        }
        if (ans != 136) printf("\n");
//        while(1);
        return;
    }
    for (int i = 1; i <= lenprime; ++i) {
        f[cur] = i;
        if (cur == 1) {
            valmain = valmain * 10 + strprime[i][1] - '0';
            valother = valother * 10 + strprime[i][4] - '0';
        } else if (cur == 2) {
            valmain = valmain * 10 + strprime[i][2] - '0';
            valother = valother * 10 + strprime[i][3] - '0';
        } else if (cur == 3) {
            valmain = valmain * 10 + strprime[i][3] - '0';
            valother = valother * 10 + strprime[i][2] - '0';
        } else {
            valmain = valmain * 10 + strprime[i][4] - '0';
            valother = valother * 10 + strprime[i][1] - '0';
        }
        for (int j = 1; j <= 4; ++j) {
            toval[j] = toval[j] * 10 + strprime[i][j] - '0';
        }
        if (!find(T, valmain) || !find(T, valother) || !tocheck(toval)) {
            valmain /= 10;
            valother /= 10;
            for (int j = 1; j <= 4; ++j) {
                toval[j] /= 10;
            }
            continue;
        }
//        printf("%d\n", ++ans);
        dfs(cur + 1, valmain, valother, toval);
        valmain /= 10;
        valother /= 10;
        for (int j = 1; j <= 4; ++j) {
            toval[j] /= 10;
        }
    }
}
void work() {
//    printf("%d\n", prime[9029]);
//    printf("%d\n", find(T, 9209));
    int toval[50] = {0};
    dfs(1, 0, 0, toval);
//    cout << ans << endl;
}

int main() {
#ifdef local
    freopen("data.txt","r",stdin);
#endif
    init_prime();
    work();
    return 0;
}

View Code