网站个人主页模板,wordpress账户页添加选项卡,长沙seo搜索,专门做问卷的网站文章目录 A 有奖猜谜思路解题方法复杂度Code B 煤球数目思路解题方法复杂度Code C 平方怪圈思路解题方法复杂度Code D 凑算式思路解题方法复杂度Code E 搭积木思路解题方法复杂度Code F 冰雹数思路解题方法复杂度Code G 四平方和思路解题方法复杂度Code I 密码脱落思路解题方法… 文章目录 A 有奖猜谜思路解题方法复杂度Code B 煤球数目思路解题方法复杂度Code C 平方怪圈思路解题方法复杂度Code D 凑算式思路解题方法复杂度Code E 搭积木思路解题方法复杂度Code F 冰雹数思路解题方法复杂度Code G 四平方和思路解题方法复杂度Code I 密码脱落思路解题方法复杂度Code A 有奖猜谜
思路 这个问题是一个简单的字符串处理问题。我们需要遍历字符串s每次遇到字符’v’我们就将结果乘以2遇到字符’x’我们就从结果中减去555。如果在任何时候结果变为负数我们就打印当前的索引并停止遍历。 解题方法 我们可以使用一个for循环来遍历字符串s。在每次迭代中我们检查当前字符是否为’v’或’x’并相应地更新结果。如果结果变为负数我们就打印当前的索引并退出循环。 复杂度
时间复杂度: O ( n ) O(n) O(n)其中n是字符串s的长度。我们需要遍历字符串s一次。 空间复杂度: O ( 1 ) O(1) O(1)。我们只需要一个变量来存储结果。 Code
public class Main {static String s vxvxvxvxvxvxvvx;public static void main(String[] args) {int res 777;for(int i 0; i s.length(); i) {if(s.charAt(i) v) {res * 2;} else {res - 555;}if(res 0) {System.out.println(i);break;}}System.out.println(res);
// System.out.println(58497);}
}B 煤球数目
思路 这是一个数学问题我们需要计算前100层的煤球数目。每一层的煤球数目都是一个等差数列的和第i层的煤球数目为12…i。 解题方法 我们可以使用一个for循环来计算前100层的煤球数目。在每次迭代中我们先将当前层的煤球数目加到结果中然后更新下一层的煤球数目。 复杂度
时间复杂度: O ( n ) O(n) O(n)其中n是层数。我们需要遍历每一层。 空间复杂度: O ( 1 ) O(1) O(1)。我们只需要两个变量来存储当前层的煤球数目和结果。 Code
public class Main {public static void main(String[] args) {int tmp 1;long res 0;for (int i 1, j 2; i 100; i, j) {res (long)tmp;tmp j;}System.out.println(res);
// System.out.println(171700);}}C 平方怪圈
思路 这是一个数学问题我们需要找到一个循环圈中的最大数字。我们可以通过不断地将一个正整数的每一位都平方后再求和得到一个新的正整数然后对新产生的正整数再做同样的处理直到结果开始循环。 解题方法 我们可以使用一个for循环来进行20次迭代这个数字足够大以确保我们找到循环。在每次迭代中我们将当前数字的每一位都平方后再求和然后更新当前数字为新的和。我们还需要一个变量来跟踪迄今为止遇到的最大数字。 复杂度
时间复杂度: O ( n ) O(n) O(n)其中n是迭代的次数。我们需要进行固定次数的迭代。 空间复杂度: O ( 1 ) O(1) O(1)。我们只需要几个变量来存储当前的和、当前的数字和最大的数字。 Code
public class Main {public static void main(String[] args) {int n 3;int sum 0;int res n;int ans 0;for (int i 0; i 20; i) {while (res 0) {sum Math.pow(res % 10, 2);res / 10;}res sum;ans Math.max(sum, ans);sum 0;}System.out.println(ans);}
}D 凑算式
思路 这是一个全排列问题我们需要找到所有可能的0-9的排列然后检查哪些排列满足给定的算式。算式为A B/C (DEFGH)/(IJKL) 10其中A、B、C、D、E、F、G、H、I、J、K、L是0-9的全排列。 解题方法 我们可以使用递归函数来生成所有可能的排列。在每次递归调用中我们将当前位置的数字与其后的每一个数字交换然后递归处理下一个位置。我们需要保存每一个生成的排列然后在所有排列中检查哪些满足给定的算式。 复杂度
时间复杂度: O ( n ! ) O(n!) O(n!)其中n是数字的数量。我们需要生成所有可能的排列。 空间复杂度: O ( n ) O(n) O(n)我们需要一个数组来保存当前的排列以及一个列表来保存所有生成的排列。 Code
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;public class Main {public static void main(String[] args) {// 思路 计算出 0 ~ 9的全排列Listint[] ans new ArrayList();int n 9;int[] a new int[n 1];for (int i 1; i n; i) {a[i] i;}f(a, 1, ans);int res 0;for(int[] arr : ans) {if(arr[1] ((double)arr[2] / arr[3]) ((double)(arr[4] * 100 arr[5] * 10 arr[6]) / (arr[7] * 100 arr[8] * 10 arr[9])) 10) {res;}}System.out.println(res);}private static void f(int[] a, int i, Listint[] ans) {if (i a.length) {ans.add(a.clone()); // 创建数组的副本并添加到结果列表中} else {for (int j i; j a.length; j) {swap(a, i, j);f(a, i 1, ans);swap(a, i, j);}}}private static void swap(int[] a, int i, int j) {int tmp a[i];a[i] a[j];a[j] tmp;}}E 搭积木
思路 这是一个动态规划问题。我们需要找到一个从顶部到底部的路径这个路径上的每一步都是从左到右的。我们可以使用一个三维数组来存储我们的动态规划状态其中每个状态表示当前的深度从顶部到底部的位置以及当前步骤的左右边界。 解题方法 我们从顶部开始对于每一层我们都尝试所有可能的左右边界。如果当前位置是空的用’.表示我们就可以向右移动。我们继续这个过程直到我们遇到一个障碍用’X’表示或者到达右边界。对于每一种可能的左右边界我们都计算出从当前位置到底部的所有可能路径的数量并将它们加起来。这个过程可以用深度优先搜索来实现。 复杂度
时间复杂度: O ( n 3 ) O(n^3) O(n3)其中n是矩阵的大小。因为我们需要遍历所有的深度和左右边界。 空间复杂度: O ( n 3 ) O(n^3) O(n3)我们需要一个三维数组来存储动态规划的状态。 Code
import java.util.Arrays;
import java.util.Scanner;public class Main {static final int N 103;static final int MOD (int)1e97;static int n, m;static char[][] s new char[N][N];static int[][][] f new int[N][N][N];static int dfs(int dep, int l, int r) {if (dep 0) {return 1;}if (f[dep][l][r] ! -1) {return f[dep][l][r];}int ans 1;for (int i l; i r; i) {if (s[dep][i] .) {for (int j i; j r; j) {if (s[dep][j] X) {break;}ans (ans dfs(dep - 1, i, j)) % MOD;}}}f[dep][l][r] ans;return f[dep][l][r];}public static void main(String[] args) {Scanner scanner new Scanner(System.in);n scanner.nextInt();m scanner.nextInt();for (int i 1; i n; i) {String line scanner.next();for (int j 1; j m; j) {s[i][j] line.charAt(j - 1); // 从每一行的第二列开始输入}}for (int[][] arr2D : f) {for (int[] arr1D : arr2D) {Arrays.fill(arr1D, -1);}}dfs(n, 1, m);System.out.println(f[n][1][m]);}
}F 冰雹数
思路 这是一个经典的数学问题也被称为Collatz猜想。对于任何一个正整数如果它是偶数我们就把它砍掉一半如果它是奇数我们就把它变成3倍加1。这样一直反复进行下去最终我们得到的必定是1。 在这个问题中我们需要找到小于或等于n的所有正整数中经过上述变换后能够得到的最大的数。 解题方法 我们可以使用一个简单的循环来解决这个问题。对于每一个小于或等于n的正整数我们都进行上述的变换直到变为1。在这个过程中我们记录下能够得到的最大的数。 复杂度
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn)其中 n n n是输入的数。因为对于每一个数我们都可能需要进行约 l o g n logn logn次操作。 空间复杂度: O ( 1 ) O(1) O(1)我们只需要常数的空间来存储当前的数和最大的数。 Code
import java.util.Scanner;
public class Main{public static void main(String[] args){Scanner in new Scanner(System.in);int n in.nextInt();long max 1;for(int i 2;i n;i) {long m i;do{max Math.max(max,m);m m % 2 0 ? m / 2 : m * 3 1;}while(m 1);}System.out.println(max);}
}G 四平方和
思路 这是一个四平方和的问题我们需要找到四个整数使得它们的平方和等于给定的数。我们可以通过枚举所有可能的四个整数来解决这个问题。 解题方法 我们从0开始对于每一个可能的a我们枚举所有可能的bc和d使得aa bb cc dd等于给定的数。我们需要注意的是为了避免重复的解我们需要保证bc和d不小于a。一旦我们找到一个解我们就可以停止搜索并输出这个解。 复杂度
时间复杂度: O ( n 2 ) O(n^2) O(n2)其中n是给定的数。因为我们需要枚举所有可能的abc和d。 空间复杂度: O ( 1 ) O(1) O(1)我们只需要常数的空间来存储abc和d。 Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main{static BufferedReader in new BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr new StreamTokenizer(in);static int n;public static void main(String[] args) throws IOException {n nextInt();for (int a 0; a * a * 4 n; a) {for (int b a; a * a b * b * 3 n; b) {for (int c b; a * a b * b c * c * 2 n; c) {int d (int) Math.sqrt(n - a * a - b * b - c * c);if (a * a b * b c * c d * d n) {out.println(a b c d);out.flush();return;}}}}}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}I 密码脱落
思路 这是一个经典的动态规划问题我们需要找到字符串中最长的回文子序列。然后我们可以通过删除一些字符来将原始字符串转换为这个回文子序列。因此我们需要删除的最小字符数就是原始字符串的长度减去最长回文子序列的长度。 解题方法 我们使用一个二维数组dp其中dp[i][j]表示字符串中从i到j的最长回文子序列的长度。我们首先初始化所有的dp[i][i]为1因为每个单独的字符都是一个回文序列。然后我们从长度为2开始逐渐增加长度更新dp数组。对于每个长度我们都枚举所有可能的起始位置然后根据以下规则更新dp[i][j] 如果s[i]等于s[j]那么dp[i][j]就等于dp[i1][j-1]2因为我们可以在dp[i1][j-1]表示的回文序列的两端添加s[i]和s[j]形成一个更长的回文序列。 如果s[i]不等于s[j]那么dp[i][j]就等于dp[i1][j]和dp[i][j-1]中的较大值因为我们可以删除s[i]或s[j]使得剩下的字符串成为一个更长的回文序列。 最后我们返回n-dp[0][n-1]这就是我们需要删除的最小字符数。 复杂度
时间复杂度: O ( n 2 ) O(n^2) O(n2)其中n是字符串的长度。我们需要枚举所有可能的子字符串所以时间复杂度是 O ( n 2 ) O(n^2) O(n2)。 空间复杂度: O ( n 2 ) O(n^2) O(n2)我们需要一个二维数组来存储动态规划的状态。 Code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;public class Main{static int MAXN1010;static int dp[][]new int[MAXN][MAXN];static BufferedReader innew BufferedReader(new InputStreamReader(System.in));static PrintWriter out new PrintWriter(new OutputStreamWriter(System.out));public static void main(String args[]) throws IOException{String sin.readLine();int ns.length();for(int len1;lenn;len) // 枚举长度for(int l0; llen-1n;l ) //枚举端点{int rllen-1;if(len1) dp[l][r]1;else{if(s.charAt(l)s.charAt(r))dp[l][r]dp[l1][r-1]2;if(dp[l][r-1]dp[l][r]) dp[l][r]dp[l][r-1];if(dp[l1][r]dp[l][r]) dp[l][r]dp[l1][r];}}out.println(n-dp[0][n-1]);out.flush();}
}
