On the way

范围最小值问题

范围最小值问题（Range Minimum Query, RMQ）。给定一个数组A[1, n]，求A[i，j]的最小值。这里假定数组A的元素不会变化（如果变化，用线段树）。范围最值查询-维基百科 Sparse-Table（ST）算法预处理时间O(nlogn)，查询O(1)。令表示从开始，长度为的一段元素中的最小值。利用动态规划，状态转移方程是：。注意。故d数组的元素个数...

Posted by Xsp on June 11, 2017

C++ IO 库

《C++ primer》th5 学习笔记第8章基本IO库设施： istream：输入操作。 ostream：输出操作。 cin：一个istream对象，从标准输入读数据。 cout：一个ostream对象，向标准输出写数据。 cerr: osstream对象，用于输出程序错误消息。 >> 运算符: 从一个istream对象读输入数据。 &l...

Posted by Xsp on June 8, 2017

C++位运算

设置bit int mask = 1 << x; number |= mask; 确定想将某一位设置为1，只需要将mask的对应位设置为1，然后位或运算。所以，以上代码会设置number的右数第x位为1（x从0开始）。清除bit number &= ~(1 << x); 确定想将某一位设置为0，需要mask的对应位置为0，其他位置为1，然后位与运算。那...

Posted by Xsp on June 7, 2017

二叉索引树(树状数组)

内容参考《算法竞赛入门经典-训练指南》二叉索引树(Binary Indexed Tree, BIT)，俗称树状数组，又以发明者命名为Fenwick树。现多用于高效计算数列的前缀和，区间和。树状数组-维基百科。应用给定一个n个元素的数组，设计一个查询操作Query(i, j) = 。如何做？如果用前缀和的思想，计算，那么 Query(i, j) = ，单次查询时间为O(1)，...

Posted by Xsp on June 6, 2017

泛型算法

《C++ primer》th5 学习笔记第10章概述泛型算法是一些经典算法的公共接口，可适用于多种容器，大多数定义在algorithm头文件，另外在numeric头文件定义了一组数值泛型算法。这些算法运行于迭代器之上。初识泛型算法只读算法 accumulate()，前两个参数指定需要求和的范围，第三个参数决定使用的加法运算符和返回值类型。如下的代码则是分别对整数和字...

Posted by Xsp on May 30, 2017

顺序容器

《C++ primer》th5 学习笔记第9章标准库顺序容器： vector 可变大小数组 deque 双端 list 双向链表 forward_list 单项链表 array 固定大小数组 string 与vector类似迭代器范围，左闭合区间[begin， end). rb...

Posted by Xsp on May 29, 2017

关联容器map,set

《C++ primer》th5 学习笔记第11章关联容器支持高效的关键字查找和访问，主要包括map、set、multimap、multiset，以及加上unordered前缀的无序的四个。在使用数组下标时，通常将其定义为size_t类型，size_t是一种机器相关的无符号类型，它被设计得足够大以便能表示内存中任意对象的大小。 map中元素是一个pair类型的对象，该对象...

Posted by Xsp on May 28, 2017

Python学习笔记

教程：廖雪峰Python教程 Python基础 Python是解释型语言。编译和解释的区别？编译型语言在编译过程中生成目标平台的指令，解释型语言在运行过程中才生成目标平台的指令。虚拟机的任务是在运行过程中将中间代码翻译成目标平台的指令。输入/输出(Input/Output，IO) print('hell...

Posted by Xsp on April 30, 2017

Mac/Linux 常用命令整理

find 文件查找查找所有后缀是.js的文件 find . -name "*.js" 查找所有.DS_Store 并删除 find . -name *.DS_Store -delete ifconfig / ipconfig 查看本机IP ifconfig 是Mac/Linux的，ipconfig 是Win的，以前总是搞混了，不过多用几次就记住了，然后想着可以这样记，两个的差别就...

Posted by Xsp on March 22, 2017

Shell 修改文件内容

如果想批量修改整个项目里面的一些内容，用Shell还是比较方便的，当然这样的一些经常需要修改的内容，应当单独在一个配置文件里声明比较好。如想修改项目里有用到的ip地址 #!/bin/bash # $1 = windows ip if [ $# != 1 ] ; then echo "USAGE: $0 WindowsIP" exit 1; fi # 获取本机IP...

Posted by Xsp on March 18, 2017