題意:把一個正整數分成若干個互不相等正整數的和,使得分成的這些數字的乘機最大。
解題思路:把這些數分成從2開始的以1為公差的等差數列即可,如果最后一個數字不夠,就從后往前將其它數字加1。
純粹是一道數學題啊。

代碼
1
import java.io.*;
2
import java.util.*;
3
class 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
}
37
posted @
2013-04-06 22:26 小鼠標 閱讀(187) |
評論 (0) |
編輯 收藏
模擬題。
用一個棧記錄著訪問過的url,每遇到"VISIT"就將棧內當前頁面(nowp指向的頁面)之后的url扔掉,然后將本次訪問的url入棧。

代碼
1
import java.io.*;
2
import java.util.*;
3
class 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 小鼠標 閱讀(157) |
評論 (0) |
編輯 收藏
摘要: 關于數字的題我的確不擅長,可能是抽象思維的能力太差了,多動手畫畫也許會好些。本以為這一題是DP,仔細分析之后才發現是模擬,原因是箱子之間的組合情況極其有限!
代碼Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1impor...
閱讀全文
posted @
2013-04-03 21:36 小鼠標 閱讀(152) |
評論 (0) |
編輯 收藏
摘要: 錯誤的解題思路:
回溯。用回溯是萬萬不行的,數據量是100^100。
正確的解題方式:
枚舉所有的帶寬b,即將所有出現的帶寬指定為minb枚舉一遍,對每個device,只需要選出device_b >= minb && device_p盡可能小。求出性價比最高的那個。數據量100 * 100。
閱讀全文
posted @
2013-03-27 17:53 小鼠標 閱讀(195) |
評論 (0) |
編輯 收藏
摘要: 題意:十二枚硬幣中有一個與其它重量不一樣,用天平只稱三次,請推斷出哪一枚銀幣與其它不一樣,是輕了還是重了?這是一道to satisty題目,就是去滿足給定的條件。解這類題目的思路有兩種:方法一、假設不知道那一枚硬幣有問題,根據條件推測出有問題的硬幣。方法二、依次假設硬幣有問題,看那種假設滿足題意。顯然,這類題目用第二種方法更好做,因為可以假設的情況是很少的。只需要把所有出現的硬幣都“懷...
閱讀全文
posted @
2013-03-22 22:31 小鼠標 閱讀(164) |
評論 (0) |
編輯 收藏
傳說中的約瑟夫環問題,剛開始想到的就是模擬,輸入10的時候就運行了數小時!網上搜索之后才知道是DP。這里有兩個重要的遞推公式:
1.
f[i] = (f[i - 1] + m) % i, f[1] = 0. f[i]表示
人數為i時最后活下來那個人的下標(從0開始),m為基數,即每數到m就讓該人出局
2.
f[i] = (f[i - 1] + m - 1) % (n - i + 1), f[0] = 0,f[i] 表示
第i輪出局的人的下標, n為一開始的總人數
解題用到的是第二個公式。
不過直接用遞推公式還是會超時,于是乎,我只好打表了。

代碼
1
import java.io.*;
2
import java.util.*;
3
class 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 小鼠標 閱讀(201) |
評論 (0) |
編輯 收藏
兩種日歷間的轉換,轉換思路是將Haab日歷轉換為實際天數,然后再轉換為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,基數為b(只有b~D+b-1這些數字),對任何一個從1開始計數的數字N,在該進制下的余數r可以表示為:
r=(N-1)%D + b

代碼
1
import java.io.*;
2
import java.util.*;
3
import java.math.*;
4
class 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 小鼠標 閱讀(258) |
評論 (0) |
編輯 收藏
簡單的排序題,用TreeSet實現。
TreeSet的排序方式有兩種:
1.讓元素自身具有可比較性,這種方法稱為自然順序或者默認順序
2.讓容器自身具有可比較性
這里是介紹第一中方法,這種方法的做法是利用元素自身的比較性,即元素實現
Comparable接口,覆蓋campareTo()方法。
再拓展一下。我們知道set中的元素不僅是有序的,而且是不能重復的,如何判斷元素是否重復呢?TreeSet和HashSet判斷方法并不一樣。在自然順序時,TreeSet判斷元素是否相同的依據是
compareTo()是否返回0,remove()和contains()也調用此方法。

代碼
1
import java.io.*;
2
import java.util.*;
3
import java.math.*;
4
class 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
}
49
class 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 小鼠標 閱讀(250) |
評論 (0) |
編輯 收藏
摘要: 前天剛買了一個平板,安卓4.0,被它上面各種存儲器搞混了,今天抽空在網上了解一番,做出如下總結,對跟存儲器相關的各種名詞做出簡短的解釋。不到之處,還請各位指正。
閱讀全文
posted @
2013-03-16 21:33 小鼠標 閱讀(1954) |
評論 (0) |
編輯 收藏
摘要: 簡單的字符串處理,數據量比較大(E5),查找效率不高會超時。一開始用TreeSet,可是無法解決重新插入時的次數增加問題,因為TreeSet無法索引到具體某個元素。后來改用TreeMap,問題迎刃而解。
代碼Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/...
閱讀全文
posted @
2013-03-16 09:54 小鼠標 閱讀(145) |
評論 (0) |
編輯 收藏