本文主要是介绍笔试,牛客.kotori和n皇后,牛客.AOE还是单体,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
目录
牛客.kotori和n皇后编辑
牛客.AOE还是单体
牛客.kotori和n皇后
想起来,我之前还写过n皇后的题,但是这个我开始只能想到暴力解法
判断是不是斜对角线,联想y=x+b和y=-x+b,假如在一条线上,那么他们的x和y会对应成比例,这个扫描+判断是一个O(n^2)的操作。
import java.util.*; import java.io.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static PrintWriter out=new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in=new Read();public static void main(String[] args) throws IOException{int n=in.nextInt();long [][]a=new long[n][2];for(int i=0;i<n;i++){a[i][0]=in.nextInt();a[i][1]=in.nextInt();}int t=in.nextInt();//暴力解法//简易的n皇后问题.@while(t>0){int ret=0;int k=in.nextInt();for(int i=0;i<k-1;i++){if(a[i][0]==a[k-1][0]||a[i][1]==a[k-1][1]||a[i][0]+a[i][1]==a[k-1][0]+a[k-1][1]||a[i][1]-a[i][0]==a[k-1][1]-a[k-1][0]){ret=1;break;}}if(ret==1){out.println("Yes");}else{out.println("No");}t--;}out.close();} } class Read{//字符串裁剪StringTokenizer st=new StringTokenizer("");BufferedReader bf=new BufferedReader(new InputStreamReader(System.in));String next()throws IOException{while(!st.hasMoreTokens()){st=new StringTokenizer(bf.readLine());}return st.nextToken();}int nextInt() throws IOException{return Integer.parseInt(next());} }
改进:哈希表,我们需要快速获取他的攻击范围,所以快速获取则使用哈希表,我们只需要获取他的攻击范围即可,怎么存,可以使用哈希Set,
问题,假如当前他第i个已经出现了会攻击的情况的话,那么后面的只需要存对应的消息,无需接着判断,因为一直会被攻击
import java.util.*; import java.io.*; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main {public static PrintWriter out =new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));public static Read in=new Read();public static void main(String[] args) throws IOException {int n = in.nextInt();long [][]a = new long[n + 1][2]; //四个哈希表一个存行,一个列,一个x,一个-x (我说的是斜率)HashSet<Long>row = new HashSet<>();HashSet<Long>col = new HashSet<>();HashSet<Long>dig1 = new HashSet<>();HashSet<Long>dig2 = new HashSet<>();int ret = (int)1e5 + 10;for (int i = 1; i <= n; i++) {a[i][0] = in.nextLong();a[i][1] = in.nextLong();if (ret != (int)1e5 + 10)continue;if (row.contains(a[i][0]) || col.contains(a[i][1]) ||dig1.contains(a[i][0] + a[i][1]) ||dig2.contains(a[i][1] - a[i][0])) {ret = i;}row.add(a[i][0]);col.add(a[i][1]);dig1.add(a[i][0] + a[i][1]);dig2.add(a[i][1] - a[i][0]);}int t = in.nextInt();//暴力解法//简易的n皇后问题.@while (t > 0) {int k = in.nextInt(); //k>=ret就是ret是从i开始,因为从i开始就可以与k保持一致下标,不然容易判断错误,多思考一步,麻烦if (k >= ret) {out.println("Yes");} else {out.println("No");}t--;}out.close();} } class Read {//字符串裁剪StringTokenizer st = new StringTokenizer("");//1.把字节流转化为字符流从IO设备中拿数据,先是建立一个内存缓冲区,然后以后都从他的内存缓冲区拿数据,BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));// 再从从内存缓冲区里面拿数据String next()throws IOException {//看他后面还有没有要裁切的数据while (!st.hasMoreTokens()) {//bf.nextLine:直接在内存缓存区里面,拿一行数据,交给这个字符串裁切对象st = new StringTokenizer(bf.readLine());}//再返回新读入这一行return st.nextToken();}public String nextLine() throws IOException {return bf.readLine();}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());} }
牛客.AOE还是单体
暴力解法,但是缺点就是复杂度过高,因为你可以看x和n范围,我们就知道了,这可能会循环很多次。
import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();long x = in.nextLong();long[]a = new long[n];long sum = 0;for (int i = 0; i < n; i++) {a[i] = in.nextLong();}int all = n;Arrays.sort(a);int p=0;while (n > x) {for (int i = 0; i < all; i++) {a[i]--;if (a[i] == 0) {n--;}else{p=i;}}sum += x;}if(all>x){for (int i=all-(int)x; i < all; i++) {if(a[i]>0){sum += a[i];}}}else{for(int i=0;i<n;i++){sum+=a[i];}}System.out.print(sum);}
}
import java.util.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别int n = in.nextInt();long x = in.nextLong();long[]a = new long[n];long sum = 0;for (int i = 0; i < n; i++) {a[i] = in.nextLong();}Arrays.sort(a);int p=0;if(n>x){for (int i=n-(int)x; i <n; i++) {if(a[i]>0){sum += a[i]-a[n-(int)x-1];}}sum+=x*a[n-(int)x-1];}else{for(int i=0;i<n;i++){sum+=a[i];}}System.out.print(sum);}
}
import java.util.*;
public class Solution {/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param coins int整型一维数组 * @return int整型*/public int getCoins (ArrayList<Integer> coins) {int n=coins.size();int []a=new int[n+2];for(int i=0;i<n+2;i++){if(i==0||i==n+1){a[i]=1;}else{a[i]=coins.get(i-1);}}int[][]dp=new int[n+2][n+2];for(int i=n;i>=1;i--){for(int j=i;j<=n;j++){for(int k=i;k<=j;k++){dp[i][j]=Math.max(dp[i][k-1]+dp[k+1][j]+a[k]*a[i-1]*a[j+1],dp[i][j]);}}}return dp[1][n];}
}
这篇关于笔试,牛客.kotori和n皇后,牛客.AOE还是单体的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!