网易互娱 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());
}
}
}
#网易互娱##笔经#
查看19道真题和解析
