Posted on 2010-12-07 18:23
王之昊 阅读(386)
评论(0) 编辑 收藏 引用 所属分类:
sgu
题目大意是给你一个数 n (1<=n <= 10
17), 现在可以重排 n 的数位，寻找一种排列使得其能够整除 17。
开始写了一个集合DP的代码。结果TLE，感觉比较奇怪，算复杂度是17*17*(2^17)=3千多万。不过过了300+的人，做到这里就感觉自己做复杂了。
后来才发现直接搜可以跑到52ms，不过到现在还是不会估计搜索的效率。只是感觉搜索很强大。
附录 一：TLE代码（集合DP）
1 import java.util.Scanner;
2
3 class Permutation{
4 int []digits;
5 int [][]visit;
6 int size;
7
8 void read(){
9 Scanner sc = new Scanner(System.in);
10 String str = sc.next();
11 digits = new int[str.length()];
12 for(int i = 0; i < str.length(); i++)
13 digits[i] = str.charAt(i) - '0';
14
15 size = 1 << digits.length;
16 visit = new int[size][17];
17 for(int i = 0; i < size; i++)
18 for(int j = 0; j < 17; j++){
19 visit[i][j] = -1;
20 }
21 }
22
23 boolean find(int a, int b){
24
25 if(a==0)return b==0;
26
27 if(visit[a][b] == 0)return false;
28 if(visit[a][b] == 1)return true;
29
30 for(int i = 0; i < digits.length; i++){
31 if( ( (1<<i) & a ) == 0)continue;
32
33 int na = a ^ (1<<i);
34 int nb = (17 + b - digits[i]) * 12 % 17;
35 if(na == 0 && digits[i] == 0) continue;
36
37 if( find( na, nb) ){
38 visit[a][b] = 1;
39 return true;
40 }
41 }
42
43 visit[a][b] = 0;
44 return false;
45 }
46
47 void print(int a, int b){
48 if( a == 0)return;
49 for(int i = 0; i < digits.length; i++){
50 if( ( (1<<i) & a ) == 0)continue;
51
52 int na = a ^ (1<<i);
53 int nb = (17 + b - digits[i]) * 12 % 17;
54 if(na == 0 && digits[i] == 0) continue;
55
56 if( find( na, nb) ){
57 print(na, nb);
58 System.out.print(digits[i]);
59 break;
60 }
61 }
62 }
63
64 void work(){
65 if( find(size-1, 0) )
66 {
67 print(size-1, 0);
68 System.out.println();
69 }
70 else
71 System.out.println(-1);
72 }
73 }
74
75 public class Solution{
76 public static void main(String[] args)throws Exception{
77 Permutation P = new Permutation();
78 P.read();
79 P.work();
80 }
81 }
附录二：Accept代码（dfs）
1 import java.util.Scanner;
2 import java.util.Arrays;
3 class Permutation{
4 int []digits;
5 int []ans;
6 static int size = 10;
7
8 void read(){
9 Scanner sc = new Scanner(System.in);
10 String str = sc.next();
11
12 ans = new int[ str.length() ];
13 digits = new int[size];
14 Arrays.fill(digits, 0);
15
16 for(int i = 0; i < str.length(); i++)
17 digits[ str.charAt(i) - '0' ] ++ ;
18 }
19
20 boolean dfs(int len, int res){
21 if(len == ans.length)return res == 0;
22
23 for(int i = 0; i < size; i++){
24 if(i==0 && len == 0)continue;
25 if(digits[i] > 0){
26 digits[i]--;
27
28 ans[len] = i;
29 if(dfs(len+1, (res*10 + i) % 17) )return true;
30
31 digits[i]++;
32 }
33 }
34 return false;
35 }
36
37 void work(){
38 if( dfs(0, 0) ){
39 for(int i = 0; i < ans.length; i++)
40 System.out.print(ans[i]);
41 System.out.println();
42 }
43 else
44 System.out.println(-1);
45 }
46 }
47
48 public class Solution{
49 public static void main(String[] args)throws Exception{
50 Permutation P = new Permutation();
51 P.read();
52 P.work();
53 }
54 }