Winter vacation homework & Stamp cutting

Winter homework

package lanqiao.lanqiao_2016;

/**
 * Created by ministrong on 2020/3/5.
 *
  Winter homework 

  Now primary school mathematics is not so fun .
  Look at this winter vacation assignment ：

 □ + □ = □
 □ - □ = □
 □ × □ = □
 □ ÷ □ = □

 ( If it doesn't show up , You can see 【 chart 1.jpg】)

  Each square represents 1~13 One of the numbers in , But don't repeat .
  such as ：
 6  + 7 = 13
 9  - 8 = 1
 3  * 4 = 12
 10 / 2 = 5

  as well as ：
 7  + 6 = 13
 9  - 8 = 1
 3  * 4 = 12
 10 / 2 = 5

  Even if there are two solutions .（ Add , The commutative law of multiplication is followed by different schemes ）

  How many solutions have you found ？


  Please fill in the integer representing the number of schemes .
  Be careful ： You should submit an integer , Don't fill in any extra content or explanatory text .


 answer ：64
 */

import java.util.Arrays;

/***
 *  Or the problem of full arrangement ,1~13 Full Permutation 
 *  Find out the match a【0】+a【1】=a【2】;a【3】-a【4】=a【5】,a【6】*a【7】=a【8】,a【9】/a【10】=a【11】
 */
public class Q6_2016_7_hanjia {
    public static int[] a=new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13};
    public static void main(String[] args) {
        long t1=System.currentTimeMillis();


        int res=0;
        do{
            if(a[0]+a[1]==a[2] && a[3]-a[4]==a[5] && a[6]*a[7]==a[8] && a[9]/a[10]==a[11]) res++;
        }while(nextque());
        System.out.println(res);

        long t2=System.currentTimeMillis();

        System.out.println(t2-t1);
    }

    public static boolean nextque(){
        int x=-1;
        for(int i=a.length-1;i>0;i--){
            if(a[i]>a[i-1]){
                x=i-1;
                break;
            }

        }
        if(x==-1) return false;
        int y=-1;
        for(int i=a.length-1;i>x;i--){
            if(a[i]>a[x]) {
                y=i;
                break;
            }
        }
        int t=a[x];
        a[x]=a[y];
        a[y]=t;

        Arrays.sort(a,x+1,a.length);
        return true;
    }
}

13 It takes time to arrange all the numbers , About a minute and a half  , Consider using pruning to optimize . But the Blue Bridge Cup is unnecessary , It's OK to calculate it within the examination time .

Cutting stamps

From left to right are figures 1、 chart 2、 chart 3.

package lanqiao.lanqiao_2016;

/**
 * Created by ministrong on 2020/3/28.
 */

/***
 *
  Cutting stamps 

  Such as 【 chart 1.jpg】,  Yes 12 Zhang Lian together 12 Zodiac Stamps .
  Now you're going to cut it out 5 Zhang Lai , The requirements must be connected .
 （ Just connecting one corner doesn't make a connection ）
  such as ,【 chart 2.jpg】,【 chart 3.jpg】 in , The part shown in pink is a qualified cut .

  Please calculate , How many different clipping methods are there .

  Please fill in the integer representing the number of schemes .
  Be careful ： You should submit an integer , Don't fill in any extra content or explanatory text .

  answer ：116

 */

import java.util.Arrays;

/****
 *  The train of thought is ： from 1~12 Middle selection 5 Number , Then see if they are connected 
 *  As for how 12 choose 5, One idea is to use full permutation 
 *  For arrays {0,0,0,0,0,0,0,1,1,1,1,1} Arrange them all ,1 The subscript of corresponds to the number selected each time 
 *  In this way, all the options can be listed 
 *  And then through dfs Verify whether it is connected 
 */
public class Q7_2016_7_jianyoupiao {
    public static int[] a=new int[]{0,0,0,0,0,0,0,1,1,1,1,1};
    public static int num=0;
    public static void main(String[] args) {
        int res=0;
        do{
            if(isok()) res++;

        }while(nextque());
        System.out.println(res);
    }
    // Is it connected 
    public static boolean isok(){
        boolean[][] t=new boolean[3][4];
        int startx=0;
        int starty=0;
        for(int i=0;i<a.length;i++){
            if(a[i]==1){
                t[i/4][i%4]=true;
                startx=i/4;
                starty=i%4;
                //System.out.println(i+1);
            }
        }
        num=0;

        return isconnect(t,startx,starty);
    }

    public static boolean isconnect(boolean[][] t,int x,int y){

            if(x>=0 && x<3 && y>=0 && y<4 && t[x][y]) {
                num++;
                if(num==5) return true;
                t[x][y]=false;
                boolean l= isconnect(t,x+1,y)||isconnect(t,x-1,y)||isconnect(t,x,y+1)||isconnect(t,x,y-1);
                //t[x][y]=true;
                return l;
            }
            else return false;

    }

    // Find the next complete permutation .
    public static boolean nextque(){
        int x=-1;
        for(int i=a.length-1;i>0;i--){
            if(a[i]>a[i-1]){
                x=i-1;
                break;
            }

        }
        if(x==-1) return false;
        int y=-1;
        for(int i=a.length-1;i>x;i--){
            if(a[i]>a[x]) {
                y=i;
                break;
            }
        }
        int t=a[x];
        a[x]=a[y];
        a[y]=t;

        Arrays.sort(a,x+1,a.length);
        return true;
    }
}