SmallMatch

123456789101112131415161718192021222324252627282930313233class Solution {public: int quickSelect(vector<int>& a, int l, int r, int index) { int q = randomPartition(a, l, r); if (q == index) { return a[q]; } else { return q < index ? quickSelect(a, q + 1, r, index) : quickSelect(a, l, q - 1, index); } } inline int randomPartition(vector<int>& a, int l, int r) { int i = ...

四种边 1.树枝边 (x是y的父节点)(是一种特殊的前向边) 2.前向边 (x是y的祖先结点) 3.后向边 (x是y的孙子结点) 4.横插边 (X 和 y是不处于不同分支，x->y,y是已经搜过的点) 定义两个时间戳 1234按照访问的时间顺序，定义时间戳dfn[u]表示遍历到u的时间戳low[u]表示从u开始走，所能遍历到的最小的时间戳是什么当dfn[u] == low[u]时，点u即为该连通分量的最高点

1.优化搜素顺序2.排除等效冗余3.可行性剪枝4.最优性剪枝5.记忆化搜索(DP)

博弈问题一、博弈问题特点1.1 状态的阐述必胜状态，必败状态，必和状态 · 对于特定的状态，如果游戏已经结束，则根据结束时的状态决定必胜，必败和必和。 ​ · 如果已经分出胜负的话，那么该状态对于获胜方为必胜状态，对于落败方为必败状态 ​ · 如果是平局，那么对于该状态对于双方都是必和状态 · 从特定状态开始，如果存在一个操作将状态变成必败状态，则当前玩家可以选择该操作，当对方操作的时候，对方选手的状态就为必败状态，因此该特定状态对于当前玩家为必胜状态 · 从特定状态开始，如果所有的操作都会将状态变成为必胜状态，那么当前玩家不管选择什么操作，当对手操作的时候，对方都为必胜状态，因此该特定状态对于当前玩家为必败状态 · 从特定状态开始，如果任何操作都不能将状态变为必败状态，但是存在一种操作将状态变为必和状态，则当前玩家选择当前操作，将必和状态留给对方，因此该特定状态对于双方玩家都为必和状态 1.2 最优策略· 争取必胜。 · 在无法达到必胜的状态下，争取必和 二、例题 913. 猫和老鼠 - 力扣（LeetCode） (leetcode-cn.com) 三、解题思路由于博 ...

基环树一、定义具有N个点N条边的连通图 形如 二、例题力扣5970](https://leetcode-cn.com/problems/maximum-employees-to-be-invited-to-a-meeting/) 三、解题思路由题目可知，判断一个员工是否能上桌，需要他喜欢的员工也要上桌，同时每个人身边最多只能做两个人，因此对于最后上桌的情况分为两种: · 每个人，左边坐着喜欢自己的员工，右边做着自己喜欢的员工 · 有两个员工相互喜欢，可以补充喜欢这两个员工的人，补充的人最后一个人为没有人喜欢，即左右两边其中一个坐着自己的喜欢的员工，另一个位置的人与自己无关。也满足题意 四、解题代码拓扑排序 + 深度优先搜索 + 分类讨论 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071class Solution {public: int maxim ...

一、字符串哈希的含义hash，就是将一个东西映射成另一个东西，类似于Map。 key->value 那么对于字符串Hash，其实就是将构造一个数字使它唯一代表一个字符串，用它的目的在于比较一个滚动的字符串是否相同的时候，我们不需要重新比较这两个字符串所有的字符，而是直接通过简单的数字计算就可以得出滚动后的字符串所对应的value，从而比较value值判断字符串是否相等，其时间复杂度为O(1)，这是一个极其高效的比较方式 二、例题2.1 题目 2.2 题目解读此题查找的是找出最长的重复字串，关键点在于:重复子串部分可以有重叠，因此我们需要逐个对比即枚举每个下标i然后取模式串的长度k，判断以下标i开始长度为k的字串是否有与其相等的字串 2.3 朴素解法枚举，然后暴力比较 缺点：比较函数是逐个字符比较，相邻的两个字符串有很多公共部分没有合理利用。时间复杂度为O(n^2) 1234567891011121314151617class Solution {public: string longestDupSubstring(string s) { i ...

BS4笔记官方文档 一、解析HTML文件1.1 配合request解析从网络上爬取的HTML12345# 爬取HTMLimport requestsreq = requests.get("https://www.baidu.com")req.encoding = 'utf-8'soup = BeautifulSoup(req.text,'lxml') 1.2 解析本地文件12345678# 直接打开 (推荐)soup = BeautifulSoup(open('sanguo.html',encoding = 'utf-8'),'lxml')#open()里面为本地的html路径# 先打开文件，再解析path = 'baidu.html'htmlfile = open(path, 'r', encoding='utf-8')htmlhandle = htmlfile.read()soup = Beautifu ...

Kruskal算法1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768class UF{public: vector<int>fa; vector<int>rank; int n; int comp_cnt;public: UF(int _n): n(_n), comp_cnt(_n), fa(_n), rank(_n, 1){ iota(fa.begin(),fa.end(),0); } int find(int x){ //cout << "find" << endl; return x==fa[x] ? x:(fa[x] = find(fa[x])); } void m ...

KMP算法一、适用范围一般用于字符的模式匹配问题 二、核心原理2.1前缀函数定义:对于长度为m的字符串s，其前缀函数为π(i)(0≤i<m)表示s的字串s[0:i]的最长的相等的真前缀和真后缀的长度。特别地，如果不存在符合条件的前后缀，那么π(i)=0。其中真前缀与真后缀的定义为不等于自身的前缀和后缀(就是不取下标为i的元素)。 2.2如何求前缀函数三、参考链接实现 strStr() - 实现 strStr() - 力扣（LeetCode） (leetcode-cn.com) 四、next代码实现 1234567891011121314151617181920212223242526272829303132class Solution {public: int strStr(string s, string p) { int n = s.size(), m = p.size(); if(m == 0) return 0; //设置哨兵 s.insert(s.begin(),' &# ...

递归分治一、思想二、例题P1010洛谷 三、解题思路我们很容易发现该题目符合递归思想，将大问题分解成小问题，分解到可以直接解决的时候进行终止 原本的思路：从左端开始遍历即通过位运算将各个位置进行遍历，关键在于对”()”和”+”的处理，括号只在i = 1 的时候是没有的，对于”+”的处理，我将采用在每个后面都加上”+”,最后进行特殊判断，将最末尾的”+”进行删除就OK 改进思路，我们知道”+”只在最后面不能存在，所以我们从后开始遍历，新的答案将加在前面，在当前ans==””时候，我们不加”+”，同时我们从右往左遍历，可以减少遍历次数，同时，将采用do while结构，可以至少进行一次操作。 三、代码12345678910111213141516171819202122232425262728#include <bits/stdc++.h>using namespace std;string add(int n, string ans) { if (n == 0) { return "0"; } ...