index.html 67 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367
  1. <!DOCTYPE html>
  2. <html lang="en">
  3. <head>
  4. <meta charset="UTF-8">
  5. <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
  6. <meta name="theme-color" content="#222">
  7. <meta name="generator" content="Hexo 4.2.0">
  8. <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  9. <link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
  10. <link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
  11. <link rel="mask-icon" href="/images/logo.svg" color="#222">
  12. <link rel="stylesheet" href="/css/main.css">
  13. <link rel="stylesheet" href="/lib/font-awesome/css/font-awesome.min.css">
  14. <link rel="stylesheet" href="/lib/pace/pace-theme-minimal.min.css">
  15. <script src="/lib/pace/pace.min.js"></script>
  16. <script id="hexo-configurations">
  17. var NexT = window.NexT || {};
  18. var CONFIG = {"hostname":"schtonn.github.io","root":"/","scheme":"Muse","version":"7.7.2","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":true,"style":"flat"},"back2top":{"enable":true,"sidebar":false,"scrollpercent":true},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":true,"pangu":false,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":false,"nav":null,"activeClass":"valine"},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":false,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideLeftIn"}}};
  19. </script>
  20. <meta name="description" content="The blog of a middle school OIer">
  21. <meta property="og:type" content="website">
  22. <meta property="og:title" content="Alex&#39;s Blog">
  23. <meta property="og:url" content="https://schtonn.github.io/index.html">
  24. <meta property="og:site_name" content="Alex&#39;s Blog">
  25. <meta property="og:description" content="The blog of a middle school OIer">
  26. <meta property="og:locale" content="en_US">
  27. <meta property="article:author" content="Alex">
  28. <meta name="twitter:card" content="summary">
  29. <link rel="canonical" href="https://schtonn.github.io/">
  30. <script id="page-configurations">
  31. // https://hexo.io/docs/variables.html
  32. CONFIG.page = {
  33. sidebar: "",
  34. isHome : true,
  35. isPost : false
  36. };
  37. </script>
  38. <title>Alex's Blog</title>
  39. <noscript>
  40. <style>
  41. .use-motion .brand,
  42. .use-motion .menu-item,
  43. .sidebar-inner,
  44. .use-motion .post-block,
  45. .use-motion .pagination,
  46. .use-motion .comments,
  47. .use-motion .post-header,
  48. .use-motion .post-body,
  49. .use-motion .collection-header { opacity: initial; }
  50. .use-motion .site-title,
  51. .use-motion .site-subtitle {
  52. opacity: initial;
  53. top: initial;
  54. }
  55. .use-motion .logo-line-before i { left: initial; }
  56. .use-motion .logo-line-after i { right: initial; }
  57. </style>
  58. </noscript>
  59. </head>
  60. <body itemscope itemtype="http://schema.org/WebPage">
  61. <div class="container use-motion">
  62. <div class="headband"></div>
  63. <header class="header" itemscope itemtype="http://schema.org/WPHeader">
  64. <div class="header-inner"><div class="site-brand-container">
  65. <div class="site-nav-toggle">
  66. <div class="toggle" aria-label="Toggle navigation bar">
  67. <span class="toggle-line toggle-line-first"></span>
  68. <span class="toggle-line toggle-line-middle"></span>
  69. <span class="toggle-line toggle-line-last"></span>
  70. </div>
  71. </div>
  72. <div class="site-meta">
  73. <div>
  74. <a href="/" class="brand" rel="start">
  75. <span class="logo-line-before"><i></i></span>
  76. <span class="site-title">Alex's Blog</span>
  77. <span class="logo-line-after"><i></i></span>
  78. </a>
  79. </div>
  80. <p class="site-subtitle">Middle school OIer</p>
  81. </div>
  82. <div class="site-nav-right">
  83. <div class="toggle popup-trigger">
  84. </div>
  85. </div>
  86. </div>
  87. <nav class="site-nav">
  88. <ul id="menu" class="menu">
  89. <li class="menu-item menu-item-home">
  90. <a href="/" rel="section"><i class="fa fa-fw fa-home"></i>Home</a>
  91. </li>
  92. <li class="menu-item menu-item-tags">
  93. <a href="/tags/" rel="section"><i class="fa fa-fw fa-tags"></i>Tags</a>
  94. </li>
  95. <li class="menu-item menu-item-archives">
  96. <a href="/archives/" rel="section"><i class="fa fa-fw fa-archive"></i>Archives</a>
  97. </li>
  98. <li class="menu-item menu-item-games">
  99. <a href="/games/" rel="section"><i class="fa fa-fw fa-gamepad"></i>Games</a>
  100. </li>
  101. <li class="menu-item menu-item-sans">
  102. <a href="/sans/" rel="section"><i class="fa fa-fw fa-heart"></i>sans</a>
  103. </li>
  104. </ul>
  105. </nav>
  106. </div>
  107. </header>
  108. <div class="back-to-top">
  109. <i class="fa fa-arrow-up"></i>
  110. <span>0%</span>
  111. </div>
  112. <div class="reading-progress-bar"></div>
  113. <main class="main">
  114. <div class="main-inner">
  115. <div class="content-wrap">
  116. <div class="content">
  117. <div class="posts-expand">
  118. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  119. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/plan/">
  120. <script>
  121. (function(){
  122. if(''){
  123. if (prompt('Password?') !== ''){
  124. alert('GOAWAY!');
  125. history.back();
  126. }
  127. }
  128. })();
  129. </script>
  130. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  131. <meta itemprop="image" content="/images/avatar.gif">
  132. <meta itemprop="name" content="Alex">
  133. <meta itemprop="description" content="The blog of a middle school OIer">
  134. </span>
  135. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  136. <meta itemprop="name" content="Alex's Blog">
  137. </span>
  138. <header class="post-header">
  139. <h1 class="post-title" itemprop="name headline">
  140. <a href="/posts/plan/" class="post-title-link" itemprop="url">plan</a>
  141. </h1>
  142. <div class="post-meta">
  143. <i class="fa fa-thumb-tack"></i>
  144. <font color=7D26CD>Pinned</font>
  145. <span class="post-meta-divider">|</span>
  146. <span class="post-meta-item">
  147. <span class="post-meta-item-icon">
  148. <i class="fa fa-calendar-o"></i>
  149. </span>
  150. <span class="post-meta-item-text">Posted on</span>
  151. <time title="Created: 2020-Mar-01 22:36:07" itemprop="dateCreated datePublished" datetime="2020-03-01T22:36:07+08:00">2020-Mar-01</time>
  152. </span>
  153. <span class="post-meta-item">
  154. <span class="post-meta-item-icon">
  155. <i class="fa fa-calendar-check-o"></i>
  156. </span>
  157. <span class="post-meta-item-text">Edited on</span>
  158. <time title="Modified: 2020-Mar-29 15:59:42" itemprop="dateModified" datetime="2020-03-29T15:59:42+08:00">2020-Mar-29</time>
  159. </span>
  160. <span id="/posts/plan/" class="post-meta-item leancloud_visitors" data-flag-title="plan" title="Views">
  161. <span class="post-meta-item-icon">
  162. <i class="fa fa-eye"></i>
  163. </span>
  164. <span class="post-meta-item-text">Views: </span>
  165. <span class="leancloud-visitors-count"></span>
  166. </span>
  167. </div>
  168. </header>
  169. <div class="post-body" itemprop="articleBody">
  170. <p>This page is locked.</p>
  171. <!--noindex-->
  172. <div class="post-button">
  173. <a class="btn" href="/posts/plan/#more" rel="contents">
  174. Read more &raquo;
  175. </a>
  176. </div>
  177. <!--/noindex-->
  178. </div>
  179. <footer class="post-footer">
  180. <div class="post-eof"></div>
  181. </footer>
  182. </article>
  183. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  184. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/matrix-pow/">
  185. <script>
  186. (function(){
  187. if(''){
  188. if (prompt('Password?') !== ''){
  189. alert('GOAWAY!');
  190. history.back();
  191. }
  192. }
  193. })();
  194. </script>
  195. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  196. <meta itemprop="image" content="/images/avatar.gif">
  197. <meta itemprop="name" content="Alex">
  198. <meta itemprop="description" content="The blog of a middle school OIer">
  199. </span>
  200. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  201. <meta itemprop="name" content="Alex's Blog">
  202. </span>
  203. <header class="post-header">
  204. <h1 class="post-title" itemprop="name headline">
  205. <a href="/posts/matrix-pow/" class="post-title-link" itemprop="url">矩阵快速幂运用</a>
  206. </h1>
  207. <div class="post-meta">
  208. <span class="post-meta-item">
  209. <span class="post-meta-item-icon">
  210. <i class="fa fa-calendar-o"></i>
  211. </span>
  212. <span class="post-meta-item-text">Posted on</span>
  213. <time title="Created: 2020-Mar-21 19:20:08" itemprop="dateCreated datePublished" datetime="2020-03-21T19:20:08+08:00">2020-Mar-21</time>
  214. </span>
  215. <span class="post-meta-item">
  216. <span class="post-meta-item-icon">
  217. <i class="fa fa-calendar-check-o"></i>
  218. </span>
  219. <span class="post-meta-item-text">Edited on</span>
  220. <time title="Modified: 2020-Mar-29 15:59:04" itemprop="dateModified" datetime="2020-03-29T15:59:04+08:00">2020-Mar-29</time>
  221. </span>
  222. <span id="/posts/matrix-pow/" class="post-meta-item leancloud_visitors" data-flag-title="矩阵快速幂运用" title="Views">
  223. <span class="post-meta-item-icon">
  224. <i class="fa fa-eye"></i>
  225. </span>
  226. <span class="post-meta-item-text">Views: </span>
  227. <span class="leancloud-visitors-count"></span>
  228. </span>
  229. </div>
  230. </header>
  231. <div class="post-body" itemprop="articleBody">
  232. <h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
  233. <p>想要了解矩阵快速幂,就不得不提到矩阵的概念。矩阵就像一个二维数组,存储了一组数据,如:</p>
  234. <p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>M</mi><mo>=</mo><mrow><mo fence="true">[</mo><mtable rowspacing="0.15999999999999992em" columnspacing="1em"><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>1</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>2</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>3</mn></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>4</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>5</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>6</mn></mstyle></mtd></mtr><mtr><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>7</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>8</mn></mstyle></mtd><mtd><mstyle scriptlevel="0" displaystyle="false"><mn>9</mn></mstyle></mtd></mtr></mtable><mo fence="true">]</mo></mrow></mrow><annotation encoding="application/x-tex">M=\left[
  235. \begin{matrix}
  236. 1&amp;2&amp;3\\
  237. 4&amp;5&amp;6\\
  238. 7&amp;8&amp;9\end{matrix}
  239. \right]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.68333em;vertical-align:0em;"></span><span class="mord mathdefault" style="margin-right:0.10903em;">M</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:3.60004em;vertical-align:-1.55002em;"></span><span class="minner"><span class="mopen"><span class="delimsizing mult"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05002em;"><span style="top:-2.2500000000000004em;"><span class="pstrut" style="height:3.1550000000000002em;"></span><span class="delimsizinginner delim-size4"><span>⎣</span></span></span><span style="top:-4.05002em;"><span class="pstrut" style="height:3.1550000000000002em;"></span><span class="delimsizinginner delim-size4"><span>⎡</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:1.55002em;"><span></span></span></span></span></span></span><span class="mord"><span class="mtable"><span class="col-align-c"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05em;"><span style="top:-4.21em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">1</span></span></span><span style="top:-3.0099999999999993em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">4</span></span></span><span style="top:-1.8099999999999994em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">7</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:1.5500000000000007em;"><span></span></span></span></span></span><span class="arraycolsep" style="width:0.5em;"></span><span class="arraycolsep" style="width:0.5em;"></span><span class="col-align-c"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05em;"><span style="top:-4.21em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">2</span></span></span><span style="top:-3.0099999999999993em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">5</span></span></span><span style="top:-1.8099999999999994em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">8</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:1.5500000000000007em;"><span></span></span></span></span></span><span class="arraycolsep" style="width:0.5em;"></span><span class="arraycolsep" style="width:0.5em;"></span><span class="col-align-c"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05em;"><span style="top:-4.21em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">3</span></span></span><span style="top:-3.0099999999999993em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">6</span></span></span><span style="top:-1.8099999999999994em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">9</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:1.5500000000000007em;"><span></span></span></span></span></span></span></span><span class="mclose"><span class="delimsizing mult"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:2.05002em;"><span style="top:-2.2500000000000004em;"><span class="pstrut" style="height:3.1550000000000002em;"></span><span class="delimsizinginner delim-size4"><span>⎦</span></span></span><span style="top:-4.05002em;"><span class="pstrut" style="height:3.1550000000000002em;"></span><span class="delimsizinginner delim-size4"><span>⎤</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:1.55002em;"><span></span></span></span></span></span></span></span></span></span></span></span></p>
  240. <p>用 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>M</mi><mrow><mi>i</mi><mo separator="true">,</mo><mi>j</mi></mrow></msub></mrow><annotation encoding="application/x-tex">M_{i,j}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.10903em;">M</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.311664em;"><span style="top:-2.5500000000000003em;margin-left:-0.10903em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathdefault mtight">i</span><span class="mpunct mtight">,</span><span class="mord mathdefault mtight" style="margin-right:0.05724em;">j</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span></span></span></span> 表示矩阵第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>i</mi></mrow><annotation encoding="application/x-tex">i</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.65952em;vertical-align:0em;"></span><span class="mord mathdefault">i</span></span></span></span> 行第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>j</mi></mrow><annotation encoding="application/x-tex">j</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.85396em;vertical-align:-0.19444em;"></span><span class="mord mathdefault" style="margin-right:0.05724em;">j</span></span></span></span> 列的数据,如 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>M</mi><mrow><mn>2</mn><mo separator="true">,</mo><mn>3</mn></mrow></msub><mo>=</mo><mn>6</mn></mrow><annotation encoding="application/x-tex">M_{2,3}=6</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.969438em;vertical-align:-0.286108em;"></span><span class="mord"><span class="mord mathdefault" style="margin-right:0.10903em;">M</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.301108em;"><span style="top:-2.5500000000000003em;margin-left:-0.10903em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mtight">2</span><span class="mpunct mtight">,</span><span class="mord mtight">3</span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.286108em;"><span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">6</span></span></span></span>。</p>
  241. <!--noindex-->
  242. <div class="post-button">
  243. <a class="btn" href="/posts/matrix-pow/#more" rel="contents">
  244. Read more &raquo;
  245. </a>
  246. </div>
  247. <!--/noindex-->
  248. </div>
  249. <footer class="post-footer">
  250. <div class="post-eof"></div>
  251. </footer>
  252. </article>
  253. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  254. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/computer/">
  255. <script>
  256. (function(){
  257. if(''){
  258. if (prompt('Password?') !== ''){
  259. alert('GOAWAY!');
  260. history.back();
  261. }
  262. }
  263. })();
  264. </script>
  265. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  266. <meta itemprop="image" content="/images/avatar.gif">
  267. <meta itemprop="name" content="Alex">
  268. <meta itemprop="description" content="The blog of a middle school OIer">
  269. </span>
  270. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  271. <meta itemprop="name" content="Alex's Blog">
  272. </span>
  273. <header class="post-header">
  274. <h1 class="post-title" itemprop="name headline">
  275. <a href="/posts/computer/" class="post-title-link" itemprop="url">How do computers work?</a>
  276. </h1>
  277. <div class="post-meta">
  278. <span class="post-meta-item">
  279. <span class="post-meta-item-icon">
  280. <i class="fa fa-calendar-o"></i>
  281. </span>
  282. <span class="post-meta-item-text">Posted on</span>
  283. <time title="Created: 2020-Mar-04 12:53:05" itemprop="dateCreated datePublished" datetime="2020-03-04T12:53:05+08:00">2020-Mar-04</time>
  284. </span>
  285. <span class="post-meta-item">
  286. <span class="post-meta-item-icon">
  287. <i class="fa fa-calendar-check-o"></i>
  288. </span>
  289. <span class="post-meta-item-text">Edited on</span>
  290. <time title="Modified: 2020-Mar-29 15:59:23" itemprop="dateModified" datetime="2020-03-29T15:59:23+08:00">2020-Mar-29</time>
  291. </span>
  292. <span id="/posts/computer/" class="post-meta-item leancloud_visitors" data-flag-title="How do computers work?" title="Views">
  293. <span class="post-meta-item-icon">
  294. <i class="fa fa-eye"></i>
  295. </span>
  296. <span class="post-meta-item-text">Views: </span>
  297. <span class="leancloud-visitors-count"></span>
  298. </span>
  299. </div>
  300. </header>
  301. <div class="post-body" itemprop="articleBody">
  302. <p>This page is locked</p>
  303. <!--noindex-->
  304. <div class="post-button">
  305. <a class="btn" href="/posts/computer/#more" rel="contents">
  306. Read more &raquo;
  307. </a>
  308. </div>
  309. <!--/noindex-->
  310. </div>
  311. <footer class="post-footer">
  312. <div class="post-eof"></div>
  313. </footer>
  314. </article>
  315. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  316. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/segment-tree/">
  317. <script>
  318. (function(){
  319. if(''){
  320. if (prompt('Password?') !== ''){
  321. alert('GOAWAY!');
  322. history.back();
  323. }
  324. }
  325. })();
  326. </script>
  327. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  328. <meta itemprop="image" content="/images/avatar.gif">
  329. <meta itemprop="name" content="Alex">
  330. <meta itemprop="description" content="The blog of a middle school OIer">
  331. </span>
  332. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  333. <meta itemprop="name" content="Alex's Blog">
  334. </span>
  335. <header class="post-header">
  336. <h1 class="post-title" itemprop="name headline">
  337. <a href="/posts/segment-tree/" class="post-title-link" itemprop="url">线段树</a>
  338. </h1>
  339. <div class="post-meta">
  340. <span class="post-meta-item">
  341. <span class="post-meta-item-icon">
  342. <i class="fa fa-calendar-o"></i>
  343. </span>
  344. <span class="post-meta-item-text">Posted on</span>
  345. <time title="Created: 2020-Mar-02 11:37:36" itemprop="dateCreated datePublished" datetime="2020-03-02T11:37:36+08:00">2020-Mar-02</time>
  346. </span>
  347. <span class="post-meta-item">
  348. <span class="post-meta-item-icon">
  349. <i class="fa fa-calendar-check-o"></i>
  350. </span>
  351. <span class="post-meta-item-text">Edited on</span>
  352. <time title="Modified: 2020-Mar-29 15:59:45" itemprop="dateModified" datetime="2020-03-29T15:59:45+08:00">2020-Mar-29</time>
  353. </span>
  354. <span id="/posts/segment-tree/" class="post-meta-item leancloud_visitors" data-flag-title="线段树" title="Views">
  355. <span class="post-meta-item-icon">
  356. <i class="fa fa-eye"></i>
  357. </span>
  358. <span class="post-meta-item-text">Views: </span>
  359. <span class="leancloud-visitors-count"></span>
  360. </span>
  361. </div>
  362. </header>
  363. <div class="post-body" itemprop="articleBody">
  364. <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
  365. <p>数组,结构体,二叉树</p>
  366. <h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
  367. <p>有时候我们会遇到一些大规模的区间查找和区间修改问题,比如让你维护一个 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span> 长度的数列,要求操作有区间求和、区间加(区间每个数加上一个值),让你在一秒内完成 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><msup><mn>0</mn><mn>5</mn></msup></mrow><annotation encoding="application/x-tex">10^5</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8141079999999999em;"><span style="top:-3.063em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight">5</span></span></span></span></span></span></span></span></span></span></span> 次操作。<br />
  368. 暴力是肯定不行的,数据范围太大,操作太多,会超时。<br />
  369. 所以我们就有一种专门解决大范围区间修改查询的数据结构:线段树。</p>
  370. <!--noindex-->
  371. <div class="post-button">
  372. <a class="btn" href="/posts/segment-tree/#more" rel="contents">
  373. Read more &raquo;
  374. </a>
  375. </div>
  376. <!--/noindex-->
  377. </div>
  378. <footer class="post-footer">
  379. <div class="post-eof"></div>
  380. </footer>
  381. </article>
  382. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  383. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/ferbonacci/">
  384. <script>
  385. (function(){
  386. if(''){
  387. if (prompt('Password?') !== ''){
  388. alert('GOAWAY!');
  389. history.back();
  390. }
  391. }
  392. })();
  393. </script>
  394. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  395. <meta itemprop="image" content="/images/avatar.gif">
  396. <meta itemprop="name" content="Alex">
  397. <meta itemprop="description" content="The blog of a middle school OIer">
  398. </span>
  399. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  400. <meta itemprop="name" content="Alex's Blog">
  401. </span>
  402. <header class="post-header">
  403. <h1 class="post-title" itemprop="name headline">
  404. <a href="/posts/ferbonacci/" class="post-title-link" itemprop="url">斐波那契数列-O(1)</a>
  405. </h1>
  406. <div class="post-meta">
  407. <span class="post-meta-item">
  408. <span class="post-meta-item-icon">
  409. <i class="fa fa-calendar-o"></i>
  410. </span>
  411. <span class="post-meta-item-text">Posted on</span>
  412. <time title="Created: 2020-Mar-02 11:35:44" itemprop="dateCreated datePublished" datetime="2020-03-02T11:35:44+08:00">2020-Mar-02</time>
  413. </span>
  414. <span class="post-meta-item">
  415. <span class="post-meta-item-icon">
  416. <i class="fa fa-calendar-check-o"></i>
  417. </span>
  418. <span class="post-meta-item-text">Edited on</span>
  419. <time title="Modified: 2020-Mar-29 15:59:30" itemprop="dateModified" datetime="2020-03-29T15:59:30+08:00">2020-Mar-29</time>
  420. </span>
  421. <span id="/posts/ferbonacci/" class="post-meta-item leancloud_visitors" data-flag-title="斐波那契数列-O(1)" title="Views">
  422. <span class="post-meta-item-icon">
  423. <i class="fa fa-eye"></i>
  424. </span>
  425. <span class="post-meta-item-text">Views: </span>
  426. <span class="leancloud-visitors-count"></span>
  427. </span>
  428. </div>
  429. </header>
  430. <div class="post-body" itemprop="articleBody">
  431. <p>引自:《信息学奥赛之-数学一本通》<br />
  432. 揍是这样:</p>
  433. <p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">F</mi><mo>⁡</mo><mo stretchy="false">(</mo><mi>n</mi><mo stretchy="false">)</mo><mo>=</mo><mfrac><msqrt><mn>5</mn></msqrt><mn>5</mn></mfrac><mo>⋅</mo><mrow><mo fence="true">[</mo><msup><mrow><mo fence="true">(</mo><mn>1</mn><mo>+</mo><msqrt><mn>5</mn></msqrt><mo fence="true">)</mo></mrow><mi>n</mi></msup><mo>−</mo><msup><mrow><mo fence="true">(</mo><mn>1</mn><mo>−</mo><msqrt><mn>5</mn></msqrt><mo fence="true">)</mo></mrow><mi>n</mi></msup><mo fence="true">]</mo></mrow></mrow><annotation encoding="application/x-tex">\operatorname{F}(n)=\dfrac{\sqrt{5}}{5}\cdot\left[\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n\right]
  434. </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mop"><span class="mord mathrm">F</span></span><span class="mopen">(</span><span class="mord mathdefault">n</span><span class="mclose">)</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span><span class="mrel">=</span><span class="mspace" style="margin-right:0.2777777777777778em;"></span></span><span class="base"><span class="strut" style="height:2.27022em;vertical-align:-0.686em;"></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.5842200000000002em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord">5</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.90722em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord">5</span></span></span><span style="top:-2.86722em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,
  435. -10,-9.5,-14c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54c44.2,-33.3,65.8,
  436. -50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10s173,378,173,378c0.7,0,
  437. 35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429c69,-144,104.5,-217.7,106.5,
  438. -221c5.3,-9.3,12,-14,20,-14H400000v40H845.2724s-225.272,467,-225.272,467
  439. s-235,486,-235,486c-2.7,4.7,-9,7,-19,7c-6,0,-10,-1,-12,-3s-194,-422,-194,-422
  440. s-65,47,-65,47z M834 80H400000v40H845z'/></svg></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.13278em;"><span></span></span></span></span></span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">⋅</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:1.854312em;vertical-align:-0.65002em;"></span><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size2">[</span></span><span class="minner"><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size2">(</span></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.956095em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord">5</span></span></span><span style="top:-2.916095em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,
  441. -10,-9.5,-14c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54c44.2,-33.3,65.8,
  442. -50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10s173,378,173,378c0.7,0,
  443. 35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429c69,-144,104.5,-217.7,106.5,
  444. -221c5.3,-9.3,12,-14,20,-14H400000v40H845.2724s-225.272,467,-225.272,467
  445. s-235,486,-235,486c-2.7,4.7,-9,7,-19,7c-6,0,-10,-1,-12,-3s-194,-422,-194,-422
  446. s-65,47,-65,47z M834 80H400000v40H845z'/></svg></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.08390500000000001em;"><span></span></span></span></span></span><span class="mclose delimcenter" style="top:0em;"><span class="delimsizing size2">)</span></span></span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:1.204292em;"><span style="top:-3.6029em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span></span></span></span></span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="minner"><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size2">(</span></span><span class="mord">1</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mord sqrt"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:0.956095em;"><span class="svg-align" style="top:-3em;"><span class="pstrut" style="height:3em;"></span><span class="mord" style="padding-left:0.833em;"><span class="mord">5</span></span></span><span style="top:-2.916095em;"><span class="pstrut" style="height:3em;"></span><span class="hide-tail" style="min-width:0.853em;height:1.08em;"><svg width='400em' height='1.08em' viewBox='0 0 400000 1080' preserveAspectRatio='xMinYMin slice'><path d='M95,702c-2.7,0,-7.17,-2.7,-13.5,-8c-5.8,-5.3,-9.5,
  447. -10,-9.5,-14c0,-2,0.3,-3.3,1,-4c1.3,-2.7,23.83,-20.7,67.5,-54c44.2,-33.3,65.8,
  448. -50.3,66.5,-51c1.3,-1.3,3,-2,5,-2c4.7,0,8.7,3.3,12,10s173,378,173,378c0.7,0,
  449. 35.3,-71,104,-213c68.7,-142,137.5,-285,206.5,-429c69,-144,104.5,-217.7,106.5,
  450. -221c5.3,-9.3,12,-14,20,-14H400000v40H845.2724s-225.272,467,-225.272,467
  451. s-235,486,-235,486c-2.7,4.7,-9,7,-19,7c-6,0,-10,-1,-12,-3s-194,-422,-194,-422
  452. s-65,47,-65,47z M834 80H400000v40H845z'/></svg></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.08390500000000001em;"><span></span></span></span></span></span><span class="mclose delimcenter" style="top:0em;"><span class="delimsizing size2">)</span></span></span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:1.204292em;"><span style="top:-3.6029em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">n</span></span></span></span></span></span></span></span><span class="mclose delimcenter" style="top:0em;"><span class="delimsizing size2">]</span></span></span></span></span></span></span></p>
  453. <p>代码揍这么简单:</p>
  454. <figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ferbo</span><span class="params">(<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line"> <span class="keyword">return</span> (<span class="built_in">sqrt</span>(<span class="number">5</span>)/<span class="number">5</span>)*(<span class="built_in">pow</span>((<span class="number">1</span>+<span class="built_in">sqrt</span>(<span class="number">5</span>))/<span class="number">2</span>,n)-<span class="built_in">pow</span>((<span class="number">1</span>-<span class="built_in">sqrt</span>(<span class="number">5</span>))/<span class="number">2</span>,n));</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
  455. <p>要是再加个快速幂就更棒了(够快了,懒得写)</p>
  456. </div>
  457. <footer class="post-footer">
  458. <div class="post-eof"></div>
  459. </footer>
  460. </article>
  461. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  462. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/dinic/">
  463. <script>
  464. (function(){
  465. if(''){
  466. if (prompt('Password?') !== ''){
  467. alert('GOAWAY!');
  468. history.back();
  469. }
  470. }
  471. })();
  472. </script>
  473. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  474. <meta itemprop="image" content="/images/avatar.gif">
  475. <meta itemprop="name" content="Alex">
  476. <meta itemprop="description" content="The blog of a middle school OIer">
  477. </span>
  478. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  479. <meta itemprop="name" content="Alex's Blog">
  480. </span>
  481. <header class="post-header">
  482. <h1 class="post-title" itemprop="name headline">
  483. <a href="/posts/dinic/" class="post-title-link" itemprop="url">网络最大流-Dinic</a>
  484. </h1>
  485. <div class="post-meta">
  486. <span class="post-meta-item">
  487. <span class="post-meta-item-icon">
  488. <i class="fa fa-calendar-o"></i>
  489. </span>
  490. <span class="post-meta-item-text">Posted on</span>
  491. <time title="Created: 2020-Mar-02 11:31:22" itemprop="dateCreated datePublished" datetime="2020-03-02T11:31:22+08:00">2020-Mar-02</time>
  492. </span>
  493. <span class="post-meta-item">
  494. <span class="post-meta-item-icon">
  495. <i class="fa fa-calendar-check-o"></i>
  496. </span>
  497. <span class="post-meta-item-text">Edited on</span>
  498. <time title="Modified: 2020-Mar-29 15:59:26" itemprop="dateModified" datetime="2020-03-29T15:59:26+08:00">2020-Mar-29</time>
  499. </span>
  500. <span id="/posts/dinic/" class="post-meta-item leancloud_visitors" data-flag-title="网络最大流-Dinic" title="Views">
  501. <span class="post-meta-item-icon">
  502. <i class="fa fa-eye"></i>
  503. </span>
  504. <span class="post-meta-item-text">Views: </span>
  505. <span class="leancloud-visitors-count"></span>
  506. </span>
  507. </div>
  508. </header>
  509. <div class="post-body" itemprop="articleBody">
  510. <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
  511. <p>存图方式(<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E8%A1%A8" target="_blank" rel="noopener" title="简单">邻接表</a>,<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" target="_blank" rel="noopener" title="都太简单了">邻接矩阵</a>),图的遍历(<a href="http://baidu.physton.com/?q=dfs" target="_blank" rel="noopener" title="简单">dfs</a>,<a href="http://baidu.physton.com/?q=bfs" target="_blank" rel="noopener" title="简单">bfs</a>)</p>
  512. <h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
  513. <p>我们举个例子吧:<br />
  514. 有一个毒瘤水管工,他会造水管,有一天他造了一个水管网络,就像一个图。其中有一个点只有出边,就是起点,还有一个点只有入边,是终点。<br />
  515. 点之间有一些管子,这些管子都有单位时间内的容量,现在毒瘤水管工想知道,他的管子在<strong>单位时间内</strong>在起点终点之间最多能流多少水。</p>
  516. <!--noindex-->
  517. <div class="post-button">
  518. <a class="btn" href="/posts/dinic/#more" rel="contents">
  519. Read more &raquo;
  520. </a>
  521. </div>
  522. <!--/noindex-->
  523. </div>
  524. <footer class="post-footer">
  525. <div class="post-eof"></div>
  526. </footer>
  527. </article>
  528. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  529. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/min-span-tree/">
  530. <script>
  531. (function(){
  532. if(''){
  533. if (prompt('Password?') !== ''){
  534. alert('GOAWAY!');
  535. history.back();
  536. }
  537. }
  538. })();
  539. </script>
  540. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  541. <meta itemprop="image" content="/images/avatar.gif">
  542. <meta itemprop="name" content="Alex">
  543. <meta itemprop="description" content="The blog of a middle school OIer">
  544. </span>
  545. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  546. <meta itemprop="name" content="Alex's Blog">
  547. </span>
  548. <header class="post-header">
  549. <h1 class="post-title" itemprop="name headline">
  550. <a href="/posts/min-span-tree/" class="post-title-link" itemprop="url">最小生成树</a>
  551. </h1>
  552. <div class="post-meta">
  553. <span class="post-meta-item">
  554. <span class="post-meta-item-icon">
  555. <i class="fa fa-calendar-o"></i>
  556. </span>
  557. <span class="post-meta-item-text">Posted on</span>
  558. <time title="Created: 2020-Mar-01 22:45:44" itemprop="dateCreated datePublished" datetime="2020-03-01T22:45:44+08:00">2020-Mar-01</time>
  559. </span>
  560. <span class="post-meta-item">
  561. <span class="post-meta-item-icon">
  562. <i class="fa fa-calendar-check-o"></i>
  563. </span>
  564. <span class="post-meta-item-text">Edited on</span>
  565. <time title="Modified: 2020-Mar-29 15:59:39" itemprop="dateModified" datetime="2020-03-29T15:59:39+08:00">2020-Mar-29</time>
  566. </span>
  567. <span id="/posts/min-span-tree/" class="post-meta-item leancloud_visitors" data-flag-title="最小生成树" title="Views">
  568. <span class="post-meta-item-icon">
  569. <i class="fa fa-eye"></i>
  570. </span>
  571. <span class="post-meta-item-text">Views: </span>
  572. <span class="leancloud-visitors-count"></span>
  573. </span>
  574. </div>
  575. </header>
  576. <div class="post-body" itemprop="articleBody">
  577. <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
  578. <p>存图方式(<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E8%A1%A8" target="_blank" rel="noopener" title="简单">邻接表</a>,<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" target="_blank" rel="noopener" title="都太简单了,没有一个打得过的">邻接矩阵</a>),<a href="https://schtonn.github.io/2020/03/01/union-find">并查集</a>。<br />
  579. 不会的快进入链接学习吧!</p>
  580. <h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
  581. <p>生成树,就是从一个图中选中<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>n</mi><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n-1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.66666em;vertical-align:-0.08333em;"></span><span class="mord mathdefault">n</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span><span class="mbin">−</span><span class="mspace" style="margin-right:0.2222222222222222em;"></span></span><span class="base"><span class="strut" style="height:0.64444em;vertical-align:0em;"></span><span class="mord">1</span></span></span></span>条边,使得这些边构成一棵树,并包含图中的所有节点。<br />
  582. 最小生成树,就是找到一种生成树,使得这个生成树的边权和最小。</p>
  583. <!--noindex-->
  584. <div class="post-button">
  585. <a class="btn" href="/posts/min-span-tree/#more" rel="contents">
  586. Read more &raquo;
  587. </a>
  588. </div>
  589. <!--/noindex-->
  590. </div>
  591. <footer class="post-footer">
  592. <div class="post-eof"></div>
  593. </footer>
  594. </article>
  595. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  596. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/union-find/">
  597. <script>
  598. (function(){
  599. if(''){
  600. if (prompt('Password?') !== ''){
  601. alert('GOAWAY!');
  602. history.back();
  603. }
  604. }
  605. })();
  606. </script>
  607. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  608. <meta itemprop="image" content="/images/avatar.gif">
  609. <meta itemprop="name" content="Alex">
  610. <meta itemprop="description" content="The blog of a middle school OIer">
  611. </span>
  612. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  613. <meta itemprop="name" content="Alex's Blog">
  614. </span>
  615. <header class="post-header">
  616. <h1 class="post-title" itemprop="name headline">
  617. <a href="/posts/union-find/" class="post-title-link" itemprop="url">并查集</a>
  618. </h1>
  619. <div class="post-meta">
  620. <span class="post-meta-item">
  621. <span class="post-meta-item-icon">
  622. <i class="fa fa-calendar-o"></i>
  623. </span>
  624. <span class="post-meta-item-text">Posted on</span>
  625. <time title="Created: 2020-Mar-01 22:44:33" itemprop="dateCreated datePublished" datetime="2020-03-01T22:44:33+08:00">2020-Mar-01</time>
  626. </span>
  627. <span class="post-meta-item">
  628. <span class="post-meta-item-icon">
  629. <i class="fa fa-calendar-check-o"></i>
  630. </span>
  631. <span class="post-meta-item-text">Edited on</span>
  632. <time title="Modified: 2020-Mar-29 15:59:58" itemprop="dateModified" datetime="2020-03-29T15:59:58+08:00">2020-Mar-29</time>
  633. </span>
  634. <span id="/posts/union-find/" class="post-meta-item leancloud_visitors" data-flag-title="并查集" title="Views">
  635. <span class="post-meta-item-icon">
  636. <i class="fa fa-eye"></i>
  637. </span>
  638. <span class="post-meta-item-text">Views: </span>
  639. <span class="leancloud-visitors-count"></span>
  640. </span>
  641. </div>
  642. </header>
  643. <div class="post-body" itemprop="articleBody">
  644. <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
  645. <p>哈哈,简单到爆,没有。</p>
  646. <h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
  647. <p>并查集是一种快到爆炸的集合算法,可以进行两项基本操作:合并两个集合(并)、查询两个参数是否在一个集合内(查)。这也是它名字的由来。</p>
  648. <!--noindex-->
  649. <div class="post-button">
  650. <a class="btn" href="/posts/union-find/#more" rel="contents">
  651. Read more &raquo;
  652. </a>
  653. </div>
  654. <!--/noindex-->
  655. </div>
  656. <footer class="post-footer">
  657. <div class="post-eof"></div>
  658. </footer>
  659. </article>
  660. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  661. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/tree-link/">
  662. <script>
  663. (function(){
  664. if(''){
  665. if (prompt('Password?') !== ''){
  666. alert('GOAWAY!');
  667. history.back();
  668. }
  669. }
  670. })();
  671. </script>
  672. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  673. <meta itemprop="image" content="/images/avatar.gif">
  674. <meta itemprop="name" content="Alex">
  675. <meta itemprop="description" content="The blog of a middle school OIer">
  676. </span>
  677. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  678. <meta itemprop="name" content="Alex's Blog">
  679. </span>
  680. <header class="post-header">
  681. <h1 class="post-title" itemprop="name headline">
  682. <a href="/posts/tree-link/" class="post-title-link" itemprop="url">树链剖分</a>
  683. </h1>
  684. <div class="post-meta">
  685. <span class="post-meta-item">
  686. <span class="post-meta-item-icon">
  687. <i class="fa fa-calendar-o"></i>
  688. </span>
  689. <span class="post-meta-item-text">Posted on</span>
  690. <time title="Created: 2020-Mar-01 22:41:02" itemprop="dateCreated datePublished" datetime="2020-03-01T22:41:02+08:00">2020-Mar-01</time>
  691. </span>
  692. <span class="post-meta-item">
  693. <span class="post-meta-item-icon">
  694. <i class="fa fa-calendar-check-o"></i>
  695. </span>
  696. <span class="post-meta-item-text">Edited on</span>
  697. <time title="Modified: 2020-Mar-29 15:59:54" itemprop="dateModified" datetime="2020-03-29T15:59:54+08:00">2020-Mar-29</time>
  698. </span>
  699. <span id="/posts/tree-link/" class="post-meta-item leancloud_visitors" data-flag-title="树链剖分" title="Views">
  700. <span class="post-meta-item-icon">
  701. <i class="fa fa-eye"></i>
  702. </span>
  703. <span class="post-meta-item-text">Views: </span>
  704. <span class="leancloud-visitors-count"></span>
  705. </span>
  706. </div>
  707. </header>
  708. <div class="post-body" itemprop="articleBody">
  709. <h3 id="前置知识"><a class="markdownIt-Anchor" href="#前置知识"></a> 前置知识</h3>
  710. <p>必备:存图方式(<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E8%A1%A8" target="_blank" rel="noopener" title="简单">邻接表</a>,<a href="http://baidu.physton.com/?q=%E9%82%BB%E6%8E%A5%E7%9F%A9%E9%98%B5" target="_blank" rel="noopener" title="都太简单了,没有一个打得过的">邻接矩阵</a>),<a href="http://baidu.physton.com/?q=dfs%E5%BA%8F" target="_blank" rel="noopener">dfs序</a>。<br />
  711. 维护:<a href="http://baidu.physton.com/?q=%E7%BA%BF%E6%AE%B5%E6%A0%91" target="_blank" rel="noopener">线段树</a>、<a href="http://baidu.physton.com/?q=%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84" target="_blank" rel="noopener">树状数组</a>、<a href="http://baidu.physton.com/?q=BST" target="_blank" rel="noopener">BST</a>。<br />
  712. 不会的快进入链接学习吧!</p>
  713. <h3 id="引入"><a class="markdownIt-Anchor" href="#引入"></a> 引入</h3>
  714. <p>树链剖分,简单来说就是把树分割成链,然后维护每一条链。一般的维护算法有线段树,树状数组和BST。复杂度为<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo stretchy="false">(</mo><mi>l</mi><mi>o</mi><mi>g</mi><mi>n</mi><mo stretchy="false">)</mo></mrow><annotation encoding="application/x-tex">O(log n)</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mord mathdefault" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathdefault" style="margin-right:0.01968em;">l</span><span class="mord mathdefault">o</span><span class="mord mathdefault" style="margin-right:0.03588em;">g</span><span class="mord mathdefault">n</span><span class="mclose">)</span></span></span></span>。</p>
  715. <!--noindex-->
  716. <div class="post-button">
  717. <a class="btn" href="/posts/tree-link/#more" rel="contents">
  718. Read more &raquo;
  719. </a>
  720. </div>
  721. <!--/noindex-->
  722. </div>
  723. <footer class="post-footer">
  724. <div class="post-eof"></div>
  725. </footer>
  726. </article>
  727. <article itemscope itemtype="http://schema.org/Article" class="post-block home" lang="en">
  728. <link itemprop="mainEntityOfPage" href="https://schtonn.github.io/posts/test/">
  729. <script>
  730. (function(){
  731. if(''){
  732. if (prompt('Password?') !== ''){
  733. alert('GOAWAY!');
  734. history.back();
  735. }
  736. }
  737. })();
  738. </script>
  739. <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
  740. <meta itemprop="image" content="/images/avatar.gif">
  741. <meta itemprop="name" content="Alex">
  742. <meta itemprop="description" content="The blog of a middle school OIer">
  743. </span>
  744. <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
  745. <meta itemprop="name" content="Alex's Blog">
  746. </span>
  747. <header class="post-header">
  748. <h1 class="post-title" itemprop="name headline">
  749. <a href="/posts/test/" class="post-title-link" itemprop="url">test</a>
  750. </h1>
  751. <div class="post-meta">
  752. <span class="post-meta-item">
  753. <span class="post-meta-item-icon">
  754. <i class="fa fa-calendar-o"></i>
  755. </span>
  756. <span class="post-meta-item-text">Posted on</span>
  757. <time title="Created: 2020-Mar-01 11:06:43" itemprop="dateCreated datePublished" datetime="2020-03-01T11:06:43+08:00">2020-Mar-01</time>
  758. </span>
  759. <span class="post-meta-item">
  760. <span class="post-meta-item-icon">
  761. <i class="fa fa-calendar-check-o"></i>
  762. </span>
  763. <span class="post-meta-item-text">Edited on</span>
  764. <time title="Modified: 2020-Mar-29 15:59:49" itemprop="dateModified" datetime="2020-03-29T15:59:49+08:00">2020-Mar-29</time>
  765. </span>
  766. <span id="/posts/test/" class="post-meta-item leancloud_visitors" data-flag-title="test" title="Views">
  767. <span class="post-meta-item-icon">
  768. <i class="fa fa-eye"></i>
  769. </span>
  770. <span class="post-meta-item-text">Views: </span>
  771. <span class="leancloud-visitors-count"></span>
  772. </span>
  773. </div>
  774. </header>
  775. <div class="post-body" itemprop="articleBody">
  776. <p><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mtext mathvariant="monospace">Is</mtext><mtext> </mtext><mtext mathvariant="monospace">KaTeX</mtext><mtext> </mtext><mtext mathvariant="monospace">working?-IT</mtext><mtext> </mtext><mtext mathvariant="monospace">WORKED!NICE!</mtext></mrow><annotation encoding="application/x-tex">\texttt{Is KaTeX working?-IT WORKED!NICE!}</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.83333em;vertical-align:-0.22222em;"></span><span class="mord text"><span class="mord texttt">Is KaTeX working?-IT WORKED!NICE!</span></span></span></span></span></p>
  777. <p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mi>a</mi><mi>b</mi></msup></mrow><annotation encoding="application/x-tex">a^b
  778. </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.8991079999999999em;vertical-align:0em;"></span><span class="mord"><span class="mord mathdefault">a</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="height:0.8991079999999999em;"><span style="top:-3.113em;margin-right:0.05em;"><span class="pstrut" style="height:2.7em;"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathdefault mtight">b</span></span></span></span></span></span></span></span></span></span></span></span></p>
  779. <p class='katex-block'><span class="katex-display"><span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo fence="true">(</mo><mfrac><mi>a</mi><mi>b</mi></mfrac><mo fence="true">)</mo></mrow><annotation encoding="application/x-tex">\left(\dfrac{a}{b}\right)
  780. </annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1.8359999999999999em;vertical-align:-0.686em;"></span><span class="minner"><span class="mopen delimcenter" style="top:0em;"><span class="delimsizing size2">(</span></span><span class="mord"><span class="mopen nulldelimiter"></span><span class="mfrac"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist" style="height:1.10756em;"><span style="top:-2.314em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathdefault">b</span></span></span><span style="top:-3.23em;"><span class="pstrut" style="height:3em;"></span><span class="frac-line" style="border-bottom-width:0.04em;"></span></span><span style="top:-3.677em;"><span class="pstrut" style="height:3em;"></span><span class="mord"><span class="mord mathdefault">a</span></span></span></span><span class="vlist-s">​</span></span><span class="vlist-r"><span class="vlist" style="height:0.686em;"><span></span></span></span></span></span><span class="mclose nulldelimiter"></span></span><span class="mclose delimcenter" style="top:0em;"><span class="delimsizing size2">)</span></span></span></span></span></span></span></p>
  781. </div>
  782. <footer class="post-footer">
  783. <div class="post-eof"></div>
  784. </footer>
  785. </article>
  786. </div>
  787. </div>
  788. <script>
  789. window.addEventListener('tabs:register', () => {
  790. let activeClass = CONFIG.comments.activeClass;
  791. if (CONFIG.comments.storage) {
  792. activeClass = localStorage.getItem('comments_active') || activeClass;
  793. }
  794. if (activeClass) {
  795. let activeTab = document.querySelector(`a[href="#comment-${activeClass}"]`);
  796. if (activeTab) {
  797. activeTab.click();
  798. }
  799. }
  800. });
  801. if (CONFIG.comments.storage) {
  802. window.addEventListener('tabs:click', event => {
  803. if (!event.target.matches('.tabs-comment .tab-content .tab-pane')) return;
  804. let commentClass = event.target.classList[1];
  805. localStorage.setItem('comments_active', commentClass);
  806. });
  807. }
  808. </script>
  809. </div>
  810. <div class="toggle sidebar-toggle">
  811. <span class="toggle-line toggle-line-first"></span>
  812. <span class="toggle-line toggle-line-middle"></span>
  813. <span class="toggle-line toggle-line-last"></span>
  814. </div>
  815. <aside class="sidebar">
  816. <div class="sidebar-inner">
  817. <ul class="sidebar-nav motion-element">
  818. <li class="sidebar-nav-toc">
  819. Table of Contents
  820. </li>
  821. <li class="sidebar-nav-overview">
  822. Overview
  823. </li>
  824. </ul>
  825. <!--noindex-->
  826. <div class="post-toc-wrap sidebar-panel">
  827. </div>
  828. <!--/noindex-->
  829. <div class="site-overview-wrap sidebar-panel">
  830. <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
  831. <p class="site-author-name" itemprop="name">Alex</p>
  832. <div class="site-description" itemprop="description">The blog of a middle school OIer</div>
  833. </div>
  834. <div class="site-state-wrap motion-element">
  835. <nav class="site-state">
  836. <div class="site-state-item site-state-posts">
  837. <a href="/archives">
  838. <span class="site-state-item-count">10</span>
  839. <span class="site-state-item-name">posts</span>
  840. </a>
  841. </div>
  842. <div class="site-state-item site-state-tags">
  843. <a href="/tags/">
  844. <span class="site-state-item-count">4</span>
  845. <span class="site-state-item-name">tags</span></a>
  846. </div>
  847. </nav>
  848. </div>
  849. <div class="links-of-author motion-element">
  850. <span class="links-of-author-item">
  851. <a href="https://github.com/schtonn" title="GitHub → https:&#x2F;&#x2F;github.com&#x2F;schtonn" rel="noopener" target="_blank"><i class="fa fa-fw fa-github"></i>GitHub</a>
  852. </span>
  853. <span class="links-of-author-item">
  854. <a href="skype:alex?call|chat" title="Skype → skype:alex?call|chat" rel="noopener" target="_blank"><i class="fa fa-fw fa-skype"></i>Skype</a>
  855. </span>
  856. </div>
  857. <div class="links-of-blogroll motion-element">
  858. <div class="links-of-blogroll-title">
  859. <i class="fa fa-fw fa-link"></i>
  860. Links
  861. </div>
  862. <ul class="links-of-blogroll-list">
  863. <li class="links-of-blogroll-item">
  864. <a href="https://yonghong.github.io/" title="https:&#x2F;&#x2F;yonghong.github.io" rel="noopener" target="_blank">Yonghong</a>
  865. </li>
  866. <li class="links-of-blogroll-item">
  867. <a href="https://source.unsplash.com/random/1600x900" title="https:&#x2F;&#x2F;source.unsplash.com&#x2F;random&#x2F;1600x900" rel="noopener" target="_blank">Background</a>
  868. </li>
  869. </ul>
  870. </div>
  871. </div>
  872. <div id="treefrog" style="text-align: center;margin-top: 18px;">
  873. <object type="application/x-shockwave-flash" style="outline:none;" data="/js/treefrog.swf?up_bodyColor=444444&up_pattern=0&up_flyColor=777777&up_tongueColor=555555&up_patternColor=000000&up_releaseFly=0&up_frogName=Froggie&up_backgroundImage=http://&up_bellySize=.5&up_footColor=444444&up_eyeColor=444444&up_backgroundColor=222222&" width="300" height="600"><param name="movie" value="http://cdn.abowman.com/widgets/treefrog/treefrog.swf?up_bodyColor=444444&up_pattern=0&up_flyColor=777777&up_tongueColor=555555&up_patternColor=000000&up_releaseFly=0&up_frogName=Froggie&up_backgroundImage=http://&up_bellySize=.5&up_footColor=444444&up_eyeColor=444444&up_backgroundColor=222222&"></param><param name="AllowScriptAccess" value="always"></param><param name="wmode" value="opaque"></param><param name="scale" value="noscale"/><param name="salign" value="tl"/></object>
  874. </div>
  875. </div>
  876. </aside>
  877. <div id="sidebar-dimmer"></div>
  878. </div>
  879. </main>
  880. <footer class="footer">
  881. <div class="footer-inner">
  882. <div class="copyright">
  883. &copy;
  884. <span itemprop="copyrightYear">2020</span>
  885. <span class="with-love">
  886. <i class="fa fa-user"></i>
  887. </span>
  888. <span class="author" itemprop="copyrightHolder">Alex Xiang</span>
  889. </div>
  890. </div>
  891. </footer>
  892. </div>
  893. <script src="/lib/anime.min.js"></script>
  894. <script src="//cdn.jsdelivr.net/npm/lozad@1/dist/lozad.min.js"></script>
  895. <script src="/lib/velocity/velocity.min.js"></script>
  896. <script src="/lib/velocity/velocity.ui.min.js"></script>
  897. <script src="/js/utils.js"></script>
  898. <script src="/js/motion.js"></script>
  899. <script src="/js/schemes/muse.js"></script>
  900. <script src="/js/next-boot.js"></script>
  901. <script>
  902. (function(){
  903. var bp = document.createElement('script');
  904. var curProtocol = window.location.protocol.split(':')[0];
  905. bp.src = (curProtocol === 'https') ? 'https://zz.bdstatic.com/linksubmit/push.js' : 'http://push.zhanzhang.baidu.com/push.js';
  906. var s = document.getElementsByTagName("script")[0];
  907. s.parentNode.insertBefore(bp, s);
  908. })();
  909. </script>
  910. <link rel="stylesheet" href="//cdn.jsdelivr.net/npm/katex@0/dist/katex.min.css">
  911. <script>
  912. NexT.utils.loadComments(document.querySelector('#valine-comments'), () => {
  913. NexT.utils.getScript('//unpkg.com/valine/dist/Valine.min.js', () => {
  914. var GUEST = ['nick', 'mail', 'link'];
  915. var guest = 'nick,mail,link';
  916. guest = guest.split(',').filter(item => {
  917. return GUEST.includes(item);
  918. });
  919. new Valine({
  920. el : '#valine-comments',
  921. verify : true,
  922. notify : true,
  923. appId : 'BmologYYnRqCv0SLHDeDdA17-gzGzoHsz',
  924. appKey : 'w9mVebFMdCmY6Nh9vfcBGaGt',
  925. placeholder: "Balabalabalablalablablbalbalabllbalblablblaablbllbalbalbllbalabalbalbalblabalbalb.",
  926. avatar : 'mm',
  927. meta : guest,
  928. pageSize : '10' || 10,
  929. visitor : true,
  930. lang : 'en' || 'zh-cn',
  931. path : location.pathname,
  932. recordIP : true,
  933. serverURLs : ''
  934. });
  935. }, window.Valine);
  936. });
  937. </script>
  938. </body>
  939. </html>