- 博客(100)
- 收藏
- 关注
RSS订阅
原创 《常犯的Mistakes》
每次和机房大佬们一起做题，都感到自己代码能力的低下，总是很久才调出题，而且往往有多处错误，并且很愚蠢。为了警醒自己，并以此提高自己调错能力，从现在起对一些犯的错误进行总结。
2020-06-06 15:07:44
236
1
原创 也许___
也许肩上越是沉重，信念越是巍峨。”在学姐的回忆录上看到这句话，还记得她说“怀着巍峨的信念，我终于走过了高三，前方的路，还很长很长”，当时我还不解地觉得高中就是最长的一段路了，现在才真正懂得前方到底是怎样广阔的通衢。很想要长篇大论的，但不知怎的潜藏的话语又吐露不出来，或许是军训站军姿时的滞望中已经想了太多，惟余浅浅的惆怅和不知所谓的安然。熟悉的代码，陌生的解答，那就缓缓适应，长啸徐行。大学，计科，熟悉又陌生的专业，面对早已遗忘的编程知识，预想更多从未接触的领域，心中除了忐忑紧张，更多的是期待。
2023-09-05 21:44:59
104
原创 浅谈Tarjan（双联通分量）
Tarjan-点双连通分量和边双连通分量点双联通分量边双连通分量若一个连通分量任意两点至少存在两条路径经过的边无重复（即完全不同），则称为边双连通分量（可理解为无重复边，两条路）。定义无向图的割边为：如果去掉无向连通图 $$边双联通分量更简洁的表达方式为：内部无桥...
2020-08-21 08:08:30
266
原创 浅谈 Tarjan（强连通分量算法）
前言做Tarjan\tt TarjanTarjan 的题，屑教练给的课件实在是太La Ji了，于是重新整理一下 Tarjan\tt TarjanTarjan 的思路TarjanTarjan\tt TarjanTarjan算法，用于解决有向图的强联通分量问题。（当然不只是，这里是这样的）在有向图中，若两点任意可达，则两点之间强联通。若有向图任意两点强联通，则称为强连通图。非强联通图的极大强联通子图称作强联通分量。Tarjan\tt TarjanTarjan 算法就是用于找有向图的强联通分量。首先，有
2020-08-20 11:12:54
212
原创 浅谈 ST 表
ST表话说以前都不会ST\tt STST表，现在来学习一波。ST\tt STST表是一种支持离线RMQ\tt RMQRMQ的数据结构。预处理为 O(nlog)O(nlog)O(nlog)。与线段树和树状数组相比更优的是，它的查询时间复杂度为 O(1)O(1)O(1) 而非 O(log)O(log)O(log)。下面来讲讲它的实现。ST\tt STST表的主体是一个二维数组 St[i][j]St[i][j]St[i][j]，St[i][j]St[i][j]St[i][j] 表示 [i,i+2j−1][i
2020-08-13 18:34:12
153
原创 [CF 372C] Watching Fireworks is Fun
题目洛谷思路要求 max∑bi=i−∣ai−x∣\max\sum b_i=_i−∣a_i−x∣max∑bi=i−∣ai−x∣可以拆成 ∑bi−min∣ai−x∣\sum b_i-\min∣a_i−x∣∑bi−min∣ai−x∣定义 dp[i][j]dp[i][j]dp[i][j] 为第 iii 时刻在 jjj 位置的最小代价。发现有些时间是空的，所以稍微改一下：dp[i][j]dp[i][j]dp[i][j] 为第 iii 个烟花绽放时刻在 jjj 位置的最小代价。易得到：dp[
2020-08-13 08:09:46
126
原创 [CF 319C] Kalila and Dimna in the Logging Industry
题目洛谷思路考虑 dp[i]dp[i]dp[i] 为砍掉第 iii 棵树的最小代价，因为 b[n]=0b[n]=0b[n]=0，所以目的是求 dp[n]dp[n]dp[n]考虑计算 dp[k]dp[k]dp[k]。因为 bib_ibi 单调递减，所以砍掉编号 >k>k>k 的树之后，就不会再回来管 kkk，而是向 nnn 奋起直追。这一点似乎很多题解里并没有考虑。所以 dp[k]dp[k]dp[k] 只会由 <k<k<k 的 dpdpdp 来转移，所以我们考虑
2020-08-12 16:30:04
184
原创 [CF 837D] Round Subset
题目洛谷题解似乎并不难，不知道为啥标了道紫题。首先可以判断出，末尾 000 的个数与选的数中 222、555 的最小值有关。那么定义 dp[i][j][k]:dp[i][j][k]:dp[i][j][k]: 前 iii 个数中选 jjj 个，得到 kkk 个 555，能得到 222 的最大个数然而，发现这不是道 01\tt 0101背包吗，怎么多搞了一维——……好吧，太久没做背包了，都忘记了。所以直接定义 dp[i][j]:dp[i][j]:dp[i][j]: 选 iii 个数，得到 jjj
2020-08-10 15:02:04
191
原创 [CF1073E] Segment Sum
似乎就是一道数位dp\tt dpdp的板，只是维数有点多，用状压来开？CodeLL k, a[MAXN], Jw[MAXN];struct node{ LL tot, Sum; node(){} node(LL TOT,LL SUM) { tot = TOT; Sum = SUM; } void Clear() { tot = Sum = 0; } bool Check() { return ~ tot && ~ Sum; }} dp[2][2][MAXN][
2020-08-09 17:48:59
150
原创 [CF 903F] Clear The Matrix
题目洛谷思路这道题一开始还是挺有思路的。首先，我们一列一列地考虑，因为长度最大为 444，所以每次只考虑一个 4∗44*44∗4的矩形就够了。如果固定了某列，现在的矩形就是一个4∗44*44∗4 的，有 161616 格，用状压 2162^{16}216 存下状态是绰绰有余的。而对于确定下一个左上角填入矩形，对于这个 4∗44*44∗4 矩形的影响也是能够计算出来的。于是定义 dp[i][j]dp[i][j]dp[i][j] 为：前 i−1i-1i−1 列都为 ′.′'.'′.′，以第 iii
2020-08-09 17:39:28
227
原创 [CF 757D] Felicity‘s Big Secret Revealed
题目洛谷思路定义 dp[i][j]dp[i][j]dp[i][j] 为： 划分到 iii 位，集合元素状态为 jjj 方案数。转移似乎很简单了，向后枚举断点，记录段值。假设断点为 kkk，段值为 ValValVal，即：dp[k][j∣(1<<(Val−1)]+=dp[i][j]dp[k][j |(1<<(Val-1)]+=dp[i][j]dp[k][j∣(1<<(Val−1)]+=dp[i][j]边界为 dp[i][0]=1dp[i][0]=1dp[i][0
2020-08-09 17:11:42
173
原创 [CF 743E] Vladik and cards
题目戳这洛谷思路似乎想到一个状态，感觉不甚靠谱。正解：似乎和我的思考有一些相似之处，然而我是把出现次数放进 dpdpdp 数组的状态里，这样是不好搞的，这就是我放弃自己思路的原因。而题解里选择的方法是：直接二分这个最少的出现次数——似乎很可行？定义 dp[i][j]dp[i][j]dp[i][j] ：考虑前 iii 位，状态（即为数组出现的不可重集）为 jjj 可得到的最长序列长度。满足二分出来的最小长度 xxx。转移似乎很简单了，考虑 xxx 个和 x+1x + 1x+1 个就好了。Cod
2020-08-08 22:18:43
147
原创 [CF 377C] Captains Mode
洛谷题解首先，只会用到 banbanban 和 pickpickpick，因为 m<=min(n,20)m<=min(n,20)m<=min(n,20)Code#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define MAXM 25#define MAXN (1 <<
2020-08-08 02:12:49
134
原创 [CF 71E] Nuclear Fusion
洛谷似乎就是一道暴搜题，只是用状态记忆化？时间复杂度似乎不会证。Code：LL n, m;string Names[] = {" ","H","He","Li","Be","B","C","N","O","F","Ne","Na","Mg","Al","Si","P","S","Cl","Ar","K", "Ca", "Sc", "Ti", "V", "Cr", "Mn", "Fe", "Co", "Ni", "Cu","Zn" ,"Ga", "Ge", "As" ,"Se" ,"Br" ,"Kr"
2020-08-06 00:09:31
189
2
原创 [CF111C Petya] and Spiders
题目洛谷思路首先，min(n,m)<=6min(n,m)<=6min(n,m)<=6 是很容易判断出来的。于是我想着：这么小的数据范围，能够直接分类讨论吗？但由于是状压dp板块的题，也没有从这方面细想，题解中似乎有分类讨论的做法。想状压dp的做法。由于之前状压dp做得太少，实在是没什么想法。看了题解梳理一下。由于蜘蛛可以往上下左右四个方向走，以及原地待着，我们将题目转化为：在棋盘上选一些点，点可以覆盖上下左右即自身，求最少多少点可以将棋盘完全覆盖。定义 dp[i][k1][k
2020-08-05 15:33:40
143
原创 [CF 629E] Famil Door and Roads
我选择先写题解再做题。思考阶段我们似乎可以考虑计算：总边数 以及 总长度如果 aaa 与 bbb 有祖先关系？总边数： 似乎是 aaa 的子树内方案数乘 bbb 的子树外方案数？ （方案数就是子树大小？）总长度： 这个有点不好算了，难道是： （aaa 的子树内所有路径总长乘 bbb 的子树外方案数）+（bbb 的子树外所有路径总长乘 aaa 的子树内方案数）+（a−ba-ba−b之间链长乘总边数）？如果 aaa 与 bbb 无祖先关系？总边数： 似乎是 aaa 的子树内方案数乘
2020-07-31 16:52:45
156
原创 [CF 1249F] Maximum Weight Subset
题目洛谷题意给定一棵含 nnn 个节点的树，每个节点含一个点权 a[i]a[i]a[i]。现在请你选出一些节点，使得这些节点的权值和最大并且这些节点中任意两个节点的距离都 >k>k>k。并输出这个最大的权值。思路一道似乎有很多时间复杂度做法的题？因为数据规模开的实在是太小了，只有 200200200，所以 n3,n2,nn^3,n^2,nn3,n2,n 都可以过，n4n^4n4 的卡卡也能过？对于很多算法，还没来得及研究，这里讲一种较为常规的 n2n^2n2 的树形 dp\tt
2020-07-30 12:35:16
174
原创 [CF 734E] Anton and Tree
题目洛谷题意有一棵树，每个点初始有黑白色，每次操作将一个同色连通块颜色翻转——至少多少次翻转能让整张图颜色相同。思路首先，可以想到：一开始可以将同色的连通块缩成一个点——这点很显然，就不说明了。缩点后，得到一张黑白分层图。现在是在这张黑白分层图上得到答案。怎么做呢？给出一个结论——答案为缩点后图的直径加一除以二。即记直径为 ddd，Ans=(d+1)/2Ans=(d+1)/2Ans=(d+1)/2证明现在考虑如何证明这个结论：懒得搞图，就不放图了。——刚刚本来还准备证一番，PPL\tt PP
2020-07-30 10:13:59
154
原创 [CF 1223E] Paint the Tree
前言竟然是一道自己做出来的树形dp\tt dpdp！题目洛谷思路很简单（毕竟我都做出来了）。设计 dp[i][0/1]dp[i][0/1]dp[i][0/1] 为 iii 号点是否选父边的答案，考虑转移即可。Codestruct node{ LL v, w; node(){} node(LL V,LL W) { v = V; w = W; }};vector<node> G[MAXN]; LL dp[MAXN][2], n, k;bool cmp(LL
2020-07-30 08:13:51
140
原创 [CF486D] Valid Sets
前言话说自己觉得区间dp\tt dpdp学的还行，但是做题速度慢了些，也不完全是学得太慢的原因，效率也很重要。希望学树形dp\tt dpdp这个版块时能百尺竿头更进一步。题目洛谷话说数据范围是 n,d<=2000n,d<=2000n,d<=2000思路考虑树形dp\tt dpdp，令 dp[i]dp[i]dp[i] 为 iii 为根节点合法子树个数。很显然，如果只这样处理状态进行树形dp\tt dpdp，会有重复状态。这时候，我们选择对 dpdpdp 进行一些限制：我们认为，
2020-07-29 21:00:47
202
原创 [CF 49E] Common ancestor
每当过了一道区间dp后，都觉得自己学懂了。然而再切一道新题——这和区间dp有关系？怎么做？做不来……看来还得不断学习提升自我。
2020-07-29 20:41:41
214
原创 [CF 39C] Moon Craters
思路显然的一个括号问题。首先我们对括号左右端点进行离散化。这个时候，若是使用传统的区间dp\tt dpdp，我们就得到了一个 O(n4)O(n^4)O(n4) 的算法。然而，我们可以减少转移数量：对于固定左右区间端点，我们先固定右端点跑出答案，这时固定左端点——常规做时，我们就应该在 [l,r][l,r][l,r] 枚举断点 midmidmid，然而这步优化的是：使用左端点为 lll，右端点 <=r<=r<=r 的括号右端点作为区间断点——这样下来总共只有 nnn 次转移，均摊后时间复
2020-07-29 12:19:02
248
原创 [CF 888F] Connecting Vertices
《那句话，说得有点深意》小时候，母亲告诉我：dp是智商题，懵懂的我只是点点头，并不懂得。长大后，学区间dp，遥望着JZM AK的身影，我才终于懂得了母亲的话
2020-07-29 10:53:30
214
原创 快速莫比乌斯反演 (FMT) && 快速莫比乌斯变换 (FMI)
前言学习笔记，写此句时还没学懂，暂时没搞清楚标题这俩到底是啥。话说看着别人的博客学的，似乎之前学的 FWT\mathcal {FWT}FWT 的或卷积和与卷积就是 FMT\mathcal {FMT}FMT，而 FWT\mathcal {FWT}FWT 应该是异或卷积。其次，这里的莫比乌斯和数论的莫比乌斯应该有所不同吧，本质上应该是类莫比乌斯形式的一种容斥式子集枚举。话不多说，走起。快速莫比乌斯反演（FMT）问题引入已知俩函数 F(s),G(s)F(s),G(s)F(s),G(s)求Ans(S)=
2020-06-13 16:14:47
224
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人