關(guān)鍵詞提取顧名思義就是將一個文檔中的內(nèi)容用幾個關(guān)鍵詞描述出來，這樣這幾個關(guān)鍵詞就可以提供這個文檔的大部分信息，從而提高信息獲取效率。 關(guān)鍵詞提取方法同樣分為有監(jiān)督和無監(jiān)督兩類，有監(jiān)督的方法比如構(gòu)造一個關(guān)鍵詞表，然后計算文檔和每個次的匹配程度用類似打標(biāo)簽的方法來進(jìn)行關(guān)鍵詞提取。這種方法的精度比較高，但
Read More
posted @ 2022-04-19 22:31
lleozhang
Views(2596)
Diggs(0)
背景與原理： BP神經(jīng)網(wǎng)絡(luò)通常指基于誤差反向傳播算法的多層神經(jīng)網(wǎng)絡(luò)，BP算法由信號的前向傳播和反向傳播兩個過程組成，在前向傳播的過程中，輸入從輸入層進(jìn)入網(wǎng)絡(luò)，經(jīng)過隱含層逐層傳遞到達(dá)輸出層輸出，如果輸出結(jié)果與預(yù)期不符那么轉(zhuǎn)至誤差反向傳播過程，否則結(jié)束學(xué)習(xí)過程。在反向傳播過程中，誤差會基于梯度下降原理分
Read More
posted @ 2022-04-05 22:51
lleozhang
Views(2150)
Diggs(0)
背景與原理： 樸素貝葉斯算法是機器學(xué)習(xí)領(lǐng)域最經(jīng)典的算法之一，仍然是用來解決分類問題的。 那么對于分類問題，我們的模型始終是：用$m$組數(shù)據(jù)，每條數(shù)據(jù)形如$(x_{1},...,x_{n},y)$，表示數(shù)據(jù)共有$n$個特征維度，而$y$表示該數(shù)據(jù)所屬的類別，不妨設(shè)有$k$個取值$C_{1},...,C
Read More
posted @ 2022-04-04 21:42
lleozhang
Views(421)
Diggs(0)
背景與原理： 首先我們需要知道集成學(xué)習(xí)的概念，所謂集成學(xué)習(xí)，就是使用一系列學(xué)習(xí)器進(jìn)行學(xué)習(xí)，并且通過某種規(guī)則把這些學(xué)習(xí)器的學(xué)習(xí)結(jié)果整合起來從而獲得比單個學(xué)習(xí)器學(xué)習(xí)效果更好的機器學(xué)習(xí)方法。這樣的方法可以用于解決單個學(xué)習(xí)器的過擬合、性能瓶頸等問題，常用的集成方式主要有Bagging（并行）和Boostin
Read More
posted @ 2022-04-04 20:09
lleozhang
Views(2654)
Diggs(0)
背景與原理： 決策樹算法是在各種已知情況發(fā)生概率的基礎(chǔ)上通過構(gòu)成決策樹來求某一事件發(fā)生概率的算法，由于這個過程畫成圖解之后很像一棵樹形結(jié)構(gòu)，因此我們把這個算法稱為決策樹。 而在機器學(xué)習(xí)中，決策樹是一種預(yù)測模型，代表對象屬性和對象值之間的一種映射，一棵決策樹的每個內(nèi)部節(jié)點會處理數(shù)據(jù)的某個維度對應(yīng)的變量
Read More
posted @ 2022-04-04 12:03
lleozhang
Views(596)
Diggs(0)
背景與原理： 支持向量機是一種用來解決分類問題的算法，其原理大致可理解為：對于所有$n$維的數(shù)據(jù)點，我們希望能夠找到一個$n$維的直線（平面，超平面），使得在這個超平面一側(cè)的點屬于同一類，另一側(cè)的點屬于另一類。而我們在尋找這個超平面的時候，我們只需要找到最接近劃分超平面的點，而一個$n$維空間中的點
Read More
posted @ 2022-03-31 23:05
lleozhang
Views(423)
Diggs(0)
背景與原理： 聚類問題與分類問題有一定的區(qū)別，分類問題是對每個訓(xùn)練數(shù)據(jù)，我給定了類別的標(biāo)簽，現(xiàn)在想要訓(xùn)練一個模型使得對于測試數(shù)據(jù)能輸出正確的類別標(biāo)簽，更多見于監(jiān)督學(xué)習(xí)；而聚類問題則是我們給出了一組數(shù)據(jù)，我們并沒有預(yù)先的標(biāo)簽，而是由機器考察這些數(shù)據(jù)之間的相似性，將相似的數(shù)據(jù)聚為一類，是無監(jiān)督學(xué)習(xí)的一個
Read More
posted @ 2022-03-31 14:09
lleozhang
Views(1339)
Diggs(0)
背景與原理： PCA（主成分分析）是將一個數(shù)據(jù)的特征數(shù)量減少的同時盡可能保留最多信息的方法。所謂降維，就是在說對于一個$n$維數(shù)據(jù)集，其可以看做一個$n$維空間中的點集（或者向量集），而我們要把這個向量集投影到一個$k<n$維空間中，這樣當(dāng)然會導(dǎo)致信息損失，但是如果這個$k$維空間的基底選取的足夠好
Read More
posted @ 2022-03-30 20:51
lleozhang
Views(2036)
Diggs(0)
背景與原理： KNN算法其實是邏輯最簡單的分類算法——我們認(rèn)為一個數(shù)據(jù)的類型是由與其最接近的數(shù)據(jù)決定的，而“接近”實際上就是我們度量兩個數(shù)據(jù)點之間的距離，如果我們把一組數(shù)據(jù)看做一個向量$(x_{1},...,x_{n},y)$，其中$y$代表這個數(shù)據(jù)的類別，那么兩組數(shù)據(jù)$X_{i},X_{j}$間的
Read More
posted @ 2022-03-28 19:56
lleozhang
Views(310)
Diggs(0)
背景與原理： 線性回歸可以實現(xiàn)對連續(xù)結(jié)果的預(yù)測，但是現(xiàn)實生活中我們常見的另一種問題是分類問題，尤其是二分類問題，在這種情況下使用線性回歸就不太合適了，我們實際上需要計算出的是一個在$[0,1]$之間的概率來告訴我們某樣本屬于某一類的概率，因此邏輯回歸應(yīng)運而生。 一般的邏輯回歸就是在線性回歸的基礎(chǔ)上嵌
Read More
posted @ 2022-03-27 16:50
lleozhang
Views(459)
Diggs(0)
背景與原理： 線性回歸是機器學(xué)習(xí)建模中最為簡單的模型，也是計算起來最為直觀的模型 所謂線性回歸，我們要建立的是這樣的模型：對一組數(shù)據(jù)，每組數(shù)據(jù)形如$(x_{1},...,x_{n},y)$，我們希望構(gòu)造一個線性函數(shù)$h_{\theta}(X)=\sum_{i=0}^{n}\theta_{i}x_{i
Read More
posted @ 2022-03-26 22:15
lleozhang
Views(442)
Diggs(0)
這類問題的基本模型是：你有$n$個小球，$m$個盒子，現(xiàn)在想把這$n$個小球放進(jìn)$m$個盒子中，問有多少種放的方法 但是只給出這樣的條件并不足夠，我們必須加上一些限制，否則結(jié)果是不確定的 一般加的有三個限制，即小球是否有區(qū)別、盒子是否有區(qū)別、允不允許有空盒子，也因此可以組合出八種不同的問題 接下來我
Read More
posted @ 2021-11-14 15:03
lleozhang
Views(652)
Diggs(0)
好久沒寫oi系列的題解了 要不是為了大作業(yè)我才不會回來學(xué)這些奇怪的東西呢 本題對抗搜索就好啦 首先要分析一點，就是由于我們的黑棋每次走兩步，白棋只走一步而且是白棋先走，所以除非白棋第一步吃掉黑棋，否則黑棋必勝 接下來就是計算黑棋如何取勝的問題了 首先簡單介紹一下對抗搜索 我們知道，兩個人下棋，兩個人
Read More
posted @ 2020-11-25 21:05
lleozhang
Views(183)
Diggs(0)
裴蜀定理： 內(nèi)容：若$gcd(a,b)=d$，則一定存在$m,n\in Z$，使$ma+nb=d$且$d$為$ma+nb$的最小正值（狹義） 證明： 令$d=gcd(a,b)$，則對任意$m,n\in Z$，有$d|am+bn$ 設(shè)$am+bn$的最小正值為$s$，則令$q=[\frac{a}{s}
Read More
posted @ 2020-07-14 21:04
lleozhang
Views(894)
Diggs(0)
本來早就打算寫退役記了，沒想到茍到了今天，也是不易了 (可能游記會咕，還是寫退役記吧qwq) 也是，作為一個菜的一批高二選手，NOI=退役 在這科競賽里，我見識到了極限的智慧 我見過了初二玩轉(zhuǎn)高數(shù)的神，見過了學(xué)了六年的魔，看到了南方一個省全是集訓(xùn)隊的高手，而你我，都只是普通人罷了。 我看到了我看不懂
Read More
posted @ 2019-07-19 15:23
lleozhang
Views(853)
Diggs(0)
1.最小生成樹： kruscal: 2.最短路： spfa（最好不要寫，他死了）... dijisktra（這個比較好） 3.LCA 倍增版本： 樹剖版本： 4.tarjan 有向圖tarjan縮點+spfa最長路 無向圖割邊： 無向圖割點： 5.網(wǎng)絡(luò)流 最大流： 費用流： 有源匯上下界最大流 有源
Read More
posted @ 2019-07-12 15:56
lleozhang
Views(478)
Diggs(0)
LCT神題... 首先暴力的做法就是每次在一個區(qū)間上link，然后暴力查詢，時間復(fù)雜度$O(爆炸)$ 但是我們可以發(fā)現(xiàn)的是，每棵樹之間互不影響！ 因此我們可以考慮離線之后分別統(tǒng)計每棵樹 但是這樣做其實并沒有優(yōu)化時空啊！ 但是等等，我們在考慮一下：我們的操作都是區(qū)間操作，也就是說我們可以用一個類似差分
Read More
posted @ 2019-07-12 10:54
lleozhang
Views(311)
Diggs(0)
并查集水題 離散化之后直接并查集合并，在不等時判斷兩者是否在同一個集合內(nèi)即可 注意排序 貼代碼：
Read More
posted @ 2019-07-12 09:26
lleozhang
Views(273)
Diggs(0)
線性基好題 首先，如果一條路徑被經(jīng)過了兩次，那么這條路徑上的權(quán)值等于沒有（廢話） 基于這一點，我們其實已經(jīng)找到了解決問題的方法了！ 首先，由于可以反復(fù)經(jīng)過一條邊，因此我們可以把一條合法的路徑看成這樣的結(jié)構(gòu)： 從$1$到$n$有一條鏈，這條鏈上掛著一些環(huán)，答案是鏈的貢獻(xiàn)異或環(huán)的貢獻(xiàn)（因為從鏈到環(huán)的邊一
Read More
posted @ 2019-07-12 09:07
lleozhang
Views(245)
Diggs(0)
有人說這題像游走... 關(guān)于游走的思想，他死了... 明明直接從期望dp的角度考慮更簡單合理嘛 首先由于是異或運算不妨逐位考慮 對于每一位，設(shè)狀態(tài)$f[i]$表示從第$i$個點到第$n$個點，這一位上是$1$的概率 那么我們按邊權(quán)討論轉(zhuǎn)移： 若這條邊邊權(quán)為$1$：$f[i]+=\frac{1-f[t
Read More
posted @ 2019-07-11 17:18
lleozhang
Views(271)
Diggs(0)
考慮轉(zhuǎn)化問題：一個點相鄰元素中有偶數(shù)個$1$等價于一個點與相鄰元素異或和為$0$ 于是直接列出異或方程組求解即可 注意由于要求不允許出現(xiàn)全0矩陣，因此如果有自由元直接給成$1$ 貼代碼：
Read More
posted @ 2019-07-11 15:45
lleozhang
Views(314)
Diggs(0)
很好的一道題，對理解最小割有很大幫助 首先，不難發(fā)現(xiàn)本題與網(wǎng)絡(luò)流24題中的某一道很類似，我們可以先跑一次dp求出每個節(jié)點的LIS，然后拆點，拆出的兩點之間連流量為刪除的代價的邊，剩下的點之間按dp的轉(zhuǎn)移連流量正無窮的邊，最后跑最小割即為第一問答案 但是第二問有個問題：又引入了一個量要求最小割字典序最
Read More
posted @ 2019-07-11 15:09
lleozhang
Views(222)
Diggs(0)
這題并不是太難 首先題目我們將每個城市拆點，由源點向一端連容量為初始人數(shù)的邊，由另一端向匯點連容量為最后人數(shù)的邊，然后按照題目要求從一端向另一端連容量無窮大的邊 這樣跑出最大流之后我們只需比較這個流量與總?cè)藬?shù)是否相等就知道是否合法了 至于輸出方案，一個點向另一個點的所有流量都會體現(xiàn)在反向邊上，因此我
Read More
posted @ 2019-07-11 11:29
lleozhang
Views(305)
Diggs(0)
費用流好題 本題的建圖很有意思 正常我們看到棋盤問題應(yīng)該先對整個棋盤黑白染色構(gòu)成一個二分圖，然后再考慮建圖的問題 但是本題題目中已經(jīng)明確區(qū)分了不同的斜線，問題在于怎么保證一個"L"形 因此我們進(jìn)一步分析：顯然柱子應(yīng)該放在有代價的位置，我們應(yīng)該由這樣的位置向上下左右連邊，保證有兩個就行 但是這樣建圖是
Read More
posted @ 2019-07-11 10:51
lleozhang
Views(213)
Diggs(0)
首先題意就是裸的最小割啦 然后考慮如何統(tǒng)計邊數(shù) 這里有一個trick： 我們設(shè)定一個大于$m$的閾值，對于每條邊的邊權(quán)我們乘這個閾值+1后跑最小割，得到的答案除以閾值就是真正的最小割，取模閾值后就是最少割掉的邊數(shù) 為什么？ 我們考慮：設(shè)原來的最小割割掉的邊權(quán)為$v_{1},v_{2}...v_{n}
Read More
posted @ 2019-07-11 09:03
lleozhang
Views(152)
Diggs(0)
思想基本同bzoj 2594，但是多了一步 首先我們發(fā)現(xiàn)這時的邊有兩個屬性了，因此我們考慮先去掉其中一者的限制 我們把所有邊按$a$大小排序，然后從小到大加入維護(hù)的最小生成樹 每次加邊時都按照$b$的大小操作bzoj 2594，然后更新答案即可 如果始終不聯(lián)通輸出-1
Read More
posted @ 2019-07-10 16:15
lleozhang
Views(232)
Diggs(0)
很好的一道LCT題目 首先我們可以發(fā)現(xiàn)，題目要求的就是最小生成樹上的一條樹鏈的最長邊的長度，因此我們實際只需動態(tài)維護(hù)最小生成樹即可 然后我們考慮怎么動態(tài)維護(hù)最小生成樹 不難發(fā)現(xiàn)，如果涉及在最小生成樹上刪邊，那么這個操作將變得非常復(fù)雜，因為我們并不知道刪邊之后要把什么樣的邊補充回去才行 但是，如果我們
Read More
posted @ 2019-07-10 16:12
lleozhang
Views(174)
Diggs(0)
LCT好題 首先我們考慮實際詢問的是什么： 從LCT的角度考慮，如果我們認(rèn)為一開始樹上每一條邊都是虛邊，把一次涂色看作一次access操作，那么詢問的實際就是兩個節(jié)點間的虛邊數(shù)量+1和子樹中的最大虛邊數(shù)量！ 這種問題顯然樹上容斥，如果設(shè)$dis_{i}$表示$i$到根節(jié)點需要經(jīng)過多少虛邊，那么答案顯
Read More
posted @ 2019-07-10 12:43
lleozhang
Views(187)
Diggs(0)
LCT板子題... 看到題目中的操作很顯然是從$i$向$i+k_{i}$連一條邊，每次修改就是刪除原來的邊再加入一條新的邊嘛 然后考慮查詢：對于被彈飛的部分，我們統(tǒng)一新建一個節(jié)點$n+1$，把所有越過邊界的部分指向這個節(jié)點即可 然后在查詢的時候只需要拎出查詢節(jié)點到$n+1$節(jié)點的樹鏈，統(tǒng)計其大小即可
Read More
posted @ 2019-07-10 10:55
lleozhang
Views(203)
Diggs(0)
真·小清新... 其實本題正解是動態(tài)點分治，但是考慮到那個東西需要先大力推導(dǎo)一波再套上一個幻想鄉(xiāng)戰(zhàn)略游戲的搞法，所以還不如大力推導(dǎo)一波，然后無腦套上一個樹剖+線段樹寫法... 首先我們考慮沒有換根操作： 沒有換根操作時，設(shè)每次修改的變化量為$\delta$，很顯然每次修改時只會影響一條樹鏈上的貢獻(xiàn)，
Read More
posted @ 2019-07-10 08:57
lleozhang
Views(168)
Diggs(0)
動態(tài)點分治好題 首先我們考慮一個暴力做法： 每次修改之后選一個點作為根搜索整棵樹，然后換根dp即可 考慮每次換根時，移向的點的消耗會減少子樹代價之和*邊權(quán)，而其余部分代價會增加剩余代價*邊權(quán) 這樣每次換根都是$O(1)$的，總時間復(fù)雜度$O(nm)$，可以通過...20分！ 貼代碼： 然后我們考慮正
Read More
posted @ 2019-07-09 20:48
lleozhang
Views(203)
Diggs(0)
首先仍然是點對之間的問題，讓我們考慮點分 由于帶修改，所以考慮動態(tài)點分治 所謂動態(tài)點分治，就是在操作之前先模擬一遍點分治的過程構(gòu)造出一棵新的樹，我們稱這棵樹為點分樹，由于這棵樹樹高是對數(shù)級別的，所以修改的時候可以在一條樹鏈上暴力修改 然后考慮本題怎么維護(hù)： 首先我們考慮答案如何統(tǒng)計：在統(tǒng)計答案時，我
Read More
posted @ 2019-07-09 19:23
lleozhang
Views(222)
Diggs(0)
點分治好題 統(tǒng)計距離正常點分治統(tǒng)計即可，我們只需考慮何時達(dá)到最優(yōu) 有兩種情況： 第一：代價最大的詢問兩個端點在不同的兩個子樹中 因為這種情況下，無論根向那個子樹移動都會等價地增加到達(dá)另一個端點的代價，因此此時總代價已經(jīng)達(dá)到最小 第二：代價最大的詢問有多組，且這些點不在同一棵子樹中 同情況一，如果我們
Read More
posted @ 2019-07-08 21:39
lleozhang
Views(203)
Diggs(0)
太久沒碰點分治的我看見這題已經(jīng)失了智... 首先這種統(tǒng)計肯定要想一想點分，當(dāng)然也有樹形dp的做法，不過還是用點分吧... 我們每次找到一個根，然后統(tǒng)計以這個根為中心，模3為0，1,2的路徑數(shù)量（這一點可以直接搜索），然后做個卷積統(tǒng)計一下即可 但是可能會出現(xiàn)重復(fù)的情況，重復(fù)來源于這種時候： 如圖所示，
Read More
posted @ 2019-07-08 19:55
lleozhang
Views(172)
Diggs(0)
首先我們考慮$n$的情況，顯然以$n$為分界線可以將整個序列分成兩部分，就像這樣： 、 那么我們考慮：在這個東西前面才會有前綴最大的統(tǒng)計，在這個東西后面才會有后綴最大的統(tǒng)計 這樣就剩下了$n-1$個元素，而我們需要把這$n-1$個元素分成$A+B-2$個集合，然后把每個集合的最大的一個放在一端，然后
Read More
posted @ 2019-07-08 18:46
lleozhang
Views(187)
Diggs(0)
題意：求$\sum_{i=1}^{n}\sum_{j=1}^{n}lcm(i,j)^{gcd(i,j)}$ 神仙題... 首先可能會想到一個轉(zhuǎn)化，就是$lcm(i,j)=\frac{ij}{gcd(i,j)}$ 然后大力往下推式子，發(fā)現(xiàn)你推不下去了... 因為$d$在分母上！！！ 然后我們考慮換一種
Read More
posted @ 2019-07-08 14:37
lleozhang
Views(201)
Diggs(0)
題意：求$\sum_{i=1}^{n}\sum_{j=1}^{n}d(ij)$ 首先推一發(fā)式子： $\sum_{i=1}^{n}\sum_{j=1}^{n}d(ij)$ 有一個結(jié)論：$d(nm)=\sum_{i|n}\sum_{j|m}[gcd(i,j)\equiv 1]$ 然后代入，得： $\su
Read More
posted @ 2019-07-08 11:54
lleozhang
Views(285)
Diggs(0)
莫比烏斯反演 還是推式子： 設(shè)$f(n)=n^{k}$ 那就是上一道題了 推的過程如下： $\sum_{i=1}^{a}\sum_{j=1}^{b}f(gcd(i,j))$ $\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{d=1}^{min(a,b)}[gcd(i,j)\equ
Read More
posted @ 2019-07-08 11:04
lleozhang
Views(236)
Diggs(0)
奇怪的莫比烏斯反演... 題意：定義$f(n)$表示將$n$質(zhì)因數(shù)分解后質(zhì)因子的最高冪次，求$\sum_{i=1}^{a}\sum_{j=1}^{b}f(gcd(i,j))$ 首先肯定是反演嘛... 推一發(fā)式子： $\sum_{i=1}^{a}\sum_{j=1}^{b}f(gcd(i,j))$ $
Read More
posted @ 2019-07-08 10:22
lleozhang
Views(241)
Diggs(0)
emmmm... 做這題之前強烈推薦先去寫一下壓位高精度加法，壓十八位就行... 然后有一個東西叫序列自動機，其實就是一個指針，用$n*|字符集|$的時空找到每個字符的下一次出現(xiàn)位置 然后如果想找到兩個字符串的所有公共子序列只需要在序列自動機上dfs即可 重點看代碼：
Read More
posted @ 2019-07-08 07:48
lleozhang
Views(166)
Diggs(0)
浙公網(wǎng)安備 33010602011771號