2025年2月16日
ABC393D题解
摘要： 大概评级：黄。 签到题。 显然，我们需要找到所有的 \(1\) 的位置，然后看其它的 \(1\) 靠拢过来需要几次操作，然后对于每个位置的答案取个最小值就好了。 直接暴力肯定是不行的，考虑优化计算其它的 \(1\) 靠拢过来需要几次操作的过程，首先为了方便，我们将当前位置设为 \(i\)，将 \(i 阅读全文
posted @ 2025-02-16 21:45 林晋堃 阅读(49) 评论(0) 推荐(0)
ABC393F题解
摘要： 大概评级：绿。 一看到这种题目，就知道肯定是数据结构题，我们首先用一个众所周知的二分来求出 \(pos\) 数组，\(pos_i\) 表示以 \(i\) 结尾的最长上升子序列的大小，然后将询问离线，弄一个 vector，命名 \(s\)，把询问中每个 \(R_i\) 为 \(i(1 \le i \l 阅读全文
posted @ 2025-02-16 21:25 林晋堃 阅读(45) 评论(0) 推荐(0)
2025年2月11日
题解：洛谷P11557 [ROIR 2016 Day 2] 有趣数字
摘要： 题目传送门。 考虑数位 dp，也就是记忆化搜索，设置一个搜索函数 \(dfs\)，有三个参数，一个是当前位数，表示搜到哪一位了，一个是从第一位到上一个位数是否全部顶上界，从第一位到上一位全部顶上界的意思是从第一位到上一位是否和对应的 \(a\) 的数位上的数相同（\(a\) 指的是搜索的字符串），第 阅读全文
posted @ 2025-02-11 22:26 林晋堃 阅读(68) 评论(0) 推荐(0)
题解：SP6517 JOCHEF - Farmer Sepp
摘要： 怎么题解全是 dp？可以用笛卡尔树啊！ 题目传送门。 笛卡尔树的介绍 笛卡尔树，是一种二叉搜索树，它满足如下条件： 每个节点的编号满足二叉搜索树的性质。 每个节点的权值满足小根堆或大根堆的性质。 大概是这个样子： 笛卡尔树的建树 请看这里。 笛卡尔树的用途 它可以用来解决区间最值问题，它有一个重要性 阅读全文
posted @ 2025-02-11 22:24 林晋堃 阅读(29) 评论(0) 推荐(0)
洛谷P4390 [BalkanOI2007] Mokia 摩基亚 题解
摘要： 题目传送门。 想必 我的另外一篇题解 已经把这道题的思路说的很清楚了，但是那道题是把所有的修改全部告诉你，然后再一个一个问你矩阵和，但是这道题他是修改中夹着询问，但是没有关系，我们照样可做。 考虑将所有询问或修改存起来，因为我的另外一篇题解的那个思路还支持修改，那我们只需要将所有修改当成那个题里的 阅读全文
posted @ 2025-02-11 22:23 林晋堃 阅读(32) 评论(0) 推荐(0)
洛谷P3755 [CQOI2017] 老C的任务 题解
摘要： 前言：这个分块和刚被撤下的不同，因为这个分块时间复杂度正确，能通过所有 hack。 题目传送门。 有没有什么可以不用离线都能解决问题的简单算法？答案是分块！！ 60pts 首先遇到这个题目，先写一个比较暴力的 \(O(mn)\) 的算法，先排序，降掉一维，剩下一维询问时直接两个二分找到左端点和右端点 阅读全文
posted @ 2025-02-11 22:22 林晋堃 阅读(54) 评论(0) 推荐(0)
洛谷P2701 [USACO5.3] 巨大的牛棚Big Barn 题解
摘要： 怎么题解全是清一色的 dp？可以用笛卡尔树啊（虽然麻烦了很多，但是我热爱）！ 题目传送门。 笛卡尔树的介绍 笛卡尔树，是一种二叉搜索树，它满足如下条件： 每个节点的编号满足二叉搜索树的性质。 每个节点的权值满足小根堆或大根堆的性质。 大概是这个样子： 笛卡尔树的建树 请看这里。 笛卡尔树的用途 它可 阅读全文
posted @ 2025-02-11 22:20 林晋堃 阅读(101) 评论(0) 推荐(0)
洛谷P1191 矩形 题解
摘要： 笛卡尔树的介绍 笛卡尔树，是一种二叉搜索树，它满足如下条件： 每个节点的编号满足二叉搜索树的性质。 每个节点的权值满足小根堆或大根堆的性质。 大概是这个样子： 笛卡尔树的建树 请看这里。 笛卡尔树的用途 它可以用来解决区间最值问题，它有一个重要性质：当这个笛卡尔树为小根堆时，\(\min_{i = 阅读全文
posted @ 2025-02-11 22:18 林晋堃 阅读(67) 评论(0) 推荐(0)
ABC391F题解
摘要： 不加火车头（不吸氧）不开快读全部 long long 提交记录。 使用了我所知的三种优化后的提交记录（最慢点还是没有在一秒内跑过啊）。 做法非常的妙，我们先将 \(A,B,C\) 这三个数组降序排序，我们设 \(f(i,j,k) = A_iB_j+B_jC_k+C_kA_i\)，由于 \(f(i,j 阅读全文
posted @ 2025-02-11 22:03 林晋堃 阅读(36) 评论(0) 推荐(0)
ABC391D题解
摘要： 前置知识： map priority_queue 思路 考虑预处理每一个图块在第几秒后会被删除。 如何预处理？我使用了一种非常暴力的做法，首先处理的过程肯定是从下往上的，于是每一个图块能被删除一定是它对应的每一列都至少有一个图块，而且每次我们肯定都是选择这个图块对应的每一列的离最下面最近的图块去拼成 阅读全文
posted @ 2025-02-11 22:00 林晋堃 阅读(52) 评论(0) 推荐(0)