前言

整体评价

T2真是一个折磨人的小妖精，写了两版DFS，第二版计数DFS才过。T3是三分模板，感觉也可以求导数。T4的数据规模才n=1000，因此中心扩展的当仁不让。

A. 游游的最长稳定子数组

滑窗经典题

从某个左端点出发，按顺序找到最远的右端点

然后把该右端点变成新的左端点，继续寻找直至结束

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) arr[i] = sc.nextInt();

        int ans = 0;
        int j = 0;
        while (j < n) {
            int k = j + 1;
            while (k < n && Math.abs(arr[k] - arr[k - 1]) <= 1) {
                k++;
            }
            ans = Math.max(ans, k - j);
            j = k;
        }

        System.out.println(ans);
    }

}

B. 游游的字符重排

暴力搜索好像TLE了，而且需要额外处理去重

那如何搜索，可以不考虑去重的情况呢？

可以对每个字母进行频数统计

然后进行dfs，这样有一个好处，就是天然去重，时间复杂度为

import java.io.*;
import java.util.*;

public class Main {

    // 计数DFS
    public static int dfs(int[] nums, int n, int now, int prev) {
        if (now == n) {
            return 1;
        }
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0 && i != prev) {
                nums[i]--;
                res += dfs(nums, n, now + 1, i);
                nums[i]++;
            }
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        char[] str = sc.next().toCharArray();
        Map<Character, Integer> hash = new HashMap<>();
        for (char c: str) hash.merge(c, 1, Integer::sum);
        int[] nums = hash.values().stream().mapToInt(x -> x).toArray();
        System.out.println(dfs(nums, str.length, 0, -1));
    }

}

C. 游游开车出游

三分板子题，该函数为凹函数。

z = y / (v + x*t) + t

该函数先单调递减，然后单调递增

1. 三分板子

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    static double calc(double y, double x, double v, double t) {
        return y / (v + x * t) + t;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        double v = sc.nextDouble(), x = sc.nextDouble(), y = sc.nextDouble();

        // 三分板子
        double l = 0.0, r = 1e9;
        while (r - l >= 1e-7) {
            // 要求1e-6
            double s = (r - l) / 3.0;
            double t1 = l + s;
            double t2 = l + 2 * s;

            double res1 = calc(y, x, v, t1);
            double res2 = calc(y, x, v, t2);

            if (res1 >= res2) {
                l = t1;
            } else {
                r = t2;
            }
        }

        System.out.println(calc(y, x, v, l));

    }

}

2. 求导

f(t) = y / (v + x*t) + t

求导

f‘(t) = -xy / (v + x*t)^2 + 1

求f'(t) = 0 的解

x^2 * t^2 + 2vx*t + v^2 - xy = 0; t为变量， x,y,v都是常数

t'=(-v +/- sqrt(xy)) / x,

不知道，牛客啥时候对latex语法不那么友好了，写起来难受，看的人更难受

因为xy>0， 所以一定有解，同时 t>=0, 因此只有一个可能解

t' = (-v + sqrt(xy)) / x

t' = max(0, t'), 保证t>=0

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    static double calc(double y, double x, double v, double t) {
        return y / (v + x * t) + t;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        double v = sc.nextDouble(), x = sc.nextDouble(), y = sc.nextDouble();

        // 求一元二次方程的根
        double t = (-v + Math.sqrt(x*y)) / x;
        // 保证t>=0
        t = Math.max(0, t);
        System.out.println(calc(y, x, v, t));
    }

}

D. 游游的回文子串

因为n=1000，所以中心扩展就好了

• 同一个区域, 长度为n, 方案数n*(n+1)/2
• 以某个区域为中心，往两边扩展，则线性增长

import java.io.BufferedInputStream;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(new BufferedInputStream(System.in));
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = sc.nextInt();
        }

        long ans = 0;
        long mod = 10_0000_0007l;
        for (int i = 0; i < n; i++) {
            // 枚举某个区域
            long t = arr[i] * (arr[i] + 1) / 2;
            ans = (ans + t % mod) % mod;

            // 中心扩展
            for (int j = 1; i - j >= 0 && i + j < n; j++) {
                if (arr[i - j] != arr[i + j]) {
                    // 长度不等，取最小，通过跳出
                    ans = (ans + Math.min(arr[i - j], arr[i + j])) % mod;
                    break;
                } else {
                    ans = (ans + arr[i - j]) % mod;
                }
            }
        }
        System.out.println(ans);

    }

}

写在最后