警惕 C++ 的未定义行为
若非明确指明，本文所探讨的标准为 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 […]
OI
CF852G Bathroom terminal 题解
前言 我不理解为什么有人喜欢简单问题复杂化啊啊啊啊啊啊啊啊啊 因为字典树不会写，所以只好写一个搜索水过去。 题意 求 $N$ 个由字母 a 到 e 组成的字符串（单词串）与一些包含 ? 的模式串的匹配个数。每一个 ? 匹配 a 到 e 的字母或者空字符。 分析 根据题目数据分析，最多有 $3$ 个 ?，所以对于每一个模式串，与之匹配的单词串最多由 $6^3 = 216$ 个；考虑到 $M$ 最大为 $5000$，暴搜绰绰有余。 所以只需要对每一个模式串进行深搜，枚举所有可能的情况，进行判断即可。 […]
使用 /dev/urandom 规避 srand(time(0)) 的整数弊端
某位同学设计了一个 A + B 的交互题，为了搞随机数据。 但是因为时间函数 time(0) 总是返回秒数，就会导致随机数一致的情况： 直到今天，这个搁置了很久的问题我打算去解决一下。 因为之前闲着没事 cat /dev/random，自然想到使用 /dev/random 解决。但是据说 /dev/random 越调用越慢，所以换用更好用的 /dev/urandom。 我们需要设法读取 /dev/urandom。但是 freopen/fopen 会出问题（读不出什么东西，容易挂），所以需要更加手 […]
欧拉（回）路
欧拉（回）路是个啥，用一点点小学奥数知识就可以理解。 都知道“一笔画”问题吧。那么，我告诉你，此“欧拉（回）路”就是“一笔画”的路径。 定义/解释 欧拉（回）路/欧拉图的形象解释： 欧拉（通）路：从一个点出发，若有某条路径可以经过这张图所有的边，则这个路径叫做“欧拉（通）路”。 欧拉回路：首尾点是同一个点的欧拉（通）路。 欧拉图： 欧拉图：具有欧拉回路的图 半欧拉图：具有欧拉通路但不具有欧拉回路的图 判定 无向图 运用小学知识，可以推出： 存在欧拉回路： 是一张连通图 所有顶点的度数都是偶数 存 […]
CF Round #850 赛后总结
这是一篇 黑历史。 萌新打的第一场 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 – 30919: GCDS – Sabbir and gcd problem 题解
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 […]
POJ3481 Double Queue 题解 （aka 双端优先队列）
题目链接：POJ3481 思路 umm 要维护一个内部有序的 双端队列？ 想到平衡树。 但是我几百年前写的 AVL Tree 板子早忘了，因为之前只学过这一个。 C++内部有序的容器——set set 是内部有序的！（实现是红黑树） 如以下代码： #include <iostream> #include <set> using namespace std; set<int> homo; int main() { homo.insert(114); homo.i […]
强连通分量 – Kosaraju Algorithm
Kosaraju算法（aka Kosaraju-Sharir算法）是一个求强连通分量的算法。其时间复杂度为$O(n+m)$（邻接表）或$O(m^2)$（邻接矩阵）。 该算法相比Tarjan算法要更简单一些。（个人观点） 本算法的基础是反图（也被称作逆图、转置图）。 基本原理 反图 参见 OI Wiki1 的解释： 对于有向图 $G$，它的 反图 (transpose graph) 指的是点集不变，每条边反向得到的图，即：若 $G$ 的反图为 $G’=(V,E’)$，则 $ […]
1 2