hackerchef - 博客园

2025年2月

摘要：原题链接：https://www.luogu.com.cn/problem/P1433 解题思路：此前已详细解析此题的完整思考过程：https://chuna2.787528.xyz/jcwy/p/18056277，这里仅以更简洁的方式重写代码。 100分代码： #include <bits/stdc+ 阅读全文

posted @ 2025-02-09 21:50 hackerchef 阅读(85) 评论(0) 推荐(0)

洛谷题单指南-进阶搜索-P1036 [NOIP 2002 普及组] 选数

摘要：原题链接：https://www.luogu.com.cn/problem/P1036 题意解读：从n个数选k个数之和为素数的方案数。解题思路：仍然采用搜索来枚举子集，只不过不同于https://chuna2.787528.xyz/jcwy/p/17999205 方案二中将每个数选或不选保存到01数组阅读全文

posted @ 2025-02-07 16:20 hackerchef 阅读(153) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-P5445 [APIO2019] 路灯

摘要：原题链接：https://www.luogu.com.cn/problem/P5445 题意解读：给定一个长度为n的01串，一共有q个时刻，对于每个时刻，可能有两种操作：1. 把第x个位置取反 2. 查询a ~ b - 1之间的串在过去有多少个时刻都为1。解题思路：一、朴素想法每个时刻对路灯的阅读全文

posted @ 2025-02-07 12:45 hackerchef 阅读(92) 评论(0) 推荐(0)

2025年1月

洛谷题单指南-线段树的进阶用法-P4602 [CTSC2018] 混合果汁

摘要：原题链接：https://www.luogu.com.cn/problem/P4602 题意解读：在一堆果汁中选出若干果汁，使得最小的美味度最大，且总体价格小于等于g，总体体积大于L，求这个最大的美味度。解题思路：显然，应该对答案进行二分，二分到一个美味度x，那么接下来check()函数要做的事阅读全文

posted @ 2025-01-22 17:08 hackerchef 阅读(61) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-P2839 [国家集训队] middle

摘要：原题链接：https://www.luogu.com.cn/problem/P2839 题意解读：求左端点在 [a,b]之间，右端点在 [c,d]之间的子区间中，最大的中位数。解题思路： 1、直男暴力法枚举左、右端点，然后排序计算中位数，这样的复杂度在n*n*logn，显然不可行。 2、渣男巧妙阅读全文

posted @ 2025-01-21 15:57 hackerchef 阅读(91) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-P3168 [CQOI2015] 任务查询系统

摘要：原题链接：https://www.luogu.com.cn/problem/P3168 题意解读：一个任务管理系统，能够查询在某个时间点运行的任务中优先级最小的 k个任务的优先级之和。解题思路：由于总时间n不超过100000，考虑针对所有时刻建立可持久化线段树，根节点为root[i]的线段树维护阅读全文

posted @ 2025-01-16 17:58 hackerchef 阅读(63) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-P2617 Dynamic Rankings

摘要：原题链接：https://www.luogu.com.cn/problem/P2617 题意解读：动态求区间第k小问题。解题思路：树套树的典型应用，具体阐述参考：https://chuna2.787528.xyz/jcwy/p/18640914 100分代码： #include <bits/stdc+ 阅读全文

posted @ 2025-01-16 09:16 hackerchef 阅读(60) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-Pathwalks

摘要：原题链接：https://www.luogu.com.cn/problem/CF960F 题意解读：按输入顺序从边中选出能首尾相连且权值递增的最多边数。解题思路：依然从最长上升子序列的模型出发，对于输入的第i条边，用a[i]，b[i]，w[i]分别表示起点、终点、权值，设f[i]表示第i条边阅读全文

posted @ 2025-01-15 15:09 hackerchef 阅读(75) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-P3293 [SCOI2016] 美味

摘要：原题链接：https://www.luogu.com.cn/problem/P3293 题意解读：计算每位顾客i认为的[li,ri]之间菜品的最大美味值，美味值是bi^(aj+xi)，bi、xi是与顾客有关的属性，aj是菜品的属性。解题思路：要计算每位顾客的最大美味值bi^(aj+xi)，是一个异阅读全文

posted @ 2025-01-13 17:46 hackerchef 阅读(57) 评论(0) 推荐(0)

洛谷题单指南-线段树的进阶用法-P3157 [CQOI2011] 动态逆序对

摘要：原题链接：https://www.luogu.com.cn/problem/P3157 题意解读：长度为n的序列，序列是1~n的排列，一共m个删除操作，每一个删除之前输出逆序对。解题思路：要计算静态的逆序对，可以通过树状数组、权值线段树等方式，时间复杂度都是O(nlogn) 要计算动态的逆序对，阅读全文

posted @ 2025-01-10 10:52 hackerchef 阅读(78) 评论(0) 推荐(0)

公告