序言

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());
        }
    }
}