京东笔试

第三题可以枚举第一个red出现的位置，然后dp预处理一下长度为i的区间内至少有一个red的情况，扫一遍统计答案就行了，感觉还有更简单的思路。

漂亮串有没有大佬给讲讲

长城力扣2170

长城直接暴力，首先统计出现过的数字种类，然后每次选两个数出来，暴力遍历数组算需要变化的次数就行，时间复杂度o(m*m*n)，m为数字的种类，我当时想的是拿点分就跑，没想到a了

第三题 坐牢

第一题bfs， 第二题贪心找奇偶位置数字出现次数最多的，特别判断最多次数一样的情况， 第三题状态dp，维护长度为7的dp，分别代表 0red + xxx, 0red + xxr, 0red + xre, 1red + xxx, 1red + xxr, 1red + xre, 2red

import java.util.Scanner; public class Main {     static class Info {         int redNotOnlyOne;         int redOnlyOne;         int none;        //构造略     }     public static Info myprocess(int n) {         //dp[i] 表示 长度为i的字符串 中至少包含两个red 只包含一个red 不包含red的情况         Info[] dp = new Info[n + 1];         dp[1] = new Info(0, 0, (int) Math.pow(26, 1));         dp[2] = new Info(0, 0, (int) Math.pow(26, 2));         dp[3] = new Info(0, 1, 17575);         for (int i = 4; i <= n; i++) {             int mod = 1000000007;             long redNotOnlyOne = 26L * dp[i - 1].redNotOnlyOne + dp[i - 3].redOnlyOne;             redNotOnlyOne %= mod;             long redOnlyOne = 26L * dp[i - 1].redOnlyOne - dp[i - 3].redOnlyOne + dp[i - 3].none;             redOnlyOne %= mod;             long none = 26L * dp[i - 1].none - dp[i - 3].none;             none %= mod;             dp[i] = new Info((int) redNotOnlyOne, (int) redOnlyOne, (int) none);         }         return dp[n];     }

只有我在意114514吗（警觉）

考虑组合数学，将red视为整体，在长度n中找两个地方放red，其余地方可以是任意值。： n = 6 =》 1 n = 7 => 可以理解为3个位置，里面挑2个放red，剩余1个字符可以取任意值：C_3^2 * 26 n = 8 => 可以理解为4个位置，里面挑2个放red，剩余2个字符可以取任意值：C_3^2 * 26^2 n = k => 理解为k - 4个位置，最后为C_(k-4)^2 * 26 ^(k - 6) 我也是结束后和同学讨论才想到，笔试时一眼动态，算死人才20%=.=

//漂亮串 AC代码，还可以优化，但是没时间做了 o_v_o. long result = dfs(n, 2, 0); System.out.println(result);     static long max = 1000000007;     static long[][][] record;     public static long dfs(int n, int count, int pre) {//count 表示 red数量 ； pre表示red前缀有几个。         if (record[n][count][pre] != 0) {             return record[n][count][pre];         }         if (n == 0) {             return count == 0 ? 1 : 0;         }         n--;         long ans = 0;         if (pre == 0) {             ans += dfs(n, count, 0) * 25 + dfs(n, count, 1);         } else if (pre == 1) {             ans += dfs(n, count, 2) + dfs(n, count, 1) + dfs(n, count, 0) * 24;         } else if (pre == 2) {             if (count == 0) {                 ans += dfs(n, count, 1) + dfs(n, count, 0) * 25;             } else {                 ans += dfs(n, count - 1, 0) + dfs(n, count, 1) + dfs(n, count, 0) * 24;             }         }         ans %= max;         record[n + 1][count][pre] = ans;         return ans;     } }

第三题动态规划，记录当前长度的0个red和1个red的不同字符串个数，最后用总的排列数减去这两种情况个数

t3考虑容斥，代码如下： mod = 10 ** 9 + 7 N = 2 * 10 ** 6 + 10 fac = [1] * N for i in range(2, N):     fac[i] = fac[i - 1] * i % mod invfac = [1] * N invfac[N - 1] = pow(fac[N - 1], mod - 2, mod) for i in range(N - 1)[::-1]:     invfac[i] = invfac[i + 1] * (i + 1) % mod def c(i, j):     return fac[i] * invfac[j] * invfac[i - j] % mod n = 1000000 ans = 0 mx = n // 3 for i in range(2, mx + 1):     if i % 2 == 0:         ans += (i - 1) * c(i + n - 3 * i, i) * pow(26, n - 3 * i, mod) % mod     else:         ans -= (i - 1) * c(i + n - 3 * i, i) * pow(26, n - 3 * i, mod) % mod     ans %= mod print(ans)

public static void main(String[] args) {         final int mod = (int)1e9 + 7;         Scanner sc = new Scanner(System.in);         int n = sc.nextInt();         int sub = 0;         int hole = 3;         long res = 1;         for(int i = 6; i < n; i ++){             res = (res * hole * 26 - sub) % mod;             sub ++;//重复的数量加1             hole ++;//每次插一个洞就多一个         }         System.out.println(res);     } 漂亮串 大佬们，这哪的逻辑有问题，把原本的两个red看成整体，初始洞的数量是3，重复的数量是0，插入一个字母，变成red x red，现在有4个洞，26*4，重复串为red xx red,减去1，字符串变成red xx red 或red xy red或者x red y red等，然后重复字符串为red xxx red，有两个，或者red xxy red和red xyy red也是两个，不断迭代，为什么过不了

a几个能进面啊

写半天编程，忘记还有选择了，寄

二维dp

我做的题为什么和你们都不一样

A几个能进面啊 1。8能不

有大佬帮忙看看我这0错那了吗

有哪位大佬能说一下第三题的题意呀。看都看不懂😭😭😭😭