-
Notifications
You must be signed in to change notification settings - Fork 2
/
index.html
1367 lines (924 loc) · 222 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="zh-TW">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.2.0">
<meta name="google-site-verification" content="KtMH6V68Z2PZJ6LKvSp5sqJFn7TxZp3dVQovd_wsgOI" />
<!-- Global site tag (gtag.js) - Google Analytics -->
<script async src="https://www.googletagmanager.com/gtag/js?id=UA-180989678-1"></script>
<script>
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'UA-180989678-1');
</script>
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
<script id="hexo-configurations">
var NexT = window.NexT || {};
var CONFIG = {"hostname":"emanlaicepsa.github.io","root":"/","scheme":"Gemini","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":true,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":false},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"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":"slideUpIn"}}};
</script>
<meta name="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
<meta property="og:type" content="website">
<meta property="og:title" content="從零開始的演算法競賽入門教學">
<meta property="og:url" content="https://emanlaicepsa.github.io/index.html">
<meta property="og:site_name" content="從零開始的演算法競賽入門教學">
<meta property="og:description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
<meta property="og:locale" content="zh_TW">
<meta property="article:author" content="emanlaicepsa">
<meta property="article:tag" content="演算法">
<meta property="article:tag" content="演算法競賽">
<meta property="article:tag" content="資訊奧林匹亞">
<meta property="article:tag" content="入門">
<meta property="article:tag" content="教學">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="https://emanlaicepsa.github.io/">
<script id="page-configurations">
// https://hexo.io/docs/variables.html
CONFIG.page = {
sidebar: "",
isHome : true,
isPost : false,
lang : 'zh-TW'
};
</script>
<title>從零開始的演算法競賽入門教學</title>
<script async src="https://www.googletagmanager.com/gtag/js?id=G-Z8B2VTRGNW"></script>
<script>
if (CONFIG.hostname === location.hostname) {
window.dataLayer = window.dataLayer || [];
function gtag(){dataLayer.push(arguments);}
gtag('js', new Date());
gtag('config', 'G-Z8B2VTRGNW');
}
</script>
<noscript>
<style>
.use-motion .brand,
.use-motion .menu-item,
.sidebar-inner,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-header { opacity: initial; }
.use-motion .site-title,
.use-motion .site-subtitle {
opacity: initial;
top: initial;
}
.use-motion .logo-line-before i { left: initial; }
.use-motion .logo-line-after i { right: initial; }
</style>
</noscript>
</head>
<body itemscope itemtype="http://schema.org/WebPage">
<div class="container use-motion">
<div class="headband"></div>
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切換導航欄">
<span class="toggle-line toggle-line-first"></span>
<span class="toggle-line toggle-line-middle"></span>
<span class="toggle-line toggle-line-last"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<h1 class="site-title">從零開始的演算法競賽入門教學</h1>
<span class="logo-line-after"><i></i></span>
</a>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger">
</div>
</div>
</div>
<nav class="site-nav">
<ul id="menu" class="main-menu menu">
<li class="menu-item menu-item-home">
<a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首頁</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>文章</a>
</li>
<li class="menu-item menu-item-從零到一：基礎語法">
<a href="/tags/%E5%BE%9E%E9%9B%B6%E5%88%B0%E4%B8%80/" rel="section"><i class="fa fa-tags fa-fw"></i>從零到一：基礎語法</a>
</li>
</ul>
</nav>
</div>
</header>
<div class="back-to-top">
<i class="fa fa-arrow-up"></i>
<span>0%</span>
</div>
<main class="main">
<div class="main-inner">
<div class="content-wrap">
<div class="content index posts-expand">
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-TW">
<link itemprop="mainEntityOfPage" href="https://emanlaicepsa.github.io/2020/10/19/overall/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="emanlaicepsa">
<meta itemprop="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="從零開始的演算法競賽入門教學">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/10/19/overall/" class="post-title-link" itemprop="url">從零開始的演算法競賽入門教學</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">發表於</span>
<time title="創建時間：2020-10-19 09:18:04" itemprop="dateCreated datePublished" datetime="2020-10-19T09:18:04+08:00">2020-10-19</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新於</span>
<time title="修改時間：2021-12-09 17:39:56" itemprop="dateModified" datetime="2021-12-09T17:39:56+08:00">2021-12-09</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="演算法競賽入門三階段"><a href="#演算法競賽入門三階段" class="headerlink" title="演算法競賽入門三階段"></a>演算法競賽入門三階段</h2><ol>
<li><h3 id="從零到一：演算法競賽會用到的基礎語法"><a href="#從零到一：演算法競賽會用到的基礎語法" class="headerlink" title="從零到一：演算法競賽會用到的基礎語法"></a><a href="2020/10/21/0-index/">從零到一：演算法競賽會用到的基礎語法</a></h3><ul>
<li>介紹競賽必定要會的語法，讓你不再困擾該學什麼!</li>
<li>對應程度：APCS 實作三級</li>
<li>預計學習時數：25 小時</li>
</ul>
</li>
<li><h3 id="從一到十：演算法競賽會用到的基礎算法"><a href="#從一到十：演算法競賽會用到的基礎算法" class="headerlink" title="從一到十：演算法競賽會用到的基礎算法"></a><a target="_blank" rel="noopener" href="https://drive.google.com/drive/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m">從一到十：演算法競賽會用到的基礎算法</a></h3><ul>
<li>AP325 講義 by 吳邦一教授</li>
<li>到底演算法競賽的演算法，指的是哪些呢?</li>
<li>對應程度：APCS 實作五級</li>
<li>預計學習時數：100 小時</li>
</ul>
</li>
<li><h3 id="十以後的世界：演算法競賽無止盡的追尋"><a href="#十以後的世界：演算法競賽無止盡的追尋" class="headerlink" title="十以後的世界：演算法競賽無止盡的追尋"></a><a target="_blank" rel="noopener" href="https://sites.google.com/site/pcshic/zi-xun-pei-xun">十以後的世界：演算法競賽無止盡的追尋</a></h3><ul>
<li>板中講義 by 蔡旻諺學長</li>
<li>什麼，你說上面你都學會了，你確定嗎?</li>
<li>對應程度：TOI 一階以上</li>
<li>預計學習時數：250 小時 up</li>
</ul>
</li>
</ol>
<h2 id="這邊會有什麼"><a href="#這邊會有什麼" class="headerlink" title="這邊會有什麼?"></a>這邊會有什麼?</h2><p>我幸運的拿到了 IOI(國際資訊奧林匹亞) 2020 的<a target="_blank" rel="noopener" href="http://stats.ioinformatics.org/people/7288">銀牌</a>，但在選訓營中，發現能進入選訓的高中生，大多都來自那些資訊社團發達的學校，如建中、實中、南一中、附中、成功等，在資訊社不活躍的學校，則幾乎沒有人進入奧林匹亞選訓營。回想起自己的學習過程，我認為關鍵在於新手入門難度。</p>
<p>包含 TOI(台灣資訊奧林匹亞) 在內的 OI 競賽入門門檻不低，於初期若沒有好的引導人(通常為高中資訊社團)，常會多走許多歪路，或者根本不知道應該要學什麼、什麼不必學，若買了一本 C++ 的書，然後一味的啃，會發現其實演算法競賽其實不需要對語法那麼熟悉。網路搜尋演算法競賽，第一本出現的書籍：打下好基礎：程式設計與演算法競賽入門經典，對新手來說也過於艱澀，且題目與台灣目前的命題趨勢並不相同。</p>
<p>這裡將會整理自己兩年來的演算法學習經驗，目標成為一本好懂、實用的演算法競賽書籍，期待能帶領更多年輕高中生，踏入這個正在台灣發展中的有趣領域！</p>
<p><strong>演算法競賽，重要的是思考，而不是過多不必要的語法</strong></p>
<h2 id="目標受眾"><a href="#目標受眾" class="headerlink" title="目標受眾"></a>目標受眾</h2><ul>
<li>完全沒寫過程式，但對數學有興趣，想嘗試演算法競賽</li>
<li>略有程式基礎，但不了解演算法競賽，或不知道競賽上有哪些常出現的演算法</li>
<li>非大校資訊社員，卻也想參加演算法競賽、進入全國賽以及選訓營</li>
</ul>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-TW">
<link itemprop="mainEntityOfPage" href="https://emanlaicepsa.github.io/2020/12/17/0-26/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="emanlaicepsa">
<meta itemprop="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="從零開始的演算法競賽入門教學">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/17/0-26/" class="post-title-link" itemprop="url">0-26 本章總結</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">發表於</span>
<time title="創建時間：2020-12-17 15:52:35" itemprop="dateCreated datePublished" datetime="2020-12-17T15:52:35+08:00">2020-12-17</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新於</span>
<time title="修改時間：2021-12-09 17:41:02" itemprop="dateModified" datetime="2021-12-09T17:41:02+08:00">2021-12-09</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="完結啦！"><a href="#完結啦！" class="headerlink" title="完結啦！"></a>完結啦！</h2><p>你已經學會了拿下 IOI 金牌所需要的所有語法了！是不是很簡單呢？</p>
<p>不知道看到例題的感想，是覺得超級簡單、或是難到完全想不到、或是剛剛好呢？</p>
<p>在後段的 STL 章節裡，我增加了例題的難度，四星的題目約是全國賽門檻等級，也就是說，如果你能不依靠詳解解出四星的題目，而你又幸運的不住台北，那你可能已經有參與全國賽的實力了喔！</p>
<p>五星以上的題目們，就真的非常難了。其中在 set 中一題被我標為 8 顆星的<strong>直升機抓寶</strong>，雖然程式只有十餘行，不過這題在當年的全國賽上，可是只有五個人解出來的大難題呢！</p>
<p>當然，如果你是初學者，寫不出太難的題目不用灰心。擺放高級題目的目的，僅僅是在說明，只需要如此簡單的語法，就能解決這麼多問題而已，對於初學者而言，能了解教學中的概念，並寫出三顆星以下的題目，就算是相當不錯的了！</p>
<h2 id="接下來"><a href="#接下來" class="headerlink" title="接下來"></a>接下來</h2><p>你已經有了基礎的知識，可能也對於演算法有了初步的了解，之後要做什麼呢？</p>
<p>參加一場 <a target="_blank" rel="noopener" href="https://codeforces.com/">Codeforces</a> Div.3 或者是 <a target="_blank" rel="noopener" href="https://atcoder.jp/home">AtCoder</a> 的 Beginner Contest 吧！如果可以，請試著在結束後查看出題者提供的題解。</p>
<p>也可以試著參加一場免費的 APCS 考試，反正免費，考爛了也不虧。</p>
<p>可以去刷一些題目，檢驗自己的學習成果。如果不知道從何寫起，可以參考一下 <a target="_blank" rel="noopener" href="https://toj.tfcis.org/oj/info/">TOJ</a> 上的高一生程式競技排名賽歷屆試題。</p>
<p>如果覺得簡單的話，恭喜你，你已經能挑戰下一階段的 AP325 了!</p>
<p>礙於時間關係(大學真的太忙了)，以及之後的教學已有完善資源，我的教學就在這裡畫上句號，希望讀完這份講義的你能有所收穫！</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-TW">
<link itemprop="mainEntityOfPage" href="https://emanlaicepsa.github.io/2020/12/14/0-25/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="emanlaicepsa">
<meta itemprop="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="從零開始的演算法競賽入門教學">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/14/0-25/" class="post-title-link" itemprop="url">0-25 bitset</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">發表於</span>
<time title="創建時間：2020-12-14 13:13:58 / 修改時間：14:43:30" itemprop="dateCreated datePublished" datetime="2020-12-14T13:13:58+08:00">2020-12-14</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="bool-陣列"><a href="#bool-陣列" class="headerlink" title="bool 陣列"></a>bool 陣列</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">bool</span> arr[<span class="number">1000005</span>];</span><br></pre></td></tr></table></figure>
<h2 id="bitset"><a href="#bitset" class="headerlink" title="bitset"></a>bitset</h2><p>bitset 是特別優化過的 bool 陣列，時間與空間均較 bool 陣列少，其中以時間的影響最為顯著。</p>
<p>bitset 的語法如下：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">bitset</span><1000005> b;</span><br></pre></td></tr></table></figure>
<p>特別的地方是，<> 內放的是大小。</p>
<h2 id="語法"><a href="#語法" class="headerlink" title="語法"></a>語法</h2><p>跟 bool 陣列一樣</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">b[<span class="number">5</span>] = <span class="number">0</span>;</span><br><span class="line">b[<span class="number">4</span>] = <span class="number">1</span>;</span><br></pre></td></tr></table></figure>
<p>有一些特別的函式</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">cout</span> << b.count() << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>.count() 回傳 bitset 中 1 的個數。</p>
<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><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line">b.<span class="built_in">set</span>();</span><br><span class="line"><span class="built_in">cout</span> << b[<span class="number">1</span>] << <span class="string">'\n'</span>;</span><br><span class="line">b.reset();</span><br><span class="line"><span class="built_in">cout</span> << b[<span class="number">1</span>] << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>.set() 將所有 bit 設為 1，.reset() 將所有 bit 設為 0。</p>
<h2 id="比-bool-陣列快的地方"><a href="#比-bool-陣列快的地方" class="headerlink" title="比 bool 陣列快的地方"></a>比 bool 陣列快的地方</h2><p>bitset 可以進行位元運算！</p>
<p>位元運算的速度極快，大約可視為正常的 1/32 倍。因此 bitset 能做到一些沒有其他方法能做到的神奇事情。</p>
<p>但… 這些事情超少的，我也只在比賽中看過一題，然而就是那一題，讓我進了二階。那題稍微有點難，可能放在這不太適合，就先放其他題目吧！</p>
<p><a target="_blank" rel="noopener" href="https://toj.tfcis.org/oj/pro/126/">TOJ 126</a></p>
<p>這題的重點是，要如何知道一個數是不是合理的。</p>
<p>假設現在合理的分數是(-2, -1, 0, 1, 2)，有一題 2 分的題目，那麼在作答完這題後，可能的分數就是這題答對與這題答錯的聯集。</p>
<p>這題答對的話，可能的分數會變成(0, 1, 2, 3, 4)，答錯的話，可能的分數會變成(-4, -3, -2, -1, 0)，所以考慮答對跟答錯的情況，可能的分數是兩者的聯集，也就是(-4, -3, -2, -1, 0, 1, 2, 3, 4)。</p>
<p>假設把可不可能用 bitset 表示，bitset 中若第 i 項是 1，表示 i 是可能的分數，反之 0 是不可能，那麼，若原來的 bitset 是 b，答了一題分數為 2 的題目後，這個 bitset 就會變成 (b >> 2) | (b << 2)。</p>
<p>b >> 2 表示答錯的狀況，可能的分數右移兩格(-2, -1, 0, 1, 2) -> (-4, -3, -2, -1, 0)， b << 2 表示答對的狀況，可能的分數左移兩格(-2, -1, 0, 1, 2) -> (0, 1, 2, 3, 4)。| 將兩者聯集起來。這樣的話，本來需要 N 次的操作，在 bitset 的使用下，變成只需要 N / 32 次了！</p>
<p>在位元運算時，bitset也不用擔心會 RE，超過的部分都會自動捨去，沒有問題！(但是可能會WA就是了)</p>
<p>另外，這題其實是一題經典問題：背包(knapsack)問題的一種變形，有興趣的話可以針對這個主題進行學習。之後應該也會有一篇專門的文章來介紹我所知道的背包問題們。</p>
<p>bitset 的使用時機非常少，但無可替代。</p>
<h2 id="練習"><a href="#練習" class="headerlink" title="練習"></a>練習</h2><p><a target="_blank" rel="noopener" href="https://toj.tfcis.org/oj/pro/126/">TOJ 126</a></p>
<p><a target="_blank" rel="noopener" href="https://www.hackerrank.com/contests/accel-hack/challenges/acyclic-graph">Hackerrank Acyclic Graph</a></p>
<h2 id="AC-Code"><a href="#AC-Code" class="headerlink" title="AC Code"></a>AC Code</h2><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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TOJ 126</span></span><br><span class="line"><span class="comment">// 因為index沒有負數，因此全部加上 10000 處理。</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n, q, ans[<span class="number">20005</span>];</span><br><span class="line"><span class="built_in">bitset</span><20005> b;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n >> q;</span><br><span class="line"> b[<span class="number">10000</span>] = <span class="number">1</span>; <span class="comment">// b[0] = 1</span></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,x;i<=n;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> x;</span><br><span class="line"> b = (b >> x) | (b << x);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">20000</span>,pre=i;i>=<span class="number">0</span>;i--){</span><br><span class="line"> <span class="keyword">if</span>(b[i]) pre = i;</span><br><span class="line"> ans[i] = pre;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,x;i<=q;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> x;</span><br><span class="line"> <span class="built_in">cout</span> << ans[x+<span class="number">10000</span>] - <span class="number">10000</span> << <span class="string">'\n'</span>; <span class="comment">// cout << ans[x] << '\n';</span></span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// Acyclic graph</span></span><br><span class="line"><span class="comment">// 建議先了解 dfs 與 vector 存圖 以及 DAG</span></span><br><span class="line"><span class="comment">// 先備知識有點多 可以跳過 之後再回來</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="built_in">bitset</span><50005> b[<span class="number">50005</span>], vis;</span><br><span class="line"><span class="keyword">int</span> n, m, in[<span class="number">50005</span>];</span><br><span class="line"><span class="built_in">vector</span><<span class="keyword">int</span>> E[<span class="number">50005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> x)</span></span>{</span><br><span class="line"> vis[x] = <span class="number">1</span>;</span><br><span class="line"> b[x][x] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">auto</span> i:E[x]){</span><br><span class="line"> <span class="keyword">if</span>(!vis[i]) dfs(i);</span><br><span class="line"> b[x] |= b[i];</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,a,b;i<=m;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> a >> b;</span><br><span class="line"> E[a].emplace_back(b);</span><br><span class="line"> in[b]++;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++){</span><br><span class="line"> <span class="keyword">if</span>(!in[i]) dfs(i);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> ans = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++){</span><br><span class="line"> <span class="keyword">if</span>(b[i].count()*<span class="number">2</span>>=n) ans++;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << ans << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-TW">
<link itemprop="mainEntityOfPage" href="https://emanlaicepsa.github.io/2020/12/14/0-24/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="emanlaicepsa">
<meta itemprop="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="從零開始的演算法競賽入門教學">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/14/0-24/" class="post-title-link" itemprop="url">0-24 linked-list</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">發表於</span>
<time title="創建時間：2020-12-14 10:48:54 / 修改時間：13:26:43" itemprop="dateCreated datePublished" datetime="2020-12-14T10:48:54+08:00">2020-12-14</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="從中間刪除？"><a href="#從中間刪除？" class="headerlink" title="從中間刪除？"></a>從中間刪除？</h2><p>如果我要刪除陣列最前最後的元素，可以用 deque 解決。</p>
<p>那，如果我今天要刪除陣列中間某個元素，或是在陣列中間插入某個元素，該怎麼做呢？</p>
<p>我們可以紀錄一個點的前、後方是誰，這樣的話，假設現在是1 -> 2 -> 3，如果我要刪除 2，我只要將 1 的後方指向 3、3 的前方指向 1，就能夠在 $O(1)$ 時間內完成刪除動作。</p>
<h2 id="缺點"><a href="#缺點" class="headerlink" title="缺點"></a>缺點</h2><p>無法隨機存取，也就是說，無法快速知道當前的第 k 項是誰。只能知道頭、尾。</p>
<p>即使刪除一個元素只需要 $O(1)$，但是光是找到那個元素就要花 $O(N)$ 了啊。我要刪掉 2，但我不知道 2 在裡面的位置在哪裡，於是我只好從頭一個一個開始找，直到我找到 2，這也是非常慢的做法。</p>
<p>因此，linked-list 不太常被使用，雖然 STL 有 list 這個結構，但我還沒用過它。</p>
<h2 id="唯一的用處"><a href="#唯一的用處" class="headerlink" title="唯一的用處"></a>唯一的用處</h2><p>來看看這題：</p>
<p><a target="_blank" rel="noopener" href="https://zerojudge.tw/ShowProblem?problemid=b938">ZJ 938</a></p>
<p>很明顯的，需要利用 linked-list 的概念來解決，只需要很簡單的刪除一個人後面的人就好。</p>
<p>那這題的瓶頸就在於，要如何維護一個人後面的人是誰。</p>
<p>一開始，每個人的後面都是自己的編號 + 1，當我刪除 1 後面的數 2 時，1 的後面就變成了原本 2 的後面 3，而其他人後面的數都不會被改變。</p>
<figure class="highlight plain"><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">1 -> 2 -> 3 -> 4</span><br><span class="line">1 -> X -> 3 -> 4 (2被殺)</span><br><span class="line">1 ------> 3 -> 4 (1後面的人變成了原來2後面的人：3)</span><br></pre></td></tr></table></figure>
<p>所以，我們開個陣列紀錄每個人現在後面是誰就好啦！完全不需要 STL 的 list 呢！事實上，list 根本沒有辦法做這題，因為找到一個人的位置需要 $O(N)$。</p>
<h2 id="練習"><a href="#練習" class="headerlink" title="練習"></a>練習</h2><p><a target="_blank" rel="noopener" href="https://zerojudge.tw/ShowProblem?problemid=b938">ZJ b938</a></p>
<p><a target="_blank" rel="noopener" href="https://zerojudge.tw/ShowProblem?problemid=d718">ZJ d718</a></p>
<p>★★★★ <a target="_blank" rel="noopener" href="https://tioj.ck.tp.edu.tw/problems/1225">TIOJ 1225</a></p>
<p>★★★★ <a target="_blank" rel="noopener" href="https://tioj.ck.tp.edu.tw/problems/1225">TIOJ 1930</a></p>
<h2 id="AC-Code"><a href="#AC-Code" class="headerlink" title="AC Code"></a>AC Code</h2><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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// ZJ b938</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n, m;</span><br><span class="line"><span class="keyword">int</span> nxt[<span class="number">1000005</span>], dead[<span class="number">1000005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) nxt[i] = i+<span class="number">1</span>;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,x;i<=m;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> x;</span><br><span class="line"> <span class="keyword">if</span>(dead[x] || nxt[x] == n+<span class="number">1</span>){</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"0u0 ...... ?\n"</span>;</span><br><span class="line"> <span class="keyword">continue</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << nxt[x] << <span class="string">'\n'</span>;</span><br><span class="line"> dead[nxt[x]] = <span class="number">1</span>;</span><br><span class="line"> nxt[x] = nxt[nxt[x]];</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// ZJ d718</span></span><br><span class="line"><span class="comment">// 將沒有組別的人的編號設為 x + 10000，以避免與組混淆</span></span><br><span class="line"><span class="comment">// 題目沒說清楚，沒有組的人也有可能入列，例如範測 1 的 8</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line">ll n, team[<span class="number">1000005</span>];</span><br><span class="line"><span class="keyword">bool</span> inq[<span class="number">10005</span>];</span><br><span class="line"><span class="built_in">queue</span><ll> q;</span><br><span class="line"><span class="built_in">queue</span><ll> cur[<span class="number">10005</span>];</span><br><span class="line"><span class="built_in">string</span> s;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span></span>{</span><br><span class="line"> fill(inq, inq+<span class="number">10001</span>, <span class="number">0</span>);</span><br><span class="line"> fill(team, team+<span class="number">1000001</span>, <span class="number">0</span>);</span><br><span class="line"> <span class="keyword">while</span>(!q.empty()) q.pop();</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=<span class="number">10000</span>;i++) <span class="keyword">while</span>(!cur[i].empty()) cur[i].pop();</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,x;i<=n;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> x;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>,y;j<=x;j++){</span><br><span class="line"> <span class="built_in">cin</span> >> y;</span><br><span class="line"> team[y] = i;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span>(<span class="number">1</span>){</span><br><span class="line"> <span class="built_in">cin</span> >> s;</span><br><span class="line"> <span class="keyword">if</span>(s[<span class="number">0</span>] == <span class="string">'E'</span>){</span><br><span class="line"> <span class="keyword">int</span> x;</span><br><span class="line"> <span class="built_in">cin</span> >> x;</span><br><span class="line"> <span class="keyword">if</span>(x > <span class="number">1000000</span> || team[x] == <span class="number">0</span>){</span><br><span class="line"> q.push(<span class="number">10000</span>+x);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">if</span>(!inq[team[x]]) q.push(team[x]), inq[team[x]] = <span class="number">1</span>;</span><br><span class="line"> cur[team[x]].push(x);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span>(s[<span class="number">0</span>] == <span class="string">'D'</span>){</span><br><span class="line"> <span class="keyword">if</span>(q.front() >= <span class="number">10000</span>){</span><br><span class="line"> <span class="built_in">cout</span> << q.front() - <span class="number">10000</span> << <span class="string">'\n'</span>;</span><br><span class="line"> q.pop();</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> <span class="built_in">cout</span> << cur[q.front()].front() << <span class="string">'\n'</span>;</span><br><span class="line"> cur[q.front()].pop();</span><br><span class="line"> <span class="keyword">if</span>(cur[q.front()].empty()){</span><br><span class="line"> inq[q.front()] = <span class="number">0</span>;</span><br><span class="line"> q.pop();</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">int</span> t = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span>(<span class="built_in">cin</span> >> n){</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">"Line #"</span> << ++t << <span class="string">'\n'</span>;</span><br><span class="line"> solve();</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TIOJ 1225</span></span><br><span class="line"><span class="comment">// 由小到大刪除元素</span></span><br><span class="line"><span class="comment">// 會使得結果變差的原因是，明明 b 能消掉 a，但 b 卻在 a 前就被消掉了。</span></span><br><span class="line"><span class="comment">// 為了不發生上述狀況，只要由小到大刪除元素就沒問題啦！</span></span><br><span class="line"><span class="comment">// 這題有 stack 的解，複雜度相同，但較好寫，可以試試想看看。</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pii pair<span class="meta-string"><ll, ll></span></span></span><br><span class="line"></span><br><span class="line">ll n, arr[<span class="number">1000005</span>], fr[<span class="number">1000005</span>], bk[<span class="number">1000005</span>];</span><br><span class="line"></span><br><span class="line"><span class="built_in">vector</span><pii> v;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) <span class="built_in">cin</span> >> arr[i], fr[i] = i<span class="number">-1</span>, bk[i] = i+<span class="number">1</span>;</span><br><span class="line"> fr[n+<span class="number">1</span>] = n;</span><br><span class="line"> bk[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"> arr[<span class="number">0</span>] = arr[n+<span class="number">1</span>] = <span class="number">1e12</span>;</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) v.emplace_back(arr[i], i);</span><br><span class="line"> sort(v.begin(), v.end());</span><br><span class="line"> </span><br><span class="line"> ll ans = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<n<span class="number">-1</span>;i++){</span><br><span class="line"> <span class="keyword">int</span> idx = v[i].second;</span><br><span class="line"> <span class="keyword">if</span>(arr[fr[idx]] > arr[bk[idx]]) ans += arr[bk[idx]];</span><br><span class="line"> <span class="keyword">else</span> ans += arr[fr[idx]];</span><br><span class="line"></span><br><span class="line"> bk[fr[idx]] = bk[idx];</span><br><span class="line"> fr[bk[idx]] = fr[idx];</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="built_in">cout</span> << ans << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TIOJ 1930</span></span><br><span class="line"><span class="comment">// 麻煩的實作題，好好維護前面跟後面是誰</span></span><br><span class="line"><span class="comment">// 為什麼distribute操作不會 TLE 呢？</span></span><br><span class="line"><span class="comment">// 因為總共可能離開隊伍的人數 = 進入隊伍的人數 = N</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n, m, a1, fr[<span class="number">2000005</span>], bk[<span class="number">2000005</span>]; </span><br><span class="line"></span><br><span class="line">ll dump;</span><br><span class="line"><span class="built_in">vector</span><<span class="keyword">int</span>> ans;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insert</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b, <span class="keyword">int</span> c)</span></span>{</span><br><span class="line"> <span class="keyword">if</span>(c == <span class="number">1</span>){</span><br><span class="line"> bk[fr[b]] = a;</span><br><span class="line"> fr[a] = fr[b];</span><br><span class="line"> fr[b] = a;</span><br><span class="line"> bk[a] = b;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> fr[bk[b]] = a;</span><br><span class="line"> bk[a] = bk[b];</span><br><span class="line"> bk[b] = a;</span><br><span class="line"> fr[a] = b;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">rebuild</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b, <span class="keyword">int</span> c)</span></span>{</span><br><span class="line"> bk[fr[a]] = bk[b];</span><br><span class="line"> fr[bk[b]] = fr[a];</span><br><span class="line"> </span><br><span class="line"> bk[fr[c]] = a;</span><br><span class="line"> fr[a] = fr[c];</span><br><span class="line"> fr[c] = b;</span><br><span class="line"> bk[b] = c;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">distribute</span><span class="params">(<span class="keyword">int</span> a, ll b, <span class="keyword">int</span> c)</span></span>{</span><br><span class="line"> <span class="keyword">if</span>(c == <span class="number">1</span>){</span><br><span class="line"> <span class="keyword">int</span> now = a;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=b;i++){</span><br><span class="line"> <span class="keyword">if</span>(now == <span class="number">0</span>){</span><br><span class="line"> dump += b-i+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> ans.emplace_back(now);</span><br><span class="line"> bk[fr[now]] = bk[now];</span><br><span class="line"> fr[bk[now]] = fr[now];</span><br><span class="line"> now = fr[now];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">int</span> now = a;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=b;i++){</span><br><span class="line"> <span class="keyword">if</span>(now == n+<span class="number">1</span>){</span><br><span class="line"> dump += b-i+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> ans.emplace_back(now);</span><br><span class="line"> bk[fr[now]] = bk[now];</span><br><span class="line"> fr[bk[now]] = fr[now];</span><br><span class="line"> now = bk[now];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span></span>{</span><br><span class="line"> dump = <span class="number">0</span>;</span><br><span class="line"> ans.clear();</span><br><span class="line"> fill(fr, fr+<span class="number">2000005</span>, <span class="number">0</span>);</span><br><span class="line"> fill(bk, bk+<span class="number">2000005</span>, <span class="number">0</span>);</span><br><span class="line"></span><br><span class="line"> <span class="built_in">cin</span> >> n >> m >> a1;</span><br><span class="line"> bk[<span class="number">0</span>] = a1, bk[a1] = n+<span class="number">1</span>, fr[a1] = <span class="number">0</span>, fr[n+<span class="number">1</span>] = a1;</span><br><span class="line"> </span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,k,a,b,c;i<=m;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> k >> a >> b >> c;</span><br><span class="line"> <span class="keyword">if</span>(k == <span class="number">1</span>) insert(a, b, c);</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span>(k == <span class="number">2</span>) rebuild(a, b, c);</span><br><span class="line"> <span class="keyword">else</span> distribute(a, b, c);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << dump << <span class="string">'\n'</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">auto</span> i:ans) <span class="built_in">cout</span> << i << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">int</span> t; <span class="built_in">cin</span> >> t;</span><br><span class="line"> <span class="keyword">while</span>(t--) solve();</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-TW">
<link itemprop="mainEntityOfPage" href="https://emanlaicepsa.github.io/2020/12/14/0-23/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="emanlaicepsa">
<meta itemprop="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="從零開始的演算法競賽入門教學">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/14/0-23/" class="post-title-link" itemprop="url">0-23 deque</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">發表於</span>
<time title="創建時間：2020-12-14 08:42:18 / 修改時間：10:27:19" itemprop="dateCreated datePublished" datetime="2020-12-14T08:42:18+08:00">2020-12-14</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="有-stack，有-queue"><a href="#有-stack，有-queue" class="headerlink" title="有 stack，有 queue"></a>有 stack，有 queue</h2><p>那理論上，應該要有一個 STL，同時具有 stack 跟 queue 的功能啊？</p>
<p>也就是說，要可以從前面跟後面拿東西、刪東西。</p>
<p>先介紹這個比較厲害的！</p>
<p>它不只可以從前面跟後面拿東西、刪東西，還可以隨時知道第 k 項是什麼！</p>
<p>也就是說，它其實更像是可以從前方插入移除的 vector。</p>
<h2 id="語法"><a href="#語法" class="headerlink" title="語法"></a>語法</h2><p>宣告：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">deque</span><<span class="keyword">int</span>> dq;</span><br></pre></td></tr></table></figure>
<p>加入元素：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">dq.push_back(<span class="number">1</span>);</span><br><span class="line">dq.push_front(<span class="number">5</span>);</span><br></pre></td></tr></table></figure>
<p>刪除元素：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">dq.pop_back();</span><br><span class="line">dq.pop_front();</span><br></pre></td></tr></table></figure>
<p>此外，由於支援隨機存取，因此如 sort、lower_bound 等在 vector 可以用的函式，在 deque 中當然也可以用！</p>
<h2 id="缺點"><a href="#缺點" class="headerlink" title="缺點"></a>缺點</h2><p>慢。</p>
<p>雖然各操作仍是 $O(1)$，但大約比 vector 慢 3 倍。</p>
<p>沒事不會用到它，沒事不要用到它。</p>
<p>對了，stack 跟 queue 其實是基於 deque 上的結構，也就是說，當你以為你在用 stack，其實程式幫你宣告的是 deque，即使你並不需要那些 deque 的功能。</p>
<p>因此，stack 跟 queue 跟 deque 一樣慢。</p>
<h2 id="練習"><a href="#練習" class="headerlink" title="練習"></a>練習</h2><p>★★★★<a target="_blank" rel="noopener" href="https://tioj.ck.tp.edu.tw/problems/1618">TIOJ 1618</a></p>
<p>★★★★<a target="_blank" rel="noopener" href="https://tioj.ck.tp.edu.tw/problems/1566">TIOJ 1566</a></p>
<h2 id="AC-Code"><a href="#AC-Code" class="headerlink" title="AC Code"></a>AC Code</h2><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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TIOJ 1618</span></span><br><span class="line"><span class="comment">// 搜尋 單調隊列</span></span><br><span class="line"><span class="comment">// 在任何時刻能看到的大樓，其高度必定由左往右遞減</span></span><br><span class="line"><span class="comment">// 用pop_front維護視力、pop_back維護高度遞減</span></span><br><span class="line"><span class="comment">// 可參考https://koios1143.github.io/2020/09/12/TOJ169/</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pii pair<span class="meta-string"><ll,ll></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line">ll n, k, h[<span class="number">500005</span>], b[<span class="number">500005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n >> k;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) <span class="built_in">cin</span> >> h[i];</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) <span class="built_in">cin</span> >> b[i];</span><br><span class="line"> </span><br><span class="line"> <span class="built_in">deque</span><pii> dq;</span><br><span class="line"> ll cur = <span class="number">0</span>, ans = <span class="number">-1e18</span>, ansid = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(ll i=<span class="number">1</span>;i<=n;i++){</span><br><span class="line"> <span class="keyword">while</span>(!dq.empty() && dq[<span class="number">0</span>].first <= i-k){</span><br><span class="line"> cur -= b[dq[<span class="number">0</span>].first];</span><br><span class="line"> dq.pop_front();</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span>(!dq.empty() && dq[dq.size()<span class="number">-1</span>].second <= h[i]){</span><br><span class="line"> cur -= b[dq[dq.size()<span class="number">-1</span>].first];</span><br><span class="line"> dq.pop_back();</span><br><span class="line"> }</span><br><span class="line"> cur += b[i];</span><br><span class="line"> dq.emplace_back(i, h[i]);</span><br><span class="line"> <span class="keyword">if</span>(cur > ans){</span><br><span class="line"> ans = cur;</span><br><span class="line"> ansid = i;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="built_in">cout</span> << ansid << <span class="string">" "</span> << ans << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TIOJ 1566</span></span><br><span class="line"><span class="comment">// 搜尋 單調隊列</span></span><br><span class="line"><span class="comment">// 維護區間最大值與最小值</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pii pair<span class="meta-string"><ll,ll></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line">ll n, m, k, h[<span class="number">10000005</span>];</span><br><span class="line"><span class="built_in">deque</span><pii> mx, mn;</span><br><span class="line"><span class="built_in">vector</span><pii> ans;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m >> k;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) <span class="built_in">cin</span> >> h[i];</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++){</span><br><span class="line"> <span class="keyword">while</span>(!mx.empty() && mx[<span class="number">0</span>].first <= i-m) mx.pop_front();</span><br><span class="line"> <span class="keyword">while</span>(!mn.empty() && mn[<span class="number">0</span>].first <= i-m) mn.pop_front();</span><br><span class="line"> <span class="keyword">while</span>(!mx.empty() && mx[mx.size()<span class="number">-1</span>].second <= h[i]) mx.pop_back();</span><br><span class="line"> <span class="keyword">while</span>(!mn.empty() && mn[mn.size()<span class="number">-1</span>].second >= h[i]) mn.pop_back();</span><br><span class="line"> mx.emplace_back(i, h[i]);</span><br><span class="line"> mn.emplace_back(i, h[i]);</span><br><span class="line"> <span class="keyword">if</span>(mx[<span class="number">0</span>].second - mn[<span class="number">0</span>].second == k){</span><br><span class="line"> <span class="keyword">if</span>(i <= m) ans.emplace_back(<span class="number">1</span>, i);</span><br><span class="line"> <span class="keyword">else</span> ans.emplace_back(i-m+<span class="number">1</span>, i);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=n+<span class="number">1</span>;i<n+m;i++){</span><br><span class="line"> <span class="keyword">while</span>(!mx.empty() && mx[<span class="number">0</span>].first <= i-m) mx.pop_front();</span><br><span class="line"> <span class="keyword">while</span>(!mn.empty() && mn[<span class="number">0</span>].first <= i-m) mn.pop_front();</span><br><span class="line"> <span class="keyword">if</span>(mx[<span class="number">0</span>].second - mn[<span class="number">0</span>].second == k){</span><br><span class="line"> <span class="keyword">if</span>(i-m > <span class="number">0</span>) ans.emplace_back(i-m+<span class="number">1</span>, n);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="built_in">cout</span> << ans.size() << <span class="string">'\n'</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">auto</span> i:ans){</span><br><span class="line"> <span class="built_in">cout</span> << i.first << <span class="string">" "</span> << i.second << <span class="string">'\n'</span>;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-TW">
<link itemprop="mainEntityOfPage" href="https://emanlaicepsa.github.io/2020/12/10/0-22/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="emanlaicepsa">
<meta itemprop="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="從零開始的演算法競賽入門教學">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/10/0-22/" class="post-title-link" itemprop="url">0-22 priority_queue</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">發表於</span>
<time title="創建時間：2020-12-10 13:57:09" itemprop="dateCreated datePublished" datetime="2020-12-10T13:57:09+08:00">2020-12-10</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新於</span>
<time title="修改時間：2020-12-14 09:45:21" itemprop="dateModified" datetime="2020-12-14T09:45:21+08:00">2020-12-14</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="堆-heap"><a href="#堆-heap" class="headerlink" title="堆(heap)"></a>堆(heap)</h2><p>在 set 的章節中我們學過，set 可以隨時維護一個排序好的集合。但這相當難以實作，並且雖然複雜度是 $O(logN)$，但有著較大的常數。</p>
<p>如果，我不需要那麼多功能，只需要支援：加入一個元素、查詢最大元素、刪除最大元素這幾個操作，其實有個比較快的方法：heap</p>
<p><a target="_blank" rel="noopener" href="https://medium.com/@Kadai/%E8%B3%87%E6%96%99%E7%B5%90%E6%A7%8B%E5%A4%A7%E4%BE%BF%E7%95%B6-binary-heap-ec47ca7aebac">heap 介紹</a></p>
<h3 id="查詢最大值"><a href="#查詢最大值" class="headerlink" title="查詢最大值"></a>查詢最大值</h3><p>直接回傳 1 號節點數字。</p>
<h3 id="刪除最大值"><a href="#刪除最大值" class="headerlink" title="刪除最大值"></a>刪除最大值</h3><p>將 N 號移到 1 號位置，接著不停與其兒子比較，將其與較大的兒子交換，直到其無法再交換為止。</p>
<h3 id="插入值"><a href="#插入值" class="headerlink" title="插入值"></a>插入值</h3><p>將新的值加入 N+1 號位置，不停與其父親比較，直到其值小於父親為止。</p>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">int</span> heap[<span class="number">1000005</span>], N = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">mx</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="keyword">return</span> heap[<span class="number">1</span>];</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">del</span><span class="params">()</span></span>{</span><br><span class="line"> assert(N > <span class="number">0</span>);</span><br><span class="line"> heap[<span class="number">1</span>] = heap[N];</span><br><span class="line"> N--;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,to;i*<span class="number">2</span><=N;i=to){</span><br><span class="line"> <span class="keyword">if</span>(i*<span class="number">2</span>+<span class="number">1</span> > N || heap[i*<span class="number">2</span>] > heap[i*<span class="number">2</span>+<span class="number">1</span>]) to = i*<span class="number">2</span>;</span><br><span class="line"> <span class="keyword">else</span> to = i*<span class="number">2</span>+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span>(heap[i] > heap[to]) <span class="keyword">break</span>;</span><br><span class="line"> swap(heap[i], heap[to]);</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ins</span><span class="params">(<span class="keyword">int</span> x)</span></span>{</span><br><span class="line"> N++;</span><br><span class="line"> heap[N] = x;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=N;i><span class="number">1</span>;i>>=<span class="number">1</span>){</span><br><span class="line"> <span class="keyword">if</span>(heap[i/<span class="number">2</span>] > heap[i]) <span class="keyword">break</span>;</span><br><span class="line"> swap(heap[i/<span class="number">2</span>], heap[i]);</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>而在 STL 中，有個名為 priority_queue 的結構，其內部便是以 heap 實作。它能夠做到 $O(1)$ 查詢最大值、$O(logN)$ 加入元素、$O(logN)$ 刪除最大值。</p>
<p>由於功能完全是 set 的子集，set 能任意刪而 priority_queue 只能刪除最大值，因此大多數時候使用 set，只有在 set 被卡時間以及特定演算法上會使用到 priority_queue。</p>
<h2 id="priority-queue"><a href="#priority-queue" class="headerlink" title="priority_queue"></a>priority_queue</h2><p>宣告</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">priority_queue</span><<span class="keyword">int</span>> pq;</span><br></pre></td></tr></table></figure>
<p>加入元素</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">pq.push(<span class="number">1</span>);</span><br></pre></td></tr></table></figure>
<p>查詢最大</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">cout</span> << pq.top() << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>刪除最大</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">pq.pop();</span><br></pre></td></tr></table></figure>
<h2 id="更改比較函式"><a href="#更改比較函式" class="headerlink" title="更改比較函式"></a>更改比較函式</h2><p>與 set 不同的是，priority_queue 其實有三個參數，分別為型態、底層容器、以及比較函式。若不需更改比較函式，宣告時只需第一參數即可，但若需要自訂比較函式，則需三個都寫出來：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">priority_queue</span><<span class="keyword">int</span>, <span class="built_in">vector</span><<span class="keyword">int</span>>, greater<<span class="keyword">int</span>>> pq;</span><br></pre></td></tr></table></figure>
<p>另一個比較反直覺的東西，則是排在 priority_queue 頂的元素，其實是跟比較函式相反的。例如說，預設的 less<> 函式，排在最上方的反而是最大的元素。若要得到最小的元素，則須使用 greater<> 比較函式。</p>
<h2 id="例題"><a href="#例題" class="headerlink" title="例題"></a>例題</h2><p>把之前 set 題裡的拿來用</p>
<p><a target="_blank" rel="noopener" href="https://tioj.ck.tp.edu.tw/problems/1161">TIOJ 1161</a></p>
<p>★★★★<a target="_blank" rel="noopener" href="https://tioj.ck.tp.edu.tw/problems/1231">TIOJ 1231</a></p>
<h2 id="AC-Code"><a href="#AC-Code" class="headerlink" title="AC Code"></a>AC Code</h2><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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 枚舉其中一個點數</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pii pair<span class="meta-string"><int,int></span></span></span><br><span class="line"></span><br><span class="line"><span class="built_in">priority_queue</span><<span class="keyword">int</span>> pq;</span><br><span class="line"><span class="keyword">int</span> n, k;</span><br><span class="line">pii arr[<span class="number">1000005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="keyword">while</span>(!pq.empty()) pq.pop();</span><br><span class="line"> <span class="built_in">cin</span> >> n >> k;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) <span class="built_in">cin</span> >> arr[i].first >> arr[i].second;</span><br><span class="line"> sort(arr+<span class="number">1</span>, arr+n+<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">int</span> ans = <span class="number">1e9</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++){</span><br><span class="line"> pq.push(arr[i].second);</span><br><span class="line"> <span class="keyword">if</span>(pq.size() > k) pq.pop();</span><br><span class="line"> <span class="keyword">if</span>(pq.size() == k) ans = min(ans, arr[i].first + pq.top());</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << ans << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="keyword">int</span> t; <span class="built_in">cin</span> >> t; <span class="keyword">while</span>(t--) solve(); </span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//TIOJ 1231</span></span><br><span class="line"><span class="comment">//從後面考慮回來</span></span><br><span class="line"><span class="comment">//最後一分鐘該放什麼呢？</span></span><br><span class="line"><span class="comment">//那倒數第二分鐘呢？</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pii pair<span class="meta-string"><ll,ll></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="built_in">priority_queue</span><ll> pq;</span><br><span class="line"></span><br><span class="line">pii arr[<span class="number">100005</span>];</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n, k;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) <span class="built_in">cin</span> >> arr[i].second >> arr[i].first;</span><br><span class="line"> sort(arr+<span class="number">1</span>, arr+<span class="number">1</span>+n, greater<pii>());</span><br><span class="line"> </span><br><span class="line"> <span class="built_in">cin</span> >> k;</span><br><span class="line"> ll t = k, idx = <span class="number">1</span>, ans = <span class="number">0</span>;</span><br><span class="line"> <span class="built_in">priority_queue</span><<span class="keyword">int</span>> pq;</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">while</span>(t > <span class="number">0</span>){</span><br><span class="line"> <span class="keyword">while</span>(idx <= n && arr[idx].first >= t){</span><br><span class="line"> pq.push(arr[idx].second);</span><br><span class="line"> idx++;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span>(pq.empty()){</span><br><span class="line"> ans -= t - arr[idx].first;</span><br><span class="line"> t = arr[idx].first;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> ans += pq.top();</span><br><span class="line"> pq.pop();</span><br><span class="line"> t--;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << ans << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-TW">
<link itemprop="mainEntityOfPage" href="https://emanlaicepsa.github.io/2020/12/09/0-21/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="emanlaicepsa">
<meta itemprop="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="從零開始的演算法競賽入門教學">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/09/0-21/" class="post-title-link" itemprop="url">0-21 map</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">發表於</span>
<time title="創建時間：2020-12-09 14:01:48 / 修改時間：15:17:37" itemprop="dateCreated datePublished" datetime="2020-12-09T14:01:48+08:00">2020-12-09</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="map-是什麼？"><a href="#map-是什麼？" class="headerlink" title="map 是什麼？"></a>map 是什麼？</h2><p>之前我們在陣列章節時，介紹了這樣一個語法：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">a[<span class="number">5</span>] = <span class="number">1</span>;</span><br><span class="line"><span class="built_in">cout</span> << a[<span class="number">5</span>] << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>這個的意思，是將 a 的第五項改變為 1，並將其輸出。當我們執行時，程式就去找： a 的第五項是什麼？再從索引(5)對到值(1)，這是一種一對一的對應關係。</p>
<p>但是，能作為索引的東西，一定只有整數嗎？或者更進一步說，只有從 0 開始到陣列大小 - 1 嗎？能不能自訂？</p>
<p>是可以的，map 在做的，就是這件事情。map 能夠將一個鍵(key)，對應到一個值(value)。</p>
<p>假設今天，我們想查詢一本書的資料，於是輸入了書名，我希望書的作者、出版社等等資訊就出現在眼前。在 C++ 裡，可以這樣寫：</p>
<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><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">map</span><<span class="built_in">string</span>, <span class="built_in">string</span>> author, publisher;</span><br><span class="line">author[<span class="string">"Le Petit Prince"</span>] = <span class="string">"Antoine de Saint-Exupéry"</span>;</span><br><span class="line">publisher[<span class="string">"Le Petit Prince"</span>] = <span class="string">"Gallimard"</span>;</span><br><span class="line"><span class="built_in">cout</span> << author[<span class="string">"Le Petit Prince"</span>] << <span class="string">" "</span> << publisher[<span class="string">"Le Petit Prince"</span>] << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>將書名作為 key，對應到一個作者與一個出版社。</p>
<h2 id="map-的語法"><a href="#map-的語法" class="headerlink" title="map 的語法"></a>map 的語法</h2><p>新增與指派：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">map</span><<span class="keyword">int</span>, <span class="keyword">int</span>> mp;</span><br><span class="line">mp[<span class="number">5</span>] = <span class="number">45</span>;</span><br></pre></td></tr></table></figure>
<p>如果 key 不存在，則這是一個新增操作。如果 key 已存在，則是會將原來的值改掉，為一個指派操作。</p>
<p>查詢：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">cout</span> << mp[<span class="number">5</span>] << <span class="string">'\n'</span>;</span><br><span class="line"><span class="built_in">cout</span> << mp[<span class="number">0</span>] << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>如果 key 已存在，會輸出索引所對應的值。如果索引不存在，則會先新增一個值為預設值的索引，再將其輸出。</p>
<p>刪除：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">mp.erase(<span class="number">5</span>);</span><br></pre></td></tr></table></figure>
<p>與 set 相同。</p>
<p>遍歷：</p>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">map</span><<span class="keyword">int</span>, <span class="keyword">int</span>> mp;</span><br><span class="line">mp[<span class="number">5</span>] = <span class="number">45</span>;</span><br><span class="line"><span class="built_in">cout</span> << mp[<span class="number">0</span>] << <span class="string">'\n'</span>;</span><br><span class="line"><span class="keyword">for</span>(<span class="keyword">auto</span> i:mp){</span><br><span class="line"> <span class="built_in">cout</span> << i.first << <span class="string">" "</span> << i.second << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>輸出結果：</p>
<figure class="highlight plain"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">0 0</span><br><span class="line">5 45</span><br></pre></td></tr></table></figure>
<p>遍歷時，會照著 key 大小由小到大輸出，型態是一個 pair，first 是 key，second 是 value。</p>
<h2 id="map-的底層結構"><a href="#map-的底層結構" class="headerlink" title="map 的底層結構"></a>map 的底層結構</h2><p>與 set 一樣使用紅黑樹實作，插入、查詢、刪除的複雜度均為$O(log N)$，其中 N 是 map 的大小。</p>
<h2 id="key-不需要排序？"><a href="#key-不需要排序？" class="headerlink" title="key 不需要排序？"></a>key 不需要排序？</h2><p>跟 set 一樣，在前面加上 unordered，實作方式改為 hash，失去照順序功能，但插入、查詢、刪除的複雜度降為 $O(1)$。</p>
<h2 id="練習"><a href="#練習" class="headerlink" title="練習"></a>練習</h2><p><a target="_blank" rel="noopener" href="https://toj.tfcis.org/oj/pro/55/">TOJ 55</a></p>
<p><a target="_blank" rel="noopener" href="https://zerojudge.tw/ShowProblem?problemid=d518">ZJ d518</a></p>
<h2 id="AC-Code"><a href="#AC-Code" class="headerlink" title="AC Code"></a>AC Code</h2><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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TOJ 55</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="built_in">unordered_map</span><<span class="keyword">int</span>, <span class="keyword">int</span>> mp;</span><br><span class="line"><span class="keyword">int</span> n, q;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,x;i<=n;i++) <span class="built_in">cin</span> >> x, mp[x]++;</span><br><span class="line"> <span class="built_in">cin</span> >> q;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,x;i<=q;i++) <span class="built_in">cin</span> >> x, <span class="built_in">cout</span> << mp[x] << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// ZJ d518</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="built_in">unordered_map</span><<span class="built_in">string</span>, <span class="keyword">int</span>> mp;</span><br><span class="line"><span class="built_in">string</span> str;</span><br><span class="line"><span class="keyword">int</span> n, id;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">while</span>(<span class="built_in">cin</span>>>n){</span><br><span class="line"> mp.clear();</span><br><span class="line"> id = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> str;</span><br><span class="line"> <span class="keyword">if</span>(!mp[str]) <span class="built_in">cout</span> << <span class="string">"New! "</span>, mp[str] = ++id;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << <span class="string">"Old! "</span>;</span><br><span class="line"> <span class="built_in">cout</span> << mp[str] << <span class="string">'\n'</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-TW">
<link itemprop="mainEntityOfPage" href="https://emanlaicepsa.github.io/2020/12/07/0-20/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="emanlaicepsa">
<meta itemprop="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="從零開始的演算法競賽入門教學">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/07/0-20/" class="post-title-link" itemprop="url">0-20 set</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">發表於</span>
<time title="創建時間：2020-12-07 10:28:52" itemprop="dateCreated datePublished" datetime="2020-12-07T10:28:52+08:00">2020-12-07</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新於</span>
<time title="修改時間：2020-12-14 08:39:14" itemprop="dateModified" datetime="2020-12-14T08:39:14+08:00">2020-12-14</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="問題"><a href="#問題" class="headerlink" title="問題"></a>問題</h2><p>如果今天，我需要支援以下兩種操作：</p>
<ol>
<li>插入一個數字</li>
<li>查詢比一個數字大的最小元素是什麼</li>
</ol>
<p>一個簡單的想法是，就用一個陣列通通存起來，然後查詢時一個一個找。這樣對於第一種插入操作是 $O(1)$ ，第二種是 $O(N)$。</p>
<p>另一個是，插入時使用 insertion sort 方法，讓整個陣列維持排序好的狀態。搜尋時就能直接使用 upper_bound 函式。這樣對於第一種插入操作是 $O(N)$ ，第二種是 $O(logN)$。</p>
<p>在插入與查詢次數差不多的情況下，這兩種方法都無法快速的解決問題。</p>
<h2 id="二元搜尋樹"><a href="#二元搜尋樹" class="headerlink" title="二元搜尋樹"></a>二元搜尋樹</h2><p>雖然現在大家可能還沒有樹的概念，還是請大家看看這個教學。</p>
<p><a target="_blank" rel="noopener" href="https://ithelp.ithome.com.tw/articles/10205875">二元搜尋樹</a></p>
<p>二元搜尋樹保證，一個節點左邊一定全部都比它小，右邊一定全部比它大。</p>
<p>可以發現，以上兩種操作都可以透過二元搜尋樹來完成。而複雜度則是以樹的深度(從一開始走到沒路可走時的最長距離)來決定。</p>
<p>在一般的二元搜尋樹中，深度並沒有保證(想像插入的數字一直遞增)，最高與元素數量 $N$ 相等。</p>
<p>但，若現在有一種二元搜尋樹，可以透過旋轉、換根等操作，保證在任何時刻，深度都是 $O(logN)$，這個題目就可以很好的解決了。</p>
<p>而 set 就可以做到這樣的事情！set 的內部，正是<strong>平衡二元搜尋樹</strong>之一的<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/%E7%BA%A2%E9%BB%91%E6%A0%91">紅黑樹</a>。</p>
<p>不同於之前的 queue 與 stack，這超難實作的，所以就直接進用法。</p>
<h2 id="set-語法"><a href="#set-語法" class="headerlink" title="set 語法"></a>set 語法</h2><p>set，意為集合，集合內不會存在兩個相同元素。</p>
<p>宣告一個 set 名為 s。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">set</span><<span class="keyword">int</span>> s;</span><br></pre></td></tr></table></figure>
<p>插入元素，若 set 內部已存在該元素，則無任何動作。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">s.insert(<span class="number">5</span>);</span><br></pre></td></tr></table></figure>
<p>移除元素，若 set 內部無該元素，則無任何動作。也可以移除一個 iterator 所指向的元素，程式會自動判斷傳入型態。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">s.erase(<span class="number">5</span>);</span><br><span class="line">s.erase(s.begin())</span><br></pre></td></tr></table></figure>
<p>回傳該元素的 <strong>iterator</strong>，若 set 內部無該元素，則回傳 end()。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">s.find(<span class="number">5</span>);</span><br></pre></td></tr></table></figure>
<p>依照順序輸出內部所有元素，複雜度 $O(N)$。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span>(<span class="keyword">int</span> i:s) <span class="built_in">cout</span> << i << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>問一個元素在不在 set 裡。可透過 find 的 return 值，或使用 s.count。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span>(s.find(<span class="number">10</span>) != s.end()) <span class="built_in">cout</span> << <span class="string">"In!\n"</span>;</span><br><span class="line"><span class="keyword">if</span>(s.count(<span class="number">10</span>)) <span class="built_in">cout</span> << <span class="string">"In!\n"</span>;</span><br></pre></td></tr></table></figure>
<p>得到 set 的第一項，可使用 *s.begin()，最後一項使用 *s.rbegin()。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">cout</span> << *s.begin() << <span class="string">'\n'</span>;</span><br><span class="line"><span class="built_in">cout</span> << *s.rbegin() << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>那，可以輸出 set 中第 K 小的數字嗎？答案是不行的，set 沒有辦法做到這點。因此，set 中是沒有 s[k] 這樣的語法的。</p>
<p>但是，set 的 iterator，可以支援 ++, – 的運算，而且是 $O(1)$ 的。所以，若能以一個變數將 begin() 存下來，之後將其 ++，便可以得到第 2 大的數字。</p>
<p>要怎麼儲存呢？用變數。那型態是什麼？是：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">set</span><<span class="keyword">int</span>>::iterator iter = s.begin();</span><br></pre></td></tr></table></figure>
<p>這名稱實在太長，因此我們使用 C++11 後出現的新功能：自動判斷型態！</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">auto</span> iter = s.begin();</span><br><span class="line"><span class="built_in">cout</span> << *(++iter) << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>因此，遍歷 set 也可以寫成：</p>
<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="keyword">for</span>(<span class="keyword">auto</span> iter = s.begin(); iter != s.end(); iter++){</span><br><span class="line"> <span class="built_in">cout</span> << *iter << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>此外，若要得到一個 iterator 的前/後一項，可以使用 prev/next，這樣不會改到本身，常見於得到 set 中最大的數。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">cout</span> << *prev(s.end()) << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<h2 id="回來看看"><a href="#回來看看" class="headerlink" title="回來看看"></a>回來看看</h2><p>原來的問題，要如何用 set 去做呢？</p>
<p>操作一很簡單，就是 insert 而已。</p>
<p>操作二呢？恩…好像還是沒辦法，如果 set 中存在要被查詢的那個數，可以寫：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">auto</span> iter = s.find(x);</span><br><span class="line"><span class="built_in">cout</span> << *(++iter) << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>但若不存在，find 函式回傳 end，就沒辦法了。</p>
<p>若是有一個類似 upper_bound 的函式就好了…</p>
<p>對，沒錯，set 的成員函式有 upper_bound()！</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">cout</span> << *s.upper_bound(<span class="number">5</span>) << <span class="string">'\n'</span>;</span><br></pre></td></tr></table></figure>
<p>順帶一提，upper_bound(s.begin(), s.end(), 5)這種寫法也能輸出正確答案，但是複雜度是糟糕的 $O(size)$。請忘記這種用法，記住 s.upper_bound() 就好！</p>
<h2 id="連續刪除-a-到-b-區間內元素"><a href="#連續刪除-a-到-b-區間內元素" class="headerlink" title="連續刪除 a 到 b 區間內元素"></a>連續刪除 a 到 b 區間內元素</h2><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="keyword">for</span>(<span class="keyword">auto</span> iter = s.find(<span class="number">5</span>); iter != s.end() && *iter < <span class="number">10</span>; iter++){</span><br><span class="line"> s.erase(iter);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>這是對的嗎？看起來好像是，但其實不是，而且會導致 RE。為什麼呢？</p>
<p>當 iter 被 erase 後，它就不存在了，因此將其++後會發生什麼事？沒有人知道。</p>
<h2 id="怎麼辦呢？"><a href="#怎麼辦呢？" class="headerlink" title="怎麼辦呢？"></a>怎麼辦呢？</h2><p>s.erase() 這個函式，其實不是 void，它會回傳被刪除的元素的下一個 iterator。</p>
<p>因此可以利用這個性質：</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">for</span>(<span class="keyword">auto</span> iter = s.find(<span class="number">5</span>); iter != s.end() && *iter < <span class="number">10</span>; iter = s.erase(iter));</span><br></pre></td></tr></table></figure>
<h2 id="我需要有多個相同元素的-set"><a href="#我需要有多個相同元素的-set" class="headerlink" title="我需要有多個相同元素的 set"></a>我需要有多個相同元素的 set</h2><p>set 在 insert 時，遇到相同元素會忽略，常常會因為這樣產生許多 bug。比如，插入 5 個 1 後刪除 1 個 1，在 set 中就不存在 1 了，但你真正想做的事，可能是跟剩下的 4 個 4 有關。</p>
<p>那要怎麼讓 set 中有多個元素呢？</p>
<p>第一個辦法是，多紀錄一個變數 cnt，代表每個元素的個數。只在 cnt 從 0 變為 1 時將其加入 set，從 1 變為 0 時將其移除。</p>
<p>但是，其實，STL 中有個東西叫 multiset，可以同時存在多個相同元素！</p>
<p>語法大致與 set 相同，但有一些東西要注意：</p>
<ol>
<li>可用 .count() 函式回傳 multiset 中元素數量。</li>
<li>s.erase(10) 代表的意思是：刪除 multiset 中<strong>所有</strong>的 10，若只刪除一個要用 s.erase(s.find(10))</li>
</ol>
<h2 id="我不需要排序，我只需要知道哪些東西在裡面"><a href="#我不需要排序，我只需要知道哪些東西在裡面" class="headerlink" title="我不需要排序，我只需要知道哪些東西在裡面"></a>我不需要排序，我只需要知道哪些東西在裡面</h2><p>STL 中，有個東西叫 unordered_set，底層以 hash 實作。插入與刪除的複雜度皆為常數稍大的 $O(1)$，一般來說會比 set 的 $O(logN)$ 快。</p>
<p>unordered_set 失去 lower_bound 與 upper_bound 功能，遍歷時也不會照大小輸出，其餘功能與 set 相同。</p>
<h2 id="自訂比較函式"><a href="#自訂比較函式" class="headerlink" title="自訂比較函式"></a>自訂比較函式</h2><p>這裡的比較函式跟 sort 的不一樣，是一個 struct，裡面有一個 operator()，所以要這樣寫：</p>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">sum_of_digits</span><span class="params">(<span class="keyword">int</span> x)</span></span>{</span><br><span class="line"> <span class="keyword">int</span> ans = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span>(x){</span><br><span class="line"> ans += x%<span class="number">10</span>;</span><br><span class="line"> x/=<span class="number">10</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> ans;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">cmp</span>{</span></span><br><span class="line"> <span class="function"><span class="keyword">bool</span> <span class="title">operator</span><span class="params">()</span><span class="params">(<span class="keyword">int</span> a, <span class="keyword">int</span> b)</span></span>{</span><br><span class="line"> <span class="keyword">return</span> sum_of_digits(a) < sum_of_digits(b);</span><br><span class="line"> }</span><br><span class="line">};</span><br><span class="line"></span><br><span class="line"><span class="built_in">set</span><<span class="keyword">int</span>, cmp> s;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> s.insert(<span class="number">56</span>);</span><br><span class="line"> s.insert(<span class="number">11</span>);</span><br><span class="line"> s.insert(<span class="number">7</span>);</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">auto</span> i:s) <span class="built_in">cout</span> << i << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>預設的比較函式是 less<>，有另一個定義好的比較函式是 greater<>，所以如果要從大排到小，可以這樣寫。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">set</span><<span class="keyword">int</span>, greater<<span class="keyword">int</span>>> s;</span><br></pre></td></tr></table></figure>
<h2 id="練習"><a href="#練習" class="headerlink" title="練習"></a>練習</h2><p><a target="_blank" rel="noopener" href="https://tioj.ck.tp.edu.tw/problems/1911">TIOJ 1911</a></p>
<p>85 分解：<br><a target="_blank" rel="noopener" href="https://zerojudge.tw/ShowProblem?problemid=b938">ZJ b938</a></p>
<p>★★★ <a target="_blank" rel="noopener" href="https://toj.tfcis.org/oj/pro/275/">TOJ 275</a></p>
<p>★★★★ <a target="_blank" rel="noopener" href="https://tioj.ck.tp.edu.tw/problems/1161">TIOJ 1161</a></p>
<p>★★★★★ <a target="_blank" rel="noopener" href="https://toj.tfcis.org/oj/pro/512/">TOJ 512</a></p>
<p>★★★★★★★★ <a target="_blank" rel="noopener" href="https://tioj.ck.tp.edu.tw/problems/1941">TIOJ 1941</a></p>
<h2 id="AC-Code"><a href="#AC-Code" class="headerlink" title="AC Code"></a>AC Code</h2><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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TIOJ 1911</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="built_in">multiset</span><ll> m;</span><br><span class="line"><span class="keyword">int</span> n;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="keyword">while</span>(<span class="built_in">cin</span> >> n){</span><br><span class="line"> <span class="keyword">if</span>(n == <span class="number">0</span>) <span class="keyword">break</span>;</span><br><span class="line"> <span class="keyword">if</span>(n > <span class="number">0</span>) m.insert(n);</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">if</span>(m.empty()) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="keyword">if</span>(n == <span class="number">-1</span>){</span><br><span class="line"> <span class="built_in">cout</span> << *m.begin() << <span class="string">' '</span>;</span><br><span class="line"> m.erase(m.begin());</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">auto</span> iter = m.end();</span><br><span class="line"> iter--; <span class="comment">// end 的前一個才是真正最大的</span></span><br><span class="line"> <span class="built_in">cout</span> << *iter << <span class="string">' '</span>;</span><br><span class="line"> m.erase(iter);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// ZJ b938 85 分解</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> n, m;</span><br><span class="line"><span class="built_in">set</span><<span class="keyword">int</span>> s;</span><br><span class="line"><span class="keyword">bool</span> dead[<span class="number">1000005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n >> m;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) s.insert(i);</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,x;i<=m;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> x;</span><br><span class="line"> <span class="keyword">if</span>(dead[x]) <span class="built_in">cout</span> << <span class="string">"0u0 ...... ?\n"</span>;</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">auto</span> iter = s.upper_bound(x);</span><br><span class="line"> <span class="keyword">if</span>(iter == s.end()) <span class="built_in">cout</span> << <span class="string">"0u0 ...... ?\n"</span>;</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> <span class="built_in">cout</span> << *iter << <span class="string">'\n'</span>;</span><br><span class="line"> dead[*iter] = <span class="number">1</span>;</span><br><span class="line"> s.erase(iter);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TOJ 275</span></span><br><span class="line"><span class="comment">// 分成小的堆跟大的堆，保持兩邊的個數差異在1以內。</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line">ll n;</span><br><span class="line"><span class="built_in">multiset</span><ll> small, big;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">pop_big</span><span class="params">()</span></span>{</span><br><span class="line"> ll x = *big.begin();</span><br><span class="line"> small.insert(x);</span><br><span class="line"> big.erase(big.begin());</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">pop_small</span><span class="params">()</span></span>{</span><br><span class="line"> ll x = *small.rbegin();</span><br><span class="line"> big.insert(x);</span><br><span class="line"> small.erase(prev(small.end()));</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cout</span> << fixed << setprecision(<span class="number">6</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,x;i<=n;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> x;</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span>(i == <span class="number">1</span> || x < *small.rbegin()) small.insert(x);</span><br><span class="line"> <span class="keyword">else</span> big.insert(x);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">while</span>(big.size() > i/<span class="number">2</span>) pop_big();</span><br><span class="line"> <span class="keyword">while</span>(big.size() < i/<span class="number">2</span>) pop_small();</span><br><span class="line"></span><br><span class="line"> <span class="keyword">double</span> ans;</span><br><span class="line"> <span class="keyword">if</span>(i&<span class="number">1</span>) ans = *small.rbegin();</span><br><span class="line"> <span class="keyword">else</span> ans = (*small.rbegin() + *big.begin()) * <span class="number">1.0</span> / <span class="number">2</span>;</span><br><span class="line"> <span class="built_in">cout</span> << ans << <span class="string">'\n'</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// 枚舉其中一個點數</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pii pair<span class="meta-string"><int,int></span></span></span><br><span class="line"></span><br><span class="line"><span class="built_in">multiset</span><<span class="keyword">int</span>,greater<<span class="keyword">int</span>>> s;</span><br><span class="line"><span class="keyword">int</span> n, k;</span><br><span class="line">pii arr[<span class="number">1000005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span></span>{</span><br><span class="line"> s.clear();</span><br><span class="line"> <span class="built_in">cin</span> >> n >> k;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) <span class="built_in">cin</span> >> arr[i].first >> arr[i].second;</span><br><span class="line"> sort(arr+<span class="number">1</span>, arr+n+<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">int</span> ans = <span class="number">1e9</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++){</span><br><span class="line"> s.insert(arr[i].second);</span><br><span class="line"> <span class="keyword">if</span>(s.size() > k) s.erase(s.begin());</span><br><span class="line"> <span class="keyword">if</span>(s.size() == k) ans = min(ans, arr[i].first + *s.begin());</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << ans << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="keyword">int</span> t; <span class="built_in">cin</span> >> t; <span class="keyword">while</span>(t--) solve(); </span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TOJ 512</span></span><br><span class="line"><span class="comment">// 每次操作 1 最多增加 2 個錯誤位置，以 set 維護錯誤位置，使你在 log 時間內能夠刪除 1 個錯誤位置</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="built_in">set</span><<span class="keyword">int</span>> s;</span><br><span class="line"><span class="keyword">int</span> n, q;</span><br><span class="line"><span class="keyword">int</span> arr[<span class="number">1000005</span>], pos[<span class="number">1000005</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">change</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span></span>{</span><br><span class="line"> s.erase(x);</span><br><span class="line"> s.erase(y);</span><br><span class="line"> swap(arr[x], arr[y]);</span><br><span class="line"> pos[arr[x]] = x;</span><br><span class="line"> pos[arr[y]] = y;</span><br><span class="line"> <span class="comment">//cout << x << " " << y << " " << arr[x] << " " << arr[y] << '\n';</span></span><br><span class="line"> <span class="keyword">if</span>(arr[x] != x) s.insert(x);</span><br><span class="line"> <span class="keyword">if</span>(arr[y] != y) s.insert(y);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">recover</span><span class="params">(<span class="keyword">int</span> x, <span class="keyword">int</span> y)</span></span>{</span><br><span class="line"> <span class="keyword">int</span> ans = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span>(<span class="number">1</span>){</span><br><span class="line"> <span class="keyword">auto</span> iter = s.lower_bound(x);</span><br><span class="line"> <span class="keyword">if</span>(iter == s.end() || *iter > y) <span class="keyword">break</span>;</span><br><span class="line"> ans++;</span><br><span class="line"> change(pos[*iter], *iter);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> ans;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n >> q;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) pos[i] = arr[i] = i;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,ope,a,b;i<=q;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> ope >> a >> b;</span><br><span class="line"> <span class="keyword">if</span>(ope == <span class="number">1</span>) change(a, b);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span> << recover(a, b) << <span class="string">'\n'</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">// TIOJ 1941</span></span><br><span class="line"><span class="comment">// 建議先了解 LIS 以後再來</span></span><br><span class="line"><span class="comment">// 注意加入一隻寶可夢時，LIS表格的變化</span></span><br><span class="line"><span class="comment">// 以set儲存LIS改變的位置即可</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="built_in">multiset</span><<span class="keyword">int</span>> s;</span><br><span class="line"><span class="keyword">int</span> n;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> ios::sync_with_stdio(<span class="number">0</span>), <span class="built_in">cin</span>.tie(<span class="number">0</span>);</span><br><span class="line"> <span class="built_in">cin</span> >> n;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>,l,r;i<=n;i++){</span><br><span class="line"> <span class="built_in">cin</span> >> l >> r;</span><br><span class="line"> s.insert(l);</span><br><span class="line"> <span class="keyword">auto</span> iter = s.upper_bound(r);</span><br><span class="line"> <span class="keyword">if</span>(iter != s.end()) s.erase(iter);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span> << s.size() << <span class="string">'\n'</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="zh-TW">
<link itemprop="mainEntityOfPage" href="https://emanlaicepsa.github.io/2020/12/03/0-19/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/avatar.gif">
<meta itemprop="name" content="emanlaicepsa">
<meta itemprop="description" content="由國際資訊奧林匹亞銀牌得主親自編寫，適合新手的演算法競賽指南。目的為減少南北差距，使每個人在演算法競賽中，都能站在公平的起跑點。">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="從零開始的演算法競賽入門教學">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2020/12/03/0-19/" class="post-title-link" itemprop="url">0-19 queue 與 stack</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">發表於</span>
<time title="創建時間：2020-12-03 16:06:33" itemprop="dateCreated datePublished" datetime="2020-12-03T16:06:33+08:00">2020-12-03</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新於</span>
<time title="修改時間：2020-12-07 10:27:00" itemprop="dateModified" datetime="2020-12-07T10:27:00+08:00">2020-12-07</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="隊列-queue"><a href="#隊列-queue" class="headerlink" title="隊列(queue)"></a>隊列(queue)</h2><p>想像有一天，你來到了師大最熱門的 TOI 拉麵店，店內空間不大，只有三十個左右，因此門外的人排成了長長的隊伍。你加入到了隊列的尾端，等待老闆叫號。隨著時間過去，前面的人依序進入店裡，也看到不少人帶著滿足的笑容走出。終於，就快輪到你了！</p>
<p>只能從後方加入，並且只能從前方取出，這就稱作 queue！</p>
<h2 id="實作"><a href="#實作" class="headerlink" title="實作"></a>實作</h2><p>知道了概念，但要怎麼實作 queue 呢？</p>
<p>我們可以先開一個足夠大的陣列，並且記錄當前隊伍最前方位置與最後方位置。</p>
<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><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> arr[<span class="number">1000005</span>], l=<span class="number">0</span>, r=<span class="number">-1</span>; <span class="comment">// 想想為什麼 r = -1</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">int</span> x)</span></span>{</span><br><span class="line"> r++;</span><br><span class="line"> arr[r] = x;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">pop</span><span class="params">()</span></span>{</span><br><span class="line"> assert(l<=r); <span class="comment">// 還有東西</span></span><br><span class="line"> l++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">front</span><span class="params">()</span></span>{</span><br><span class="line"> assert(l<=r);</span><br><span class="line"> <span class="keyword">return</span> arr[l];</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">siz</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="keyword">return</span> r-l+<span class="number">1</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> push(<span class="number">1</span>); <span class="comment">// 從後方加入元素</span></span><br><span class="line"> push(<span class="number">2</span>); </span><br><span class="line"> push(<span class="number">5</span>);</span><br><span class="line"> <span class="built_in">cout</span> << front() <<<span class="string">'\n'</span>; <span class="comment">// 查看最前方元素</span></span><br><span class="line"> <span class="built_in">cout</span> << siz() <<<span class="string">'\n'</span>; <span class="comment">// 查看queue大小</span></span><br><span class="line"> pop(); <span class="comment">// 從前方移除元素</span></span><br><span class="line"> <span class="built_in">cout</span> << front() <<<span class="string">'\n'</span>; <span class="comment">// 查看最前方元素</span></span><br><span class="line"> <span class="built_in">cout</span> << siz() <<<span class="string">'\n'</span>; <span class="comment">// 查看queue大小</span></span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>這樣雖然可以得到正確的答案，但不免會有浪費空間(pop 後前方空間就浪費了)或記憶體不夠大的問題，因此，可將 r mod 陣列長度，當元素存到底時，就再回到第一格，以避免浪費空間，當然，陣列還是要開得夠大，至少必須超過同時存在的元素數量。</p>