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