牛客周赛 Round 10 解题报告 | 珂学家 | 三分模板 + 计数DFS + 回文中心扩展

---

前言

---

整体评价

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

---

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

#include <bits/stdc++.h>using namespace std;int main() {int n;cin >> n;vector<int> arr(n);for (int i = 0; i< n; i++) {cin >> arr[i];}int res = 1;int j = 0;while (j < n) {int k = j + 1;while (k < n && abs(arr[k - 1] - arr[k]) <= 1) {k++;}res = max(res, k - j);j = k;}cout << res << endl;return 0;
}

---

B. 游游的字符重排

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

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

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

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

import java.io.*;
import java.util.*;public class Main {// 计数DFSpublic 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));}}

#include <bits/stdc++.h>using namespace std;using int64 = long long;int64 dfs(const string &s, char last, int mask) {int n = s.length();if (mask == (1 << n) - 1) {return 1LL;}int64 res = 0;for (int i = 0; i < n; i++) {if ((mask & (1 << i)) == 0) {if (s[i] == last || (i > 0 && s[i] == s[i - 1] && (mask &(1 << (i - 1))) == 0) ) {continue;}res += dfs(s, s[i], mask | (1 << i));}}return res;
}int main() {string s;cin >> s;sort(s.begin(), s.end());int64 res = dfs(s, ' ', 0);cout << res << endl;return 0;
}

---

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-6double 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>=0t = 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);}}

---

写在最后