1.九宫幻方

image.png
输入：

0 7 2 0 5 0 0 3 0

输出：

6 7 2 1 5 9 8 3 4

1.1思路分析

  • dfs暴力枚举（此方法超时，原因是：用dfs求9个数的全排列需要的时间复杂度太大）

题目要求我们列举出满足要求的九宫幻方，那么我们就用dfs求出所有可能的九宫，再添加条件：横竖斜所有数字加起来都满足相等的条件，把这些满足的九宫幻方放入一个集合中，最后我们枚举集合中的每一个幻方排列，和输入的数进行比较，如果当前数为0，则continue，如果当前数与枚举数相同，则continue；直到当前数不为零，且与枚举数也不相等时，说明这个枚举的幻方与给定的幻方不匹配，那么我们继续枚举下一个幻方。

1.2代码

  1. import java.util.LinkedList;
  2. import java.util.List;
  3. import java.util.Scanner;
  5. public class Main {
  6.     static boolean[] vis = new boolean[10];
  7.     static List<List<Integer>> res = new LinkedList<>();
  8.     static List<Integer> list=new LinkedList<>();
  9.     //static List<List<Integer>> ans=new LinkedList<>();
  10.     public static void main(String[] args) {
  11.         int[] arr=new int[9];
  12.         int count=0;
  13.         boolean flag=true;
  14.         Scanner sc=new Scanner(System.in);
  15.         for(int i=0;i<arr.length;i++){
  16.             arr[i]=sc.nextInt();
  17.         }
  18.         int index=0;
  20.         dfs(1);
  21.         for(List<Integer> list1:res){
  22.             flag=true;
  23.             for(int i=0;i<list1.size();i++){
  24.                 if(arr[i]==0) continue;
  25.                 if(arr[i]==list1.get(i))continue;
  26.                 if(arr[i]!=0&&arr[i]!=list1.get(i)){
  27.                     flag=false;
  28.                 }
  29.             }
  30.             if(flag){
  31.                 index=res.indexOf(list1);
  32.                 count++;
  33.             }
  34.         }
  35.         if(count==1){
  36.             System.out.println(res.get(index).get(0)+" "+res.get(index).get(1)+" "+res.get(index).get(2));
  37.             System.out.println(res.get(index).get(3)+" "+res.get(index).get(4)+" "+res.get(index).get(5));
  38.             System.out.println(res.get(index).get(6)+" "+res.get(index).get(7)+" "+res.get(index).get(8));
  39.         }else if(count>1){
  40.             System.out.println("Too Many");
  41.         }
  42.     }
  44.     public static void dfs(int n) {
  45.         if (list.size()==9) {
  46.             if(ismatch(list)) {
  47.                 res.add(new LinkedList<>(list));
  48.             }
  49.             return;
  50.         }
  52.         for (int i = 1; i < 10; i++) {
  53.             if (vis[i]) {
  54.                 continue;
  55.             }
  56.             vis[i] = true;
  57.             list.add(i);
  58.             dfs(n + 1);
  59.             list.remove(list.size()-1);
  60.             vis[i] = false;
  62.         }
  63.     }
  65.     public static boolean ismatch(List<Integer> list){
  66.         return list.get(0)+list.get(1)+list.get(2)==15&&
  67.                 list.get(3)+list.get(4)+list.get(5)==15&&
  68.                 list.get(6)+list.get(7)+list.get(8)==15&&
  69.                 list.get(0)+list.get(4)+list.get(8)==15&&
  70.                 list.get(2)+list.get(4)+list.get(6)==15&&
  71.                 list.get(0)+list.get(3)+list.get(6)==15&&
  72.                 list.get(1)+list.get(4)+list.get(7)==15&&
  73.                 list.get(2)+list.get(5)+list.get(8)==15;
  74.     }
  75. }

2.拉马车

image.png
image.png

2.1思路分析

很典型的模拟题，数据结构题目中已经给我们暗示了，为了正确的将重复字符与其之间的字符放入各牌组的末尾，我们可以用一个栈来保存已经出过了牌，如果在栈中遇到了重复的元素，那么依次弹出栈并加入各牌组末尾即可，如果没有重复元素，那么直接入栈，并由另一个牌组出牌。
题主在此题踩了大坑，清楚是模拟，但是摸不清一种情况：一个牌组连续摸到相同牌。导致逻辑混乱处理不清，200分钟只能堪堪过一个测试用例（真是菜狗啊）。

2.2代码

  1. import java.util.LinkedList;
  2. import java.util.Queue;
  3. import java.util.Scanner;
  4. import java.util.Stack;
  5. public class Main008_拉马车 {
  6.      public static void main(String[] args) {
  7.         Scanner in = new Scanner(System.in);
  8.       String a = in.nextLine();
  9.       String b = in.nextLine();
  10.       int len = a.length()+b.length();
  11.       Queue<Character> queue1 = new LinkedList<Character>();
  12.       Queue<Character> queue2 = new LinkedList<Character>();
  13.       Stack<Character> stack = new Stack<Character>();
  14.       // 字符串中字符的入队操作
  15.       for(int i=0;i<a.length();i++) 
  16.           queue1.offer(a.charAt(i));
  17.       for(int i=0;i<b.length();i++) 
  18.           queue2.offer(b.charAt(i));
  19.       Boolean Awin = true; // 初始和A赢牌时A先出牌
  20.       int count = 0 ;  // 计数双方一共出牌多少次，当count过大时返回 -1
  21.       while(!queue1.isEmpty() && !queue2.isEmpty()) {
  22.           count++;
  23.           if(count==10000)  break; // 当达到10000次，说明存在死循环，即跳出循环，返回-1
  24.           if(Awin==true) {  //初始和A赢牌时A先出牌
  25.               if(stack.contains(queue1.peek())) { //判断栈中是否包含队首元素
  26.                    Awin = true;  //包含，则A局部获胜，Awin=true；
  27.                    char t = queue1.poll(); // 记录队首元素，并出队
  28.                   queue1.offer(t);   // 将元素添加至队尾
  29.                   while(stack.peek()!=t)  // 将两个相同元素之间的栈中的元素添加至队尾
  30.                      queue1.offer(stack.pop());
  31.                   queue1.offer(stack.pop()); //将栈中和队首相同的元素添加中队尾
  32.               }else {
  33.                    stack.push(queue1.poll()); //栈中不包含队首元素
  34.                    Awin = false;   // Awin=false; 下次B出牌
  35.               }
  36.           // 注释同上
  37.          }else {
  38.              if(stack.contains(queue2.peek())) {
  39.                   Awin = false;   // stack中存在元素和B出牌的元素相同时，则B收牌，下次B先出牌
  40.                  char t = queue2.poll();
  41.                  queue2.offer(t);
  42.                  while(stack.peek()!=t) {
  43.                    queue2.offer(stack.pop());
  44.                   }
  45.                   queue2.offer(stack.pop());
  46.              }else {
  47.                   stack.push(queue2.poll());
  48.                   Awin = true;
  49.              }
  50.           }
  51.        }
  52.        StringBuffer sb = new StringBuffer();
  53.        if(queue2.isEmpty()) {
  54.           int size = queue1.size();
  55.           for(int i=0;i<size;i++) // queue.size()；每出队一次变化一次，so应提前记录
  56.                sb.append(queue1.poll());
  57.            System.out.println(sb.toString());
  58.         }else if(queue1.isEmpty()) {
  59.            int size = queue2.size();
  60.            for(int i=0;i<size;i++)
  61.             sb.append(queue2.poll());
  62.            System.out.println(sb.toString());
  63.       }else if(count==10000) // 循环10000次内，未分胜负，则认为死循环，输出-1
  64.            System.out.println(-1);
  65.     }
  66. }

3.K倍区间

image.png
输入：

5 2 1 2 3 4 5

输出

6

3.1思路分析

  • 最容易想到的是暴力解法，两个指针，每次移动就计算依次区间和，满足K倍区间的要求，那么count++。
  • 暴力解法很明显，面对1e5的数据，很容易超时，因此我们需要一个优化技巧来降低时间复杂度，这个就是前缀和，根据第八届蓝桥杯省赛（C组） - 图5构建前缀和数组，那么时间复杂度将降到O（n2）

3.2代码

  • 暴力 ```java import java.util.LinkedList; import java.util.List; import java.util.Scanner;

public class Main4 { //暴力法

  1. public static void main(String[] args) {
  2.     List<Integer> list=new LinkedList<>();
  3.     Scanner sc=new Scanner(System.in);
  4.     int N=sc.nextInt();
  5.     int K=sc.nextInt();
  6.     int ans=0;
  7.     sc.nextLine();
  8.     for(int i=0;i<N;i++){
  9.         list.add(sc.nextInt());
  10.     }
  11.     for(int i=0;i<list.size();i++){
  12.         for(int j=i;j< list.size();j++){
  13.             if(sum(list,i,j)%K==0){
  14.                 ans++;
  15.             }
  16.         }
  17.     }
  18.     System.out.println(ans);
  19. }
  21. public static int sum(List<Integer> list,int i,int j){
  22.     int sum=0;
  23.     for(;i<=j;i++){
  24.         sum+=list.get(i);
  25.     }
  26.     return sum;
  27. }

}

  2. - 构建前缀和数组
  3. ```java
  4. public class Main4 {        //前缀和
  5.     public static void main(String[] args) {
  6.         List<Integer> list = new LinkedList<>();
  7.         Scanner sc = new Scanner(System.in);
  8.         int N = sc.nextInt();
  9.         int K = sc.nextInt();
  10.         int[] arr=new int[N];
  11.         int[] next=new int[N+1];
  12.         next[0]=0;
  13.         int sum=0;
  14.         sc.nextLine();
  15.         int ans = 0;
  16.         for (int i = 0; i < N; i++) {
  17.             arr[i]=sc.nextInt();
  18.         }
  19.         for(int i=1;i<next.length;i++){
  20.             sum+=arr[i-1];
  21.             next[i]=sum;
  22.             //System.out.println(next[i]);
  23.         }
  24.         for(int i=0;i<next.length;i++){
  25.             for(int j=i+1;j<next.length;j++){
  26.                 if((next[j]-next[i])%K==0){
  27.                     ans++;
  28.                 }
  29.             }
  30.         }
  31.         System.out.println(ans);
  32.     }
  33. }

4.分巧克力

image.png
输入：

2 10 6 5 5 6

输出：

2

4.1思路分析

1.最直观的方法就是暴力法，已知一个巧克力的长（HI）和宽（WI），那么我们从中可以切出的正方形数量第八届蓝桥杯省赛（C组） - 图7，按照上述测试用例来说，HI=6,WI=5，那么可以切出边长为1的正方形=HI/6WI/5=30，边长为2的正方形=HI/6WI/5=3*2=6。一遍一遍的枚举，如果能切出的数量>=K，那么就更新一下能够切出的最大边长。

4.2代码

  1. import java.util.LinkedList;
  2. import java.util.List;
  3. import java.util.Scanner;
  5. public class Main5 {
  6.     public static void main(String[] args) {
  7.         Scanner sc=new Scanner(System.in);
  8.         int N=sc.nextInt();
  9.         int K=sc.nextInt();
  10.         int res=1;
  11.         sc.nextLine();
  12.         List<Integer>[] list=new LinkedList[N];
  13.         for(int i=0;i<list.length;i++){
  14.             list[i]=new LinkedList<>();
  15.             list[i].add(sc.nextInt());
  16.             list[i].add(sc.nextInt());
  17.         }
  18.         //从边长为1开始切分
  19.         for(int i=1;i<10000;i++){
  20.             int count=0;
  21.             for(int j=0;j< list.length;j++){
  22.                 int HI=list[j].get(0);
  23.                 int WI=list[j].get(1);
  24.                 count+=HI/i*WI/i;
  25.             }
  26.             if(count>=K)res=Math.max(res,i);
  27.         }
  28.         System.out.println(res);
  29.     }
  30. }