文章目录
- 🧡🧡t1_求余🧡🧡
- 思路
- 代码
- 🧡🧡t2_灌水🧡🧡
- 思路
- 代码
- 🧡🧡t3_字符显示🧡🧡
- 思路
- 代码
- 🧡🧡t4_区间最大和🧡🧡
- 思路
- 代码
- 🧡🧡t5_转换次数🧡🧡
- 思路
- 代码
- 🧡🧡t6_数位和相等🧡🧡
- 思路
- 代码
- 🧡🧡t7_公约移动🧡🧡
- 思路
- 代码
- 🧡🧡t8_循环位移🧡🧡
- 思路
- 代码
- 🧡🧡t9_最多约数🧡🧡
- 思路
- 代码
- 🧡🧡t10_最后的元音🧡🧡
- 思路
- 代码
- 🧡🧡t11_最大落差🧡🧡
- 思路
- 代码
🧡🧡t1_求余🧡🧡
思路
- 方法1: 2 2023 2^{2023} 22023数太大了,现有的long类型无法存储,但是题目只问这个数除以1000的余数,因此答案只和这个大数的最后3位数有关,可以模拟逐渐×2的过程,其中每一次都截取最后3位数。
- 方法2:当然,java中也可以用BigInteger来存储这个数,再配合pow和mod方法也能求出答案。
代码
import java.math.BigInteger;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
// ============方法1==============
int two = 1; // 2^0
int ans = 0;
for (int i = 1; i <= 2023; i++) {
two *= 2;
ans = two % 1000;
two = two % 1000;
}
System.out.println(ans);
// =============方法2=============
BigInteger base = new BigInteger("2");
BigInteger exponent = new BigInteger("2023");
BigInteger big2 = base.pow(exponent.intValue());
// 求余数
BigInteger modulus = new BigInteger("1000");
BigInteger remainder = big2.mod(modulus);
System.out.println(remainder);
}
}
🧡🧡t2_灌水🧡🧡
问题描述
小蓝有一个 01 短阵。他打算将第一行第一列的0变为2。变化过程有传染性,每次2 的上下左右四个相邻的位置中的0都会变成2。直到最后每个2的周围都是1或2 结束。
请问,最终矩阵中有多少个2?
以下是小蓝的矩阵,共 30 行 40 列。
0000100010000001101010101001001100000011
0101111001111101110111100000101010011111
1000010000011101010110000000001011010100
0110101010110000000101100100000101001001
0000011010100000111111001101100010101001
0110000110000000110100000000010010100011
0100110010000110000000100010000101110000
0010011010100110001111001101100110100010
1111000111101000001110010001001011101101
0011110100011000000001101001101110100001
0000000101011000010011111001010011011100
0000100000011001000100101000111011101100
0010110000001000001010100011000010100011
0110110000100011011010011010001101011011
0000100100000001010000101100000000000010
0011001000001000000010011001100101000110
1110101000011000000100011001001100111010
0000100100111000001101001000001010010001
0100010010000110100001100000110111110101
1000001001100010011001111101011001110001
0000000010100101000000111100110010101101
0010110101001100000100000010000010110011
0000011101001001000111011000100111010100
0010001100100000011000101011000000010101
1001111010010110011010101110000000101110
0110011101000010100001000101001001100010
1101000000010010011001000100110010000101
1001100010100010000100000101111111111100
1001011010101100001000000011000110110000
0011000100011000010111101000101110110001
这是一道结果填空的题,你只需要算出结果后提交即可。
思路
坐标+感染,考虑直接BFS搜索,每个位置的往上下左右四个方向探索前,注意判断方向合法性和只有0的地方才能感染。
代码
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Scanner;
public class Main {
public static class Node {
int x, y;
public Node(int x, int y) {
this.x = x;
this.y = y;
}
}
public static Deque<Node> deque = new ArrayDeque<>();
public static char[][] grid = new char[35][45];
public static int[] dx = { -1, 1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
for (int i = 1; i <= 30; i++) {
String s = sc.next();
for (int j = 1; j <= 40; j++) {
grid[i][j] = s.charAt(j - 1);
}
}
// System.out.println(Arrays.deepToString(grid));
deque.addLast(new Node(1, 1));
while (!deque.isEmpty()) {
Node node = deque.removeLast();
int x = node.x;
int y = node.y;
grid[x][y] = '2';
for (int i = 0; i < 4; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if (tx < 1 || tx > 30 || ty < 1 || ty > 40)
continue;
if (grid[tx][ty] != '0')
continue;
deque.addLast(new Node(tx, ty));
}
}
int ans = 0;
for (char[] row : grid) {
for (char c : row) {
if (c == '2')
ans++;
}
}
System.out.println(ans); // 541
}
}
🧡🧡t3_字符显示🧡🧡
问题描述
小蓝要在屏幕上放置一行文字,每个字的宽度相同。
小蓝发现,如果每个字的宽为 36 像素,一行正好放下 30 个字,字符之间和前后都没有任何空隙。
请问,如果每个字宽为 10 像素,字符之间不包含空隙,一行可以放下多少个字?
思路
小学数学。。。。
代码
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(36 * 30 / 10);
}
}
🧡🧡t4_区间最大和🧡🧡
- 问题描述
给定一个序列 a[1],α[2],…,a[n]和一个整数k,请找出一个长度正好为 k 的区间,使得区间中所有数的和最大。
即要找到一个整数p,使得1≤p且p+k-1≤n,使得a[p]+a[p+1]+···+a[p+k-1]最大。 - 输入格式
输入的第一行包含两个整数 n,た。
第二行包含 , 个整数,相邻的整数之间使用一个空格分隔,表示给定的序列。 - 输出格式
输出一行包含一个整数,表示最大的区间和,你只需要输出和就行不需要输出方案。 - 样例
6 3
2 3 9 1 9 5
19
思路
最大n为 1 0 5 10^5 105,暴力法的两层for会超时,这正是前缀和所要解决的问题:以O(n)复杂度查询某个区间之和。
另外,考虑输入数据也蛮多的,用StreamTokenizer输入,加加速。
代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
public class Main {
public static final int N = 100010;
public static int[] arr = new int[N];
public static long[] s = new long[N];
public static StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
public static int ini() throws IOException {
st.nextToken();
return (int) st.nval;
}
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
int n = ini();
int k = ini();
for (int i = 1; i <= n; i++) {
arr[i] = ini();
}
for (int i = 1; i <= n; i++) {
s[i] = s[i - 1] + arr[i];
}
long maxv = Long.MIN_VALUE;
for (int i = 1; i <= n - k + 1; i++) {
maxv = Math.max(maxv, s[i + k - 1] - s[i - 1]);
}
System.out.println(maxv);
}
}
🧡🧡t5_转换次数🧡🧡
- 问题描述
给定一个整数,对这个整数的一次转换是指将这个整数变为这个整数的所有数位上的非零数字的乘积。
例如,对123456789进行-次转换变为1x2x3x4x5x6x7x8x9=362880,再进行次转换变为3x6x2x8x8=2304,再进行次转换变为2x3x4=24,再进行次转换变为 8。
给定一个整数,请依次将转换过程中经历的每个整数输出,直到小于10 - 输入格式
输入一行包含一个整数 n 。 - 输出格式
输出多行,每行包含一个整数。 - 样例
123456789
362880
2304
24
8
思路
简单模拟,又是取某个数的每一位数这个操作,蓝桥杯考的太多了。
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
while (n >= 10) {
long mul = 1;
while (n > 0) {
if (n % 10 != 0)
mul *= n % 10;
n /= 10;
}
n = mul;
System.out.println(mul);
}
}
}
🧡🧡t6_数位和相等🧡🧡
- 问题描述
如果一个正整数转化成二进制与转换成八进制后所有数位的数字之和相等,则称为数位和相等的数。
前几个数位和相等的正整数为 1,8,9,64…
请问第 23 个数位和相等的正整数是多少?
这是一道结果填空的题,你只需要算出结果后提交即可。
思路
java中可以用Integer.toBinaryString和Integer.toOctalString转二进制和八进制,再比对判断即可。
代码
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
int cnt = 0;
for (int i = 1; i <= 1000000; i++) {
String bin = Integer.toBinaryString(i);
String oct = Integer.toOctalString(i);
int bin_sum = 0;
int oct_sum = 0;
for (int j = 0; j < bin.length(); j++) {
bin_sum += bin.charAt(j) - '0';
}
for (int j = 0; j < oct.length(); j++) {
oct_sum += oct.charAt(j) - '0';
}
if (bin_sum == oct_sum)
cnt++;
if (cnt == 23) {
System.out.println(i); //4169
break;
}
}
}
}
🧡🧡t7_公约移动🧡🧡
- 问题描述
小蓝站在一个 n 行 m 列的方格图中间,方格图的每一个方格上都标有一个正整数。
如果两个相邻方格(上下左右四个方向相邻)内的数的最大公约数大于1,则可以从其中一个方格移动到另一个方格,当然也可以从另一个方格移回第一个方格。
假设小蓝开始时站在第r行第c列,请问小蓝可以移动到方格图内的多少个方格? - 输入格式
输入的第一行包含两个整数n,m ,用一个空格分隔,表示方格图的行数和列数。
接下来 n 行,每行包含 m 个正整数,相邻整数间用一个空格分隔,依次表示方格图中从第 1 行到第 n行,每行从第 1列到第 m 列中的数。
接下来一行包含两个整数 r, c,用一个空格分隔,表示小蓝所在的行号和列号。 - 输出格式
输出一行包含一个整数,表示答案。 - 样例
3 4
3 6 5 5
2 4 3 5
7 8 3 8
3 2
5
思路
跟前面t2_灌水问题类似,t2_灌水中每个坐标的上下左右四个相邻位置中为0即可感染,而这题中每个坐标的上下左右四个相邻位置满足最大公约数>1即可“感染“,然后统计数目就行,因此也可以采用bfs来做。 当然也能用dfs来做,这里我顺便练习dfs了。
另外,还是要背背用欧几里得法求最大公约数gcd的代码,挺常用的。
代码
import java.util.Scanner;
public class Main {
public static long gcd(long n1, long n2) {
while (n2 != 0) {
long res = n1 % n2; // 余数
n1 = n2;
n2 = res;
}
return n1;
}
public static int[][] grid = new int[1005][1005];
public static boolean[][] used = new boolean[1005][1005];
public static int[] dx = { -1, 1, 0, 0 };
public static int[] dy = { 0, 0, -1, 1 };
public static int cnt = 0;
public static int n, m;
public static void dfs(int x, int y) {
// System.out.println(x + " " + y);
used[x][y] = true;
cnt++;
for (int k = 0; k < 4; k++) {
int tx = x + dx[k];
int ty = y + dy[k];
if (tx < 1 || tx > n || ty < 1 || ty > m)
continue;
if (used[tx][ty])
continue;
if (gcd(grid[x][y], grid[tx][ty]) <= 1)
continue;
dfs(tx, ty);
// System.out.println("回溯:" + tx + " " + ty);
}
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
grid[i][j] = sc.nextInt();
}
}
int r = sc.nextInt();
int c = sc.nextInt();
dfs(r, c);
System.out.println(cnt);
}
}
🧡🧡t8_循环位移🧡🧡
思路
小学数学,考察模运算和除运算的区别,这里总结一下吧:
- % 模运算:x%10就是取 x 的最后一位,x%1000就是取 x的最后三位,以此类推。。
- / 除运算:x/10就是去掉 x 的最后一位,x/1000就是去掉 x的最后三位,以此类推。。
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int x = sc.nextInt();
System.out.println((x % 100000) * 10 + (x / 100000));
}
}
🧡🧡t9_最多约数🧡🧡
思路
求约数个数,即%==0的个数。
代码
public class Main {
public static int[] arr = { 393353, 901440, 123481, 850930, 423154, 240461, 373746, 232926, 396677, 486579, 744860,
468782, 941389, 777714, 992588, 343292, 385198, 876426, 483857, 241899, 544851, 647930, 772403, 109929,
882745, 372491, 877710, 340000, 659788, 658675, 296521, 491295, 609764, 718967, 842000, 670302, };
public static void main(String[] args) {
// TODO Auto-generated method stub
int maxv = -1;
int ans = 0;
for (int i = 0; i < 36; i++) {
int cnt = 0;
for (int j = 1; j <= arr[i]; j++) {
if (arr[i] % j == 0)
cnt++;
}
if (cnt > maxv) {
maxv = cnt;
ans = arr[i];
}
}
System.out.println(ans);
}
}
🧡🧡t10_最后的元音🧡🧡
思路
easy
代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
String s = sc.next();
char ans = 'a';
for (char c : s.toCharArray()) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
ans = c;
}
System.out.println(ans);
}
}
🧡🧡t11_最大落差🧡🧡
思路
简单遍历数组即可,可以稍微简写代码:边输入边检查。
代码
import java.util.Scanner;
public class Main {
public static int[] arr = new int[1005];
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int max_leep = -1;
boolean flag = false;
for (int i = 1; i <= n; i++) {
arr[i] = sc.nextInt();
if (i > 1 && arr[i] < arr[i - 1]) {
max_leep = Math.max(max_leep, arr[i - 1] - arr[i]);
flag = true;
}
}
if (flag)
System.out.println(max_leep);
else
System.out.println(0);
}
}