盛日辉的博客
0%

发表于 分类于

题目

2187A Restricted Sorting

题目意思

现在有一个数组 $a$ ，要将它通过元素交换排序成一个非降序的数组，要求是每次交换的两个元素满足 $|a_i - a_j| \ge k$ 也就是选差值至少为 $k$ 的两个元素。

求最大的 $k$ 。如果没有，输出 $-1$ 。

思路

错误思路

先得到排序之后的正确的数组 $b$ ，

阅读全文 »

发表于 更新于 分类于

题目：3845. 最大子数组异或值

0-1 字典树（异或字典树）

这个如果了解异或字典树就不算难，可惜我比赛的时候没有想到。直接贴代码。

说明一下单调队列里的一个小点。

while max_q and nums[max_q[-1]] <= x: 和 while min_q and nums[min_q[-1]] >= x: 的等号的作用：

  • 代码简洁，如果不加的的话在出队的时候，两个 if left > 要写成 while；
  • 空间复杂度更好。

附两个单调队列的题：

阅读全文 »

发表于 更新于 分类于

EOJ 5201. Kaleidoscope

读完题，心想这不就是个动态规划么，定义 $dp[i]$ 表示铺满 $i$ 行的方案数，然后从 $i-1$ 和 $i-2$ 行转移过来，特殊算一下两行的情况用来转移，这不就好了么。

但是写了八百遍调试了九千遍之后仍然不对。

后来意识到（当然也是问了 Gemini 得到了正确思路后），最后铺满，并不是只能从之前的铺满的状态转移过来，它完全可以从第 $i-1$ 行伸出一些到第 $i$ 行然后仍然可以铺满的。

所以这道题的正确思路是状压DP。

定义每一列的格子的占有情况为二进制数 $s$，其中 $1$ 表示有棋子 $0$ 表示没有棋子。用递归的方式分别计算所有状态对应的“下一个”状态是什么及其数量。

具体的看代码吧，这里想再说一下动态规划的初始值和最后的返回值为什么都是 $dp[0]$。因为 $dp[s]$ 可以理解成是第 $i - 1$ 行留给第 $i$ 行的状态是 $s$，一开始棋盘的空的，可以认为是第 $0$ 列（棋盘的列从 $1$ 开始）留给第 $1$ 列的是 $0$ 。同样的，当所有格子都铺满了，可以认为最后留给第 $m+1$ 列的状态是 $0$。用 Gemini 的话来说，$0$ 状态相当于「收口」。

阅读全文 »

发表于 更新于 分类于

题目

题目链接：https://acm.ecnu.edu.cn/problem/5200/

思路

读完题只是隐约感觉可以用二分，但没有别的任何想法了。

于是问了 Gemini G 老师，它提示了可以用 尺取法 和 动态规划 来做。因为答案必定是由两个子数组的和相减得到的，而数据规模只有 $100$，因此可以枚举出所有的子数组和，然后排序之后利用尺取法即同向双指针来找到两个数作为划分之后所有区间的最大、最小的子数组和，判断这样的最大、最小子数组和能否被成功划分出来。

尺取法就像在序列上移动的一条“毛毛虫”或一个“伸缩滑窗”：它通过同向交替移动左、右两个端点，在 $O(n)$ 时间内高效地扫描出所有符合条件的区间。

简单来说，就是右端点负责扩张以寻找可行解，左端点负责收缩以寻找最优解。

如何判断呢？

G 老师给的方法是动态规划。定义 $dp[i]$ 表示数组的前 $i$ 个数字，是否能被合法地划分为若干个区间，使得每个区间的和 $S$ 都在范围 $[L, R]$ 之内。对于每一个位置 $i$ (从 $1$ 到 $n$)，尝试枚举上一个区间的结束位置 $j$：

阅读全文 »

发表于 更新于 分类于

题目链接：https://acm.ecnu.edu.cn/problem/3462/

也是一道执着地优化 Python 的一道题。思路并不太难，试填法加连通性判断就行，连通性判断可以 BFS 、并查集等好多方法了。

主要记录一些优化 Python 的点，因为同样的思路，C++ 就能轻松过而 Python 就是不行。

输入

生成器不如 ptr 指针读。

生成器法代码如下：

这个方法，不如

阅读全文 »

发表于 更新于 分类于

一道用 Python 一下子就一行带走的题，但竟然还有高级做法……

题目

题目链接

Python 一行流

也有写成 print(int(eval(input()))) 这样的。但我觉得题目里的 / 应当是 整除 ，最好换成 Python 的 // 更好一些。

不过在负数的情况下，Python 的整除和 C/C++ 的整除还不一样。Python 的 -5 // 2 结果是 -3 ，而 C++ 里 -5 / 2 的结果是 -2 。

双栈模拟

阅读全文 »

发表于 更新于 分类于

线段树基础

线段树可以在 $𝑂(log⁡𝑁)$O(\log N) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。

原理

一些问题与解释

1. 线段树的大小

假设数组的大小是 $n$ ，把它们全部放在底层，满足这样的最小的满二叉树的高度是 $\lceil log_{2}{n} \rceil + 1$ （根节点高度是 $1$ ），结点个数是 $2^ {\lceil log_{2}{n} \rceil + 1} - 1$ ，又因为线段树的下标从 $1$ 开始，因此总的空间就是 $2^{\lceil log_{2}{n} \rceil + 1}$ ，即 $2 << (n-1).bit_length()$ 。

几坨莫名其妙的东西

$\lfloor \log_2 n \rfloor = n.bit_length() - 1 = \lceil \log_2 (n+1) \rceil - 1$

$\lceil \log_2 n \rceil = (n-1).bit_length()= \lfloor \log_2 (n-1) \rfloor + 1$ （当 $n > 1$ 时）

$2^{x} => 1 << x => 2 << (x - 1)$

阅读全文 »

发表于 更新于 分类于

直接到最重要的地方。

题目

2026. Telephone Lines

题目翻译理解

一共有 $N$ 个电线杆，其中有 $P$ 对电线杆之间可以连电缆。现在要选一些可连接的电线杆对，使 $1$ 号电线杆和 $n$ 号电线杆连接起来。电话公司可以为 $K$ 根电缆免费，最终收费为需要收费的最长的那根电缆（费用等于长度）。问最少费用是多少？

思路

二分

题目问的是需要支付的最长的那根费用的最小值是多少，是一个最小化最大值问题，可以考虑用二分。

阅读全文 »

发表于 更新于 分类于

输入输出

buffer.read() 字节流读入

  • Python 原生 input() / sys.stdin.readline() 逐行读入的问题， 面对题目 m≤1e6 行数据读入，会触发1e6 + 次 IO 系统调用，而 Python 作为解释型语言，对「频繁系统调用」极度敏感；
  • 普通sys.stdin.read()是字符流读取，buffer.read() 是字节流读取，跳过字符编码转换，速度更快。
  • sys.stdin.buffer.read().split() 会把字节流按空白分割成字符串元素列表，ptr 是遍历这个列表的元素索引。

sys.stdout.write() 代替 print()

Python 原生print()函数并非底层输出，包含大量冗余操作：

  • 自动添加换行符、格式化校验；
  • 内置输出缓冲机制，会额外占用内存并增加处理耗时。
阅读全文 »

发表于 更新于 分类于

这道题有点折磨。首先是思路不太简单，用 ChatGPT 的话来说，就是有着“三层‘逼迫’”——当然，对于大佬来说可能也是常规了。然后是 Python 的问题，一直超内存，最后是 Gemini 优化后终于过了。因此在这里记录一下。

题目

题目链接：https://acm.ecnu.edu.cn/problem/3681/

思路

先给出一个判断一个数与一个数组的中位数之间大小关系的方法：

假设一个数为 $X$，数组的中位数是 $M$，将数组中大于等于 $X$ 的数看作 $1$ 、小于 $X$ 的数看作 $-1$，则如果整个数组的和小于 $0$ ，则 $X \gt M$，而如果和大于等于 $0$，说明 $X \le M$。

因为这道题里中位数是排序后的第 $\lfloor \frac{n}{2} \rfloor + 1$ 个，所以当 $X == M$ 的时候，和大于或者等于 $0$ 。

对于这道题，直接求非常难，转换为判定性问题，即假定结果是 $X$，是否存在一条从 $1$ 到 $n$ 的路径中位数 $M >= X$ 。

怎样判断存在？这里要用 拓扑排序 和 动态规划 了。首先用前面的方法假设一个数 $X$ 进行权值转换，定义 $dp[i]$ 为结点 $1$ 到 $i$ 的最大权值和（从 $1$ 到 $i$ 会有好多路径，每个路径都会有一个权值和，取最大的那个作为 $dp[i]$ ），若 $dp[n] >= 0$，说明存在一条 $1$ 到 $n$ 的路径中位数 $M \ge X$ ，否则说明 $M \lt X$ 。

阅读全文 »

发表于 更新于 分类于

题目

这里主要是记一下对 84 题灵神题解中的代码的理解。

三次遍历

这里主要抓住在最后遍历的时候，枚举的 $h$ 是矩形的高，$l$ 和 $r$ 是在这个高的情况下左右各可以到多远，开区间 $(l,r)$ 构成矩形的宽，就可以了。

两次遍历

在上面方法中 $left$ 的遍历中，弹出栈顶的条件是：$h <= 栈顶$ ，而 $h$ 一定是在栈顶的右边（后遍历到），所以，弹出栈顶的这个动作，其实蕴含着，$h$ 是栈顶右边最近的小于等于它的柱子。

阅读全文 »

发表于 更新于 分类于

在一些计数问题中，有的时候需要预处理组合数。这里有两种方法：

  1. 动态规划（杨辉三角），用于规模较小的情况；
  2. 阶乘 + 逆元，用于规模较大的情况。

动态规划（杨辉三角）

计算 $C(n,k)$ ，从 $n$ 个里面取 $k$ 个，从动态规划的角度来思考可以看成以下两种情况的和：

  1. 第 $n$ 个选，在前 $n-1$ 个里再选 $k-1$ 个；
  2. 第 $n$ 个不选，在前 $n-1$ 个里再选 $k$ 个。

因此，$C(n,k)=C(n-1,k-1) + C(n-1,k)$ ——将杨辉三角“变个形”，可以发现这和杨辉三角的计算规则是一致的。

代码

阅读全文 »

发表于 更新于 分类于

记录一下抠二分查找细节的过程。

// 运算符

是除了之后向下取整。

对于(left+right)//2来说，奇数个就正好是中间，偶数个会更靠近left一些。

关于区间的讨论

左闭右闭

阅读全文 »