这篇文章咕了两个月。感谢 @rickyxrc 的催更。 如果你还不知道什么是强连通分量的话，参见我本系列的上一篇文章：强连通分量 – Kosaraju Algorithm 引入 强连通分量的缩点，就是把图上的每一个强连通分量都视作一个点（或者更通俗的，缩成一个点）。SCC 与 SCC 之间的边连接依然参照原图保留。 缩点解决了部分算法「跑不了环」的问题，比如拓扑排序。并且对于部分题目，缩点之后的图对于原图来说没有太大的区别。 图示 如图所示，1 2 3 和 4 5 6 分别属于两个 SCC。把 […]
因为我们学校里的在线评测系统没有办法屏蔽 #pragma GCC optimize 预处理指令，因此出现了如下的状况： 因此，今天我决定从根源上禁止这些行为。 正好前两天看到洛谷上屏蔽手动 O2 O3 Ofast 的方式，于是今天自己就来试着修改 GCC 的源代码，并计划手动编译并上线测试。 需求整理 魔改编译器禁止手动优化； 编译器版本之间可以分离，不予系统自带的编译器冲突； GCC 9 + GCC 12。 准备工作 如果你也是某个 OJ 的运维/管理，直接在服务器上构建源代码会更好，但是注意 […]
若非明确指明，本文所探讨的标准为 C++14。 引入 阅读下面的一段代码，判断输出。 #include <iostream> int i = 1; int arr[10]; int main() { while (i < 10) arr[++i] = arr[i – 1] + 1; for (i = 1; i < 10; i++) { std::cout << arr[i] << ‘ ‘; } } A. 0 1 2 3 4 5 6 7 8 B. 0 […]
前言 我不理解为什么有人喜欢简单问题复杂化啊啊啊啊啊啊啊啊啊 因为字典树不会写，所以只好写一个搜索水过去。 题意 求 $N$ 个由字母 a 到 e 组成的字符串（单词串）与一些包含 ? 的模式串的匹配个数。每一个 ? 匹配 a 到 e 的字母或者空字符。 分析 根据题目数据分析，最多有 $3$ 个 ?，所以对于每一个模式串，与之匹配的单词串最多由 $6^3 = 216$ 个；考虑到 $M$ 最大为 $5000$，暴搜绰绰有余。 所以只需要对每一个模式串进行深搜，枚举所有可能的情况，进行判断即可。 […]
某位同学设计了一个 A + B 的交互题，为了搞随机数据。 但是因为时间函数 time(0) 总是返回秒数，就会导致随机数一致的情况： 直到今天，这个搁置了很久的问题我打算去解决一下。 因为之前闲着没事 cat /dev/random，自然想到使用 /dev/random 解决。但是据说 /dev/random 越调用越慢，所以换用更好用的 /dev/urandom。 我们需要设法读取 /dev/urandom。但是 freopen/fopen 会出问题（读不出什么东西，容易挂），所以需要更加手 […]
欧拉（回）路是个啥，用一点点小学奥数知识就可以理解。 都知道“一笔画”问题吧。那么，我告诉你，此“欧拉（回）路”就是“一笔画”的路径。 定义/解释 欧拉（回）路/欧拉图的形象解释： 欧拉（通）路：从一个点出发，若有某条路径可以经过这张图所有的边，则这个路径叫做“欧拉（通）路”。 欧拉回路：首尾点是同一个点的欧拉（通）路。 欧拉图： 欧拉图：具有欧拉回路的图 半欧拉图：具有欧拉通路但不具有欧拉回路的图 判定 无向图 运用小学知识，可以推出： 存在欧拉回路： 是一张连通图 所有顶点的度数都是偶数 存 […]
请注意，本文仅供交流学习使用，任何利用此方式违反法律的行为将会收到制裁。云服务厂商知道你在干违法的事。 今天因为某些原因，vjudge.net 的服务器在大陆（尤其是我们学校）无法访问。但是我们要在那个平台上刷题。 正巧手上有台双程 CN2 GIA 的服务器（腾讯云新加坡轻量），计划着做个镜像。服务器在学校的访问速度（四川移动）还行。 0x00. 反代镜像的要点 服务器对外对内速率都很好，要不然可能会负优化。 被镜像的网站在国内的访问速度必须要慢（雾 不要反代违法违规网站，要不然会被叫去喝茶。 […]
这是一篇 黑历史。 萌新打的第一场 CF。（但是 Div.2）（Div.1比较难搞）（因为菜） 晚上8:05开题，做了两个半小时（但是摸了好一会儿的鱼），一共六题，做出来两题（但是是同一个问题的简单和复杂的两个版本，即 A1 和 A2），总得分825，Rank 6288，有效题目完成时间 1 小时 20 分钟。 总体分析 A1~2 看到 A1，多次询问，第一反应 $O(1)$ 找规律。经过不懈的 OEIS，反反复复确认了三遍，把代码写完调通；最后成功通过A1、A2。再去 Discord 上看一眼 […]
警告，本文KaTex排版较多，请耐心等待页面加载完成再浏览。 如果有不想看的章节，请查看左侧 TOC 跳过。 0x00 什么是矩阵乘法 这是一个 $\rm 2\times 3$ 的矩阵。 $\rm A =\begin{bmatrix}a_{1,1} & a_{1,2} & a_{1,3} \cr a_{2,1} & a_{2,2} & a_{2,3}\end{bmatrix}$ 这是另一个 $\rm 3\times 4$ 的矩阵。 $ \rm B = \begin […]
SPOJ 原题传送门 洛谷RMJ传送门 这是一道数论题。 思路 因为要求找到的整数 $x$ 是一个互质于 $a_i$ 的数，所以很显然 $x$ 为质数的时候最优。 根据互质的一些性质，$a_i$ 和 $x$ 没有共同的质因数，所以可以标记所有 $a_i (1\le i\le n)$ 的质因数，然后选取最小的未被标记的质数。 举个例子： $\rm{a = \tt{[11, 45, 14, 19, 81]}}$ 标记如下 故选择13作为 $x$。 看到这里，就滚去写代码罢！ $$ \raisebox […]