使用Hexo搭建个人博客并部署到Github

操作系统环境:Ubuntu 19.04

Git版本:2.20.1

Node.js版本:10.15.2

npm版本:5.8.0

前置环境安装

安装前提

在你的电脑上安装 Git、Node.js 以及 npm:

1
sudo apt install git nodejs npm

在某些发行版,源中的 nodejs 与 npm 版本过低,不能完成 Hexo 的正常使用,如果出现这种问题,请到 Nodejs 官网以及 npm 官网下载较新版本。

安装hexo

1
sudo npm install -g hexo-cil

初始化你的博客

在你希望创建博客的目录下运行指令:

1
hexo init

由于 npm 的问题,我在运行本命令的时候出现了错误,如下图:

1570935913884

只需要再手动运行 npm install 命令就可以了。

执行本命令后,我们会发现在当前目录下多出了以下文件:

1570936230837

其中:

  • node_modules:nodejs的依赖包,各种插件会被安装在里面;

  • scaffolds:页面模板;

  • source:资源,这里面的内容将会按照页面分别,未来也将会呈现在生成的静态页面中;

    如我在这个目录中创建了 img 文件夹并在其中放置了 index.jpg 文件,预览或者发布后在浏览器中输入页面地址/img/index.jpg即可访问这个文件。而以 markdown 编写的博客文件将会被转换成 html 文件并按照配置中的设置来保存到静态页面结构中。

  • theme:存放主题的文件夹,默认安装 landscape 主题;

  • _config.yml:配置文件,具体内容将会在后面的内容中提及。

此时输入以下命令(实时预览博客):

1
hexo server

并在浏览器中输入:http://localhost:4000,你就可以看到你的博客最开始的样子了。

增加你的第一篇博客

使用如下命令创建一篇博客:

1
hexo new '文章名'

比如我想创建一篇叫做 test 的博客,我就需要输入 hexo new 'text'(去掉引号也是可以的)。接下来我们就可以在/source/_posts文件夹下看到我刚刚创建的text.md文件。打开我们会发现上面已经有一部分内容:

1570938154144

这一部分灰色背景框住的部分叫做 Font-matter,用于指定个别文件的变量。它具体的markdown代码为:

1
2
3
4
5
---
title: test
date: 2019-10-13 11:38:55
tags:
---

Hexo 预先定义了一些参数:

参数 描述 默认值
layout 布局
title 标题
date 建立日期 文件建立日期与时间
updated 更新日期 文件更新日期
comments 开启文章的评论功能 true
tags 标签(不适用于分页)
categories 分类(不适用于分页)
permalink 覆盖文章地址
keywords 仅用于 meta 标签和 Open Graph 的关键词(不推荐使用)

除了使用 YAML 你也可以使用 JSON 来编写 Front-matter,例如:

1
2
3
"title": "Hello World",
"date": "2013/7/13 20:46:25"
;;;

Font-matter以下,你就可以使用熟悉的 markdown 来编写你的博文了。

配置

你的博客的一些基础配置可以在_config.yaml中来修改,具体内容如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
# Hexo Configuration
## Docs: https://hexo.io/docs/configuration.html
## Source: https://github.com/hexojs/hexo/

# Site
title: Hexo # 博客标题,会显示在你的页面标题中
subtitle: # 副标题
description: # 描述,用于告诉搜索引擎
keywords: # 关键词
author: John Doe # 作者,你的名字
language: en # 语言,简体中文设置为 zh-CN
timezone: # 时区,东八区设置为 Asia/Shanghai

# URL
## If your site is put in a subdirectory, set url as 'http://yoursite.com/child' and root as '/child/'
url: http://yoursite.com # 网址,具体见下文描述
root: / # 网站根目录
permalink: :year/:month/:day/:title/ # 网站的永久连接格式,具体见下文描述
permalink_defaults: # 永久连接中各部分的默认值

# Directory # 这些目录将会与你的主题设置等有关
source_dir: source # 资源文件夹名称
public_dir: public # 发布文件夹名称,这个文件夹用于存放生成的站点文件
tag_dir: tags # 标签文件夹名称
archive_dir: archives # 归档文件夹名称
category_dir: categories # 分类文件夹名称
code_dir: downloads/code # Include code文件夹,是source_dir下的子目录
i18n_dir: :lang # 国际文件夹
skip_render: # 跳过指定文件的渲染,发布时不会生成这些文件

# Writing
new_post_name: :title.md # 新文章的文件名称
default_layout: post # 预设布局,post即按照主题中layout文件夹下的post.ejs来布局
auto_spacing: false # 在中英文之间自动加入空格
titlecase: false # 把标题转换为title case
external_link: true # 在新标签页中打开连接
filename_case: 0 # 把文件名称转换为 (1)小写 或 (2)大写 (0)不转换
render_drafts: false # 显示草稿(?)
post_asset_folder: false # 启动 Asset 文件夹(?)
relative_link: false # 把链接改为与根目录的相对位址
future: true # 显示未来的文章(按照Front-matter中的data属性判断)
highlight: # 代码块高亮
enable: true # 启用高亮
line_number: true # 显示行号
auto_detect: false
tab_replace:

# Home page setting
# path: Root path for your blogs index page. (default = '')
# per_page: Posts displayed per page. (0 = disable pagination)
# order_by: Posts order. (Order by date descending by default)
index_generator: # 主页设置
path: '' # 路径
per_page: 10 # 每页显示的文章个数
order_by: -date # 按照日期排序

# Category & Tag
default_category: uncategorized # 默认的分类
category_map:
tag_map:

# Date / Time format
## Hexo uses Moment.js to parse and display date
## You can customize the date format as defined in
## http://momentjs.com/docs/#/displaying/format/
date_format: YYYY-MM-DD # 日期格式
time_format: HH:mm:ss # 时间格式

# Pagination
## Set per_page to 0 to disable pagination
per_page: 10 # 分页:每页现实的文章量
pagination_dir: page # 分页目录

# Extensions
## Plugins: https://hexo.io/plugins/
## Themes: https://hexo.io/themes/
theme: landscape # 设置主题

# Deployment
## Docs: https://hexo.io/docs/deployment.html
deploy: # 部署设置
type:

特殊的:

  • 如果您的网站存放在子目录中,例如 http://yoursite.com/blog,则请将您的 url 设为 http://yoursite.com/blog 并把 root 设为 /blog/
  • permalink设置为:year/:month/:day/:title/时,你的生成于2019年10月1日的名为Hello的博客将以http://你博客的网址/2019/10/01/Hello/来访问。

主题

Hexo 主题商店 来找到你的想要的主题。

一个主题文件夹中主要有以下文件/文件夹:

  • _config.yml:主题的配置文件;
  • languages:主题的语言文件;
  • layout:页面布局方案;
  • scripts:脚本文件;
  • source:资源文件。

由于不同主题的具体内容不同,所以在此不再对主题的配置进行讨论。

部署到 Github

Github Pages 是 Github 提供的免费的静态网站解决方案,用以方便用户发布自己的项目。Github Pages 为每一个用户提供一个静态网站,域名为 <username>.github.io。用之搭建静态的个人博客是很好的选择的

在Github的设置

创建一个名为 <username>.github.io 的仓库,注意 <username> 部分一定要替换成你的用户名:

1570940939271

在本地Git中配置你的Github账户信息

在终端中输入以下命令:

1
2
git config --global user.name "YourName"
git config --global user.email "YourEmail"

将其中的YourNameYourEmail修改成你的用户名和账户邮箱。

再输入以下命令创建SSH:

1
ssh-keygen -t rsa -C "youremail@example.com"

1570942286216

按照图片中的内容找到生成的id_rsa.pub,并将内容复制到 Github 设置中的 SSH keys 中。

1570942588589

1570942725229

再输入以下命令来确认 SSH 连接:

1
ssh -T git@github.com

1570942877965

在Hexo中配置上你的 Github 信息

修改博客的_config.yml中关于 deploy(部署)的配置(将其中的<username>改成你的 github 用户名,内容不保留尖括号):

1
2
3
4
5
deploy:
type: git
repo: git@github.com:<username>/<username>.github.io.git
branch: master
message:

在你的博客目录下打开终端,输入以下命令:

1
2
3
hexo clean
hexo generate
hexo server
  • hexo clean/hexo c:清除本地以前生成的静态页面文件。
  • hexo generate/hexo g:在本地生成静态页面文件,并保存到public文件夹下。
  • hexo deploy/hexo d:上传部署到 Github。

部署完成后,就可以在浏览器中访问http://username.github.io(username替换为你的Github用户名)来访问你的博客了。

其他

绑定个人域名

  1. 购买域名,国内的话可以购买的地方很多,推荐阿里云万网。

    个人认为还是.com与.net的域名更好一些,但相对其他域名来说活动会更少。你也可以尝试现在个人博客多使用的.cc、.name、.me、.io等域名。

  2. 增加CNAME,在你的source目录下藤甲一个名为CNAME文件,并在里面增加上你的域名。

  3. 在你的域名解析DNS中增加上记录:

    记录类型 主机记录 解析路线 记录值
    A www 默认 IP地址
    CNAME @ 默认 你的github页面网址
    • 记录类型:

      • A:指定主机对应的IP地址;
      • CNAME:别名记录;
      • NS:域名服务器记录;
      • MX:邮件交换记录,指向邮箱服务器。

      我们在这里只需要记录一个 A 记录和一个 CNAME 记录就可以了。

    • 主机记录(域名前缀:

      • @:直接解析主域名,没有前缀;
      • 某一个英文字符串:前缀为这个字符串的域名;
      • :泛解析,匹配其他所有前缀域名。

    其中IP地址可以通过ping命令获得:

    1570944714395

  4. 重新部署。

hexo-admin 插件

hexo-admin插件是一个方便后台登录管理hexo博客的插件,你可以在这上面方便地创建并编写新博客。

1570944895391

安装本插件

在博客目录下打开终端并输入:

1
npm install --save hexo-admin

使用本插件

首先你要在本地预览你的博客,输入:

1
hexo server

然后打开浏览器访问localhost:4000/admin即可进入该插件后台。

配置本插件

为防止他人试用本插件,我们可以在设置中添加用户名密码。在 Settings 中找到 Setup authentification here。

1570945162102

1570945192774

设置你的用户名和密码。

然后将下方生成的配置文件内容存放到博客配置文件_config.yml中,即可加密。

算法学习:马拉车算法

学习自博客:

马拉车算法(音译,Manacher’s algorithm)是一个复杂度为 $O(n)$ 的、求一个字符串最长回文子序列的算法。

回文字符串,就是指无论从左向右读还是从右向左读结果都是一样的字符串。如字符串google的最长回文字串为goog

极限暴力的求得字符串最长回文字序列的方法都是寻找每个中心点开始向两边扩延一位一位地看是否相同,这样的算法复杂度回到 $O(n^2)$,显然不满足一般的需求。且由于回文字符串长度的奇偶问题,还需要特别的奇偶分类问题:如回文字符串aba的中心是b这个字母,回文字符串abba的中心是两个b之间。这两种情况需要分别考虑。

马拉车算法思想

去除字符串长度奇偶分类的问题

马拉车首先在每两个字符之间(包括首尾两端)插入一个原字符串没有的特殊符号,比如#。假设我们现在的字符串为google,插入#后便转换为了:#g#o#o#g#l#e#。设字符串长度为 $len$,加入的特殊字符个数一定为 $len + 1$,而 $len$ 与 $len + 1$ 中必为一奇一偶,所以结果一定是一个奇数,这样的话部分回文字符串(如#g#o#o#g#)的中心一定会是一个字符而不是两字符中间。

半径数组

设原来的字符串为 $str$,加上特殊字符处理后的字符串为$strM$。为了记录每一位对应的最长回文字串半径,我们引入与 $strM$ 半径数组 $p[]$,其中 $p[i]$ 表示以 $strM[i]$ 为中心的最长回文字串的半径,如果 $p[i] = 1$ 就说明该回文串就是 $strM[i]$ 本身。如例子#g#o#o#g#l#e#,可得到如下表格:

$i$ 0 1 2 3 4 5 6 7 8 9 10 11 12
$strM[i]$ # g # o # o # g # l # e #
$p[i]$ 1 2 1 2 5 2 1 2 1 2 1 2 1

可以观察到,$p[i] - 1$ 就是以第 $i$ 位为中心的回文字串在原字符串中的长度。假设在原字符串中,该回文字符串的长度 $l$,由于加入了 $l+ 1$ 个#,在新字符串中的长度就会变为 $ln = 2 \times l + 1$。而 $p[i]$ 存储的是新的字符串的回文字串的半径,也就是 $\frac{ln + 1}{2}$ $=$ $l + 1$,即 $p[i] = l + 1$,所以最终结果为 $p[i] - 1$。

由于字符串的最开始与最后都有一个#字符,为了在搜索回文字串时避免总是判断是否越界,我们在字符串的左端与右端都加上另外一个特殊字符,如$^。(其实最后一位处不需要加上这个特殊字符,因为字符串的最后本来就是有一位\0用以标记字符串的结束的。)

所以这个算法的重点就在于如何计算数组 $p[]$ 的值。

$p[]$ 数组求解

引入两个变量,分别为idmx。其中id为一个已经检查过了的最大的回文字符串的中心点,mx为这个回文字符串的最终点。在马拉车算法的过程中,我们不断的对这两个变量进行更新。在这个过程中,我们有公式:
$$
p[i] = \min(mx - i, p[2\times id - i])
$$
现在我们就重点来讲解这个公式,如下图所示(其中 $j$ 是 $i$ 关于 $id$ 的对称点($j = 2\times id - i$),蓝色串➀为以 $j$ 为中心的回文串,橙色串为以 $i$ 为中心的回文串,绿色串为以 $id$ 为中心的回文串):

1565748502350

目前我们已经求得了满足 $0 \leq x \leq i - 1$ 的 $p[x]$,接下来就是要使用以前的数据推得 $p[i]$。会有如下情况

  1. $i \leq mx$

    由于 $j$ 与 $i$ 关于 $id$ 对称,所以以 $j$ 为中心的回文串关于 $id$ 对称一下就成了以 $i$ 为中心的回文串。所以我们这个时候需要判断一下情况:

    1. 如果橙色串的末尾没有超过 $mx$, 即 $p[j] \leq mx - i$,此时 $p[i] = p[j]$。
    2. 如果橙色串的末尾超过了$mx$,即 $p[j] > mx - i$,此时就不能确定 $p[i] = p[j]$ 一定会成立了。则先赋值 $p[i] = mx - i$ ,然后手动向两边扩来得到最长回文子串。为什么 $p[j] = mx -i + 1$ 的情况归到了这里?因为当 $p[j] = mx -i + 1$,我们的回文子串直接定到了 $mx$ 上,我们不能确定 $mx$ 以后的位是否还能满足关于 $i$ 回文。
  2. $i > mx$

    那我们只能保证 $mx - i $ 这一段是满足的,所以我们就先让 $p[i] = mx -i$,其余部分使用笨方法慢慢扩张。

有没有可能橙色串的左端超过了 $mx$ 的对称点呢?不可能。如果说左端超过了 $mx$ 的对称点,且中心位于 $i$ 的话,则 $i$ 为中心的回文字串长度会超过以 $id$ 为中心的回文字串,也就是说以 $j$ 为中心的回文子串长度超过了 $id$ 为中心的回文字串,那么我的 $id$ 在之前应该被更新为 $j$。所以这种情况是不存在的。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
string Manacher(string str)
{
/*改造字符串*/
string res="$#";
for(int i=0; i < (int)str.length(); ++i) {
res += str[i];
res += "#";
}

/*数组*/
vector<int> p(res.length(), 0);
int mi = 0, right = 0; //mi为最大回文串对应的中心点,right为该回文串能达到的最右端的值
int maxLen = 0, maxPoint = 0; //maxLen为最大回文串的长度,maxPoint为记录中心点

for (int i = 1; i < res.length(); ++i){
p[i] = (right > i)? min(p[2 * mi - i], right - i) : 1; //关键句,文中对这句以详细讲解

while(res[i + p[i]] == res[i - p[i]])
++p[i];

if(right < i + p[i]) //超过之前的最右端,则改变中心点和对应的最右端
{
right = i + p[i];
mi = i;
}

if(maxLen < p[i]) //更新最大回文串的长度,并记下此时的点
{
maxLen = p[i];
maxPoint = i;
}
}
return str.substr((maxPoint - maxLen) / 2, maxLen - 1);
}

题解:HDU6641 TDL

本题为 2019 HDU Multi-University Training Contest 6 的 1008 题

题目传送门🚪

Problem Description

For a positive integer $n$, let’s denote function $f(n,m)$ as the $m$-th smallest integer $x$ that $x>n$ and $\mathrm{gcd}(x,n)=1$. For example, $f(5,1)=6$ and $f(5,5)=11$.

You are given the value of $m$ and $(f(n,m)−n)\oplus n$, where $\oplus$ denotes the bitwise XOR operation. Please write a program to find the smallest positive integer $n$ that $(f(n,m)−n)\oplus n=k$, or determine (whether) it is impossible.

Input

The first line of the input contains an integer $T$($1 \leq T \leq 10$), denoting the number of test cases.

In each test case, there are two integers $k,m$($1 \leq k\leq 10^{18}$,$1\leq m\leq100$).

Output

For each test case, print a single line containing an integer, denoting the smallest $n$. If there is no solution, output $-1$ instead.

Sample Input

1
2
3
2
3 5
6 100

Sample Output

1
2
5
-1

顺便吐槽下出题人的英语水平,“or determine it is impossible” 是什么鬼?

题意 & 题解

一道(对众多大佬来说比较水的)数论题,被拿来当签到题QAQ。

题目中,$(f(n,m) - n)\oplus n=k$,我们设 $d = f(n,m) - n$,则有 $d \oplus n = k$,两面同时异或上 $n\oplus k$,则有 $d \oplus n \oplus n \oplus k = k\oplus n \oplus k$ $\Rightarrow$ $n = d \oplus k$。$f(n,m)$ 表示大于 $n$ 的第 $m$ 大的与 $n$ 互质的数。由于 $m \leq 100$,一个奇数周围与它互质的数一般要多于与它不互质的数(举个例子,假设一个奇数 $9$,它周围有 $10$、$11$、$12$、$13$、$14$、$15$、$16$、$17$、$18$、$19$、$20$,其中与它互质的有$11$、$13$、$14$、$16$、$17$、$19$、$20$,要多于不与它互质的个数),所以我去枚举 $d$ 的值要优于枚举 $n$ 的值,况且一个数与它相邻的数一定是互质的,所以我们从 $1$ 开始枚举 $d$ 就可以了。枚举 $d$ 带入 $n = d \oplus p$ 得到的 $n$ 带回 $d=f(n,m)-n$ 中进行验证,如果成立,则代表这个结果是可行的。$f(n,m) = n + d$,$f(n,m)$ 满足与 $n$ 互质,即 $\mathrm{gcd}(f(n,m), n) = 1$,根据更相减损术,$\mathrm{gcd}(f(n,m) - n,n)$ $=$ $\mathrm{gcd}(f(n,m),n)$,所以枚举 $d$ 后通过判断 $d$ 与 $n$ 是否互质可以排除很多不满足的情况。而 $d$ 的枚举我们只需要枚举到第 $115$ 个质数,理由如下:

根据算术基本定理(唯一分解定理),任何一个大于 $1$ 的合数自然数 $N$,都可以分解成有限个质数的乘积,即:
$$
N = P_1^{a_{1}}P_2^{a_{2}}P_3^{a_{3}} \cdots P_n^{a_{n}}=\prod_{i=1}^nP_i^{a_i}
$$
根据约数个数定理,一个数的因数个数 $K$ 为:
$$
K = (a_1+1)(a_2+1)(a_3+1)\cdots(a_k+1)=\prod_{i=1}^n(a_i+1)
$$
最终结果 $n$ 不会超过long long的范围,而前 $16$ 个质数之积已经超过了long long的范围,也就是说,最小的一个可分解为 $15$ 个以上质数的数已经不符合要求了,所以最终结果 $n$ 最多有 $15$ 质数因数。而根据更相减损术,如果对于一个质数 $x$ 与一个自然数 $n$ 互质,则 $x$ 也与 $x+n$ 互质。如果我们根据算术基本定理对 $n$ 分解后它有 $15$ 个素数因数,那么第 $115$ 个素数(即 $631$)一定会是 $d$ 可以取到的极限了。所以 $d$ 只需要从 $1$ 枚举到 $631$,超出此范围就一定没有满足的结果了。

AC代码

来自同队的 zyg 大佬,感谢大佬!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <string.h>
#include <algorithm>
#include <cmath>
#include <cstdio>

using namespace std ;
typedef long long ll ;

ll gcd (ll x , ll y){
if (y==0) return x ;
else return gcd(y,x%y) ;
}
const ll maxn = 1e18+5 ;
int main(){
int t ;
scanf("%d",&t) ;
while(t--){
ll k ;
int m ;
ll ans = maxn ;
scanf("%lld %d",&k , &m) ;
for (ll i = 1; i <= 631 ; i++) { // 631是第115个质数
ll n = i^k ;
if (gcd(i,n)!=1) continue ;
int temp = 0 ;
for (ll j = 1 ; j< i ; j++) {
if (gcd(j,n)==1) temp++ ;
}
if (temp==m-1&&ans>n){
ans = n ;
}
}
if (ans == maxn) cout << -1 << endl ;
else cout << ans << endl ;
}
return 0 ;
}

题解:HDU6629 String Mathching

本题为 2019 HDU Multi-University Training Contest 5 的 1007 题

题目传送门:🚪

Problem Description

String matching is a common type of problem in computer science. One string matching problem is as following:

Given a string $S[0\cdots len−1]$, please calculate the length of the longest common prefix of $S[i\cdots len−1]$ and $S[0 \cdots len−1]$ for each $i>0$.

I believe everyone can do it by brute force.
The pseudo code of the brute force approach is as the following:

img

We are wondering, for any given string, what is the number of compare operations invoked if we use the above algorithm. Please tell us the answer before we attempt to run this algorithm.

input

The first line contains an integer $T$, denoting the number of test cases.
Each test case contains one string in a line consisting of printable ASCII characters except space.

  • $1 \leq T \leq 30$

  • string length $\leq 106$ for every string

Output

For each test, print an integer in one line indicating the number of compare operations invoked if we run the algorithm in the statement against the input string.

Sample Input

1
2
3
4
 3
_Happy_New_Year_
ywwyww
zjczzzjczjczzzjc

Sample Output

1
2
3
17
7
32

题意 & 算法

题目就是问题目中这个算法中比较的次数。题目中提及的算法就是暴力对串中每一个位置进行前缀匹配。我们可以推知,如果子串长度为 $x$ ,我们就需要进行 $x+1$ 次匹配(因为还有一次匹配失败的情况)。而如果我匹配的子串最后一位到达了原串的最后一位的话,我们只需要进行 $x$ 次匹配(因为匹配失败的情况不会出现了)。所以这个问题就转换成了前缀匹配。扩展KMP算法就是为这种问题产生的。

KMP算法讲解传送门:🚪

这个题挺坑的,各种卡时间啊。卡memset()(其实也没必要用memset()),卡cin……T 了一晚上我才过去……

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;
int nexts[1000006];
char T[1000006];
long long ans = 0;
void getNext(){
int m = strlen(T);
// m:T的长度
int a = 0, p = 0;
for (int i = 1; i < m; i++) {
if (i >= p || i + nexts[i - a] >= p) {
if (i >= p) p = i;
while (p < m && T[p] == T[p - i])
p++;
nexts[i] = p - i;
if(i + nexts[i] >= m)
ans += nexts[i];
else ans += nexts[i] + 1;
a = i;
}
else{
nexts[i] = nexts[i - a];
if(i + nexts[i] >= m)
ans += nexts[i];
else ans += nexts[i] + 1;
}
}
}
int main(){
int n;
scanf("%d", &n);
while(n--){
scanf("%s", T);
ans = 0;
getNext();
printf("%lld\n", ans);
}
return 0;
}

算法学习:扩展KMP

2019年8月5日下午,冰冷的雨滴击打着脆弱的窗户玻璃,机房里异常的安静,仿佛每个人都等待着一轮风暴。HDU的第五场多校赛已经过去了一半,距离吃饭只有两个半小时了,但我却没有一点开心的感觉。抬头,映入眼帘的就是一道魔鬼签到题目,和红色背景白色字体的“(-5)”字眼。机房的空调从来没有这么好使过,我甚至感到浑身寒冷,有几分想要颤抖身体。

比赛还是如期地结束了。这场比赛的这个签到题我还是没能做出来。是的,爆零了。我开始怀疑人生,怀疑自己存在的意义。挫败的我打开了题解,发现了这个叫做”扩展KMP“算法。虽然忧伤,但我还是尝试学习一下这个算法。于是……

题解传送门🚪

算法引入

假设现在有两个字符串,分别为 $S$ 与 $T$ ,其中 $S$ 为待匹配的串,$T$ 为进行匹配的串,现在我需要知道 $S$ 的每一位开始,分别可以匹配成功 $T$ 串中从头开始的连续的多长子串。

举个例子,比如现在 $S$ 为字符串AAAAABBB, $T$ 为字符串AAAAAC。我们定义数组extend[]为最终结果,其中 $extend[i]$ 为 $S.\mathrm{substr}(i,n)$ ($S[i \cdots n-1]$) 中与 $T$ 匹配成功的最长相同前缀的长度。如本例中可得到如下表格:

$i$ 0 1 2 3 4 5 6 7
$S$ A A A A A B B B
extend[i] 5 4 3 2 1 0 0 0

如果使用暴力进行这个匹配过程的话,算法复杂度就达到了 $O(m\times n)$,所以我们要用更好的算法来解决这个问题。这就是扩展 KMP 的任务。

算法思想

我们为何引入并使用next[]数组

暴力算法的问题就在于extend[]数组中的数据彼此之间是会有一些联系的,而暴力法并没有用上这些联系而直接进行了重新匹配。

假设我们现在匹配到了第 $i$ 个位置,如下图:

1565080573726

其中图中 $p$ 指从 $S$ 的第 $a$ 位开始与 $T$ 匹配成功的最后一位的下一位,也就是说 $S.\mathrm{substr}(a,p) = T.\mathrm{substr}(0,p-a)$。如果从 $i$ 开始的几位与 $T$ 开头的几位相同,那么 $extend[i]$ 的值就是这段距离的长度。所以我们引入 next[]数组来记录匹配串 $T$ 中相同前缀部分的长度。比如对于AAAAAC,我们就可以得到以下列表:

$i$ 0 1 2 3 4 5
$T$ A A A A A C
next[i] 6 4 3 2 1 0

从头开始遍历 $S$,设当前遍历到了第 $i$ 位,$i + next[i -a ]$ 的值会有以下几种情况:

注意next[]数组

  1. $i + next[i - a] <p$

    1565095531149

    说明这个时候的 $i + next[i-a]$ 还在可控范围内。因为我们已经知道了 $S.\mathrm{substr}(a, p)$ 与 $T.\mathrm{substr}(0, p-a)$ 相同,而 $S[i + next[i -a]]$ 还在 $S.\mathrm{substr}(a, p)$ 的范围内,所以这个时候 $S.\mathrm{substr}(i, i + next[i - a])$ 与 $T.\mathrm{substr}(i - a, i - a + next[i - a])$ 就可以成立,于是 $S.\mathrm{substr}(i, i + next[i - a])$ 与 $T.\mathrm{substr}(0, next[i - a])$ 就会成立,所以我们就可以知道 $extend[i]$ 的值为 $next[i - a]$。

  2. $i + next[i - a] = p$

    1565095544744

    这种情况下,$S[p]$ 与 $T[p - a]$ 不一定相同,$T[p - i]$ 与 $T[p - a]$ 也不一定相同,但却有 $T[p - a]$ 与 $S[p]$ 相同的情况,所以我们就直接对比 $S[p]$ 与 $T[p - a]$ 及以后。然后得到 $next[i]$ 的值。当我最后匹配直到 $S[p + k]$ 与 $T[p+k-a]$ 相同,则可得到 $next[i]$ 的值为 $p + k - i$。下一次再匹配时,只需要从 $a = i$、$p = p + k$ 开始就可以了。

  3. $i + next[i - a] > p$

    1565097429456

    这种情况下我们就不能确定这上面的匹配方式相同了,所以我们就需要从 $S[p]$ 与 $T[p - i]$ 开始匹配,具体做法同第 $2$ 种情况。

获得next[]数组

其实这个就很简单了。next[]数组反映的即是 $T$ 字符串中从第 $i$ 位开始的内容与从第 $0$ 位内容开始的最大相同前缀,所以其实只是把 $T$ 与自己匹配跑了一编这个算法。

算法模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
int next[100];
int extend[100];
string S, T;
void getNext(){
int m = T.length();
// m:T的长度
int a = 0, p = 0;
next[0] = m;
for (int i = 1; i < m; i++) {
if (i >= p || i + next[i - a] >= p) {
if (i >= p) p = i;
while (p < m && T[p] == T[p - i])
p++;
next[i] = p - i;
a = i;
}
else
next[i] = next[i - a];
}
}
void getExtend(){
int n = S.length();
int m = T.length();
int a = 0, p = 0;
getNext();
for (int i = 0; i < n;i ++){
if (i >= p || i + next[i - a] >= p) {
// i >= p 的作用:举个典型例子,S 和 T 无一字符相同
if (i >= p) p = i;
while (p < n && p - i < m && S[p] == T[p - i])
p++;
extend[i] = p - i;
a = i;
}
else
extend[i] = next[i - a];
}
}

题解:洛谷P1955:[NOI2015]程序自动分析

算法:并查基、离散化、文件读入与写出。

题目描述

在实现程序自动分析的过程中,常常需要判定一些约束条件是否能被同时满足。

考虑一个约束满足问题的简化版本:假设 $x_1,x_2,x_3\dots$代表程序中出现的变量,给定 $n$ 个形如$x_i=x_j$或$x_i \neq x_j$的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:$x_1=x_2,x_2=x_3,x_3=x_4,x_4\neq x_1$,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

现在给出一些约束满足问题,请分别对它们进行判定。

输入格式

从文件prog.in中读入数据。

输入文件的第 $1$ 行包含 $1$ 个正整数 $t$,表示需要判定的问题个数。注意这些问题之间是相互独立的。

对于每个问题,包含若干行:

第 $1$ 行包含 $1$ 个正整数 $n$ ,表示该问题中需要被满足的约束条件个数。接下来 $n$ 行,每行包括 $3$ 个整数 $i,j,e$,描述 $1$ 个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 $e=1$,则该约束条件为 $xi=xj$;若 $e=0$,则该约束条件为 $xi\neq xj$;

输出格式

输出到文件 prog.out 中。

输出文件包括 $t$ 行。

输出文件的第 $k$ 行输出一个字符串“ YES” 或者“NO”(不包含引号,字母全部大写),“YES” 表示输入中的第 $k$ 个问题判定为可以被满足,“NO” 表示不可被满足。

输入输出样例

输入 #1

1
2
3
4
5
6
7
2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

输出 #1

1
2
NO
YES

输入 #2

1
2
3
4
5
6
7
8
9
10
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

输出 #2

1
2
YES
NO

说明/提示

【样例解释1】

在第一个问题中,约束条件为:$x1=x2,x1\neq x2$。这两个约束条件互相矛盾,因此不可被同时满足。

在第二个问题中,约束条件为:$x1=x2,x1=x2$。这两个约束条件是等价的,可以被同时满足。

【样例说明2】

在第一个问题中,约束条件有三个:$x1=x2,x2=x3,x3=x1$。只需赋值使得$x1=x1=x1$,即可同时满足所有的约束条件。

在第二个问题中,约束条件有四个:$x1=x2,x2=x3,x3=x4,x4\neq x1$。由前三个约束条件可以推出$x1=x2=x3=x4$,然而最后一个约束条件却要求$x1\neq x4$,因此不可被满足。

【数据范围】

img

【时限2s,内存512M】

题目传送门:🚪

文件读入与写出

虽说题干写着从文件读入,写出到文件,但其实这个题完全不需要……直接标准读入读出就可以……可怜我太实诚……酿造了如下惨状:

1564486633365

既然提到了就说说这个……

C的方法

  • fopen()函数

    使用方式:fp = fopen("input.in", "r")

    • 第一个参数为打开文件的文件名;
    • 第二个参数为文件方式,是文件的类型和操作要求,有如下几种(组合):
      • r:只读(read),要求文件必须已经存在;
      • w:只写(Write),若文件不存在则自动创建,如果已存在则删除原文件后新建;
      • a:追加(Append),保留文件中已有内容,从文件尾开始写;
      • t:文本文件(Text),可忽略;
      • b:二进制文件(Binary);
      • +:读写。
    • 返回值为文件指针,为FILE类型的指针变量。

    在具体使用此方法写入时,使用fscanf(fp, "%d", &n)来读取:

    • 第一个参数为文件指针名,即使用fopen返回的指针;
    • 第二个参数为格式控制符,同scanf()的使用方式;
    • 第三及以后的参数为传入变量的指针。

    使用fprintf(fp, "%d\n", n)来写入文件:

    • 第一个参数为文件指针名,即使用fopen返回的指针;
    • 第二个参数为格式控制符,同printf()的使用方式;
    • 第三及以后的参数为输出变量。

    结束使用该函数使用:fclose(fp)

  • freopen()函数

    使用方式:freopen("input.in", "r", stdin);freopen("output.out", "w", stdout);

    • 第一个参数为打开文件的文件名;
    • 第二个参数为文件方式,同fopen()函数;
    • 第三个参数为文件指针,通常使用标准流文件(stdin/stdout/stderr)。

    使用freopen()函数,并使用了标准流文件后,就可以直接使用scanf()printf()来读入和写出。

    结束使用fclose(stdin);fclose(stdout)

C++的方法

1
2
3
4
5
6
ifstream inputFL("input.in");
ofstream outputFL("putput.out");
inputFL >> n;
outputFL << n << endl;
inputFL.close();
outputFL.close();

正式题解

基本题意就是给你几个约束条件看他们能不能共存成立。而相等关系的约束条件我们可以很容易地想到将其转换为一个图,出现相等关系就说明它们在一个个图上 $\Rightarrow$ 两个值的最终祖先节点相同。而出现不等关系就说明它们没在一个图上,所以这个问题就可以转换成一个并查集问题。在这里贴上并查基常用的板子:

  • 得到最终祖先:

    1
    2
    3
    4
    5
    int get(int x){
    if(x == fa[x]){
    return x;
    }else return fa[x] = get(fa[x]);
    }
  • 合并两棵树:

    1
    2
    3
    4
    5
    6
    7
    void merge(int a, int b){
    int faOa = get(a);
    int faOb = get(b);
    if(faOa != faOb){
    fa[b] = a;
    }
    }

而注意到题目数据量很大,$i$、$j$ 的范围到了 $10^9$,无法开那么大的数组,所以我们使用到了离散化。我的离散化的博文的传送门:🚪

基本思想就是看输入的两个值是否相同,如果相同就保留到一棵树上。如果不相同的话检查两个点的根结点是否相同,如果相同则说明这两个值已经相同,出现矛盾,则输出“NO”。为了实现这个思想,我们首先要对输入进行排序,将相等关系放在前面预先判断。

AC代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <bits/stdc++.h>
#define inputFL cin
#define outputFL cout
using namespace std;
struct Node{
int x;
int y;
bool e;
}Nodes[100005];
bool cmp(Node a, Node b){
return a.e > b.e;
}
int dict[1000005];
int fa[1000005];
int cnt, uqcnt;
int n;
int get(int x){
if (x == fa[x]) {
return x;
}else return fa[x] = get(fa[x]);
}
// void merge(int x, int y){
// fa[get(x)] = get(y);
// }
int main(){
// ifstream inputFL("prog.in"); // C++方式, C使用freopen()
// ofstream outputFL("prog.out");
int T;
inputFL >> T;
while(T--){
inputFL >> n;
memset(dict, 0, sizeof(dict));
memset(fa, 0, sizeof(fa));
uqcnt = cnt = 0;
for (int i = 0; i < n; i++) {
inputFL >> Nodes[i].x >> Nodes[i].y >> Nodes[i].e;
dict[cnt++] = Nodes[i].x;
dict[cnt++] = Nodes[i].y;
}
sort(dict, dict + cnt);
uqcnt = unique(dict, dict + cnt) - dict;
for (int i = 0; i < n; i++) {
Nodes[i].x = lower_bound(dict, dict + uqcnt, Nodes[i].x) - dict;
Nodes[i].y = lower_bound(dict, dict + uqcnt, Nodes[i].y) - dict;
}
for (int i = 0; i < uqcnt; i++) {
fa[i] = i;
}
bool check = 1;
sort(Nodes, Nodes + n, cmp);
for (int i = 0; i < n; i++) {
int a = get(Nodes[i].x);
int b = get(Nodes[i].y);
if (Nodes[i].e) {
fa[a] = b;
}else{
if (a == b) {
check = 0;
outputFL << "NO" << endl;
break;
}
}
}
if (check)
outputFL << "YES" << endl;
}
}

特别提醒:一定要分清离散化中各个变量的具体含义与用处,否则就会出现以下的状况而无从下手:

1564489428381

算法学习:离散化

Banner 图源网络,侵删。

离散化

离散化:将无限空间中的有限个体映射到有限的空间中。

比如说我有一个无尽的坐标轴,上面有 $10^4$ 个点,每个点的坐标值可以很大很大接近无限。如果我想知道比其中一个点小的点有多少个,暴力比较每个点的坐标值则会因为数据过大而 Boom。而我们通过点与点相对关系,将点的值进行重新赋值,则可以大大减小算法的复杂度。

比如,我现在的数轴上只有6个点, 他们的坐标分别为 $0$、$610$、$10^5+2$、$99$、$5$、$10^9+45$,如果我只是按照他们原有的值进行比较,最大要比较到 $10^9+45$。而如果我们用他们的相对大小来进行比较,即转换为 $0$、$3$、$4$、$2$、$1$、$5$ 则会方便很多。这就是离散化的思想,就是将离散的事物进行重新分配

离散化方法:排序+二分

(推荐使用本方法)

基本原理就是排序后使用STL中的unque()函数来获取整体数据不同元素的个数,然后在已排序序列二分查找 $num[i]$ 的值,从而得到对 $num[i]$ 对应的值,然后进行重新赋值。

1
2
3
4
5
6
7
8
for(int i = 0; i < n; i++){
scanf("%d", &num[i]);
disc[i] = num[i]; // num:原数据数组,disc:离散化后的数组
}
sort(disc, disc + n);
cnt = unique(disc, disc + n) - disc; // STL中的unique函数,具体内容见👇
for(int i = 0; i < n; i++)
num[i] = lower_bound(disc, disc + n, num[i]) - disc;
  • unique(a, b)函数:STL中比较常见的函数,他的功能是“删除”序列中所有相邻的重复元素(只保留一个),因为只是处理相邻的重复元素所以在使用这个函数之前要进行排序。(此处略去更具体的都能再写一页博客的内容)。其中参数a,b为指针,类似sort()函数中的参数。
  • lower_bound(a, b, v)函数:二分查找返回ab指针之间空间中大于等于 $v$ 的第一个迭代器。

离散化方法:排序+暴力

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <bits/stdc++.h>
#define MAX_N 1e5+5 // 根据实际问题调整
struct Node{
int data;
int index;
}num[MAX_N];
bool cmp(Node a, Node b){
return a.data < b.data;
}
int rank[MAX_N], n;
int main(){
scanf("%d", &n);
for(int i = 0;i < n; i++){
scanf("%d", &num[i].data);
num[i].index = i;
}
sort(num, num + n, cmp);
for(int i = 1; i <= n; i++){
rank[num[i].id] = i;
}
return 0;
}

排序之后按照原顺序进行赋值,相同元素就会出现离散化不成同一元素的情况,所以不推荐这种方法。


听大佬说洛谷P1955是一道有关离散化的题,我这个蒟蒻还没有做。🙃

有时间做了再搞题解什么的。🙃

题解我搞出来了,传送门:🚪

算法学习:后缀数组

学习自:

后缀数组简介

后缀:从字符串某个位置 $i$ 到字符串末尾的子串,我们定义以字符串 $str$ 的第 $i$ 位为第一个元素的后缀为suff[i]。(后缀的英文:suffix

后缀数组:把字符串 $str$ 的每一个后缀按照字典序排序后所形成的数组。

后缀数组的实现

变量定义

  • suff[]数组,用来记录从第 $i$ 位开始的后缀
  • sa[]数组(suffix array),存储的是字典第 $i$ 小的后缀的下标。比如sa[0] = 8代表的是suff[]数组中第 $8$ 位后缀在字典序中最小。而suff(sa[0])才真正存储这最小的那个后缀的内容。
  • rank[]数组,与sa[]相反,存储的是下标为 $i$ 的后缀为第几小。一定存在关系 $\text{rank}[\text{sa}[i]] = i$。

倍增算法

问题在于我们怎么给这个后缀数组排序,如果强硬 sort 的话,sort 算法复杂度本来就有 $O(n\log_2n)$ 字符串排序还不用于一般数字的排序,每个字符串对比还有 $O(n)$ 复杂度。也就是说用 sort 的话,复杂度会达到 $O(n^2\log_2n)$。这就很伤不是么,所以我们要想出来一个复杂度更低的算法。

我们知道,两个字符串的比较,如果前半部分相同则比较结果取决于后半部分的比较结果,否则只需要看前半部分的比较结果。基于这个事实,我们考虑以下方法:

对于字符串 $str$,定义k-前缀为:

$$
str_k=\begin{cases}
str[0\dots k - 1] = str.\mathrm{substr}(0, k) & (k\leq str.\mathrm{length}()) \\
str & (k > str.\mathrm{length}())
\end{cases}
$$
然后类似的,我们定义出基于k-前缀意义下的sa[]数组和rank[]数组,在这里我们记作 $sa_k$ 与 $rank_k$ 数组。其中 $sa_k$ 为k-前缀意义下的后缀数组,$rank_k$ 为k-前缀意义下的名次数组。则有以下计算方式:

  • 容易求出 $rank_1$ 的值与 $sa_1$ 的值,只需要进行 sort 对第一个字母排序就可以了。

  • 得到了 $rank_k$,则定义二元组 $(rank_k[i],rank_k[i + k])$,按照“如果 $rank_k[i]$ 相同则比较$rank_k[i +k]$,否则则比较 $rank_k[i]$ ”的方法来进行sort,即可求出 $sa_{2k}$。

  • 求出了 $sa_k$ 则可以很快求出 $rank_k$,有以下关系:
    $$
    rank_k[i] = \begin{cases}
    rank_k[i - 1] & suff[sa[i]]_k = suff[sa[i - 1]]_k \\
    rank_k[i - 1] + 1 & suff[sa[i]] _ k \neq suff[sa[i - 1]]_k
    \end{cases}
    $$

这样的话我们求解的顺序就是:
$$
sa_1 \ \& \ rank_1 \rightarrow sa_2 \rightarrow rank_2 \rightarrow sa_4 \rightarrow rank_4 \rightarrow \cdots \rightarrow sa_n \rightarrow rank_n
$$
当不再出现并列的 $rank$ 的时候就可以结束循环。整个过程如下图所示:

1564227558972

每一次排序需要进行 $n\log_2n$ 次比较,每一次比较需要 $O(1)$ 复杂度,总共进行 $\log_2n$ 次比较,因此总时间复杂度为$O(n\log_2^2n)$。

基数排序

这一部分我们要试图探索比 $O(n\log _2^2n)$ 更优的排序算法。

算法学习:线性基

线性基 ——异或和求最大值

学习自博客:https://blog.sengxian.com/algorithms/linear-basis

基(basis)是线性代数中的一个概念,他是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素被称为基向量。向量空间中的任意一个元素,都可以唯一地被表示成基向量的线性组合。异或空间基向量,被称为线性基。

从线性代数开始的异或世界

线性空间(向量空间)

定义$({\Bbb F},\mathrm V,+,\cdot)$为线性空间(Vector Space)。其中 $\Bbb F$ 为域,其中的元素为标量;$\mathrm V$ 为集合,其中的元素称为向量,有以下两个运算:

  1. 向量加法:$\mathrm V+\mathrm V\rightarrow \mathrm V$,记作 ${\bf v}+{\bf w},\exists {\bf v},{\bf m} \in \mathrm V$;
  2. 标量乘法:${\Bbb F}\cdot \mathrm V\rightarrow \mathrm V$,记作 $a \cdot {\bf v}, \ \exists {\bf a} \in {\Bbb F},{\bf v}\in \mit \mathrm V$

且运算满足以下公理:

  1. 向量加法结合律:${\bf u} + ({\bf v} + {\bf w}) = ({\bf u} + {\bf v} ) + {\bf w}$;
  2. 向量加法交换律:${\bf v} + {\bf w} = {\bf w} + {\bf v}$;
  3. 向量加法的单位元:$\mathrm V$ 中有一个被称为零向量的 $\bf 0$,$\forall {\bf v}\in \mathrm V$,${\bf v} + {\bf 0} = {\bf v}$;
  4. 向量加法的逆元素:$\forall {\bf v}\in \mathrm {V}$,$\exists {\bf w} \in \mathrm V$,使得${\bf v} + {\bf w} = 0$,其中 ${\bf w}$ 称为 ${\bf v}$ 的逆元;
  5. 标量乘法与标量的域乘法相容:$a(b{\bf v} ) = (ab){\bf v}$;
  6. 标量乘法的单位元:域$\Bbb F$存在乘法单位元 $1$ 满足 $1{\bf v} = {\bf v}$;
  7. 标量乘法对向量加法的分配律:$a({\bf u} + {\bf v}) = a{\bf u} + a{\bf v}$;
  8. 标量乘法对域加法的分配律:$(a+b){\bf v} = a{\bf v} + b{\bf v}$。

基本性质

  • 零元素 $0$ 是唯一的;
  • 对任意的$a\in {\Bbb F}$,$a \cdot {\bf 0} = {\bf 0}$;
  • 对任意的${\bf u}\in \mathrm V$,${\bf 0}\cdot{\bf u} = {\bf 0}$( ${\bf 0}$ 是 $\Bbb F$ 的加法单位元);
  • 如果 $a \cdot {\bf u} = {\bf 0}$,则要么 $a = 0$ ,要么 ${\bf u} = {\bf 0}$;
  • 向量加法的逆向量 $\bf v$ 是唯一的,记作$-\bf v$。${\bf u} + {- \bf v}$ 也可以写成 ${\bf u} - \bf v$,两者都是标准的;
  • 对 $\forall {\bf u} \in \mathrm V$, $-1\cdot {\bf u}=-{\bf u}$。
  • 对 $\forall a\in \Bbb F$ 以及${\bf u}\in V$,$(-a)\cdot {\bf u} = -(a\cdot {\bf u}) = a \cdot (-{\bf u})$。

其他扩展内容

最为常见的向量空间的例子是给定了直角坐标系的平面:平面上的每一点 $P$ 都有一个坐标 $P(x,y)$ ,并对应着一个向量 $(x,y)$。所有普通意义上的平面向量组成了一个空间,记作 $\Bbb R^2$(因为每个向量都可以表示为两个实数构成的有序数组$(x,y)$。可以验证,对于普通意义上的向量加法和标量乘法,$\Bbb R^2$ 满足向量空间的所有公理。设所有普通意义上的平面向量记作 $\mathrm V$ ,则 ${\Bbb R}^2 = ({\Bbb R}, \mathrm V,+,\cdot)$。实际上,向量空间是 $\Bbb R^2$ 的推广。

对于通常意义上的多项式加法和标量乘法,所有系数为实数的多项式的集合 $\Bbb R[\bf X]$ 也构成一个向量空间。更广泛的,所有从实数域射到实数域的连续函数的集合 $\mathcal C(\mathbb R,\mathbb R)$也是向量空间

线性无关

对向量空间中 $\mathrm V$ 上的 $n$ 个元素的向量组 $({\bf v}_1,\dots,{\bf v}_n)$,若存在不全为 $0$ 的数 $a_i\in \mathbb F$,满足:
$$
a_1{\bf v}_1 + a_2{\bf v_2} + \dots + a_n{\bf v} _ n = 0
$$
则称 $n$ 个向量线性相关Linearly Dependent),否则称为线性无关Linearly Independent)。

线性组合

对于向量空间中 $\mathrm V$ 上 $n$ 个元素的向量组 $({\bf v}_1,\dots,{\bf v}_n)$,其线性组合Linear Combination)是如下形式的向量:
$$
a_1{\bf v_1} + a_2{\bf v}_2 + \dots+a_n{\bf v}_n
$$
其中 $a_1,\dots,a_n\in \mathbb F$。

张成(Span

对于相连空间中 $V$ 上 $n$ 个元素的向量组 $({\bf v}_1,\dots,{\bf v}_n)$,其所有线性组合所构成的集合称为 $({\bf v}_1,\dots,{\bf v}_n)$ 的张成Span),记作$\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$。

基(Basis)

Basis)(也称为基底)是描述、刻画向量空间的基本工具。向量空间的基是它的一个特殊的子集,基的元素称为基向量。向量空间中任意一个元素,都可以唯一地表示成基向量的线性组合。如果基中元素个数有限,就称向量空间为有限维向量空间,将元素的个数称作向量空间的维数

给定一个向量空间 ${\displaystyle \mathrm {V}}$。${\displaystyle \mathrm {V}}$ 的一组 ${\displaystyle {\mathfrak {B}}}$ 是指 ${\displaystyle \mathrm {V} }$ 里面的可线性生成 ${\displaystyle \mathrm {V} }$ 的一个线性无关子集。${\displaystyle {\mathfrak {B}}}$ 的元素称为基向量

更详细来说,设 ${\displaystyle {\mathfrak {B}}={\mathbf e_{1},\mathbf e_{2},\cdots ,\mathbf e_{n}}}$ 是在系数域 ${\displaystyle \mathbb {F}}$(比如实数域 ${\displaystyle \mathbb {R}}$ 或复数域${\displaystyle \mathbb {C}}$)上的向量空间 ${\displaystyle \mathrm {V}}$ 的有限子集。如果 ${\displaystyle {\mathfrak {B}}}$ 满足下列条件:

  1. 对任意 ${\displaystyle (\lambda_{1},\lambda_{2},\cdots ,\lambda_{n})\in \mathbb {F} ^{n}}$ ,如果 ${\displaystyle \lambda_{1}\mathbf e_{1}+\lambda_{2}\mathbf e_{2}+\cdots +\lambda_{n}\mathbf e_{n}=0}$ 则必然 ${\displaystyle \lambda _{1}=\lambda _{2}=\cdots =\lambda _{n}=0}$;
  2. 对任意 ${\displaystyle \mathbf v\in \mathrm {V} }$,可以选择 ${\displaystyle (\lambda_{1},\lambda_{2},\cdots ,\lambda_{n})\in \mathbb {F} ^{n}}$,使得 ${\displaystyle v=\lambda_{1}\mathbf e_{1}+\lambda_{2}\mathbf e_{2}+\cdots +\lambda_{n}\mathbf e_{n}}$。

就说 ${\displaystyle {\mathfrak {B}}}$ 是向量空间 ${\displaystyle \mathrm {V} }$ 的一组

性质

设 $\mathfrak {B}$ 是向量空间 $\mathrm V$ 的基。则 $\mathfrak {B}$ 具有以下性质:

  1. $\mathrm V$ 是 $\mathfrak {B}$ 的极小生成集,就是说只有 $\mathfrak {B}$ 能张成 $\mathrm V$,而它的任何真子集都不张成全部的向量空间。
  2. $\mathfrak {B}$ 是 $\mathrm V$ 中线性无关向量的极大集合,就是说 $\mathfrak {B}$ 在 $\mathrm V$ 中是线性无关集合,而且 $\mathrm V$ 中没有其他线性无关集合包含它作为真子集。
  3. $\mathrm V$中所有的向量都可以按唯一的方式表达为 $\mathfrak {B}$ 中向量的线性组合。

第三点尤其重要,感性的理解,基就是向量空间中的一个子集,它可以通过唯一的线性组合,来张成向量空间中所有的向量,这样就可以大大的缩小我们向量空间的大小。

线性相关性引理(Linear Dependent Lemma

如果 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$ 在 $\mathrm V$ 中是线性相关的,并且 $\mathbf{v}_1 \neq 0$,则有至少一个 $j \in {2, \ldots, m}$使得下列成立:

  1. $\mathbf{v}_j \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_{j - 1})$;
  2. 如果从$ (\mathbf{v}_1, \ldots, \mathbf{v}_n)$ 去掉第 $j$ 项,则剩余向量组的张成仍然等于 $\mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v_n})$。

证明:

设 $(\mathbf{v}_1, \ldots, \mathbf{v}_n)$在 $\mathrm V$ 中是线性相关的,并且 $\mathbf{v}_1 \neq \mathbf{0}$,则有不全为 $0$ 的 $a_1, \ldots, a_n \in \mathbb F$,使得
$$
a_1\mathbf{v}_1 + \ldots + a_m\mathbf{v}_m = \mathbf{0}
$$
$a_2, a_3, \ldots, a_n$不会全为 $0$(因为 $\mathbf{v}_1 \neq \mathbf{0}$)。设 $j$ 是 ${2, \ldots, m}$ 中使得 $a_j \neq 0$ 的最大者,那么
$$
\mathbf{v}_j = -\frac {a_1} {a_j}\mathbf{v}_1 - \ldots - \frac {a_{j - 1}} {a_j}\mathbf{v}_{j - 1}
$$
这就有 $(1)$ 成立。

为了证明 $(2)$,设 $\mathbf{u} \in \mathrm{span}(\mathbf{v}_1, \ldots, \mathbf{v}_n)$,则存在 $c_1, \ldots, c_n \in F$,使得
$$
\mathbf{u} = c_1\mathbf{v}_1 + \ldots + c_n\mathbf{v}_n
$$
在上面的等式中,可以用之前的等式右边来代替$ \mathbf{v}_j$。这样 $\mathbf{u} $包含于从 $(\mathbf{v}_0, \ldots, \mathbf{v}_n)$ 去掉第 $j$ 项的张成,因而 $(2)$ 成立。

线性基

对于一个十进制数 $a$,我们将其转换为二进制得到 $(b_m\dots b_0)_2$。然后将转换后的二进制看作是一个向量,则得到$\mathbf a = (b_m,b_{m-1},\dots,b_0)$。方便起见,我们称向量 $\mathbf a$ 的第 $i$ 位为 $b_i$。

向量组 $\mathbf a_1,\dots\mathbf a_n$ 可以张成一个向量集合 $\mathrm{span}(\mathbf a_1,\dots,\mathbf a_n)$,则可以得到一个线性空间 $\mathrm V = ({0,1},\mathrm{span}(\mathbf a_1,\dots,\mathbf a_n),\oplus,\cdot)$。

按照以下的方法得到这个线性空间的一个基 $\mathfrak B = (\mathbf a_1,\dots,\mathbf a_n)$ :

第 $1$ 步:如果 $\mathbf a_1 = \mathbf 0$,则从 $\mathfrak B$ 中去除 $\mathbf a_1$,否则保持 $\mathfrak B$ 不变。

第 $j$ 步:如果 $\mathbf a_j \in \mathrm{span}(\mathbf a_1, \dots ,\mathbf a_{j - 1})$ ,则从 $\mathfrak B$ 中去掉 $\mathbf a_j$,否则保持 $\mathfrak B$ 不变。

经过 $n$ 步后终止程序,得到一个向量组 $\mathfrak B$。由于每一次去掉的项包含于前面诸向量的张成,到最后这个组 $\mathfrak B$ 仍然可以张成 $\mathrm V$。而且这一程序确保了 $\mathfrak B$ 中的任何向量都不包含于它前面诸向量的张成,根据线性相关性引理可知 $\mathfrak B$ 是线性无关的。于是 $\mathfrak B$ 是 $\mathrm V$ 的一个基。

利用高斯消元来判断向量能否被前面的向量张成,就可以写出下面的程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#define MAX_BASE 63 // 当数据为long long型时,int型为31
void cal(){
for(int i = 0; i < n; i++){
for(int j = MAX_BASE; j >= 0; j--){
if(a[i] >> j & 1){
if(b[j])
a[i] ^= b[j];
else{
b[j] = a[i];
for (int k = j - 1; k >= 0; k--){
if (b[k] && (b[j] >> k & 1))
b[j] ^= b[k];
}
for (int k = j + 1; k <= MAX_BASE; k++){
if (b[k] >> j & 1)
b[k] ^= b[j];
}
break;
}
}
}
}4
}
  • b[]数组用来记录最后得到的基 $\mathfrak B$ ;a[]数组为起初的每一个数字,即 $\mathbf a_1,\mathbf a_2,\dots,\mathbf a_n$。
  • 虽然数组每一个位置存储的是一个int型数字,但实际上表示的是一个二进制向量,为了表述方便,我们称b[i]为数组b[]的第 $i$ 行。
  • 在第 $i$ 步时,从高到低考虑数 $a_i$ 为 $1$ 的二进制位 $j$,如果数组b[]中第 $j$ 行已经存在内容了,我们就不能将$a_i$ 加到b[]中第 $j$ 行这个位置。而为了保证未来加进去的基向量与其他基向量线性无关,将数 $a_i$ 与 $b_i$ 进行异或计算,就可以消掉可用已经存在的基向量来表示的部分。
  • 如果数组b[]中的第 $j$ 行不存在内容(内容为 $0$),则我们可以将(已经被前面步骤处理好的)数 $a_i$ 加入到这一行。此后为了维护对角矩阵,先用下面的行消自己,再用自己消上面的行。
  • 上面代码中,b[j] >> k & 1可以用来判断 $b_j$ 二进制的第 $k$ 位是否为 $1$。为什么需要& 1?如果没有这个操作,我得到的不仅仅是第 $k$ 的信息,& 1可以让结果只保留第 $k$ 位的信息。

我们来模拟一下这个过程。设 $n = 5$,$a = {7, 1, 4, 3, 5}$。矩阵 $\mathfrak B$ 一开始长这样:
$$
\begin{bmatrix}
0 &0 &0 \\
0 &0 &0 \\
0 &0 &0
\end{bmatrix}
$$
我们从 $a_1$ 开始,$a_1 = 7 = (111)_2 = \mathbf a_1$,而 $\mathfrak B$ 目前为空。所以我就可以直接把他放进去了,因为$j = \mathrm{$MAX\_BASE} = 2$,所以我就把他放在了第二行(因为是上三角矩阵,所以最下面的为第 $0$ 行)。
$$
\begin{bmatrix}
1 &1 &1 \\
0 &0 &0 \\
0 &0 &0
\end{bmatrix}
$$
然后考虑放$a_2$,$a_2 = 1 = (001)_2 = \mathbf a_2$,在 $j = 2$ 与 $j = 1$ 时都不满足a[i] >> j & 1的条件,所以不进行操作。$j = 0$ 时,第 $0$ 行没内容,所以就直接放在了第 $0$ 行上,于是矩阵就成了:
$$
\begin{bmatrix}
1 &1 &1 \\
0 &0 &0 \\
0 &0 &1
\end{bmatrix}
$$
然后用下面的行消自己,好的不存在下面的行。再用自己消上面的行,所以第 $2$ 行会消去最后一个 $1$,矩阵变成:
$$
\begin{bmatrix}
1 &1 &0 \\
0 &0 &0 \\
0 &0 &1
\end{bmatrix}
$$
接下来就轮到了 $a_3$ 了,$a_3 = 4 = (100)_2 = \mathbf a_3$,在 $j = 2$ 时符合条件,但第 $2$ 行已经有内容了,所以我们进行 $a_3 = a_3 \oplus b_2$ 的操作,于是 $a_3$ 成了 $(010)_2$ 。$j = 1$ 时有一次满足条件,所以将他放在了第 $1$ 行上,于是矩阵成了:
$$
\begin{bmatrix}
1 &1 &0 \\
0 &1 &0 \\
0 &0 &1
\end{bmatrix}
$$
然后用下面的行消自己,好的什么都消不了。然后用自己消上面的行,所以第 $2$ 行中间的 $1$ 被消掉了,矩阵变成了:
$$
\begin{bmatrix}
1 &0 &0 \\
0 &1 &0 \\
0 &0 &1
\end{bmatrix}
$$
接下来谁也进不去了,结束。

那既然已经知道了结果会是一个上三角矩阵为啥我不直接生成一个呢?因为最终生成的 $\mathfrak B$ 很有可能不是一个满的上三角矩阵,比如这个样子的:
$$
\begin{bmatrix}
1 &0 &1&0 \\
0 &1 &0 &0 \\
0 &0 &0 &0 \\
0 &0 &0 &1
\end{bmatrix}
$$
这样所有被选上的 $\mathbf a_i$ 构成了一个向量空间 $\mathrm V$ 的一个基 $\mathfrak B$,同样矩阵 $b$ 的每一个非 $\mathbf 0$ 向量 $\mathbf b_i$ 组成的基也是向量空间 $\mathrm V$ 的基。我们所指的线性基,特指高斯消元解出的对角矩阵的非零行构成的向量组。如果矩阵的主对角线上第 $i$ 行的元素为 $1$,此时我们称第 $i$ 位存在于线性基中。对于存在于线性基的二进制位,有一个重要的性质:
$$
对于任意存在于线性基的二进制位\ i ,至多只有一个\ \mathbf b_j\ 满足第\ i\ 位为\ 1。
$$
因为我们已经在得到线性基的过程中,不断地使用每一个向量来对上下进行消除,所以 $\mathbf b_j$ 一定消去了别的向量第 $i$ 位上的 $1$,所以二进制位 $i$ 只存在于 $\mathbf b_j$ 上。而对于不再线性基中的二进制位 $i$,那么主对角线第 $i$ 行位以下的全部为 $0$, 而上方就可能会有若干个 $1$。

线性基的应用

线性基的题型相对比较固定,以下几类基本就是线性基了:

  • 最大异或和
  • 第 $k$ 大异或和 / 这些元素的异或和是第几大
  • 求所有异或值的和

例题$(1)$ To xor or not to xor

题目连接:https://codeforces.com/problemsets/acmsguru/problem/99999/275

Description

The sequence of non-negative integers $A_1$, $A_2$, …, $A_n$ is given. You are to find some subsequence $Ai_1$, $Ai_2$, …, $Ai_k$ $(1 \leq i_1 < i_2 < … < i_k \leq N)$ such, that $Ai_1 \oplus Ai_2 \oplus \dots \oplus Ai_k$ has a maximum value.

Input

The first line of the input file contains the integer number $N$ $(1 \leq N \leq 100)$. The second line contains the sequence $A_1, A_2, \dots , A_n (0 \leq Ai \leq 10^{18})$.

Output

Write to the output file a single integer number – the maximum possible value of $Ai_1 \oplus Ai_2 \oplus \dots \oplus Ai_k$ .

Sample test(s)

Input
1
2
3 
11 9 5
Output
1
14

很单纯的求最大异或和。根据以上的内容,我们可以求出这个向量空间的一组线性基 $\mathfrak B$,则最大的异或和就是将线性基中所有的向量异或起来得到的向量所对应的数。证明如下:

最高的二进制位只存在于数值最大的基向量上,所以最大的基向量肯定要被选。运用归纳法,假设前 $i$ 大的都需要选,考虑第 $i + 1$ 大的向量选不选。显然第 $i + 1$ 大的基向量能对异或和贡献它的最高的二进制位 $j$,因为二进制位 $j$ 在之前的异或和中必然为零(因为二进制位 $j$ 只存在于第 $i + 1$ 大的基向量中)。如果不选,之后的所有数对答案的贡献都只能在小于这个二进制位的地方做贡献,总是比选 $i + 1$ 得到的答案小,所以这个数必须选。

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define MAX_BASE 63
long long a[101];
long long b[MAX_BASE];
int n;
void cal(){
for(int i = 0; i < n; i++){
for(int j = MAX_BASE; j >= 0; j--){
if(a[i] >> j & 1){
if(b[j])
a[i] ^= b[j];
else{
b[j] = a[i];
for (int k = j - 1; k >= 0; k--){
if (b[k] && (b[j] >> k & 1))
b[j] ^= b[k];
}
for (int k = j + 1; k <= MAX_BASE; k++){
if (b[k] >> j & 1)
b[k] ^= b[j];
}
break;
}
}
}
}
}
int main(){
scanf("%d" ,&n);
memset(b, 0, sizeof(b));
memset(choice, 0, sizeof(choice));
for (int i = 0; i < n; i++) {
scanf("%lld", &a[i]);
}
cal();
long long ans = 0;
for (int i = 0; i <= MAX_BASE; i++) {
if(b[i]){
ans ^= b[i];
}
}
printf("%lld\n", ans);
}

算法学习:尺取法

假设给你一个数组与一个整数,要求你的到这个数组中的一个子区间使其的区间和等于这个整数,你会怎么做呢。可能首先想到的就是开一个双重循环,然后每一次都求一次和,然后和给定的数进行比较:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int sum;
int ansi, ansj;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
sum = 0;
for(int k = i; k <= j; k++){
sum += ls[k];
}
if(sum == x){
ansi = i; ansj = j;
goto ans;
}
}
}
ans:
printf("%d %d\n", ansi, ansj);

这样的话,复杂度就会到达 $O(n^2)$。

尺取法的算法思想来源于以上那个算法,区别在于不再对前后指针进行疯狂枚举,也不再需要每次都进行一次求和。我们设置两个指针,起初都指向开头。然后如果区间的元素和小于给定的数,则将右指针右移。如果大于指定的数,则将区间的左指针右移。相同就出结果了。这样的话每次求和只需要加上或减去那个唯一一个有区别的元素。复杂度会降低到 $O(n)$。

如下习题(POJ 3016):

Description

A sequence of $N$ positive integers $(10 < N < 100000)$, each of them less than or equal $10000$, and a positive integer $S(S < 100000000)$ are given. Write a program to find the minimal length of the subsequence of consecutive elements of the sequence, the sum of which is greater than or equal to $S$.

Input

The first line is the number of test cases. For each test case the program has to read the numbers $N$ and $S$, separated by an interval, from the first line. The numbers of the sequence are given in the second line of the test case, separated by intervals. The input will finish with the end of file.

Output

For each the case the program has to print the result on separate line of the output file. if no answer, print $0$.

Sample Input

1
2
3
4
5
2
10 15
5 1 3 5 10 7 4 9 2 8
5 11
1 2 3 4 5

Sample Output

1
2
2
3

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <climits>
using namespace std;
int lis[100005];
long long sum;
int min(int a, int b){
if(a > b)
return b;
else return a;
}
int main(){
int T;
scanf("%d", &T);
while(T--){
int N, S;
scanf("%d %d", &N, &S);
for (size_t i = 0; i < (size_t)N; i++) {
scanf("%d", &lis[i]);
}
int left = 0, right = 0;
sum = lis[0];
int ans = INT_MAX;
while(left <= right && right < N){
if(sum < S){
right++;
sum += lis[right];
}else if(sum >= S){
ans = min(ans, right - left + 1);
sum -= lis[left];
left++;
}
}>
if(ans != INT_MAX)
printf("%d\n", ans);
else printf("0\n");
}
}
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×