蓝桥杯刷题——day6
- 题目一
- 题干
- 解题思路
- 代码
- 题目二
- 题干
- 解题思路
- 代码
题目一
题干
小明发现49很有趣，首先，它是个平方数。它可以拆分为4和9，拆分出来的部分也是平方数。169 也有这个性质，我们权且称它们为：拼接平方数。100 可拆分1,00，这有点勉强，我们规定，0,00,000 等都不算平方数。小明想：还有哪些数字是这样的呢？你的任务出现了：找到某个区间的所有拼接平方数。
输入： 两个正整数 a,b，其中（a<b<10的6次方）
输出： 若干行，每行一个正整数。表示所有的区间 [a,b] 中的拼接平方数，从小到大输出。
示例一：
输入：
169 10000
输出：
169
361
1225
1444
1681
3249
4225
4900
9025
题目链接：拼接平方数
解题思路
这条题目很简单，首先我们从a遍历到b，在遍历的过程中先要满足他是一个平方数，如果是平方数，那么我们记录他的位数，然后再根据位数逐个划分为两个部分，在判断这两个部分是否是平方数。下面是完整代码：
代码
import java.util.Scanner;
public class Main {public static boolean is_sqrt(int a) {if (a == 0){return false;}double num = Math.sqrt(a);return num == Math.floor(num);}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int a = scanner.nextInt();int b = scanner.nextInt();for (int i = a; i <= b; i++) {int tmp = i;if (is_sqrt(tmp)) {int num = 1;while (tmp / 10 != 0) {num++;tmp = tmp / 10;}while (num > 0) {num--;int ten = (int) Math.pow(10, num);int x = i / ten;int y = i % ten;if (is_sqrt(x)&& is_sqrt(y)){System.out.println(i);}}}}}
}
is_sqrt函数是用于判断一个数是否是平方数，首先根据题意，0不是平方数，然后我们将这个数进行开平方，然后向下取值，如果向下取值和开平方数是一样的，那就证明该数是平方数，然后num用于记录该数的位数，x和y分别记录分开来的数字，如果同时满足x和y都是平方数，则打印出来。
题目二
题干
在一个排列中，一个折点是指排列中的一个元素，它同时小于两边的元素，或者同时大于两边的元素。对于一个1∼n 的排列，如果可以将这个排列中包含t个折点，则它称为一个t+1 单调排列。例如，排列 (1,4,2,3)是一个3单调排列，其中4和2都是折点，给定n和k，请问1∼n的所有排列中有多少个k单调排列？
输入： 输入一行包含两个整数n和k。
输出： 输出一个整数，表示答案。答案可能很大，你可需要输出满足条件的排列 数量除以123456 的余数即可。
示例一：
输入：
4 2
输出：
12
题目链接：排列数
解题思路
这条题目可以说是相当的难了，刚拿到手可能想到的是暴力解法，可能完全无从下手，这时候我们就要想到用动态规划来解决了，我们先来理解一下这条题目的大致意思，我们来看这么一个图：
我们可以看到有两个折点（5和1），这个5和1将这个数列分为了三段（红-蓝-红标了出来），题目问我们我现在给你一个两个数（一个表示节点的个数，一个表示分为了几段），问有多少种方法。这个就是题目的大致意思了，那么如何解决呢？我们假设dp[i][j] 表示 1∼i 的排列中j单调序列的个数。我们需要分以下几种情况：
1.j为偶数，并且序列开始处上升状态，如图：
- 当我们把i+1插入到两个“峰”的前后时，我们发现j没有发生改变，并且开始序列仍然保持上升的状态，我们发现如果有j个单调序列，那么就会有j/2个“峰”，那么得到转移方程式：
dp[i+1][j] = dp[i+1][j] + dp[i][j] × j
- 当我们把i+1插入到开头处时，开头序列就会从上升状态变为下降状态，同时单调序列从j变为j+1；同样的，当我们把i+1插入到末尾时，结尾序列就会从下降状态变为上升状态，同时单调序列从j变为j+1；因此转移方程式：
dp[i + 1][j + 1] = dp[i + 1][j + 1] + dp[i][j] × 2
- 以上两种考虑完了，我们发现将n+1插入其他的位置，j个单调序列就会变为j+2，除去以上两种情况，剩下(i+1)−j−2 = i−j−1种情况，得到转移方程：
dp[i + 1][j + 2] = dp[i + 1][j + 2] + dp[i][j] * (i - j - 1)
2.j为偶数，并且序列开始处下降状态，如图：
- 当我们把i+1插入到两个“峰”的前后时，我们发现j没有发生改变，并且开始序列仍然保持下降的状态，我们发现如果有j个单调序列，那么就会有（j/2）-1个“峰”，同时我们又发现，如果将i+1插入开始位置和结束位置，他的j也不会发生变化，因此总共有2×[(j/2)-1]+2个情况，化简可得就是为j，那么得到转移方程式：
dp[i+1][j] = dp[i+1][j] + dp[i][j] × j
- 当我们把i+1插入开始的第二个节点和结束的倒数第二个节点时，j个单调序列就会从j变为j+1，因此我们得到转移方程：
dp[i + 1][j + 1] = dp[i + 1][j + 1] + dp[i][j] × 2
- 以上两种考虑完了，我们发现将n+1插入其他的位置，j个单调序列就会变为j+2，除去以上两种情况，剩下(i+1)−j−2 = i−j−1种情况，得到转移方程：
dp[i + 1][j + 2] = dp[i + 1][j + 2] + dp[i][j] * (i - j - 1)
3.j为奇数，并且序列开始处上升状态和4.j为奇数，并且序列开始处下降状态这两种情况与上面的结果是一模一样的所以我们就不在赘述，因为这些状态转移方程是一摸一样的，我们就可以进行合并，这也是为什么求状态转移方程时，我们会在前面加上一个自身，例如dp[i+1][j] = dp[i+1][j] + dp[i][j] × j ，这个状态转移方程中我们是dp[i+1][j] = dp[i+1][j] + dp[i][j] × j，而不是dp[i+1][j] = dp[i][j] × j，就是这个原因。最后让我们看一下完整代码：
代码
import java.util.Scanner;
public class Main {public static void main(String[] args) {int[][] dp = new int[505][505];int mod = 123456;Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();if (n == 1) {if (m == 1) {System.out.println(1);} else {System.out.println(0);}}dp[2][1] = 2;for (int i = 2; i < n; i++) {for (int j = 1; j <= m; j++) {dp[i + 1][j] = (dp[i + 1][j] + dp[i][j] * j) % mod;dp[i + 1][j + 1] = (dp[i + 1][j + 1] + dp[i][j] * 2) % mod;dp[i + 1][j + 2] = (dp[i + 1][j + 2] + dp[i][j] * (i - j - 1)) % mod;}}System.out.println(dp[n][m] % mod);}
}
这条题目可以说是相当有难度，因此千万不要因为做不出来垂头丧气，也不怕各位笑话这条题目我看别人解析，自己理解就花了一个多小时。当然如果能自己做出来那真的是特别的厉害，可以说是将动态规划融会贯通了，如果有什么疑问或者问题，欢迎私信+评论，谢谢各位的点赞收藏。
