schtonn
/
public


			
							123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549
							<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  

  <title>Schtonn&#39;s Blog</title>
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta property="og:type" content="website">
<meta property="og:title" content="Schtonn&#39;s Blog">
<meta property="og:url" content="http://yoursite.com/index.html">
<meta property="og:site_name" content="Schtonn&#39;s Blog">
<meta property="og:locale" content="en_US">
<meta property="article:author" content="Schtonn">
<meta name="twitter:card" content="summary">
  
    <link rel="alternate" href="/atom.xml" title="Schtonn&#39;s Blog" type="application/atom+xml">
  
  
    <link rel="icon" href="/favicon.png">
  
  
    <link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
  
  
<link rel="stylesheet" href="/css/style.css">

<meta name="generator" content="Hexo 4.2.0"></head>

<body>
  <div id="container">
    <div id="wrap">
      <header id="header">
  <div id="banner"></div>
  <div id="header-outer" class="outer">
    <div id="header-title" class="inner">
      <h1 id="logo-wrap">
        <a href="/" id="logo">Schtonn&#39;s Blog</a>
      </h1>
      
        <h2 id="subtitle-wrap">
          <a href="/" id="subtitle">Schtonn&#39;s blog</a>
        </h2>
      
    </div>
    <div id="header-inner" class="inner">
      <nav id="main-nav">
        <a id="main-nav-toggle" class="nav-icon"></a>
        
          <a class="main-nav-link" href="/">Home</a>
        
          <a class="main-nav-link" href="/archives">Archives</a>
        
      </nav>
      <nav id="sub-nav">
        
          <a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
        
        <a id="nav-search-btn" class="nav-icon" title="Search"></a>
      </nav>
      <div id="search-form-wrap">
        <form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit">&#xF002;</button><input type="hidden" name="sitesearch" value="http://yoursite.com"></form>
      </div>
    </div>
  </div>
</header>
      <div class="outer">
        <section id="main">
  
    <article id="post-plan" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/01/plan/" class="article-date">
  <time datetime="2020-03-01T14:36:07.000Z" itemprop="datePublished">2020-Mar-01</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2020/03/01/plan/">plan</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="薄弱项">薄弱项</h3>
<ol type="1">
<li><strong>作文</strong>
<ol type="1">
<li>写日记
<ul>
<li>每天固定 9:00-9:30</li>
<li>内容不必精美</li>
<li>一周写五天，两天机动</li>
</ul></li>
<li>读书
<ul>
<li>作文辅导书为主 <code>作文大全等</code></li>
<li>其他书籍为辅</li>
</ul></li>
<li>录音</li>
</ol></li>
</ol>
        
          <p class="article-more-link">
            <a href="/2020/03/01/plan/#more">Read More</a>
          </p>
        
      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/01/plan/" data-id="ck7cjuv770006pc13gb2c772t" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/other/" rel="tag">other</a></li></ul>

    </footer>
  </div>
  
</article>


    <article id="post-segment-tree" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/02/segment-tree/" class="article-date">
  <time datetime="2020-03-02T03:37:36.000Z" itemprop="datePublished">2020-Mar-02</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2020/03/02/segment-tree/">线段树</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="前置知识">前置知识</h3>
<p>数组，结构体，二叉树</p>
<h3 id="引入">引入</h3>
<p>有时候我们会遇到一些大规模的区间查找和区间修改问题，比如让你维护一个 <span class="math inline">\(10^5\)</span> 长度的数列，要求操作有区间求和、区间加（区间每个数加上一个值），让你在一秒内完成 <span class="math inline">\(10^5\)</span> 次操作。 暴力是肯定不行的，数据范围太大，会超时。 所以我们就有一种专门解决大范围区间修改查询的数据结构：线段树。</p>
        
          <p class="article-more-link">
            <a href="/2020/03/02/segment-tree/#more">Read More</a>
          </p>
        
      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/02/segment-tree/" data-id="ck7cjuv730004pc13034b6qa3" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph/" rel="tag">graph</a></li></ul>

    </footer>
  </div>
  
</article>


    <article id="post-ferbonacci" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/02/ferbonacci/" class="article-date">
  <time datetime="2020-03-02T03:35:44.000Z" itemprop="datePublished">2020-Mar-02</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2020/03/02/ferbonacci/">斐波那契数列-O(1)</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p>引自：《信息学奥赛之-数学一本通》 揍是这样： <span class="math display">\[\operatorname{F}(n)=\dfrac{\sqrt{5}}{5}\cdot\left[\left(1+\sqrt{5}\right)^n-\left(1-\sqrt{5}\right)^n\right]\]</span> 代码揍这么简单： <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> 要是再加个快速幂就更棒了（够快了，懒得写）</p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/02/ferbonacci/" data-id="ck7cjuv6x0002pc13efhpdn5h" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/math/" rel="tag">math</a></li></ul>

    </footer>
  </div>
  
</article>


    <article id="post-dinic" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/02/dinic/" class="article-date">
  <time datetime="2020-03-02T03:31:22.000Z" itemprop="datePublished">2020-Mar-02</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2020/03/02/dinic/">网络最大流-Dinic</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="前置知识">前置知识</h3>
<p>存图方式（<a href="http://baidu.physton.com/?q=邻接表" target="_blank" rel="noopener" title="简单">邻接表</a>，<a href="http://baidu.physton.com/?q=邻接矩阵" 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>
<h3 id="引入">引入</h3>
<p>我们举个例子吧： 有一个毒瘤水管工，他会造水管，有一天他造了一个水管网络，就像一个图。其中有一个点只有出边，就是起点，还有一个点只有入边，是终点。 点之间有一些管子，这些管子都有单位时间内的容量，现在毒瘤水管工想知道，他的管子在<strong>单位时间内</strong>在起点终点之间最多能流多少水。
        
          <p class="article-more-link">
            <a href="/2020/03/02/dinic/#more">Read More</a>
          </p>
        
      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/02/dinic/" data-id="ck7cjuv6t0001pc135euzdup8" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph/" rel="tag">graph</a></li></ul>

    </footer>
  </div>
  
</article>


    <article id="post-min-span-tree" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/01/min-span-tree/" class="article-date">
  <time datetime="2020-03-01T14:45:44.000Z" itemprop="datePublished">2020-Mar-01</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2020/03/01/min-span-tree/">最小生成树</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="前置知识">前置知识</h3>
<p>存图方式（<a href="http://baidu.physton.com/?q=邻接表" target="_blank" rel="noopener" title="简单">邻接表</a>，<a href="http://baidu.physton.com/?q=邻接矩阵" target="_blank" rel="noopener" title="都太简单了，没有一个打得过的">邻接矩阵</a>），<a href="https://schtonn.github.io/2020/03/01/union-find" target="_blank" rel="noopener">并查集</a>。 不会的快进入链接学习吧！</p>
<h3 id="引入">引入</h3>
<p>生成树，就是从一个图中选中<span class="math inline">\(n-1\)</span>条边，使得这些边构成一棵树，并包含图中的所有节点。 最小生成树，就是找到一种生成树，使得这个生成树的边权和最小。
        
          <p class="article-more-link">
            <a href="/2020/03/01/min-span-tree/#more">Read More</a>
          </p>
        
      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/01/min-span-tree/" data-id="ck7cjuv750005pc1346vq1oag" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph/" rel="tag">graph</a></li></ul>

    </footer>
  </div>
  
</article>


    <article id="post-union-find" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/01/union-find/" class="article-date">
  <time datetime="2020-03-01T14:44:33.000Z" itemprop="datePublished">2020-Mar-01</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2020/03/01/union-find/">并查集</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="前置知识">前置知识</h3>
<p>哈哈，简单到爆，没有。</p>
<h3 id="引入">引入</h3>
<p>并查集是一种快到爆炸的集合算法，可以进行两项基本操作：合并两个集合（并）、查询两个参数是否在一个集合内（查）。这也是它名字的由来。
        
          <p class="article-more-link">
            <a href="/2020/03/01/union-find/#more">Read More</a>
          </p>
        
      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/01/union-find/" data-id="ck7cjuv7e000dpc131fbxc304" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/struct/" rel="tag">struct</a></li></ul>

    </footer>
  </div>
  
</article>


    <article id="post-tree-link" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/01/tree-link/" class="article-date">
  <time datetime="2020-03-01T14:41:02.000Z" itemprop="datePublished">2020-Mar-01</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2020/03/01/tree-link/">树链剖分</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <h3 id="前置知识">前置知识</h3>
<p>必备：存图方式（<a href="http://baidu.physton.com/?q=邻接表" target="_blank" rel="noopener" title="简单">邻接表</a>，<a href="http://baidu.physton.com/?q=邻接矩阵" target="_blank" rel="noopener" title="都太简单了，没有一个打得过的">邻接矩阵</a>），<a href="http://baidu.physton.com/?q=dfs%E5%BA%8F" target="_blank" rel="noopener">dfs序</a>。 维护：<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>。 不会的快进入链接学习吧！</p>
<h3 id="引入">引入</h3>
<p>树链剖分，简单来说就是把树分割成链，然后维护每一条链。一般的维护算法有线段树，树状数组和BST。复杂度为<span class="math inline">\(O(log n)\)</span>。
        
          <p class="article-more-link">
            <a href="/2020/03/01/tree-link/#more">Read More</a>
          </p>
        
      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/01/tree-link/" data-id="ck7cjuv7b000bpc136ug4frq4" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/graph/" rel="tag">graph</a></li></ul>

    </footer>
  </div>
  
</article>


    <article id="post-test" class="article article-type-post" itemscope itemprop="blogPost">
  <div class="article-meta">
    <a href="/2020/03/01/test/" class="article-date">
  <time datetime="2020-03-01T03:06:43.000Z" itemprop="datePublished">2020-Mar-01</time>
</a>
    
  </div>
  <div class="article-inner">
    
    
      <header class="article-header">
        
  
    <h1 itemprop="name">
      <a class="article-title" href="/2020/03/01/test/">test</a>
    </h1>
  

      </header>
    
    <div class="article-entry" itemprop="articleBody">
      
        <p><span class="math inline">\(\texttt{Is KaTeX working?-IT WORKED!NICE!}\)</span> <span class="math display">\[a^b\]</span> <span class="math display">\[\left(\dfrac{a}{b}\right)\]</span></p>

      
    </div>
    <footer class="article-footer">
      <a data-url="http://yoursite.com/2020/03/01/test/" data-id="ck7cjuv790009pc13hflwhteh" class="article-share-link">Share</a>
      
      
  <ul class="article-tag-list" itemprop="keywords"><li class="article-tag-list-item"><a class="article-tag-list-link" href="/tags/other/" rel="tag">other</a></li></ul>

    </footer>
  </div>
  
</article>


</section>
        
          <aside id="sidebar">
  
    
  <div class="widget-wrap">
    <h3 class="widget-title">Tags</h3>
    <div class="widget">
      <ul class="tag-list" itemprop="keywords"><li class="tag-list-item"><a class="tag-list-link" href="/tags/graph/" rel="tag">graph</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/math/" rel="tag">math</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/other/" rel="tag">other</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/struct/" rel="tag">struct</a></li></ul>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Tag Cloud</h3>
    <div class="widget tagcloud">
      <a href="/tags/graph/" style="font-size: 20px;">graph</a> <a href="/tags/math/" style="font-size: 10px;">math</a> <a href="/tags/other/" style="font-size: 15px;">other</a> <a href="/tags/struct/" style="font-size: 10px;">struct</a>
    </div>
  </div>

  
  <div class="widget-wrap">
    <h3 class="widget-title">Archives</h3>
    <div class="widget">
      <ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2020/03/">March 2020</a></li></ul>
    </div>
  </div>


  <div class="widget-wrap">
    <h3 class="widget-title">Recent Posts</h3>
    <div class="widget">
      <ul>
        
          <li>
            <a href="/2020/03/02/segment-tree/">线段树</a>
          </li>
        
          <li>
            <a href="/2020/03/02/ferbonacci/">斐波那契数列-O(1)</a>
          </li>
        
          <li>
            <a href="/2020/03/02/dinic/">网络最大流-Dinic</a>
          </li>
        
          <li>
            <a href="/2020/03/01/min-span-tree/">最小生成树</a>
          </li>
        
          <li>
            <a href="/2020/03/01/union-find/">并查集</a>
          </li>
        
      </ul>
    </div>
  </div>

  
</aside>
        
      </div>
      <footer id="footer">
  
  <div class="outer">
    <div id="footer-info" class="inner">
      &copy; 2020 Schtonn<br>
      Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
    </div>
  </div>
</footer>
    </div>
    <nav id="mobile-nav">
  
    <a href="/" class="mobile-nav-link">Home</a>
  
    <a href="/archives" class="mobile-nav-link">Archives</a>
  
</nav>
    

<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>


<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">

  
<script src="/fancybox/jquery.fancybox.pack.js"></script>


<script src="/js/script.js"></script>


  </div>
</body>
</html>