Blowing up unordered_map, and how to stop getting hacked on it
repost from https://codeforces.com/blog/entry/62393.
Blowing up unordered_map
C++ has always had the convenient data structures std::set and std::map, which are tree data structures whose operations take time. With C++11, we finally received a hash set and hash map in std::unordered_set and std::unordered_map. Unfortunately, I've seen a lot of people on Codeforces get hacked or fail system tests when using these. In this post I'll explain how it's possible to break these data structures and w ...
SSH端口转发教程
本文主要介绍什么是 SSH 隧道以及如何使用 SSH 隧道实现端口转发，包括 SSH 隧道加密数据传输以及绕过防火墙。
1. 什么是 SSH 隧道
SSH 隧道是 SSH 中的一种机制，它能够将其他 TCP 端口的网络数据通过 SSH 连接来转发，并且自动提供了相应的加密及解密服务。因为 SSH 为其他 TCP 链接提供了一个安全的通道来进行传输，因此这一过程也被叫做“隧道”（tunneling）。
SSH 隧道也可以叫做端口转发
SSH 隧道能够提供两大功能：
加密 SSH Client 端至 SSH Server 端之间的通讯数据。
突破防火墙的限制完成一些之前无法建立的 TCP 连接。
本地转发和远程转发
SSH 端口转发自然需要 SSH 连接，而 SSH 连接是有方向的，从 SSH Client 到 SSH Server 。而我们的应用也是有方向的，比如需要连接 MySQL Server 时，MySQL Server 自然就是 Server 端，我们应用连接的方向也是从应用的 Client 端连接到应用的 Server 端。如果这两个连接的方向一致，那我们就说它是本地 ...
Hadoop集群搭建详细教程
服务器存储环境准备
服务器硬件规格如下
服务器rios-cad2：7T空硬盘*1
服务器rios-cad6-121：7TB空硬盘*1。
服务器rios-cad6-122：7TB空硬盘*1。
首先需要对空硬盘进行分区、格式化文件系统、挂载。
分区
先介绍两种分区表：
MBR分区表：（MBR含义：主引导记录）
所支持的最大卷：2TB
对分区的设限：最多4个主分区或3个主分区加一个扩展分区
GPT分区表：（GPT含义：GUID分区表）
支持最大卷：18EB（1EB=1024TB）
每个磁盘最多支持128个分区
因此，当磁盘超过2TB时，我们要么将磁盘分为多个MBR分区，否则需要使用GBT分区。
Linux传统的分区工具fdisk不支持GPT分区，但可以使用另一个工具parted来对GPT磁盘操作。parted功能很强大，既可用命令行也可以用于交互式。注意：parted只可以对没有做过任何分区的空盘做分区。
这里我们只对硬盘（编号/dev/sda）分1个分区，因此我们使用parted工具来实现GPT分区。
$ sudo parted /dev/sdaNU Parted 3.1U ...
Linux动态链接中的GOT和PLT
本文主要讨论什么是延迟加载？什么是PLT与GOT表？PLT表与GOT表到底建立跳转关系的？延迟加载有好处与弊端？
GOT和PLT是什么
PLT：Procedure Link Table，程序链接表。
GOT：Global Offset Table，全局偏移表。
这两个表相互配合解决外部函数符号地址，解决运行时重定位的问题。这种方法能让函数在调用时才确定地址，进程的启动时间加快，只需一次绑定，也称为延迟绑定，接下来通过例子示意。
代码示意与分析
#include <stdio.h>void testprintf(){ printf("hello\n");}int main(){ char acTemp[100] = {0}; printf("begin\n"); testprintf(); return 0;}
上面是一段非常简单的C程序，就调一个printf函数，一个自定义的testprintf函数。其中我们知道printf是libc.so里面的函数，在默认情况下，gl ...
Magic Number 0x3f3f3f3f
在做算法题时，我们常常需要用到一个能够表示“无穷大”的值INF，最容易想到的，我们可以把INF设为0x7fffffff，因为这是32位int的最大值。如果这个无穷大只用于一般的比较（比如求最小值时min变量的初值），那么0x7fffffff确实是一个完美的选择。但是更多情况下，0x7fffffff并不是一个最好的选择，比如在Dijkstra算法中，我们使用松弛操作：
if (dist[u] + weight[u][v] < dist[v]) dist[v] = dist[u] + weight[u][v];
如果u和v之间没有边，那么weight[u]=INF，如果此时将INF取作0x7fffffff，那么dist[u] + weight[u][v]就会向上溢出而变成负数，我们的松弛操作便出错了！
准确来说，0x7fffffff在作为32位整数的情况下不能满足无穷大加无穷大依然是无穷大这个条件，一旦溢出就变成了一个很小的负数。
可以考虑这样一个取值INF=0x3f3f3f3f，0x3f3f3f3f的十进制是1061109567，是109级别的（和0x7fffffff一个数 ...
AcWing 801. 二进制中1的个数
原题链接：https://www.acwing.com/problem/content/803/
思路：
采用lowbit()函数
采用位运算
#include <iostream>int bitCount(unsigned int n) { n = ((n & 0xAAAAAAAA) >> 1) + (n & ~0xAAAAAAAA); n = ((n & 0xCCCCCCCC) >> 2) + (n & ~0xCCCCCCCC); n = ((n & 0xF0F0F0F0) >> 4) + (n & ~0xF0F0F0F0); n = ((n & 0xFF00FF00) >> 8) + (n & ~0xFF00FF00); n = ((n & 0xFFFF0000) >> 16) + (n & ~0xFFFF0000); return n;}int count(int n) { int ...
AcWing 2816. 判断子序列
原题链接：https://www.acwing.com/activity/content/problem/content/2981/
思路：基础的双指针算法。
#include <iostream>#define N 100005int a[N], b[N];int n, m;int main() { scanf("%d %d", &n, &m); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < m; ++i) scanf("%d", &b[i]); int i = 0, j = 0; while (j < m && i < n) { if (a[i] == b[j]) i++; j++; } printf("%s", (i == n ? "Yes" : "No")); return 0;}
AcWing 800. 数组元素的目标和
原题链接：https://www.acwing.com/problem/content/submission/code_detail/22373905/
两种思路：
，因此可以采用二分查找的思路，时间复杂度。
由于所给数组已经有序，可以采用矩阵搜索的思路。等价于在一个矩阵中寻找目标值，其中满足沿轴方向和轴方向都是递增的。这种方法时间复杂度为。
#include <iostream>#include <algorithm>int n, m, x; int bin_search(int b[], int left, int right, int target) { int i = left, j = right, mid; while (i < j) { mid = (i + j) >> 1; if (b[mid] > target) j = mid; else if (b[mid] < target) i = mid + 1; else return mid; ...
AcWing 799. 最长连续不重复子序列
原题链接：https://www.acwing.com/problem/content/description/801/
思路：
用一个pos[]数组来存储某个数上次出现的位置
双指针i和j，表示当前最长不重复区间[i,j)。每当将要把nums[j]纳入区间时，考察nums[j]上次出现的位置。
若在i的左侧，则可以直接把nums[j]纳入最长不重复区间。
否则，将i移动到nums[j]上次出现位置的右侧。
#include <iostream>#include <cstring>#define N 100005int nums[N];// 记录一个数上次出现的位置int pos[N];int n;// 区间[i, j)，j表示下一个将要纳入区间的数的下标int longest_repeat() { int i = 0, j = 1, max = 0; while (j <= n) { if (j - i > max) max = j -i; if (j == n) break; if ...
AcWing 798. 差分矩阵
原题链接：https://www.acwing.com/problem/content/800/
参考之前的构造一维矩阵的思路（差分是前缀和的逆运算），假设数组是的前缀和矩阵，有以下等式成立： 将除了矩阵以外的所有项移到左边，就可以得到根据前缀和矩阵求出差分矩阵的等式： 构造出差分矩阵后，就可以根据一维差分的思想，来修改二维差分矩阵了。这个过程本质上用的也还是容斥原理。
#include<iostream>#define N 1005int a[N][N];int b[N][N];int n, m, q;// 构建二维差分矩阵，本质是前缀和的逆运算void build() { // a[i][j] = a[i][j-1] + a[i-1][j] - a[i-1][j-1] + b[i-1][j-1] // b[i-1][j-1] = a[i][j] - a[i][j-1] - a[i-1][j] + a[i-1][j-1] for (int i = 1; i <= n; i++) { for (int j = 1; j <= ...