题目链接：戳这里
参考博客：戳这里 （看的我叹为观止

题意：求有多少个n*n矩阵满足下列条件

• Ai, j ∈ {0, 1, 2} for all 1 ≤ i, j ≤ n.
• Ai, j = Aj, i for all 1 ≤ i, j ≤ n.
• Ai, 1 + Ai, 2 + … + Ai, n = 2 for all 1 ≤ i ≤ n.
• A1, 1 = A2, 2 = … = An, n = 0.

解题思路：根据上面的条件我们会发现这个矩阵其实可以类比图的邻接矩阵。每个点的度为2相当于该点在一个环内。

题目链接：戳这里
参考博客：戳这里 (阿狸现在越来越强了哎

题意：长度为n的字符串，删掉m个字符后有多少种不同的字串。

解题思路：dp[i][j]表示加入第i个数字后，总共删掉j个数字时，有多少种不同的序列。假设不考虑有重复的情况，dp方程为：dp[i][j]=dp[i-1][j] (第i个数字不删)+dp[i-1][j-1] (第i个数字删)。

题目链接：戳这里
参考博客：戳这里

先备知识

LGV 算法 (Lindström–Gessel–Viennot lemma)

从{a1,a2,a3,...an}到{b1,b2,...bn}的不相交路径的条数

题目链接：戳这里

题意：给出G1，G2两个图判断G2中有多少个子图与G1同构。

解题思路：这题的难点在于构造。我们可以设一个mp数组作为G1的映射，然后全排列mp数组，判断G2中有多少个子图与G1同构。

例如：

首先介绍dijkstra和spfa两者的实现思路

参考博客：戳这里

djkstra

Dijkstra是一种求单源最短路的基础算法，时间复杂度在不加堆优化的情况下是o(n^2)的，加了堆优化就能简化到o(nlogn)，而且算法稳定性很强（从这点上来说比SPFA好多了，具体怎么好下面再讲），基础思路如下：

题目链接：戳这里

题意：t组样例，每组给n个数和q次查询，求每次查询中[1, l]和[r, n]中不同的数的个数

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1

$ hexo new "My New Post"

More info: Writing

Run server

1

$ hexo server

More info: Server

Generate static files

1

$ hexo generate

More info: Generating

Deploy to remote sites

1

$ hexo deploy

More info: Deployment