沙雕博主的消失

据悉,该博主由于长期不更新博客,正在接受联邦屌插局的屌插。

今天偶尔打开来看看,发现自己真的好久没写东西了

和班里别的同学比一下真是太垃圾了!

就这样吧(x

打算给JB全系列网站加一下HTTP/2支持

刚刚看到HTTP/3草案都出了……

对了GitHub突然又被墙了,欢迎使用JB GitLab

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

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

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

平板电视介绍

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

闷声发大财

赚 大 了

事情是这样的:

  • 早上线代课无聊刷微博
  • 网路冷眼推了一本屌炸天的Problem Solving书
  • 下载欣赏 -> 卧槽这内容神了
  • 给作者(world final玩家+coach+助理研究员+Google员工)发了封邮件,说想把他的东西写进自己的模板里
  • 然后作者竟然把他们用的模板直接推给我了

绝了!还用什么NJU模板!

所以之前你看到的aunt想要自己写模板的事情吹了。

最长回文子序列与最长回文子串

两种截然不同的问题。

最长回文子序列 (subsequence)

解决方法是动态规划。$dp[i][j]$表示区间$[i, j]$中最长的回文子序列的长度,那么可以获得递推公式
$$dp[i][j] = \begin{cases} dp[i+1][j-1] + 2 & s[i] == s[j] \\ \max(dp[i][j-1], dp[i+1][j]) & s[i] \neq s[j] \\ 1 & i == j \end{cases}$$

那还挺简单的

最长回文子串 (substring)

超暴力解法

对于每一个起始位置和结束位置,枚举所有可能的情况然后判断。时间复杂度$O(n^3)$。

暴力解法

列举每一个中心位置判断。时间复杂度$O(n^2)$。

Manacher算法

不知道哪个傻逼翻译成马拉车算法,我还以为和马+车有关系。

算法概述

  1. 首先通过插入相同的字符将$n$位的字符串转换为$2n+1$位的字符串,那么所有的回文串一定是奇数长度的。
  2. 维护数组$len$,$len[i]$记录以$i$为中心的最长回文串的右端到$i$的距离。$$len[i] = r – i + 1$$
  3. 以$i$为中心的最长回文串的长度是$len[i] – 1$(考虑对称性)。

计算方式

从左往右计算$len$数组,假设在计算$len[i]$时,前面所有位置中右端最远的回文串的中心为$mc$,$mr = mc + len[mc] – 1$。取$i$关于$mc$的对称点$j = 2mc – i$。

  1. 如果$i <= mr$
    1. 如果$i + len[j] < mr$,说明以$i$、$j$为中心的回文串关于$mc$完全对称,且是以$mc$为中心的回文串的子串。$len[i] = len[j]$。
    2. 如果$i + len[j] \ge mr$,需要对$mr$右侧的字符串进行手动匹配。
  2. 如果$i > mr$,得不到信息,只能手动匹配。

算法分析

你觉得我是$O(n^2)$的?其实我是线性的!

因为$mr$只能增长不能减小,所以复杂度是$O(n)$的。(如果放在期末考试里我绝对证不出来。)

例题

HDU3068,纯模板题。

因为没有判断取$mr-mc$和$len[j]$中较小的那一个WA了一发。找了一个反例是jojojooooj

#include <bits/stdc++.h>
using namespace std;
char ori[110005] = {};
char s[250005] = {};
int len[250005] = {};
int tot = 0, mc = 0, mr = 0, ans = 0;

int getString() {
  s[0] = '#';
  int tot = (int) strlen(ori);
  for (int i = 0; i < tot; ++i) {
    s[(i << 1) + 1] = ori[i];
    s[(i << 1) + 2] = '#';
  }
  return tot << 1;
}

int main() {
  while (scanf(" %s", ori) != EOF) {
    mc = mr = 0;
    ans = 1;
    tot = getString();
    for (int i = 0; i <= tot; ++i) {
      int j = (mc << 1) - i;
      if (i <= mr) {
        len[i] = min(mr - i + 1, len[j]);
        int pl = i - len[i], pr = i + len[i];
        while (pl >= 0 && pr <= tot && s[pl] == s[pr]) {
          len[i]++;
          pl--; pr++;
        }
      } else {
        len[i] = 1;
        int pl = i - len[i], pr = i + len[i];
        while (pl >= 0 && pr <= tot && s[pl] == s[pr]) {
          len[i]++;
          pl--; pr++;
        }
      }
      if (i + len[i] > mr) {
        mc = i;
        mr = i + len[i] - 1;
      }
      if (len[i] > ans) {
        ans = len[i] - 1;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

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$中。