Mcginn's Blog

Mcginn's Blog

make a better version of self

B-Tree
简介简单来说,B-Tree 是针对大数据存取的平衡树,考虑了磁盘读取对查找效率的影响。 B-Tree 的主要思想是通过减少磁盘读取次数来提高数据存取性能,而磁盘读取次数与树高相关。故B-Tree 允许每个节点拥有多于 2 个的子节点来减小树高。 与二叉平衡树类似,B-Tree 中的每个节点存储若干键值(keys)以及子节点地址。 图 1. B-Tree 结构图 定义和性质阶(order):将子节点的允许最大数量定义为阶,如图 1 为 5 阶树。 $m$ 阶的 B-Tree 满足以下定义: 每个节点最多能有 $m$ 个子节点。 每个内部节点至少有 $\lceil \frac m2\r...
AhoCorasick Algorithm
简介AhoCorasick 算法(简称 AC 自动机),解决多模式串的字符匹配问题,即给定若干个单词串 $W_i$,求在文本串 $T$ 中的出现位置。KMP 算法解决单模式串的字符匹配,所以 AC 自动机可认为是 KMP 算法的扩展。 预备知识 字典树(Trie):树上任意节点到根的路径所构成的子串,记为 $S(u)$,都是某个插入串的前缀。 KMP 算法:利用最长前后缀完成线性匹配。 核心思想AhoCorasick 本质上与 KMP 算法是一样的,都是通过相同前后缀减少重复计算问题,只是数据结构不同。 对应于 KMP,AC 自动机需要构建最长公共前后缀(LCPS,Longese Co...
Knuth-Morris-Pratt Algorithm
KMP 算法解决在文本串(text)快速找出单词(word)的所有出现位置。 暴力匹配的时间复杂度为 $O(|T||W|)$,而 KMP 算法通过引入最长前后缀,将检索的时间复杂度降至线性。 最长前后缀 lps indicates longest proper prefix which is also suffix. 最长前后缀(LPS, Longest proper Prefix and Suffix)表示既是原串 $S$ 的真前缀也是后缀的最长子串 $T$,其中 $|T|\lt |S|$。 LPS(aaa) = aa \\ LPS(abcdab)=ab检索过程假设已知单词串的每个...
ICPC Resolver 踩坑
应用场景从 DOMjudge 系统中导出数据,使用 ICPC Tools/Resolver 滚榜。 DOMjudge 版本:7.0.1。 Resolver 版本:2.0.1798。如果使用 DOMjudge 评测,建议使用 2.1 及以上版本。 数据操作 搜索 ICPC Tools,下载 ICPC Resolver.rar。 运行 award.sh,通过 REST 导入 event feed(一场比赛的所有信息流)。 123URL: http://59.77.134.102/domjudge/api/contests/5USER: amdinPassword: ******* 点击 s...
斜率优化
斜率优化针对形如: dp(i)=\min _{j=1}^{i-1} (dp(j)+cost(i, j))的动态规划转移方程,可通过’’斜率’’的单调性进行优化。 题一、[HNOI2008]玩具装箱TOY题意 题目链接给定长为 $1\le N\le 50000$ 的序列 $1\le C_i\le 10^7$,将序列分成若干连续段,每段 $[i, j]$ 的花费为 ((j - i+\sum_{k=i}^jC_k)-L)^2其中 $L$ 为常数,$1\le L \le 10^7$。要求计算总的最小花费代价。 解题思路利用前缀和 $S_i​$,区间 $[i, j]​$ 序列和可表示成 $S_...
Nowcoder-出题人的数组
链接:https://ac.nowcoder.com/acm/contest/545/C来源:牛客网 题目描述出题人有两个数组 $A, B$,请你把两个数组归并起来使得 $Cost=∑i∗C_i$ 最小,要求两个原数组的顺序在新数组中保持不变。 输入描述第一行输入两个正整数 $n,m$,分别表示数组 $A, B$ 的长度。第二行输入 $n$ 个正整数,表示数组 $A$。第二行输入 $m$ 个正整数,表示数组 $B$ 。 输出描述一个正整数,表示最小代价 $Cost$。 示例 1输入输出3 31 3 52 6 475 备注$n, m \le 100000$ $A_i, B_i \le ...
Windows 下使用 Vim
简要说明主要针对 ACM/ICPC 竞赛选手在 Windows 10 系统下使用 vim 编写 C/C++ 代码。 功能配置: 编译和运行 *.cpp 文件; 一键复制代码; 记事本打开代码。 git bash 和 gvim 都配置了一遍。gvim 使用 Windows 自带的 cmd 运行的话,鼠标是没办法移动光标的,并且配置相对 git bash 较麻烦,所以推荐使用 git bash。 Vimrc 配置 编辑安装路径下的 vimrc 文件,例如 “D:\Git\etc\vimrc”,配置快捷键。 123456set nu ai ci si mouse=a ts=4 sts=4...
论文笔记 Tips and Tricks for Visual Question Answering
简介​ 该论文作者取得了 2017 VQA Challenge 的第一,总结一些 tips 和 tricks 来提升 VQA 的表现。 ​ 这篇论文的每个实验使用不同的随机种子重复3次实验来统计结果。 模型 一些细节 所有问题的长度固定 14。 问题特征 $q$ 与图像特征 $\hat v$ 的融合使用 Hadamard product(逐项相乘)。 h = f_q(q) \circ f_v(\hat v) 目标函数(损失函数) L=-\sum_i^M\sum_j^N s_{ij}\log (\hat s_{ij})-(1-s_{ij})\log(1-\hat s_...
DOMjudge 配置
Domserver 部署PHP timezone php.ini 文件位置 CentOS/RedHat/Fedora = /etc/php.ini Ubuntu/Debian/LinuxMint = /etc/php5/apache2/php.ini 选择时区,通常定位为 “Asia/Shanghai” PHP: List of Supported Timezones 编辑 php.ini 文件 1date.timezone = "Asia/Shanghai" 重启 Apache Service。 1sudo service apache2 restart MySQL ...
论文笔记 Semantic Compositional Networks for Visual Captioning
简介​ 该论文提出了语义组合网络(Semantic Compositional Network, SCN),其有效利用语义概念(标签)来达到效果比较好的图文生成。 Semantic compositional networks 模型基础 使用CNN提取图像特征,RNN作文字生成。 文字生成的概率公式: p(\bold X | \bold I) = \prod _{t=1}^Tp(x_t|x_0, \dots , x_{t-1}, v) $ \bold X = (x_1, \dots , x_T)$ 表示文字序列,$v$ 为提取的图像特征。 LSTM的转换函数: h_t ...
avatar
Mcginn
just go