首页 > 网易互娱 8.7 笔试
头像
sick白牧
发布于 2021-08-10 10:53
+ 关注

网易互娱 8.7 笔试

序言

2个半小时,3道题,时间充足

1. 身份证合法性检查

一个合法的身份证应该满足:
前17位分别有一个权重,按顺序依次为7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2,
将前17位乘对应的权重,求和,再对11取余。根据取余的结果不同,有以下映射{0,1,2,3,4,5,6,7,8,9,10}->{1,0,X,9,8,7,6,5,4,3,2}
如果映射后的字符和第18位一致,则合法。
但是由于身份证被污染了,导致1517位部分看不清,用*表示,可能取值为09。

输入

第一行一个t,表示有t个身份证
接下来t行,每一行一个待检查身份证

输出

合法的身份证数目

解析

按题目要求计算即可,一个有10种可能,两个有100种可能,三个*有1000种可能,暴力枚举没有超时。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main1 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t>0){
            int sum = 0;
            String s = scanner.next();
            List<String> res = fun3(fun2(fun1(s)));
            for(String ss:res){
                if(check(ss))
                    sum++;
            }
            System.out.println(sum);
            t--;
        }
    }
    public static List<String> fun1(String s){
        List<String> res = new ArrayList<>();
        if(s.charAt(14)=='*'){
            for(int i=0;i<=9;i++)
                res.add(s.substring(0,14)+i+s.substring(15));
        }else
            res.add(s);
        return res;
    }

    public static List<String> fun2(List<String> ss){
        List<String> res = new ArrayList<>();
        for(String s:ss)
            if(s.charAt(15)=='*'){
                for(int i=0;i<=9;i++)
                    res.add(s.substring(0,15)+i+s.substring(16));
            }else
                res.add(s);
        return res;
    }

    public static List<String> fun3(List<String> ss){
        List<String> res = new ArrayList<>();
        for(String s:ss)
            if(s.charAt(16)=='*'){
                for(int i=0;i<=9;i++)
                    res.add(s.substring(0,16)+i+s.substring(17));
            }else
                res.add(s);
        return res;
    }

    static int[] w = new int[]{7,9,10,5,8,4,2,1,6,3,7,9,10,5,8,4,2};
    public static boolean check(String s){
        int sum = 0;
        for(int i=0;i<17;i++){
            sum += w[i]*Integer.parseInt(s.charAt(i)+"");
        }
        sum = sum%11;
        char r = 'n';
        switch (sum){
            case 0:r='1';break;
            case 1:r='0';break;
            case 2:r='X';break;
            case 3:r='9';break;
            case 4:r='8';break;
            case 5:r='7';break;
            case 6:r='6';break;
            case 7:r='5';break;
            case 8:r='4';break;
            case 9:r='3';break;
            case 10:r='2';break;
            default:break;
        }
        return r==s.charAt(17);
    }
}

2. 田径赛跑顺序

题目描述

有n个运动员赛跑,裁判不小心把顺序忘了,采访了一些观众,他们给出了自己看到的部分顺序,即只知道某位运动员在某位运动员前。请根据这些线索输出运动员的跑步顺序。

输入

第一行t,表示有t组数据
接下来每组数据:
输入n,m
接下来m行,每一行为观众观测到的数据,第一个数为c,表示这一行之后还有c个数,这c个数取1~n,分别表示运动员的编号,出现在后面的运动员的名次一定比出现在前面的运动员的名次低。

输出

若能求出所有运动员的顺序,输出顺序;若不能,输出“NO”

解析

正确做法是拓扑排序,将入度为0的运动员加入队列,依次从队列取出元素,将线索中排在他前面的运动员的入度-1,如果最后所有运动员都被正确入队出队,则唯一的出队顺序就是跑步排名。
但我当时比较蠢没想到是拓扑排序。
我的做法是用一个map<int,set>表示第i号运动员前面的运动员编号的集合,则至少有一个运动员后面再无运动员,从他开始作为排名的末尾,向前按dfs查map,查到的set里的元素加入到排名再往前查,直到map没有这个元素(队首)时,排名的长度若等于n则表示该排名即为所求队列,如果不为n说明这条查找路径是漏了的,直接抛弃。
反思:由于查找到最终前都无法得知目前路径是否错误,所以进行了大量不必要的计算,所以会超时...还有条减枝思路就是再用一个map<int,int>记录i号运动员离队尾最远的排名,如果当前路径中的离队尾的排名小于它就直接舍弃,通俗的说就是如果已经有路径(从末尾往前)花5步走到他,则当前路径如果花2步或3步走到它的一定是遗漏了的,直接剪掉。
只过了50%,TLE。

import java.util.*;
public class Main21 {
    static Map<Integer,Set<Integer>> map;
    static int n;
    static List<Integer> result;
    static int[] visited;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t>0){
            n = scanner.nextInt();
            int m = scanner.nextInt();
            map = new HashMap<>();
            result = new ArrayList<>();
            visited = new int[n+1];
            for(int i=0;i<m;i++){
                int c = scanner.nextInt();
                int[] tt = new int[c];
                for(int j=0;j<c;j++)
                    tt[j]=scanner.nextInt();
                for(int j=0;j<c-1;j++){
                    Set<Integer> temp = map.getOrDefault(tt[j+1], new HashSet<>());
                    temp.add(tt[j]);
                    visited[tt[j]] = 1;
                    map.put(tt[j+1],temp);
                }
            }
            for(int i=1;i<=n;i++){
                if(visited[i]==1)
                    continue;
                List<Integer> list = new ArrayList<>();
                list.add(i);
                find(i,list);
            }
            if(result.size()==0)
                System.out.println("NO");
            else{
                Collections.reverse(result);
                for(int i=0;i<result.size()-1;i++)
                    System.out.print(result.get(i)+" ");
                System.out.println(result.get(result.size()-1));
            }
            t--;
        }
    }
    public static void find(int x,List<Integer> list){
        if(result.size()!=0)
            return;
        if(list.size()==n){
            result = list;
            return;
        }
        if(!map.containsKey(x))
            return;
        for(int e:map.get(x)){
            List<Integer> list1 = new ArrayList<>(list);
            list1.add(e);
            find(e,list1);
        }

    }
}

3. 技能加点

题目描述

游戏中基础伤害为1,有n个技能,每个技能触发的概率为a[i],触发能造成w[i]倍的伤害,现有k点可以加到技能上,每个技能每加一点,触发概率提升1%,最高到100%。求最大期望伤害。
为方便计算,最后结果乘100的n次方,最后再取模1000000007.

输入

第一行t,表示有t组数据
接下来每组数据:
输入n和k
接下来n行,每行两个数,分别为初始a[i]和w[i]

输出

最大期望伤害

解析

用堆保存目前技能的触发概率和伤害,每次取堆头元素概率+1即可。关键是堆的两个技能之间的比较函数怎么写。
如果一个技能已经加满100,直接取另一个技能。
如果两个技能伤害一样,则取当前触发概率小的那个。
其他情况,先假设加到技能1上,算出伤害t1,再假设加到技能2上,算出伤害t2,对比t1和t2,谁大取谁即可。

import java.math.BigInteger;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main3 {

    static class Point{
        int a;
        int w;

        public Point(int a, int w) {
            this.a = a;
            this.w = w;
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while(t>0){
            int n = scanner.nextInt();
            int k = scanner.nextInt();
            t--;
            int[] a = new int[n];
            int[] w = new int[n];
            Queue<Point> q = new PriorityQueue<>(new Comparator<Point>() {
                @Override
                public int compare(Point o1, Point o2) {
                    if(o1.a==100)
                        return 1;
                    if(o2.a==100)
                        return -1;
                    if(o1.w==o2.w)
                        return o1.a-o2.a;
                    long t1 = ((o1.a+1)*o1.w+(100-(o1.a+1)))*(o2.a*o2.w+(100-o2.a));
                    long t2 = (o1.a*o1.w+(100-o1.a))*((o2.a+1)*o2.w+(100-(o2.a+1)));
                    return (int)(-t1+t2);

                }
            });
            for(int i=0;i<n;i++){
                a[i] = scanner.nextInt();
                w[i] = scanner.nextInt();
                q.add(new Point(a[i],w[i]));
            }
            while(k>0){
                Point p = q.poll();
                if(p.a<100)
                    p.a++;
                q.add(p);
                k--;
            }
            BigInteger res = BigInteger.valueOf(1);
            while(q.size()!=0){
                Point p = q.poll();
                res = res.multiply(BigInteger.valueOf(p.a  * p.w + (100 - p.a)));
                res = res.mod(BigInteger.valueOf(1000000007));
            }
            System.out.println(res.intValue());
        }
    }
}

全部评论

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

推荐话题

相关热帖

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

近期精华帖

热门推荐