文章目录

• Day13
• • 第一题
  • • 第七届2016年蓝桥杯国赛
    • 一步之遥
  • 第二题
  • • 第十二届2021年蓝桥杯省赛
    • 回路计数
  • 第三题
  • • 第八届2017年蓝桥杯省赛
    • 方格分割

Day13

第一题

第七届2016年蓝桥杯国赛

一步之遥

C++C组第1题

填空题

签到题，非常简单的数学问题。

public class Main {public static void main(String[] args) {for (int i = 1; i < 9999; i++) {for (int j = 1; j < 9999; j++) {if (i * 97 - j * 127 == 1) { // 想到这个等式即可System.out.println(i + j);return;}}}}}

第二题

第十二届2021年蓝桥杯省赛

回路计数

C++A组第5题

填空题

状态压缩dp

不是很会…给大家贴代码了

public class Main {    static boolean[][] v = new boolean[25][25];    static long[][] dp = new long[1 << 21][25];    public static void main(String[] args) { long res = 0; // 存边 注意下标 for (int i = 1; i <= 21; i++) {     for (int j = 1; j <= 21; j++) {  if (gcd(i, j) == 1)      v[i - 1][j - 1] = v[j - 1][i - 1] = true;  else      v[i - 1][j - 1] = v[j - 1][i - 1] = false;     } } dp[1][0] = 1; for(int i = 1; i < (1 << 21); i++){     for(int j = 0; j < 21; j++){  // 如果当前状态中不存在楼j 跳过  if((i >> j & 1) == 0) continue;  // 寻找从楼j能够到达的下一栋楼  for(int k = 0; k < 21; k++){      // 楼k已经访问或者j到k无边 跳过      if((i >> k & 1) == 1 || !v[j][k]) continue;      dp[i + (1 << k)][k] += dp[i][j];  }     } } // 将以i为结尾点的回路求和 for(int i = 0; i < 21; i++) res += dp[(1 << 21) - 1][i]; System.out.println(res);    }    private static int gcd(int a, int b){ return b != 0 ? gcd(b, a % b) : a;    }}

在oj平台提交结果还得用大整数提交…

import java.math.BigInteger;public class Main {    public static void main(String[] args) { BigInteger b = new BigInteger("881012367360"); System.out.println(b);    }}

第三题

第八届2017年蓝桥杯省赛

方格分割

JavaA组第4题

填空题

其实是一道对称图案的dfs搜索方案数问题。

public class Main {static int[][] st = new int[7][7];static int ans;public static void main(String[] args) {dfs(3, 3); // 从中点开始搜System.out.println(ans / 4); // 去重}private static void dfs(int sx, int sy) {if (sx == 0 || sy == 0 || sx == 6 || sy == 6) { // 剪到边界 说明找到一种方案ans++;return;}st[sx][sy] = 1;st[6 - sx][6 - sy] = 1;int[] dx = {-1, 0, 1, 0}, dy = {0, -1, 0, 1};for (int i = 0; i < 4; i++) {int x = sx + dx[i], y = sy + dy[i];if (x < 0 || x > 6 || y < 0 || y > 6) continue; // 越界if (st[x][y] == 0) {dfs(x, y);}}// 回溯st[sx][sy] = 0;st[6 - sx][6 - sy] = 0;}}

参考视频：2017年第八届蓝桥杯 - 省赛 - C/C++大学A组 - D. 方格分割