米哈游秋招笔试

给定一个区间，在这个区间内找到满足条件的三元组个数：

\begin{aligned} l & \leq a < b < c \leq r \\ max (a, b, c) & < lcm (a, b, c) < \sum (a, b, c) \end{aligned}

🔍 展开代码

1.js

const rl = require("readline").createInterface({ input: process.stdin });
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  const queryTimes = +inputs[0];
  for (let i = 1; i <= queryTimes; i++) {
    const [left, right] = inputs[i].split(" ").map(Number);
    const result = deal(left, right);
    console.log(result);
  }
});

function findLCM(i, j, k) {
  for (let start = k + 1; ; start++) {
    if (start % i === 0 && start % j === 0 && start % k === 0) return start;
    // 不超时的关键
    if (start === i + j + k) return -1;
  }
}

/**
 * @description 找到区间内 left <= a < b < c
 * 满足 max < lcm < sum
 */
function deal(left, right) {
  // 区间宽度如果不足以容纳三个数
  const width = right - left;
  if (width < 3) return 0;

  let res = 0;

  for (let i = left; i <= right - 2; i++) {
    for (let j = i + 1; j <= right - 1; j++) {
      for (let k = j + 1; k <= right; k++) {
        const lcm = findLCM(i, j, k);
        if (lcm === -1) continue;
        if (k < lcm && i + j + k > lcm) res++;
      }
    }
  }

  return res;
}

击鼓的时候，可能只会响一声，也可能因为共鸣响两声。现在给你一个声音结果，你来推断产生这个声音序列的方案数。

🔍 展开代码

2.js

const rl = require("readline").createInterface({ input: process.stdin });
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  const DIV = 1e9 + 7;
  const queryTimes = +inputs[0];
  for (let i = 1; i <= queryTimes; i++) {
    const sequence = inputs[i];
    const solutionCnt = deal(sequence);
    console.log(solutionCnt % DIV);
  }
});

function deal(str) {
  const arr = [];
  const len = str.length;
  for (let i = 0; i < len; i++) {
    const arrLen = arr.length;
    const cur = str[i];
    if (!arrLen) arr.push(cur);
    else {
      const lastLength = arr[arrLen - 1].length;
      const last = arr[arrLen - 1][lastLength - 1];
      if (last === cur) {
        arr[arrLen - 1] += cur;
      } else {
        arr.push(cur);
      }
    }
  }
  const fibonnaci = [0, 1, 2, 3, 5];
  for (let i = 5; i < 2e5; i++) {
    fibonnaci[i] = fibonnaci[i - 1] + fibonnaci[i - 2]; 
    fibonnaci[i] = (fibonnaci[i - 1] + fibonnaci[i - 2]) % DIV; 
  }

  //   const dp = Array.from({ length: arr.length }, (_, index) => {
  //     const len = arr[index].length;
  //     return fibonnaci[len];
  //   });
  //   return dp.reduce((pre, cur) => pre * cur, 1);
  const dp = arr.map((block) => fibonnaci[block.length]); 
  return dp.reduce((pre, cur) => (pre * cur) % DIV, 1); 
}

给你一个图，对于第一个点，计算到各个点的最优路径。最优路径是指，你可以选择连续的一段子路径，对其权值作给定的异或操作，尽力使得最后总路径整体权值最小。

🔍 展开代码

3.js

const rl = require("readline").createInterface({ input: process.stdin });
const inputs = [];
rl.on("line", (line) => inputs.push(line));
rl.on("close", () => {
  const [nodesCount, edgesCount, xor] = inputs[0].split(" ").map(Number);
  const edges = [];
  for (let i = 1; i <= edgesCount; i++) {
    const [source, target, weight] = inputs[i].split(" ").map(Number);
    edges.push({ source, target, weight });
  }
  const result = findBestPath(nodesCount, edgesCount, xor, edges);
  console.log(result);
});

/**
 * @param {number} nc 顶点个数
 * @param {number} ec 边的条数
 * @param {number} xor 寻找最优代价的路径异或因子
 * @param {Array<{source:number,target:number,weight:number}>} edges 有向边的信息
 * @return {string} 从第一个节点出发到各自节点最小代价
 */
function findBestPath(nc, ec, xor, edges) {
  const result = Array.from({ length: nc }, () => Infinity);
  result[0] = 0;

  const dfs = (start, end, edges) => {
    const path = [];
    // ...
  };

  const optimize = (path, xor) => {
    const len = path.length;
    const dp = new Array(len);
    for (let i = 0; i < len; i++) {
      const currentWeight = path[i].weight;
      const optimizedWeight = currentWeight ^ xor;
      dp[i] = optimizedWeight;
    }

    // 接下来应该找到 dp 的最小子数组和

    return;
  };

  for (let i = 2; i <= nc; i++) {
    // 从第一个节点到第i个节点
    const path = dfs(1, i, edges);
    if (!path.length) {
      result[i] = -1;
      continue;
    }
    // 存在可达路径
    result[i] = optimize(path, xor);
  }

  return result.join(" ");
}

/* ----------------------------------------------------------------------- */
/*                           Answer By ChatGpt                             */
/* ----------------------------------------------------------------------- */

/**
 * @param {number} nc 节点数量
 * @param {number} xor 异或因子
 * @param {Array<{source:number,target:number,weight:number}>} edges 边数组
 * @returns {Array<number>} 每个节点的最优代价
 */
function findBestPath(nc, xor, edges) {
  // 构建邻接表
  const graph = Array.from({ length: nc + 1 }, () => []);
  for (const e of edges) {
    graph[e.source].push({ to: e.target, weight: e.weight });
  }

  const result = Array(nc + 1).fill(-1);
  result[1] = 0; // 节点1到自身为0

  // DFS 找到一条从1到目标节点的路径
  const dfs = (current, target, visited = new Set()) => {
    if (current === target) return [];
    visited.add(current);
    for (const edge of graph[current]) {
      if (!visited.has(edge.to)) {
        const subPath = dfs(edge.to, target, visited);
        if (subPath !== null) return [edge, ...subPath];
      }
    }
    visited.delete(current);
    return null;
  };

  // 优化函数：计算路径最优代价（允许连续子段异或）
  const optimize = (path, xor) => {
    const n = path.length;
    const prefix = [0];
    for (let i = 0; i < n; i++) {
      prefix.push(prefix[prefix.length - 1] + path[i].weight);
    }

    const dp = Array(n + 1).fill(Infinity);
    dp[0] = 0;

    for (let i = 1; i <= n; i++) {
      // 不使用异或
      dp[i] = dp[i - 1] + path[i - 1].weight;
      // 尝试连续子段异或
      for (let j = 0; j < i; j++) {
        const segmentSum = prefix[i] - prefix[j];
        dp[i] = Math.min(dp[i], dp[j] + (segmentSum ^ xor));
      }
    }

    return dp[n];
  };

  // 遍历节点
  for (let node = 2; node <= nc; node++) {
    const path = dfs(1, node, new Set());
    if (!path) {
      result[node] = -1;
    } else {
      result[node] = optimize(path, xor);
    }
  }

  return result.slice(1); // 去掉 result[0]
}

米哈游秋招笔试 ​

米哈游秋招笔试