STL——std::sort(一次值得记录的排障)
今天在使用std::sort的时候遇到了一个非常奇妙的溢出异常,先给大家看代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; struct node { int x; int y; }; node in[1005]; bool comp(const st...
今天在使用std::sort的时候遇到了一个非常奇妙的溢出异常,先给大家看代码 #include <bits/stdc++.h> using namespace std; typedef long long ll; struct node { int x; int y; }; node in[1005]; bool comp(const st...
本文所有的证明均参见OI Wiki 欧几里德定理 证明参见OI Wiki $$gcd(a,b)=gcd(b,a \; mod \; b)$$ 利用这一重要的定理,容易发现这样的操作递归到最后一定会得到一个\(gcd(m,0)\),此时值为m,我们就可以利用递归法...
我们之前已经大约说到了关于多重背包的问题,是针对每一个物体而言为深度维度去进行的研究,现在让我们将问题研究的尺度从深度向广度延展,如果在背包的物品当中存在彼此之间的相关性我们应该怎么去处理呢。这就是我们在这篇文章中所...
补题8/12 问题 A: sciorz画画 tag:动态规划 问题 B: 奎奎发红包 tag:贪心 问题 C: 关于我转生变成史莱姆这档事 tag:广搜,数论 问题 D: 大数 tag:字符串kmp 问题 E: Ktree 问题 F: 求和 tag:矩阵快...
以——“煊哥的难题”为例 STL当中为我们提供了非常多的高效容器,利用好的话可以给我们的程序带来极大的便利 Description 煊哥待在家里实在无聊,于是出了一道难题来考考你们。 众所周知,两点确定一条直线,现给出\(2n\)个点...
——以“最长回文子串”及“回文子串个数”为例 首先明确,这两题使用动态规划均能求解,不过复杂度还是相对较高 这里先给出动态规划的状态转移方程,有兴趣的读者不妨一试 \(dp[i][j]\)表示字符串中从\(i\)到\(j\)的子串是否为回...
——以“钻石收集者”与“Subsequence”为例 如果有同学细心去做Codeforces,会发现有这么一类标签叫Two Pointers。没错,这就是我们今天的主角——尺取法。 还有一部分同学会将尺取法叫成毛毛虫法。 其实这是相当形象的一种叫法,...
set是STL的一个关联容器并带有自动排序和去重的功能 Sets are containers that store unique elements following a specific order. ——C++ Reference set的操作并不复杂,有以下几种 迭代器begin cbegin 返回指向...
以“【模板】单源最短路径(弱化版)”为例 最短路径是图论当中的重点内容之一 这里我们借由洛谷上的一条模板题来理解一下什么是SPFA 首先明确,SPFA并不是一个算法的名字,这只是一个中国老师在1996年在Bellman–Ford算法基础...
本篇将介绍在各类算法竞赛中应用广泛,也是最为基础的一种素数筛法,欧拉筛,他的本质是Eratosthenes筛的优化 在介绍欧拉筛之前,我们不妨先整体感悟一点就是素数的存在虽然是无序 的 (至少目前并没有有力的证明素数的分布存在一...