-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
252 lines (222 loc) · 30.3 KB
/
index.html
File metadata and controls
252 lines (222 loc) · 30.3 KB
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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
<!DOCTYPE html><html lang="en" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>ExileK1G的个人博客</title><meta name="author" content="ExileK1G"><meta name="copyright" content="ExileK1G"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="be yourself">
<meta property="og:type" content="website">
<meta property="og:title" content="ExileK1G的个人博客">
<meta property="og:url" content="https://exilek1g.github.io/index.html">
<meta property="og:site_name" content="ExileK1G的个人博客">
<meta property="og:description" content="be yourself">
<meta property="og:locale" content="en_US">
<meta property="og:image" content="https://i.loli.net/2021/02/24/5O1day2nriDzjSu.png">
<meta property="article:author" content="ExileK1G">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://i.loli.net/2021/02/24/5O1day2nriDzjSu.png"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="https://exilek1g.github.io/index.html"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = {
root: '/',
algolia: undefined,
localSearch: undefined,
translate: undefined,
noticeOutdate: undefined,
highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
copy: {
success: 'Copy Successful',
error: 'Copy Error',
noSupport: 'Browser Not Supported'
},
relativeDate: {
homepage: false,
post: false
},
runtime: '',
dateSuffix: {
just: 'Just now',
min: 'minutes ago',
hour: 'hours ago',
day: 'days ago',
month: 'months ago'
},
copyright: undefined,
lightbox: 'fancybox',
Snackbar: undefined,
infinitegrid: {
js: 'https://cdn.jsdelivr.net/npm/@egjs/infinitegrid/dist/infinitegrid.min.js',
buttonText: 'Load More'
},
isPhotoFigcaption: false,
islazyload: false,
isAnchor: false,
percent: {
toc: true,
rightside: false,
},
autoDarkmode: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
title: 'ExileK1G的个人博客',
isPost: false,
isHome: true,
isHighlightShrink: false,
isToc: false,
postUpdate: '2024-03-04 19:21:29'
}</script><script>(win=>{
win.saveToLocal = {
set: (key, value, ttl) => {
if (ttl === 0) return
const now = Date.now()
const expiry = now + ttl * 86400000
const item = {
value,
expiry
}
localStorage.setItem(key, JSON.stringify(item))
},
get: key => {
const itemStr = localStorage.getItem(key)
if (!itemStr) {
return undefined
}
const item = JSON.parse(itemStr)
const now = Date.now()
if (now > item.expiry) {
localStorage.removeItem(key)
return undefined
}
return item.value
}
}
win.getScript = (url, attr = {}) => new Promise((resolve, reject) => {
const script = document.createElement('script')
script.src = url
script.async = true
script.onerror = reject
script.onload = script.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
script.onload = script.onreadystatechange = null
resolve()
}
Object.keys(attr).forEach(key => {
script.setAttribute(key, attr[key])
})
document.head.appendChild(script)
})
win.getCSS = (url, id = false) => new Promise((resolve, reject) => {
const link = document.createElement('link')
link.rel = 'stylesheet'
link.href = url
if (id) link.id = id
link.onerror = reject
link.onload = link.onreadystatechange = function() {
const loadState = this.readyState
if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
link.onload = link.onreadystatechange = null
resolve()
}
document.head.appendChild(link)
})
win.activateDarkMode = () => {
document.documentElement.setAttribute('data-theme', 'dark')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
}
}
win.activateLightMode = () => {
document.documentElement.setAttribute('data-theme', 'light')
if (document.querySelector('meta[name="theme-color"]') !== null) {
document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
}
}
const t = saveToLocal.get('theme')
if (t === 'dark') activateDarkMode()
else if (t === 'light') activateLightMode()
const asideStatus = saveToLocal.get('aside-status')
if (asideStatus !== undefined) {
if (asideStatus === 'hide') {
document.documentElement.classList.add('hide-aside')
} else {
document.documentElement.classList.remove('hide-aside')
}
}
const detectApple = () => {
if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
document.documentElement.classList.add('apple')
}
}
detectApple()
})(window)</script><meta name="generator" content="Hexo 6.3.0"></head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="https://i.loli.net/2021/02/24/5O1day2nriDzjSu.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/archives/"><div class="headline">Articles</div><div class="length-num">25</div></a><a href="/tags/"><div class="headline">Tags</div><div class="length-num">1</div></a><a href="/categories/"><div class="headline">Categories</div><div class="length-num">2</div></a></div><hr class="custom-hr"/></div></div><div class="page" id="body-wrap"><header class="full_page" id="page-header"><nav id="nav"><span id="blog-info"><a href="/" title="ExileK1G的个人博客"><span class="site-name">ExileK1G的个人博客</span></a></span><div id="menus"><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="site-info"><h1 id="site-title">ExileK1G的个人博客</h1></div><div id="scroll-down"><i class="fas fa-angle-down scroll-down-effects"></i></div></header><main class="layout" id="content-inner"><div class="recent-posts" id="recent-posts"><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2024/03/04/%E7%88%AC%E8%99%AB%E7%9F%A5%E4%B9%8E/" title="python爬虫爬取知乎评论">python爬虫爬取知乎评论</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2024-03-03T16:00:00.000Z" title="Created 2024-03-04 00:00:00">2024-03-04</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%88%AC%E8%99%AB/">爬虫</a></span></div><div class="content">12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152# -*- coding:utf-8 -*-import jsonimport socketimport urllib.errorimport requestsimport urllib.requestimport urllib.parsefrom bs4 import BeautifulSoupimport reimport datetimeimport timeimport osimport xlwings as xwimport pandas as pdfrom pandas import Series, DataFramefrom icecream import icheaders = { 'cookie': 'SESSIONID=NbZdSDM9vxjCm49QloVUek1p4SESon111VN5lO28kIn; JOID=UFsVAkiK ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2023/12/28/%E5%B7%A6%E7%A8%8B%E4%BA%91%E7%AE%97%E6%B3%95%E4%BD%93%E7%B3%BB%E8%AF%BE%E7%AC%94%E8%AE%B0/IndexTree%E3%80%81AC%E8%87%AA%E5%8A%A8%E6%9C%BA/" title="IndexTree、AC自动机">IndexTree、AC自动机</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2023-12-27T16:00:00.000Z" title="Created 2023-12-28 00:00:00">2023-12-28</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">IndexTree特点:
1)支持区间查询
2)没有线段树那么强,但是非常容易改成一维,二维,三维的结构
3)只指出单点更新(线段树可以实现范围更新)
ps:线段树的作用:1.add(L,R,10),某个区间同时加上10
2.update(L,R,7)某个区间同时变成7
3.求区间(L,R)的累加和
三分函数的时间复杂度都为O(logN)
例如数组{1,2,3,4,5,6,7,8}
index=1->管1
index=2->管1,2
index=3->管3
index=4->管1,2,3,4
index=5->管5
index=6->管5,6
index=7->管7
index=8->管1,2,3,4,5,6,7,8
规律一:当将index化为二进制表示的形式
如当index=8=01000
将最右边的1改为0并在末尾加上1后的二进制形式为index’=00001
则index ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2023/12/26/%E5%B7%A6%E7%A8%8B%E4%BA%91%E7%AE%97%E6%B3%95%E4%BD%93%E7%B3%BB%E8%AF%BE%E7%AC%94%E8%AE%B0/KMP%E7%AE%97%E6%B3%95/" title="KMP算法">KMP算法</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2023-12-25T16:00:00.000Z" title="Created 2023-12-26 00:00:00">2023-12-26</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">KMP算法简单介绍KMP（Knuth-Morris-Pratt）算法是一种用于字符串匹配的经典算法，其目的是在一个文本串（主串）中查找一个模式串的出现位置。与朴素的字符串匹配算法相比，KMP算法具有更高的效率，特别是在处理大型文本时。
KMP算法的核心思想是利用已经匹配过的部分信息来避免不必要的比较。算法的关键在于构建一个部分匹配表（Partial Match Table，PMT），该表用于存储模式串中每个位置的最长前缀和最长后缀的匹配长度。
经典例题引入题目描述:给定文本串 T 和模式串 P，找到模式串在文本串中的第一次出现的位置。
一般的暴力算法(朴素字符串匹配算法):
1234567891011121314151617int search(char text[], char pattern[]) { int m = strlen(pattern); int n = strlen(text); for (int i = 0; i <= n - m; i++) { int j; for (j = 0; j < ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2023/12/24/%E5%B7%A6%E7%A8%8B%E4%BA%91%E7%AE%97%E6%B3%95%E4%BD%93%E7%B3%BB%E8%AF%BE%E7%AC%94%E8%AE%B0/%E6%9A%B4%E5%8A%9B%E9%80%92%E5%BD%92%E5%88%B0%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/" title="暴力递归到动态规划">暴力递归到动态规划</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2023-12-23T16:00:00.000Z" title="Created 2023-12-24 00:00:00">2023-12-24</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">dp数组的维数–>看可变参数的个数
模型:从左往右尝试模型,范围尝试模型,样本对应模型,业务限制模型
题目一 robotwalk题目描述:
假设有排成一行的N个位置，记为1～N，N一定大于或等于2开始时机器人在其中的M位置上（M一定是1～N中的一个）如果机器人来到1位置，那么下一步只能往右来到2位置；
如果机器人来到N位置，那么下一步只能往左来到N—1位置；如果机器人来到中间位置，那么下一步可以往左走或者往右走；
规定机器人必须走K步，最终能来到P位置（P也是1～N中的一个）的方法有多少种给定四个参数N、M、K、P，返回方法数。
方法一(纯递归dfs)(有大量的重复计算):
123456789101112131415161718192021//方法一:纯暴力搜索(dfs，递归)//机器人当前来到的位置是cur//机器人还有rest步需要去走//最终的目标是aim//有哪些位置？1-N//返回：机器人从cur出发，走过rest步之后，最终停在aim的方法数是多少int process1(int cur,int rest,int aim,int N){ if(rest ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2023/12/23/%E7%94%B1%E9%80%92%E5%BD%92,%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2%E5%BC%95%E5%85%A5%E9%80%92%E6%8E%A8/" title="由递归,记忆化搜索引入递推">由递归,记忆化搜索引入递推</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2023-12-22T16:00:00.000Z" title="Created 2023-12-23 00:00:00">2023-12-23</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">以经典的跳楼梯问题来解析递推(dfs),记忆化搜索与递推的区别递归(类似于深度优先搜索dfs)(dfs属于递归的一种)记忆化搜索
递推(ps.记忆化搜索和递推的时间复杂度都比递归小,但空间复杂度高,实现了空间换时间)(动态规划是递推的一个子集)
优化过程:最暴力的dfs–>记忆化搜索–>递推(dp )
记忆化搜索=暴力dfs+记录答案
递推的公式=dfs向上递归的公式(递推公式通常更容易理解为自底向上的递归)
递推数组的初始值=递归的边界
例题:大盗阿福
题目描述阿福是一名经验丰富的大盗。趁着月黑风高，阿福打算今晚洗劫一条街上的店铺。
这条街上一共有 NN 家店铺，每家店中都有一些现金。阿福事先调查得知，只有当他同时洗劫了两家相邻的店铺时，街上的报警系统才会启动，然后警察就会蜂拥而至。
作为一向谨慎作案的大盗，阿福不愿意冒着被警察追捕的风险行窃。他想知道，在不惊动警察的情况下，他今晚最多可以得到多少现金？
【输入】输入的第一行是一个整数T(T≤50)T(T≤50) ，表示一共有T组数据。
接下来的每组数据，第一行是一个整数N(1≤N≤100 ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2023/12/22/DFS%E6%AD%A3%E7%A1%AE%E5%85%A5%E9%97%A8%E6%96%B9%E5%BC%8F%20%20DFS%20+%20%E9%80%92%E5%BD%92%E4%B8%8E%E9%80%92%E6%8E%A8%E4%B9%A0%E9%A2%98%20%E7%88%86%E6%90%9C/" title="DFS正确入门方式 DFS + 递归与递推习题 爆搜">DFS正确入门方式 DFS + 递归与递推习题 爆搜</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2023-12-21T16:00:00.000Z" title="Created 2023-12-22 00:00:00">2023-12-22</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">
DFS入门级模板看CSDN文章 DFS入门级（模板）_dfs模型-CSDN博客
题目一 烤鸡
题目描述猪猪 Hanke 特别喜欢吃烤鸡（本是同畜牲，相煎何太急！）Hanke 吃鸡很特别，为什么特别呢？因为他有 10种配料（芥末、孜然等），每种配料可以放 1 到 3 克，任意烤鸡的美味程度为所有配料质量之和。
现在， Hanke 想要知道，如果给你一个美味程度 n ，请输出这 1010 种配料的所有搭配方案。
输入格式一个正整数 n，表示美味程度。
输出格式第一行，方案总数。
第二行至结束，1010 个数，表示每种配料所放的质量，按字典序排列。
如果没有符合要求的方法，就只要在第一行输出一个 0。
输入输出样例输入 #1
111
输出 #1
1234567891011101 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2023/12/22/c++%E6%B1%82%E6%9C%80%E5%A4%A7%E5%85%AC%E5%80%8D%E6%95%B0%E5%92%8C%E6%9C%80%E5%B0%8F%E5%85%AC%E7%BA%A6%E6%95%B0/" title="c++求最大公倍数和最小公约数">c++求最大公倍数和最小公约数</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2023-12-21T16:00:00.000Z" title="Created 2023-12-22 00:00:00">2023-12-22</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">一：
123456789101112#include <iostream>// 计算最大公约数（Greatest Common Divisor）int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b);}// 计算最小公倍数（Least Common Multiple）int lcm(int a, int b) { return a / gcd(a, b) * b; // LCM = a * b / GCD(a, b)}
二（c++中的库函数）:
123#include <numeric> // 包含 gcd 和 lcm 函数int gcdResult = std::gcd(num1, num2);int lcmResult = std::lcm(num1, num2);
</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2023/12/20/%E8%BF%B7%E5%AE%AB%E9%97%AE%E9%A2%98/" title="迷宫问题">迷宫问题</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2023-12-19T16:00:00.000Z" title="Created 2023-12-20 00:00:00">2023-12-20</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">迷宫问题
问题描述:迷宫由m行n列的单元格组成,每个单元格要么是空地,要么是障碍物,请你找出一条从起点到终点的最小路径长度
DFS深搜解决迷宫问题
DFS深搜要点：
使用递归方式求解：先判断当前点是否为终点，非终点时递归调用DFS
调用DFS前当前点标记为已访问，DFS执行结束后当前点标记为未访问：前者防止递归调用时重复访问当前点走回头路，后者是为探索其他路径时能重复访问该点。
使用外部变量统计最小步数
代码:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354#include<stdio.h>int min = 999999;int p, q,m,n;//p,q分别表示终点的行坐标和列坐标。 m，n表示该迷宫的函数和列数int dx[4] = { 0,1,0,-1 };int dy[4] = { 1,0,-1,0 };int a[100][100];//1表示空地，2表示障碍物in ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2023/12/18/%E5%B7%A6%E7%A8%8B%E4%BA%91%E7%AE%97%E6%B3%95%E4%BD%93%E7%B3%BB%E8%AF%BE%E7%AC%94%E8%AE%B0/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95/" title="贪心算法">贪心算法</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2023-12-17T16:00:00.000Z" title="Created 2023-12-18 00:00:00">2023-12-18</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">贪心算法的基本思想是每次选择局部最优解,期望最终得到全局最优解,其解题思路无法证明,只能用对数器(另个用纯暴力解法)来证明其正确性(贪心就是没道理)(ps.证明贪心不对–>举反例)
题目一
题目描述:一个项目要占用一个会议室宣讲，会议室不能同时容纳两个项目的宣讲，给你每一个项目开始的时间和结束的时间，你来安排宣讲的日程，要求会议室进行的宣讲的场次最多，返回最多的宣讲场次
贪心算法思路:对于这个问题，我们可以按照项目的结束时间进行排序，然后依次选择结束时间最早的项目。在每一步选择时，我们==选择的项目应该是与当前会议室时间不冲突且结束时间最早的项目==。这样可以最大程度地释放会议室，使得能够安排更多的宣讲场次。
代码:
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include <stdio.h>#include <stdlib.h>// 结构体表示一个项目struct ...</div></div></div><div class="recent-post-item"><div class="recent-post-info no-cover"><a class="article-title" href="/2023/12/18/%E5%B7%A6%E7%A8%8B%E4%BA%91%E7%AE%97%E6%B3%95%E4%BD%93%E7%B3%BB%E8%AF%BE%E7%AC%94%E8%AE%B0/%E5%B9%B6%E6%9F%A5%E9%9B%86/" title="并查集">并查集</a><div class="article-meta-wrap"><span class="post-meta-date"><i class="far fa-calendar-alt"></i><span class="article-meta-label">Created</span><time datetime="2023-12-17T16:00:00.000Z" title="Created 2023-12-18 00:00:00">2023-12-18</time></span><span class="article-meta"><span class="article-meta-separator">|</span><i class="fas fa-inbox"></i><a class="article-meta__categories" href="/categories/%E7%AE%97%E6%B3%95/">算法</a></span></div><div class="content">并查集算法
典型题目
题解：
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include<cstdio>#include<cstdlib>using namespace std;#define MAXN 20001int fa[MAXN];void init(int n) { for (int i = 1; i <= n; i++) fa[i] = i;}int find(int x){ if (x == fa[x]) return x; else { fa[x] = find(fa[x]);//父节点设为根节点 return fa[x];//返回父节点 }}void unionn(int i, int j) { int i_fa = find(i);//找到i的祖先 int j_fa = ...</div></div></div><nav id="pagination"><div class="pagination"><span class="page-number current">1</span><a class="page-number" href="/page/2/#content-inner">2</a><a class="page-number" href="/page/3/#content-inner">3</a><a class="extend next" rel="next" href="/page/2/#content-inner"><i class="fas fa-chevron-right fa-fw"></i></a></div></nav></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="is-center"><div class="avatar-img"><img src="https://i.loli.net/2021/02/24/5O1day2nriDzjSu.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/></div><div class="author-info__name">ExileK1G</div><div class="author-info__description">be yourself</div></div><div class="card-info-data site-data is-center"><a href="/archives/"><div class="headline">Articles</div><div class="length-num">25</div></a><a href="/tags/"><div class="headline">Tags</div><div class="length-num">1</div></a><a href="/categories/"><div class="headline">Categories</div><div class="length-num">2</div></a></div><a id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/xxxxxx"><i class="fab fa-github"></i><span>Follow Me</span></a></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn fa-shake"></i><span>Announcement</span></div><div class="announcement_content">This is my Blog</div></div><div class="sticky_layout"><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>Recent Post</span></div><div class="aside-list"><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2024/03/04/%E7%88%AC%E8%99%AB%E7%9F%A5%E4%B9%8E/" title="python爬虫爬取知乎评论">python爬虫爬取知乎评论</a><time datetime="2024-03-03T16:00:00.000Z" title="Created 2024-03-04 00:00:00">2024-03-04</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2023/12/28/%E5%B7%A6%E7%A8%8B%E4%BA%91%E7%AE%97%E6%B3%95%E4%BD%93%E7%B3%BB%E8%AF%BE%E7%AC%94%E8%AE%B0/IndexTree%E3%80%81AC%E8%87%AA%E5%8A%A8%E6%9C%BA/" title="IndexTree、AC自动机">IndexTree、AC自动机</a><time datetime="2023-12-27T16:00:00.000Z" title="Created 2023-12-28 00:00:00">2023-12-28</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2023/12/26/%E5%B7%A6%E7%A8%8B%E4%BA%91%E7%AE%97%E6%B3%95%E4%BD%93%E7%B3%BB%E8%AF%BE%E7%AC%94%E8%AE%B0/KMP%E7%AE%97%E6%B3%95/" title="KMP算法">KMP算法</a><time datetime="2023-12-25T16:00:00.000Z" title="Created 2023-12-26 00:00:00">2023-12-26</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2023/12/24/%E5%B7%A6%E7%A8%8B%E4%BA%91%E7%AE%97%E6%B3%95%E4%BD%93%E7%B3%BB%E8%AF%BE%E7%AC%94%E8%AE%B0/%E6%9A%B4%E5%8A%9B%E9%80%92%E5%BD%92%E5%88%B0%E5%8A%A8%E6%80%81%E8%A7%84%E5%88%92/" title="暴力递归到动态规划">暴力递归到动态规划</a><time datetime="2023-12-23T16:00:00.000Z" title="Created 2023-12-24 00:00:00">2023-12-24</time></div></div><div class="aside-list-item no-cover"><div class="content"><a class="title" href="/2023/12/23/%E7%94%B1%E9%80%92%E5%BD%92,%E8%AE%B0%E5%BF%86%E5%8C%96%E6%90%9C%E7%B4%A2%E5%BC%95%E5%85%A5%E9%80%92%E6%8E%A8/" title="由递归,记忆化搜索引入递推">由递归,记忆化搜索引入递推</a><time datetime="2023-12-22T16:00:00.000Z" title="Created 2023-12-23 00:00:00">2023-12-23</time></div></div></div></div><div class="card-widget card-categories"><div class="item-headline">
<i class="fas fa-folder-open"></i>
<span>Categories</span>
</div>
<ul class="card-category-list" id="aside-cat-list">
<li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E7%88%AC%E8%99%AB/"><span class="card-category-list-name">爬虫</span><span class="card-category-list-count">1</span></a></li><li class="card-category-list-item "><a class="card-category-list-link" href="/categories/%E7%AE%97%E6%B3%95/"><span class="card-category-list-name">算法</span><span class="card-category-list-count">20</span></a></li>
</ul></div><div class="card-widget card-tags"><div class="item-headline"><i class="fas fa-tags"></i><span>Tags</span></div><div class="card-tag-cloud"><a href="/tags/%E6%95%B0%E7%BB%84/" style="font-size: 1.1em; color: #999">数组</a></div></div><div class="card-widget card-archives"><div class="item-headline"><i class="fas fa-archive"></i><span>Archives</span></div><ul class="card-archive-list"><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2024/03/"><span class="card-archive-list-date">March 2024</span><span class="card-archive-list-count">1</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2023/12/"><span class="card-archive-list-date">December 2023</span><span class="card-archive-list-count">17</span></a></li><li class="card-archive-list-item"><a class="card-archive-list-link" href="/archives/2023/11/"><span class="card-archive-list-date">November 2023</span><span class="card-archive-list-count">7</span></a></li></ul></div><div class="card-widget card-webinfo"><div class="item-headline"><i class="fas fa-chart-line"></i><span>Info</span></div><div class="webinfo"><div class="webinfo-item"><div class="item-name">Article :</div><div class="item-count">25</div></div><div class="webinfo-item"><div class="item-name">UV :</div><div class="item-count" id="busuanzi_value_site_uv"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">PV :</div><div class="item-count" id="busuanzi_value_site_pv"><i class="fa-solid fa-spinner fa-spin"></i></div></div><div class="webinfo-item"><div class="item-name">Last Update :</div><div class="item-count" id="last-push-date" data-lastPushDate="2024-03-04T11:21:29.814Z"><i class="fa-solid fa-spinner fa-spin"></i></div></div></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">©2020 - 2024 By ExileK1G</div><div class="framework-info"><span>Framework </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>Theme </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="darkmode" type="button" title="Toggle Between Light And Dark Mode"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="Toggle between Single-column and Double-column"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside-config" type="button" title="Setting"><i class="fas fa-cog fa-spin"></i></button><button id="go-up" type="button" title="Back To Top"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox/fancybox.umd.min.js"></script><div class="js-pjax"></div><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>