标题：密文搜索
福尔摩斯从X星收到一份资料，全部是小写字母组成。
他的助手提供了另一份资料：许多长度为8的密码列表。
福尔摩斯发现，这些密码是被打乱后隐藏在先前那份资料中的。
请你编写一个程序，从第一份资料中搜索可能隐藏密码的位置。要考虑密码的所有排列可能性。
数据格式：
输入第一行：一个字符串s，全部由小写字母组成，长度小于1024*1024
紧接着一行是一个整数n,表示以下有n行密码，1<=n<=1000
紧接着是n行字符串，都是小写字母组成，长度都为8
要求输出：
一个整数, 表示每行密码的所有排列在s中匹配次数的总和。
例如：
用户输入：
aaaabbbbaabbcccc
2
aaaabbbb
abcabccc
则程序应该输出：
4
这是因为：第一个密码匹配了3次，第二个密码匹配了1次，一共4次。
资源约定：
峰值内存消耗（含虚拟机） < 512M
CPU消耗 < 5000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
package action; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class demo { public static void getResult(String A, String[] pwd) { int count = 0; ArrayList<Integer> list = new ArrayList<Integer>(); int[] num = new int[pwd.length]; for(int i = 0;i < pwd.length;i++) { int hash = pwd[i].hashCode(); if(list.contains(hash)) { int j = list.indexOf(hash); num[j]++; } else { list.add(hash); num[list.size() - 1]++; } } for(int i = 0;i <= A.length() - 8;i++) { String s = A.substring(i, i + 8); char[] temp = s.toCharArray(); Arrays.sort(temp); StringBuffer t = new StringBuffer(""); for(int j = 0;j < 8;j++) t.append(temp[j]); s = t.toString(); int hash = s.hashCode(); if(list.contains(hash)) { int k = list.indexOf(hash); count = count + num[k]; } } System.out.println(count); } public static void main(String[] args) { Scanner in = new Scanner(System.in); String A = in.next(); int n = in.nextInt(); String[] pwd = new String[n]; for(int i = 0;i < n;i++) { char[] arrayP = in.next().toCharArray(); Arrays.sort(arrayP); StringBuffer s = new StringBuffer(""); for(int j = 0;j < arrayP.length;j++) s.append(arrayP[j]); pwd[i] = s.toString(); } getResult(A, pwd); } }
标题：居民集会
蓝桥村的居民都生活在一条公路的边上，公路的长度为L，每户家庭的位置都用这户家庭到公路的起点的距离来计算，第i户家庭距起点的距离为di。
每年，蓝桥村都要举行一次集会。今年，由于村里的人口太多，村委会决定要在4个地方举行集会，其中3个位于公路中间，1个位最公路的终点。
已知每户家庭都会向着远离公路起点的方向去参加集会，参加集会的路程开销为家庭内的人数ti与距离的乘积。
给定每户家庭的位置di和人数ti，请为村委会寻找最好的集会举办地：p1, p2, p3, p4 (p1<=p2<=p3<=p4=L),使得村内所有人的路程开销和最小。
【输入格式】
输入的第一行包含两个整数n, L，分别表示蓝桥村的家庭数和公路长度。
接下来n行，每行两个整数di, ti，分别表示第i户家庭距离公路起点的距离和家庭中的人数。
【输出格式】
输出一行，包含一个整数，表示村内所有人路程的开销和。
【样例输入】
6 10
1 3
2 2
4 5
5 20
6 5
8 7
【样例输出】
18
【样例说明】
在距起点2, 5, 8, 10这4个地方集会，6个家庭需要的走的距离分别为1, 0, 1, 0, 2, 0，总的路程开销为1*3+0*2+1*5+0*20+2*5+0*7=18。
【数据规模与约定】
对于10%的评测数据，1<=n<=300。
对于30%的评测数据，1<=n<=2000，1<=L<=10000，0<=di<=L，di<=di+1，0<=ti<=20。
对于100%的评测数据，1<=n<=100000，1<=L<=1000000，0<=di<=L，di<=di+1，0<=ti<=1000000。
资源约定：
峰值内存消耗（含虚拟机） < 512M
CPU消耗 < 8000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意：不要使用package语句。不要使用jdk1.7及以上版本的特性。
注意：主类的名字必须是：Main，否则按无效代码处理。
package action; import java.util.Scanner; public class demo { public static int n, L; public static int[] D, T; public static int[][] W; public static int mergeValue(int start, int end, int count) { if(count == 0) return W[start][end]; int result = W[0][L]; for(int i = start + 1;i < end;i++) { int left = mergeValue(start, i, count - 1); int right = mergeValue(i, end, count - 1); result = Math.min(result, left + right); } return result; } public static void getResult() { for(int i = 0;i <= L;i++) for(int j = i;j <= L;j++) for(int k = 0;k < n;k++) { if(D[k] > i && D[k] < j) W[i][j] += (j - D[k]) * T[k]; } int result = mergeValue(0, L, 2); System.out.println(result); } public static void main(String[] args) { Scanner in = new Scanner(System.in); n = in.nextInt(); L = in.nextInt(); D = new int[n]; T = new int[n]; W = new int[L + 1][ L + 1]; for(int i = 0;i < n;i++) { D[i] = in.nextInt(); T[i] = in.nextInt(); } getResult(); } }
样例跑出来了。我准备了真实测试数据，但是不行。。。。很尴尬。
第一个测试数据
299 9998 51 7 66 20 146 18 151 19 154 15 157 12 162 8 199 15 215 14 227 9 338 17 339 19 373 7 379 14 383 5 683 3 684 7 687 20 688 7 713 16 728 10 794 18 810 12 838 10 841 7 854 5 863 19 909 20 915 10 981 9 1030 9 1085 15 1091 5 1145 1 1188 14 1210 14 1225 1 1262 5 1278 1 1286 18 1349 9 1390 10 1393 10 1419 7 1433 14 1445 20 1461 18 1469 20 1486 11 1500 14 1538 1 1540 13 1557 18 1589 1 1666 14 1712 15 1754 15 1904 17 1930 2 1952 10 1988 8 2015 13 2022 1 2022 5 2040 10 2088 5 2104 5 2188 1 2204 11 2217 6 2231 9 2424 10 2427 11 2445 16 2451 19 2508 7 2525 6 2543 18 2547 16 2548 20 2554 3 2562 1 2572 19 2608 18 2635 6 2651 1 2658 9 2674 13 2785 8 2866 17 2950 5 2976 16 2990 9 3031 5 3074 8 3101 4 3123 8 3170 14 3178 5 3186 12 3311 6 3331 16 3336 13 3391 5 3555 10 3569 14 3625 16 3698 7 3709 9 3711 13 3718 1 3794 9 3833 10 3859 12 3883 9 3888 3 3988 10 4094 20 4149 7 4179 10 4241 17 4243 20 4289 16 4303 14 4316 10 4330 17 4366 15 4378 18 4378 17 4384 19 4401 13 4448 3 4457 20 4523 5 4539 2 4574 13 4639 20 4655 20 4671 13 4819 11 4888 20 4898 15 4917 10 4924 13 5054 2 5058 19 5097 7 5101 20 5192 14 5193 11 5198 17 5199 20 5207 13 5229 12 5268 7 5318 8 5361 3 5374 1 5391 15 5398 5 5460 19 5519 12 5539 5 5541 18 5611 10 5617 6 5625 14 5633 12 5636 19 5707 9 5732 10 5763 7 5763 15 5802 1 5806 20 5815 2 5856 1 5882 17 5918 9 5960 5 5985 18 6006 18 6024 20 6064 13 6084 14 6130 16 6160 2 6175 18 6255 12 6277 18 6300 10 6310 19 6334 13 6388 8 6457 9 6475 1 6484 8 6527 19 6544 14 6551 12 6649 6 6718 19 6726 3 6755 3 6796 10 6798 7 6804 13 6819 6 6880 1 6903 12 6915 6 6958 2 6996 18 7054 2 7136 2 7238 15 7328 2 7367 19 7389 12 7404 12 7444 1 7470 10 7520 17 7534 2 7559 18 7678 5 7682 13 7752 4 7793 10 7812 13 7815 3 7864 15 7867 16 7871 1 7874 15 7922 19 7942 13 8030 6 8070 3 8083 3 8147 1 8179 11 8191 4 8219 11 8224 19 8249 5 8289 9 8318 16 8372 11 8391 3 8406 15 8489 6 8518 6 8543 6 8586 13 8598 4 8649 20 8652 6 8755 1 8757 7 8769 4 8854 14 8875 19 8952 15 9022 3 9092 11 9094 4 9096 11 9097 8 9105 8 9169 20 9206 3 9241 8 9243 6 9258 18 9272 20 9337 19 9344 8 9347 7 9476 2 9496 12 9526 3 9541 2 9574 8 9586 15 9676 6 9700 16 9706 3 9709 13 9764 10 9772 9 9778 10 9822 2 9832 3 9865 12 9876 18 9915 2 9944 12 9953 5
第二个就时间忒长了。
