京东秋招笔试

定义幸运数为只由 $3$ 和 $7$ 组成的数字，定义 $f (n)$ 返回大于等于 n 的第一个幸运数。现给定一个区间，对于区间上所有整数值，调用这个函数并返回最后的和。即，对于区间 $[a, b]$ 求出 $\sum_{n = a}^{b} f (n)$ 。

🔍 展开代码

1.js

const rl = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  const T = +inputs[0]; // 数据组数
  const queries = inputs
    .slice(1, T + 1)
    .map((item) => item.split(" ").map(Number));

  // 预生成幸运数
  const lucky = [];
  function dfs(num) {
    if (num > 1e18) return;
    if (num > 0) lucky.push(num);
    dfs(num * 10 + 3);
    dfs(num * 10 + 7);
  }
  dfs(0);
  lucky.sort((a, b) => a - b);

  for (let [L, R] of queries) {
    console.log(deal(L, R, lucky));
  }
});

function deal(L, R, lucky) {
  let sum = 0;
  let cur = L;
  let index = lowerBound(lucky, L);
  while (cur <= R) {
    const next = lucky[index];
    const end = Math.min(R, next);
    sum += (end - cur + 1) * next;
    cur = end + 1;
    index++;
  }
  return sum;
}

/**
 *
 * @description 实际上用的就是二分查找
 * @returns 找到第一个大于等于自身的幸运数
 */
function lowerBound(arr, target) {
  let l = 0;
  let r = arr.length;
  while (l < r) {
    const mid = (l + r) >> 1;
    if (arr[mid] >= target) r = mid;
    else l = mid + 1;
  }
  return l;
}

一共有 $m$ 道可选的菜，请制定未来 $n$ 天的菜单，要求每天与前一天菜的序号相差大于等于 $k$ 。

找到动态规划的状态转移公式如下：

d p [l e n] [l a s t] = \sum_{\begin{matrix} x = 1 \\ | l a s t - x | \geq k \end{matrix}}^{m} d p [l e n - 1] [x]

那么我们最后只要输出 $\sum_{l a s t = 1}^{m} d p [n] [l a s t]$ 就行了。

同时，我们注意到 $| l a s t - x | \geq k \Leftrightarrow x \in [1, l a s t - k] \cup [l a s t + k, m]$ 。

因此过程中我们需要引入前缀和数组来降低遍历复杂度，因此最终结果可以表示为：

p r e [j] = \sum_{x = 1}^{j} d p [l e n - 1] [x]

确定合法区间我们需要在 $[1, m]$ 去除掉 $[l a s t - k + 1, l a s t + k - 1]$ ，最终表达式可以化简为：

d p [l e n] [l a s t] = p r e [l a s t - k] + (p r e [m] - p r e [l a s t + k - 1])

🔍 展开代码

2.js

const rl = require("readline").createInterface({
  input: process.stdin,
  output: process.stdout,
});
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  const [n, m, k] = inputs[0].split(" ").map(Number);
  console.log(deal(n, m, k));
});

/**
 *
 * @description 长度为 n 的序列，数字范围为 1 ~ m，相邻数字差值 >= k
 * @returns 符合条件的序列个数 % 998244353
 */
function deal(n, m, k) {
  const MOD = 998244353; // 取模值，防止结果溢出

  // 初始状态：长度为1的序列，每个数字都可作为序列，因此每个位置的方案数为1
  let dp = new Array(m + 1).fill(1);

  // 从长度2开始计算，直到长度n
  for (let len = 2; len <= n; len++) {
    // 前缀和数组：pre[j] 表示 dp[1] + dp[2] + ... + dp[j]
    const pre = new Array(m + 1).fill(0);
    for (let j = 1; j <= m; j++) {
      pre[j] = (pre[j - 1] + dp[j]) % MOD; // 累加并取模
    }

    // 计算新的dp数组（长度为len时的状态）
    const newDp = new Array(m + 1).fill(0);
    for (let last = 1; last <= m; last++) {
      let res = 0; // 存储当前last的方案数

      // 累加左区间 [1, last - k] 的和（若区间有效）
      if (last - k >= 1) {
        res += pre[last - k];
      }

      // 累加右区间 [last + k, m] 的和（若区间有效）
      if (last + k <= m) {
        // 右区间和 = 总和 - 前缀和[last + k - 1]
        res += pre[m] - pre[last + k - 1] + MOD; // +MOD防止负数
      }

      newDp[last] = res % MOD; // 取模后存入新状态
    }

    dp = newDp; // 更新dp为当前长度的状态
  }

  // 最终结果：长度为n时，所有可能结尾的方案数之和
  return dp.reduce((a, b) => (a + b) % MOD, 0);
}

京东秋招笔试 ​

京东秋招笔试