1.标题： 购物单
小明刚刚找到工作，老板人很好，只是老板夫人很爱购物。老板忙的时候经常让小明帮忙到商场代为购物。小明很厌烦，但又不好推辞。
这不，XX大促销又来了！老板夫人开出了长长的购物单，都是有打折优惠的。
小明也有个怪癖，不到万不得已，从不刷卡，直接现金搞定。
现在小明很心烦，请你帮他计算一下，需要从取款机上取多少现金，才能搞定这次购物。
取款机只能提供100元面额的纸币。小明想尽可能少取些现金，够用就行了。
你的任务是计算出，小明最少需要取多少现金。
以下是让人头疼的购物单，为了保护隐私，物品名称被隐藏了。
-----------------
**** 180.90 88折
**** 10.25 65折
**** 56.14 9折
**** 104.65 9折
**** 100.30 88折
**** 297.15 半价
**** 26.75 65折
**** 130.62 半价
**** 240.28 58折
**** 270.62 8折
**** 115.87 88折
**** 247.34 95折
**** 73.21 9折
**** 101.00 半价
**** 79.54 半价
**** 278.44 7折
**** 199.26 半价
**** 12.97 9折
**** 166.30 78折
**** 125.50 58折
**** 84.98 9折
**** 113.35 68折
**** 166.57 半价
**** 42.56 9折
**** 81.90 95折
**** 131.78 8折
**** 255.89 78折
**** 109.17 9折
**** 146.69 68折
**** 139.33 65折
**** 141.16 78折
**** 154.74 8折
**** 59.42 8折
**** 85.44 68折
**** 293.70 88折
**** 261.79 65折
**** 11.30 88折
**** 268.27 58折
**** 128.29 88折
**** 251.03 8折
**** 208.39 75折
**** 128.88 75折
**** 62.06 9折
**** 225.87 75折
**** 12.89 75折
**** 34.28 75折
**** 62.16 58折
**** 129.12 半价
**** 218.37 半价
**** 289.69 8折
--------------------
需要说明的是，88折指的是按标价的88%计算，而8折是按80%计算，余者类推。
特别地，半价是按50%计算。
请提交小明要从取款机上提取的金额，单位是元。
答案是一个整数，类似4300的样子，结尾必然是00，不要填写任何多余的内容。
特别提醒：不许携带计算器入场，也不能打开手机。
答案：5200（这题需要细心和耐心）
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
double sum = 0;
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
double a = in.nextDouble();
double b = in.nextDouble();
sum += a*b;
System.out.println(sum);
}
}
}
运算结果：
180.90 0.88
159.19210.25 0.65
165.8545
56.14 0.9
216.3805
104.65 0.9
310.56550000000004
100.30 0.88
398.82950000000005
297.15 0.50
547.4045000000001
26.75 0.65
564.7920000000001
130.62 0.5
630.1020000000001
240.28 0.58
769.4644000000001
270.62 0.8
985.9604
115.87 0.88
1087.9260000000002
247.34 0.95
1322.8990000000001
73.21 0.9
1388.788
101.00 0.5
1439.288
79.54 0.5
1479.058
278.44 0.7
1673.966
199.26 0.5
1773.596
12.97 0.9
1785.269
166.30 0.78
1914.983
125.50 0.58
1987.773
84.98 0.9
2064.255
113.35 0.68
2141.333
166.57 0.5
2224.618
42.56 0.9
2262.922
81.90 0.95
2340.727
131.78 0.8
2446.151
255.89 0.78
2645.7452
109.17 0.9
2743.9982
146.69 0.68
2843.7474
139.33 0.65
2934.3119
141.16 0.78
3044.4167
154.74 0.8
3168.2087
59.42 0.8
3215.7447
85.44 0.68
3273.8439000000003
293.70 0.88
3532.2999000000004
261.79 0.65
3702.4634000000005
11.30 0.88
3712.4074000000005
268.27 0.58
3868.0040000000004
128.29 0.88
3980.8992000000003
251.03 0.8
4181.7232
208.39 0.75
4338.0157
128.88 0.75
4434.6757
62.06 0.9
4490.5297
225.87 0.75
4659.9322
12.89 0.75
4669.5997
34.28 0.75
4695.3097
62.16 0.58
4731.3625
129.12 0.5
4795.922500000001
218.37 0.5
4905.107500000001
289.69 0.8
5136.859500000001
2.标题：纸牌三角形
A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。
下图就是一种排法（如有对齐问题，参看p1.png）。
A
9 6
4 8
3 7 5 2
这样的排法可能会有很多。
如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？
请你计算并提交该数字。
注意：需要提交的是一个整数，不要提交任何多余内容。
答案：144
import java.util.Scanner;
public class Main {
static int arr[];
static int n = 9;
static int count = 0;
public static void main(String[] args) {
arr = new int[10];
for(int i = 0; i < 9; i++) {
arr[i] = i+1;
}
perm(0);
System.out.println(count/6);
}
public static void perm(int offset) {
if(offset == n-1) {
compare();
return;
}
for(int i = offset; i < n; i++) {
swap(i, offset);
perm(offset + 1);
swap(i, offset);
}
}
public static void compare() {
int n1 = arr[0] + arr[1] + arr[2] + arr[3];
int n2 = arr[3] + arr[4] + arr[5] + arr[6];
int n3 = arr[6] + arr[7] + arr[8] + arr[0];
if(n1 == n2 && n1 == n3) {
count++;
}
}
public static void swap(int a, int b) {
int temp;
temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
}
3.标题：承压计算
X星球的高科技实验室中整齐地堆放着某批珍贵金属原料。
每块金属原料的外形、尺寸完全一致，但重量不同。
金属材料被严格地堆放成金字塔形。
7
5 8
7 8 8
9 2 7 2
8 1 4 9 1
8 1 8 8 4 1
7 9 6 1 4 5 4
5 6 5 5 6 9 5 6
5 5 4 7 9 3 5 5 1
7 5 7 9 7 4 7 3 3 1
4 6 4 5 5 8 8 3 2 4 3
1 1 3 3 1 6 6 5 5 4 4 2
9 9 9 2 1 9 1 9 2 9 5 7 9
4 3 3 7 7 9 3 6 1 3 8 8 3 7
3 6 8 1 5 3 9 5 8 3 8 1 8 3 3
8 3 2 3 3 5 5 8 5 4 2 8 6 7 6 9
8 1 8 1 8 4 6 2 2 1 7 9 4 2 3 3 4
2 8 4 2 2 9 9 2 8 3 4 9 6 3 9 4 6 9
7 9 7 4 9 7 6 6 2 8 9 4 1 8 1 7 2 1 6
9 2 8 6 4 2 7 9 5 4 1 2 5 1 7 3 9 8 3 3
5 2 1 6 7 9 3 2 8 9 5 5 6 6 6 2 1 8 7 9 9
6 7 1 8 8 7 5 3 6 5 4 7 3 4 6 7 8 1 3 2 7 4
2 2 6 3 5 3 4 9 2 4 5 7 6 6 3 2 7 2 4 8 5 5 4
7 4 4 5 8 3 3 8 1 8 6 3 2 1 6 2 6 4 6 3 8 2 9 6
1 2 4 1 3 3 5 3 4 9 6 3 8 6 5 9 1 5 3 2 6 8 8 5 3
2 2 7 9 3 3 2 8 6 9 8 4 4 9 5 8 2 6 3 4 8 4 9 3 8 8
7 7 7 9 7 5 2 7 9 2 5 1 9 2 6 5 3 9 3 5 7 3 5 4 2 8 9
7 7 6 6 8 7 5 5 8 2 4 7 7 4 7 2 6 9 2 1 8 2 9 8 5 7 3 6
5 9 4 5 5 7 5 5 6 3 5 3 9 5 8 9 5 4 1 2 6 1 4 3 5 3 2 4 1
X X X X X X X X X X X X X X X X X X X X X X X X X X X X X X
其中的数字代表金属块的重量（计量单位较大）。
最下一层的X代表30台极高精度的电子秤。
假设每块原料的重量都十分精确地平均落在下方的两个金属块上，
最后，所有的金属块的重量都严格精确地平分落在最底层的电子秤上。
电子秤的计量单位很小，所以显示的数字很大。
工作人员发现，其中读数最小的电子秤的示数为：2086458231
请你推算出：读数最大的电子秤的示数为多少？
注意：需要提交的是一个整数，不要填写任何多余的内容。
答案：72665192664
单位换算，电子秤的单位并不是1，而是2086458231/min，在用max乘上这个单位就是答案了
可以看成：
1 0
1 2 0
1 2 3 0
import java.util.Scanner;
public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
double[][] a = new double[30][30];
double min = 1000000;
double max = 0;
for(int i=0;i<29;i++){
for(int j=0;j<=i;j++){
a[i][j]=sc.nextDouble();
}
}
for(int i=1;i<30;i++){
for(int j=0;j<=i;j++){
if(j==0)
a[i][j] = a[i-1][j]/2.0+a[i][j];
else
a[i][j] = a[i-1][j-1]/2.0+ a[i-1][j]/2.0+a[i][j];
}
}
for(int i=0;i<30;i++){
max = Math.max(max, a[29][i]);
min = Math.min(min, a[29][i]);
}
System.out.println(max);
System.out.println(min);
System.out.println((long)(2086458231l/min*max));
}
}
1
1 2
1 2 3
import java.util.Scanner;
public class Main {
static double arr[][] = new double[30][30];
static double max = 0;
static double min = 1000000;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
for(int i = 0; i < 29; i++ ) {
for(int j = 0; j <= i; j++) {
arr[i][j] = in.nextDouble();
}
}
for(int i = 1; i < 30; i++) {
for(int j = 0; j <= i; j++) {
if(j == 0) {
arr[i][j] += arr[i-1][j] * 0.5;
} else if(j == i) {
arr[i][j] += arr[i-1][j-1] * 0.5;
} else {
arr[i][j] =arr[i][j] + arr[i-1][j-1] * 0.5 + arr[i-1][j] * 0.5;
}
}
}
double sum = 0;
for(int i=0; i < 30; i++) {
max = Math.max(max, arr[29][i]);
min = Math.min(min, arr[29][i]);
}
System.out.println(max + ":" + min);
System.out.println((long)(2086458231l/min*max));
}
}
4.
标题：魔方状态
二阶魔方就是只有2层的魔方，只由8个小块组成。
如图p1.png所示。
小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：
2 2 4
前面：橙色
右面：绿色
上面：黄色
左面：绿色
下面：橙色
后面：黄色
请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。
如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。
请提交表示状态数的整数，不要填写任何多余内容或说明文字。
答案：没思路
不知道对不对，得到35个，把魔方分成了8块，3种不同类型的，数量为2，2, 4。再全排列，然后减去相同的排列数，最后考虑了六个方向的摆放位置，这种做法应该是错的，求大神解答。
import java.util.Arrays;
import java.util.HashSet;
import java.util.Scanner;
public class Main {
static int n = 8;
static int arr[] = {1,1,2,2,3,3,3,3};
static int k = 0;
static HashSet<String> hashset = new HashSet<String>();
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
perm(0);
System.out.println(hashset.size()/6);
}
static void perm(int offset) {
if(offset == n - 1) {
compare();
}
for(int i = offset; i < n-1; i++) {
swap(offset, i);
perm(offset+1);
swap(offset, i);
}
}
static void swap(int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
static void compare() {
hashset.add(Arrays.toString(arr));
}
}
5.
标题：取数位
求1个整数的第k位数字有很多种方法。
以下的方法就是一种。
public class Main
{
static int len(int x){
if(x<10) return 1;
return len(x/10)+1;
}
// 取x的第k位数字
static int f(int x, int k){
if(len(x)-k==0) return x%10;
return ______________________; //填空
}
public static void main(String[] args)
{
int x = 23513;
//System.out.println(len(x));
System.out.println(f(x,3));
}
}
对于题目中的测试数据，应该打印5。
请仔细分析源码，并补充划线部分所缺少的代码。
注意：只提交缺失的代码，不要填写任何已有内容或说明性的文字。
答案：f(x/10,3)
6.标题：最大公共子串
最大公共子串长度问题就是：
求两个串的所有子串中能够匹配上的最大长度是多少。
比如："abcdkkk" 和 "baabcdadabc"，
可以找到的最长的公共子串是"abcd",所以最大公共子串长度为4。
下面的程序是采用矩阵法进行求解的，这对串的规模不大的情况还是比较有效的解法。
请分析该解法的思路，并补全划线部分缺失的代码。
public class Main
{
static int f(String s1, String s2)
{
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int[][] a = new int[c1.length+1][c2.length+1];
int max = 0;
for(int i=1; i<a.length; i++){
for(int j=1; j<a[i].length; j++){
if(c1[i-1]==c2[j-1]) {
a[i][j] = __________________; //填空
if(a[i][j] > max) max = a[i][j];
}
}
}
return max;
}
public static void main(String[] args){
int n = f("abcdkkk", "baabcdadabc");
System.out.println(n);
}
}
注意：只提交缺少的代码，不要提交已有的代码和符号。也不要提交说明性文字。
答案：a[i-1][j-1] + 1
7.标题：日期问题
小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。
比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。
给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？
输入
----
一个日期，格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)
输入
----
输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。
样例输入
----
02/03/04
样例输出
----
2002-03-04
2004-02-03
2004-03-02
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
答案：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;
import java.util.Scanner;
public class Main {
static String a1, b1, c1;
static ArrayList<Integer> list = new ArrayList<Integer>();
static int arr[] = new int[3];
static int p = 0;
static void getDate(String a1, String b1, String c1) {
int a;
if (Integer.parseInt(a1) >= 0 && Integer.parseInt(a1) <= 59)
a = Integer.parseInt(("20" + a1));
else
a = Integer.parseInt(("19" + a1));
int b = Integer.parseInt(b1);
int c = Integer.parseInt(c1);
if (((a % 4 == 0 && a % 100 != 0) || a % 400 == 0) && b == 2 && c > 0 && c <= 29)
arr[p++] = Integer.parseInt("" + a + b1 + c1);
if (a % 4 != 0 && b == 2 && c > 0 && c <= 28)
arr[p++] = Integer.parseInt("" + a + b1 + c1);
if ((b == 1 || b == 3 || b == 5 || b == 7 || b == 8 || b == 10 || b == 12) && c > 0 && c <= 31)
arr[p++] = Integer.parseInt("" + a + b1 + c1);
if ((b == 4 || b == 6 || b == 9 || b == 11) && c > 0 && c <= 30)
arr[p++] = Integer.parseInt("" + a + b1 + c1);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String[] ss = s.split("/");
a1 = ss[0];
b1 = ss[1];
c1 = ss[2];
getDate(a1, b1, c1);
getDate(b1, c1, a1);
getDate(c1, b1, a1);
Arrays.sort(arr);
for (int i = 0; i < p; i++ ) {
System.out.println(
("" + arr[i]).substring(0, 4) + "-" + ("" + arr[i]).substring(4, 6) + "-" + ("" + arr[i]).substring(6, 8));
}
}
}
8.标题：包子凑数
小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有N种蒸笼，其中第i种蒸笼恰好能放Ai个包子。每种蒸笼都有非常多笼，可以认为是无限笼。
每当有顾客想买X个包子，卖包子的大叔就会迅速选出若干笼包子来，使得这若干笼中恰好一共有X个包子。比如一共有3种蒸笼，分别能放3、4和5个包子。当顾客想买11个包子时，大叔就会选2笼3个的再加1笼5个的（也可能选出1笼3个的再加2笼4个的）。
当然有时包子大叔无论如何也凑不出顾客想买的数量。比如一共有3种蒸笼，分别能放4、5和6个包子。而顾客想买7个包子时，大叔就凑不出来了。
小明想知道一共有多少种数目是包子大叔凑不出来的。
输入
----
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)
输出
----
一个整数代表答案。如果凑不出的数目有无限多个，输出INF。
例如，
输入：
2
4
5
程序应该输出：
6
再例如，
输入：
2
4
6
程序应该输出：
INF
样例解释：
对于样例1，凑不出的数目包括：1, 2, 3, 6, 7, 11。
对于样例2，所有奇数都凑不出来，所以有无限多个。
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
提交程序时，注意选择所期望的语言类型和编译器类型。
答案： 背包问题。。。如果给出的数中没有互质的数那就是INF（欧几里问题）。如果有就用背包问题解决。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int dp[] = new int[10001];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n ;
while(in.hasNext()) {
//结果
int rest = 0;
boolean check = false;
n = in.nextInt();
int arr[] = new int[n+1];
for(int i = 1; i <= n; i++) {
arr[i] = in.nextInt();
}
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n; j++) {
if(judge(arr[i],arr[j])) {
check = true;
break;
}
}
if(check) {
break;
}
}
if(!check) {
System.out.println("INF");
continue;
}
dp[0] = 1;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= 10000; j++ ) {
if(arr[i] > j) {
continue;
}
if(dp[j-arr[i]] == 1) {
dp[j] = 1;
}
}
}
for(int i = 0; i < 10000; i++) {
if(dp[i] != 1) {
rest++;
}
}
System.out.println(rest);
}
}
static public boolean judge(int a, int b) {
int t = 0;
while(b > 0) {
t = a%b;
a = b;
b = t;
}
if(a == 1) {
return true;
}
return false;
}
}
9.标题： 分巧克力
儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。
为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：
1. 形状是正方形，边长是整数
2. 大小相同
例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？
输入
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
输入保证每位小朋友至少能获得一块1x1的巧克力。
输出
输出切出的正方形巧克力最大可能的边长。
样例输入：
2 10
6 5
5 6
样例输出：
2
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
答案：
仔细审题，发现它两个要求，很快就想到了一个数的分解因子，利用二分法解决数据过大的问题，粗心了，忘了考虑这一点。
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int n, m ;
static int arr[][];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
n = in.nextInt();
m = in.nextInt();
arr = new int[n][2];
for(int i = 0; i < n; i++) {
arr[i][0] = in.nextInt();
arr[i][1] = in.nextInt();
}
int low = 1, high = 100000;
while(low < high - 1) {
int mid = (low + high) /2;
if(!solve(mid)) {
high = mid;
} else {
low = mid;
}
}
System.out.println(low);
}
}
static boolean solve (int a) {
int sum = m;
for(int i = 0; i < n; i++) {
sum -= (arr[i][0]/a) * (arr[i][1]/a);
if(sum <= 0) {
return true;
}
}
return false;
}
}
10.标题： k倍区间
给定一个长度为N的数列，A1, A2, ... AN，如果其中一段连续的子序列Ai, Ai+1, ... Aj(i <= j)之和是K的倍数，我们就称这个区间[i, j]是K倍区间。
你能求出数列中总共有多少个K倍区间吗？
输入
-----
第一行包含两个整数N和K。(1 <= N, K <= 100000)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100000)
输出
-----
输出一个整数，代表K倍区间的数目。
例如，
输入：
5 2
1
2
3
4
5
程序应该输出：
6
资源约定：
峰值内存消耗（含虚拟机） < 256M
CPU消耗 < 2000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
不要使用package语句。不要使用jdk1.7及以上版本的特性。
主类的名字必须是：Main，否则按无效代码处理。
答案：
import java.util.Arrays;
import java.util.Scanner;
//减少sum的值能避免大数问题
public class Main {
static int n, k ,number ;
static int arr[];
static int sum;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while(in.hasNext()) {
n = in.nextInt();
k = in.nextInt();
int count = 0;
arr = new int[n];
for(int i= 0; i < n; i++) {
arr[i] = in.nextInt();
}
for(int i = 0; i < n; i++) {
sum = 0;
for(int j = i; j < n; j++) {
number = arr[j] % k;
sum += number;
sum = sum % k;
if(sum == 0) {
count++;
}
}
}
System.out.println(count);
}
}
}