赛题目录
A.美丽的2（签到）1.原试题2.简要分析3.实现代码4.答案 B.扩散（多源BFS）1.原试题2.简要分析3.实现代码4.答案 C.阶乘约数（数论）1.原试题2.简要分析3.实现代码4.答案 D.本质上升序列（dp）1.原试题2.简要分析3.实现代码4.答案 D.玩具蛇（DFS）1.原试题2.简要分析3.实现代码4.答案 总结A.美丽的2（签到）
1.原试题
2.简要分析
签到题，遍历所有数，将数字转成字符串，判断是否包含2即可。3.实现代码
public class __A {public static void main(String[] args) {int ans = 0;for(int i = 1; i <= ; i++){String s = String.valueOf(i);if(s.contains("2")){//System.out.println(s);ans++;}}System.out.println(ans);}}
4.答案
563
B.扩散（多源BFS）
1.原试题
2.简要分析
多源BFS，需要注意画布是无限大的，负坐标也可能扩散到，需要将初始四个坐标整体往右下角移动。每一层的扩散算一步，总共层BFS，就是扩散了分钟。数量级是1亿，几秒可以跑完。3.实现代码
public class __B {static class Node{int x;int y;public Node(int x, int y) {this.x = x;this.y = y;}}static int[][] grid = new int[10000][10000];static int[][] dist = new int[10000][10000];static int[] dx = {-1,0,1,0};static int[] dy = {0,1,0,-1};public static void main(String[] args) {grid[4000][4000] = 1;grid[6020][4011] = 1;grid[4011][4014] = 1;grid[6000][6000] = 1;bfs();int ans = 0;for(int i = 0; i < 10000; i ++){for(int j = 0; j < 10000; j++){if(grid[i][j] == 1){ans++;}}}System.out.println(ans);}static void bfs(){Queue<Node> q = new LinkedList<>();q.offer(new Node(4000,4000));q.offer(new Node(6020,4011));q.offer(new Node(4011,4014));q.offer(new Node(6000,6000));while(!q.isEmpty()){Node node = q.peek(); q.poll();if(dist[node.x][node.y] == ){return;}for(int i = 0; i < 4; i++){int x = node.x + dx[i];int y = node.y + dy[i];if(grid[x][y] == 1){continue;}grid[x][y] = 1;q.offer(new Node(x,y));dist[x][y] = dist[node.x][node.y] + 1;}}}}
4.答案
20312088
C.阶乘约数（数论）
1.原试题
2.简要分析
是一道数论的题目，需要掌握以下的基础数论知识：（阶乘数定理）
任意一个正整数 X 都可以表示成若干个质数乘积的形式：
X = p 1 a 1 ∗ p 2 a 2 ∗ p 3 a 3 . . . ∗ p k a k X = p_{1}^{a^{1}}*p_{2}^{a^{2}}*p_{3}^{a^{3}}...*p_{k}^{a^{k}} X=p1a1∗p2a2∗p3a3...∗pkakX的约数个数n为：
n = ( a 1 + 1 ) ∗ ( a 2 + 1 ) ∗ ( a 3 + 1 ) . . . ∗ ( a k + 1 ) n = (a_{1} + 1)* (a_{2} + 1)* (a_{3} + 1)...* (a_{k} + 1) n=(a1+1)∗(a2+1)∗(a3+1)...∗(ak+1)
接下来只需要求出1-100中所有的质数，然后将100!用这些质数表示出来，得到每个质数的指数，最后相乘就能得到约数的个数。
需要使用long型存储答案。
3.实现代码
public class __C {static long ans = 1;static int[] t = new int[101];//判断一个数是不是素数static boolean issu(int n){for(int i = 2; i <= Math.sqrt((double)n); i++){if(n % i == 0){return false;}}return true;}//将1-100中所有的素数加入t表中 初始化为1，最后计算约数个数时不需要再加1static void addt(){t[2] = 1;for(int i = 3; i <= 100 ; i++){if(issu(i)){t[i] = 1;}}}public static void main(String[] args) {addt();for(int i = 2; i <= 100; i++){int x = i;//遍历每个质数 用质数将x表示出来for(int j = 2; j<= 100; j++){if(t[j]!=0){while(x % j == 0){x /= j;//质数j的指数加1t[j] ++;}}}}//统计所有质数的指数，得到答案for(int i = 2; i <= 100; i++){if(t[i]!=0){ans*=(t[i]);}}System.out.println(ans);}}
4.答案
39001250856960000
D.本质上升序列（dp）
1.原试题
数据如下：（200个小写字母）
tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl
2.简要分析
递增子序列的计数问题，注意一个字符也算，取字符的位置不同但最后子序列相同也只算一种。设dp[i]表示到以第i个字符结尾的递增子序列的个数。（i >= 0）设0 < j < i，如果c[i] > c[j]，c[j]算入新的递增子序列中，那么dp[i] += dp[j]。如果c[i] == c[j]，c[i]和c[j]的递增子序列数量存在重复部分，那么dp[i] -= dp[j]。如果c[i] < c[j，c[j]对dp[i]没有贡献。3.实现代码
public class __D {static String s = "tocyjkdzcieoiodfpbgcncsrjbhmugdnojjddhllnofawllbhfiadgdcdjstemphmnjihecoapdjjrprrqnhgccevdarufmliqijgihhfgdcmxvicfauachlifhafpdccfseflcdgjncadfclvfmadvrnaaahahndsikzssoywakgnfjjaihtniptwoulxbaeqkqhfwl";static int ans;public static void main(String[] args) {char cs[] = s.toCharArray();int dp[] = new int[200];for(int i = 0; i < 200; i++){dp[i] = 1;}for(int i = 0; i < cs.length; i++){for(int j = 0; j < i; j++){if(cs[i] >cs[j]){dp[i] += dp[j];}if(cs[i] == cs[j]){dp[i] -= dp[j];}}}for(int i = 0; i < dp.length; i++){ans+=dp[i];}System.out.println(ans);}}
4.答案
3616159
D.玩具蛇（DFS）
1.原试题
2.简要分析
经典DFS问题，尝试以每一个格子为1，走出一条路径，最后统计路径总数。注意每次尝试以新的格子为1时，要把方格全部清空。3.实现代码
public class __E {static int[] dx = {-1,0,1,0};static int[] dy = {0,1,0,-1};static int[][] grid = new int[4][4];static int ans;static void init(){for(int i = 0; i < 4; i++){for(int j = 0; j < 4; j++){grid[i][j] = 0;}}}public static void main(String[] args) {for(int i = 0; i < 4; i++){for(int j =0; j < 4; j++){init();grid[i][j] = 1;dfs(i,j,1);}}System.out.println(ans);}static void dfs(int x,int y,int step){for(int i = 0; i < 4; i++){int nx = x + dx[i];int ny = y + dy[i];if(nx > 3 || ny > 3 || nx < 0 || ny < 0 || grid[nx][ny] == 1){continue;}if(step == 15){ans++;}grid[nx][ny] = 1;dfs(nx,ny,step+1);grid[nx][ny] = 0;}}}
4.答案
552
总结
国赛填空题除了第一题签到外，其余的都需要对经典算法熟悉，并且能快速编码。数论的基本知识，DFS，BFS，基础dp，都需要非常熟悉。ATFWUS -05-24
