1.P1464 [PacNW 1999] Function

题目描述

对于一个递归函数 w(a,b,c)w(a,b,c)

  • 如果 a≤0a \le 0 或 b≤0b \le 0 或 c≤0c \le 0 就返回值 11。

  • 如果 a>20a>20 或 b>20b>20 或 c>20c>20 就返回 w(20,20,20)w(20,20,20)

  • 如果 a<ba<b 并且 b<cb<c 就返回 w(a,b,c−1)+w(a,b−1,c−1)−w(a,b−1,c)w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)。

  • 其它的情况就返回 w(a−1,b,c)+w(a−1,b−1,c)+w(a−1,b,c−1)−w(a−1,b−1,c−1)w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)

这是个简单的递归函数，但实现起来可能会有些问题。当 a,b,ca,b,c 均为 1515 时，调用的次数将非常的多。你要想个办法才行。

注意：例如 w(30,−1,0)w(30,-1,0) 又满足条件 11 又满足条件 22，请按照最上面的条件来算，答案为 11。

输入格式

会有若干行。

并以 −1,−1,−1-1,-1,-1 结束。

输出格式

输出若干行，每一行格式：

w(a, b, c) = ans

注意空格。

输入输出样例 #1

输入 #1

1
2
3
1 1 1
2 2 2
-1 -1 -1

输出 #1

1
2
w(1, 1, 1) = 2
w(2, 2, 2) = 4

说明/提示

数据规模与约定

保证输入的数在 [−9223372036854775808,9223372036854775807][-9223372036854775808,9223372036854775807] 之间，并且是整数。

保证不包括 −1,−1,−1-1, -1, -1 的输入行数 TT 满足 1≤T≤1051 \leq T \leq 10 ^ 5。

题解

正常递归是超时的，所以要优化。这里可以使用记忆化，就是将已经算过的数据存储到一个数组中，这样下次要用的时候就不用再进行计算。

在这道题目中，如果数据大于20就都会返回w(20,20,20)，所以这个记忆数组只要20就够了。递归函数的具体做法是，先判断是否是小于等于0和大于20 的情况，分别返回。再判断输入的数是否已经存储过了，已经存储则直接返回，否则继续下面的判断。继续判断abc之间的大小情况，并返回，在返回之前还要将这个数据存储进记忆化数组中（因为上面已经判断完既不是大于20的也没有存储过）。

整体流程没有问题，但是还有一些小问题会导致运行错误和超时。

首先是re，因为输入的数据会很大，所以接收的时候要用long来接收，传入函数的时候也要用long，但是因为数组不能是long，所以在函数中存储数据的时候要先将其强转为int。

然后是tle，慢了0.2秒。要用快读和字符串构建。快读用readLine()一次读一行，然后再用split(" ")分隔，最后用a=Long.parseLong(s[0])将字符串转为long。字符串构建在每次循环中把数据加进去，最后三个数字都等于-1的时候再sb.toString()输出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.*;
import java.io.*;

public class Main
    {
        static int[][][] memory=new int[21][21][21];
        public static void main(String[] args) throws Exception
            {
                BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
                StringBuilder sb=new StringBuilder();
                long a=0;
                long b=0;
                long c=0;
                while(true)
                {
                    String line=br.readLine();
                    String[] s=line.split(" ");
                    a=Long.parseLong(s[0]);
                    b=Long.parseLong(s[1]);
                    c=Long.parseLong(s[2]);
                    if(a==-1&&b==-1&&c==-1)
                    {
                        System.out.print(sb.toString());
                        return;
                    }
                    sb.append("w("+a+", "+b+", "+c+") = "+w(a,b,c)+"\n");
                }
            }
        public static int w(long a,long b,long c)
            {
                
                if(a<=0||b<=0||c<=0)
                {
                    return 1;
                }
                if(a>20||b>20||c>20)
                {
                    return w(20,20,20);
                }
                if(memory[(int)a][(int)b][(int)c]!=0)
                {
                    return memory[(int)a][(int)b][(int)c];
                }
                if(a<b&&b<c)
                {
                    memory[(int)a][(int)b][(int)c]=w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c);
                    return memory[(int)a][(int)b][(int)c];
                }
                else
                {
                    memory[(int)a][(int)b][(int)c]=w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1);
                    return memory[(int)a][(int)b][(int)c];
                }
            }
    }

2.B3621 枚举元组

题目描述

nn 元组是指由 nn 个元素组成的序列。例如 (1,1,2)(1,1,2) 是一个三元组、(233,254,277,123)(233,254,277,123) 是一个四元组。

给定 nn 和 kk，请按字典序输出全体 nn 元组，其中元组内的元素是在 [1,k][1, k] 之间的整数。

「字典序」是指：优先按照第一个元素从小到大的顺序，若第一个元素相同，则按第二个元素从小到大……依此类推。详情参考样例数据。

输入格式

仅一行，两个正整数 n,kn, k。

输出格式

若干行，每行表示一个元组。元组内的元素用空格隔开。

输入输出样例 #1

输入 #1

1
2 3

输出 #1

1
2
3
4
5
6
7
8
9
1 1
1 2
1 3
2 1
2 2
2 3
3 1
3 2
3 3

输入输出样例 #2

输入 #2

1
3 3

输出 #2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
1 3 2
1 3 3
2 1 1
2 1 2
2 1 3
2 2 1
2 2 2
2 2 3
2 3 1
2 3 2
2 3 3
3 1 1
3 1 2
3 1 3
3 2 1
3 2 2
3 2 3
3 3 1
3 3 2
3 3 3

说明/提示

对于 100%100\% 的数据，有 n≤5,k≤4n\leq 5, k\leq 4。

题解

数据量不是很大，不知道枚举能不能行。用dfs，就是开一个数组，表示对应位置的数字，给一个位置赋值后就递归其下一个位置，数组存满了就输出

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
import java.util.*;
import java.io.*;
    
public class Main
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String line=br.readLine();
        String[] s=line.split(" ");
        int n=Integer.parseInt(s[0]);
        int k=Integer.parseInt(s[1]);
        StringBuilder sb=new StringBuilder();

        int[] a=new int[n];
        dfs(n,k,sb,0,a);
        System.out.print(sb.toString());
        
    }
    public static void dfs(int n,int k,StringBuilder sb,int index,int[] a)
    {
        if(index==n)
        {
            for(int i=0;i<n;i++)
            {
                sb.append(a[i]+" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=1;i<=k;i++)
        {
            a[index]=i;
            dfs(n,k,sb,index+1,a);
        }
    }
}

3.B3622 枚举子集（递归实现指数型枚举）

题目描述

今有 nn 位同学，可以从中选出任意名同学参加合唱。

请输出所有可能的选择方案。

输入格式

仅一行，一个正整数 nn。

输出格式

若干行，每行表示一个选择方案。

每一种选择方案用一个字符串表示，其中第 ii 位为 Y 则表示第 ii 名同学参加合唱；为 N 则表示不参加。

需要以字典序输出答案。

输入输出样例 #1

输入 #1

1
3

输出 #1

1
2
3
4
5
6
7
8
NNN
NNY
NYN
NYY
YNN
YNY
YYN
YYY

说明/提示

对于 100%100\% 的数据，保证 1≤n≤101\leq n\leq 10。

题解

和上一道题一样，稍微改一下即可，每个位置只有两种选择，所以只需要循环两次

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import java.util.*;
import java.io.*;
    
public class Main
{
    public static void main(String[] args) throws Exception
    {
        Scanner scan=new Scanner(System.in);
        int n=scan.nextInt();
        StringBuilder sb=new StringBuilder();
        
        int[] a=new int[n];
        dfs(n,sb,0,a);
        System.out.print(sb.toString());
        
    }
    public static void dfs(int n,StringBuilder sb,int index,int[] a)
    {
        if(index==n)
        {
            for(int i=0;i<n;i++)
            {
                if(a[i]==1)
                {
                    sb.append("N");
                }
                else
                {
                    sb.append("Y");
                }
                
            }
            sb.append("\n");
            return;
        }
        for(int i=1;i<=2;i++)
        {
            a[index]=i;
            dfs(n,sb,index+1,a);
        }
    }
}

4.B3623 枚举排列（递归实现排列型枚举）

题目描述

今有 nn 名学生，要从中选出 kk 人排成一列拍照。

请按字典序输出所有可能的排列方式。

输入格式

仅一行，两个正整数 n,kn, k。

输出格式

若干行，每行 kk 个正整数，表示一种可能的队伍顺序。

输入输出样例 #1

输入 #1

1
3 2

输出 #1

1
2
3
4
5
6
1 2
1 3
2 1
2 3
3 1
3 2

说明/提示

对于 100%100\% 的数据，1≤k≤n≤101\leq k\leq n \leq 10。

题解

还是类似的问题，但是这里要求的是选取的时候不能有重复。所以开一个哈希表，在循环的时候先判断，当前数字是否已经选取过了，如果是则跳过当前循环，开始下一个循环（这时的index也就是位置是不变的，只是取值增加），如果否则赋值，并且将其添加到哈希表中，然后开始递归，要注意的是在递归完后需要用map.remove(a[index])撤销上面将元素加入哈希表的操作，因为递归结束代表当前这种选择已经结束，开始同一层的不同选择

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;
import java.io.*;
    
public class Main
{
    static HashMap<Integer,Integer> map=new HashMap<>();
    public static void main(String[] args) throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String line=br.readLine();
        String[] s=line.split(" ");
        int n=Integer.parseInt(s[0]);
        int k=Integer.parseInt(s[1]);
        StringBuilder sb=new StringBuilder();

        int[] a=new int[n];
        dfs(n,k,sb,0,a);
        System.out.print(sb.toString());
        
    }
    public static void dfs(int n,int k,StringBuilder sb,int index,int[] a)
    {
        
        if(index==k)
        {
            for(int i=0;i<k;i++)
            {
                sb.append(a[i]+" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=1;i<=n;i++)
        {
            if(map.containsKey(i))
            {
                continue;
            }
            else
            {
                a[index]=i;
                map.put(a[index],index);
            }
            
            dfs(n,k,sb,index+1,a);
            map.remove(a[index]);
        }
    }
}

5.P10448 组合型枚举

题目描述

从 1∼n1 \sim n 这 nn 个整数中随机选出 mm 个，输出所有可能的选择方案。

输入格式

两个整数 n,mn, m ,在同一行用空格隔开。

输出格式

按照从小到大的顺序输出所有方案，每行 11 个。

首先，同一行内的数升序排列，相邻两个数用一个空格隔开。

其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如 1 3 5 7 排在 1 3 6 8 前面）。

输入输出样例 #1

输入 #1

1
5 3

输出 #1

1
2
3
4
5
6
7
8
9
10
1 2 3 
1 2 4 
1 2 5 
1 3 4 
1 3 5 
1 4 5 
2 3 4 
2 3 5 
2 4 5 
3 4 5

说明/提示

对于所有测试数据满足 0≤m≤n0 \le m \le n , $ n+(n-m) \le 25 $。

题解

思路还是差不多，这里要求的是既不能重复还要按照大小顺序来排列，那么就可以把之前用的哈希表去掉了，判断大小顺序的时候把判重的工作也做了，只要不是首位就要判断和前一位的大小关系

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.util.*;
import java.io.*;
    
public class Main
{
    public static void main(String[] args) throws Exception
    {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String line=br.readLine();
        String[] s=line.split(" ");
        int n=Integer.parseInt(s[0]);
        int k=Integer.parseInt(s[1]);
        StringBuilder sb=new StringBuilder();

        int[] a=new int[n];
        dfs(n,k,sb,0,a);
        System.out.print(sb.toString());
        
    }
    public static void dfs(int n,int k,StringBuilder sb,int index,int[] a)
    {
        
        if(index==k)
        {
            for(int i=0;i<k;i++)
            {
                sb.append(a[i]+" ");
            }
            sb.append("\n");
            return;
        }
        for(int i=1;i<=n;i++)
        {
            if(index>0&&i<=a[index-1])
            {
                continue;
            }
            a[index]=i;
            
            dfs(n,k,sb,index+1,a);
        }
    }
}

6.P2089 烤鸡

题目背景

猪猪 Hanke 得到了一只鸡。

题目描述

猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 1010 种配料（芥末、孜然等），每种配料可以放 11 到 33 克，任意烤鸡的美味程度为所有配料质量之和。

现在， Hanke 想要知道，如果给你一个美味程度 nn ，请输出这 1010 种配料的所有搭配方案。

输入格式

一个正整数 nn，表示美味程度。

输出格式

第一行，方案总数。

第二行至结束，1010 个数，表示每种配料所放的质量，按字典序排列。

如果没有符合要求的方法，就只要在第一行输出一个 00。

输入输出样例 #1

输入 #1

1
11

输出 #1

1
2
3
4
5
6
7
8
9
10
11
10
1 1 1 1 1 1 1 1 1 2 
1 1 1 1 1 1 1 1 2 1 
1 1 1 1 1 1 1 2 1 1 
1 1 1 1 1 1 2 1 1 1 
1 1 1 1 1 2 1 1 1 1 
1 1 1 1 2 1 1 1 1 1 
1 1 1 2 1 1 1 1 1 1 
1 1 2 1 1 1 1 1 1 1 
1 2 1 1 1 1 1 1 1 1 
2 1 1 1 1 1 1 1 1 1

说明/提示

对于 100%100\% 的数据，n≤10000n \leq 10000。

题解

还是一样的思路，但是多了一个做累加和的部分，并且作为参数传递。用StringBuilder也可以解决先输出方案数再输出具体方案的顺序问题

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.*;

public class Main
    {
         static int count;
         public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            StringBuilder sb=new StringBuilder();
            int[] a=new int[10];
            int sum=0;

            dfs(n,0,a,sb,sum);
            System.out.println(count);
            System.out.print(sb.toString());
        }

        public static void dfs(int n,int index,int[] a,StringBuilder sb,int sum)
        {
            if(index==10&&sum==n)
            {
                for(int i=0;i<10;i++)
                    {
                        sb.append(a[i]+" ");
                    }
                sb.append("\n");
                count++;
                return;
            }
            if(index==10)
            {
                return;
            }
            for(int i=1;i<=3;i++)
                {
                    a[index]=i;
                    if(sum+i>n)
                    {
                        break;
                    }
                    dfs(n,index+1,a,sb,sum+i);
                }
        }
    }

7.P15435 [蓝桥杯 2025 国 Python B] 免费披萨

题目背景

Python 选手可以尝试使用 PyPy3 提交本题。

题目描述

蓝桥小镇披萨店的老板刚刚烤制了他人生中的第 nn 个披萨！为了庆祝这一重要时刻，他推出了一项名为“幸运订单”的活动，顾客有机会赢取免费披萨。以下是活动的具体规则：

  1. 生成订单编号：每位顾客需要生成一个九位数的订单编号。生成方法如下：首先，将数字 11 到 88 进行任意排列（每个数字正好出现一次），组成一个八位数。然后，在这个八位数的任意位置（可以是开头、结尾或中间）插入一个 11 到 88 的数字，从而得到一个九位数的订单编号。

  2. 计算最大公约数，赢取免费披萨：披萨店老板会计算每位顾客生成的订单编号与 nn 的最大公约数（GCD）。如果某个订单编号与 nn 的最大公约数最大，那么该顾客就有机会赢得免费披萨。注意：订单编号必须严格满足上述生成规则，如果有多个订单编号与 nn 的最大公约数相同且达到最大值，则只有生成数值最小的订单编号的顾客能够获奖。

现在，小蓝也想参加这个活动，并希望赢取免费披萨。请你帮助小蓝找出能够让他赢得免费披萨的订单编号。

输入格式

输入一行包含一个八位的正整数 nn，表示披萨店老板烤制的第 nn 个披萨。

输出格式

输出一行包含一个九位的正整数表示答案，即小蓝能够赢得免费披萨的最小订单编号。

输入输出样例 #1

输入 #1

1
12345678

输出 #1

1
415637826

说明/提示

评测用例规模与约定

对于所有评测用例，107≤n<10810^7 \le n < 10^8。

题解

总共三个部分，先求出八个数字的全排列，再遍历八个位置插入八种数字，最后用gcd进行比较

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.*;

public class Main
    {
        static int[] a=new int[8];
        static boolean[] used=new boolean[9];
        static int n;
        static int maxgcd=0;
        static int ans=Integer.MAX_VALUE;
        
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            n=scan.nextInt();

            dfs(0);
            System.out.print(ans);

        }

        public static int gcd(int a,int b)
        {
            if(b==0)
            {
                return a;
            }
            return gcd(b,a%b);
        }

        public static int build(int p,int x)
        {
            int num=0;
            for(int i=0;i<p;i++)
                {
                    num=num*10+a[i];
                }
            num=num*10+x;
            for(int i=p;i<8;i++)
                {
                    num=num*10+a[i];
                }
            return num;
        }

        public static void dfs(int index)
        {
            if(index==8)
            {
                for(int i=0;i<=8;i++)
                    {
                        for(int j=1;j<=8;j++)
                            {
                                int num=build(i,j);
                                int g=gcd(num,n);
                                if(g>maxgcd)
                                {
                                    maxgcd=g;
                                    ans=num;
                                }
                                else if(g==maxgcd&&num<ans)
                                {
                                    ans=num;
                                }
                            }
                    }
                return;
            }
            for(int i=1;i<=8;i++)
                {
                    if(used[i])
                    {
                         continue;   
                    }
                    a[index]=i;
                    used[i]=true;
                    dfs(index+1);
                    used[i]=false;
                }
        }
    }

8.P6183 [USACO10MAR] The Rock Game S

题目描述

在奶牛回家休息和娱乐之前，Farmer John 希望它们通过玩游戏获得一些智力上的刺激。

游戏板由 nn 个相同的洞组成，这些洞最初都是空的。一头母牛要么用石头盖住一个空的洞，要么揭开一个先前被盖住的洞。游戏状态的定义是所有洞是否被石头覆盖的情况。

游戏的目标是让奶牛到达每个可能的游戏状态一次，最后回到初始状态。

以下是他们其中一次游戏的示例（空的洞用 O 表示，用石头盖住的洞用 X 表示）：

时刻 洞 1 洞 2 洞 3 描述
00 O O O 一开始所有的洞都是空的
11 O O X 盖上洞 3
22 X O X 盖上洞 1
33 X O O 打开洞 3
44 X X O 盖上洞 2
55 O X O 打开洞 1
66 O X X 盖上洞 3
77 X X X 盖上洞 1

现在牛被卡住玩不下去了！他们必须打开一个洞，然而不管他们打开哪个洞，他们都会到达一个他们已经到达过的状态。例如，如果他们从第二个洞中取出岩石，他们将到达他们在时刻 22 已经访问过的状态（X O X）。

下面是一个 3 个孔的有效解决方案：

时间 洞 1 洞 2 洞 3 描述
00 O O O 一开始所有的洞都是空的
11 O X O 盖上洞 2
22 O X X 盖上洞 3
33 O O X 打开洞 2
44 X O X 盖上洞 1
55 X X X 盖上洞 2
66 X X O 打开洞 3
77 X O O 打开洞 2
88 O O O 打开洞 1，恢复到原来的状态

现在，奶牛们厌倦了这个游戏，它们想找你帮忙。

给定 nn，求游戏的有效解决方案序列。如果有多个解决方案，则输出任意一个。

输入格式

仅一行，一个整数 nn。

输出格式

共 2n+12^n+1 行，每行一个长度为 nn 的字符串，其中只包含字符 O 和 X，该行中的第 ii 个字符表示第 ii 个孔在此状态下是被覆盖还是未覆盖，第一行和最后一行必须全部都是 O。

输入输出样例 #1

输入 #1

1
3

输出 #1

1
2
3
4
5
6
7
8
9
OOO
OXO
OXX
OOX
XOX
XXX
XXO
XOO
OOO

说明/提示

样例 1 说明

见题目描述。

数据规模与约定

对于 100%100\% 的数据，有 1≤n≤151\le n\le15。

题解

非常巧的思路orz

如果n=1时，答案为

1
2
3
0

1

再加一个0

如果n=2时，先将n=1时的答案翻转拼接在原答案的后面即

1
2
3
4
5
6
7
0

1

1

0

并且在前一半的答案（原n=1的答案）的后面加上0，后一半（原n=1的翻转）的后面加上1，即

1
2
3
4
5
6
7
00

10

11

01

正好就是n=2时的答案

后面n增大也同理，都是前一个的原答案后面加上翻转，同时前一半加0，后一半加1

其实就是格雷码问题：相邻两个数之间只有一位二进制不同

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
import java.util.*;

public class Main 
{
    public static void main(String[] args) 
    {
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt(); 

        int[][] a=new int[100000][20];
        int num=2;
        a[1][1]=0;
        a[2][1]=1;

        for(int i=2;i<=n;i++)
        {
    		num*=2;
        	for(int j=1;j<=num/2;j++)
            {
    			for(int k=1;k<i;k++)
                    {
                        a[num/2+j][k]=a[num/2-j+1][k];
                    }
    		}
    		for(int j=1;j<=num;j++)
            {
                if(j>num/2)
                {
                    a[j][i]=1;
                }
        		 else 
                {
                    a[j][i]=0;
                }
        	}
        }
    	for(int i=1;i<=num;i++)
        {
    		for(int j=1;j<=n;j++)
                {
                    if(a[i][j]==1)
                    {
                        System.out.print("X");
                    }
                
        		  else
                    {
                    System.out.print("O");
                    }
                }
    		System.out.printf("\n");
    	}
    	for(int i=1;i<=n;i++)
        {
            System.out.print("O");
        }
    }    
}

9.P13886 [蓝桥杯 2023 省 Python A] 分糖果

题目描述

两种糖果分别有 99 个和 1616 个，要全部分给 77 个小朋友，每个小朋友得到的糖果总数最少为 22 个最多为 55 个，问有多少种不同的分法。糖果必须全部分完。

只要有其中一个小朋友在两种方案中分到的糖果不完全相同，这两种方案就算作不同的方案。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只输出这个整数，填写多余的内容将无法得分。

输入输出样例 #1

输入 #1

1

输出 #1

1

题解

构造dfs，分别传入第一堆的个数，第二堆的个数，以及当前为第几个小朋友，并在函数中限制两种糖果相加的个数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;

public class Main
    {
        static int ans=0;
        public static void main(String[] args)
        {
            dfs(9,16,0);
            System.out.print(ans);
        }

        public static void dfs(int a,int b,int index)
        {
            if(a<0||b<0)
            {
                return;
            }
            if(index==7&&a==0&&b==0)
            {
                ans++;
                return;
            }
            for(int i=0;i<=a;i++)
                {
                    for(int j=0;j<=b;j++)
                        {
                            if(i+j>=2&&i+j<=5)
                            {
                                dfs(a-i,b-j,index+1);
                            }
                        }
                }
        }
    }

10.P2404 自然数的拆分问题

题目描述

任何一个大于 11 的自然数 nn，总可以拆分成若干个小于 nn 的自然数之和。现在给你一个自然数 nn，要求你求出 nn 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。

输入格式

输入：待拆分的自然数 nn。

输出格式

输出：若干数的加法式子。

输入输出样例 #1

输入 #1

1
2
7

输出 #1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

说明/提示

数据保证，2≤n≤82\leq n\le 8。

题解

依旧构造dfs，和之前的组合型枚举类似，都是要按字典序输出。函数中每次把n减去一个数作为参数传递，同时需要多跳过一种情况，就是第一个数就是这个数本身的时候，最后输出的时候只需要循环当前位置个数的次数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            StringBuilder sb=new StringBuilder();
            int[] a=new int[8];
            
            dfs(n,sb,a,0);
            System.out.print(sb.toString());
            
        }

        public static void dfs(int n,StringBuilder sb,int[] a,int index)
        {
            if(n<0)
            {
                return;
            }
            if(n==0)
            {
                sb.append(a[0]);
                for(int i=1;i<index;i++)
                    {
                        if(a[i]!=0)
                        {
                            sb.append("+"+a[i]);
                        }
                    }
                sb.append("\n");
                return;
            }

            for(int i=1;i<=n;i++)
                {
                    
                    if(index>0&&i<a[index-1])
                    {
                        continue;
                    }
                    if(index==0&&i==n)
                    {
                        continue;
                    }
                    a[index]=i;
                    dfs(n-i,sb,a,index+1);
                    
                }
            
        }
    }

11.P2386 放苹果

题目描述

把 mm 个同样的苹果放在 nn 个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法。（5,1,15,1,1 和 1,1,51,1,5 是同一种方法）

输入格式

第一行是测试数据的数目 tt，以下每行均包括二个整数 mm 和 nn，以空格分开。

输出格式

对输入的每组数据 mm 和 nn，用一行输出相应的结果。

输入输出样例 #1

输入 #1

1
2
1
7 3

输出 #1

1
8

输入输出样例 #2

输入 #2

1
2
3
4
5
3
3 2
4 3
2 7

输出 #2

1
2
3
4
2
4
2

说明/提示

对于所有数据，保证：1≤m,n≤101\leq m,n\leq 10，0≤t≤200 \leq t \leq 20。

题解

构造一个dfs函数，传入盘子和苹果个数，然后分成空出一个盘子和先每个盘子里放一个苹果两种情况

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int t=scan.nextInt();
            for(int i=0;i<t;i++)
                {
                    int m=scan.nextInt();
                    int n=scan.nextInt();
                    System.out.println(dfs(m,n));
                }
        }

        public static int dfs(int m,int n)
        {
            if(m==0)
            {
                return 1;
            }
            if(n==1)
            {
                return 1;
            }
            if(n>m)
            {
                return dfs(m,m);
            }

            return dfs(m,n-1) + dfs(m-n,n);

        }
    }

12.P6566 [NOI Online #3 入门组] 观星

题目描述

Jimmy 和 Symbol 约好一起看星星，浩瀚的星空可视为一个长为 NN、宽为 MM 的矩阵，矩阵中共有 N×MN\times M 个位置，一个位置可以用坐标 (i,j)(i,j)（1≤i≤N1\le i\le N，1≤j≤M1\le j\le M）来表示。每个位置上可能是空的，也可能有一个星星。

对于一个位置 (i,j)(i,j)，与其相邻的位置有左边、左上、上面、右上、右边、右下、下面、左下 8 个位置。相邻位置上的星星被视为同一个星座，这种关系有传递性，例如若 (1,1),(1,2),(1,3)(1,1),(1,2),(1,3) 三个位置上都有星星，那么这三个星星视为同一个星座。包含的星星数量相同的星座被视为一个星系（一个星系中的星座不一定相邻），星系的大小为星系中包含的所有星星数量。

由于 Symbol 太喜欢星系了，他就想考一考 Jimmy，让 Jimmy 求出星空中有多少个星系，他还想知道，最大的星系有多大。

输入格式

第一行两个整数 N,MN,M 表示矩阵的长宽。

接下来 NN 行每行 MM 个字符，每个字符只可能是.或*。这 NN 行中第 ii 行的第 jj 个字符是*表示位置 (i,j)(i,j) 上有一个星星，否则表示它是空的。

输出格式

仅一行两个整数，用空格分隔开，分别表示星系的数量与最大星系的大小。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
5 7
*......
..**..*
.*...*.
...*...
....*..

输出 #1

1
3 4

输入输出样例 #2

输入 #2

1
2
3
4
5
6
7
8
9
10
11
10 10
**..**.**.
***....*..
*...**.**.
...*..*...
..........
**...**.*.
..*.*....*
..........
***..*.*..
.***..*...

输出 #2

1
4 12

说明/提示

对于 20%20\% 的数据，N,M≤20N,M\le 20，最大星系大小不超过 200。

对于 50%50\% 的数据，N,M≤400N,M\le 400。

对于 70%70\% 的数据，N,M≤1100N,M\le 1100。

对于 100%100\% 的数据，2≤N,M≤15002\le N,M\le 1500，最大星系大小不超过 100000。

题解

和之前的岛屿问题很像。构造出来的dfs要传入获取到的星和是否访问。对于一个点来说，如果越界或不是星星或已经访问过，那么都返回1。排除了上面的情况就是一颗未访问过的星星，就将其标记为已访问，并且对其八个方向进行递归，同时把结果相加返回

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import java.util.*;

public class Main
    {
        static int[] number=new int[100001];
        static int max=0;
        static int count=0;
        static int n=0;
        static int m=0;
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            n=scan.nextInt();
            m=scan.nextInt();
            int[][] star=new int[n][m];
            for(int i=0;i<n;i++)
                {
                    String s=scan.next();
                    for(int j=0;j<m;j++)
                        {
                            if(s.charAt(j)=='.')
                            {
                                star[i][j]=0;
                            }
                            else
                            {
                                star[i][j]=1;
                            }
                        }
                }
            boolean[][] visited=new boolean[n][m];
            for(int i=0;i<n;i++)
                {
                    for(int j=0;j<m;j++)
                        {
                            if(visited[i][j]!=true&&star[i][j]==1)
                            {
                                int size=dfs(star,i,j,visited);
                                number[size]++;
                            }
                        }
                }
            for(int i=1;i<100001;i++)
                {
                    if(number[i]!=0)
                    {
                        count++;
                        max=Math.max(max,i*number[i]);
                    }
                }
            System.out.print(count+" "+max);
                     
        }

        public static int dfs(int[][] star,int i,int j,boolean[][] visited)
        {
            if(i<0||j<0||i>=n||j>=m)
            {
                return 0;
            }
            if(star[i][j]==0)
            {
                return 0;
            }
            if(visited[i][j]==true)
            {
                return 0;
            }

            visited[i][j]=true;

            return 1
            +dfs(star,i-1,j,visited)
            +dfs(star,i+1,j,visited)
            +dfs(star,i,j-1,visited)
            +dfs(star,i,j+1,visited)
            +dfs(star,i-1,j-1,visited)
            +dfs(star,i+1,j+1,visited)
            +dfs(star,i+1,j-1,visited)
            +dfs(star,i-1,j+1,visited);
            
        }
    }

13.P1088 [NOIP 2004 普及组] 火星人

题目描述

人类终于登上了火星的土地并且见到了神秘的火星人。人类和火星人都无法理解对方的语言，但是我们的科学家发明了一种用数字交流的方法。这种交流方法是这样的，首先，火星人把一个非常大的数字告诉人类科学家，科学家破解这个数字的含义后，再把一个很小的数字加到这个大数上面，把结果告诉火星人，作为人类的回答。

火星人用一种非常简单的方式来表示数字――掰手指。火星人只有一只手，但这只手上有成千上万的手指，这些手指排成一列，分别编号为 1,2,3,⋯1,2,3,\cdots。火星人的任意两根手指都能随意交换位置，他们就是通过这方法计数的。

一个火星人用一个人类的手演示了如何用手指计数。如果把五根手指――拇指、食指、中指、无名指和小指分别编号为 1,2,3,41,2,3,4 和 55，当它们按正常顺序排列时，形成了 55 位数 1234512345，当你交换无名指和小指的位置时，会形成 55 位数 1235412354，当你把五个手指的顺序完全颠倒时，会形成 5432154321，在所有能够形成的 120120 个 55 位数中，1234512345 最小，它表示 11；1235412354 第二小，它表示 22；5432154321 最大，它表示 120120。下表展示了只有 33 根手指时能够形成的 66 个 33 位数和它们代表的数字：

三位数 代表的数字
123123 11
132132 22
213213 33
231231 44
312312 55
321321 66

现在你有幸成为了第一个和火星人交流的地球人。一个火星人会让你看他的手指，科学家会告诉你要加上去的很小的数。你的任务是，把火星人用手指表示的数与科学家告诉你的数相加，并根据相加的结果改变火星人手指的排列顺序。输入数据保证这个结果不会超出火星人手指能表示的范围。

输入格式

共三行。
第一行一个正整数 NN，表示火星人手指的数目（1≤N≤100001 \le N \le 10000）。
第二行是一个正整数 MM，表示要加上去的小整数（1≤M≤1001 \le M \le 100）。
下一行是 11 到 NN 这 NN 个整数的一个排列，用空格隔开，表示火星人手指的排列顺序。

输出格式

NN 个整数，表示改变后的火星人手指的排列顺序。每两个相邻的数中间用一个空格分开，不能有多余的空格。

输入输出样例 #1

输入 #1

1
2
3
4
5
3
1 2 3 4 5

输出 #1

1
1 2 4 5 3

说明/提示

对于 30%30\% 的数据，N≤15N \le 15。

对于 60%60\% 的数据，N≤50N \le 50。

对于 100%100\% 的数据，N≤10000N \le 10000。

题解

要求的是给出的数字的下面M个排列，这道题目就是标准的next_permutation算法

要求下一个排列，对于一个数字先从右向左找到一个数字，这个数字要比其右边一个的数字小，然后对于这个数字，找其后面所有数字中比其大的最小数字，然后这两个数字交换。再把最开始找到的数字的位置后面的所有数字按升序排列。对于交换来说，因为要找到a[i]<a[i+1]的位置，那么这个位置后面的所有数字必然是按照降序来排列的，找其后面所有数字中比其大的最小数字就只需要找比他大的数字就是符合要求的。对于升序排列来说，就是用双指针交换，因为原本是降序排序，并且前面的交换中是和比他大的数字进行的交换（仍然保持降序），所以不需要对要交换的数字进行大小关系比较。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int N=scan.nextInt();
            int M=scan.nextInt();

            int[] a=new int[N];
            for(int i=0;i<N;i++)
                {
                    a[i]=scan.nextInt();
                }

            for(int k=0;k<M;k++)
                {
                    for(int i=N-2;i>=0;i--)
                    {
                        if(a[i]<a[i+1])
                        {
                            for(int j=N-1;j>i;j--)
                                {
                                    if(a[j]>a[i])
                                    {
                                        int t=a[i];
                                        a[i]=a[j];
                                        a[j]=t;
                                        break;
                                    }
                                }
                        
                            int l=i+1;
                            int r=N-1;
                            while(l<r)
                                {
                                    int t=a[l];
                                    a[l]=a[r];
                                    a[r]=t;
                                    l++;
                                    r--;
                                }
                            break;
                        }
                    }
                }
            


            for(int num:a)
                {
                    System.out.print(num+" ");
                }
        }
    }

14.B4482 [语言月赛 202601] 数字游戏 II

题目描述

千秋正在玩一种数字游戏，这种数字游戏需要在一个 4×44\times 4 的网格内填数，每个方格内填入一个 1∼41\sim 4 范围内的整数。

游戏胜利当且仅当下面的条件被全部满足：

  • 将网格划分为 44 个 2×22\times 2 的子网格，每个子网格中不存在重复的数

  • 网格的每行不存在重复的数

  • 网格的每列不存在重复的数

千秋已经填好了其中的若干个数，请你完成剩余的数，使得游戏胜利。可能存在多种符合要求的填法，你只需要给出其中一种即可。

输入格式

输入四行，每行四个数，表示网格已经填入的数。

未填入的位置用 00 表示。

保证已经填入的位置均符合游戏胜利的要求。

输出格式

输出 4 行，每行 4 个整数。表示完成后的游戏局面。

输入输出样例 #1

输入 #1

1
2
3
4
3 0 4 1
4 1 2 0
1 0 3 2
2 3 1 0

输出 #1

1
2
3
4
3 2 4 1
4 1 2 3
1 4 3 2
2 3 1 4

说明/提示

用 nn 表示未填的格子数目。

对于 5%5\% 的测试数据，n=1n=1。

对于另外 25%25\% 的测试数据，n=4n=4 且恰好有一行未填。

对于另外 30%30\% 的测试数据，n=7n=7 且恰好有一行一列未填。

对于 100%100\% 的测试数据，1≤n≤161 \le n \le 16，已经填好的数不违反游戏胜利的要求，保证存在符合游戏胜利的解。

题解

这道题就是一个数独的问题，直接使用回溯算法

将接收的棋盘数据和当前位置传入回溯函数。首先要判断当前位置是否已经填了数字，如果已经填了，那么就递归下一个位置，如果没填就循环当前可以填入的元素。对一个元素进行判断，是否在同一行和列出现过，并且在规定的子网格内（2*2的范围）是否出现过（这里先确定是第几个子网格，再循环这个子网格中的每个位置）。判断元素可以填入后给当前位置赋值，然后进行下一个位置的递归。如果下一个位置的列已经越界则开始下一行，如果行已经越界则找到可行解直接返回。如果递归没有成功就撤销当前的选择，继续循环下一个可以填入的数字。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int[][] board=new int[4][4];
            for(int i=0;i<4;i++)
                {
                    for(int j=0;j<4;j++)
                        {
                            board[i][j]=scan.nextInt();
                        }
                }
            if(backtrack(board,0,0))
            {
                for(int i=0;i<4;i++)
                    {
                        for(int j=0;j<3;j++)
                            {
                                System.out.print(board[i][j]+" ");
                            }
                        System.out.println(board[i][3]);
                    }
            }
            
        }

        public static boolean backtrack(int[][] board,int i,int j)
        {
            if(j==4)
            {
                return backtrack(board,i+1,0);
            }

            if(i==4)
            {
                return true;
            }

            if(board[i][j]!=0)
            {
                return backtrack(board,i,j+1);
            }

            for(int k=1;k<=4;k++)
                {
                    if(!isValid(board,i,j,k))
                    {
                        continue;
                    }

                    board[i][j]=k;

                    if(backtrack(board,i,j+1))
                    {
                        return true;
                    }

                    board[i][j]=0;
                }
            return false;
            
        }

        public static boolean isValid(int[][] board,int i,int j,int k)
        {
            for(int n=0;n<4;n++)
                {
                    if(board[n][j]==k)
                    {
                        return false;
                    }

                    if(board[i][n]==k)
                    {
                        return false;
                    }

                    if(board[(i/2)*2+n/2][(j/2)*2+n%2]==k)
                    {
                        return false;
                    }
                }
            return true;
        }
        
    }

15.B3862 图的遍历（简单版）

题目描述

给出 NN 个点，MM 条边的有向图，对于每个点 vv，求 A(v)A(v) 表示从点 vv 出发，能到达的编号最大的点。

输入格式

第 11 行 22 个整数 N,MN,M，表示点数和边数。

接下来 MM 行，每行 22 个整数 Ui,ViU_i,V_i，表示边 (Ui,Vi)(U_i,V_i)。点用 1,2,…,N1,2,\dots,N 编号。

输出格式

一行 NN 个整数 A(1),A(2),…,A(N)A(1),A(2),\dots,A(N)。

输入输出样例 #1

输入 #1

1
2
3
4
4 3
1 2
2 4
4 3

输出 #1

1
4 4 3 4

说明/提示

  • 对于 100%100\% 的数据，1≤N,M≤1031 \leq N,M \leq 10^3。

题解

这道题用dfs。构造dfs函数，传入接收的数据和当前节点，以及是否访问。用邻接表将数据存入，用graph[n].add(m)将m节点存入到对应可以连接的n节点。在dfs函数中，先判断当前节点是否已经访问过，如果未访问则访问。同时如果当前节点大于记录的最大值则更新最大值，然后开始递归当前节点的邻接表中的元素即连接的节点。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
import java.util.*;

public class Main
    {
        static int max=0;
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int N=scan.nextInt();
            int M=scan.nextInt();
            
            List<Integer>[] graph=new ArrayList[N+1];
            for(int i=1;i<=N;i++)
                {
                    graph[i]=new ArrayList<>();
                }

            for(int i=0;i<M;i++)
                {
                    int n=scan.nextInt();
                    int m=scan.nextInt();
                    graph[n].add(m);
                }

            for(int i=1;i<N;i++)
                {
                    boolean[] visited=new boolean[N+1];
                    max=0;
                    dfs(graph,i,visited);
                    System.out.print(max+" ");
                }
            boolean[] visited=new boolean[N+1];
            dfs(graph,N,visited);
            System.out.print(max);
            
        }

        public static void dfs(List<Integer>[] graph,int n,boolean[] visited)
        {
            if(visited[n])
            {
                return;
            }

            visited[n]=true;

            if(n>max)
            {
                max=n;
            }

            for(int next:graph[n])
                {
                    dfs(graph,next,visited);
                }
        }
    }

16.P4961 小埋与扫雷

题目背景

小埋总是在家中打游戏，一天，她突然想玩Windows自带的扫雷，在一旁的哥哥看见了，想起了自己小时候信息课在机房玩扫雷的日子，便兴致勃勃地开始教小埋扫雷。然而，小埋还是不明白 3bv\mathrm{3bv}（Bechtel’s Board Benchmark Value，每局将所有非雷的方块点开所需最少左键点击数，参见扫雷网的教程 ）怎么算，于是她找到了你。

题目描述

小埋会告诉你一盘扫雷，用一个 n×mn\times m 的矩阵表示，11 是雷 ，00 不是雷，请你告诉她这盘扫雷的 3bv\mathrm{3bv} 。

周围八格没有“雷”且自身不是“雷”的方格称为“空格”，周围八格有“雷”且自身不是“雷”的方格称为“数字”，由“空格”组成的八连通块称为一个“空”。$\mathrm{3bv}=\ 周围八格没有“空格”的“数字”个数周围八格没有“空格”的“数字”个数+$“空"的个数。

如果看不懂上面的计算方式，可以看题目背景中给出的教程，或者看下面的样例解释。

注：八连通

输入格式

第一行有两个整数 nn 和 mm，代表这盘扫雷是一个 n×mn \times m 的矩阵。

后面的 nn 行每行有 mm 个整数，表示这个矩阵，每个数字为 00 或 11，11 代表是雷，00 代表不是雷。

输出格式

一个整数，代表这盘扫雷的 3bv\mathrm{3bv} 。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
8
9
8 8
0 0 0 1 1 0 0 0 
1 0 0 1 0 0 0 1 
1 0 0 1 0 0 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 1 0 0 
0 0 0 0 0 0 0 0 
0 0 0 0 0 0 0 0 
0 1 0 0 0 0 0 0

输出 #1

1
13

说明/提示

1≤n, m≤10001\le n,\ m\le 1000

样例解释

题解

还是和岛屿问题很像，这里的岛屿就变成了题目中的“空”，“空格”就是陆地

首先把空格全部找出来，把这些位置存到新的数组empty中，然后对这个数组进行岛屿问题的dfs，对于一个陆地也就是“空格”，将其访问并对其八个方向进行递归。这是对题目中“空"的个数的统计。然后对于周围八格没有“空格”的“数字”个数，首先“数字”是原棋盘中除了数字部分和empty数组中统计出的“空格“的位置以外的地方，这些都是”数字“，再对这些数字做判断，判断其八个方向上是否有”空格“（这里的判断还是在empty中判断，所以不能和之前的岛屿问题一样直接把陆地淹没，而是标记为已访问）

写完发现只有一个点re了，居然是栈爆了。。。只能改成手动栈了orz，我辛苦写的dfs啊TAT

原本的递归dfs用的是系统调用栈，空间比较小，深度太大导致StackOverflowError栈爆了

但是自己写Deque<int[]> stack用的是堆内存的数据结构，这个空间就比较大了，不容易爆

stack.push(new int[]{i, j});把坐标存进去。int[] cur = stack.pop();从栈中取出一个坐标，并进行一次dfs。stack.push(new int[]{nx, ny});把八个方向上的坐标压进栈

逻辑都是一样，一个是系统来存，一个是自己来存

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
import java.util.*;

public class Main
    {
        static int[] dx={0,0,1,-1,1,1,-1,-1};
        static int[] dy={1,-1,0,0,1,-1,1,-1};
        static int n=0;
        static int m=0;
        static int emptynum=0;
        static int numbercount=0;
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            n=scan.nextInt();
            m=scan.nextInt();

            int[][] board=new int[n][m];
            for(int i=0;i<n;i++)
                {
                    for(int j=0;j<m;j++)
                        {
                            board[i][j]=scan.nextInt();
                        }
                }
            
            int[][] empty=new int[n][m];
            
            for(int i=0;i<n;i++)
                {
                    rowloop:
                    for(int j=0;j<m;j++)
                        {
                            if(board[i][j]==1)
                            {
                                continue;
                            }
                            for(int k=0;k<8;k++)
                                {
                                    int nx=i+dx[k];
                                    int ny=j+dy[k];
                                    if(nx<0||nx>=n||ny<0||ny>=m)
                                    {
                                        continue;
                                    }
                                    if(board[nx][ny]==1)
                                    {
                                        continue rowloop;
                                    }
                                    
                                }
                                empty[i][j]=1;
                        }
                }

            boolean[][] visited=new boolean[n][m];
            for(int i=0;i<n;i++)
                {
                    for(int j=0;j<m;j++)
                        {
                            if(empty[i][j] != 0 && !visited[i][j])
                            {
                                emptynum++;

                                Deque<int[]> stack = new ArrayDeque<>();
                                stack.push(new int[]{i, j});
                                visited[i][j] = true;

                                while(!stack.isEmpty())
                                {
                                    int[] cur = stack.pop();
                                    int x = cur[0];
                                    int y = cur[1];

                                    for(int k = 0; k < 8; k++)
                                    {
                                        int nx = x + dx[k];
                                        int ny = y + dy[k];

                                        if(nx < 0 || nx >= n || ny < 0 || ny >= m)
                                        {
                                            continue;
                                        }

                                        if(empty[nx][ny] == 0 || visited[nx][ny])
                                        {
                                            continue;
                                        }

                                        visited[nx][ny] = true;
                                        stack.push(new int[]{nx, ny});
                                    }
                                }
                            }
                        }
                }

            for(int i=0;i<n;i++)
                {
                    rowloop:
                    for(int j=0;j<m;j++)
                        {
                            if(empty[i][j]==0&&board[i][j]==0)
                            {
                                for(int k=0;k<8;k++)
                                    {
                                        int nx=i+dx[k];
                                        int ny=j+dy[k];
                                        if(nx<0||nx>=n||ny<0||ny>=m)
                                        {
                                            continue;
                                        }
                                        if(empty[nx][ny]==1)
                                        {
                                            continue rowloop;
                                        }
                                    }
                                numbercount++;
                            }
                        }
                }

            System.out.print(numbercount+emptynum);

            
        }

    /*
        public static void dfs(int[][] empty,int i,int j,boolean[][] visited)
        {
            if(empty[i][j]==0||visited[i][j])
            {
                return;
            }

            visited[i][j]=true;
            for(int k=0;k<8;k++)
                {
                    int nx=i+dx[k];
                    int ny=j+dy[k];
                    if(nx<0||nx>=n||ny<0||ny>=m)
                    {
                        continue;
                    }
                    dfs(empty,nx,ny,visited);    
                }
        }
        */
    }

17.P1149 [NOIP 2008 提高组] 火柴棒等式

题目描述

给你 nn 根火柴棍，你可以拼出多少个形如 A+B=CA+B=C 的等式？等式中的 AA、BB、CC 是用火柴棍拼出的整数（若该数非零，则最高位不能是 00）。用火柴棍拼数字 0∼90\sim9 的拼法如图所示：

注意：

  1. 加号与等号各自需要两根火柴棍；

  2. 如果 A≠BA\neq B，则 A+B=CA+B=C 与 B+A=CB+A=C 视为不同的等式（A,B,C≥0A,B,C\geq0）；

  3. nn 根火柴棍必须全部用上。

输入格式

一个整数 n(1≤n≤24)n(1 \leq n\leq 24)。

输出格式

一个整数，能拼成的不同等式的数目。

输入输出样例 #1

输入 #1

1
14

输出 #1

1
2

输入输出样例 #2

输入 #2

1
18

输出 #2

1
9

说明/提示

【输入输出样例 1 解释】

22 个等式为 0+1=10+1=1 和 1+0=11+0=1。

【输入输出样例 2 解释】

99 个等式为

0+4=40+4=4、0+11=110+11=11、1+10=111+10=11、2+2=42+2=4、2+7=92+7=9、4+0=44+0=4、7+2=97+2=9、10+1=1110+1=11、11+0=1111+0=11。

题解

好像不用dfs，就存粹暴力，估计个大概的最大值，然后循环。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;

public class Main
    {

        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int n=scan.nextInt();
            int[] sticks={6,2,5,5,4,5,6,3,7,6};
            int[] cost=new int[2000];
            for(int i=0;i<2000;i++)
                {
                    if(i==0)
                    {
                        cost[i]=6;
                    }
                    int t=i;
                    while(t!=0)
                        {
                            cost[i]=cost[i]+sticks[t%10];
                            t=t/10;
                        }
                }
            int ans=0;
            for(int i=0;i<1000;i++)
                {
                    for(int j=0;j<1000;j++)
                        {
                            int k=i+j;
                            if(cost[i]+cost[j]+cost[k]==n-4)
                            {
                                ans++;
                            }
                        }
                }
            System.out.print(ans);
        }

    }

18.P8801 [蓝桥杯 2022 国 B] 最大数字

题目描述

给定一个正整数 NN。你可以对 NN 的任意一位数字执行任意次以下 2 种操作:

  1. 将该位数字加 11。如果该位数字已经是 99，加 11 之后变成 00。

  2. 将该位数字减 11。如果该位数字已经是 00，减 11 之后变成 99。

你现在总共可以执行 11 号操作不超过 AA 次，22 号操作不超过 BB 次。

请问你最大可以将 NN 变成多少?

输入格式

第一行包含 3 个整数：NN，AA，BB 。

输出格式

一个整数代表答案。

输入输出样例 #1

输入 #1

1
123 1 2

输出 #1

1
933

说明/提示

【样例说明】

对百位数字执行 22 次 22 号操作，对十位数字执行 11 次 11 号操作。

【评测用例规模与约定】

对于 30%30 \% 的数据，1≤N≤100;0≤A,B≤101 \leq N \leq 100 ; 0 \leq A, B \leq 10

对于 100%100 \% 的数据, 1≤N≤1017;0≤A,B≤1001 \leq N \leq 10^{17} ; 0 \leq A, B \leq 100

题解

用的记忆化搜索，也就是数位dp。

对于dfs函数，循环当前位置的数字可以变成的数字，如果符合条件，也就是还有操作次数可以操作成循环到的数字，则开始递归下一位数字并且次数减少。最终记录最值并且返回最值。

这道题中因为N大于0，所以最大值不可能是0，记忆化数组的默认值是0就不用改了，如果是其他题目可以修改为-1，或者加一个visited数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
import java.util.*;

public class Main
    {
        static long[][][] memory;
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            long N=scan.nextLong();
            String s=String.valueOf(N);
            int len=s.length();
            int[] a=new int[len];
            for(int i=0;i<len;i++)
                {
                    a[i]=s.charAt(i)-'0';
                }
            memory=new long[len+1][101][101];
            int A=scan.nextInt();
            int B=scan.nextInt();

            long[] p = new long[len];
            p[len - 1] = 1;
            for (int i = len - 2; i >= 0; i--) 
            {
                p[i] = p[i + 1] * 10;
            }

            System.out.print(dfs(0,A,B,len,a,p));
            
        }

        public static long dfs(int pos,int A,int B,int len,int[] a,long[] p)
        {
            if(pos>=len)
            {
                return 0;
            }
            if(memory[pos][A][B]!=0)
            {
                return memory[pos][A][B];
            }

            long ans=0;
            int d=a[pos];

            for(int i=9;i>=0;i--)
                {
                    int inc=(i-d+10)%10;
                    int dec=(d-i+10)%10;

                    if(inc<=A)
                    {
                        long next=dfs(pos+1,A-inc,B,len,a,p);
                        ans=Math.max(ans,i*p[pos]+next);
                    }

                    if(dec<=B)
                    {
                        long next=dfs(pos+1,A,B-dec,len,a,p);
                        ans=Math.max(ans,i*p[pos]+next);
                    }
                    
                }

            memory[pos][A][B]=ans;
            return ans;
            
        }

        
    }

19.P12139 [蓝桥杯 2025 省 A] 黑白棋

题目描述

小蓝最近迷上了一款名为“黑白棋填充”的游戏。该游戏在一个方形网格棋盘上进行，其中部分格子已经填有黑色或白色的棋子，而其他格子为空，等待玩家填入棋子。

游戏规则是，玩家需要按照以下规则填满整个棋盘，才能算作胜利：

  1. 黑白棋子数量均等：
    在每一行和每一列中，黑色棋子和白色棋子的数量必须相等。

  2. 相邻棋子限制：
    在棋盘的任何一行或一列中，不能有超过两个相同颜色的棋子连续排列（即不允许出现“黑黑黑”或“白白白”的情况）。

  3. 行列唯一性：
    每一行的棋子排列方式必须是唯一的，不能与棋盘中的任何其他行完全相同。
    每一列的棋子排列方式必须是唯一的，不能与棋盘中的任何其他列完全相同。
    行与列之间的棋子排列不作比较，即行可以与列相同，无需满足行列间的唯一性。

现在有一个 6×66 \times 6 的棋盘，如上图所示，其中部分格子已填入棋子（黑色或白色），其余格子需要你填充，题目保证有唯一解。

请给出唯一的正确解，并按照以下格式输出答案：

  • 黑色棋子用 11 表示，白色棋子用 00 表示。

  • 从左到右、从上到下的顺序，依次遍历棋盘上的所有格子，并将这些值拼接成一个长度为 3636 的字符串。

例如，假设最终填充完成后的棋盘如下（仅为示例，并非真实答案）：

1
2
3
4
5
6
1 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 1 0 0 0
0 0 1 1 0 0
0 0 1 1 1 1

则输出结果应为：100000000000000000001000001100001111。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要编写一个程序输出这个整数，输出多余的内容将无法得分。

题解

可以直接推理

1
2
3
4
5
6
1 0 x 0 x x
x x x 0 x x
x x x x 0 0
x x x x x x
x x 1 x x 1
x 0 x x 1 x

首先因为不能三个相连，所以（3，6）和（4，4）必是1

1
2
3
4
5
6
1 0 1 0 x x
x x x 0 x x
x x x 1 0 0
x x x x x x
x x 1 x x 1
x 0 x x 1 x

因为不能三个相连所以（1，4）必然是1，这样这一行的剩下两个才不会都是1而导致相连，则同理确定（1，5）是0

1
2
3
4
5
6
1 0 1 0 x x
0 x x 0 x x
1 x x 1 0 0
x x x x x x
x x 1 x x 1
x 0 x x 1 x

再同理得（1，1）是1，则（6，1）必然不能为1，应为0。（4，1）同样必须为1，则（3，1）为0

1
2
3
4
5
6
1 0 1 0 x x
0 x x 0 x x
1 x x 1 0 0
x x x x x x
x x 1 x x 1
1 0 0 1 1 0

第一列的1都已经填完，所以剩下两个位置都应该为0。若（2，2）为0，则其上三个都为1，所以只能为1，同理（2，5）也只能为0，则第二行剩余两个也可填出。填出后（4，3）也可填出为1

1
2
3
4
5
6
1 0 1 0 x x
0 1 x 0 x x
1 x x 1 0 0
0 x x 1 x x
0 1 1 0 0 1
1 0 0 1 1 0

（3，5）只能为0，否则剩余两个位置会和（4，5）形成三个0相连，则这一行剩余两个为1

1
2
3
4
5
6
1 0 1 0 x x
0 1 0 0 1 1
1 x x 1 0 0
0 x x 1 x x
0 1 1 0 0 1
1 0 0 1 1 0

（5，3）只能为1，可以将最后两列剩余空格都填出

1
2
3
4
5
6
1 0 1 0 0 1
0 1 0 0 1 1
1 x x 1 0 0
0 x x 1 1 0
0 1 1 0 0 1
1 0 0 1 1 0

最后将剩余四个空填出

1
2
3
4
5
6
1 0 1 0 0 1
0 1 0 0 1 1
1 0 1 1 0 0
0 1 0 1 1 0
0 1 1 0 0 1
1 0 0 1 1 0

dfs也能做，就是尝试撤销。

代码

1
2
3
4
5
6
7
8
9
10
import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            System.out.print("101001010011101100010110011001100110");
        }
    }

20.P12266 [蓝桥杯 2024 国 Python B] 不同的总分值

题目描述

在今年蓝桥杯的决赛中，一共有 1010 道题目，每道题目的分数依次为 55 分，55 分，1010 分，1010 分，1515 分，1515 分，2020 分，2020 分，2525 分，2525 分。

假设某位参赛选手在解答每一道题时，要么能得到该题的全部分数，要么就得 00 分。那么请问，这位参赛选手在完成这 1010 道题之后，所能获得的总分值存在多少种不同的情况？

注意，总分值仅需关注选手 1010 道题的总得分，而无需关注具体是由哪些题获得了相应的分数。例如，选手第一道题获得 55 分其余题均为 00 分，与第二道题获得 55 分其余题均为 00 分，应视为同一种情况。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要编写一个程序输出这个整数，输出多余的内容将无法得分。

题解

观察每道题的分值5,5,10,10,15,15,20,20,25,25，其实就是5×(1,1,2,2,3,3,4,4,5,5)，也就是对于1-5这五个数字，每个数字可以任选0-2次。那么最大就是全选就是2(1+2+3+4+5)=30，并且从0到30每个数都可以凑出，所以共有31种。

用dfs也能做，对每一道题做选择，传入一个参数表示当前选到第几个数字了，再传入一个参数表示当前总分用于累加，再用哈希表来去重。

代码

1
2
3
4
5
6
7
8
9
import java.util.*;

public class Main
    {
        public static void main(String[] args)
        {
            System.out.print(31);
        }
    }

21.P10386 [蓝桥杯 2024 省 A] 五子棋对弈

题目描述

“在五子棋的对弈中，友谊的小船说翻就翻？” 不！对小蓝和小桥来说，五子棋不仅是棋盘上的较量，更是心与心之间的沟通。这两位挚友秉承着 “友谊第一，比赛第二” 的宗旨，决定在一块 5×55 × 5 的棋盘上，用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落，于是决定用一场和棋（平局） 作为彼此友谊的见证。比赛遵循以下规则：

  1. 棋盘规模：比赛在一个 5×55 × 5 的方格棋盘上进行，共有 2525 个格子供下棋使用。

  2. 棋子类型：两种棋子，黑棋与白棋，代表双方。小蓝持白棋，小桥持黑棋。

  3. 先手规则：白棋（小蓝）具有先手优势，即在棋盘空白时率先落子（下棋）。

  4. 轮流落子：玩家们交替在棋盘上放置各自的棋子，每次仅放置一枚。

  5. 胜利条件：率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。

  6. 平局条件：当所有 2525 个棋盘格都被下满棋子，而未决出胜负时，游戏以平局告终。

在这一设定下，小蓝和小桥想知道，有多少种不同的棋局情况（终局不同看成不同情况，终局相同而落子顺序不同看成同一种情况），既确保棋盘下满又保证比赛结果为平局。

输入格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

输出格式

这是一道结果填空题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。

题解

dfs剪枝，dfs函数中传入当前位置和当前白子和黑子的个数。同时再加一个函数用于判断当放下这个子的时候会不会导致这一行或列或斜线上有五个相同的棋子相连，从而进行剪枝

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
import java.util.*;

public class Main
    {
        static int[][] board=new int[5][5];
        static int ans=0;
        public static void main(String[] args)
        {
            dfs(0,0,0);
            System.out.print(ans);
            
        }

        public static void dfs(int index,int white,int black)
        {   
            if(white>13||black>12)
            {
                return;
            }

            if(white+25-index<13||black+25-index<12)
            {
                return;
            }

            if(index==25)
            {
                if(white==13&&black==12)
                {
                    ans++;
                }
                return;
            }

            int row=index/5;
            int column=index%5;
            board[row][column]=1;
            if(!win(row,column))
            {
                dfs(index+1,white+1,black);
            }
            
            board[row][column]=2;
            if(!win(row,column))
            {
                dfs(index+1,white,black+1);
            }
            
            board[row][column]=0;
        
        }


        public static boolean win(int row,int column)
        {
            if(board[row][0]!=0&&
               board[row][0]==board[row][1]&&
               board[row][1]==board[row][2]&&
               board[row][2]==board[row][3]&&
               board[row][3]==board[row][4])
            {
                return true;
            }

            if(board[0][column]!=0&&
               board[0][column]==board[1][column]&&
               board[1][column]==board[2][column]&&
               board[2][column]==board[3][column]&&
               board[3][column]==board[4][column])
            {
                return true;
            }

            if(row==column)
            {
                if(board[0][0]!=0&&
                   board[0][0]==board[1][1]&&
                   board[1][1]==board[2][2]&&
                   board[2][2]==board[3][3]&&
                   board[3][3]==board[4][4])
                {
                    return true;
                }
            }

            if(row+column==4)
            {
                if(board[0][4]!=0&&
                   board[0][4]==board[1][3]&&
                   board[1][3]==board[2][2]&&
                   board[2][2]==board[3][1]&&
                   board[3][1]==board[4][0])
                {
                    return true;
                }
            }

            return false;

        }
    }

22.P12253 [蓝桥杯 2024 国 Java B] 宝塔

题目描述

小蓝最近迷上了宝塔游戏，这是一款迷宫填数游戏，玩家需要按照规则将高度为 11 至 NN 的宝塔放置在一个 N×NN \times N 大小的水平放置的棋盘当中，每个宝塔占据棋盘的一个方格。具体规则如下：

  1. 宝塔的高度只有 1,2,…,N1, 2, \ldots, N。

  2. 每一行、每一列中不可以出现相同高度的宝塔。

  3. 棋盘周围的箭头中的数字表示从这个位置看向棋盘时可以看到的宝塔个数。

下图 1 是一个棋盘以及答案以供参考。图 2 是你需要解决的问题，你需要输出 2525 个数字表示答案，按照棋盘布局从左至右、从上至下的顺序输出即可。例如对于图 1 对应的棋盘而言，输出的答案是：14324321214332141432432121433214。题目保证答案只有一个。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只需要编写一个程序输出这个整数，输出多余的内容将无法得分。

题解

依旧类似于数独游戏，还是dfs先按照数独规则做出来，然后做一个可视约束的剪枝函数。一个是行的剪枝，一个是列的剪枝，行的剪枝在每次列到达最后一列后执行，判断这一行。列的剪枝在整个棋盘都完成之后再执行，检查所有列。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
import java.util.*;

public class Main
    {
        static int[][] board=new int[5][5];
        static int[] left={2,2,3,2,1};
        static int[] right={3,3,1,2,4};
        static int[] up={2,2,1,3,3};
        static int[] down={1,4,2,2,3};
        public static void main(String[] args)
        {
            if(dfs(0,0))
            {
                for(int i=0;i<5;i++)
                    {
                        for(int j=0;j<5;j++)
                            {
                                System.out.print(board[i][j]);
                            }
                    }
                
            }
        }


        public static boolean dfs(int i,int j)
        {
            if(j==5)
            {
                if(checkrow(i))
                {
                    return dfs(i+1,0);
                }
                return false;
            }

            if(i==5)
            {
                if(checkcolumn())
                {
                    return true;
                }
                return false;
            }

            if(board[i][j]!=0)
            {
                return dfs(i,j+1);
            }

            for(int k=1;k<=5;k++)
                {
                    if(!isvalid(k,i,j))
                    {
                        continue;
                    }
                    
                    board[i][j]=k;

                    if(dfs(i,j+1))
                    {
                        return true;
                    }

                    board[i][j]=0;
                }
            return false;

        }

        public static boolean isvalid(int k,int i,int j)
        {
            for(int q=0;q<5;q++)
                {
                    if(board[i][q]==k)
                    {
                        return false;
                    }

                    if(board[q][j]==k)
                    {
                        return false;
                    }
                }
            return true;
        }

        public static boolean checkrow(int i)
        {
            int max=0;
            int cnt=0;

            for(int j=0;j<5;j++)
                {
                    if(board[i][j]>max)
                    {
                        max=board[i][j];
                        cnt++;
                    }
                }
            if(cnt!=left[i])
            {
                return false;
            }

            max=0;
            cnt=0;

            for(int j=4;j>=0;j--)
                {
                    if(board[i][j]>max)
                    {
                        max=board[i][j];
                        cnt++;
                    }
                }
            if(cnt!=right[i])
            {
                return false;
            }

            return true;
            
        }


        public static boolean checkcolumn()
        {
            for(int j=0;j<5;j++)
                {
                    int max=0;
                    int cnt=0;
                    for(int i=0;i<5;i++)
                        {
                            if(board[i][j]>max)
                            {
                                max=board[i][j];
                                cnt++;
                            }
                        }
                    if(cnt!=up[j])
                    {
                        return false;
                    }

                    max=0;
                    cnt=0;

                    for(int i=4;i>=0;i--)
                        {
                            if(board[i][j]>max)
                            {
                                max=board[i][j];
                                cnt++;
                            }
                        }
                    if(cnt!=down[j])
                    {
                        return false;
                    }
                }
            return true;
        }
    }

23.P10578 [蓝桥杯 2024 国 A] 旋转九宫格

题目描述

给定一个 3×33\times 3 的九宫格，每个格子内分别含有一个数字，每个格子里的数字互不相同。每步我们可以选择任意一个 2×22\times 2 的区域将其顺时针旋转，例如：

例如

1
2
3
1 2 3
4 5 6
7 8 9

将其旋转右上角，可得：

1
2
3
1 5 2
4 6 3
7 8 9

问最少需要几步才能将给定的状态旋转为

1
2
3
1 2 3
4 5 6
7 8 9

输入格式

输入的第一行包含一个整数 TT 表示询问的组数。

接下来依次输入每组询问。

每组询问包含三行，每行包含三个数，表示询问的九宫格的状态。

输出格式

输出 TT 行，每行包含一个整数表示本次询问的答案。

输入输出样例 #1

输入 #1

1
2
3
4
5
6
7
2
1 2 3
4 5 6
7 8 9
1 5 2
4 6 3
7 8 9

输出 #1

1
2
0
3

说明/提示

对于 60%60\% 的评测用例，T=1T=1;

对于所有评测用例，T≤105T\le 10^5。

题解

用bfs来做。先将已完成的状态作为起始反过来找当前状态，判断队列中不空，就取出来，并且对其进行四种旋转，如果旋转后的不在哈希表中就将其放入并且放入队列中。对所有情况做预处理后再根据输入的情况直接取出。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import java.util.*;

public class Main
    {
        static HashMap<String,Integer> map=new HashMap<>();
        public static void main(String[] args)
        {
            Scanner scan=new Scanner(System.in);
            int T=scan.nextInt();
            

            bfs();
            for(int k=0;k<T;k++)
                {
                    StringBuilder sb=new StringBuilder();
                    for(int i=0;i<9;i++)
                        {
                            sb.append(scan.nextInt());
                        }
                    String end=sb.toString();
                    System.out.println(map.get(end));
                }
        }

        public static void bfs()
        {
            Queue<String> q=new ArrayDeque<>();
            String start="123456789";
            q.offer(start);
            map.put(start,0);

            while(!q.isEmpty())
                {
                    String cur=q.poll();
                    int step=map.get(cur);

                    String n1 = rotate(cur, 0, 1, 3, 4); 
                    String n2 = rotate(cur, 1, 2, 4, 5); 
                    String n3 = rotate(cur, 3, 4, 6, 7); 
                    String n4 = rotate(cur, 4, 5, 7, 8);

                    if (!map.containsKey(n1)) 
                    {
                        map.put(n1, step + 1);
                        q.offer(n1);
                    }
                    if (!map.containsKey(n2)) 
                    {
                        map.put(n2, step + 1);
                        q.offer(n2);
                    }
                    if (!map.containsKey(n3))
                    {
                        map.put(n3, step + 1);
                        q.offer(n3);
                    }
                    if (!map.containsKey(n4)) 
                    {
                        map.put(n4, step + 1);
                        q.offer(n4);
                    }
                }

            
            
        }

        public static String rotate(String cur,int a,int b,int c,int d)
        {
            char[] s=cur.toCharArray();
            char t=s[a];
            s[a]=s[b];
            s[b]=s[d];
            s[d]=s[c];
            s[c]=t;

            return new String(s);
        }
        
    }

24.P13877 [蓝桥杯 2023 省 Java A] 与或异或

题目描述

小蓝有一张门电路的逻辑图，如下图所示：

:::align{center}

图中每个三角形代表着一种门电路，可能是与门、或门、异或门中的任何一种，它接受上一层中的两个圆形中的数据作为输入，产生一个输出值输出到下一级（如图中箭头所示）。图中圆形表示的是暂存的输出结果，取值只可能是 0 或 1，为了便于表示我们用 arr[i][j]arr[i][j] 表示第 ii（0≤i≤40 \leq i \leq 4）行第 jj（0≤j≤i0 \leq j \leq i）个圆形的值。其中 arr[0]=(In[0],In[1],In[2],In[3],In[4])arr[0] = (In[0], In[1], In[2], In[3], In[4]) 表示的是输入数据，对于某个 arr[i][j]arr[i][j]（i≤0i \leq 0），计算方式为 arr[i][j]=arr[i−1][j] op arr[i−1][j+1]arr[i][j] = arr[i-1][j] \ op \ arr[i-1][j+1]，其中 opop 表示的是将 arr[i−1][j]arr[i-1][j]、arr[i−1][j+1]arr[i-1][j+1] 作为输入，将 arr[i][j]arr[i][j] 作为输出的那个门电路, 与门、或门、异或门分别对应于按位与 (&)(\&)、按位或 (∣)(|)、按位异或 (^) 运算符。

现在已知输入为 In[0]=1,In[1]=0,In[2]=1,In[3]=0,In[4]=1In[0] = 1, In[1] = 0, In[2] = 1, In[3] = 0, In[4] = 1，小蓝想要使得最终的输出 OutOut 的值为 1，请问一共有多少种不同的门电路组合方式？其中上图中显示的就是一种合法的方式。

输入格式

无

输出格式

这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只输出这个整数，填写多余的内容将无法得分。

题解

一共就十个门，直接枚举都行。用dfs就是每次做出选择后递归

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;

public class Main
    {
        static int[][] arr=new int[5][5];
        static int ans=0;
        public static void main(String[] args)
        {
            arr[0][0] = 1;
            arr[0][1] = 0;
            arr[0][2] = 1;
            arr[0][3] = 0;
            arr[0][4] = 1;

            dfs(1,0);
            System.out.print(ans);
        }

        public static void dfs(int i,int j)
        {
            if(i==5)
            {
                if(arr[4][0]==1)
                {
                    ans++;
                }
                return;
            }

            if(j==5-i)
            {
                dfs(i+1,0);
                return;
            }

            int a=arr[i-1][j];
            int b=arr[i-1][j+1];

            arr[i][j]=a&b;
            dfs(i,j+1);

            arr[i][j]=a|b;
            dfs(i,j+1);

            arr[i][j]=a^b;
            dfs(i,j+1);
            
        }
    }