java

2020第十一屆藍橋杯JavaB組省賽總結

大題的類名沒寫Main,再見了。

如果需要大題的程式碼可以說一聲,有人需要我就寫一下,裸考被這個類名搞到心態崩了。

試題 A: 門牌製作

思路 :624

import .io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
  
public class Main {
    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;
    
    public static void main(String[] args) {
    	
    	for(int i = 1; i <= 2020; i++) {
    		check(i);
    	}
    	
		System.out.println(ans);
	}

	private static void check(int i) {
		while(i > 0) {
			if(i % 10 == 2) ++ans;
			i /= 10;
		}
	}
}

試題 B: 尋找 2020

思路: 16520

程式碼:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
  
public class Main {
    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 char c[][] = new char[M][M];
    
    public static void main(String[] args) {
    	while(cin.hasNext()) {
    		String s = cin.next();
    		m = s.length();
    		c[n++] = s.toCharArray();
    	}
    	for(int i = 0; i < n; i++)
    		for(int j = 0; j < m; j++)
    			if(c[i][j] == '2')
    				check(i, j);
    	
	}

	private static void check(int i, int j) {
		if(i + 3 < n)
			if(c[i+1][j] == '0' && c[i+2][j] == '2' && c[i+3][j] == '0')
				++ans;
		if(j + 3 < m)
			if(c[i][j+1] == '0' && c[i][j+2] == '2' && c[i][j+3] == '0')
				++ans;
		if(i + 3 < n && j + 3 < n)
			if(c[i+1][j+1] == '0' && c[i+2][j+2] == '2' && c[i+3][j+3] == '0')
				++ans;
	}
}

試題 C: 蛇形填數

思路: 761

程式碼:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
  
public class Main {
    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 int c[][] = new int[M][M];
    
    public static void main(String[] args) {
    	check(1, 1, 1, 1);
    	System.out.println(c[20][20]);
	}

	private static void check(int i, int j, int w, int f) {
		c[i][j] = w;
		if(i > 50 || j > 50) return;
		if(i == j && i == 1) check(i, j+1, w+1, -f);
		else if(f == -1) {
			if(j == 1) check(i+1, j, w+1, -f);
			else check(i+1, j-1, w+1, f);
		}
		else if(f == 1) {
			if(i == 1) check(i, j+1, w+1, -f);
			else check(i-1, j+1, w+1, f);
		}
		
	}
}

試題 D: 七段碼

思路: 80

  1. 按邊建圖dfs保證聯通,二進位制列舉判重。

程式碼:

import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
 
  
public class Main {
    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];
    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;
		check(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: 排序

思路: 其實就是逆序數,算一下就可以,但是考試的時候腦子抽了一直dfs。

程式碼:

試題 F: 成績分析

思路:

  1. 注意一下平均分的四捨五入就可以了。

程式碼:

試題 G: 單詞分析

思路:

  1. 用個HashMap<Character,Integer>計數即可。

程式碼:

試題 H: 數字三角形

思路:

  1. d

    p

    [

    i

    ]

    [

    j

    ]

    +

    =

    m

    a

    x

    (

    d

    p

    [

    i

    1

    ]

    [

    j

    1

    ]

    ,

    d

    p

    [

    i

    1

    ]

    [

    j

    ]

    )

    dp[i][j]+=max(dp[i-1][j-1],dp[i-1][j])

    dp[i][j]+=max(dp[i1][j1],dp[i1][j])

  2. n為奇數時答案為

    d

    p

    [

    n

    ]

    [

    (

    n

    +

    1

    )

    /

    2

    ]

    dp[n][(n+1)/2]

    dp[n][(n+1)/2],偶數則是

    m

    a

    x

    (

    d

    p

    [

    n

    ]

    [

    n

    /

    2

    ]

    ,

    d

    p

    [

    n

    ]

    [

    n

    /

    2

    +

    1

    ]

    )

    max(dp[n][n/2],dp[n][n/2+1])

    max(dp[n][n/2],dp[n][n/2+1])

試題 I: 子串分值和

思路:

  1. 開26個數組儲存每個字母出現的下標
  2. 然後根據每個字母出現的下標差來計算當前字母對所有區間的答案貢獻
  3. O

    (

    26

    n

    )

    O(26n)列舉即可

    O(26n)

試題 J: 裝飾珠

思路: 不會

本文章已修改原文用詞符合繁體字使用者習慣使其容易閱讀

版權宣告:此處為CSDN博主「我不會DP」的原創文章,依據CC 4.0 BY-SA版權協議,轉載請附上原文出處連結及本宣告。

原文連結:https://blog.csdn.net/JiangHxin/article/details/109134914