yunayu

分类

题解(1)

/ 注册

全部文章（共12篇）

题解 | #计数#（含乘法逆元讲解）

我爱数学！我爱数学！我爱数学！从前有一位老师说，如果你想学好一个学科，只需要每天早上醒来，大喊三遍你爱它。所以说，数学到底是什么呢？一路走来，她不断变换着样子。从前，她作为一门学科，伴随我们走完完整的学生时代。现在，她化为算法竞赛中的一个板块，藏匿在一道道题目描述中,等待着我们的造访。我常认...

2026-01-29

24 20

题解 | #计数#（含乘法逆元讲解）

我爱数学！我爱数学！我爱数学！从前有一位老师说，如果你想学好一个学科，只需要每天早上醒来，大喊三遍你爱它。所以说，数学到底是什么呢？一路走来，她不断变换着样子。从前，她作为一门学科，伴随我们走完完整的学生时代。现在，她化为算法竞赛中的一个板块，藏匿在一道道题目描述中,等待着我们的造访。我常认...

数学双指针组合数学

2026-01-29

1 16

题解 | 小苯的最短路（位运算+数学）

猜的。好了不开玩笑了。分析题目，可得任意两点间XOR下路径长度都不会小于它们XOR的结果。这是一个很显然的结果，因为XOR在位与位之间是独立的，且其定义为相同记为0，不同记为1。在本题中值相同的位显然已经最优了，不用考虑。考虑值不同的位(0/1或1/0)，我们不可能找到一个中间值使得这个代价在传递中...

2026-01-28

2 20

题解 | 好好好数组（数学）（证明看这里）

一道很没意思的数学，东分析西分析最后能推出来，但是感觉没什么意思。但是看了一圈题解区为什么没有证明？遂发之。证明都在注释里了，应该还算完备（？有不懂的地方留言或私信我 #include<bits/stdc++.h> using namespace std; #define int lo...

2026-01-25

2 22

题解 | 邮递员送信（单源正反带权最短路）

本题题意是对于每一个点i，向结果累加1->i与i->1的最短路长度。我们知道朴素版Dijkstra可以在O(n^2)的复杂度内处理出单个点到全图的单源最短路。最最朴素的思想是对于每一个点，都去求出其到其余所有点的最短路，但是这样时间复杂度来到了O(n^3)。注意到i->1的最短路等...

2026-01-23

1 14

题解 | #小红删数字（线性dp）#

讲讲思路最近做了各种dp，DAG上dp，分层dp，换根dp，AC自动机上dp......所以看到这道题第一眼就发现这是一个无后效性的线性递推。为什么是线性？因为某一轮各结果的方案数完全取决于上一轮各结果的方案数。不难发现，本题虽然比较大，但模数特别小，所以可以实现的状态转移。如何构...

2026-01-20

4 23

题解 | 阅读理解（std::map）

stl签到题。写一个从string映射到set的map即可，其中set的作用是存储包含当前string的段落索引。使用set替换vector是为了去重。 #include<bits/stdc++.h> using namespace std; int n, m, t; string s;...

2026-01-19

1 14

题解 | 护花使者 [贪心交换论证（Exchange Argument）]

贪心中很重要且典型的一种策略：交换论证。结论：存在最优策略序列，使得毁坏花朵总数最少，当且仅当：考虑这个序列中的任意一对相邻点 a，b，若 a 在 b 之前送走，均有 a.time*b.harm<=b.time*a.harm.证明：假设存在一种策略序列，存在相邻点 a b 使得 a.time*...

2026-01-18

1 22

题解 | 有趣的区间（补集思想+组合数学）

很显然的补集思想+组合数学。不难得出包含任意奇数的区间都为有趣的区间，单步容斥可得所有区间个数减去无趣区间个数即为有趣区间个数，而无趣区间为全为偶数的区间。优化计数可用组合数学，即连续的最大无趣区间包含的无趣区间个数只与区间长度有关，因此可实现时间复杂度为的计数。天冷了，请多喝热水，祝您拥有美好的一...

2026-01-17

3 20

题解 | 【模板】拓扑排序

拓扑排序板子，如果是刚接触图论的话这个主要是用来判环，还是比较好用和好写的。原理是不断删去入度为0的点，这样环外的点会不断从叶子脱落(离环最远的点姑且称作叶子)，而环上的点会被天然地保留下来。具体实现是使用队列存储还未删去的入度为0的节点。初始时遍历每个节点判断入度是否为0，若为叶子则入队。初始化结...

2026-01-16

3 22