蓝桥杯JavaB组
2013年
3. 振兴中华
入门dfs
public class T3 {
public static void main(String[] args) {
int ans = 0;
ans = dfs(0, 0);
System.out.println(ans);
}
static int dfs(int i, int j) {
if (i == 3 || j == 4) {
return 1;
}
return dfs(i + 1, j) + dfs(i, j + 1);
}
}
4. 黄金连分数
思路分析:
① 转换为斐波那契数列找规律 最重要的是确定需要多少项(n)才能保证得到的100位小数是稳定的
② double 无法表示100位小数 BigInteger、BigDecimal 除法的表示
③ 截取字符串(103位),出去“‘0”和“.”剩余101位 确保四舍五入
import java.math.BigDecimal;
import java.math.BigInteger;
public class T4 {
public static void main(String[] args) {
BigInteger a = BigInteger.ONE;
BigInteger b = BigInteger.ONE;
for (int i = 3; i < 500; i++) {
BigInteger t = b;
b = a.add(b);
a = t;
}
BigDecimal divide = new BigDecimal(a, 110).divide(new BigDecimal(b, 110), BigDecimal.ROUND_HALF_DOWN);
System.out.println(divide.toPlainString().substring(0, 103));
}
}
7. 错误票据
输入比较特别、比较的格式。
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
ArrayList<Integer> list = new ArrayList<>();
int N = scanner.nextInt();
scanner.nextLine();
for (int i = 0; i < N; i++) {
String line = scanner.nextLine();
String[] split = line.split(" ");
for (int j = 0; j < split.length; j++) {
list.add(Integer.parseInt(split[j]));
}
}
Collections.sort(list);
int a = 0, b = 0;
for (int i = 1; i < list.size(); i++) {
if (list.get(i) - list.get(i - 1) == 2) {
a = list.get(i) - 1;
}
if (list.get(i).equals(list.get(i - 1))) {
b = list.get(i);
}
}
System.out.println(a + " " + b);
}
}
8. 幸运数(Hard)
比较麻烦。
import java.util.Scanner;
/*
* 题目描述
幸运数是波兰数学家乌拉姆命名的。它采用与生成素数类似的“筛法”生成。
首先从1开始写出自然数1,2,3,4,5,6,…
1 就是第一个幸运数。
我们从2这个数开始。把所有序号能被2整除的项删除,变为:
1 _ 3 _ 5 _ 7 _ 9 …
把它们缩紧,重新记序,为:
1 3 5 7 9 … 。这时,3为第2个幸运数,然后把所有能被3整除的序号位置的数删去。
注意,是序号位置,不是那个数本身能否被3整除!! 删除的应该是5,11, 17, …
此时7为第3个幸运数,然后再删去序号位置能被7整除的(19,39,…)
最后剩下的序列类似:
1, 3, 7, 9, 13, 15, 21, 25, 31, 33, 37, 43, 49, 51, 63, 67, 69, 73, 75, 79, …
本题要求:
输入两个正整数m n, 用空格分开 (m < n < 1000*1000)
程序输出 位于m和n之间的幸运数的个数(不包含m和n)。
例如:
用户输入:
1 20
程序输出:
5
例如:
用户输入:
30 69
程序输出:
8
资源约定:
峰值内存消耗(含虚拟机) < 64M
CPU消耗 < 2000ms
请严格按要求输出,不要画蛇添足地打印类似:“请您输入…” 的多余内容。
所有代码放在同一个源文件中,调试通过后,拷贝提交该源码。
注意:不要使用package语句。不要使用jdk1.6及以上版本的特性。
注意:主类的名字必须是:Main,否则按无效代码处理。
*/
// 每一轮会删除多个幸运数(m~n区间比较大时)
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = sc.nextInt();
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = 2 * i + 1; // 第一轮删掉第一个幸运数2对应位置倍数的项(即剩余奇数)
}
int luckyIdx = 1; // 幸运数下标 a[lucky]为幸运数
while (true) {
int p = luckyIdx + 1; // 每次遇到幸运数,将后面数字往前移动所需要移动的步数
for (int i = luckyIdx + 1; i < n; i++) {
if ((i + 1) % a[luckyIdx] == 0) {
continue; // 遇到幸运数 不采取任何操作
} else {
a[p] = a[i];
p++; // 每轮遇到一个幸运数,后面的数字所需移动的步数将逐步加1
}
}
luckyIdx++; // 定位到下一轮的第一个幸运数下标
if (a[luckyIdx] >= n) {
break;
}
}
int ans = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] >= n) break;
if (a[i] > m) {
ans ++;
}
}
System.out.println(ans);
}
}
9. 带分数(Hard)
全排列模板
import java.util.Scanner;
public class Main {
static int ans;
static int N;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
f(arr, 0);
System.out.println(ans);
}
private static void f(int[] arr, int k) {
if (k == 9) {
check(arr);
return;
}
for (int i = k; i < arr.length; i++) {
int t = arr[i];
arr[i] = arr[k];
arr[k] = t;
f(arr, k + 1);
t = arr[i];
arr[i] = arr[k];
arr[k] = t;
}
}
private static void check(int[] arr) {
for (int i = 1; i <= 7; i++) {
int num1 = toInt(arr, 0, i);
if (num1 >= N) {
continue;
}
for (int j = 1; j <= 8 - i; j++) {
int num2 = toInt(arr, i, j);
int num3 = toInt(arr, i + j, 9 - i - j);
if (num2 % num3 == 0 && num1 + num2 / num3 == N) {
ans ++;
}
}
}
}
private static int toInt(int[] arr, int startPosition, int len) {
int t = 1, ans = 0;
for (int i = startPosition + len - 1; i >= startPosition; i--) {
ans += arr[i] * t;
t *= 10;
}
return ans;
}
}
10. 连号区间数(Medium)
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[] arr = new int[n + 1];
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
}
int ans = 0;
for (int i = 1; i <= n; i++) {
int max = arr[i];
int min = arr[i];
for (int j = i; j <= n; j++) {
if (arr[j] > max) {
max = arr[j];
}
if (arr[j] < min) {
min = arr[j];
}
if (i == j) {
ans ++;
} else {
if (max - min == j - i) {
ans++;
}
}
}
}
System.out.println(ans);
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)