神策笔试

public class IPV6转数字 {
    /**
     * 大致题意有n行数据 (但不知道n是多少)
     * 计算每一行IPV6格式的串的10进制数是多少，但可能不满足格式
     * 不能以0开头  0可以使用省略写法  a.0.b=> a..b 但是开头和结尾不可以省略
     * 1.0.0.0.0.0.9===> 1......9或者1.....0.9等等情况
     * 每一部分是8个bit组成的10进制数 左边是高位右边是低位
     *
     * 输入可能含 !@等特殊字符
     * 输出  n行结果如果某行非法那一行输出-1
     *
     * 自己分析出：
     *  ipv6的合法格式 由点分割的为7部分 每一部分要么空要么 是数字
     *  当前部分合法就左移到对应的高位部分
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s = sc.next();
            System.out.println(parse(s));
        }
    }

    static long parse(String s) {
        // 开头结尾不能是0或省略写法
        if (s.charAt(0) == '.' || s.charAt(s.length() - 1) == '.')
            return -1;
        String[] nums = s.split("\\.");
        // 必须被分为7部分 每部分的值[0,255] (11111111) = (1<<8)-1=255
        if (nums.length != 7)
            return -1;
        long res = 0;
        try {
            for (int i = 0; i < nums.length; i++) {
                long x;
                //这部分 很容易忽略解析出x=0时，如果i==0这就不合法了
                if (nums[i].length() == 0 || ((x = Integer.parseInt(nums[i])) == 0 && i != 0)) {
                    continue;
                } else if (x > 255 || x < 0 || x == 0) {
                    return -1;
                }
                // 当前x只是把这部分的10进制算出来 还要左移到对应的位上去
                // ________.________.________.________.________.________.________
                //     a.b.c.d.e.f.g
                //    算出x=g时不需要移位他就在自己对应的2进制位上
                //    算出x=f时 需要左移8位
                //    同理算出x=e时需要左移 16位
                res += x << (nums.length - i - 1) * 8;
            }
        } catch (Exception e) {
            // 解析x出异常就直接捕获异常得了 懒得特判了
            return -1;
        }
        return res;
    }
}

public class 构造期待 {
    /**
     * 声明：原题目并不叫这个我只是利用大致题意捏的
     * 题目大致描述如下
     * 连续n天的股票价格
     * a0 a1 a2 a3 .... an-1
     * 找到2支股满足: (股票价格之和 - 与相距天数) 最大
     * 大致思路：
     *  题意也就是：j > i,  max{ aj + ai - (j - i) }
     *  等价转化并构造出： x = aj -j + ai + i
     *  这样在跑一遍时  当前的  aj - j是固定的 只需要找到以前最大的ai + i,那么当前的x最大
     *  相当于是对以前的一个期待， 期待一个最大的 ai + i
     *  构造完x，那么很容易想到使用大顶堆保存 当前遍历元素 aj + j
     *
     *
     *  类似的：对于哈西专题经常有这种期待比如当前有前缀和，期待一下以前的某个前缀和来满足题目要求的某种性质
     */
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        String s = sc.nextLine();
        String[] ss = s.split(" ");
        int[] a = new int[n];
        for (int i = 0; i < ss.length; i++) {
            a[i] = Integer.parseInt(ss[i]);
        }

        PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.reverseOrder());
        int x = -1;
        for (int j = 0; j < a.length; j++) {
            if (!q.isEmpty()) {
                x = Math.max(q.peek() + a[j] - j, x);
            }
            q.offer(a[j] + j);
        }

        System.out.println(x);


    }
}

public class 罗马 {

    static int N = (int) 1e6 * 3;

    /**
     * 罗马编号为始终是1，其他城市编号都大于1
     * 各城市有道路相连 组成一颗树形结构 a,b从出发点只朝着罗马前进问最早相遇在那座城市
     * a，b可以停下等对方，也可以走
     * 输入描述：
     * 第一行 n 表示n条道路两
     * 接下来n行 每行2个数 道路2端的城市编号
     * 最后一行是2座出发城市
     *
     * 输出描述：
     * 输出一行 ： 相遇最早的城市
     */
    public static void main(String[] args) {
        // write your code here

        // 题目很类似最近公共祖先
        // 使用标记法lca 只跑80%
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        List<Integer>[] g = new List[N + 1];
        Arrays.setAll(g, k -> new ArrayList<Integer>(10));
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            g[a].add(b);
            g[b].add(a);
        }
        int a = sc.nextInt(), b = sc.nextInt();

        ArrayDeque<Integer> q = new ArrayDeque<>();

        int[] p = new int[N + 1];
        boolean[] st = new boolean[N + 1];
        st[1] = true;
        q.add(1);
        while (!q.isEmpty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                int x = q.poll();
                for (int y : g[x]) {
                    if (!st[y]) {
                        p[y] = x;
                        st[y] = true;
                        q.offer(y);
                    }
                }
            }
        }

        boolean[] v = new boolean[N + 1];
        mark(v, p, a);
        int j = mark(v, p, b);
        System.out.println(j);
    }

    static int mark(boolean[] v, int[] p, int x) {
        for (int i = x; i >= 1; i = p[i]) {
            if (v[i])
                return i;
            v[i] = true;
        }
        return -1;
    }
}