Solve

USACO 4.3.2 Prime3

题目解答

这是一个比较优秀的枚举搜索题目。所用策略：构造 + 二分 + 枚举 + 剪枝。

其实题目本身不难，我的方法是：先构造出所有要用到的素数，然后在这个已经压缩的状态空间中枚举。因为素数构造好了，所以检索一个数字是否是素数时可以直接二分。搜索时先要搜对角线，然后有两个顺序去继续搜索： A，由内到外； B，由外到内。事实上对于这道题目，可以进行最大限度的剪枝才是好的顺序，所以综合考虑 B是更好的选择。

USACO 4.3.2

剪枝策略：(以下剪枝缺一不可)

  1. 素数与加和判断。
  2. 起始不为 0的判断。
  3. 末尾为奇判断。

总结，事实上我这样做并不能加快程序的速度，唯一的优点是空间小(对于 C++)，以及编程的难度小(虽然长，但是很好写，至少循环层次很少)。另外我做了A顺序的程序，第三个点就达到13s！如有兴趣参观我的第一个程序可以联系我。

运行结果

Compiling…
Compile: OK
Executing…
Test 1: TEST OK [0.119 secs, 2972 KB]
Test 2: TEST OK [0.140 secs, 2972 KB]
Test 3: TEST OK [0.151 secs, 2972 KB]
Test 4: TEST OK [0.238 secs, 2972 KB]
Test 5: TEST OK [0.227 secs, 2972 KB]
Test 6: TEST OK [0.637 secs, 2972 KB]
Test 7: TEST OK [0.637 secs, 2972 KB]
Test 8: TEST OK [0.799 secs, 2972 KB]
Test 9: TEST OK [1.220 secs, 2972 KB]
Test 10: TEST OK [1.696 secs, 2972 KB] //我感觉我的程序是以时间换空间 = =|||
All tests OK.

Your program (‘prime3’) produced all correct answers! This is your
submission #3 for this problem. Congratulations!

程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include<cstdio>
#include<cstring>
#include<cmath>
#define BIG 1005
const bool LIE = true;
struct node{
    int num[6],val;
}pri[BIG];
int K1,Lenp,TOTAL,FIRST,ranc[6][6],RANC[BIG][6][6],outtot,multi[]={0,1,10,100,1000,10000};
inline bool checkprime(const int &prime){ //二分法查找
    if(!(prime&1)) return false ;
    int left=1,right=Lenp,mid=(left+right)>>1;
    while(left<right){
        if(prime>pri[mid].val){
            left=mid+1;
            mid=(left+right)>>1;
        }
        else{
            right=mid;
            mid=(left+right)>>1;
        }
    }
    if(prime==pri[left].val) return true ;
    return false;
}
inline int add(const bool &lie, const int &pos,const int &len){ //求和函数
    int sum=0;
    if(lie) for(int i=1;i<=len;i++) sum+=ranc[i][pos];
        else for (int i=1;i<=len;i++) sum+=ranc[pos][i];
    return sum;
}
inline int multiply(const bool &lie, const int &pos){ //求数字的函数
    int num=0;
    if(lie) for(int i=1;i<=5;i++) num+=ranc[i][pos]*multi[6-i];
        else for (int i=1;i<=5;i++) num+=ranc[pos][i]*multi[6-i];
    return num;
}
inline int multiply(const bool &lie, const int &wh,const int &pos){ //求数字的函数
    int num=0;
    if(lie) for(int i=1;i<=5;i++) num+=RANC[wh][i][pos]*multi[6-i];
        else for (int i=1;i<=5;i++) num+=RANC[wh][pos][i]*multi[6-i];
    return num;
}
inline void lastcheck(){ //可行性判断，并生成最终方案
    int TOT2,TOT3,TOT4,TOT5,TOT6;
    TOT3=add(!LIE,2,5)-ranc[2][3];
    TOT4=add(!LIE,4,5)-ranc[4][3];
    if(TOT3>TOTAL || TOT4>TOTAL ) return;
    ranc[2][3]=TOTAL-TOT3;ranc[4][3]=TOTAL-TOT4;
    TOT2=multiply(LIE,3);TOT4=multiply(!LIE,2);
    TOT5=multiply(!LIE,3);TOT6=multiply(!LIE,4);
    if(!checkprime(TOT2) || !checkprime(TOT5) || !
        checkprime(TOT4) || !checkprime(TOT6)) return;
    memcpy(RANC[++outtot],ranc, sizeof(ranc));
}
bool midpane2(int lev){
    if(lev>2){
        lastcheck();
        return true ;
    }
    switch(lev){
        case(1):
               for(int i=1;i<=Lenp;i++)
                if(pri[i].num[1]==ranc[1][1] && pri[i].num[5]==ranc[5][1]
                && pri[i].num[2] && pri[i].num[3] && pri[i].num[4]){
                    for(int i1=2;i1<=4;i1++) ranc[i1][1]=pri[i].num[i1];
                    if(!midpane2(lev+1)) return false;
                }
        break;
        case(2):
               for(int i=1;i<=Lenp;i++)
                if(pri[i].num[1]==ranc[1][5] && pri[i].num[5]==ranc[5][5]
                && (pri[i].num[2]&1) && (pri[i].num[3]&1) && (pri[i].num[4]&1)){
                    for(int i1=2;i1<=4;i1++) ranc[i1][5]=pri[i].num[i1];
                    if(!midpane2(lev+1)) return false;
                }
        break;
    }
    return true;
}
bool midpane1(int lev){
    if(lev>2){
        int TOT1,TOT2; //以下是可行性剪枝
        TOT1=add(LIE,2,5)-ranc[3][2];
        TOT2=add(LIE,4,5)-ranc[3][4];
        if(TOT1>TOTAL || TOT2>TOTAL) return true;
        ranc[3][2]=TOTAL-TOT1;ranc[3][4]=TOTAL-TOT2;
        TOT1=multiply(LIE,2);TOT2=multiply(LIE,4);
        if(!checkprime(TOT1) || !checkprime(TOT2)) return true;
        midpane2(1);
        return true ;
    }
    switch(lev){
        case(1):
            for(int i=1;i<=Lenp;i++)
                if(pri[i].num[1]==ranc[1][1] && pri[i].num[5]==ranc[1][5]
                && pri[i].num[2] && pri[i].num[3] && pri[i].num[4]){ //对于开头是否是0要剪枝
                    for(int i1=2;i1<=4;i1++) ranc[1][i1]=pri[i].num[i1];
                    if(!midpane1(lev+1)) return false;
                }
        break;
        case(2):
               for(int i=1;i<=Lenp;i++)
                if(pri[i].num[1]==ranc[5][1] && pri[i].num[5]==ranc[5][5]
                && (pri[i].num[2]&1) && (pri[i].num[3]&1) && (pri[i].num[4]&1)){ //末尾的剪枝：判断是不是奇数
                    for(int i1=2;i1<=4;i1++) ranc[5][i1]=pri[i].num[i1];
                    if(!midpane1(lev+1)) return false;
                }
        break;
    }
    return true;
}
inline void crosspane(){
    for(int i=1;i<=Lenp;i++)
        if(pri[i].num[1]==FIRST){
            for(int i1=1;i1<=5;i1++) ranc[i1][i1]=pri[i].num[i1];
            for(int j=1;j<=Lenp;j++)
                if(pri[j].num[3]==ranc[3][3]){
                    for(int j1=1;j1<=5;j1++) ranc[j1][6-j1]=pri[j].num[6-j1]; //以下是可行性剪枝，对于当前总和超过TOTAL的要剪掉
                    if(ranc[1][1]+ranc[1][5]>TOTAL || ranc[1][1]+ranc[5][1]>TOTAL || ranc[5][1]+ranc[5][5]>TOTAL || ranc[1][5]+ranc[5][5]>TOTAL ||
                       ranc[2][2]+ranc[2][4]>TOTAL || ranc[2][2]+ranc[4][2]>TOTAL || ranc[4][2]+ranc[4][4]>TOTAL || ranc[4][4]+ranc[4][2]>TOTAL)
                       continue;
                    midpane1(1);
                }
        }
}
inline bool cmp(const int &A, const int &B){
    int ma,mb;
    for(int i=1;i<=5;i++){
        ma=multiply(!LIE,A,i);
        mb=multiply(!LIE,B,i);
        if(ma<mb) return true;
        if(ma==mb) continue ;
        if(ma>mb) return false;
    }
    return false;
}
inline void sort(){
    int ranc[6][6];
    for(int i=1;i<outtot;i++)
        for(int j=1;j<=outtot-i;j++)
            if(cmp(j,j+1)){
                memcpy(ranc,RANC[j], sizeof(RANC[j]));
                memcpy(RANC[j],RANC[j+1], sizeof(RANC[j+1]));
                memcpy(RANC[j+1],ranc, sizeof(ranc));
            }
}
int main()
{
    freopen("prime3.in", "r",stdin);
    freopen("prime3.out", "w",stdout);
    scanf("%d%d",&TOTAL,&FIRST);
    for(int i=10001;i<=99997;i+=2){ //提前构造出满足条件的素数
        bool flag=false ;
        for(int j=2;j<=(int)sqrt(i);j++) if(i%j==0){flag=true ;break;}
        if(!flag){
            int total=0,k=i,num[6],pos=0;
            while(k>0){
                num[6-(++pos)]=k%10;
                total+=num[6-pos];
                k/=10;
            }
            if(total==TOTAL){
                memcpy(pri[++Lenp].num,num, sizeof(num));
                pri[Lenp].val=i;
            }
        }
    }
    crosspane();
    sort(); //冒泡排序
    for(int k=outtot;k>=1;k--){
        for(int i=1;i<=5;i++){
            for(int j=1;j<=5;j++)
                printf( "%d",RANC[k][i][j]);
            printf( "\n");
        }
        if(k!=1) printf("\n" );
    }
    if(!outtot) printf( "NONE\n");
    return 0;
}

后记

本文是百度空间的移植，附：全部USACO题目解答。