平板电视与可动态更新的堆

家电下乡高价回收,笔记本、电脑、洗衣机……

嗯……不是那个平板电视。

平板电视介绍

Policy-Based Data Structures,简称平板电视,是C++ STD库函数的一套数据结构的总称。平板电视的功能强大,囊括了以下丰富内容:

  • 基于树规则的数据结构,包括了比STL跑的快到不知道哪里去的红黑树、根本手写不了的斐波那契堆、以及SPLAY TREE 
  • 基于字典树规则的数据结构(主要是Trie树)
  • 基于链表规则的数据结构(没有了解过)
  • 基于Hash规则的数据结构(Hashtable)
  • 还有本篇的重点:支持动态修改的堆(优先队列)

平板电视的使用主要是各种牛逼的树和优先队列。使用平板电视需要注意环境:在程序中引入头文件<bits/extc++.h>,如果编译通过就可以使用平板电视。

  • ACM/ICPC全部支持(理论上)
  • 做不出的OJ题(注意POJ全不支持)
  • 自己写程序爱用就用

我喜欢的是平板电视里的堆

使用平板电视的堆需要注意:PBDS的模板名与STD的完全一致,所以不能同时使用using namespace std; using namespace __gnu_pbds;,只能用一个或者最安全就是不要用整个namespace。

优先队列的模板

优先队列的模板如下:

template<
    typename Value_Type,
    typename Cmp_Fn = std::less<Value_Type>,
    typename Tag = pairing_heap_tag,
    typename Allocator = std::allocator<char> >
class priority_queue;

此处的四个参数分别是:数据类型、比较函数、堆种类和内存分配器。堆的种类共有5种:pairing_heap_tag, binary_heap_tag, binomial_heap_tag, rc_binomial_heap_tag, or thin_heap_tag

优先队列的使用

对于默认的堆,只需要用__gnu_pbds::priority_queue<int> pq;就可以声明了。默认和STD一样是大根堆,有pushtoppopclearemptybeginend等方法,可以和STD的优先队列一样使用。

不同的是,平板电视的优先队列的push方法会返回一个指针迭代器__gnu_pbds::priority_queue< TypeName >::point_iterator。这个指针迭代器会一直指着插入的数据,可以随时访问值,但注意不能直接修改它。

如果要修改某个值,可以调用modify方法,这个方法接受两个参数,第一个参数是指针迭代器,第二个是要更新的值(变大变小都可以)。

参考代码:

// A priority queue of integers.
priority_queue<int> p;

// Insert some values into the priority queue.
priority_queue<int>::point_iterator it = p.push(0);

p.push(1);
p.push(2);

// Now modify a value.
p.modify(it, 3);

assert(p.top() == 3);

可以将位于堆底的0修改成3,并且这个值在修改后冒到堆顶,并且指向它的迭代器也跟着过来了。

需要注意的是,如果指针迭代器对应的值已经被弹出堆,这个时候访问指针迭代器就会造成segment fault。

使用样例

由于GCC的页面出bug了,暂时没法阅读examples文件。链接:https://gcc.gnu.org/onlinedocs/libstdc++/ext/pb_ds/pq_examples.html

跑得非常快

在某道卡时间(其实根本不卡)的题目中使用cin cout读入、输出数据,平板电视优先队列来实现Dijkstra算法,全部跑完只用了572ms,根本没有被卡时间,跑的快的不得了!

(然后由于一些傻逼错误导致WA27%,找了四个多小时都没出错在哪,后来跟别人拍来拍去才知道自己题意没理解对……)

解决一个弱智的PHP问题

What happened

刚把服务器搬迁到Digital Ocean,一个cron任务总是报错,提示给我class PDO not found in ...

然后安装了php-pdo php-mysql,用phpinfo()看到的结果是

PDO support enabled
PDO drivers dblib, firebird, mysql, odbc, pgsql, sqlite

然而,cron还是给服务器发邮件提示class PDO not found

Search the Friendly Web

想着一定是自己哪里搞错了,我上各种网搜索缺少PDO怎么解决,然后解决方案几乎都是

  • apt/yum安装PDO并启用,但是我已经启用了
  • pecl安装PDO,我用不着pecl
  • 在php文件中添加use PDO;,文件里也有这句

为什么傻逼程序还提示缺这个库呢?

Solve the Frustrating Problem

经过半个多小时的排查……神tm是因为我的cron里命令是php -n

而这个选项的含义是:-n No php.ini file will be used

再恁马的见!

Problem solved.

Digital Ocean的学生优惠

免费的东西,为什么不要呢?

介绍

Digital Ocean,大牌子计算服务提供商之一。人民群众喜闻乐见的V2EX就是用的Digital Ocean的服务器。

优点

  • 界面贼好看(比Vultr好多了,秒杀国内垃圾提供商)
  • 帮助文档齐全(Vultr的一键app根本没法用)
  • 价格实惠(最低套餐月租$5,和Vultr基本一个价格)
  • 功能多(但是要花钱啊)

缺点

  • 只支持信用卡或者Paypal,并且必须绑定账户
  • 很多功能需要额外氪金
标准VPS售价

白嫖套餐

Digital Ocean的每个用户可以使用1个邀请码。所以只能白嫖一次。

使用学生认证过的GitHub账户登陆https://education.github.com/pack,可以在页面中找到Digital Ocean的板块,点击”Get offer code”生成优惠码,然后去Digital Ocean注册。注册完了之后在付款信息页输入代码就可以获得50刀巨额财富。(10个月呢)

Digital Ocean的使用

  • Droplet的添加和安装都是傻瓜式的,安装完了之后如果是具体的应用可以RTFM查看使用方法。其实可以直连ip,服务器端都配置好了提示页面。
  • WordPress等app已经安装好了certbot,可以直接运行来注册SSL证书、开启HTTPS访问。自带服务器端的配置文件位于/etc/apache2/sites-available,网页根目录位于/var/www/html,apache2默认用户为www-data
  • DO的防火墙挺严的……默认只有22、80、443端口,不过22就是个坑人端口。
  • DO支持把域名和服务器一起管理,只需要把nameserver改成DO提供的域名服务器就可以了。

C++11 std骚操作

bits库

<bits/stdc++.h>包括了C++的所有标准库。

<bits/extc++.h>史诗般的外挂,包含了__gnu_pbds的所有内容,包括gp_hash_tablerope等。打死我都不要自己写数据结构了!

类型推导

编译器根据右边的表达式自动判断返回类型。

然而这玩意随便用用就能自损一千,特别好用的地方就是声明迭代器循环变量。

基于范围的for循环

不用写那么多东西,太爽了!但是记得要将循环变量用引用声明,否则随随便便就能TLE。

#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
int main() {
  vi v = {1, 1, 4, 5, 1, 4, 1, 9, 1, 9};
  for (auto &i : v) {
    cout << i;
  }
  return 0;
}

运行结果:

1145141919

容器去重

<algorithm>里有一个unique函数,会将升序排序的容器中所有的除了第一次出现的元素全部扔掉。

用法:先排序,然后调用unique(start, end);

#include <bits/stdc++.h>
using namespace std;

#define trav(a, A) for (auto &a : A)
#define all(A) A.begin(), A.end()
typedef vector<int> vi;

int main() {
  vi v = {1, 1, 4, 5, 1, 4, 1, 9, 1, 9};
  sort(all(v));
  auto last = unique(all(v));
  v.erase(last, v.end());
  trav(it, v) {
    cout << it << " ";
  }
  return 0;
}

输出结果:

1 4 5 9

bitset

初始化:bitset<length> foo; 构造函数可以用一个数或01字符串做参数。

对象函数:

  • []运算符或test(pos)访问某一位。
  • all()判断是否全为1。
  • any()none()判断是否有1。
  • count()返回所有1的个数
  • set()reset()flip()改变某一位的值。若无参数传入,则对所有的位执行同样的操作。
  • to_string()to_ulong()变成01字符串和整数。

hash

C++11启支持对string类、bitsetvector<bool>的hashing,使用方法如下:

#include <bits/stdc++.h>
using namespace std;

int main() {
  string str1 = "That's good.";
  string str2 = "That's goood.";
  hash<string> h;
  
  cout << h(str1) << endl << h(str2);
  return 0;
}

运行结果:

2177240917276858684
14580988214652125085

Kosaraju算法分析 (CLRS 22.5)

CLRS写的什么鬼东西根本看不懂啊啊啊

Kosaraju是什么

Wiki表示Kosaraju在1978年发明了这个算法但是没把他的论文发表出来,1981年别人独立发现了该算法并发表。

那为什么不发表呢……

Kosaraju的基本方法

  1. 对$G$进行一次深搜
  2. 求$G$的逆$G^T$,并对所有点按照完成时间降序排序
  3. 对$G^T$进行一次深搜
  4. 同一个深度搜索子过程中的所有点都在同一个联通分量里

正确性证明

Kosaraju算法的正确性证明依赖于定理22.14:

$C$和$C’$都是强连通分量,如果存在$(u,v) \in E$, $u \in C$, $v \in C’$,那么最晚完成时间$f(C) > f(C’)$。

有了以上定理,我们就可以用数学归纳法证明第二次DFS所有的子过程中的点都在同一个连通分量里了。

假设已经找到了$k$个强连通分量,
1. $k=0$,显然正确。
2. $k \neq 0$,假设寻找第$k+1$个强连通分量时,最先找到的点是$u$(树根$u \in C$),那么此时$C$中所有的点都是白色,都会变成$u$的后代。同时,根据22.14得到的推论22.15,所有离开$C$的点一定前往已经被搜索过的强连通分量$C’$。所以在此次搜索中,以$u$为根的树中的所有点一定在同一个强连通分量$C$中。

Z Shell与Oh My Zsh

Z Shell

官网:http://zsh.sourceforge.net

据官网所称,Z Shell (zsh)是为了交互使用而打造的,也是一个强大的脚本语言,具有很多bash、ksh、tcsh的特性。

然而实际使用中,zsh就是一个和vi一样的一般般的软件。

安装Z Shell

  • Linux: apt install zsh
  • Windows: 洗洗睡吧

设置为默认shell

可用cat /etc/shells查看所有可用shell,用chsh -s "path-to-shell"设置默认选项。注意zsh与bash配置文件不同,环境变量需要重新配置。

Oh My Zsh

vi有vim这个外挂般的存在,zsh也有OMZ这个天外飞仙一样的软件外挂

Your terminal never felt this good before.

OMZ官网(https://ohmyz.sh/)如此说到。

功能

管理zsh的配置文件,拥有海量插件和主题,让你high到不行啊

插件(选推)

z

做PA总是cd太累了,z可以帮你模糊匹配你要前往的文件夹,比如你要从nemu/src/cpu/exec前往nemu/include/cpu,只需要执行z cpu回车就可以了,z会自动从浏览记录中匹配寻找文件夹。如果有多个重名文件夹,按tab键就可以看到列表了。

autojump

与z相同的功能,但是要额外安装autojump。跳转指令是j,我更喜欢z因为不用装东西。

extract

tar/zip/rar解压缩选项太多根本记不住怎么办?现在只要一个x指令就解决问题了!

git

自带的,包括branch显示和一大堆浓缩指令,不介绍了。

zsh-autosuggestions和zsh-syntax-highlighting

功能如标题所示,用shell就和用IDE一样,太爽了!

last-working-dir

打开终端自动回到上次工作的目录,很多人推,我不知道这个有啥好用的。

主题

https://github.com/robbyrussell/oh-my-zsh/wiki/Themes

自己挑,改配置文件就可以了,不过估计基本都会选agnoster。