Hello World 2025 蓝桥杯选拔赛题解

ExRoc · 2024-12-21 15:30:43 · 个人记录

T552570 小 hi 的奇妙旅行 Ⅰ

注意数据范围：int 类型数据最大能存约 2\times10^9 的数字，两个 2\times10^9 大小的数据相加会出现溢出错误，需要用 long long 类型

AC 代码示例

一个 N 行 M 列的字符串矩阵中，本来有一个全由 # 字符构成的矩形，但矩形缺了一个口子用 . 字符代替，找到这个缺口的坐标。

AC 代码示例

AC 代码示例

点击链接查看数据生成代码

参考代码

预处理前缀和 sum_i=\sum_{j=1}^i num_j 优化暴力做法
枚举到第 i 个数字时，直接对当前结果取反（即 -sum_i）加上后面 n-i 个数字的和（即 sum_n-sum_i），这样只需要 O(n) 次枚举，每次枚举 O(1) 计算得到结果，对所有枚举结果取最大绝对值
整体时间复杂度 O(n)

AC 代码示例

点击链接查看数据生成代码

参考代码

假设在第 i 个数字进行取反，求后 n-i 个数字在计算过程中可能出现的最大绝对值
如果可以维护计算时出现的最大值与最小值，就可以对每次枚举 O(1) 算出后续计算过程中绝对值的最大值
如果只取出后 n-i 个数字单独组成一个数组，这些数字计算过程的最大（最小）值也就是从第 i+1 个数字往后加的过程中，相对前 i 个数字和的最大、最小偏移量，满足如下公式：

mx_{i+1}=\max\limits_{i<j\leq n}(sum_j-sum_i)=\max\limits_{i<j\leq n}(sum_j)-sum_i

同理

mn_{i+1}=\min\limits_{i<j\leq n}(sum_j-sum_i)=\min\limits_{i<j\leq n}(sum_j)-sum_i

以上 mx_{i+1} 与 mn_{i+1} 排除了前 i 个数字对后面计算的影响，将前 i 个数字的“和的相反数”考虑进去后，就是最终在整个计算过程中的最大、最小值：

ans_{max}=\max_{0\leq i\leq n}(-sum_i+mx_{i+1}) \\ ans_{min}=\min_{0\leq i\leq n}(-sum_i+mn_{i+1}) \\ ans=\max(abs(ans_{max}),abs(ans_{min}))

AC 代码示例

点击链接查看数据生成代码

若 n\geq m：取 n 个数字的前 m 个反复依次加到第 1 到第 m 个位置上，加满 L 轮，问最后哪个位置的数字最大；

若 n<m：将 n 个数字依次加到 m 个位置上，如果 n 个数字用完了再从第 1 个数字开始循环往后加，直到加满 L 轮。

参考代码

若 n\geq m，则只需要考虑前 m 个数字的大小，本题难点在 n<m 的情况
为方便说明，这里以 n=6,m=8,L=5 的情况为例，以下表格中，第 i 行表示第 i 个位置（人），第 j 列表示第 i 个位置被第 j 次被累加（均从 0 开始）

首先观察到，第 0 个位置依次被 h_0,h_2,h_4 累加，第 2 个位置依次被 h_2,h_4,h_0 累加，第 4 个位置依次被 h_4,h_0,h_2 累加，如果 L 足够大，这将是一个在行上以 2 为周期、在列上以 3 为周期的循环，行周期 T_{row}=\gcd(n,m)，列周期 T_{col}=\frac{lcm(n,m)}{m}=\frac{nm}{\gcd(n,m)\times m}=\frac{n}{\gcd(n,m)}
首先以行为周期考虑
- 每 T_{row}=\gcd(n,m) 行为一个周期，因此只需要处理前 i=0,1,\cdots,T_{row}-1 行，就可以 O(1) 推出后面的 i+T_{row},i+2T_{row},...,i+kT_{row} 行
- 第 0,2,4 行对应的 h_i 下标集合均为 0,2,4 循环，且下标的顺序不变，因此对于第 i~(0\leq i<T_{row}) 行，处理出该行的前缀和，后续第 i+kT 行就可以用利用该前缀和循环性质 O(1) 计算出结果
再以每行内的列为周期考虑
- 首先计算出经过 L 轮后，第 i 行有 \frac{nL}{m}+((nL\%m)>i?1:0) 列，其中 \frac{nL}{m} 表示 L 轮经过了完整的列数，最后的 (nL\%m)>i 表示在 nL 无法整除 m 的情况下是否多出一列，若多出一列，则列数加一
- 先处理出前 T_{col}=\frac{n}{\gcd(n,m)} 列的前缀和 sum_i=\sum_j^i h_j~i，列数在 T_{col} 整数倍的部分可以直接用 sum_{T_{col}} 的整数倍乘上去，多出来的部分使用循环下标的前缀和计算

AC 代码示例

点击链接查看数据生成代码