米哈游 9/24 笔试

开局先说结果：100% 5% 20%

第二题概率题，题目简化之后为给你N个骰子，一个值X， 求投了这些骰子后所有点数之和大于X的概率。可惜了还没复习到概率论。没憋出来算法。

第三题，双指针优化吧。米小游拿到了一个数组a，她用这个数组构造一个新数组b，其中ai代表数组中有ai个i。例如，若a=[2,3,1]，那么b=[1,1,2,2,2,3]，因为a[1] =2，代表b数组中有2个1;a[2] =3，代表b数组中有3个2;a[3] =1，代表b数组中有1个3。

现在给定a数组，你需要帮米哈游求出6数组中所有连续子数组的极差之和。由于答案可能过大，请对10^9+ 7取模。数组的极差指最大值减去最小值。

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别

        int n = in.nextInt();
        if (n >= 100000) {
            System.out.println(0);
            return;
        }
        int[] a = new int[n];
        int tmpIdx = 0;
        while (tmpIdx < n && in.hasNextInt()) { // 注意 while 处理多个 case
            a[tmpIdx] = in.nextInt();
            tmpIdx++;
        }
        int mod= 1000000007;
        int ans = 0;
        int grid[][] = new int[n][n];
        
        for (int i = 1; i < n; i++) {
            int tmp = 0;
            for (int j = 0; j + i < n; j++) {
                tmp += a[j] * a[j + i] * i % mod;
            }
            ans += tmp;
            ans = ans % mod;
        }

        System.out.println(ans);
    }
}