題意：把一個正整數(shù)分成若干個互不相等正整數(shù)的和，使得分成的這些數(shù)字的乘機最大。
解題思路：把這些數(shù)分成從2開始的以1為公差的等差數(shù)列即可，如果最后一個數(shù)字不夠，就從后往前將其它數(shù)字加1。
純粹是一道數(shù)學題啊。
代碼
1
import java.io.*;
2import java.util.*;
3class Main
4
{
5
public static void main(String[] args)
6
{
7 Scanner sc = new Scanner(System.in);
8 int N = sc.nextInt();
9 int num[] = new int[200];
10 int count = 2;
11 int i;
12 for(i = 0; ; i++)
13 {
14 if(count <= N){
15 num[i] = count;
16 N -= count++;
17
}
18 else
19 break;
20 }
21 int len = i;
22 for(i = len - 1; i >= 0 && N > 0; i--)
23 {
24 num[i]++;
25 N--;
26 }
27 for(i = len - 1; i >= 0 && N > 0; i--)
28 {
29 num[i]++;
30 N--;
31 }
32 for(i = 0; i < len - 1; i++)
33 System.out.print(num[i] + " ");
34 System.out.println(num[i]);
35 }
36
}
37posted @
2013-04-06 22:26 小鼠標 閱讀(202) |
評論 (0) |
編輯 收藏
模擬題。
用一個棧記錄著訪問過的url，每遇到"VISIT"就將棧內當前頁面（nowp指向的頁面）之后的url扔掉，然后將本次訪問的url入棧。
代碼
1import java.io.*;
2import java.util.*;
3class Main
4{
5 public static void main(String[] args)
6 {
7 String[] urlStack = new String[110];
8 urlStack[0] = "http://www.acm.org/";
9 int top = 1;
10 int nowp = 0;
11 Scanner sc = new Scanner(System.in);
12 String strt = sc.nextLine();
13 while(!"QUIT".equals(strt)){
14 String[] strs = strt.split(" ");
15
16 if("VISIT".equals(strs[0])){
17 System.out.println(strs[1]);
18 top = nowp + 1;
19 urlStack[top++] = strs[1];
20 nowp++;
21 }
22 else if("BACK".equals(strs[0])){
23 if(nowp > 0){
24 System.out.println(urlStack[--nowp]);
25 }
26 else
27 System.out.println("Ignored");
28 }
29 else if("FORWARD".equals(strs[0])){
30 if(nowp < top - 1)
31 {
32 System.out.println(urlStack[++nowp]);
33 }
34 else
35 System.out.println("Ignored");
36 }
37
38 strt = sc.nextLine();
39 }
40
41
42 }
43
44}
45
posted @
2013-04-04 21:52 小鼠標 閱讀(180) |
評論 (0) |
編輯 收藏
摘要: 關于數(shù)字的題我的確不擅長，可能是抽象思維的能力太差了，多動手畫畫也許會好些。本以為這一題是DP，仔細分析之后才發(fā)現(xiàn)是模擬，原因是箱子之間的組合情況極其有限！
代碼Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1impor...
閱讀全文
posted @
2013-04-03 21:36 小鼠標 閱讀(164) |
評論 (0) |
編輯 收藏
摘要: 錯誤的解題思路：
回溯。用回溯是萬萬不行的，數(shù)據(jù)量是100^100。
正確的解題方式：
枚舉所有的帶寬b，即將所有出現(xiàn)的帶寬指定為minb枚舉一遍，對每個device，只需要選出device_b >= minb && device_p盡可能小。求出性價比最高的那個。數(shù)據(jù)量100 * 100。
閱讀全文
posted @
2013-03-27 17:53 小鼠標 閱讀(215) |
評論 (0) |
編輯 收藏
摘要: 題意：十二枚硬幣中有一個與其它重量不一樣，用天平只稱三次，請推斷出哪一枚銀幣與其它不一樣，是輕了還是重了？這是一道to satisty題目，就是去滿足給定的條件。解這類題目的思路有兩種：方法一、假設不知道那一枚硬幣有問題，根據(jù)條件推測出有問題的硬幣。方法二、依次假設硬幣有問題，看那種假設滿足題意。顯然，這類題目用第二種方法更好做，因為可以假設的情況是很少的。只需要把所有出現(xiàn)的硬幣都“懷...
閱讀全文
posted @
2013-03-22 22:31 小鼠標 閱讀(181) |
評論 (0) |
編輯 收藏
傳說中的約瑟夫環(huán)問題，剛開始想到的就是模擬，輸入10的時候就運行了數(shù)小時！網上搜索之后才知道是DP。這里有兩個重要的遞推公式：
1.
f[i] = (f[i - 1] + m) % i, f[1] = 0. f[i]表示
人數(shù)為i時最后活下來那個人的下標（從0開始），m為基數(shù)，即每數(shù)到m就讓該人出局
2.
f[i] = (f[i - 1] + m - 1) % (n - i + 1), f[0] = 0，f[i] 表示
第i輪出局的人的下標， n為一開始的總人數(shù)
解題用到的是第二個公式。
不過直接用遞推公式還是會超時，于是乎，我只好打表了。
代碼
1import java.io.*;
2import java.util.*;
3class Main
4{
5
6 public static void main(String[] args)throws Exception
7 {
8 Scanner sc = new Scanner(System.in);
9 int key[] = {0, 2, 7, 5,
10 30, 169, 441, 1872,
11 7632, 1740, 93313, 459901,
12 1358657, 2504881, 13482720};
13 int k = sc.nextInt();
14 while(k != 0)
15 {
16 /**//*for(int m = k + 1; ; m++)
17 {
18 if(isOK(k, m))
19 {
20 System.out.println(m);
21 break;
22 }
23 }*/
24 System.out.println(key[k]);
25 k = sc.nextInt();
26 }
27
28 }
29 public static boolean isOK(int k, int m)
30 {
31 int f = 0;
32 for(int i = 1; i <= k; i++)
33 {
34 f = (f + m - 1) % (2 * k - i + 1);
35 if(f < k)
36 {
37 return false;
38 }
39 }
40 return true;
41
42 }
43}
44
posted @
2013-03-21 14:34 小鼠標 閱讀(219) |
評論 (0) |
編輯 收藏
兩種日歷間的轉換，轉換思路是將Haab日歷轉換為實際天數(shù)，然后再轉換為Tzolkin日歷。進制轉換時需要注意，
取模時為了避免結果為0時的特殊情況，我們要采取一個小技巧。下面我舉例說明：
假設每月有30天，每月日期編號從1開始（也就是說日期號為1~30），請問今年的第11天是幾號？第60天呢？第61天呢？
回答上面的問題并不困難，可是程序中我們應該怎樣計算呢？
(11-1)%30 + 1 = 11，因此第11天是11號；
(60-1)%30 + 1 = 30，因此第60天是30號；
(61-1)%30 + 1 = 1，因此第61天是1號。
由上面的例子我們不難總結出下面的公式：
假設進制為D，基數(shù)為b（只有b~D+b-1這些數(shù)字），對任何一個從1開始計數(shù)的數(shù)字N，在該進制下的余數(shù)r可以表示為：
r=(N-1)%D + b
代碼
1import java.io.*;
2import java.util.*;
3import java.math.*;
4class Main
5{
6 private static TreeMap<String, Integer> haabmap = new TreeMap<String, Integer>();
7 private static String[] tmonth = {
8 "imix", "ik", "akbal", "kan", "chicchan",
9 "cimi", "manik", "lamat", "muluk", "ok",
10 "chuen", "eb", "ben", "ix", "mem",
11 "cib", "caban", "eznab", "canac", "ahau"
12 };
13
14 public static void main(String[] args)
15 {
16 getHaabmap();
17 Scanner sc = new Scanner(System.in);
18
19 int N = sc.nextInt();
20 sc.nextLine();
21 System.out.println(N);
22 for(int i = 0; i < N; i++)
23 {
24 String str1 = sc.nextLine();
25 String[] strArry = str1.split(" ");
26
27 int day = Integer.parseInt(
28 new String(strArry[0].toCharArray(), 0, strArry[0].length() - 1));
29 String month = strArry[1];
30 int year = Integer.parseInt(strArry[2]);
31
32 int allDays = day + 1;
33 allDays += (haabmap.get(month) - 1) * 20;
34 allDays += year * 365;
35
36 int tyear = (allDays - 1) / 260;//look here!!
37
38 int lastDays = (allDays - 1) % 260 + 1;//from 1
39 int forNumber = (lastDays - 1) % 13 + 1;//from 1
40 int forName = (lastDays - 1) % 20;//from 0
41 System.out.println(forNumber + " " + tmonth[forName] + " " + tyear);
42 }
43
44 }
45 public static void getHaabmap()
46 {
47 haabmap.put("pop", 1);
48 haabmap.put("no", 2);
49 haabmap.put("zip", 3);
50 haabmap.put("zotz", 4);
51 haabmap.put("tzec", 5);
52 haabmap.put("xul", 6);
53 haabmap.put("yoxkin", 7);
54 haabmap.put("mol", 8);
55 haabmap.put("chen", 9);
56 haabmap.put("yax", 10);
57 haabmap.put("zac", 11);
58 haabmap.put("ceh", 12);
59 haabmap.put("mac", 13);
60 haabmap.put("kankin", 14);
61 haabmap.put("muan", 15);
62 haabmap.put("pax", 16);
63 haabmap.put("koyab", 17);
64 haabmap.put("cumhu", 18);
65 haabmap.put("uayet", 19);
66 }
67}
68
posted @
2013-03-18 15:21 小鼠標 閱讀(279) |
評論 (0) |
編輯 收藏
簡單的排序題，用TreeSet實現(xiàn)。
TreeSet的排序方式有兩種：
1.讓元素自身具有可比較性，這種方法稱為自然順序或者默認順序
2.讓容器自身具有可比較性
這里是介紹第一中方法，這種方法的做法是利用元素自身的比較性，即元素實現(xiàn)
Comparable接口，覆蓋campareTo()方法。
再拓展一下。我們知道set中的元素不僅是有序的，而且是不能重復的，如何判斷元素是否重復呢？TreeSet和HashSet判斷方法并不一樣。在自然順序時，TreeSet判斷元素是否相同的依據(jù)是
compareTo()是否返回0，remove()和contains()也調用此方法。
代碼
1import java.io.*;
2import java.util.*;
3import java.math.*;
4class Main
5{
6
7 public static void main(String[] args)
8 {
9 Scanner sc = new Scanner(System.in);
10
11 int n, m;
12 n = sc.nextInt();
13 m = sc.nextInt();
14 sc.nextLine();
15 TreeSet<MyClass> strset = new TreeSet<MyClass>();
16 for(int i = 0; i < m; i++)
17 {
18 StringBuffer buf1 = new StringBuffer(sc.nextLine());
19
20 int value = 0;
21 for(int j = 0; j < n - 1; j++)
22 {
23 for(int k = j + 1; k < n; k++)
24 {
25 if(buf1.charAt(j) - buf1.charAt(k) > 0)
26 value ++;
27 }
28 }
29
30 strset.add(new MyClass(buf1, value, i));
31 }
32
33 /**//*for(MyClass myct : strset)
34 {
35 //System.out.println("::" + myct.getBuf() + "::v=" + myct.getValue()
36 // + "::seq=" + myct.getSeq());
37 System.out.println(myct.getBuf());
38 }*/
39 Iterator<MyClass> it = strset.iterator();
40 while(it.hasNext())
41 {
42 MyClass myc = it.next();
43 System.out.println(myc.getBuf());
44 }
45
46 }
47
48}
49class MyClass implements Comparable<MyClass>
50{
51 private StringBuffer buf;
52 private int value;
53 private int seq;
54 public MyClass(StringBuffer buf, int value, int seq)
55 {
56 this.buf = buf;
57 this.value = value;
58 this.seq = seq;
59 }
60 public StringBuffer getBuf()
61 {
62 return buf;
63 }
64 public int getValue()
65 {
66 return this.value;
67 }
68 public int getSeq()
69 {
70 return this.seq;
71
72 }
73 public int compareTo(MyClass myc2)
74 {
75 int t = this.value - myc2.value;
76 if(t == 0)
77 return this.seq - myc2.seq;
78 return t;
79
80 }
81}
82
posted @
2013-03-17 21:13 小鼠標 閱讀(266) |
評論 (0) |
編輯 收藏
摘要: 前天剛買了一個平板，安卓4.0，被它上面各種存儲器搞混了，今天抽空在網上了解一番，做出如下總結，對跟存儲器相關的各種名詞做出簡短的解釋。不到之處，還請各位指正。
閱讀全文
posted @
2013-03-16 21:33 小鼠標 閱讀(1993) |
評論 (0) |
編輯 收藏
摘要: 簡單的字符串處理，數(shù)據(jù)量比較大（E5），查找效率不高會超時。一開始用TreeSet，可是無法解決重新插入時的次數(shù)增加問題，因為TreeSet無法索引到具體某個元素。后來改用TreeMap，問題迎刃而解。
代碼Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/...
閱讀全文
posted @
2013-03-16 09:54 小鼠標 閱讀(159) |
評論 (0) |
編輯 收藏