题意:把一个正整数分成若干个互不相等正整数的和,使得分成的这些数字的乘机最大。
解题思路:把这些数分成从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 小鼠标 阅读(185) |
评论 (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 小鼠标 阅读(155) |
评论 (0) |
编辑 收藏
摘要: 关于数字的题我的确不擅长,可能是抽象思维的能力太差了,多动手画画也许会好些。本以为这一题是DP,仔细分析之后才发现是模拟,原因是箱子之间的组合情况极其有限!
代码Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/--> 1impor...
阅读全文
posted @
2013-04-03 21:36 小鼠标 阅读(149) |
评论 (0) |
编辑 收藏
摘要: 错误的解题思路:
回溯。用回溯是万万不行的,数据量是100^100。
正确的解题方式:
枚举所有的带宽b,即将所有出现的带宽指定为minb枚举一遍,对每个device,只需要选出device_b >= minb && device_p尽可能小。求出性价比最高的那个。数据量100 * 100。
阅读全文
posted @
2013-03-27 17:53 小鼠标 阅读(193) |
评论 (0) |
编辑 收藏
摘要: 题意:十二枚硬币中有一个与其它重量不一样,用天平只称三次,请推断出哪一枚银币与其它不一样,是轻了还是重了?这是一道to satisty题目,就是去满足给定的条件。解这类题目的思路有两种:方法一、假设不知道那一枚硬币有问题,根据条件推测出有问题的硬币。方法二、依次假设硬币有问题,看那种假设满足题意。显然,这类题目用第二种方法更好做,因为可以假设的情况是很少的。只需要把所有出现的硬币都“怀...
阅读全文
posted @
2013-03-22 22:31 小鼠标 阅读(160) |
评论 (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 小鼠标 阅读(200) |
评论 (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 小鼠标 阅读(255) |
评论 (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 小鼠标 阅读(247) |
评论 (0) |
编辑 收藏
摘要: 前天刚买了一个平板,安卓4.0,被它上面各种存储器搞混了,今天抽空在网上了解一番,做出如下总结,对跟存储器相关的各种名词做出简短的解释。不到之处,还请各位指正。
阅读全文
posted @
2013-03-16 21:33 小鼠标 阅读(1942) |
评论 (0) |
编辑 收藏
摘要: 简单的字符串处理,数据量比较大(E5),查找效率不高会超时。一开始用TreeSet,可是无法解决重新插入时的次数增加问题,因为TreeSet无法索引到具体某个元素。后来改用TreeMap,问题迎刃而解。
代码Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/...
阅读全文
posted @
2013-03-16 09:54 小鼠标 阅读(144) |
评论 (0) |
编辑 收藏