第十一届蓝桥杯题解
A，门牌制作
签到题，利用int转换到String就可以检验每一个字符是不是2
package train;
public class test_12 {
public static void main(String[] args){
int ans=0;
for(int i=1;i<=2020;i++){
String str=String.valueOf(i);
for(int j=0;j<str.length();j++){
if(str.charAt(j)=='2')
ans++;
}
}
System.out.println(ans);
}
}
B，寻找2020
此题解法很暴力，模拟题，我是直接输入了这个矩阵，转换成字符数组，其他的好像在读
本地文件，都可以，但是输入数组，在测试网站过不了，填空题，不好操作，答案：16520
package train;
import java.util.Scanner;
public class test_13 {
static int ans=0;
public static void judge(int i,int j,char[][] st){
if(i+3<st.length){
StringBuilder s=new StringBuilder();
s.append(st[i][j]);
s.append(st[i+1][j]);
s.append(st[i+2][j]);
s.append(st[i+3][j]);
if(s.toString().equals("2020"))
ans++;
}//判断行中是否有2020
if(j+3<st.length){
StringBuilder s=new StringBuilder();
s.append(st[i][j]);
s.append(st[i][j+1]);
s.append(st[i][j+2]);
s.append(st[i][j+3]);
if(s.toString().equals("2020"))
ans++;
}//判断列是否有2020
if(j+3<st.length&&i+3<st.length){
StringBuilder s=new StringBuilder();
s.append(st[i][j]);
s.append(st[i+1][j+1]);
s.append(st[i+2][j+2]);
s.append(st[i+3][j+3]);
if(s.toString().equals("2020"))
ans++;
}//判断斜线上是否有2020
}
public static void main(String[] args)
{
int n=300;
char[][] map=new char[n][n];
Scanner sc=new Scanner(System.in);
for(int i=0;i<map.length;i++){
map[i]=sc.next().toCharArray();
}
for(int i=0;i< map.length;i++)
for(int j=0;j<map.length;j++){
judge( i,j,map);
}
System.out.println(ans);
}
}
C，蛇形填数
找到规律，就很好做，看对角线上n行n列的值就是nn+(n-1)(n-1)的值
package train;
public class test_14 {
public static void main(String[]args)
{
System.out.println(20*20+19*19);
}
}
D，七段码
利用并查集和dfs解出
并查集说白了其实是利用三个函数来创造一个树形结构，来做到查和结合集合的作用
第一个函数：begin()来初始化n'个节点
public static void begin(){
for(int i=1;i<=7;i++){
pre[i]=i;
}//每个节点都是自己的根节点
}//初始化数组，代表7个边
第二个函数：find(int x)来查找x，y的根节点
利用路径压缩，来找到自己的上级
public static int find(int x){
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);
}//完成路径压缩，来找上级
第三个函数：merge(int x,int y)来合并两个集合，或者说是两个树形结构，只要合并其根节点即可，
public static boolean merge (int x,int y){
x=find(x);y=find(y);
if(x==y)return false;
else pre[x]=y;
return true;
}
之后就是本题，具体看代码
package train;
public class test_15 {
//表示出图的各种边的组合
public static boolean[][] edge=new boolean[8][8];
public static int []pre=new int [8];
public static int ans=0;
public static boolean[]tag=new boolean[8];
//去查找父节点，
public static int find(int x){
if(pre[x]==x)return x;
return pre[x]=find(pre[x]);
}//完成路径压缩，来找上级
public static void begin(){
for(int i=1;i<=7;i++){
pre[i]=i;
}//每个节点都是自己的根节点
}//初始化数组，代表7个边
//合并两个集合，两个根节点不一样就合并
public static void merge(int x,int y){
pre[find(y)]=find(x);
}
//判断是否图连通
public static boolean judge(){
begin();
for(int i=1;i<=7;i++)
for(int j=i+1;j<=7;j++){
if(tag[i]&&tag[j]&&edge[i][j])//判断点是不是被选择，且两点之间是否连通
merge(i,j);
}
//判断集合个数
int collectionnum=0;
for(int i=1;i<=7;i++)
if(tag[i]&&pre[i]==i)
collectionnum++;
return collectionnum==1;
}
public static void dfs(int i){
if(i>7){
if(judge())
ans++;
return;
}
tag[i]=false;
dfs(i+1);
tag[i]=true;
dfs(i+1);
}
public static void main(String []args){
//把连通的边赋值为true
edge[1][2] = edge[2][1] = true;
edge[1][6] = edge[6][1] = true;
edge[2][3] = edge[3][2] = true;
edge[2][7] = edge[7][1] = true;
edge[3][7] = edge[7][3] = true;
edge[3][4] = edge[4][3] = true;
edge[4][5] = edge[5][4] = true;
edge[5][7] = edge[7][5] = true;
edge[5][6] = edge[6][5] = true;
edge[6][7] = edge[7][6] = true;
dfs(1);
System.out.println(ans);
}
}
E，排序
一个长度为n的字符串，如果进行冒泡排序，假设他每次比较都进行了交换，那么它最多交换 (n-1)+(n-2)+…+1 = n*(n-1）/2 （进行n-1趟操作，第一趟操作交换n-1次，之后每趟交换的次数依次递减）。
所以先算出交换100次最少需要多长的字符串，发现不能整除，长度15的字符串要交换105次，长度14的字符串要交换91次，注意这个公式是假设么一次都交换的公式，那么我们选一个长度为15的字符串来减少5次交换次数，再看题目要求是字典序最小的字符串，所以我们从a开始数到第15个，所以我们选定abcdefghijklmno这是排序后的字符串，然后倒过来onmlkjihgfedcba(我以为到这里就结束了，经过测评，没有通过，写了一个冒泡排序，发现是105次，忘记减少5次排序了)，那么此时在到过来的字符串前，只要把第6个字符放到最前面就可以减少5次交换，达到100次交换，变成jonmlkihgfedcba，
package train;
import java.util.Scanner;
public class test_16 {
public static void main(String [] args){
// Scanner in = new Scanner(System.in);
// int nums = in.nextInt();
// String[] str = new String[nums];
// String temp;
// int cnt=0;
// for( int i = 0; i < str.length; i++)
// {
// str[i] = in.nextLine();
// }
//
// for(int i = 0; i < nums-1; i++) //排序次数
// {
// for(int j = 0; j < nums - i - 1; j++)
// {
// if(str[j].compareTo(str[j+1]) > 0) //比较str1和str2
// {
// temp = str[j];
// str[j] = str[j+1];
// str[j+1] = temp;
// cnt++;
// }
// }
// }
// for(int i = 0; i < str.length; i++)
// {
// System.out.println(str[i]);
// }
// System.out.println(cnt);
System.out.println("jonmlkihgfedcba");
}
}
F，成绩分析
签到题
package train;
import java.util.Scanner;
public class test_17 {
public static void main(String[]args){
Scanner br=new Scanner(System.in);
int n;
n=br.nextInt();
int [] a=new int [n];
for(int i=0;i<n;i++){
a[i]=br.nextInt();
}
int max=a[0],min=a[0],sum=0;
double pp;
for(int i=0;i<n;i++){
if(max<a[i])max=a[i];
if(min>a[i])min=a[i];
sum+=a[i];
}
pp=sum/(n*1.0);
System.out.println(max);
System.out.println(min);
System.out.println(String.format("%.2f",pp));
}
}
G，单词分析
签到题
package train;
import java.util.Scanner;
public class test_18 {
public static void main(String[] args){
Scanner br=new Scanner(System.in);
String s=br.nextLine();
int []ch=new int [26];
for(int i=0;i<s.length();i++){
ch[s.charAt(i)-97]++;
}
int max=0;
int ii=0;
for(int i=0;i<26;i++){
if(max<ch[i]) {
max=ch[i];
ii=i;
}
}
char chh=(char)(ii+97);
System.out.println(chh);
System.out.println(max);
}
}
H，数字三角形
经典dp，采用逆推，因为告知向左下走的次数与向右下走的次数相差不能超过 1，所以一定落在中位数上最后一位数，所以从n-1层逆推
package train;
import java.util.Scanner;
public class test_19{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int[][] nums = new int[105][105];
int[][] dp = new int[105][105];
for(int i=1; i<=n; i++){
for(int j=1; j<=i; j++){
nums[i][j] = sc.nextInt();
}
}
if(n%2==0){
dp[n][n/2] = nums[n][n/2];
dp[n][n/2+1] = nums[n][n/2+1];
} else {
dp[n][n/2+1] = nums[n][n/2+1];
}
//逆向遍历dp
for(int i=n-1; i>=1; i--){
for(int j=1; j<=i; j++){
//注意边界！
if(dp[i+1][j] != 0 || dp[i+1][j+1] != 0){
dp[i][j] = nums[i][j] + Math.max(dp[i+1][j], dp[i+1][j+1]);//每次填充上一层的数字是逆推的最大和
}
}
}
System.out.println(dp[1][1]);
}
}