牛客周赛 Round 92 题解 Java

目录

A 小红的签到题

B 小红的模拟题

C 小红的方神题

D 小红的数学题

E 小红的 ds 题

F 小红的小苯题

A 小红的签到题

直接构造类似于 a_aaaa，a_aaaaaaaa 这种 即可

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;

/**
 * 题目地址
 *
 */

// xixi♡西
public class Main {

    static IoScanner sc = new IoScanner();
    static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (1e9 + 7);

    static int n;
    static int arr[];
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

    /**
     * @throws IOException
     */
    private static void solve() throws IOException {
        // todo
        int n=sc.nextInt();
        dduo("a_");
        for(int i=0;i<n-2;i++) {
        	dduo("a");
        }
    }

    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }

    static <T> void dduo(T t) {
        System.out.print(t);
    }

    static <T> void dduoln() {
        System.out.println("");
    }

    static <T> void dduoln(T t) {
        System.out.println(t);
    }
}

/**
 * IoScanner类
 *
 * @author Dduo
 * @version 1.0
 * @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。
 */
class IoScanner {
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;

    public IoScanner() {
        bf = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer("");
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    public String nextLine() throws IOException {
        return bf.readLine();
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    public char nextChar() throws IOException {
        return next().charAt(0);
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public float nextFloat() throws IOException {
        return Float.parseFloat(next());
    }

    public BigInteger nextBigInteger() throws IOException {
        return new BigInteger(next());
    }

    public BigDecimal nextDecimal() throws IOException {
        return new BigDecimal(next());
    }
}

B 小红的模拟题

第一眼以为是 dfs

但是看到了

只有一个陷阱格子

所以只要规定一条到终点的路线 先一直往右走 再一直往下走

如果陷阱格子在这条线路上

就一直往下走 再一直往右走 以到达终点

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;

/**
 * 题目地址
 *
 */

// xixi♡西
public class Main {

    static IoScanner sc = new IoScanner();
    static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (1e9 + 7);

    static int n;
    static int arr[];
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

    /**
     * @throws IOException
     */
    private static void solve() throws IOException {
        // todo
        int n=sc.nextInt();
        int m=sc.nextInt();
        
        char arr[][]=new char[n][m];
        for(int i=0;i<n;i++) {
        	String str=sc.next();
        	arr[i]=str.toCharArray();
        }
        
        int x=0;
        int y=0;
        for(int i=0;i<n;i++) {
        	for(int j=0;j<m;j++) {
        		if(arr[i][j]=='#') {
        			x=i;
        			y=j;
        		}
        	}
        }
        
        if(x==0||y==m-1) {
          	for(int i=0;i<n-1;i++) {
        		dduo("S");
        	}
        	for(int i=0;i<m-1;i++) {
        		dduo("D");
        	}
        }else if(y==0||x==n-1){
        	for(int i=0;i<m-1;i++) {
        		dduo("D");
        	}
        	for(int i=0;i<n-1;i++) {
        		dduo("S");
        	}
        }else {
        	for(int i=0;i<n-1;i++) {
        		dduo("S");
        	}
        	for(int i=0;i<m-1;i++) {
        		dduo("D");
        	}
        }
        
    }

    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }

    static <T> void dduo(T t) {
        System.out.print(t);
    }

    static <T> void dduoln() {
        System.out.println("");
    }

    static <T> void dduoln(T t) {
        System.out.println(t);
    }
}

/**
 * IoScanner类
 *
 * @author Dduo
 * @version 1.0
 * @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。
 */
class IoScanner {
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;

    public IoScanner() {
        bf = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer("");
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    public String nextLine() throws IOException {
        return bf.readLine();
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    public char nextChar() throws IOException {
        return next().charAt(0);
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public float nextFloat() throws IOException {
        return Float.parseFloat(next());
    }

    public BigInteger nextBigInteger() throws IOException {
        return new BigInteger(next());
    }

    public BigDecimal nextDecimal() throws IOException {
        return new BigDecimal(next());
    }
}

C 小红的方神题

其实我想了一会

然后根据样例试了试

输入 4

1 4 3 2

输入 5

1 5 4 3 2

都是符合的

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;

/**
 * 题目地址
 *
 */

// xixi♡西
public class Main {

    static IoScanner sc = new IoScanner();
    static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (1e9 + 7);

    static int n;
    static int arr[];
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

    /**
     * @throws IOException
     */
    private static void solve() throws IOException {
        // todo
        int n=sc.nextInt();
        
        if(n==1||n==2) {
        	dduoln("-1");
        	return;
        }
        
        dduo(1+" ");
        
        for(int i=n;i>=2;i--) {
        	dduo(i+" ");
        }
    }

    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }

    static <T> void dduo(T t) {
        System.out.print(t);
    }

    static <T> void dduoln() {
        System.out.println("");
    }

    static <T> void dduoln(T t) {
        System.out.println(t);
    }
}

/**
 * IoScanner类
 *
 * @author Dduo
 * @version 1.0
 * @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。
 */
class IoScanner {
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;

    public IoScanner() {
        bf = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer("");
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    public String nextLine() throws IOException {
        return bf.readLine();
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    public char nextChar() throws IOException {
        return next().charAt(0);
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public float nextFloat() throws IOException {
        return Float.parseFloat(next());
    }

    public BigInteger nextBigInteger() throws IOException {
        return new BigInteger(next());
    }

    public BigDecimal nextDecimal() throws IOException {
        return new BigDecimal(next());
    }
}

D 小红的数学题

我的首先想到的是韦达定理

要求是 x1 x2 互不相同 而且 x1+x2+x1*x2==k

之后 x1+x2 为 p ，x1*x2 为 q

其次进行了打表

获取了大量数据

发现奇数的话 是一定可以的 只要构造其中一个数为 1 即可

接着是偶数

我找出的规律是这样的

然后根据规律推

放大循环的次数 就过了

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;

/**
 * 题目地址
 *
 */

// xixi♡西
public class Main {

    static IoScanner sc = new IoScanner();
    static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (1e9 + 7);

    static int n;
    static int arr[];
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

    /**
     * @throws IOException
     */
    private static void solve() throws IOException {
        // todo
    	
//    	TreeSet<Integer>hs=new TreeSet<>();
//    	for(int i=1;i<=100;i++) {
//    		for(int j=i+1;j<=100;j++) {
//    			// k
//    			if( (i+j+i*j) %2==0) {
//    				dduoln((i+j)+" "+(i*j)+" "+(i+j+i*j));	
//    			}
//    			hs.add((i+j+i*j));
//    		}
//    	}
//    	
//    	for(Integer i:hs) {
//    		if(i%2==0) {
//    			dduoln(i);
//    		}
//    	}
    	
    	long k=sc.nextLong();
    	if(k%2!=0) {
    		// 奇数
    		if(k==1||k==3) {
    			dduoln("-1");
    			return;
    		}
    		long ans1=k-1;
    		ans1/=2;
    		long ans2=(1+ans1);
    		dduoln((ans1)+" "+(ans2));	
    	}else {
    		// 偶数
    		long zuobian=14;
    		long youbian=6;
    		
    		long zuopbianjia=12;
    		long youbianjia=4;
    		
    		// todo
    		for(int i=0;i<1000000;i++) {
    			if(k-zuobian<0) {
    				dduoln("-1");
    				return;
    			}
    			long youbianshengxialai=k-zuobian;
    			if(youbianshengxialai%youbian==0) {
    				long nn=youbianshengxialai/youbian;
//    				dduoln(nn);
//    				dduoln((zuobian-youbian)+" "+nn*(youbian-2));
    				dduoln((youbian+2*nn)+" "+((zuobian-youbian)+(nn*(youbian-2))));
    				return;
    			}
    			zuopbianjia+=8;
    			zuobian+=zuopbianjia;
    			youbian+=youbianjia;
    		}
    	}
        
        
    }

    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }

    static <T> void dduo(T t) {
        System.out.print(t);
    }

    static <T> void dduoln() {
        System.out.println("");
    }

    static <T> void dduoln(T t) {
        System.out.println(t);
    }
}

/**
 * IoScanner类
 *
 * @author Dduo
 * @version 1.0
 * @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。
 */
class IoScanner {
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;

    public IoScanner() {
        bf = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer("");
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    public String nextLine() throws IOException {
        return bf.readLine();
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    public char nextChar() throws IOException {
        return next().charAt(0);
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public float nextFloat() throws IOException {
        return Float.parseFloat(next());
    }

    public BigInteger nextBigInteger() throws IOException {
        return new BigInteger(next());
    }

    public BigDecimal nextDecimal() throws IOException {
        return new BigDecimal(next());
    }
}

E 小红的 ds 题

我感觉这题的难度小于 D

给出二叉树每一层的节点

然后构造出二叉树

每个节点有 0 个 1 个 2 个节点

我们直接顺着往下构造就行

直接一层一层推

什么情况下构造不出来呢

当这下层的节点数大于这一层的两倍时无法构造 因为这一层的每个节点最多连下一层的两个节点

接着就是一个个构造

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;

/**
 * 题目地址
 *
 */

// xixi♡西
public class Main {

    static IoScanner sc = new IoScanner();
    static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (1e9 + 7);

    static int n;
    static int arr[];
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

    /**
     * @throws IOException
     */
    private static void solve() throws IOException {
        // todo
    	int n=sc.nextInt();
    	long arr[]=new long[n+1];
    	for(int i=1;i<=n;i++) {
    		arr[i]=sc.nextLong();
    	}
    	
    	for(int i=2;i<=n;i++) {
    		if( (arr[i]) > (arr[i-1]*2) ) {
    			dduoln("-1");
    			return;
    		}
    	}
    	
    	dduoln("1");
    	
    	long cnt=2;
    	
    	for(int i=1;i<=n;i++) {
    		long ans=arr[i]; // 当前层有多少节点
    		if(i==n) {
        		// 最后一层
    			for(int j=0;j<ans;j++) {
    				dduoln("-1 -1");
    			}
    		}else {
    			// 下一层有多少个节点
    			long next=arr[i+1];
//    			cnt+=ans;
    			for(int j=0;j<ans;j++) {
    				if(next>=2) {
        				dduo(cnt);
        				dduo(" ");
        				cnt++;
        				dduoln(cnt);
        				cnt++;
        				next-=2;
        			}else if(next==1){
        				dduo(cnt);
        				dduo(" ");
        				cnt++;
        				dduoln("-1");
        				next-=1;
        			}else {
        				dduoln("-1 -1");
        			}
    			}    			
    		}
//			cnt+=ans;
    	}
        
    }

    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }

    static <T> void dduo(T t) {
        System.out.print(t);
    }

    static <T> void dduoln() {
        System.out.println("");
    }

    static <T> void dduoln(T t) {
        System.out.println(t);
    }
}

/**
 * IoScanner类
 *
 * @author Dduo
 * @version 1.0
 * @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。
 */
class IoScanner {
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;

    public IoScanner() {
        bf = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer("");
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    public String nextLine() throws IOException {
        return bf.readLine();
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    public char nextChar() throws IOException {
        return next().charAt(0);
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public float nextFloat() throws IOException {
        return Float.parseFloat(next());
    }

    public BigInteger nextBigInteger() throws IOException {
        return new BigInteger(next());
    }

    public BigDecimal nextDecimal() throws IOException {
        return new BigDecimal(next());
    }
}

F 小红的小苯题

构造一个矩阵 每行每列的异或和构成排列

这样构造 然后正好要满足这个情况

就是 行加列%4==3

很奇妙！

// @github https://github.com/Dddddduo
// @github https://github.com/Dddddduo/acm-java-algorithm
// @github https://github.com/Dddddduo/Dduo-mini-data_structure
import java.util.*;
import java.io.*;
import java.math.*;
import java.lang.*;
import java.time.*;

/**
 * 题目地址
 *
 */

// xixi♡西
public class Main {

    static IoScanner sc = new IoScanner();
    static final int mod = (int) (1e9 + 7);
//    static final int mod = (int) (1e9 + 7);

    static int n;
    static int arr[];
    static boolean visited[];
    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>();

    /**
     * @throws IOException
     */
    
    // 2 5
    // 0 0 0 0 7
    // 1 2 3 4 2
    private static void solve() throws IOException {
        // todo
    	  int n = sc.nextInt();
          int m = sc.nextInt();
          int k = n + m;
          
          if (k % 4 != 3) {
              dduoln("-1");
              return;
          }

          // 行
          int[] rows = new int[n];
          for (int i = 0; i < n; i++) {
              rows[i] = k - i;
          }
          
          // 列
          int[] cols = new int[m];
          for (int i = 0; i < m; i++) {
              cols[i] = i + 1;
          }

          int[][] arr = new int[n][m];
          for (int i = 0; i < n - 1; i++) {
              for (int j = 0; j < m - 1; j++) {
            	  arr[i][j] = 0;
              }
              arr[i][m - 1] = rows[i];
          }

          if (m == 0) {
        	  dduoln("-1");
              return;
          }

          // 列处理
          for (int j = 0; j < m - 1; j++) {
        	  arr[n - 1][j] = cols[j];
          }

          int ans = 0;
          for (int i = 0; i < n - 1; i++) {
        	  ans ^= rows[i];
          }
          
          int x = cols[m - 1] ^ ans;
          arr[n - 1][m - 1] = x;

          for (int i = 0; i < n; i++) {
              int xor = 0;
              for (int num : arr[i]) {
                  xor ^= num;
              }
              assert xor == rows[i] : "Row " + i + " xor error";
          }

          for (int j = 0; j < m; j++) {
              int xor = 0;
              for (int i = 0; i < n; i++) {
                  xor ^= arr[i][j];
              }
              assert xor == cols[j] : "Col " + j + " xor error";
          }

          for (int[] row : arr) {
              StringBuilder sb = new StringBuilder();
              for (int num : row) {
                  sb.append(num).append(" ");
              }
              dduoln(sb.toString());
          }
        
    }

    public static void main(String[] args) throws Exception {
        int t = 1;
//        t = sc.nextInt();
        while (t-- > 0) {
            solve();
        }
    }

    static <T> void dduo(T t) {
        System.out.print(t);
    }

    static <T> void dduoln() {
        System.out.println("");
    }

    static <T> void dduoln(T t) {
        System.out.println(t);
    }
}

/**
 * IoScanner类
 *
 * @author Dduo
 * @version 1.0
 * @description 通过IO流操作缓冲区减少了与底层输入输出设备的交互次数，旨在简化 Java 中的标准输入读取操作。
 */
class IoScanner {
    BufferedReader bf;
    StringTokenizer st;
    BufferedWriter bw;

    public IoScanner() {
        bf = new BufferedReader(new InputStreamReader(System.in));
        st = new StringTokenizer("");
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
    }

    public String nextLine() throws IOException {
        return bf.readLine();
    }

    public String next() throws IOException {
        while (!st.hasMoreTokens()) {
            st = new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }

    public char nextChar() throws IOException {
        return next().charAt(0);
    }

    public int nextInt() throws IOException {
        return Integer.parseInt(next());
    }

    public long nextLong() throws IOException {
        return Long.parseLong(next());
    }

    public double nextDouble() throws IOException {
        return Double.parseDouble(next());
    }

    public float nextFloat() throws IOException {
        return Float.parseFloat(next());
    }

    public BigInteger nextBigInteger() throws IOException {
        return new BigInteger(next());
    }

    public BigDecimal nextDecimal() throws IOException {
        return new BigDecimal(next());
    }
}