1、十一届
1.1、解密(结果填空`5)
Q：
小明设计了一种文章加密的方法：对于每个字母 c，将它变成某个另外的字符 Tc。下表给出了字符变换的规则： 在这里插入图片描述 例如，将字符串 YeRi 加密可得字符串 EaFn。 小明有一个随机的字符串，加密后为 EaFnjISplhFviDhwFbEjRjfIBBkRyY（由 30 个大小写英文字母组成，不包含换行符） 请问原字符串是多少？ 答案提交 这是一道结果填空题，你只需要算出结果后提交即可。 本题的结果为一个只包含 30 个大小写英文字母的字符串，在提交答案时只填写这个字符串，填写多余的内容将无法得分。
A：
YeRjkGSmnlRzgDlvRwYkXkrGWWHXaA
对应数据查表即可
1.2、纪念日(结果填空`5)
Q:
2020 年 7 月 1 日是A组织 成立 99 周年纪念日。 A组织成立于 1921 年 7 月 23 日。 请问从 1921 年 7 月 23 日中午 12 时到 2020 年 7 月 1 日中午 12 时一共包 含多少分钟？ 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个 整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
A:
public class Solution {
public static void main(String[] args) throws ParseException {
SimpleDateFormat s = new SimpleDateFormat("yyyy-MM-dd");
Date date1 = s.parse("1921-7-23");
Date date2 = s.parse("2020-7-1");
int result = (int) ((date2.getTime() - date1.getTime()) / (1000 * 60));
System.out.println(result);
}
}
1.3、合并检测(结果填空`10)
Q:
新冠疫情由新冠病毒引起，最近在 A 国蔓延，为了尽快控制疫情， A 国准 备给大量民众进病毒核酸检测。然而，用于检测的试剂盒紧缺。 为了解决这一困难，科学家想了一个办法：合并检测。 即将从多个人（k 个）采集的标本放到同一个试剂盒中进行检测。 如果结果为阴性，则说明这 k 个人都是阴性，用一个试剂盒完成了 k 个人的检测。 如果结果为阳性，则说明 至少有一个人为阳性， 需要将这 k 个人的样本全部重新独立检测（从理论上看， 如果检测前 k−1 个人都是阴性可以推断出第 k 个人是阳性， 但是在实际操作中 不会利用此推断，而是将 k 个人独立检测）， 加上最开始的合并检测，一共使用 了 k + 1 个试剂盒完成了 k 个人的检测。 A 国估计被测的民众的感染率大概是 1%，呈均匀分布。 请问 k 取多少能 最节省试剂盒？ 这是一道结果填空题，你只需要算出结果后提交即可。 本题的结果为一个 整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
A:
思路：
我们假设总共有100人，那么患者为1人 > 1. 如果k为10，那么可以分为10组，也就是需要10个试剂，但当检查到有患者的一组时，需要对这组每个人再分别进行一次检测，也就是说还需要10个试剂，总共试剂就为10+10=20 > 2. 如果k为33，那么可以分为4组，33+33+33+1，也就是需要100 / k个试剂+1，当检查到有患者的一组时，需要对每个人进行检测，就是再需要33个试剂 > > 所以我们可以推出公式，如果k可以整除100，那么需要总试剂就为100 / k + k > 如果不能够整除，那么就为 100 / k + 1 + k
public class Solution {
public static void main(String[] args) {
int min = 0;
int sum = Integer.MAX_VALUE;
for (int i = 1; i < 100; i++) {
if (100 % i == 0) {
if (100 / i + i < sum) {
sum = 100 / i + i;
min = i;
}
} else {
if (100 / i + 1 + i < sum) {
sum = 100 / i + 1 + i;
min = i;
}
}
}
System.out.println(min);
}
}
1.4、分配口罩(结果填空`10)
Q:
某市市长获得了若干批口罩，给定每批口罩的数量， 市长要把口罩分配给市内的 2 所医院，由于物流限制，每一批口罩只能全部分配给其中一家医院。 市长希望 2 所医院获得的口罩总数之差越小越好。 请你计算这个差最小是多少？ 答案提交: 这是一道结果填空题，你只需要算出结果后提交即可。 本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
A:
思路：递归函数 dfs函数的三个参数分别为 k、sum1、sum2 k代表正在处理数字的下标 sum1为1号医院的口罩数量 sum2位2号医院的口罩数量 当k=15时，说明所有口罩全部分配完成，此时要确定最小值和当前两个医院数量的差值 函数体中处理的是不同路径 第一个是给1号医院分配 第二个是给2号医院分配 经过多次递归回溯，会计算出所有分配情况的最小值
public class Solution {
public static long res = Long.MAX_VALUE;
public static long[] num = {9090400, 8499400, 5926800, 8547000, 4958200,
4422600, 5751200, 4175600, 6309600, 5865200,
6604400, 4635000, 10663400, 8087200, 4554000};
public static void main(String[] args) {
dfs(0, 0, 0);
System.out.println(res);
}
public static void dfs(int k, long sum1, long sum2) {
if (k == 15) {
res = Math.min(res, Math.abs(sum1 - sum2));
return;
}
dfs(k + 1, sum1 + num[k], sum2);
dfs(k + 1, sum1, sum2 + num[k]);
}
}
1.5、斐波那契数列最大公约数(结果填空`15)
Q：
【问题描述】 斐波那契数列满足 F1 = F2 = 1，从 F3 开始有 Fn = Fn 1 + Fn 2。请你计算 GCD(F2020, F520)，其中 GCD(A, B) 表示 A 和 B 的最大公约数。 【答案提交】 这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个 整数，在提交答案时只填写这个整数，填写多余的内容将无法得分
A：
首先求出两个斐波那契数 可以利用递归求，但是在试验时，采用递归花费时间较长，不建议 两个结果用BigInteger存取，因为使用long会溢出 求最大公约数可以利用欧几里得算法，BigInteger已经包装好，可以直接调用
public class Solution2 {
public static void main(String[] args) {
BigInteger num1 = fib(2020);
System.out.println(num1);
BigInteger num2 = fib(520);
System.out.println(num2);
System.out.println(num1.gcd(num2));
}
public static BigInteger fib(int n) {
BigInteger a = BigInteger.ONE;
BigInteger b = BigInteger.ONE;
BigInteger c = BigInteger.ONE;
if (n <= 2) {
return a;
}
for (int i = 3; i <= n; i++) {
c = a.add(b);
a = b;
b = c;
}
return c;
}
}
1.6、分类计数(编程大题`15)
Q:
输入一个字符串，请输出这个字符串包含多少个大写字母，多少个小写字母，多少个数字。 【输入格式】 输入一行包含一个字符串。 【输出格式】 输出三行，每行一个整数，分别表示大写字母、小写字母和数字的个数。 【样例输入】 1+a=Aab 【样例输出】 1 3 1 【评测用例规模与约定】 对于所有评测用例，字符串由可见字符组成，长度不超过 100。
A:
思路：本题就是个简单的遍历 可以利用Character包装类里的方法 isDigit（char） 判断该字符是否为数字 isUpperCase（char） 判断该字符是否为大写字母 isLowerCase（char） 判断字符是否为小写字母
public class Solution {
public static void main(String[] args) {
String str = new Scanner(System.in).nextLine();
int a = 0, b = 0, c = 0;
for (int i = 0; i < str.length(); i++) {
if (Character.isDigit(str.charAt(i))) {
c++;
} else if (Character.isUpperCase(str.charAt(i))) {
a++;
} else if (Character.isLowerCase(str.charAt(i))) {
b++;
}
}
System.out.println(a);
System.out.println(b);
System.out.println(c);
}
}
1.7、八次求和(编程大题`20)
Q:
【问题描述】 给定正整数 n, 求 1^8 + 2^8 +···+ n^8 mod 123456789 。其中 mod 表示取余。 【输入格式】 输入的第一行包含一个整数 n。 【输出格式】 输出一行，包含一个整数，表示答案。 【样例输入】 2 【样例输出】 257 【样例输入】 987654 【样例输出】 43636805 【评测用例规模与约定】 对于 20% 的评测用例，1≤n≤20。 对于 60% 的评测用例，1≤n≤1000。 对于所有评测用例，1≤n≤1000000。
A:
public class Solution {
public static void main(String[] args) {
int n = new Scanner(System.in).nextInt();
BigInteger sum = BigInteger.ZERO;
for (int i = 1; i <= n; i++) {
sum = sum.add(new BigInteger(String.valueOf(i)).pow(8));
}
BigInteger result = sum.mod(new BigInteger("123456789"));
System.out.println(result);
}
}
1.8、字符串编码(编程大题`20)
Q:
问题描述 小明发明了一种给由全大写字母组成的字符串编码的方法。 对于每一个大写字母，小明将它转换成它在 26 个英文字母中序号，即 A → 1, B → 2, … Z →26。 这样一个字符串就能被转化成一个数字序列：比如 ABCXYZ → 123242526。 现在给定一个转换后的数字序列，小明想还原出原本的字符串。 当然这样的还原有可能存在多个符合条件的字符串。 小明希望找出其中字典序最大的字符串。 输入格式： 一个数字序列。 输出格式: 一个只包含大写字母的字符串，代表答案 样例输入: 123242526 样例输出 LCXYZ 评测用例规模与约定 对于 20% 的评测用例，输入的长度不超过 20。 对于所有评测用例，输入的长度不超过 200000。
A:
思路：定义一个arr数组存取26个英文字母，便于使用，对应位置存储 首先遍历数列，如果第一个数+第二个数<=26,说明存在字典序更大的字母 这样添加后记得i++，因为i向后移动了一位 否则添加原位置的字母 注意判断i+1是否越界
public class Solution {
public static char[] arr = {
'0',
'A', 'B', 'C', 'D', 'E', 'F', 'G',
'H', 'I', 'J', 'K', 'L', 'M', 'N',
'O', 'P', 'Q', 'R', 'S', 'T', 'U',
'V', 'W', 'X', 'Y', 'Z'
};
public static void main(String[] args) {
String str = new Scanner(System.in).nextLine();
StringBuilder res = new StringBuilder();
for (int i = 0; i < str.length(); i++) {
if (i + 1 < str.length()) {
int x = (str.charAt(i) - '0') * 10 + (str.charAt(i + 1) - '0');
if (x <= 26) {
res.append(arr[x]);
i++;
} else {
res.append(arr[str.charAt(i) - '0']);
}
} else {
res.append(arr[str.charAt(i) - '0']);
}
}
System.out.println(res);
}
}
1.9、BSTL插入节点问题(编程大题`25)
放弃
1.10、网络分析(编程大题`25)
放弃
2、十届
2.1、组队(结果填空`5)
Q:
作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员， 组成球队的首发阵容。 每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1 号位至 5 号位的评分之和最大可能是多少？
A：
490
2.2、不同子串(结果填空`5)
Q:
【问题描述】 一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。 注意在计算时，只算本质不同的串的个数。 请问，字符串0100110001010001 有多少个不同的非空子串？
【答案提交】 这是一道结果填空的题，你只需要算出 结果后提交即可。本题的结果为一 个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。
A:
public class Solution {
public static void main(String[] args) {
Set
String s = "0100110001010001";
for (int i = 0; i < s.length(); i++) {
for (int j = i; j < s.length(); j++) {
set.add(s.substring(i, j + 1));
}
}
/*for (Object o : set) {
System.out.println(o);
}*/
System.out.println(set.size());
}
}
2.3、数列求值(结果填空`10)
Q:
给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求 第 20190324 项的最后 4 位数字。 【答案提交】 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个 4 位整数（提示：答案的千位不为 0），在提交答案时只填写这个整数，填写 多余的内容将无法得分。
A:
斐波那契数列，使用BigInteger
public class Solution {
public static void main(String[] args) {
int n = 20190324;
long[] a = new long[n];
a[0] = a[1] = a[2] = 1;
for (int i = 3; i < n; i++) {
a[i] = a[i - 1] + a[i - 2] + a[i - 3];
if (a[i] > 10000) {
a[i] %= 10000;
}
}
System.out.println(a[n - 1]);
}
}
public class Solution3 {
public static void main(String[] args) {
BigInteger a = BigInteger.ONE;
BigInteger b = BigInteger.ONE;
BigInteger c = BigInteger.ONE;
BigInteger d = BigInteger.ONE;
int n = 20190324;
for (int i = 3; i < n; i++) {
d = a.mod(new BigInteger("10000")).add(b.mod(new BigInteger("10000"))).add(c.mod(new BigInteger("10000")));
a = b;
b = c;
c = d;
}
System.out.println(d.mod(new BigInteger("10000")));
}
}
2.4、数的分解(结果填空`10)
Q:
把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包 含数字 2 和 4，一共有多少种不同的分解方法？ 注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。
A:
// 三次for循环暴力求解
public class Solution {
public static void main(String[] args) {
int count = 0;
for (int i = 1; i < 2019; i++) {
for (int j = 1; j < 2019; j++) {
for (int k = 1; k < 2019; k++) {
if (k + j + i == 2019 && !Integer.toString(i).contains("2") && !Integer.toString(i).contains("4") && !Integer.toString(j).contains("2") && !Integer.toString(j).contains("4") && !Integer.toString(k).contains("2") && !Integer.toString(k).contains("4") && i != j && i != k && j != k) {
count++;
}
}
}
}
System.out.println(count / 6);
}
}
2.5、迷宫(结果填空`15)
Q:
【问题描述】 下图给出了一个迷宫的平面图，其中标记为 1 的为障碍，标记为 0 的为可 以通行的地方。
1 010000
2 000100
3 001001
4 110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这 个它的上、下、左、右四个方向之一。对于上面的迷宫，从入口开始，可以按DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向下、向上、向左、向右走。对于下面这个更复杂的迷宫（30 行 50 列），请找出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字典序最小的一个作为答案。请注意在字典序中D 1 01010101001011001001010110010110100100001000101010 2 00001000100000101010010000100000001001100110100101 3 01111011010010001000001101001011100011000000010000 4 01000000001010100011010000101000001010101011001011 5 00011111000000101000010010100010100000101100000000 6 11001000110101000010101100011010011010101011110111 7 00011011010101001001001010000001000101001110000000 8 10100000101000100110101010111110011000010000111010 9 00111000001010100001100010000001000101001100001001 10 11000110100001110010001001010101010101010001101000 11 00010000100100000101001010101110100010101010000101 12 11100100101001001000010000010101010100100100010100 13 00000010000000101011001111010001100000101010100011 14 10101010011100001000011000010110011110110100001000 15 10101010100001101010100101000010100000111011101001 16 10000000101100010000101100101101001011100000000100 17 10101001000000010100100001000100000100011110101001 18 00101001010101101001010100011010101101110000110101 19 11001010000100001100000010100101000001000111000010 20 00001000110000110101101000000100101001001000011101 21 10100101000101000000001110110010110101101010100001 22 00101000010000110101010000100010001001000100010101 23 10100001000110010001000010101001010101011111010010 24 00000100101000000110010100101001000001000000000010 25 11010000001001110111001001000011101001011011101000 26 00000110100010001000100000001000011101000000110011 27 10101000101000100010001111100010101001010000001000 28 10000010100101001010110000000100101010001011101000 29 00111100001000010000000110111000000001000000001011 30 10000001100111010111010001000110111010101101111000 【答案提交】 这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一 个字符串，包含四种字母 D、U、L、R，在提交答案时只填写这个字符串，填 写多余的内容将无法得分。 A: 思路： 本题是典型的迷宫问题，可以利用bfs（广度优先遍历） 也可以用dfs进行搜索路径，但最终要字典序最小，所以dfs不太容易操作 广搜的顺义要以D-L-R-U进行，因为要字典序最小 这点可以利用4次循环即可 怎么判断是最小路径呢？ 因为是广搜，要一层一层的搜 所以当前节点探寻了每个和它相邻的节点 一但到达终点即退出，最小路径为探索的层数，这点和深搜不太相同， dfs是不断进行递归回溯，进行比较找最小值 而bfs可以利用自身优势确定最小值 public class Solution { public static int dir[][] = new int[][] {{1,0},{0,-1},{0,1},{-1,0}}; public static char direction[] = new char[] {'D','L','R','U'}; public static int[][] map=new int[30][50]; public static boolean[][] visit=new boolean[30][50]; public static void main(String[] args){ Scanner sc=new Scanner(System.in); for(int i=0;i<30;i++) { String s=sc.next(); for(int j=0;j<50;j++) { map[i][j]=s.charAt(j)-'0'; } } bfs(new Point(0, 0)); } public static void bfs(Point start) { Queue q.add(start); visit[start.i][start.j]=true; while(!q.isEmpty()) { Point p=q.peek(); if(p.i==29&&p.j==49) { System.out.println(p.step); System.out.println(p.way); return; } for(int i=0;i<4;i++) { int new_i=p.i+dir[i][0]; int new_j=p.j+dir[i][1]; Point temp=new Point(new_i,new_j); if(new_i>=0&&new_j>=0&&new_i<30&&new_j<50&&!visit[new_i][new_j]&&map[new_i][new_j]!=1) { visit[new_i][new_j]=true; temp.step=p.step+1; temp.way=p.way+direction[i]; q.add(temp); } } q.poll(); } } } class Point{ int i; int j; int step; String way; public Point() { i=j=step=0; way=""; } public Point(int i,int j) { this.i=i; this.j=j; step=0; way=""; } } 2.6、特别数的和(编程大题`15) Q: 小明对数位中含有 2、0、1、9 的数字很感兴趣（不包括前导 0） ，在 1 到 40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是 574。 请问，在 1 到 n 中，所有这样的数的和是多少？ 【输入格式】 输入一行包含两个整数 n。 【输出格式】 输出一行，包含一个整数，表示满足条件的数的和。 【样例输入】 40 【样例输出】 574 【评测用例规模与约定】 对于 20% 的评测用例，1 ≤ n ≤ 10。 对于 50% 的评测用例，1 ≤ n ≤ 100。 对于 80% 的评测用例，1 ≤ n ≤ 1000。 对于所有评测用例，1 ≤ n ≤ 10000。 A: public class Solution { public static void main(String[] args) { int n = new Scanner(System.in).nextInt(); int sum = 0; for (int i = 1; i <= n; i++) { if (Integer.toString(i).contains("2") || Integer.toString(i).contains("0") || Integer.toString(i).contains("1") || Integer.toString(i).contains("9")) { sum += i; } } System.out.println(sum); } } 2.7、外卖店优先级(编程大题`20) Q: “饱了么”外卖系统中维护着 N 家外卖店，编号 1 ∼ N。每家外卖店都有 一个优先级，初始时 (0 时刻) 优先级都为 0。 每经过 1 个时间单位，如果外卖店没有订单，则优先级会减少 1，最低减 到 0；而如果外卖店有订单，则优先级不减反加，每有一单优先级加 2。 如果某家外卖店某时刻优先级大于 5，则会被系统加入优先缓存中；如果 优先级小于等于 3，则会被清除出优先缓存。 给定 T 时刻以内的 M 条订单信息，请你计算 T 时刻时有多少外卖店在优 先缓存中。 【输入格式】 第一行包含 3 个整数 N、M 和 T。 以下 M 行每行包含两个整数 ts 和 id，表示 ts 时刻编号 id 的外卖店收到 一个订单。 【输出格式】 输出一个整数代表答案。 【样例输入】 2 6 6 1 1 5 2 3 1 6 2 2 1 6 2 【样例输出】 1 【样例解释】 6 时刻时，1 号店优先级降到 3，被移除出优先缓存；2 号店优先级升到 6， 加入优先缓存。所以是有 1 家店 (2 号) 在优先缓存中。 【评测用例规模与约定】 对于 80% 的评测用例，1≤ N,M,T ≤10000。 对于所有评测用例，1≤ N,M,T ≤100000，1≤ts≤T，1≤id ≤ N。 A: 思路： 定义三个数组 score[]代表每个店的优先级分数 flag[]代表该店是否在优先缓存中 ans[][]存储每个时刻每家店的单数，行代表时间，列代表每家店的编号 遍历该二维数组，如果某时刻，某家店的单数为0 则判断它现在的分数是多少，如果大于0，则将其减1 如果该位置订单数不为0，则判断它此时有多少订单，加上订单数*2的分数 一轮处理过后判断它的分数是多少 如果大于5，则将其加入优先缓存中 否则将其除去 最后统计flag数组中有多少true即可 public class Solution { public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int t=sc.nextInt(); int[] score=new int[n]; boolean[] flag=new boolean[n]; int[][] ans=new int[t][n]; for(int i=0;i int ts=sc.nextInt(); int id=sc.nextInt(); ans[ts-1][id-1]++; } for(int i=0;i for(int j=0;j if(ans[i][j]==0) { if(score[j]!=0) { score[j]-=1; } } else { for(int k=0;k score[j]+=2; } } if(score[j]>5) { flag[j]=true; } else if(score[j]<=3) { flag[j]=false; } } } int res=0; for(boolean i:flag) { if(i) { res++; } } System.out.println(res); } } 2.8、人物相关性分析(编程大题`20) Q: 【问题描述】 小明正在分析一本小说中的人物相关性。他想知道在小说中 Alice 和 Bob 有多少次同时出现。 更准确的说，小明定义 Alice 和 Bob“同时出现”的意思是：在小说文本 中 Alice 和 Bob 之间不超过 K 个字符。 例如以下文本： ThisisastoryaboutAliceandBob.AlicewantstosendaprivatemessagetoBob. 假设 K = 20，则 Alice 和 Bob 同时出现了 2 次，分别是”Alice and Bob” 和”Bob. Alice”。前者 Alice 和 Bob 之间有 5 个字符，后者有 2 个字符。 注意: 1. Alice 和 Bob 是大小写敏感的，alice 或 bob 等并不计算在内。 2. Alice 和 Bob 应为单独的单词，前后可以有标点符号和空格，但是不能 有字母。例如 Bobbi 並不算出现了 Bob。 【输入格式】 第一行包含一个整数 K。 第二行包含一行字符串，只包含大小写字母、标点符号和空格。长度不超 过 1000000。 【输出格式】 输出一个整数，表示 Alice 和 Bob 同时出现的次数。 【样例输入】 20 ThisisastoryaboutAliceandBob.AlicewantstosendaprivatemessagetoBob. 【样例输出】 2 【评测用例规模与约定】 对于所有评测用例，1≤ K ≤1000000。 2.9、后缀表达式(编程大题`25) Q: 【问题描述】 给定 N 个加号、M 个减号以及 N + M + 1 个整数 A1,A2,··· ,AN+M+1， 小明想知道在所有由这 N 个加号、M 个减号以及 N + M +1 个整数凑出的合法的 后缀表达式中，结果最大的是哪一个？ 请你输出这个最大的结果。 例如使用1 2 3 + -，则 “2 3 + 1 -” 这个后缀表达式结果是 4，是最大的。 【输入格式】 第一行包含两个整数 N 和 M。 第二行包含 N + M + 1 个整数 A1,A2,··· ,AN+M+1。 【输出格式】 输出一个整数，代表答案。 【样例输入】 1 1 1 2 3 【样例输出】 4 【评测用例规模与约定】 对于所有评测用例，0≤ N,M ≤100000，−109 ≤ Ai ≤109。 2.10、灵能传输(编程大题`25) Q: 【问题描述】 在游戏《星际争霸 II》中，高阶圣堂武士作为星灵的重要 AOE 单位，在 游戏的中后期发挥着重要的作用， 其技能”灵能风暴“可以消耗大量的灵能对 一片区域内的敌军造成毁灭性的伤害。 经常用于对抗人类的生化部队和虫族的 刺蛇飞龙等低血量单位。 【问题描述】 你控制着 n 名高阶圣堂武士，方便起见标为 1,2,··· ,n。每名高阶圣堂武士 需要一定的灵能来战斗，每个人有一个灵能值 ai 表示其拥有的灵能的多少（ai 非负表示这名高阶圣堂武士比在最佳状态下多余了 ai 点灵能，ai 为负则表示这 名高阶圣堂武士还需要 −ai 点灵能才能到达最佳战斗状态）。现在系统赋予了 你的高阶圣堂武士一个能力，传递灵能，每次你可以选择一个 i ∈ [2,n−1]，若 ai ≥ 0 则其两旁的高阶圣堂武士，也就是 i−1、i + 1 这两名高阶圣堂武士会从 i 这名高阶圣堂武士这里各抽取 ai 点灵能；若 ai < 0 则其两旁的高阶圣堂武士， 也就是 i−1,i+1 这两名高阶圣堂武士会给 i 这名高阶圣堂武士 −ai 点灵能。形 式化来讲就是 ai−1+ = ai,ai+1+ = ai,ai−= 2ai。灵能是非常高效的作战工具，同时也非常危险且不稳定，一位高阶圣堂 武士拥有的灵能过多或者过少都不好，定义一组高阶圣堂武士的不稳定度为 maxn i=1|ai|，请你通过不限次数的传递灵能操作使得你控制的这一组高阶圣堂武 士的不稳定度最小。 【输入格式】 本题包含多组询问。输入的第一行包含一个正整数 T 表示询问组数。 接下来依次输入每一组询问。 每组询问的第一行包含一个正整数 n，表示高阶圣堂武士的数量。 接下来一行包含 n 个数 a1,a2,··· ,an。 【输出格式】 输出 T 行。每行一个整数依次表示每组询问的答案。 【样例输入】 3 3 5 -2 3 4 0 0 0 0 3 1 2 3 【样例输出】 3 0 3 【样例说明】 对于第一组询问： 对 2 号高阶圣堂武士进行传输操作后 a1 = 3，a2 = 2，a3 = 1。答案为 3。 对于第二组询问： 这一组高阶圣堂武士拥有的灵能都正好可以让他们达到最佳战斗状态。 【样例输入】 3 4 -1 -2 -3 7 4 2 3 4 -8 5 -1 -1 6 -1 -1 【样例输出】 5 7 4 【数据规模与约定】 对于所有评测用例，T ≤3，3≤n≤300000，|ai|≤109。 评测时将使用 25 个评测用例测试你的程序，每个评测用例的限制如下 3、九届 3.1、第几天(结果填空`5) Q: 2000年的1月1日，是那一年的第1天。 那么，2000年的5月4日，是那一年的第几天？ 注意：需要提交的是一个整数，不要填写任何多余内容。 A: 125 3.2、方格计数(结果填空`7) Q: 如图所示，在二维平面上有无数个1x1的小方格,我们以某个小方格的一个顶点为圆心画一个半径为1000的圆。 你能计算出这个圆里有多少个完整的小方格吗？ A: public class Solution { private static final int R = 1000; private static long ans; public static void main(String[] args) { for (int i = 1; i <= 1000; i++) { for (int j = 1; j <= 1000; j++) { if (i * i + j * j <= R * R) { ans++; } } } System.out.println(ans * 4); } } 3.3、负数幂(结果填空`13) Q: 设i为虚数单位。对于任意正整数n，(2+3i)^n 的实部和虚部都是整数。 求 (2+3i)^123456 等于多少？ 即(2+3i)的123456次幂，这个数字很大，要求精确表示。 答案写成 “实部±虚部i” 的形式，实部和虚部都是整数（不能用科学计数法表示），中间任何地方都不加空格，实部为正时前面不加正号。(2+3i)^2 写成: -5+12i， (2+3i)^5 的写成: 122-597i public class Solution { public static void main(String[] args) throws FileNotFoundException { PrintStream pp = new PrintStream(new FileOutputStream("C:\\Users\\16342\\Desktop\\f.txt")); System.setOut(pp); //打印重定向 打印到文件中 BigInteger a = new BigInteger("2"); //存实部 BigInteger b = new BigInteger("3");//存虚部 BigInteger c = new BigInteger("2");//存总实部 BigInteger d = new BigInteger("3");//存总虚部 for (int i = 1; i < 123456; i++) { BigInteger ta = c; BigInteger tb = d; c = a.multiply(ta); c = c.subtract(b.multiply(tb)); d = b.multiply(ta); d = d.add(a.multiply(tb)); } System.out.println(c.toString() + "\n---------" + d.toString()); pp.close(); } } 3.4、测试次数(结果填空`17) x星球的居民脾气不太好，但好在他们生气的时候唯一的异常举动是：摔手机。 各大厂商也就纷纷推出各种耐摔型手机。x星球的质监局规定了手机必须经过耐摔测试，并且评定出一个耐摔指数来，之后才允许上市流通。 x星球有很多高耸入云的高塔，刚好可以用来做耐摔测试。塔的每一层高度都是一样的，与地球上稍有不同的是，他们的第一层不是地面，而是相当于我们的2楼。 如果手机从第7层扔下去没摔坏，但第8层摔坏了，则手机耐摔指数=7。 特别地，如果手机从第1层扔下去就坏了，则耐摔指数=0。 如果到了塔的最高层第n层扔没摔坏，则耐摔指数=n 为了减少测试次数，从每个厂家抽样3部手机参加测试。 某次测试的塔高为1000层，如果我们总是采用最佳策略，在最坏的运气下最多需要测试多少次才能确定手机的耐摔指数呢？ 请填写这个最多测试次数。 注意：需要填写的是一个整数，不要填写任何多余内容。 public class Solution { private static int n = 3; private static int m = 1000; private static int[][] dp = new int[n + 1][m + 1]; public static void main(String[] args) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j] = j;//初始化，最坏情况莫过于此 } } for (int i = 2; i <= n; i++) {//一部手机时，只能从一层开始一层一层摔 for (int j = 1; j <= m; j++) {//假设一共有j层楼 for (int k = 1; k <= j; k++) {//假设从k层摔 dp[i][j] = Math.min(dp[i][j], Math.max(dp[i - 1][k - 1], dp[i][j - k]) + 1); } } } System.out.println(dp[3][1000]); } } 3.5、快速排序(代码填空`9) 略 3.6、递增三元组(编程大题`11) 标题：递增三元组 给定三个整数数组 A = [A1, A2, … AN], B = [B1, B2, … BN], C = [C1, C2, … CN]， 请你统计有多少个三元组(i, j, k) 满足： 1 <= i, j, k <= NAi < Bj < Ck 【输入格式】 第一行包含一个整数N。 第二行包含N个整数A1, A2, … AN。 第三行包含N个整数B1, B2, … BN。 第四行包含N个整数C1, C2, … CN。 对于30%的数据，1 <= N <= 100 对于60%的数据，1 <= N <= 1000 对于100%的数据，1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000 【输出格式】 一个整数表示答案 【输入样例】 3 1 1 1 2 2 2 3 3 3 【输出样例】 27 思路：以b数组为基准 二分 public class Solution { private static int n; private static long ans; private static int[] a; private static int[] b; private static int[] c; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); a = new int[n]; b = new int[n]; c = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } for (int i = 0; i < n; i++) { b[i] = sc.nextInt(); } for (int i = 0; i < n; i++) { c[i] = sc.nextInt(); } Arrays.sort(a); Arrays.sort(b); Arrays.sort(c); for (int i = 0; i < b.length; i++) { ans += binMin(b[i]) * binMax(b[i]); } System.out.println(ans); } public static long binMax(int x) { int min = 0; int max = c.length; int mid = (min + max) / 2; while (min < max) { if (c[mid] > x) { max = mid; } else if (c[mid] <= x) { min = mid + 1; } mid = (min + max) / 2; } return c.length - max; } public static long binMin(int x) { //寻找小于x的最大值 int min = 0; int max = a.length; int mid = (max + min) / 2; while (min < max) { if (a[mid] < x) { min = mid + 1; } else if (a[mid] >= x) { max = mid; } mid = (max + min) / 2; } return max; } } 3.7、螺旋折线(编程大题`19) 如图p1.pgn所示的螺旋折线经过平面上所有整点恰好一次。 对于整点(X, Y)，我们定义它到原点的距离dis(X, Y)是从原点到(X, Y)的螺旋折线段的长度 例如dis(0, 1)=3, dis(-2, -1)=9 给出整点坐标(X, Y)，你能计算出dis(X, Y)吗？ public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); long X = in.nextLong(); long Y = in.nextLong(); // 判断所在点所在的正方形 long n = Math.max(Math.abs(X) , Math.abs(Y)); // 1. 之前正方形的长度和 long Sn = 4*(n-1)*n; // 2. 计算点(-n, -n) 到点(X, Y)的距离, 考虑清楚情况 long sum = 0; long px = -n, py = -n; long d1 = X-px, d2 = Y-py; if (Y > X) { sum += (d1+d2); } else { sum += (8*n-d1-d2); } System.out.println(sum + Sn); } } 3.8、日志统计(编程大题`21) 小明维护着一个程序员论坛。现在他收集了一份"点赞"日志，日志共有N行。其中每一行的格式是： ts id 表示在ts时刻编号id的帖子收到一个"赞"。 现在小明想统计有哪些帖子曾经是"热帖"。如果一个帖子曾在任意一个长度为D的时间段内收到不少于K个赞，小明就认为这个帖子曾是"热帖"。 具体来说，如果存在某个时刻T满足该帖在[T, T+D)这段时间内(注意是左闭右开区间)收到不少于K个赞，该帖就曾是"热帖"。 给定日志，请你帮助小明统计出所有曾是"热帖"的帖子编号。 【输入格式】 第一行包含三个整数N、D和K。 以下N行每行一条日志，包含两个整数ts和id。 对于50%的数据，1 <= K <= N <= 1000 对于100%的数据，1 <= K <= N <= 100000 0 <= ts <= 100000 0 <= id <= 100000 【输出格式】 按从小到大的顺序输出热帖id。每个id一行。 【输入样例】 7 10 2 0 1 0 10 10 10 10 1 9 1 100 3 100 3 【输出样例】 1 3 public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int d = in.nextInt(); int k = in.nextInt(); ArrayList HashSet HashMap for (int i = 0; i < n; i++) { int a = in.nextInt(); int b = in.nextInt(); map.put(b, 0); list.add(new Node(a, b)); } Collections.sort(list); int min = list.get(0).t, max = list.get(0).t, i = 0, j = 0; while (j < n) {//双指针 Node u = list.get(j); max = u.t; map.put(u.id, map.get(u.id) + 1); while (max - min >= 10) { Node v = list.get(i); map.put(v.id, map.get(v.id) - 1); i++; min = list.get(i).t; } if (map.get(u.id) >= k) set.add(u.id); j++; } ArrayList for (int x : set) ans.add(x); Collections.sort(ans); for (int x : ans) System.out.println(x); } } class Node implements Comparable int t, id; public Node(int t, int id) { this.t = t; this.id = id; } @Override public int compareTo(Node o) { return this.t - o.t; } } 3.9、全球变暖(编程大题`23) 略 3.10、堆的计数(编程大题`25) 略 4、八届 4.1、购物单(结果填空`5) 太简单，略 4.2、纸牌三角形(结果填空`11) A,2,3,4,5,6,7,8,9 共9张纸牌排成一个正三角形（A按1计算）。要求每个边的和相等。 下图就是一种排法（如有对齐问题，参看p1.png）。 A 9 6 4 8 3 7 5 2 这样的排法可能会有很多。 如果考虑旋转、镜像后相同的算同一种，一共有多少种不同的排法呢？ 请你计算并提交该数字。 注意：需要提交的是一个整数，不要提交任何多余内容。 public class Solution { public static void main(String[] args) { dfs(0); System.out.println(ans / 6.0); } static int[] a = new int[]{1, 2, 3, 4, 5, 6, 7, 8, 9}; static int ans = 0; static void dfs(int m) { if (m >= 9) { if (a[0] + a[1] + a[3] + a[5] == a[0] + a[2] + a[4] + a[8] && a[0] + a[1] + a[3] + a[5] == a[5] + a[6] + a[7] + a[8]) { ans++; } return; } for (int i = m; i < 9; i++) { swap(i, m); dfs(m + 1); swap(i, m); } } static void swap(int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; } } 4.3、承压计算(结果填空`13) 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台极高精度的电子秤。 假设每块原料的重量都十分精确地平均落在下方的两个金属块上， 最后，所有的金属块的重量都严格精确地平分落在最底层的电子秤上。 电子秤的计量单位很小，所以显示的数字很大。 public class _03承压计算1 { static long[][] arr = new long[30][30]; public static void main(String[] args) { Scanner sc = new Scanner(System.in); long factor=1;//2的 30次方 for (int i = 0; i < 30; ++i) { factor<<=1; } // 输入数据放入二维数组 for (int i = 0; i < 29; ++i) { for (int j = 0; j <= i; ++j) { long a=sc.nextLong(); arr[i][j]=a*factor;//每个数据都乘以factor } } //自上而下处理a[i][j]*factor（2的30次方）-->除以2，计入a[i+1][j]和a[i+1][j+1] //循环处理第1~N-1行 for (int i = 0; i < 29; ++i) { for (int j = 0; j <=i ; ++j) { long ha =arr[i][j]/2; arr[i+1][j]+=ha; arr[i+1][j+1]+=ha; } } //对a[N-1]这一行进行排序，查看最小值与factor之间的倍数关系，决定最大值是多少 Arrays.sort(arr[29]); System.out.println(arr[29][0]); System.out.println(arr[29][29]); System.out.println(arr[29][29]/(arr[29][0]/2086458231)); } } 4.4、魔方状态(结果填空`17) 二阶魔方就是只有2层的魔方，只由8个小块组成。 小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下： 前面：橙色 右面：绿色 上面：黄色 左面：绿色 下面：橙色 后面：黄色 请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。 如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态 /* 标题：魔方状态 二阶魔方就是只有2层的魔方，只由8个小块组成。 如图p1.png所示。 小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下： 前面：橙色 右面：绿色 上面：黄色 左面：绿色 下面：橙色 后面：黄色 请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。 如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。 请提交表示状态数的整数，不要填写任何多余内容或说明文字。 */ public class _03魔方状态 { static char[][] start = {"oybbgb".toCharArray(), "oygbbb".toCharArray(), "bygbby".toCharArray(), "bybbgy".toCharArray(), "obbogb".toCharArray(), "obgobb".toCharArray(), "bbgoby".toCharArray(), "bbbogy".toCharArray()}; static char[][][] q = new char[2000000][8][6]; static Set static int front, tail; static String to_string(char[][] a) { String ans = ""; for (int i = 0; i < 8; ++i) { ans += new String(a[i]); } return ans; } private static void swap(char[] a, int i, int j) { char t = a[i]; a[i] = a[j]; a[j] = t; } private static void swap(char[][] a, int i, int j) { char[] t = a[i]; a[i] = a[j]; a[j] = t; } //上层的块的旋转，面的相对位置调换 static void ucell(char[] a) { swap(a, 0, 2); swap(a, 2, 5); swap(a, 5, 4); } //上层顺时针旋转 static void u(char[][] s) { ucell(s[0]); ucell(s[1]); ucell(s[2]); ucell(s[3]); // 块的相对位置调换 swap(s, 1, 0); swap(s, 2, 1); swap(s, 3, 2); } //右层旋转是面的位置变化 static void rcell(char[] a) { swap(a, 1, 0); swap(a, 0, 3); swap(a, 3, 5); } static void r(char[][] s)//魔方右层顺时针转 { rcell(s[1]); rcell(s[2]); rcell(s[6]); rcell(s[5]); // 块的位置变化 swap(s, 2, 1); swap(s, 5, 1); swap(s, 6, 5); } static void fcell(char[] a) { swap(a, 2, 1); swap(a, 1, 4); swap(a, 4, 3); } static void f(char[][] s)//前面一层 顺时针转 { fcell(s[0]); fcell(s[1]); fcell(s[4]); fcell(s[5]); swap(s, 1, 5); swap(s, 0, 1); swap(s, 4, 0); } static void uwhole(char[][] s)//整个魔方从顶部看 顺时针转 用于判重 { u(s);//上层旋转 // 下层旋转 ucell(s[4]); ucell(s[5]); ucell(s[6]); ucell(s[7]); // 完成自旋后，块的位置变动 swap(s, 5, 4); swap(s, 6, 5); swap(s, 7, 6); } static void fwhole(char[][] s)//整个魔方从前面看 顺时针转 用于判重 { f(s); fcell(s[2]); fcell(s[6]); fcell(s[7]); fcell(s[3]); swap(s, 2, 6); swap(s, 3, 2); swap(s, 7, 3); } static void rwhole(char[][] s)//整个魔方从右边看 顺时针转 用于判重 { r(s); rcell(s[0]); rcell(s[3]); rcell(s[4]); rcell(s[7]); swap(s, 3, 7); swap(s, 0, 3); swap(s, 4, 0); } static boolean try_insert(char[][] s) { char[][] k = new char[8][6]; memcpy(k, s); for (int i = 0; i < 4; i++) { fwhole(k); for (int j = 0; j < 4; j++) { uwhole(k); for (int q = 0; q < 4; q++) { rwhole(k); if (all_state.contains(to_string(k))) { return false; } } } } all_state.add(to_string(k)); return true; } private static void memcpy(char[][] k, char[][] s) { for (int i = 0; i < 8; i++) { for (int j = 0; j < 6; j++) { k[i][j] = s[i][j]; } } } static void solve() { front = 0; tail = 1; all_state.add(to_string(start)); memcpy(q[front], start);//填充q[0]，相当于第一个状态入队列 while (front < tail) { /*将其所有变形，尝试加入set中*/ memcpy(q[tail], q[front]);//拷贝到tail u(q[tail]);//上层顺时针旋转 if (try_insert(q[tail])) { tail++;//扩展队列 } memcpy(q[tail], q[front]);//拷贝到tail r(q[tail]);//右层顺时针旋转 if (try_insert(q[tail])) { tail++;//扩展队列 } memcpy(q[tail], q[front]);//拷贝到tail f(q[tail]);//前顺时针旋转 if (try_insert(q[tail])) { tail++;//扩展队列 } front++;//弹出队首 // cout << front << " " << tail << endl; } System.out.println(front); } public static void main(String[] args) { solve(); } } 4.5、取位数(代码填空`7) 代码填空略 4.6、最大公共子串(代码填空`9) 代码填空略 4.7、日期问题(编程大题`19) 小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在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 public class Solution { static boolean isLeap(int year) { return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0; } static String f(int a, int b, int c) { if (a >= 0 && a <= 59) a += 2000; else if (a >= 60 && a <= 99) a += 1900; else return ""; if (b < 1 || b > 12) return ""; if (c < 1 || c > 31) return ""; boolean _isLeap = isLeap(a); switch (b) {//日期校验 case 2: if (_isLeap && c > 29) return ""; if (!_isLeap && c > 28) return ""; break; case 4: if (c > 30) return ""; break; case 6: if (c > 30) return ""; break; case 9: if (c > 30) return ""; break; case 11: if (c > 30) return ""; break; default: break; } String _a = a + "", _b = b + "", _c = c + ""; if (_b.length() == 1) _b = "0" + _b; if (_c.length() == 1) _c = "0" + _c; return _a + "-" + _b + "-" + _c; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String in = sc.nextLine(); int a = 0, b = 0, c = 0; a = (in.charAt(0) - '0') * 10 + (in.charAt(1) - '0'); b = (in.charAt(3) - '0') * 10 + (in.charAt(4) - '0'); c = (in.charAt(6) - '0') * 10 + (in.charAt(7) - '0'); String case1 = f(a, b, c); String case2 = f(c, a, b); String case3 = f(c, b, a); /*TreeSet带去重和排序功能*/ Set if (!case1.equals("")) ans.add(case1); if (!case2.equals("")) ans.add(case2); if (!case3.equals("")) ans.add(case3); for (String s : ans) { System.out.println(s); } } } 4.8、包子凑数(编程大题`21) 小明几乎每天早晨都会在一家包子铺吃早餐。他发现这家包子铺有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，所有奇数都凑不出来，所以有无限多个。 public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] a = new int[n + 5]; int[] dp = new int[10005];//只有2个数时，最大不能组合的数x*y-x-y，有这个公式 int ans = 0; dp[0] = 1; for (int i = 1; i <= n; i++) a[i] = in.nextInt(); int g = a[1]; for (int i = 2; i <= n; i++) g = gcd(g, a[i]); if (g != 1) { System.out.println("INF"); return; } for (int i = 1; i <= n; i++) for (int j = a[i]; j <= 10000; j++) dp[j] = Math.max(dp[j], dp[j - a[i]]); for (int j = 1; j <= 10000; j++) if (dp[j] == 0) ans++; System.out.println(ans); } static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } } 4.9、分巧克力(编程大题`23) 儿童节那天有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 while(l<=r) { int mid = l + (r-l)/2; if(ok(mid)) { l=mid+1; ans=mid; }else r = mid - 1; } System.out.println(ans); 4.10、K倍区间(编程大题`25) 给定一个长度为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 public class Solution { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); int[] sum = new int[n + 1]; for (int i = 1; i <= n; i++) { sum[i] = sum[i - 1] + scanner.nextInt(); } int ans = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= n; j++) { if ((sum[j + 1] - sum[j]) % k == 0) { ans++; } } } System.out.println(ans); } } 5、七届 5.1、煤球数目(结果填空`3) 有一堆煤球，堆成三角棱锥形。具体： 第一层放1个， 第二层3个（排列成三角形）， 第三层6个（排列成三角形）， 第四层10个（排列成三角形）， … 如果一共有100层，共有多少个煤球？ 请填表示煤球总数目的数字。 public class Solution { public static void main(String[] args) { int sum = 0; int s = 0; for (int i = 1; i <= 100; i++) { s += i; sum += s; } System.out.println(sum + " " + s); } } 5.2、生日蜡烛(结果填空`5) 某君从某年开始每年都举办一次生日party，并且每次都要吹熄与年龄相同根数的蜡烛。 现在算起来，他一共吹熄了236根蜡烛。 请问，他从多少岁开始过生日party的？ 请填写他开始过生日party的年龄数。 public class Solution { public static void main(String[] args) { for (int i = 1; i <= 100; i++) { for (int j = i + 1; j <= 100; j++) { if ((i + j) * (j - i + 1) / 2 == 236) { System.out.println(i + " " + j); } } } } } 5.3、凑算式(结果填空`9) B DEF A + — + ------- = 10 C GHI （如果显示有问题，可以参见【图1.jpg】） 这个算式中AI代表19的数字，不同的字母代表不同的数字。 比如： 6+8/3+952/714 就是一种解法， 5+3/1+972/486 是另一种解法。 这个算式一共有多少种解法？ 注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。 //暴力循环解决 5.4、分小组(代码填空`11) 略 5.5、抽签(代码填空`13) 略 5.6、方格填数(结果填空`15) 填入0~9的数字。要求：连续的两个数字不能相邻。 （左右、上下、对角都算相邻） 一共有多少种可能的填数方案？ 请填写表示方案数目的整数。 注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。 //全排列后，加入判断条件 5.7、剪邮票(结果填空`19) 太复杂略 5.8、四平方和(编程大题`21) 5.9、取球博弈(编程大题`23) 5.10、压缩变换(编程大题`31) 8、四届 8.1、世纪末的星期(结果填空`3) 曾有邪教称1999年12月31日是世界末日。当然该谣言已经不攻自破。 还有人称今后的某个世纪末的12月31日，如果是星期一则会… 有趣的是，任何一个世纪末的年份的12月31日都不可能是星期一!! 于是，“谣言制造商”又修改为星期日… 1999年的12月31日是星期五，请问：未来哪一个离我们最近的一个世纪末年（即xx99年）的12月31日正好是星期天（即星期日）？ 请回答该年份（只写这个4位整数，不要写12月31等多余信息） 2299，Calender类可用于1970年以后的日期操作 public class Solution { public static void main(String[] args) { Calendar calendar = Calendar.getInstance(); for (int i = 1999; i < 10000; i += 100) { calendar.set(Calendar.YEAR, i); calendar.set(Calendar.MONTH, 11); calendar.set(Calendar.DAY_OF_MONTH, 31); if (calendar.get(Calendar.DAY_OF_WEEK) == Calendar.SUNDAY) { System.out.println(i); break; } } } } 8.2、马虎的算式(结果填空`6) 小明是个急性子，上小学的时候经常把老师写在黑板上的题目抄错了。 有一次，老师出的题目是：36 x 495 = ? 他却给抄成了：396 x 45 = ? 但结果却很戏剧性，他的答案竟然是对的！！ 因为 36 * 495 = 396 * 45 = 17820 类似这样的巧合情况可能还有很多，比如：27 * 594 = 297 * 54 假设 a b c d e 代表1~9不同的5个数字（注意是各不相同的数字，且不含0） 能满足形如： ab * cde = adb * ce 这样的算式一共有多少种呢？ 请你利用计算机的优势寻找所有的可能，并回答不同算式的种类数。 满足乘法交换律的算式计为不同的种类，所以答案肯定是个偶数。 public class Solution { public static void main(String[] args) { int count = 0; for (int a = 1; a <= 9; a++) { for (int b = 1; b <= 9; b++) { for (int c = 1; c <= 9; c++) { for (int d = 1; d <= 9; d++) { for (int e = 1; e <= 9; e++) { if ((a * 10 + b) * (c * 100 + d * 10 + e) == (a * 100 + d * 10 + b) * (c * 10 + e) && a != b && a != c && a != d && a != e && b != c && b != d && b != e && c != d && c != e && d != e) { count++; } } } } } } System.out.println(count); } } 推荐链接
您阅读本篇文章共花了：
发表评论