大题的类名没写Main，再见了。
文章目录
- 试题 A: 门牌制作
- 试题 B: 寻找 2020
- 试题 C: 蛇形填数
- 试题 D: 七段码
- 试题 E: 排序
- 试题 F: 成绩分析
- 试题 G: 单词分析
- 试题 H: 数字三角形
- 试题 I: 子串分值和
- 试题 J: 装饰珠
试题 A: 门牌制作
思路 ：624
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;
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
- 按边建图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: 成绩分析
思路：
- 注意一下平均分的四舍五入就可以了。
代码:
试题 G: 单词分析
思路：
- 用个HashMap<Character,Integer>计数即可。
代码:
试题 H: 数字三角形
思路：
- 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[i−1][j−1],dp[i−1][j])
- 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: 子串分值和
思路：
- 开26个数组保存每个字母出现的下标
- 然后根据每个字母出现的下标差来计算当前字母对所有区间的答案贡献
- O ( 26 n ) 枚 举 即 可 O(26n)枚举即可 O(26n)枚举即可
试题 J: 装饰珠
思路： 不会
