《算法导论》(Introduction to Algorithm)读书笔记
发表于|ACM
|浏览量:
文章作者: Himekawa
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 Himekawaの小屋！
赞助
微信
相关推荐
2024-12-19
图论基础
图的定义 点用边连起来就叫做图。在严格意义上，图是一种数据结构，定义为：graph=(V,E)graph=(V,E)graph=(V,E)。 其中，V={p∣p=(a,b)}V=\{p|p=(a,b)\}V={p∣p=(a,b)}是一个非空有限集合，代表顶点（结点），EEE代表边的集合。 图的相关概念 有向图：图的边有方向，只能按箭头方向从一点到另一点。 无向图：图的边没有方向，可以双向。 结点的度：无向图中与结点相连的边的数目，称为结点的度。 结点的入度：在有向图中，以这个结点为终点的有向边的数目。 结点的出度：在有向图中，以这个结点为起点的有向边的数目。 注：有向图中所有顶点的入度之和等于所有顶点的出度之和。 权值：边的“费用”，可以形象地理解为边的长度。 连通：如果图中结点U，V之间存在一条从U通过若干条边、点到达V的通路，则称U、V 是连通的。如果图中任意两点都是连通的，那么图被称作连通图。 回路：起点和终点相同的路径，称为回路，或"环"。 完全图：一个nnn阶的完全无向图含有$\frac{n(n-1)}{2} 条边；一个条边；一个条边；一...
2025-03-12
几道算法题解
好久没写算法题了，一写才发现自己真忘光了。还好这几题基本上都是暴力题（ 头痛好想睡觉 A-子串分值 第一题一看就有点蒙，读完题发现不难，然后写了个暴力，过了样例，然后很显然地 TLE 了 于是写了个简单的记忆优化，但复杂度还是 O(n2logn)O(n^2logn)O(n2logn) ，所以又爆了 爆两次之后仔细分析了一下，他要求的字符串中总共就 26 个字母，我们不妨从字符出发，求每个字符的贡献度。例如样例是ababc的话，对于第一个a贡献度就是 2，第二个b贡献度就是 4，以此类推。 因为该字符能做出贡献的 substr 中一定只包含一个它，所以我们往左右两边找上一个和下一个它即可。而贡献度 DiD_iDi 的计算方式可由乘法原理得： Di=(i−l)(r−i)D_i=(i-l)(r-i) Di=(i−l)(r−i) 也就是左边字符数+1 乘右边字符数+1。而把两个乘数算出来再相乘的复杂度应该是O(n)O(n)O(n)，按理说是可以过的 那为什么没过呢，因为我忘记开long long了 XD 代码如下 12345678910111213141516171819202122...
评论