sgu 502

Posted on 2010-12-07 18:23 王之昊 阅读(385) 评论(0)  编辑 收藏 引用 所属分类: sgu
题目大意是给你一个数 n (1<=n <= 1017), 现在可以重排 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] == 0continue;
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] == 0continue;
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-10) )
66         {
67             print(size-10);
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(00) ){
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 }


只有注册用户登录后才能发表评论。
相关文章:
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


posts - 26, comments - 7, trackbacks - 0, articles - 17

Copyright © 王之昊