紫书第七章例题（暴力求解法）
1.除法（Division, UVa 725）
#include <cstdio>
#include <cstring>
bool isOk(int a, int b){
char buff[20];
int visited[15];
memset(visited, 0, sizeof(visited));
sprintf(buff, "%05d%05d", a, b);
for (int i =0; i < 10; i++){
int temp = buff[i] - '0';
if (0 == visited[temp]){
visited[temp]++;
} else {
return false;
}
}
return true;
}
int main(void){
int N, cnt = 0;
bool flag = false;
for (;scanf("%d", &N) && N;){
if (cnt > 0){
printf("\n");
}
cnt++;
flag = false;
for (int i = 1234; i< 100000; i++){
if (0 == i%N){
int ans = i/N;
if (isOk(i, ans)){
printf("%05d / %05d = %d\n", i, ans, N);
flag = true;
}
}
}
if (!flag){
printf("There are no solutions for %d.\n",N);
}
}
return 0;
}
View Code
PE了，真是神奇，，C++处理字符串还是不够熟练。这种简单题目不能一次过就说明还是太水啊！！
2.最大乘积（Maximum Product, UVa 11059）
1 #include <cstdio>
2 #include <cstring>
3 #define ll long long
4 int a[20], n, cnt;
5 int main(void){
6 for (cnt = 1;~scanf("%d", &n);cnt++){
7 for (int i = 1; i <= n; i++){
8 scanf("%d", &a[i]);
9 }
10 ll S = 1, maxn = 0;
11 for (int i = 1; i <= n; i++){
12 S = 1;//忘记
13 for (int j = i; j <= n; j++){
14 S *= a[j];
15 if (S > maxn){
16 maxn = S;
17 }
18 }
19 }
20 if (maxn < 0){
21 maxn = 0;
22 }
23 printf("Case #%d: The maximum product is %lld.\n\n", cnt, maxn);
24 getchar();
25 }
26 return 0;
27 }
View Code
WA，因为逻辑没理清，忘这忘那！！
3.素数环（Prime Ring Problem, UVa 524）
1 #include "cstdio"
2 #include "cstring"
3 #include "cmath"
4 int n,vis[20], A[20];
5 bool isPrime[50];
6
7 void dfs(int cur){
8 if (cur==n && isPrime[A[0]+A[n-1]]) {
9 for (int i=0; i < n-1; i++) printf("%d ", A[i]);
10 printf("%d\n", A[n-1]);
11 } else {
12 for (int i = 2; i <= n; i++) {
13 if (!vis[i] && isPrime[i+A[cur-1]]) {
14 A[cur] = i;
15 vis[i] = 1;
16 dfs(cur+1);
17 vis[i] = 0;
18 }
19 }
20 }
21 }
22 void check(){
23 for (int i = 2; i < 50; i++){
24 isPrime[i] = true;
25 for (int k = 2; k < sqrt(i)+1; k++){
26 if (i%k == 0){
27 isPrime[i] = false;
28 break;
29 }
30 }
31 }
32 }
33 int main(int argc, char const *argv[])
34 {
35 int t = 0;
36 check();
37 for (;~scanf("%d", &n);){
38 memset(vis, 0, sizeof(vis));
39 A[0] = 1;
40 if (t > 0){printf("\n");}
41 printf("Case %d:\n", ++t);
42 dfs(1);
43 }
44 return 0;
45 }
View Code
这一题PE两次，空行输出真是个大坑。
4.困难的串（Krypton Factor, UVa 129）
1 #include <cstdio>
2 #include <cstring>
3 #include <string>
4
5 int n,L, cnt;
6 char v[81];
7
8 bool judge(int cur)
9 {
10 for(int i=1;i<=(cur+1)/2;i++)//判断长度为2*i的后缀是否有相同的
11 {
12 bool equal=1;
13 for(int j=0;j<i;j++)
14 if(v[cur-i-j]!=v[cur-j])
15 {
16 equal=0;
17 break;
18 }
19 if(equal)
20 return false;
21 }
22 return true;
23 }
24
25 int dfs(int cur)
26 {
27 for(int i=0;i<L;i++)
28 {
29 v[cur]='A'+i;
30 if(judge(cur))
31 {
32 cnt++;
33 if(cnt==n)
34 {
35 //attention format
36 for (int i=0; i<=cur; i++){
37 printf("%c", v[i]);
38 if ((i+1)%4 == 0 && i!=cur) {
39 printf(" ");
40 }
41 if (i!=cur && (i+1)%64==0){
42 printf("\n");
43 }
44 }
45 printf("\n%d", cur+1);
46 return 1;
47 }
48 if(dfs(cur+1))
49 return 1;
50 }
51 }
52 return 0;
53 }
54
55 int main()
56 {
57 for(;scanf("%d%d", &n, &L);) {
58 cnt=0;
59 dfs(0);
60 }
61 return 0;
62 }
View Code
超时！
1 #include "cstdio"
2 int n, L, cnt;
3 int S[100];
4 int dfs(int cur){
5 if(cnt++ == n){
6 for(int i = 0; i < cur; i++) {
7 printf("%c", 'A'+S[i]);
8 if ((i+1)!=cur && (i+1)%4 ==0 && (i+1)!=64){printf(" ");}
9 if ((i+1)!=cur && (i+1)%64 == 0){printf("\n");}
10 }
11 printf("\n%d\n", cur);
12 return 0;
13 }
14 for(int i = 0; i < L; i++){
15 S[cur] = i;
16 int ok = 1;
17 for(int j = 1; j*2 <= cur+1; j++){
18 int equal = 1;
19 for(int k = 0; k < j; k++)
20 if(S[cur-k] != S[cur-k-j]) { equal = 0; break; }
21 if(equal) { ok = 0; break; }
22 }
23 if(ok) if(!dfs(cur+1)) return 0;
24 }
25 return 1;
26 }
27 int main(int argc, char const *argv[])
28 {
29 for (;scanf("%d%d", &n, &L) && n;){
30 cnt = 0;
31 dfs(0);
32 }
33 return 0;
34 }
View Code
PE三次，更可怕的是思路也被完全碾压，回溯！！
