Leptit

题解

/ 注册

全部文章 / 题解（共7篇）

P3372 【模板】线段树 1、P3368 【模板】树状数组 2

对于形如修改部分区间同时对部分区间求和一类问题，我们可以设原数组 ,差分数组为 ,有当需要在区间加上时，修改和两点即可，问题是如何快速求出给定区间的和。也即求形如的和。将差分数组带入得于是当 , 当 , ... 于是原式化为进一步的有到这里...

C++ 树状数组

2025-12-17

0 20

P1072 [NOIP 2009 提高组] Hankson 的趣味题

题目的意思很简单，找到一个，其满足那我们可以看出，一个必要条件是：是的倍数，同时是的约数。那我们可以枚举的所有满足条件的数，时间复杂度，极端情况下，是能去到。首先，枚举的范围是可以降到的，但是其实我们可以进一步的转换思路，与其枚举，不如试着枚举使得 ...

C++ 数学

2025-12-03

0 20

P10484 送礼物

拿到这道题，很容易写一个的算法，可是注意 ,必通不过此题。但是如果能减少一半的搜索树规模，是能在内通过规模的测试样例的，于是我们就想到了双向搜索，具体的做法是：先搜索 ,然后将所有可能的重量存入数组，排序之后再搜索 ,这样的话对于第二趟搜索得到的每一个重量，我们去二分查找第一趟得...

C++ 深度优先搜索二分查找

2025-11-19

0 20

P10480 可达性统计

题目要求一幅图的所有顶点所能到达的顶点数，最直观的想法是通过DFS或BFS暴力搜索，但是在最坏情况下，要访问个顶点和条边，又有个顶点，总的时间复杂度就是而和能去到,别说时间上不允许，空间就先告急了。好在题目中的图是有向无环图（DAG），有良好的性质，那就是可以找到入度为0的顶点进行拓扑排序，这...

C++ 拓扑排序

2025-11-01

0 19

P5440 【XR-2】奇迹

暴力模拟即可，开始我尝试记录每个‘-’的位置，然后遍历pos数组，枚举0-9，然而这种写法很恶心。那么自然想到了搜索，每次访问到‘-’枚举0-9即可，进入下一次搜索，注意终止条件是当index==9时，因为使用的是1-base。然后剔除一些非法日期即可符合题意，这样能过。 #include<...

C++ 深度优先搜索

2025-10-23

0 30

B4414 [GESP202509 三级] 日历制作

方法一：题目要求打印12月的日历，第一行一定是一样的，我们放在一个字符串s中，然后就只剩下两部分需要考虑了，一是从星期几开始，二是一个月要打多少天。第一部分可以这样考虑，题目中已经给出了9月的日历，可以发现是从星期一开始的，也就是没有空格，这点性质很好，我们接下来这样考虑：如果比到9.1这一天每...

C++ 字符串

2025-10-23

0 153

P5194 [USACO05DEC] Scales S

看到题目很容易想到递归，每件物品选或不选即可，时间复杂度,可以过 #include<iostream> #include<vector> void dfs(int& res, int& curr, std::vector<int>& v,...

C++ 深度优先搜索

2025-10-22

0 24