首页 > 网易雷火8.6 游戏研发工程师 笔试
头像
sick白牧
编辑于 2021-08-09 11:23
+ 关注

网易雷火8.6 游戏研发工程师 笔试

说明

总共3个小时,题目描述纯属个人回忆,可能用词和原版有所区别。前3道a了,第四道中的4种情况只推导出了2种,过了56%,请参考其他大佬。

1. 队伍匹配

题目描述

有两个人想组队参加匹配2v2游戏,他们的分数分别是q1和q2,组队匹配的规则是两支队伍的各自分数和之间的差距小于等于p;如果参加者是两人,则自动组成队,如果是单人玩家,则可以与另外一名单独玩家临时组队。

输入

第一行输入q1,q2,p,x,其中q1/q2/p的定义如上文所示,x为其他双人组的数目。

接下来x行,每行两个数,分别是这双人组的分数

接着输入y,y为单人组的数目。

解析来y行,每行一个数,是单人玩家的分数。

输出

这两个人能匹配的到的对手的排列组合数。

解析

送分题,计算双人组符合条件的数目a,再O(n2)暴力遍历单人组符合条件的数目,相加就完了。

import java.util.Scanner;

public class Main1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int q1 = scanner.nextInt();
        int q2 = scanner.nextInt();
        int p = scanner.nextInt();
        int x = scanner.nextInt();
        int[] a = new int[x];
        int[] b = new int[x];

        int res = 0;
        int q = q1+q2;
        for(int i=0;i<x;i++){
            a[i] = scanner.nextInt();
            b[i] = scanner.nextInt();
            if(Math.abs(a[i]+b[i]-q)<=p)
                res++;
        }

        int y = scanner.nextInt();
        int[] c = new int[y];

        for(int i=0;i<y;i++)
            c[i] = scanner.nextInt();
        for(int i=0;i<y;i++)
            for(int j=i+1;j<y;j++){
                if(Math.abs(c[i]+c[j]-q)<=p)
                    res++;
            }

        System.out.println(res);

    }
}

2. 跑酷

题目描述

一名玩家参加跑酷游戏,赛道均分为一段段高低不等的台阶,玩家从相同高度的台阶前进需要t1,跳到比现有台阶高一级的台阶需要t2,跳到比现有台阶低的台阶需要t3。同时游戏存在另一条平行赛道,平行赛道每个台阶的高度与原对应台阶的高度的和恒为4。玩家也可以切换在对应位置的两条赛道来回切,花费t4。玩家从起点跑到最后一个台阶视为游戏完成。

输入

第一行 n t1 t2 t3 t4
第二行有n个数,分别是第一条赛道的各台阶高度

输出

玩家完成游戏的最短耗时

解析

DFS,在每个位置上要么继续跑,要么切跑道,按两条跑法搜索,若当前时长已经大于最小时长则剪枝。另外用一个hashmap保存已经计算过的结果,由于有两条赛道,所以最多保存2n的位置上到终点的最短时间。

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main2 {
    static long minTime;
    static int n;
    static int[] h;
    static int[] h2;
    static int t1,t2,t3,t4;
    static Map<String,Long> map;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        t1 = scanner.nextInt();
        t2 = scanner.nextInt();
        t3 = scanner.nextInt();
        t4 = scanner.nextInt();

        h = new int[n];
        h2 = new int[n];
        minTime = Long.MAX_VALUE;
        map = new HashMap<>();

        for(int i=0;i<n;i++){
            h[i] = scanner.nextInt();
            h2[i] = 4 - h[i];
        }
        fun(0,0,true);
        System.out.println(minTime);

    }

    static void fun(int now,long t,boolean flag){
        if(t>=minTime)
            return;
        if(map.containsKey(now+""+flag)){
            long oldT = map.get(now+""+flag);
            if(t>=oldT)
                return;
        }
        map.put(now+""+flag,t);

        if(flag){
            if(now!=n-1){
                if(h[now+1]==h[now])
                    fun(now+1,t+t1, true);
                else if(h[now+1]<h[now])
                    fun(now+1,t+t3, true);
                else if(h[now+1]-h[now]==1)
                    fun(now+1,t+t2, true);
            }else
                minTime = Math.min(minTime,t);
        }else{
            if(now!=n-1){
                if(h2[now+1]==h2[now])
                    fun(now+1,t+t1, false);
                else if(h2[now+1]<h2[now])
                    fun(now+1,t+t3, false);
                else if(h2[now+1]-h2[now]==1)
                    fun(now+1,t+t2, false);
            }else
                minTime = Math.min(minTime,t);
        }
        fun(now,t+t4,!flag);
    }
}

3. 解析配置文件

题目描述

有一个配置文件,对它进行逐行解析,满足以下条件:

  • 需要存在空行,空行指的是仅有空格的行。
  • 若该行以“#”开头,则表示该行为注释行,忽略改行
  • 每一行只有一个key和value,形式如 key=value,若出现多个等号,则以第一个等号为主,其他等号视为value的值。
  • 无论是key和value都要略去前后的空格
  • value种可能存在{key}的情况,称为引用value,需要奖{key}替换为key对应的value。若引用的值不存在或循环引用,则解析失败。
  • 引用的大括号不匹配也视为匹配失败
  • 题目保证key和value自身没有大括号字段,即大括号一定是引用。

输入

第一行一个t,表示有t行数据。
接下来t行,即为文件的内容
最后一行key,表示要查询的key

输出

如果解析失败,输出“ERROR”;
如果解析成功,但不存在该key,输出“NULL”
如果解析成功并存在该key,输出该key的value

解析

按照题目要求逐行解析即可,先把全文空格删了,遇到空行或者注释行直接跳过。
用map表示已经解析出来的键值对,map2表示含有引用等待继续解析的键值对。
逐行解析,如果遇到引用,则加入map2,如果没有引用且格式正确,插入map。
接下来进行循环:
对于map2中的任意value,可以通过大括号得知求出该value中的引用有哪些,如果这些引用在map中存在,则替换它。
若替换后该value不存在引用,则将其从map2移到map1
当该轮循环没有发生替换,则退出循环。
退出循环后,检查map2,如果map2的大小不为0,则表示存在循环引用或引用不存在,直接输出解析失败。
如果map2的大小为0,说明全部解析成功,按题目要求返回map中的value即可。

import java.util.*;

public class Main3 {

    static void fun3(){
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        Map<String,String> map = new HashMap<>();
        Map<String,String> map2 = new HashMap<>();
        scanner.nextLine();
        while(t>0){
            String line = scanner.nextLine();
            if(line.replace(" ","").equals("")||line.startsWith("#")){
                t--;
                continue;
            }
            int index = line.indexOf("=");
            String key = line.substring(0,index).trim();
            String value = line.substring(index+1).trim();

            if(key.equals("")||value.equals("")){
                System.out.println("ERROR");
                return;
            }
            if(value.contains("{")&&!check(value)){
                System.out.println("ERROR");
                return;
            }
            if(value.contains("{"))
                map2.put(key,value);
            else
                map.put(key,value);
            t--;
        }
        boolean flag = true;
        while(flag){
            flag = false;
            if(map2.keySet().size()==0)
                continue;
            List<String> temp = new ArrayList<>();
            for(String key:map2.keySet()){
                String value = map2.get(key);
                List<String> childs = getChild(value);
                for(String child:childs){
                    if(map.containsKey(child)){
                        value = value.replace("{"+child+"}",map.get(child));
                        flag = true;
                    }
                }
                if(value.contains("{"))
                    map2.put(key,value);
                else{
                    temp.add(key);
                    map.put(key,value);
                }
            }
            for(String key:temp)
                map2.remove(key);
        }

        String url = scanner.nextLine();
        if(map2.keySet().size()==0)
            System.out.println(map.getOrDefault(url, "NULL"));
        else
            System.out.println("ERROR");
    }

    static boolean check(String s){
        int cnt = 0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='{')
                cnt++;
            else if(s.charAt(i)=='}')
                cnt--;
            if(cnt<0)
                return false;
        }
        return cnt == 0;
    }

    static List<String> getChild(String s){
        List<String> res = new ArrayList<>();
        StringBuilder temp = new StringBuilder();
        boolean flag = false;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='{')
                flag = true;
            else if(s.charAt(i)=='}'){
                flag = false;
                res.add(temp.toString());
                temp = new StringBuilder();
            }
            else{
                if(flag)
                    temp.append(s.charAt(i));
            }
        }
        return res;
    }
    public static void main(String[] args) {
        fun3();
    }
}

4. 莫比乌斯赛车大逃杀

题目描述

赛车的跑道是一个长为M的纸条,但是将纸条一头旋转180后,接入另一头,形成一个莫比乌斯环。该环上有N量赛车,你控制1号赛车可以做以下行为:

  • 攻击你前方或后方距离小于等于L的赛车,使其退赛
  • 立刻瞬移到纸带背面,速度和方向不变
    求要歼灭除你自己之外的其他赛车,最短要多久,结果保留两位小数。

    输入:

    第一行 m n L
    第二行 有n个数,分别是1N号赛车的初始位置
    第三行 有n个数,分别是1
    N号赛车的速度,方向一致向前

    输出:

    使得只有自己留在场上的最短时间

    解析

    莫比乌斯环,由于自己可以瞬移到纸带的正反面,以自己为参考系,速度与方向不变,相当于其他车在抵达终点后,瞬移到起点又开始跑。(实际上其他车是跑到纸带的背面的新一圈,但对你而言没有区别),假设i号车的速度为vi,初始位置为si,只用考虑vi与v1,si与s1之间的大小关系所形成的四种情况追逐关系就能算出1号车歼灭i号车所需要的时间。最后输出最大的那个时间。
    由于时间来不及了,我只推导出两种,过了56%的用例...
import java.util.Scanner;

public class Main4 {

    static int m;
    static int l;
    static int s0;
    static int v0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        m = scanner.nextInt();
        int n = scanner.nextInt();
        l = scanner.nextInt();
        int[] s = new int[n];
        int[] v = new int[n];

        for(int i=0;i<n;i++)
            s[i] = scanner.nextInt();
        for(int i=0;i<n;i++)
            v[i] = scanner.nextInt();
        s0 = s[0];
        v0 = v[0];
        double max = 0;
        for(int i=1;i<n;i++)
            max = Math.max(max,fun(s[i],v[i]));
        System.out.printf("%.2f\n",max);
    }

    public static double fun(int s1,int v1){
        if(Math.abs(s1-s0)<=l)
            return 0;
        if(s1>s0&&v1>=v0)
            return (m-s1+s0-l)/(double)(v1-v0);
        if(s1>s0&&v1<v0){


            double t = (m-s1)/(double)v1;
            double t2 = (s1-s0-l)/(double)(v0-v1);
            if(t2<=t)
                return t2;
            else{

                //return 0;
            }


        }
        if(s1<s0&&v1>=v0){
            double t = (m-s0)/(double)v0;
            double t2 = (s0-s1-l)/(double)(v1-v0);
            if(t2<=t)
                return t2;
            else{
                t = (m-s1)/(double)v1;
                double s3 = s0+ t*v0-m;
                return t+s3/(double)(v1-v0);
            }
        }

        if(s1<s0&&v1<v0){
            //return 0;
            return (s1-s0+m-l)/(double)(v0-v1);
        }
        return 0;
    }
}

全部评论

(1) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐