SmoothNumbersHard
SRM 388 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8565&rd=11122
给定N和K，返回N中最大素数因子小于等于K的数字个数

解法与素数的计算流程相通
自下向上，只是对每个数多记录一次其最大素数因子
 1mport java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class SmoothNumbersHard
 8{
 9    public int countSmoothNumbers(int N, int k)
10    {
11        boolean[] prime = new boolean[N+1];
12        int[] divider = new int[N+1];
13        Arrays.fill(prime,true);
14        Arrays.fill(divider, 1);
15        for(int i = 2 ; i <= N; ++ i){
16            if(prime[i]){
17                divider[i] = i;
18                for(int j = 2; i * j <= N; ++ j){
19                    prime[i*j] = false;
20                    divider[i*j] = i;
21                }
22            }
23        }
24        int ans = 0;
25        for(int i = 1 ; i <= N ; ++ i){
26            if(divider[i] <= k)
27                ans++;
28        }
29        return ans;
30    }
31    
posted @ 2009-11-08 19:54 jav7er 阅读(59) | 评论 (0) | 编辑 收藏
 
ProductBundling
TopCoder SRM324  Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=6811&rd=10004
给出n种商品不同顾客的购买选择，计算打包组合的商品，即所有顾客要么都买要么都不买的组合，返回最小的打包数。

最直接的想法就是遍历一边，每个顾客的数据分成不断对当前的各个包取交和取减分为更小的包
可是这样的复杂度高达2的N次方，以案例的数据量50来看一定是超时的
答案是将输入从不同顾客的产品选择转化成为不同产品的购买顾客
结果是直接比较两种产品的就可以知道是否可以在同一个包中
大大降低的复杂度
只要能相通这一点
后面的代码是非常容易的
posted @ 2009-11-07 19:42 jav7er 阅读(60) | 评论 (0) | 编辑 收藏
 
DivisibleByDigits
TopCoder SRM 375 Level2 950
http://www.topcoder.com/stat?c=problem_statement&pm=8318&rd=10794
给出一个数n，返回以n开头的可以被n的每一位非零数字整除的数。

题目本身暴力计算没难度
终点在于对有解性或者解的估计
由于1～9的最小公倍数是2520
所以在n0000到n2519中一定有一个数可以整除其所有位
最多计算次数也就是1＋10＋100＋1000＋2520
posted @ 2009-11-07 18:01 jav7er 阅读(83) | 评论 (0) | 编辑 收藏
 
OnTime
TopCoder SRM 339 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=7423&rd=10663
N个车站，若干辆车，每辆车有始发、终点、开车时间、运行时间和票价5个参数，求从第一站到最后一站在T时间内最便宜的乘车方案。

初看是很简单的DP，只要用数组从第一行向后逐行计算即可
可是后来看了测试数据发现了逆行车
所以在计算顺序上加了队列 相当于是一个宽搜

解决时候主要的问题出在了DP数组的定义上
一开始的思路是用车站和车去开二维数组
这样的话每个值又要用时间和价格两个参数去记录
计算过程也非常复杂
后来经过提示改成用车站和时间去记录价格
就方便多了

 1import java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class OnTime
 8{
 9    //the queue has to record two dimensions 
10    public class pair{
11        int n;
12        int t;
13        public pair(int n, int t){
14            this.n = n;
15            this.t = t;
16        }
17    }
18    
19    public int minCost(int N, int T, String[] buses)
20    {
21        int L = buses.length;
22        int[] a = new int[L];
23        int[] b = new int[L];
24        int[] depart = new int[L];
25        int[] time = new int[L];
26        int[] cost = new int[L];
27        
28        //data parse
29        int i;
30        for(i = 0; i < L; ++i){
31            String temps = buses[i];
32            String[] ints = temps.split(" ");
33            a[i] = Integer.parseInt(ints[0]);
34            b[i] = Integer.parseInt(ints[1]);
35            depart[i] = Integer.parseInt(ints[2]);
36            time[i] = Integer.parseInt(ints[3]);
37            cost[i] = Integer.parseInt(ints[4]);
38        }
39        
40        int[][] table = new int[N][T+1];
41        for(int[] ta : table)
42            Arrays.fill(ta, Integer.MAX_VALUE);
43        table[0][0] = 0;
44        
45        //first station is special
46        Queue<pair> q = new LinkedList<pair>();
47        for(i = 0 ; i < L; ++ i){
48            if(a[i] == 0 && depart[i] >= 0 && depart[i]+time[i] <= T){
49                table[b[i]][depart[i]+time[i]] = table[0][0] + cost[i];
50                q.add(new pair(b[i],depart[i]+time[i]));
51            }
52        }
53        
54        //bfs search
55        while(!q.isEmpty()){
56            pair out = q.poll();
57            for(i = 0; i < L; ++ i){
58                if(a[i] == out.n && depart[i] > out.t && depart[i] + time[i] <=T &&
59                        cost[i] + table[out.n][out.t] < table[b[i]][depart[i]+time[i]]){
60                    table[b[i]][depart[i]+time[i]] = table[out.n][out.t] + cost[i];
61                    q.add(new pair(b[i],depart[i]+time[i]));
62                }
63            }
64        }
65        
66        
67        //find min 
68        int min = table[N-1][0];
69        for(i = 1 ; i <= T ; ++ i){
70            if(table[N-1][i] < min)
71                min = table[N-1][i];
72        }
73        
74        
75        return (min==Integer.MAX_VALUE?-1:min);
76    
77    }
78}
posted @ 2009-11-07 10:46 jav7er 阅读(74) | 评论 (0) | 编辑 收藏
 
QuasiLatinSquares
TopCoder SRM 392 Level2 1000
原题地址：http://www.topcoder.com/stat?c=problem_statement&pm=8561&rd=11126
两个整数n和d, 1<=n<=10, 1<=d<=n,求一个n*n方阵，每一行每一列都存在0～d的每个数，如果有多个矩阵，返回字母序最小的一个。

从头递归搜索，对每个位置从小遍历所有值，针对每个值做如下操作：
1.赋值为0
2.检查该行剩下的位置是否足够放下还没有出现的所有的数，若否返回第一步并且＋＋；
3.检查该列剩下的位置是否足够放下还没有出现的所有的数，若否返回第一步并且＋＋；
4.现在是一个可以考虑的值，首先是终结值，若该位置已经是矩阵右下角，则返回true，这是唯一返回true的起点
5.向后递归调用函数，调用下一个位置
6.如果返回值为true，则返回true，否则继续
7.返回false

总的来说，递归的顺序，1是遍历所有可能值，2，3是排除和剪枝，4是检测成功条件，5是递归调用，6，7是递归的结果
算法的复杂度较高，（15，15）就已经算不出了，而且还不知道该怎么计算时间复杂度，这样的递归应该复杂度是很高的
可是通过剪枝应该优化了很多，不过不知道计算复杂度时侯要怎么考虑。

很大程度上还是根据提示写完的，代码能力太弱啦！
 1import java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class QuasiLatinSquares
 8{
 9    int[][] ans;
10    int n;
11    int d;
12    
13    public String[] makeSquare(int n, int d)
14    {
15        
16        this.n = n;
17        this.d = d;
18        ans = new int[n][n];
19        backtrace(0,0);
20        
21        //change the integer matrix to string array
22        String[] ret = new String[n];
23        for(int i = 0; i < n ; ++ i){
24            StringBuilder sb = new StringBuilder();
25            sb.append(ans[i][0]);
26            for(int j = 1; j < n ; ++ j){
27                sb.append(" ");
28                sb.append(ans[i][j]);
29            }
30            ret[i] = sb.toString();
31        }
32        return ret;
33    }
34    
35    public boolean backtrace(int i, int j){
36        //have to check every value here
37        for(int v = 0; v < d; ++ v){
38            ans[i][j] = v;
39            
40            //check whether still enough place for numbers that haven't appear
41            boolean[] row = new boolean[d];
42            boolean[] col = new boolean[d];
43            Arrays.fill(row, false);
44            Arrays.fill(col, false);
45            for(int rowidx = 0; rowidx <= i; ++ rowidx)
46                row[ans[rowidx][j]] = true;
47            for(int colidx = 0; colidx <= j; ++ colidx)
48                col[ans[i][colidx]] = true;
49            int rct = 0, cct = 0;
50            for(boolean b:row){
51                if(b == false) rct++;
52            }
53            for(boolean b:col){
54                if(b == false) cct++;
55            }
56            if(rct > n-1-i)
57                continue;
58            if(cct > n-1-j)
59                continue;
60            
61            //if it's the last place, success!
62            if((i == n-1) && (j == n-1))
63                return true;
64
65            //recursively calculate latter numbers based on this value
66            boolean next;
67            if(j != n-1)
68                next = backtrace(i,j+1);
69            else
70                next = backtrace(i+1,0);
71            //if it has reached the end,it means this value has led to success, else it means the value has to increase
72            if(next == true)
73                return true;
74            
75        }
76        //have checked every number but none matches, former numbers has to reconsider
77        return false;
78    }
79}
posted @ 2009-11-03 21:21 jav7er 阅读(77) | 评论 (0) | 编辑 收藏
 
仅列出标题
共2页: 上一页 1 2 
 
Powered by:
BlogJava
Copyright © jav7er