牛客周赛 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 {// todoint 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 {// todoint 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 {// todoint 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;// todofor(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 {// todoint 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 2private static void solve() throws IOException {// todoint 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());}
}