8.3米哈游笔试（已挂）
第一道
package com.面试中的算法.米哈游秋招;
import java.util.Scanner;
/**
* @author xing'chen
* @version 1.0
* @description:
* 米小游有一个长度为 n 的数组，其中第 i 个元素为 ai。现在定义数组的价值是最大的相邻数字的乘积。例如数组为 [3,5,1,2] ，
* 相邻元素的乘积分别是 35=15,51=5和1*2=2 ，则数组的价值是这些数字中的最大值，即 15。
*
* 现在米小游想要任选数组中的某两个相邻的元素进行交换（你必须使用这次交换机会），他想知道最大可以将数组的价值更改为多少？
*
* 输入描述
*
* 第一行输入一个整数 n(2<=n<=10^5) 表示数组的长度。 第二行输入 n 个整数 a1,a2,.....,an (1<=ai<=10^5) 表示数组中的值。
*
* 输出描述
*
* 在一行上输出一个整数表示答案。
* @date 2024/8/3 20:37
*/
public class MAIN1 {
public static void main(String[] args) {
//表示数组长度
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
long[] arr=new long[n];
//表述该数组的各数字
for (int i = 0; i < n; i++) {
arr[i]=scanner.nextInt();
}
long res=-1;
for (int i = 0; i < n-1; i++) {
res=Math.max(res,arr[i]*arr[i+1]);
}
//在原有数组的基础上将任意 两个相邻的 两个数字进行交换，得到乘积的最大值
for (int i=0;i<n-1;i++){
long left=(i>0)?arr[i-1]*arr[i+1]:0;
long right=(i<n-2)?arr[i+1]*arr[i+2]:0;
res=Math.max(res,Math.max(left,right));
}
System.out.println(res);
scanner.close();
}
}
第二道
package com.面试中的算法.米哈游秋招;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
/**
* @author xing'chen
* @version 1.0
* @description:
*
* 商店里有 n个商品，分别编号为 1~n ，每个商品都有一个价值 vali和体积 wi，米小游有一个有一个 m 容量的背包，
* 他能够装得下任意多个体积之和不超过 m 的商品。
*
* 米小游认为有些东西一起购买会带来灾难，比如可莉的角色立牌和蹦蹦炸弹的小手办，所以他设定了 k组互斥关系，
* 每组关系给定两个数字 a,b，表示编号为 a 的商品和编号为 b的商品不能同时购买。
*
* 米小游希望装下的物品的价值之和最大，请你帮帮他求出最大价值。
*
* 输入描述
*
* 第一行输入三个整数 n,m,k(1<=n<=15;1<=m<=10^9;0<=k<=15)表示商品数量、背包容量和互斥关系数量。
*
* 接下来 n行，每行输入两个整数 wi,vali(1<=wi,vali<=10^9) 表示每个物品的体积和价值。
*
* 接下来 k行，每行输入两个整数 a,b(1<=a,b<=n,a≠b)，描述一组互斥关系。
*
* 输出描述
*
* 在一行上输出一个整数表示答案。
* @date 2024/8/3 20:52
*/
public class MAIN2 {
private static int n,m,k;
private static int[][] arr;
private static Set<Integer>[] ans;
private static int res=0;
private static boolean check(int i,Set<Integer> les){
for(int a:les){
if(ans[a].contains(i)){
return false;
}
}return true;
}
private static void backend(int i,int currValue,int currWeight,Set<Integer> les){
if(i>=n){
res=Math.max(res,currValue);
return;
}
backend(i+1,currValue,currWeight,les);
//不是互斥关系且重量满足就可以计算该数据然后回溯重新计算，直到找到最大值
if(check(i,les)&&currWeight+arr[i][0]<=m){
les.add(i);
backend(i+1,currValue+arr[i][0],currWeight+arr[i][0],les);
les.remove(i);
}
}
//对数据进行数据结构的选择，之后进行赋值
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
n= in.nextInt();
m=in.nextInt();
k=in.nextInt();
arr=new int[n][2];
ans=new HashSet[n];
//商品的重量和价值的初始化
for (int i = 0; i < n; i++) {
arr[i][0]=in.nextInt();
arr[i][1]=in.nextInt();
}
for (int i = 0; i < n; i++) {
ans[i]=new HashSet<>();
}
for (int i=0;i<k;i++){
int a=in.nextInt()-1;
int b=in.nextInt()-1;
ans[a].add(b);
ans[b].add(a);
}
Set<Integer> les=new HashSet<>();
backend(0,0,0,les);
System.out.println(res);
in.close();
// int[] dp=new int[n+1];
//
// //互斥表的序号为n的序号
// //相当于给了一串商品，除去互斥关系之后，在剩下的商品中获得价值之和最大，且体积小于等于m
// dp[0]=arr[0][1];//初始为第一个商品的价值
// for (int j = 0; j < k; j++) {
// for (int i = 0; i < n; i++) {
// if(ans[j][0]==i&&ans[j][1]!=i+1) {
// dp[i + 1] = arr[i][1] + arr[i + 1][1];
// }else if(ans[j][0]==i&&ans[j][1]==i+1){
// dp[i+1]=Math.max(dp[i+1],dp[i]);
// }
// }
// }
// System.out.println(2*dp[n-1]);
}
}
第三道
package com.面试中的算法.米哈游秋招;
import java.util.*;
/**
* @author xing'chen
* @version 1.0
* @description:
* 米小游和派蒙在进行一场游戏。游戏在一个基环树（点数与边数相等的无向简单连通图）上进行，定义图中一个点的度数为与其相连的边数，
* 二人轮流进行以下操作：
*
* ● 选择图中一个度数为 1 的点，删除这个点以及与这个点相连的边。
*
* 图中有一个特殊的点 x ，删除了点 x 的玩家即获得胜利。
*
* 现在，由米小游先进行操作。在双方都采取最优策略的情况下，胜者是谁？
*
* 输入描述
*
* 每个测试文件均包含多组测试数据。第一行输入一个整数 T(1<=T<=1000) 代表数据组数，每组测试数据描述如下：
*
* 第一行输入两个整数 n,x(3<=n<=10^5, 1<=x<=n) 表示图的点数及特殊点的编号。
*
* 此后 n 行，第 i 行输入两个整数 ui 和 vi (1<=vi,ui<=n ; ui!=vi) 表示树上第 i 条边连接节点 ui 和 vi 。保证图联通，没有重边。
*
* 除此之外，保证给定的边构成一个基环树，所有的 n 之和不超过 2*10^5 。
*
* 输出描述
*
* 对于每一组测试数据，在一行上输出胜者的名字（ Xiaoyo 或 Pyrmont ）。特别地，若点 x 不可能被删除，请输出 Draw 。
* @date 2024/8/7 11:04
*/
public class MAIN3 {
private static void solve() {
int n = sc.nextInt();
int x = sc.nextInt();
List<List<Integer>> graph = new ArrayList<>(n + 1);
//初始化数组
for (int i = 0; i <= n; ++i) {
graph.add(new ArrayList<>());
}
int[] indegre = new int[n + 1];
for (int i = 0; i < n; ++i) {
int a = sc.nextInt();
int b = sc.nextInt();
graph.get(a).add(b);
graph.get(b).add(a);
indegre[a]++;
indegre[b]++;
}
Deque<Integer> q = new ArrayDeque<>();
for (int i = 1; i <= n; ++i) {
if (indegre[i] == 1) {
if (i == x) {
System.out.println("Xiaoyo");
return;
}
q.add(i);
}
}
int cnt = 0;
boolean flg = false;
while (!q.isEmpty()) {
int node = q.poll();
cnt++;
if (node == x) {
flg = true;
continue;
}
for (int next : graph.get(node)) {
indegre[next]--;
if (indegre[next] == 1) {
q.add(next);
}
}
}
if (!flg) {
System.out.println("Draw");
} else if (cnt % 2 == 0) {
System.out.println("Pyrmont");
} else {
System.out.println("Xiaoyo");
}
}
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
int T = sc.nextInt();
for (int i = 0; i < T; ++i) {
solve();
}
sc.close();
}
}
#米哈游求职进展汇总#
投递淘天集团等公司10个岗位 >