yunxiu

分类

题解(30)

/ 注册

全部文章（共29篇）

p2880

本题要求处理多个区间查询，每次查询需要快速得到区间内最大值与最小值的差值。由于数据规模较大（n ≤ 5×10⁴, q ≤ 1.8×10⁵），需要使用高效的区间查询算法。这里采用 ST表（Sparse Table）算法，其特点是在 O(n log n) 时间内预处理，之后每个查询可在 O(1) 时间...

C++

2025-12-19

0 15

B3852(图)

题目要求对每个节点（从 1 到），将其所有出边指向的节点按照权值从小到大排序，权值相同时按节点编号从小到大排序。然后依次输出每个节点的出边指向的节点序列（按从小到大输出）。解题思路存储结构：使用邻接表（vector<vector<int>> edge...

C++

2025-12-19

0 17

尺取法（双指针）

题目大意给定一个长度为的正整数序列和一个整数，求最短的连续子序列，使其元素和大于等于。输出最短长度，若不存在则输出。解题思路本题是经典的尺取法（双指针）应用。由于序列中所有元素均为正整数，满足单调性，可以使用双指针高效求解：初始化：左右指针 left = 0 和 right =...

C++

2025-12-12

0 27

滑动窗口

题目大意给定一个长度为的序列，求最长的连续子序列，使得子序列中所有元素互不相同。解题思路本题要求最长的不含重复元素的连续子序列，可以使用滑动窗口（双指针）结合哈希表高效解决：滑动窗口：维护一个窗口，保证窗口内元素唯一。哈希表：记录每个元素最后出现的位置，用于快速判断重复和移动左指...

C++

2025-12-12

0 27

poj——2566

题目大意给定一个整数序列（可能包含负数）和一个非负整数目标值，要求找到一个连续子序列，使得该子序列和的绝对值最接近。输出这个绝对值以及子序列的左右端点（下标从1开始，左端点小于等于右端点）。解题思路前缀和与排序：计算前缀和数组 prefix，其中 prefix[0] = 0，pre...

2025-12-12

0 20

双指针+二分查找

题目要求：给定一个长度为 ( n ) 的数组 ( a )，对所有区间 ([l, r])（(1 \le l \le r \le n)），求出每个区间第 ( K ) 大的数（若区间长度 < K，则忽略该区间），然后将所有这些“第 K 大”收集起来，再求这整个集合中的第 ( M ) 大的数。核心...

C++

2025-12-12

0 30

跳石头（二分）

题目分析在一条笔直的河道中，起点和终点之间有 N 块岩石。组委会至多移走 M 块岩石（起点和终点不能移走），要求使得选手在比赛过程中最短跳跃距离尽可能大。需要求出这个最短跳跃距离的最大值。解题思路这是一个典型的最大化最小值问题，通常使用二分答案法求解。具体思路如下：二分答案：假设最短跳跃距...

C++

2025-12-12

0 20

借教室（二分）

题解思路本题要求按顺序处理教室租借订单，当某个订单无法满足时（即从第天到第天中至少有一天的剩余教室数量不足个），立即停止并输出该订单编号。如果所有订单均可满足，则输出 0。优化策略二分：二分查找第一个无法满足的订单编号。假设前个订单可以满足，则尝试更大的；否则，尝试更...

C++

2025-12-12

0 16

哈夫曼树

哈夫曼编码安全判断题解问题本质本题要求判断一个字符串使用哈夫曼编码（Huffman Coding）后的最小总存储位数是否小于等于给定的安全值 m。这实际上是在考察哈夫曼编码的核心原理：通过构建最优二叉树使编码总长度最小化。哈夫曼编码原理深度剖析 1. 哈夫曼编码的核心思想给出现频率高的字符...

C++

2025-12-05

0 35

后缀表达式（压栈+字符串和数字之间的处理）

后缀表达式的计算可以通过栈来实现。后缀表达式的特点是运算符位于两个操作数之后，且不需要考虑运算符优先级，计算顺序严格从左到右。本题中，输入字符串包含数字、运算符（+、-、*、/）、操作数结束符（.）和表达式结束符（@）。需要注意：操作数可能为负数（如 -3 表示为 -3.）。除法运算需向 0 ...

C++

2025-12-05

0 23