一些c++模板.pdf 866.67KB

l141930402需要积分:4(1积分=1元)

资源文件列表:

c++.zip 大约有3个文件

c++/
c++/c++模板.pdf 468.12KB
c++/基础算法.pdf 579.08KB

资源介绍:

一些c++模板.pdf

<link href="/image.php?url=https://csdnimg.cn/release/download_crawler_static/css/base.min.css" rel="stylesheet"/><link href="/image.php?url=https://csdnimg.cn/release/download_crawler_static/css/fancy.min.css" rel="stylesheet"/><link href="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90048609/5/raw.css" rel="stylesheet"/><div id="sidebar" style="display: none"><div id="outline"></div></div><div class="pf w0 h0" data-page-no="1" id="pf1"><div class="pc pc1 w0 h0"><img alt="" class="bi x0 y0 w1 h1" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90048609/bg1.jpg"/><div class="c x0 y1 w2 h0"><div class="t m0 x1 h2 y2 ff1 fs0 fc0 sc0 ls0 ws0">1 </div><div class="t m0 x2 h2 y3 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h3 y4 ff2 fs1 fc0 sc1 ls0 ws0">常用代码模板<span class="_ _0"> </span><span class="ff3 sc0">1</span>——基础算法<span class="ff1 sc0"> </span></div><div class="t m0 x2 h4 y5 ff2 fs1 fc0 sc0 ls0 ws0">快速排序算法模<span class="_ _1"></span>板<span class="ff4"> <span class="_ _0"> </span></span>——<span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 785. <span class="_"> </span></span>快速排序<span class="ff1"> </span></div><div class="t m0 x2 h4 y6 ff4 fs1 fc0 sc0 ls0 ws0">void quic<span class="_ _1"></span>k_sort(int q[],<span class="_ _1"></span> int l, in<span class="_ _1"></span>t r)<span class="ff1"> </span></div><div class="t m0 x2 h4 y7 ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y8 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">if (l >= <span class="_ _1"></span>r) return<span class="_ _1"></span>;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y9 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 ya ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">int i = l<span class="_ _1"></span> <span class="ff1">-</span> 1, j = r + <span class="_ _1"></span>1, x = q[l + r ><span class="_ _1"></span>> 1];<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yb ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (i<span class="_ _1"></span> < j)<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yc ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">{<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yd ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>do i ++ ; while (q[i]<span class="_ _1"></span> < x);<span class="ff1"> </span></div><div class="t m0 x2 h4 ye ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>do j <span class="ff1 ls2">--</span> ; while (q[j<span class="_ _1"></span>] > x);<span class="ff1"> </span></div><div class="t m0 x2 h4 yf ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (i < j) swap<span class="_ _1"></span>(q[i], q[j]);<span class="ff1"> </span></div><div class="t m0 x2 h4 y10 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">}<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y11 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">quick_so<span class="_ _1"></span>rt(q, l, j), quic<span class="_ _1"></span>k_sort(q, j + <span class="_ _1"></span>1, r);<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y12 ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y13 ff2 fs1 fc0 sc0 ls0 ws0">归并排序算法模<span class="_ _1"></span>板<span class="ff4"> <span class="_ _0"> </span></span>——<span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 787. <span class="_"> </span></span>归并排序<span class="ff1"> </span></div><div class="t m0 x2 h4 y14 ff4 fs1 fc0 sc0 ls0 ws0">void mer<span class="_ _1"></span>ge_so<span class="_ _1"></span>rt(int q[],<span class="_ _1"></span> int l, in<span class="_ _1"></span>t r)<span class="ff1"> </span></div><div class="t m0 x2 h4 y15 ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y16 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">if (l >= <span class="_ _1"></span>r) return<span class="_ _1"></span>;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y17 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y18 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">int mi<span class="_ _1"></span>d = l + r >> <span class="_ _1"></span>1;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y19 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">mer<span class="_ _1"></span>ge_sort(q, l,<span class="_ _1"></span> mid);<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y1a ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">mer<span class="_ _1"></span>ge_sort(q, m<span class="_ _1"></span>id + 1, r)<span class="_ _1"></span>;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y1b ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y1c ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">int k <span class="_ _1"></span>= 0, i = l, j = m<span class="_ _1"></span>id + 1;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y1d ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (i<span class="_ _1"></span> <= mid && j <<span class="_ _1"></span>= r)<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y1e ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (q[i] <= q[j]) t<span class="_ _1"></span>mp[k ++ ] = q[i ++ ]<span class="_ _1"></span>;<span class="ff1"> </span></div><div class="t m0 x2 h4 y1f ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>else tmp[k ++ ] = q<span class="_ _1"></span>[j ++ ];<span class="ff1"> </span></div><div class="t m0 x2 h4 y20 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y21 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (i<span class="_ _1"></span> <= mid) tmp[<span class="_ _1"></span>k ++ ] = q[i ++ ];<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y22 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (j <= r) tmp[k ++ ]<span class="_ _1"></span> = q[j ++ ];<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y23 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y24 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">fo<span class="_ _1"></span>r (i = l, j = <span class="_ _1"></span>0; i <= r; i ++, j ++ ) q[i<span class="_ _1"></span>] = tmp[j];<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y25 ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y26 ff2 fs1 fc0 sc0 ls0 ws0">整数二分算法模<span class="_ _1"></span>板<span class="ff4"> <span class="_ _0"> </span></span>——<span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 789. <span class="_"> </span></span>数的范围<span class="ff1"> </span></div><div class="t m0 x2 h4 y27 ff4 fs1 fc0 sc0 ls0 ws0">bool check(in<span class="_ _1"></span>t x) {/* ... */<span class="_ _1"></span>} // <span class="_ _2"> </span><span class="ff2">检查<span class="_ _0"> </span></span>x<span class="_"> </span><span class="ff2">是否满足某种性<span class="_ _1"></span>质<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y28 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y29 ff4 fs1 fc0 sc0 ls3 ws0">// <span class="_ _0"> </span><span class="ff2 ls4">区间<span class="_ _3"></span></span><span class="ls0">[l, r]<span class="ff2">被划分<span class="_ _1"></span>成<span class="ff4">[l, mid]</span>和<span class="ff4">[mid<span class="_ _1"></span> + 1, r]<span class="ff2">时使<span class="_ _1"></span>用：<span class="ff1"> </span></span></span></span></span></div><div class="t m0 x2 h4 y2a ff4 fs1 fc0 sc0 ls0 ws0">int bs<span class="_ _1"></span>earch_1(in<span class="_ _1"></span>t l, in<span class="_ _1"></span>t r)<span class="ff1"> </span></div><div class="t m0 x2 h4 y2b ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y2c ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (l<span class="_ _1"></span> < r)<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2d ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">{<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2e ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>int mid = l + <span class="_ _1"></span>r >> 1;<span class="ff1"> </span></div><div class="t m0 x2 h4 y2f ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (check(mid<span class="_ _1"></span>)) r = mid; <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span>// check()<span class="ff2 ls4">判断<span class="_ _0"> </span></span>mid<span class="_"> </span><span class="ff2">是否满足性质<span class="ff1"> </span></span></div></div></div><div class="pi" data-data='{"ctm":[1.611792,0.000000,0.000000,1.611792,0.000000,0.000000]}'></div></div><div id="pf2" class="pf w0 h0" data-page-no="2"><div class="pc pc2 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90048609/bg2.jpg"><div class="c x0 y1 w2 h0"><div class="t m0 x1 h2 y2 ff1 fs0 fc0 sc0 ls0 ws0">2 </div><div class="t m0 x2 h2 y3 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y30 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>else l = mid + 1<span class="_ _1"></span>;<span class="ff1"> </span></div><div class="t m0 x2 h4 y31 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">}<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y6 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">re<span class="_ _1"></span>turn l;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y7 ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y32 ff4 fs1 fc0 sc0 ls3 ws0">// <span class="_ _0"> </span><span class="ff2 ls4">区间<span class="_ _3"></span></span><span class="ls0">[l, r]<span class="ff2">被划分<span class="_ _1"></span>成<span class="ff4">[l, mid <span class="ff1">-</span> <span class="ls5">1]<span class="_ _1"></span><span class="ff2 ls0">和<span class="ff4">[mid, r]<span class="_ _1"></span><span class="ff2">时使用：<span class="ff1"> </span></span></span></span></span></span></span></span></div><div class="t m0 x2 h4 y9 ff4 fs1 fc0 sc0 ls0 ws0">int bs<span class="_ _1"></span>earch_2<span class="_ _1"></span>(int l, in<span class="_ _1"></span>t r)<span class="ff1"> </span></div><div class="t m0 x2 h4 ya ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 yb ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (l<span class="_ _1"></span> < r)<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yc ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">{<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yd ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>int mid = l + <span class="_ _1"></span>r + 1 >> 1;<span class="ff1"> </span></div><div class="t m0 x2 h4 ye ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (check(mid<span class="_ _1"></span>)) l = mid;<span class="ff1"> </span></div><div class="t m0 x2 h4 yf ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>else r = mid <span class="ff1">-</span> <span class="ls6">1;</span><span class="ff1"> </span></div><div class="t m0 x2 h4 y10 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">}<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y11 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">re<span class="_ _1"></span>turn l;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y12 ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y13 ff2 fs1 fc0 sc0 ls0 ws0">浮点数二分算法<span class="_ _1"></span>模板<span class="ff4"> <span class="_ _0"> </span></span><span class="ls4">——</span><span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _2"> </span>AcWing <span class="_ _1"></span>790. <span class="_ _0"> </span><span class="ff2">数的三次方根<span class="_ _1"></span><span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y33 ff4 fs1 fc0 sc0 ls0 ws0">bool check(doub<span class="_ _1"></span>le x) {/* ...<span class="_ _1"></span> */} // <span class="_ _2"> </span><span class="ff2 ls4">检查<span class="_ _0"> </span></span>x<span class="_ _0"> </span><span class="ff2">是否满足某种<span class="_ _1"></span>性质<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y15 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y16 ff4 fs1 fc0 sc0 ls0 ws0">double bsear<span class="_ _1"></span>ch_3<span class="_ _1"></span>(double l, doub<span class="_ _1"></span>le r)<span class="ff1"> </span></div><div class="t m0 x2 h4 y17 ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y34 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">cons<span class="_ _1"></span>t double e<span class="_ _1"></span>ps = 1e<span class="ff1">-</span>6; <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span>// eps <span class="_ _2"> </span><span class="ff2">表示精度，<span class="_ _1"></span>取决于题目对精<span class="_ _1"></span>度的要求<span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y19 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (r <span class="ff1">-<span class="_ _1"></span><span class="ff4"> l > eps)<span class="ff1"> </span></span></span></span></div><div class="t m0 x2 h4 y1a ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">{<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y1b ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>double mid = (l +<span class="_ _1"></span> r) / 2;<span class="ff1"> </span></div><div class="t m0 x2 h4 y1c ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (check(mid<span class="_ _1"></span>)) r = mid;<span class="ff1"> </span></div><div class="t m0 x2 h4 y1d ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>else l = mid;<span class="ff1"> </span></div><div class="t m0 x2 h4 y1e ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">}<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y1f ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">re<span class="_ _1"></span>turn l;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y20 ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y35 ff2 fs1 fc0 sc0 ls0 ws0">高精度加法<span class="ff4"> <span class="_ _0"> </span></span><span class="ls4">——</span><span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 791.<span class="_ _1"></span> <span class="_ _2"> </span><span class="ff2">高精度加法<span class="_ _1"></span><span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y22 ff4 fs1 fc0 sc0 ls0 ws0">// C = A + <span class="_ _1"></span>B, A >= 0,<span class="_ _1"></span> B >= 0<span class="ff1"> </span></div><div class="t m0 x2 h4 y23 ff4 fs1 fc0 sc0 ls0 ws0">vecto<span class="_ _1"></span>r<int> add<span class="_ _1"></span>(vecto<span class="_ _1"></span>r<int> <span class="_ _1"></span>&A, vector<span class="_ _1"></span><int> &B<span class="_ _1"></span>)<span class="ff1"> </span></div><div class="t m0 x2 h4 y24 ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y25 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">if (A.siz<span class="_ _1"></span>e() < B.siz<span class="_ _1"></span>e(<span class="_ _1"></span>)) ret<span class="_ _1"></span>urn add(B, <span class="_ _1"></span>A);<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y36 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y37 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">vect<span class="_ _1"></span>or<int<span class="_ _1"></span>> C;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y28 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">int t<span class="_ _1"></span> = 0;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y38 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">fo<span class="_ _1"></span>r (int i =<span class="_ _1"></span> 0; i < A.siz<span class="_ _1"></span>e(); i ++ )<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2a ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">{<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2b ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>t += A[i];<span class="ff1"> </span></div><div class="t m0 x2 h4 y2c ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (i < B.siz<span class="_ _1"></span>e()) t += B[i];<span class="_ _1"></span><span class="ff1"> </span></div><div class="t m0 x2 h4 y2d ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>C.push_back(t % 1<span class="_ _1"></span>0);<span class="ff1"> </span></div><div class="t m0 x2 h4 y2e ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>t /= 10;<span class="ff1"> </span></div><div class="t m0 x2 h4 y39 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">}<span class="ff1"> </span></span></div></div></div><div class="pi" data-data='{"ctm":[1.611792,0.000000,0.000000,1.611792,0.000000,0.000000]}'></div></div><div id="pf3" class="pf w0 h0" data-page-no="3"><div class="pc pc3 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90048609/bg3.jpg"><div class="c x0 y1 w2 h0"><div class="t m0 x1 h2 y2 ff1 fs0 fc0 sc0 ls0 ws0">3 </div><div class="t m0 x2 h2 y3 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y30 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y31 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">if (t) C.pus<span class="_ _1"></span>h_back(t);<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y6 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">re<span class="_ _1"></span>turn C;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y7 ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y32 ff2 fs1 fc0 sc0 ls0 ws0">高精度减法<span class="ff4"> <span class="_ _0"> </span></span><span class="ls4">——</span><span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 792.<span class="_ _1"></span> <span class="_ _2"> </span><span class="ff2">高精度减法<span class="_ _1"></span><span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y3a ff4 fs1 fc0 sc0 ls0 ws0">// C = A <span class="ff1">-</span> B<span class="_ _1"></span>, <span class="_ _2"> </span><span class="ff2 ls4">满足<span class="_ _0"> </span></span>A >= B,<span class="_ _1"></span> A >= 0, B <span class="_ _1"></span>>= 0<span class="ff1"> </span></div><div class="t m0 x2 h4 ya ff4 fs1 fc0 sc0 ls0 ws0">vecto<span class="_ _1"></span>r<int> sub(<span class="_ _1"></span>vect<span class="_ _1"></span>or<int> <span class="_ _1"></span>&A, vecto<span class="_ _1"></span>r<int> &B<span class="_ _1"></span>)<span class="ff1"> </span></div><div class="t m0 x2 h4 yb ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 yc ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">vect<span class="_ _1"></span>or<int<span class="_ _1"></span>> C;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yd ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">fo<span class="_ _1"></span>r (int i =<span class="_ _1"></span> 0, t = 0; i < A.<span class="_ _1"></span>size()<span class="_ _1"></span>; i ++ )<span class="ff1"> </span></span></div><div class="t m0 x2 h4 ye ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">{<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yf ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>t = A[i] <span class="ff1">-</span> <span class="ls7">t;</span><span class="ff1"> </span></div><div class="t m0 x2 h4 y10 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (i < B.siz<span class="_ _1"></span>e()) t <span class="ff1">-</span>= B[i];<span class="_ _1"></span><span class="ff1"> </span></div><div class="t m0 x2 h4 y11 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>C.push_back((t + <span class="_ _1"></span>10) % 10);<span class="ff1"> </span></div><div class="t m0 x2 h4 y12 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (t < 0) t = 1<span class="_ _1"></span>;<span class="ff1"> </span></div><div class="t m0 x2 h4 y3b ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>else t = 0;<span class="ff1"> </span></div><div class="t m0 x2 h4 y14 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">}<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y15 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y16 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (C.s<span class="_ _1"></span>ize<span class="_ _1"></span>() > 1 && C.<span class="_ _1"></span>back() == 0) C.pop_b<span class="_ _1"></span>ack();<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y17 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">re<span class="_ _1"></span>turn C;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y18 ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y3c ff2 fs1 fc0 sc0 ls0 ws0">高精度乘低精度<span class="_ _1"></span><span class="ff4"> <span class="_ _0"> </span><span class="ff2 ls4">——<span class="_ _3"></span></span> <span class="_ _2"> </span><span class="ff2">模板题</span> <span class="_ _0"> </span>AcWing 79<span class="_ _1"></span>3. <span class="_ _2"> </span><span class="ff2">高精度乘法<span class="_ _1"></span><span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y1a ff4 fs1 fc0 sc0 ls0 ws0">// C = A * b, <span class="_ _1"></span>A >= 0, b >= <span class="_ _1"></span>0<span class="ff1"> </span></div><div class="t m0 x2 h4 y1b ff4 fs1 fc0 sc0 ls0 ws0">vecto<span class="_ _1"></span>r<int> mul<span class="_ _1"></span>(vecto<span class="_ _1"></span>r<int> <span class="_ _1"></span>&A, int b)<span class="ff1"> </span></div><div class="t m0 x2 h4 y1c ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y1d ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">vect<span class="_ _1"></span>or<int<span class="_ _1"></span>> C;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y1e ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y1f ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">int t<span class="_ _1"></span> = 0;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y20 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">fo<span class="_ _1"></span>r (int i =<span class="_ _1"></span> 0; i < A.siz<span class="_ _1"></span>e() || t; i ++ )<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y21 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">{<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y22 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (i < A.siz<span class="_ _1"></span>e()) t += <span class="_ _1"></span>A[i] * b;<span class="ff1"> </span></div><div class="t m0 x2 h4 y23 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>C.push_back(t % 1<span class="_ _1"></span>0);<span class="ff1"> </span></div><div class="t m0 x2 h4 y24 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>t /= 10;<span class="ff1"> </span></div><div class="t m0 x2 h4 y25 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">}<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y36 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y37 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (C.s<span class="_ _1"></span>ize<span class="_ _1"></span>() > 1 && C.<span class="_ _1"></span>back() == 0) C.pop_b<span class="_ _1"></span>ack();<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y28 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y38 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">re<span class="_ _1"></span>turn C;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2a ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y3d ff2 fs1 fc0 sc0 ls0 ws0">高精度除以低精<span class="_ _1"></span>度<span class="ff4"> <span class="_ _0"> </span></span>——<span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 794. <span class="_"> </span></span>高精度除法<span class="ff1"> </span></div><div class="t m0 x2 h4 y2c ff4 fs1 fc0 sc0 ls3 ws0">// <span class="ls0">A / b = C ... r<span class="_ _4"></span>, A >= <span class="_ _1"></span>0, b > 0<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2d ff4 fs1 fc0 sc0 ls0 ws0">vecto<span class="_ _1"></span>r<int> di<span class="_ _1"></span>v(vecto<span class="_ _1"></span>r<int> <span class="_ _1"></span>&A, int b, int &<span class="_ _1"></span>r)<span class="ff1"> </span></div><div class="t m0 x2 h4 y2e ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y39 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">vect<span class="_ _1"></span>or<int<span class="_ _1"></span>> C;<span class="ff1"> </span></span></div></div></div><div class="pi" data-data='{"ctm":[1.611792,0.000000,0.000000,1.611792,0.000000,0.000000]}'></div></div><div id="pf4" class="pf w0 h0" data-page-no="4"><div class="pc pc4 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90048609/bg4.jpg"><div class="c x0 y1 w2 h0"><div class="t m0 x1 h2 y2 ff1 fs0 fc0 sc0 ls0 ws0">4 </div><div class="t m0 x2 h2 y3 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y30 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">r = 0;<span class="_ _1"></span><span class="ff1"> </span></span></div><div class="t m0 x2 h4 y31 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">fo<span class="_ _1"></span>r (int i =<span class="_ _1"></span> A.size(<span class="_ _1"></span>) <span class="ff1">-</span> 1; i >= 0; i <span class="ff1 ls2">--</span> <span class="_ _1"></span>)<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y6 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">{<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y7 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>r = r * 10 + A[i]<span class="_ _1"></span>;<span class="ff1"> </span></div><div class="t m0 x2 h4 y8 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>C.push_back(r / b<span class="_ _1"></span>);<span class="ff1"> </span></div><div class="t m0 x2 h4 y9 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>r %= b;<span class="ff1"> </span></div><div class="t m0 x2 h4 ya ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">}<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yb ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">re<span class="_ _1"></span>vers<span class="_ _1"></span>e(C.begin()<span class="_ _1"></span>, C.end());<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yc ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (C.s<span class="_ _1"></span>ize<span class="_ _1"></span>() > 1 && C.<span class="_ _1"></span>back() == 0) C.pop_b<span class="_ _1"></span>ack();<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yd ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">re<span class="_ _1"></span>turn C;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 ye ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y3e ff2 fs1 fc0 sc0 ls0 ws0">一维前缀和<span class="ff4"> <span class="_ _0"> </span></span><span class="ls4">——</span><span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 795.<span class="_ _1"></span> <span class="_ _2"> </span><span class="ff2">前缀和<span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y10 ff4 fs1 fc0 sc0 ls0 ws0">S[i] = a[1] <span class="_ _1"></span>+ a[2] + ... a[i]<span class="ff1"> </span></div><div class="t m0 x2 h4 y11 ff4 fs1 fc0 sc0 ls0 ws0">a[l] + ... + a[<span class="_ _1"></span>r] = S[r] <span class="ff1">-</span> S[l <span class="ff1">-</span> <span class="ls5">1]<span class="_ _1"></span><span class="ff1 ls0"> </span></span></div><div class="t m0 x2 h4 y3f ff2 fs1 fc0 sc0 ls0 ws0">二维前缀和<span class="ff4"> <span class="_ _0"> </span></span><span class="ls4">——</span><span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 796.<span class="_ _1"></span> <span class="_ _2"> </span><span class="ff2">子矩阵的和<span class="_ _1"></span><span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y13 ff4 fs1 fc0 sc0 ls0 ws0">S[i, j] = <span class="_ _0"> </span><span class="ff2">第<span class="_ _0"> </span></span>i<span class="_"> </span><span class="ff2">行<span class="_ _0"> </span></span>j<span class="_ _0"> </span><span class="ff2">列格子左上部分<span class="_ _1"></span>所有元素的和<span class="_ _1"></span><span class="ff1"> </span></span></div><div class="t m0 x2 h4 y33 ff2 fs1 fc0 sc0 ls0 ws0">以<span class="ff4">(x1, y1)</span>为<span class="_ _1"></span>左上角，<span class="ff4">(x2, y<span class="_ _1"></span>2)<span class="ff2">为右下角的子<span class="_ _1"></span>矩阵的和为<span class="_ _1"></span>：<span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y15 ff4 fs1 fc0 sc0 ls0 ws0">S[x2, y2] <span class="ff1">-</span> S[x<span class="_ _1"></span>1 <span class="ff1">-</span> 1, y2] <span class="ff1">-</span> S[x<span class="_ _1"></span>2, y1 <span class="ff1">-</span> 1] + S[x1 <span class="_ _1"></span><span class="ff1">-<span class="ff4"> 1, y1 </span>-<span class="ff4"> <span class="ls5">1]</span></span> </span></div><div class="t m0 x2 h4 y40 ff2 fs1 fc0 sc0 ls0 ws0">一维差分<span class="ff4"> <span class="_ _0"> </span></span>——<span class="ff4"> <span class="_ _0"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 797. <span class="_ _0"> </span></span>差分<span class="ff1"> </span></div><div class="t m0 x2 h4 y41 ff2 fs1 fc0 sc0 ls0 ws0">给区间<span class="ff4">[l, r]</span>中<span class="_ _1"></span>的每个数加<span class="_ _1"></span>上<span class="_ _0"> </span><span class="ff4">c</span>：<span class="ff4">B[l] += c, <span class="_ _1"></span>B[r + 1] <span class="ff1">-</span><span class="ls8">= c<span class="_ _1"></span><span class="ff1 ls0"> </span></span></span></div><div class="t m0 x2 h4 y34 ff2 fs1 fc0 sc0 ls0 ws0">二维差分<span class="ff4"> <span class="_ _0"> </span></span>——<span class="ff4"> <span class="_ _0"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 798. <span class="_ _0"> </span></span>差分矩阵<span class="ff1"> </span></div><div class="t m0 x2 h4 y3c ff2 fs1 fc0 sc0 ls0 ws0">给以<span class="ff4">(x1, y<span class="_ _1"></span>1)<span class="ff2">为左上角，</span>(x<span class="_ _1"></span>2, y2)<span class="ff2">为右下角的<span class="_ _1"></span>子矩阵中的<span class="_ _1"></span>所有元素加上<span class="_ _0"> </span><span class="ff4">c<span class="_ _1"></span><span class="ff2">：<span class="ff1"> </span></span></span></span></span></div><div class="t m0 x2 h4 y1a ff4 fs1 fc0 sc0 ls0 ws0">S[x1, y1] +=<span class="_ _1"></span> c, S[x2 + 1, y<span class="_ _1"></span>1] <span class="ff1">-</span>= c, S[x1, y2 <span class="_ _1"></span>+ 1] <span class="ff1">-</span>= c, S[x2 <span class="_ _1"></span>+ 1, y2 + 1] +<span class="_ _1"></span>= c<span class="ff1"> </span></div><div class="t m0 x2 h4 y42 ff2 fs1 fc0 sc0 ls0 ws0">位运算<span class="ff4"> <span class="_ _0"> </span></span><span class="ls4">——<span class="_ _3"></span></span><span class="ff4"> <span class="_ _0"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 801. <span class="_ _0"> </span></span>二进制中<span class="_ _0"> </span><span class="ff4">1<span class="_"> </span></span>的个数<span class="ff1"> </span></div><div class="t m0 x2 h4 y43 ff2 fs1 fc0 sc0 ls0 ws0">求<span class="_ _0"> </span><span class="ff4">n<span class="_"> </span></span><span class="ls4">的第<span class="_ _2"> </span></span><span class="ff4">k<span class="_"> </span></span>位数字<span class="ff4">: n >> k & 1<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y44 ff2 fs1 fc0 sc0 ls0 ws0">返回<span class="_ _0"> </span><span class="ff4">n<span class="_"> </span></span>的最后一位<span class="_ _0"> </span><span class="ff4">1</span>：<span class="ff4">lo<span class="_ _1"></span>wbit(n) = n<span class="_ _1"></span> & <span class="ff1">-</span>n<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y45 ff2 fs1 fc0 sc0 ls0 ws0">双指针算法<span class="ff4"> <span class="_ _0"> </span></span><span class="ls4">——</span><span class="ff4"> <span class="_ _2"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWIng <span class="_ _5"></span>799. <span class="_ _0"> </span></span>最长连续不重复子<span class="_ _1"></span>序列<span class="ff4">, <span class="_ _5"></span>AcWing <span class="_ _5"></span>800. <span class="_ _0"> </span></span>数组元素的目</div><div class="t m0 x2 h4 y46 ff2 fs1 fc0 sc0 ls0 ws0">标和<span class="ff1"> </span></div><div class="t m0 x2 h4 y20 ff4 fs1 fc0 sc0 ls0 ws0">fo<span class="_ _1"></span>r (int i = 0, j =<span class="_ _1"></span> 0; i < n; i ++ <span class="_ _1"></span>)<span class="ff1"> </span></div><div class="t m0 x2 h4 y21 ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y22 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (j < i && check<span class="_ _1"></span>(i, j)) j ++ ;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y23 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y47 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">// <span class="_ _0"> </span><span class="ff2">具体问题的逻辑<span class="_ _1"></span><span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y25 ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y26 ff2 fs1 fc0 sc0 ls0 ws0">常见问题分类：<span class="_ _1"></span><span class="ff1"> </span></div><div class="t m0 x2 h4 y27 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">(1) <span class="_ _0"> </span><span class="ff2">对于一个序列，<span class="_ _1"></span>用两个指针维<span class="_ _1"></span>护一段区间<span class="_ _1"></span><span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y48 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">(2) <span class="_ _0"> </span><span class="ff2">对于两个序列，<span class="_ _1"></span>维护某种次序<span class="_ _1"></span>，比如归并排<span class="_ _1"></span>序中合并两个有<span class="_ _1"></span>序序列的操作<span class="_ _1"></span><span class="ff1"> </span></span></span></div><div class="t m0 x2 h4 y29 ff2 fs1 fc0 sc0 ls0 ws0">离散化<span class="ff4"> <span class="_ _0"> </span></span><span class="ls4">——<span class="_ _3"></span></span><span class="ff4"> <span class="_ _0"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 802. <span class="_ _0"> </span></span>区间和<span class="ff1"> </span></div><div class="t m0 x2 h4 y49 ff4 fs1 fc0 sc0 ls0 ws0">vecto<span class="_ _1"></span>r<int> alls<span class="_ _1"></span>; // <span class="_ _0"> </span><span class="ff2">存储所有待离散化<span class="_ _1"></span>的值<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y3d ff4 fs1 fc0 sc0 ls0 ws0">sort(alls.b<span class="_ _1"></span>egin(), alls.end()<span class="_ _1"></span>); // <span class="_ _2"> </span><span class="ff2">将所有值排<span class="_ _1"></span>序<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y4a ff4 fs1 fc0 sc0 ls0 ws0">alls.er<span class="_ _1"></span>ase(unique(alls<span class="_ _1"></span>.begin(), al<span class="_ _1"></span>ls.end()), alls.end<span class="_ _1"></span>()); <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>// <span class="_ _0"> </span><span class="ff2">去掉重复元素<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2d ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y4b ff4 fs1 fc0 sc0 ls3 ws0">// <span class="_ _0"> </span><span class="ff2 ls0">二分求出<span class="_ _0"> </span><span class="ff4">x<span class="_ _0"> </span></span>对应的离散<span class="_ _1"></span>化的值<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2f ff4 fs1 fc0 sc0 ls0 ws0">int fin<span class="_ _1"></span>d(int x) // <span class="_ _0"> </span><span class="ff2">找到第一个大于<span class="_ _1"></span>等于<span class="_ _0"> </span><span class="ff4">x<span class="_"> </span></span>的位置<span class="ff1"> </span></span></div></div></div><div class="pi" data-data='{"ctm":[1.611792,0.000000,0.000000,1.611792,0.000000,0.000000]}'></div></div><div id="pf5" class="pf w0 h0" data-page-no="5"><div class="pc pc5 w0 h0"><img class="bi x0 y0 w1 h1" alt="" src="/image.php?url=https://csdnimg.cn/release/download_crawler_static/90048609/bg5.jpg"><div class="c x0 y1 w2 h0"><div class="t m0 x1 h2 y2 ff1 fs0 fc0 sc0 ls0 ws0">5 </div><div class="t m0 x2 h2 y3 ff1 fs0 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y30 ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y31 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">int l = <span class="_ _1"></span>0, r = alls.s<span class="_ _1"></span>ize() <span class="ff1">-</span> <span class="_ _1"></span><span class="ls5">1;<span class="ff1 ls0"> </span></span></span></div><div class="t m0 x2 h4 y6 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">while (l<span class="_ _1"></span> < r)<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y7 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">{<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y8 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>int mid = l + <span class="_ _1"></span>r >> 1;<span class="ff1"> </span></div><div class="t m0 x2 h4 y9 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (alls[mid] >= x<span class="_ _1"></span>) r = mid;<span class="ff1"> </span></div><div class="t m0 x2 h4 ya ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>else l = mid + 1<span class="_ _1"></span>;<span class="ff1"> </span></div><div class="t m0 x2 h4 yb ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">}<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y4c ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">re<span class="_ _1"></span>turn r + 1; // <span class="_"> </span><span class="ff2">映射到<span class="_ _0"> </span></span>1, 2, ...n<span class="ff1"> </span></span></div><div class="t m0 x2 h4 yd ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y4d ff2 fs1 fc0 sc0 ls0 ws0">区间合并<span class="ff4"> <span class="_ _0"> </span></span>——<span class="ff4"> <span class="_ _0"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 803. <span class="_ _0"> </span></span>区间合并<span class="ff1"> </span></div><div class="t m0 x2 h4 y3e ff4 fs1 fc0 sc0 ls3 ws0">// <span class="_ _0"> </span><span class="ff2 ls0">将所有存在交集的区<span class="_ _1"></span>间合并<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y10 ff4 fs1 fc0 sc0 ls0 ws0">void mer<span class="_ _1"></span>ge(v<span class="_ _1"></span>ecto<span class="_ _1"></span>r<PII> &seg<span class="_ _1"></span>s)<span class="ff1"> </span></div><div class="t m0 x2 h4 y11 ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y12 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">vect<span class="_ _1"></span>or<PII> r<span class="_ _1"></span>es;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y3b ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y14 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">sort(segs.b<span class="_ _1"></span>egin(), segs<span class="_ _1"></span>.end());<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y15 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y16 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">int s<span class="_ _1"></span>t = <span class="ff1">-</span>2e9, <span class="_ _1"></span>ed = <span class="ff1">-</span>2e9;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y17 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">fo<span class="_ _1"></span>r (auto seg<span class="_ _1"></span> : segs)<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y18 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (ed < seg.<span class="_ _1"></span>firs<span class="_ _1"></span>t)<span class="ff1"> </span></div><div class="t m0 x2 h4 y19 ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>{<span class="ff1"> </span></div><div class="t m0 x2 h4 y1a ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>if (st != <span class="ff1">-</span>2e9) <span class="_ _1"></span>res.push_back<span class="_ _1"></span>({st, <span class="_ _1"></span>ed});<span class="ff1"> </span></div><div class="t m0 x2 h4 y1b ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>st = seg.<span class="_ _1"></span>firs<span class="_ _1"></span>t, ed = s<span class="_ _1"></span>eg.second;<span class="_ _1"></span><span class="ff1"> </span></div><div class="t m0 x2 h4 y1c ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>}<span class="ff1"> </span></div><div class="t m0 x2 h4 y1d ff4 fs1 fc0 sc0 ls0 ws0"> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span> <span class="_ _0"> </span> <span class="_ _2"> </span> <span class="_ _2"> </span>else ed = max<span class="_ _1"></span>(ed, s<span class="_ _1"></span>eg.second);<span class="ff1"> </span></div><div class="t m0 x2 h4 y1e ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y1f ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">if (st<span class="_ _1"></span> != <span class="ff1">-</span>2e9) r<span class="_ _1"></span>es.push_back({s<span class="_ _1"></span>t, ed});<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y20 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y21 ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">segs = r<span class="_ _1"></span>es;<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y22 ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h3 y4e ff2 fs1 fc0 sc1 ls0 ws0">常用代码模板<span class="_ _0"> </span><span class="ff3 sc0">2</span>——数据结构<span class="ff1 sc0"> </span></div><div class="t m0 x2 h4 y47 ff2 fs1 fc0 sc0 ls0 ws0">单链表<span class="ff4"> <span class="_ _0"> </span></span><span class="ls4">——<span class="_ _3"></span></span><span class="ff4"> <span class="_ _0"> </span></span>模板题<span class="ff4"> <span class="_ _0"> </span>AcWing 826. <span class="_ _0"> </span></span>单链表<span class="ff1"> </span></div><div class="t m0 x2 h4 y4f ff4 fs1 fc0 sc0 ls0 ws0">// head<span class="_"> </span><span class="ff2">存储链表头，<span class="_ _6"></span><span class="ff4">e[]<span class="ff2">存储节点<span class="_ _1"></span>的值，<span class="_ _6"></span><span class="ff4">ne[]<span class="ff2">存储<span class="_ _1"></span>节点的<span class="_ _0"> </span><span class="ff4">next<span class="_"> </span></span>指针，<span class="_ _6"></span><span class="ff4 ls9">idx<span class="_"> </span><span class="ff2 ls0">表示当前用到了哪个</span></span></span></span></span></span></span></div><div class="t m0 x2 h4 y26 ff2 fs1 fc0 sc0 ls0 ws0">节点<span class="ff1"> </span></div><div class="t m0 x2 h4 y37 ff4 fs1 fc0 sc0 ls0 ws0">int head, e[<span class="_ _1"></span>N], ne[N], idx<span class="_ _1"></span>;<span class="ff1"> </span></div><div class="t m0 x2 h4 y28 ff1 fs1 fc0 sc0 ls0 ws0"> </div><div class="t m0 x2 h4 y29 ff4 fs1 fc0 sc0 ls3 ws0">// <span class="_ _0"> </span><span class="ff2 ls0">初始化<span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2a ff4 fs1 fc0 sc0 ls0 ws0">void init<span class="_ _1"></span>()<span class="ff1"> </span></div><div class="t m0 x2 h4 y2b ff4 fs1 fc0 sc0 ls0 ws0">{<span class="ff1"> </span></div><div class="t m0 x2 h4 y2c ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">head = <span class="ff1">-</span><span class="ls6">1;</span><span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2d ff4 fs1 fc0 sc0 ls1 ws0"> <span class="ls0">idx = 0;<span class="_ _1"></span><span class="ff1"> </span></span></div><div class="t m0 x2 h4 y2e ff4 fs1 fc0 sc0 ls0 ws0">}<span class="ff1"> </span></div><div class="t m0 x2 h4 y39 ff1 fs1 fc0 sc0 ls0 ws0"> </div></div></div><div class="pi" data-data='{"ctm":[1.611792,0.000000,0.000000,1.611792,0.000000,0.000000]}'></div></div>

100+评论昵称:

captcha

类型	标题	大小	时间
	山大ppt模板.zip	67.63MB	5月前

	付费自习室系统微信小程序+SSM毕业设计源码+数据库+论文+启动教程.zip	27.01MB	5月前
	基于MATLAB的车牌识别实现车牌定位技术实现【带界面GUI】.zip	71.63KB	5月前
	基于MATLAB的车牌识别实现车牌定位系统【GUI带界面】.zip	71.51KB	5月前
	C/C++ 语言参考,适合新手使用	115.3KB	5月前

	AI中控无人直播助手关键词+gpt回复+自动讲解	26.97MB	5月前
	123456789778	46.88KB	5月前
	上机指导与基础上机题(学生版).zip	1.96MB	5月前