10.13 模拟赛

2024--梦熊&太戈--NOIP十三连测 #12【订正】 - 比赛 - 梦熊联盟 (mna.wang)

复盘

T1 显然不太会做。样例 4 模拟了好久终于明白了。但是显然不会推广。

\(n\le2\) 是极易的。对于 \(n =3\)，根据刚才模拟样例时的一些思考，感觉好像除了样例的 1 2 4 之外答案都是 \(1\)。于是有 \(40\) 了。

T2 是数学题，好像不难。部分分特别充足。很快放弃了冲正解。

中间有一个问题不太会做：

从 \((0, 0)\) 开始，每一步只能向上/下/左/右走。求恰好 \(m\) 步后走到 \((x,y)\) 的方案数。

后来绕过这个问题做出了 \(60\) 分。但是这个问题貌似也挺重要的。

T3。暴力非常不好打。跳了。

T4。为什么 24 不是半完全幂？哦 \(a < b\)。那这简直太困难了。

部分分。直接按照题意模拟，算不了复杂度，但是 \(10^6\) 跑过了。

提交之前想看看 \(10^8\) 要跑多长时间，结果秒出了。于是将 bool 数组开大至 \(10^8\)。预期 \(50\)。

预计 \(40+60+0+50=150\)。结果 D int 函数没写返回值挂 0 了。

总结

• 好的：
  • 数学直觉还是有的。
• 不足：
  • 做的时候有点懒散，导致 T3 的暴力分拖到了最后导致没打。
  • 低级错误 int 函数无返回值。

知识点

• T1：找规律；
• T2：几何，组合；

题解

A. 硬币

令 \(b_i = a_{i+1}/a_i\)。将 \(b\) 升序排序。答案为 \(\max \log_{b_i}i + 1\)。

B. 狼群

我们将坐标系顺时针旋转 \(45^{\circ}\)，得到 \((x-y,x+y)\)。这样的好处是，原本向上下左右走都只在一个维度上发生改变，而现在必须要在两个维度上同时发生改变。这样我们就能将两个维度独立开。

即每个点现在能到达的点是 \((x\pm 1, y \pm 1)\)。每一维都必须走一步。

接下来我们考虑求解 \(f(x),g(y)\) 表示最终所有狼走到 \(x\) 这条横线的方案数，以及 \(y\) 这条横线的方案数。那么即走到 \(x\) 这条横线，也走到 \(y\) 这条竖线，就代表走到了 \((x, y)\) 这个点。即走到 \((x,y)\) 的方案数是 \(f(x) \times g(y)\)。

我们要对每个点都求一个方案数再加和，即答案为 \(\sum\sum f(x) \times g(y)\)。显然可以化简成 \(\sum f(x) \times \sum g(y)\)。我们考虑 \(f\) 的求解。

令 \(h(i, j)\) 表示在数轴上从 \(i\) 走到 \(j\)，每次只能向前或向后，且总步数恰好为 \(m\) 的方案数。

若能求出来 \(h\)，那么 \(f(j) = \prod_i h(x_i,j)\)，即每个点在第一维上都走到 \(j\) 的方案数的乘积。因为我们只是考虑一个维度所以将其视作在数轴上移动也无妨。

于是问题是如何求解 \(h(i, j)\)。

注意到，有 \(|i-j|\) 步是我们不得不走的。或者说 \(|i-j|\) 是从 \(i\) 走到 \(j\) 的最短步数。如果 \(|i-j|<m\) 则 \(h(i, j)=0\)。

同时，由于如果我们想向后走一步，那么之后必须会有一步向前抵消这一步。也就是说若 \(|i-j|-m\) 是奇数则 \(h(i, j)=0\)。

对于剩下的情况。实际上我们总共向后走多少步是可以计算的，即 \((m - |i-j|)/2\)。于是答案变成从总共 \(m\) 步中选这么多步向后走的方案数，即 \(\dbinom m {(m - |i-j|)/2}\)。