牛客练习赛#115

A

题目链接

首先统计出每个数的个数cnt[i]，显然只有最大数才可以当作山峰,那么对于每一个数而言,它会有[0, cnt[i]]个自己放在山峰左边,随之山峰右边的数也会确定，共(1 + cnt[i])种情况。

int T = in.nextInt();
long mod = 998244353;
void solve() {
    while (T-- > 0) {
        int n = in.nextInt();
        int max = -1;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int key = in.nextInt();
            map.merge(key, 1, Integer::sum);
            max = Math.max(max, key);
        }
        long ans = 1;
        for (Map.Entry<Integer, Integer> e : map.entrySet()) {
            int key = e.getKey(), v = e.getValue();
            if (key == max) continue;
            ans = ans * (v + 1) % mod;
        }
        out.println(ans);
    }
}

B

题目链接

如果对于l到r的长度不断二分,大于0的次数如果大于等于count的,那么必定存在,反之必不存在,对于x而言最少的操作就是1次,两边都具有单调性,那么可以设mid = (l + r) / 2，那么ans一定位于[l, mid]或[mid + 1, r]之间,对两段区间二分即可找到答案.

int T = in.nextInt();

    void solve() {
        while (T-- > 0) {
            int l = in.nextInt(), r = in.nextInt(), c = in.nextInt();
            int ll = l, rr = r;
            int cnt = (r - l + 1);
            int k = 0;
            while (cnt > 0) {
                k++;
                cnt /= 2;
            }
            if (k < c) {
                out.println(-1);
                continue;
            }
            int lx = ll, rx = (ll + rr) / 2;
            while (lx < rx) {
                int mmid = lx + rx + 1 >> 1;
                if (f(ll, rr, mmid) <= c) lx = mmid;
                else rx = mmid - 1;
            }
            if (f(ll, rr, rx) == c) out.println(rx);
            else {
                lx = (ll + rr) / 2;
                rx = rr;
                while (lx < rx) {
                    int mmid = lx + rx + 1 >> 1;
                    if (f(ll, rr, mmid) <= c) lx = mmid;
                    else rx = mmid - 1;
                }
                out.println(rx);
            }
        }
    }


    int f(int l, int r, int x) { // l <= x <= r
        int cnt = 0;
        while (l <= r) {
            cnt++;
            int mid = (l + r) / 2;
            if (mid == x) break;
            if (mid < x) l = mid + 1;
            else r = mid - 1;
        }
        return cnt;
    }

C

题目链接

可以证明,倾斜度一定存在于两个相邻的数之间(不会证明),使用TreeSet维护相邻两个数的绝对值差值即可,需要维护相对值差值diff.

void solve() {
    int n = in.nextInt(), q = in.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = in.nextInt();
    }
    int[] diff = new int[n];
    TreeMap<Integer, Integer> map = new TreeMap<>(Comparator.comparing(e -> -e));
    for (int i = 0; i < n - 1; i++) {
        diff[i] = arr[i] - arr[i + 1];
        map.merge(Math.abs(diff[i]), 1, Integer::sum);
    }
    out.println(map.firstKey());
    for (int i = 0; i < q; i++) {
        int l = in.nextInt(), r = in.nextInt(), va = in.nextInt();
        l -= 1;
        r -= 1;
        if (l > 0) {
            map.computeIfPresent(Math.abs(diff[l - 1]), (k, v) -> v > 1 ? v - 1 : null);
            diff[l - 1] -= va;
            map.merge(Math.abs(diff[l - 1]), 1, Integer::sum);
        }
        if (r < n - 1) {
            map.computeIfPresent(Math.abs(diff[r]), (k, v) -> v > 1 ? v - 1 : null);
            diff[r] += va;
            map.merge(Math.abs(diff[r]), 1, Integer::sum);
        }
        out.println(map.firstKey());
    }

}