【不重要的前言】
去年參賽前還是信心滿滿的。第一次參賽沒什麼經驗，七段碼和排序這兩道填空題卡太久了，導緻後面大題會做的沒有拿下。
怎麼說呢，還是自己水準不夠。隻拿了省二。應該就對了前三道填空題和後面兩道大題。
今年重新報名Java B組，希望經過一年的學習能圓當初的遺憾，盡力寫吧。
第十一屆2020年JavaB組原題
提取碼：g8d6
2020年JavaB組真題
- 試題 A：門牌制作
- 試題 B: 尋找 2020
- 試題 C： 蛇形填數
- 試題 D：七段碼
- 試題 E：排序
- 試題 F：成績分析
- 試題 G：單詞分析
- 試題 H： 數字三角形
- 試題 I：子串分值和
試題 A：門牌制作
【思路】
數的分解
package 第十一屆;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月1日 下午8:28:46
* 答案：624
*/
public class _A門牌制作 {
static int getCnt(int num) {
int ans = 0;
while( num > 0) {
if( num % 10 == 2) ans++;
num /=10;
}
return ans;
}
public static void main(String[] args) {
int res = 0; //624
for(int i = 1; i <= 2020; i ++)
res += getCnt(i);
System.out.println(res);
//System.out.println(getCnt(3));
}
}
試題 B: 尋找 2020
【題目描述】
【思路】
有三種走法，往下走四個格子，對角（從左上到右下）走四個格子,往上走四個格子。 dfs将每種格子的可能走法枚舉，同時統計能走出2020的路徑的方案數。
答案：16520
package 第十一屆;
import java.util.Scanner;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月1日 下午8:51:23
*/
public class _B尋找2020 {
static int N = 310;
static char f[][] = new char[N][N];
//右 右下 下 左下
static int dir[][] = { {0, 1}, {1, 1}, {1, 0}};
static int ans = 0;
static int n, m;
public static void dfs(int x, int y, int step, int d, int res) {
if( step == 4) {
if( res == 2020) ans ++;
return;
}
int a = x + dir[d][0], b = y + dir[d][1];
if( a >= 0 && a < m && b >= 0 && b < n)
dfs(a, b, step + 1, d, res * 10 + (f[a][b] - '0') );
}
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
n = reader.nextInt();
m = reader.nextInt();
for(int i = 0; i < n; i ++) {
String string = reader.next();
for(int j = 0; j < m; j ++)
f[i][j]= string.charAt(j);
}
for(int d = 0; d < 3; d ++) {
for(int i = 0; i < n; i ++) {
for(int j = 0; j < m; j ++)
dfs(i, j, 1, d, f[i][j] - '0');
}
}
System.out.println(ans);
}
}
試題 C： 蛇形填數
【題目描述】
【思路】
發現規律，橫縱坐标之和為定值，且該定值為在該條對角線的數字個數-1。對角線數字的個數為1、2、 3、 4、 5、 6……
編号（從0開始）為奇數的對角線，自右上向左下。編号為偶數的對角線，自左下向右上。
package 第十一屆;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月1日 下午9:28:49
*/
public class _C蛇形填數 {
static int N = 50;
static int f[][] = new int[N][N];
public static void main(String[] args) {
int num = 1;
int k = 0; //橫縱坐标和為k
while( num <= 1000) {
if( (k & 1) == 1) { //編号為奇數的對角線: x坐标從0開始
for(int x = 0; x <= k; x ++)
f[x][k - x] = num ++;
}else {//編号為偶數的對角線：x坐标從k開始
for(int x = k; x >= 0; x --)
f[x][k - x] = num ++;
}
//下一條對角線
k ++;
}
System.out.print(f[19][19] + "\t");
/*
for(int i = 0; i < N; i ++) {
for(int j = 0; j < N; j ++)
System.out.print(f[i][j] + "\t");
System.out.println();
}*/
}
}
實際上就這題而言也不用每個都求出。寫出蛇形矩陣的一部分，會發現規律：
| (行号，列号) | 值 |
|---|---|
| (1,1) | 1 |
| (2,2) | 5 |
| (3,3) | 13 |
| (4,4) | 25 |
| (5,5) | 41 |
| (6,6) | 61 |
| (i,i) | 每隔一項，差4 * (i - 1) ( i = 1 、2、3……i - 1) |
| (n,n) | 1 + (1 + (n - 1))*(n - 1) *4 /2 |
代入求得761
試題 D：七段碼
【題目描述】
【思路】
圖
使用鄰接連結清單存儲每條邊的關系，如
q[a]：b、f
q[b]：a、c 、g、
q[c]：b、d、g
q[d]：c、e
q[e]：d、f、g
q[f]：a、e、g
q[g]：b、c、f、e
然後從1到7枚舉組成數字的段數，分别以每一個字母開頭取枚舉，
原先以為重複計算的隻有反轉後相同的排列，是以用了下面的方法：
//去掉翻轉之後相同的數字串
Set<String> ans = new CopyOnWriteArraySet<>();
for(String s: set) {
if( s.length() == 1) {//一個字元 反轉之後必定有本身
ans.add(s);
continue;
}
//{ab, ba} {ab,}
StringBuffer sb = new StringBuffer(s);//ab ba
String ns = sb.reverse().toString();//ba ab
if( ans.contains(ns)) continue;//其逆序已經存在則跳過不統計該數字
ans.add(s);
}
for(String s: ans) {
System.out.println(s);
}
//a 的ASCII碼值為97
System.out.println(ans.size());
後來才發現不止：dcge、edcg也是重複的一種。
想到要是每一種方案都能按照升序拍好，那就就好統計了。
package 第十一屆;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Scanner;
import java.util.Set;
import java.util.concurrent.CopyOnWriteArraySet;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月1日 下午10:20:51
* 類說明
*/
/*
錄入資料：
a b
a f
b a
b c
b g
c b
c d
c g
d c
d e
e d
e f
e g
f a
f e
f g
g b
g c
g f
g e
0
答案：
abceg
de
def
beg
deg
abcef
bceg
cefg
abfg
abcdfg
bcdefg
ab
ef
abefg
eg
bfg
af
cde
cdg
abcfg
adef
bcdg
bcde
defg
abeg
abef
bcdeg
abdefg
abdef
bc
fg
bcd
aef
ceg
bg
bcg
cdefg
cdfg
bcdfg
abcefg
abcdf
a
cd
b
c
abc
afg
d
cg
abf
e
cfg
f
g
abg
efg
abcde
abcg
abcf
befg
bcfg
cdef
cdeg
abcd
abcdef
abcdeg
abcdefg
答案：67
*/
public class _D七段碼 {
//初始化為N個空的ArrayList, 表示每一個q[i]都為空
static int N = 7;
static List<Character> [] q = new ArrayList[N];
static boolean st[] = new boolean[N]; //每一段隻允許被使用一次
static Set<String> set = new CopyOnWriteArraySet<>();
public static void dfs(int father,int son, int cnt, String s) {
//System.out.println(son + " "+cnt + " "+s);
if( cnt == 1) {
set.add(s);
return;
}
st[son] = true;
for(Character c: q[son]) {//枚舉son的鄰接邊
int next = c - 'a';
if( !st[next] && next != father) {
String ns = Character.toString(c);
dfs(son, c - 'a', cnt - 1, s + ns);
}
}
}
public static void main(String[] args) {
for(int i = 0; i < N; i ++)
q[i] = new ArrayList<Character>();
Scanner reader = new Scanner(System.in);
while(true) {
String s[] = reader.nextLine().split(" ");
if( s[0].equals("0") ) break;
char x = s[0].charAt(0), y = s[1].charAt(0);
q[ x - 'a'].add(y);
}
for(int i = 1; i <= 7; i ++) {//枚舉段數
for(int start = 0; start < 7; start ++) {//以哪個字母開頭
Arrays.fill(st,false);
char c = (char) ('a' + start);
String s = Character.toString(c);
dfs(- 1, start, i, s);
}
}
Set<String> ans = new HashSet<>();
for(String s: set) {
char c[] = s.toCharArray();
Arrays.sort(c);
//c.toString() 得到的是位址
String nString = new String(c);
if( !ans.contains(nString)) ans.add(nString);
}
for(String s: ans)
System.out.println(s);
System.out.print(ans.size());
}
}
看了一些其他大佬的答案 好像自己算錯了 ，别人答案是：80
代碼源自 江先生的故事 2020第十一屆藍橋杯JavaB組省賽總結
package 第十一屆;
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月4日 下午5:40:55
* 類說明
*/
public class _D七段碼2 {
static int N = 100000 * 4 + 5;
static int M = 1000 + 5;
static int mod = 1000000009;
static Scanner cin = new Scanner(System.in);
static int ans = 0, n, m;
static ArrayList<Integer> g[] = new ArrayList[N]; //建圖 第i個數組的元素都跟i相連
static boolean vis[] = new boolean[N]; //判斷目前這條線段是否被遞歸過
static boolean dp[] = new boolean[N]; //二進制判重
static int a[] = new int[1<<8];
public static void main(String[] args) {
for(int i = 1; i <= 7; i++)
g[i] = new ArrayList<Integer>();
//這裡就是賦予數字意義 重新連邊
add(1, 2); add(1, 6); add(2, 7); add(2, 3); add(3, 4);
add(4, 5); add(5, 6); add(5, 7); add(6, 7); add(3, 7);
for(int i = 1; i <= 7; i++) {
vis[i] = true; //這裡枚舉是保證至少有一條燈管是亮着的
dfs(i , 1);
vis[i] = false;
}
System.out.println(ans);
}
//建立聯通塊的同時
private static void dfs(int u, int k) {
a[k] = u; //遞歸的第k條線段是數字編号為u的線段
check(k); //對每個狀态都判重
//這裡從1枚舉到k就是枚舉目前聯通塊相連的邊
for(int i = 1; i <= k; i++) {
for(int v: g[a[i]]) {
if(vis[v]) continue;
vis[v] = true;
dfs(v, k + 1);
vis[v] = false;
}
}
}
private static void check(int k) {
int res = 0;
for(int i = 1; i <= k; i++) {//因為每個線段的數字不同 代表的二進制數字也就不同
res += (1<<a[i]);
}
if(dp[res]) return;
dp[res] = true;
ans++;
}
private static void add(int i, int j) {
g[i].add(j); g[j].add(i);
}
}
試題 E：排序
【題目描述】
【思路】
容易發現，相同交換次數，完全逆序時，所需的字元串最少。又要求字典序最小，是以最左端應該是越靠近a越好。理想字元串形如 ： ……edcba。 假設完全逆序，最少需要字元串為x個，則交換次數為：(1 + x - 1)*(x - 1) / 2 >= 100,解得x >=15。14個字元完全逆序交換次數為98,15個字元完全逆序交換次數為105。是以字元長度至少是15。這樣一來就得到了枚舉的字元串長度。onmlkjihgfedcba的交換次數為105，想到隻要有一個字元少交換5次，其他字元相對順序不變，而實際上這樣是不可能做到的，因為少交換意味着要在原來逆序的位置上往右移動，這樣一來其他字元的相對順序也就發生了改變。
但換種思路，我隻要5個字元，每個字元都少移動1次，其他字元相對正确位置不發生改變即可。這樣也就是原逆序字元串左邊的第6個字元j往左移動5位即可 。即：jonmlkihgfedcba。 然後代入程式檢驗。
package 第十一屆;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月2日 下午12:02:40
*/
public class _E排序 {
public static void bubble_sort(char [] c) {
/*
* 雙指針一左（j）一右（i）
* 如果c[j] > c[j + 1]，則交換i、j所指元素且i ++、 j ++
* 否則
*
*/
int n = c.length;
int cnt = 0; //交換次數
for(int i = 0; i < n - 1; i ++) {
for( int j = 0; j < n - 1 - i; j ++) {
if( c[j] > c[j + 1]) {
char tmp = c[j + 1];
c[j + 1] = c[j];
c[j] = tmp;
cnt ++;
}
}
}
System.out.println(new String(c));
System.out.println(cnt);
}
public static void main(String[] args) {
//abcdefghijklmno
char c[] = "jonmlkihgfedcba".toCharArray();
//char c[] = "onmlkjihgfedcba".toCharArray();
bubble_sort(c);
}
}
試題 F：成績分析
【題目描述】
【思路】
白給題
String.format("%.2f", ans )保留小數，注意sum為int類型，做除法的時候要強轉避免精度丢失。
package 第十一屆;
import java.util.Scanner;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月3日 下午4:40:51
*/
public class _F成績分析 {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
int n = reader.nextInt();
int f [] = new int[n];
int min = 100, max = 0;
for(int i = 0; i < n; i ++)
f[i] = reader.nextInt();
int sum = 0;
for(int i = 0; i < n; i ++) {
if( f[i] > max) max = f[i];
if( f[i] < min) min = f[i];
sum += f[i];
}
System.out.println(max);
System.out.println(min);
double ans = sum / (double) n;
System.out.printf(String.format("%.2f", ans ));
/*
double t = 71.29571428571429 ;
System.out.printf(String.format("%.2f\n", t));//71.30
double s = 71.23471428571429 ;
System.out.printf(String.format("%.2f\n", s ));//71.23
*/
}
}
試題 G：單詞分析
【題目描述】
【思路】
白給題 開個數組統計就可了
package 第十一屆;
import java.util.Scanner;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月3日 下午4:58:20
*/
public class _G單詞分析 {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
String s = reader.next();
char c [] = s.toCharArray();
int cnt[] = new int[26];
int n = c.length;
for(int i = 0; i < n; i ++)
cnt[ c[i] - 'a'] ++;
int index = 0;
for(int i = 1; i < 26; i ++)
if(cnt[i] > cnt[index] ) index = i;
char ch =(char) (index + 'a');
System.out.println( ch);
System.out.println( cnt[index]);
}//nlanga
}
試題 H： 數字三角形
【題目描述】
【思路】
就是要求在向左下和向右下的步數之差不超過1的情況下，求走過的路徑的最大值。
是以隻要dfs搜尋一遍，在葉子結點的時候判斷從該路徑過來的左右步數之差以及更新路徑最大值。
有搜尋的方向是向下的是以不用擔心走回頭路的問題，是以不用标記數組。且不會越界。
package 第十一屆;
import java.util.Scanner;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月3日 下午5:14:28
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
*/
public class _H數字三角形 {
static int N = 110;
static int f[][] = new int[N][N];
//下、 右下
static int dir[][] ={{1, 0}, {1, 1}};
static int ans = 0, n;
/**
*
* @param x
* @param y
* @param sum 目前路徑和
* @param left 走左邊的次數
* @param right 走右邊的次數
*/
static void dfs(int x, int y, int sum, int left, int right) {
if(x == n - 1) {
if( Math.abs( left - right) <= 1) {
if( sum > ans) ans = sum;
}
return;
}
for(int i = 0; i < 2; i++) {
int a = x + dir[i][0], b = y + dir[i][1];
dfs(a, b, sum + f[a][b], left + (i == 0? 1:0), right + (i == 1? 1:0));
}
}
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
n = reader.nextInt();
for(int i = 0; i < n; i ++)
for(int j = 0; j <= i; j ++)
f[i][j] = reader.nextInt();
dfs(0, 0, f[0][0], 0, 0);
System.out.println(ans);
}
}
試題 I：子串分值和
【思路】
直接做法是求出所有子串，需要O(n^2)時間複雜度，然後統計每個子串的分值需要O(n)的複雜度，總時間複雜度為O( n ^3)。這樣隻能過掉n<=100的資料。
但思考了一下，其實統計子串分值的過程可以不用，隻需使用HashSet統計[i,j]區間的不同字元個數。
package 第十一屆;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
* @author JohnnyLin
* @version Creation Time：2021年4月3日 下午5:54:04
*/
public class _I子串分值和 {
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
String s = reader.next();
char c[] = s.toCharArray();
int n = s.length();
int ans = 0; //統計分值
for(int i = 0; i < n; i ++) {
Set<Character> sub = new HashSet<>();
for(int j = i; j < n; j ++) {
sub.add(c[j]);
ans += sub.size();
}
}
System.out.println(ans);
}
}
算法時間複雜度為O(n^2),隻能AC 60%的資料。
要想全部資料AC，算法時間複雜度需要O(n*logn)以内。