-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
936 lines (796 loc) · 124 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
<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.9.0">
<meta charset="utf-8" name="viewport" content="width=device-width, initial-scale=1.0, minimum-scale=1, maximum-scale=1, user-scalable=no">
<meta http-equiv="X-UA-Compatible" content="ie=edge">
<title>Naukri's Blog</title>
<!-- JQuery -->
<script src="/lib/jquery.min.js"></script>
<!-- Font Awesome -->
<script src="/lib/fontawesome/all.min.js"></script>
<!-- Title & Icon -->
<link rel="icon" href="/img/favicon.ico">
<!-- Google Analytics -->
<meta name="google-site-verification" content="Xl6ILac3vA_Uk3OURVO1Qsm6arpq-14A7nyzaYwFhR4">
<!-- MyStyle -->
<link rel="stylesheet" href="/css/style.css">
<!-- LayoutBehavior -->
<script src="/js/layoutBehavior.js"></script>
<!-- PostBehavior -->
<script src="/js/postBehavior.js"></script>
</head>
<body id="layout" style="background-image: url(/img/winxp.jpg);">
<nav id="navbar" class="banner-style">
<div class="navbar-list wrapper">
<div class="nav-item-avatar">
<img src="/img/gitcat.png" alt="avatar" onmousedown="return false;">
</div>
<div class="nav-item-links-left">
<ul class="links">
<li class="item">
<a class="item-link" href="/">
首頁
</a>
</li>
<li class="item">
<a class="item-link" href="/archives">
歸檔
</a>
</li>
</ul>
</div>
<div class="nav-item-links-right">
<ul class="links">
<li class="item">
<a href="https://zerojudge.tw/UserStatistic?id=47443" title="ZeroJudge">
<i class="item-link fas fa-code"></i>
</a>
</li>
<li class="item">
<a href="https://github.com/naukri7707" title="Github">
<i class="item-link fab fa-github"></i>
</a>
</li>
</ul>
</div>
</div>
</nav>
<div id="messageField">
<p>Test Message</p>
</div>
<header id="header">
<img class="banner-img" src="/img/banner.jpg" onmousedown="return false" alt="headerImage">
<div class="banner-inner">
<div class="banner-title">
Naukri's Blog
</div>
</div>
</header>
<div class="wrapper main-body">
<main id="main">
<article id="d373: 5. 乳酪的誘惑" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/" title="線上解題 (252)">
<div class="meta-list-link-text">
線上解題
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/ZeroJudge/" title="ZeroJudge (251)">
<div class="meta-list-link-text">
ZeroJudge
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
d373: 5. 乳酪的誘惑
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/線上解題/ZeroJudge/d373/">
<h1 class="title-text" title="d373: 5. 乳酪的誘惑">d373: 5. 乳酪的誘惑</h1>
</a>
<div class="separator"></div>
<div class="info">
<i class="fas fa-tags"></i>
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/BFS/">BFS</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Dijkstra/">Dijkstra</a></li></ul>
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-09-19
</time>
</div>
</header>
<div class="content toc-article">
<h2 id="內容"><a href="#內容" class="headerlink" title="內容"></a>內容</h2><p>這個問題跟傳統的老鼠走迷宮問題不太一樣，給定一個四方形的格點空間<br>x 座標與 y 座標由左下角原點以 0 開始往右和往上遞增，裡面有一個區域是鼠窩，另外有一個區域是乳酪屋<br>此外還有很多障礙物是用來阻擋鼠輩的橫行，也就是障礙物是不可穿越的。<br>在此空間裡可能沒有路可以從鼠窩走到乳酪屋，此種情況你必須回報沒有路徑<br>如果有路可以連接鼠窩跟乳酪屋的話，你必須算出從鼠窩走到乳酪屋的最短路徑。<br>老鼠的每一步只能往四個方向走:上、下、左、右，不能走對角方向。出發點與終點可以是鼠窩與乳酪屋的任何一個位置。<br>以圖一為例，鼠窩到乳酪屋的最短距離為 15，由鼠窩裡圓圈所標示的點(10,2)往左出發走到乳酪屋中圓圈所標示的點(1,8)。<br>鼠窩與乳酪屋的形狀一定是一條直線，障礙物可以是一點可以是一條直線也可以是一個矩形區域<br>圖一中的障礙物是由三個點與兩條直線所構成，分別為點(2,6)、(3,5)、與(4,4)和線(4,3)~(7,3)與(7,4)~(7,9)。<br>在找尋最短路徑時，不要只派遣一隻老鼠出任務，這樣會累死這隻可憐的倒霉鼠的。</p>
<p><img src="https://zerojudge.tw/images/problems/d373.jpg" alt="img1"></p>
<hr>
<h2 id="輸入"><a href="#輸入" class="headerlink" title="輸入"></a>輸入</h2><p>輸入的第一行為兩個整數，描述方形格點空間的大小，第一個表示行的數目，第二個表示列的數目<br>在此問題中行和列的數目都不會超過 1000 (<=1000)。<br>接下來“.mb”表示後面用兩點來描述鼠窩的位置，每個點先 x 座標再 y 座標，兩個點沒有固定的先後排序。<br>接下來“.cb”表示後面用兩點來描述乳酪屋的位置，兩個點也沒有固定的先後排序。<br>最後“.bb”表示後面開始每一行描述一個障礙物的位置，不管是一點還是一條線都是用兩點來表示<br>最後以“.be”表示結束。</p>
<blockquote>
<p>以圖一為例，其輸入檔案如下:<br>14 10<br>.mb 10 4 10 1<br>.cb 1 8 4 8<br>.bb<br>2 6 2 6<br>3 5 3 5<br>4 4 4 4<br>4 3 7 3<br>7 9 7 4<br>.be</p>
</blockquote>
<h2 id="輸出"><a href="#輸出" class="headerlink" title="輸出"></a>輸出</h2><p>沒有路徑的話，輸出“no path”。有路徑的話輸出最短路徑距離。</p>
<blockquote>
<p>15</p>
</blockquote>
<hr>
<h2 id="解題思路"><a href="#解題思路" class="headerlink" title="解題思路"></a>解題思路</h2><p>強化版的尋路問題，因為可以從鼠窩的任意點出發且抵達乳酪屋的任意點及代表結束，因此將所有鼠窩的點都當作起點，使用 Dijkstra 從所有起點向外擴張，直到擴張至乳酪屋時結束。擴張的總輪數即為鼠窩移動至乳酪屋的最短距離，輸出該值即可。</p>
<ul>
<li><p>地圖很大，使用佇列紀錄下次擴張的位置。</p>
</li>
<li><p>每個測資點僅一筆測資且鼠窩和乳酪屋皆只有一筆資料。</p>
</li>
</ul>
<div class="hidden-content">
<hr>
<h2 id="完整程式碼"><a href="#完整程式碼" class="headerlink" title="完整程式碼"></a>完整程式碼</h2><h6 id="AC-8ms-4MB"><a href="#AC-8ms-4MB" class="headerlink" title="AC (8ms, 4MB)"></a>AC (8ms, 4MB)</h6><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX 1010</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> SWAP(x, y) (x)^=((y)^=((x)^=(y)))</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> x, y;</span><br><span class="line">}Point;</span><br><span class="line"></span><br><span class="line">Point quene1[MAX * <span class="number">4</span>], quene2[MAX * <span class="number">4</span>];</span><br><span class="line"><span class="keyword">int</span> <span class="built_in">map</span>[MAX][MAX];</span><br><span class="line"><span class="keyword">char</span> input[<span class="number">100</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">char</span>* <span class="title">getUInt</span><span class="params">(<span class="keyword">register</span> <span class="keyword">char</span> buffer[], <span class="keyword">register</span> <span class="keyword">unsigned</span> <span class="keyword">int</span>* dst)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">while</span> (*buffer < <span class="string">'0'</span>)</span><br><span class="line"> <span class="keyword">if</span> (!*buffer++) <span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line"> *dst = *buffer ^ <span class="string">'0'</span>;</span><br><span class="line"> <span class="keyword">while</span> (*++buffer >= <span class="string">'0'</span>)</span><br><span class="line"> * dst = (*dst << <span class="number">3</span>) + (*dst << <span class="number">1</span>) + (*buffer ^ <span class="string">'0'</span>);</span><br><span class="line"> <span class="keyword">return</span> buffer;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">setMap</span><span class="params">(<span class="keyword">int</span> <span class="built_in">map</span>[][MAX], Point s, Point e, <span class="keyword">int</span> val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span> (e.x < s.x) SWAP(e.x, s.x);</span><br><span class="line"> <span class="keyword">if</span> (e.y < s.y) SWAP(e.y, s.y);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = s.x; i <= e.x; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = s.y; j <= e.y; j++)</span><br><span class="line"> <span class="built_in">map</span>[i][j] = val;</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">getAns</span><span class="params">(<span class="keyword">int</span> row, <span class="keyword">int</span> col, <span class="keyword">register</span> Point* nowTop)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> Point* now = quene1, * next = quene2, * nextTop, * tmp;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> step = <span class="number">1</span>;; step++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (nowTop == now)</span><br><span class="line"> <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line"> nextTop = next;</span><br><span class="line"> <span class="keyword">while</span> (now <= --nowTop)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">map</span>[nowTop->x][nowTop->y]) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="built_in">map</span>[nowTop->x][nowTop->y] = step;</span><br><span class="line"> <span class="keyword">if</span> (nowTop->x > <span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">map</span>[nowTop->x - <span class="number">1</span>][nowTop->y])</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">map</span>[nowTop->x - <span class="number">1</span>][nowTop->y] == <span class="number">-2</span>)</span><br><span class="line"> <span class="keyword">return</span> step;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> nextTop->x = nowTop->x - <span class="number">1</span>, nextTop++->y = nowTop->y;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (nowTop->x < row)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">map</span>[nowTop->x + <span class="number">1</span>][nowTop->y])</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">map</span>[nowTop->x + <span class="number">1</span>][nowTop->y] == <span class="number">-2</span>)</span><br><span class="line"> <span class="keyword">return</span> step;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> nextTop->x = nowTop->x + <span class="number">1</span>, nextTop++->y = nowTop->y;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (nowTop->y > <span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">map</span>[nowTop->x][nowTop->y - <span class="number">1</span>])</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">map</span>[nowTop->x][nowTop->y - <span class="number">1</span>] == <span class="number">-2</span>)</span><br><span class="line"> <span class="keyword">return</span> step;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> nextTop->x = nowTop->x, nextTop++->y = nowTop->y - <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (nowTop->y < col)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">map</span>[nowTop->x][nowTop->y + <span class="number">1</span>])</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">map</span>[nowTop->x][nowTop->y + <span class="number">1</span>] == <span class="number">-2</span>)</span><br><span class="line"> <span class="keyword">return</span> step;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> nextTop->x = nowTop->x, nextTop++->y = nowTop->y + <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> tmp = now, now = next, next = tmp;</span><br><span class="line"> nowTop = nextTop;</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"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">char</span>* st;</span><br><span class="line"> <span class="keyword">int</span> n, m, ans;</span><br><span class="line"> Point s, e, * nowTop = quene1;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d %d"</span>, &n, &m);</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%*s %d %d %d %d"</span>, &s.x, &s.y, &e.x, &e.y);</span><br><span class="line"> <span class="keyword">if</span> (e.x < s.x) SWAP(e.x, s.x);</span><br><span class="line"> <span class="keyword">if</span> (e.y < s.y) SWAP(e.y, s.y);</span><br><span class="line"> <span class="keyword">int</span> idx = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = s.x; i <= e.x; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = s.y; j <= e.y; j++)</span><br><span class="line"> nowTop->x = i, nowTop++->y = j;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%*s %d %d %d %d %*s"</span>, &s.x, &s.y, &e.x, &e.y);</span><br><span class="line"> setMap(<span class="built_in">map</span>, s, e, <span class="number">-2</span>);</span><br><span class="line"> getchar();</span><br><span class="line"> <span class="keyword">while</span> (gets(input) && input[<span class="number">1</span>] != <span class="string">'b'</span>)</span><br><span class="line"> {</span><br><span class="line"> st = getUInt(input, &s.x), st = getUInt(st, &s.y);</span><br><span class="line"> st = getUInt(st, &e.x), st = getUInt(st, &e.y);</span><br><span class="line"> setMap(<span class="built_in">map</span>, s, e, <span class="number">-3</span>);</span><br><span class="line"> }</span><br><span class="line"> ans = getAns(n - <span class="number">1</span>, m - <span class="number">1</span>, nowTop);</span><br><span class="line"> <span class="keyword">if</span> (ans == <span class="number">-1</span>)</span><br><span class="line"> <span class="built_in">puts</span>(<span class="string">"no path"</span>);</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d"</span>, ans);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
</div>
<div class="more">
<a class="more-button" onclick="readMore()">閱讀更多</a>
</div>
</div>
</article>
<article id="e253: a + b problem" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/" title="線上解題 (252)">
<div class="meta-list-link-text">
線上解題
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/ZeroJudge/" title="ZeroJudge (251)">
<div class="meta-list-link-text">
ZeroJudge
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
e253: a + b problem
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/線上解題/ZeroJudge/e253/">
<h1 class="title-text" title="e253: a + b problem">e253: a + b problem</h1>
</a>
<div class="separator"></div>
<div class="info">
<i class="fas fa-tags"></i>
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/位元運算/">位元運算</a></li></ul>
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-09-04
</time>
</div>
</header>
<div class="content toc-article">
<h2 id="內容"><a href="#內容" class="headerlink" title="內容"></a>內容</h2><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">add</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">while</span>(b) {</span><br><span class="line"> <span class="keyword">int</span> ta = a _ b, tb = (a _ b) __ <span class="number">1</span>;</span><br><span class="line"> a = __, b = __;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> a;</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> a, b;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d %d"</span>, &a, &b);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d"</span>, add(a, b));</span><br><span class="line"></span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>請把上述程式的'_'填完，讓 add()可以回傳 a+b 的結果。</p>
<p>一個'_'代表一個字元</p>
<p>不准使用+ - * /運算子</p>
<hr>
<h2 id="輸入"><a href="#輸入" class="headerlink" title="輸入"></a>輸入</h2><p>(本題無輸入)</p>
<blockquote>
<p>(本題無輸入)</p>
</blockquote>
<h2 id="輸出"><a href="#輸出" class="headerlink" title="輸出"></a>輸出</h2><p>依照從上到下、從左到右的順序輸出填入的答案，並用空白隔開</p>
<p>ex:</p>
<p>/ * && gg cc</p>
<blockquote>
<p>(答案被帕克吃掉了)</p>
</blockquote>
<hr>
<h2 id="解題思路"><a href="#解題思路" class="headerlink" title="解題思路"></a>解題思路</h2><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">add</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="function"></span>{</span><br><span class="line"> <span class="keyword">while</span> (b)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> ta = a ^ b, tb = (a & b) << <span class="number">1</span>;</span><br><span class="line"> a = ta, b = tb;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> a;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>模擬加法。</p>
<div class="hidden-content">
<hr>
<h2 id="完整程式碼"><a href="#完整程式碼" class="headerlink" title="完整程式碼"></a>完整程式碼</h2><h6 id="AC-19ms-3-5MB"><a href="#AC-19ms-3-5MB" class="headerlink" title="AC (19ms, 3.5MB)"></a>AC (19ms, 3.5MB)</h6><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></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"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">puts</span>(<span class="string">"^ & << ta tb"</span>);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
</div>
<div class="more">
<a class="more-button" onclick="readMore()">閱讀更多</a>
</div>
</div>
</article>
<article id="a020: 身份證檢驗" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/" title="線上解題 (252)">
<div class="meta-list-link-text">
線上解題
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/ZeroJudge/" title="ZeroJudge (251)">
<div class="meta-list-link-text">
ZeroJudge
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
a020: 身份證檢驗
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/線上解題/ZeroJudge/a020/">
<h1 class="title-text" title="a020: 身份證檢驗">a020: 身份證檢驗</h1>
</a>
<div class="separator"></div>
<div class="info">
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-08-05
</time>
</div>
</header>
<div class="content toc-article">
<h2 id="內容"><a href="#內容" class="headerlink" title="內容"></a>內容</h2><p>我國的身份證字號有底下這樣的規則，因此對於任意輸入的身份證字號可以有一些基本的判斷原則，請您來判斷一個身份證字號是否是正常的號碼(不代表確有此號、此人)。</p>
<p>(1) 英文代號以下表轉換成數字</p>
<pre><code>A=10 台北市 J=18 新竹縣 S=26 高雄縣
B=11 台中市 K=19 苗栗縣 T=27 屏東縣
C=12 基隆市 L=20 台中縣 U=28 花蓮縣
D=13 台南市 M=21 南投縣 V=29 台東縣
E=14 高雄市 N=22 彰化縣 W=32 金門縣
F=15 台北縣 O=35 新竹市 X=30 澎湖縣
G=16 宜蘭縣 P=23 雲林縣 Y=31 陽明山
H=17 桃園縣 Q=24 嘉義縣 Z=33 連江縣
I=34 嘉義市 R=25 台南縣</code></pre><p>(2) 英文轉成的數字, 個位數乘９再加上十位數的數字</p>
<p>(3) 各數字從右到左依次乘１、２、３、４．．．．８</p>
<p>(4) 求出(2),(3) 及最後一碼的和</p>
<p>(5) (4)除 10 若整除，則為 real，否則為 fake</p>
<p>例： T112663836</p>
<p>2 + 7*9 + 1*8 + 1*7 + 2*6 + 6*5 + 6*4 + 3*3 + 8*2 + 3*1 + 6 = 180</p>
<p>除以 10 整除，因此為 real</p>
<hr>
<h2 id="輸入"><a href="#輸入" class="headerlink" title="輸入"></a>輸入</h2><p>一組身份證號碼</p>
<blockquote>
<p>T112663836<br>S154287863</p>
</blockquote>
<h2 id="輸出"><a href="#輸出" class="headerlink" title="輸出"></a>輸出</h2><p>輸出 real or fake</p>
<blockquote>
<p>real<br>fake</p>
</blockquote>
<hr>
<h2 id="解題思路"><a href="#解題思路" class="headerlink" title="解題思路"></a>解題思路</h2><p>建一個表去對應 A~Z 要對應的數字，接著依照規則算出結果後和 10 取餘判斷即可。</p>
<div class="hidden-content">
<hr>
<h2 id="完整程式碼"><a href="#完整程式碼" class="headerlink" title="完整程式碼"></a>完整程式碼</h2><h6 id="AC-2ms-60KB"><a href="#AC-2ms-60KB" class="headerlink" title="AC (2ms, 60KB)"></a>AC (2ms, 60KB)</h6><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> sum, eng[<span class="number">26</span>] = { <span class="number">10</span> ,<span class="number">11</span> ,<span class="number">12</span> ,<span class="number">13</span> ,<span class="number">14</span> ,<span class="number">15</span> ,<span class="number">16</span> ,<span class="number">17</span> ,<span class="number">34</span> ,<span class="number">18</span> ,<span class="number">19</span> ,<span class="number">20</span> ,<span class="number">21</span></span><br><span class="line"> ,<span class="number">22</span> ,<span class="number">35</span> ,<span class="number">23</span> ,<span class="number">24</span> ,<span class="number">25</span> ,<span class="number">26</span> ,<span class="number">27</span> ,<span class="number">28</span> ,<span class="number">29</span> ,<span class="number">32</span> ,<span class="number">30</span> ,<span class="number">31</span> ,<span class="number">33</span> };</span><br><span class="line"><span class="keyword">char</span> input[<span class="number">11</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"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">while</span> (gets(input) != <span class="literal">NULL</span>)</span><br><span class="line"> {</span><br><span class="line"> sum = eng[input[<span class="number">0</span>] - <span class="string">'A'</span>] / <span class="number">10</span> + (eng[input[<span class="number">0</span>] - <span class="string">'A'</span>] % <span class="number">10</span>) * <span class="number">9</span> + (input[<span class="number">8</span>] - <span class="string">'0'</span>) + (input[<span class="number">9</span>] - <span class="string">'0'</span>);</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">8</span>; i++)</span><br><span class="line"> sum += (input[i] - <span class="string">'0'</span>) * (<span class="number">9</span> - i);</span><br><span class="line"> <span class="keyword">if</span> (sum % <span class="number">10</span> == <span class="number">0</span>) <span class="built_in">puts</span>(<span class="string">"real"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">puts</span>(<span class="string">"fake"</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
</div>
<div class="more">
<a class="more-button" onclick="readMore()">閱讀更多</a>
</div>
</div>
</article>
<article id="[模板] Heap(堆積)" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/模板庫/" title="模板庫 (8)">
<div class="meta-list-link-text">
模板庫
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
[模板] Heap(堆積)
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/模板庫/Heap/">
<h1 class="title-text" title="[模板] Heap(堆積)">[模板] Heap(堆積)</h1>
</a>
<div class="separator"></div>
<div class="info">
<i class="fas fa-tags"></i>
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Heap/">Heap</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/模板/">模板</a></li></ul>
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-09-24
</time>
</div>
</header>
<div class="content toc-article">
<h2 id="模板"><a href="#模板" class="headerlink" title="模板"></a>模板</h2><h3 id="Heap-主結構"><a href="#Heap-主結構" class="headerlink" title="Heap 主結構"></a>Heap 主結構</h3><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> HEAPSIZ 1024</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="comment">/* your data here */</span></span><br><span class="line">}Node;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> Node val[HEAPSIZ];</span><br><span class="line"> <span class="keyword">int</span> last;</span><br><span class="line">}Heap;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> <span class="title">cmp</span><span class="params">(<span class="keyword">register</span> <span class="keyword">const</span> Node* lhs, <span class="keyword">register</span> <span class="keyword">const</span> Node* rhs)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="comment">/* compare values here */</span></span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">swap</span><span class="params">(<span class="keyword">register</span> Node* lhs, <span class="keyword">register</span> Node* rhs)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> Node tmp = *lhs;</span><br><span class="line"> *lhs = *rhs, * rhs = tmp;</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">insNode</span><span class="params">(<span class="keyword">register</span> Heap* heap, <span class="keyword">register</span> Node val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> heap->val[++heap->_last] = val;</span><br><span class="line"> <span class="keyword">int</span> now = heap->_last, base = now >> <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span> (base && cmp(&heap->val[base], &heap->val[now]) < <span class="number">0</span>)</span><br><span class="line"> swap(&heap->val[now], &heap->val[base]), now >>= <span class="number">1</span>, base >>= <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">delNode</span><span class="params">(<span class="keyword">register</span> Heap* heap)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> swap(&heap->val[<span class="number">1</span>], &heap->val[heap->_last--]);</span><br><span class="line"> <span class="keyword">int</span> now = <span class="number">1</span>, derived = <span class="number">2</span>;</span><br><span class="line"> <span class="keyword">while</span> (derived <= heap->_last)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (cmp(&heap->val[derived], &heap->val[derived + <span class="number">1</span>]) < <span class="number">0</span> && derived < heap->_last) derived++;</span><br><span class="line"> <span class="keyword">if</span> (cmp(&heap->val[derived], &heap->val[now]) < <span class="number">0</span>) <span class="keyword">break</span>;</span><br><span class="line"> swap(&heap->val[derived], &heap->val[now]), now <<= <span class="number">1</span>, derived <<= <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<div class="hidden-content">
<hr>
<h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><p>本組模板為堆積模板，可以用來實現簡單的最大 / 最小堆。</p>
<h3 id="結構"><a href="#結構" class="headerlink" title="結構"></a>結構</h3><h4 id="Node"><a href="#Node" class="headerlink" title="Node"></a>Node</h4><p>本結構使用者自定義的資料，如果你只要使用編譯器預設的資料型態(int/double…)，你可以將 Node 直接定義成該型態</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Node;</span><br></pre></td></tr></table></figure>
<p>這樣在新增節點時會比較方便。</p>
<h4 id="Heap"><a href="#Heap" class="headerlink" title="Heap"></a>Heap</h4><p>本結構為堆積的主結構，使用他來宣告一個新的堆積，結構中的 _last 為保證結構正運作的必要參數，請不要任意更改它除非你清楚了解它的作用。</p>
<h3 id="函式"><a href="#函式" class="headerlink" title="函式"></a>函式</h3><h4 id="cmp"><a href="#cmp" class="headerlink" title="cmp()"></a>cmp()</h4><p>本函式為比較函式。</p>
<h5 id="參數"><a href="#參數" class="headerlink" title="參數"></a>參數</h5><h6 id="lhs-const-Node"><a href="#lhs-const-Node" class="headerlink" title="lhs (const Node*)"></a>lhs (const Node*)</h6><p>本參數為比較資料的左項。</p>
<h6 id="rhs-const-Node"><a href="#rhs-const-Node" class="headerlink" title="rhs (const Node*)"></a>rhs (const Node*)</h6><p>本參數為比較資料的右項。</p>
<h5 id="回傳值"><a href="#回傳值" class="headerlink" title="回傳值"></a>回傳值</h5><p>回傳比較後的結果。</p>
<h4 id="insNode"><a href="#insNode" class="headerlink" title="insNode()"></a>insNode()</h4><p>本函式會新增一筆資料至目標堆積。</p>
<h5 id="參數-1"><a href="#參數-1" class="headerlink" title="參數"></a>參數</h5><h6 id="heap-Heap"><a href="#heap-Heap" class="headerlink" title="heap (Heap*)"></a>heap (Heap*)</h6><p>本參數為目標堆積。</p>
<h6 id="val-Node"><a href="#val-Node" class="headerlink" title="val (Node)"></a>val (Node)</h6><p>本參數為存入目標堆積的元素。</p>
<h5 id="回傳值-1"><a href="#回傳值-1" class="headerlink" title="回傳值"></a>回傳值</h5><p>本函式無回傳值。</p>
<h4 id="delNode"><a href="#delNode" class="headerlink" title="delNode()"></a>delNode()</h4><p>本函式會將目標堆積頂端的元素刪除。</p>
<h5 id="參數-2"><a href="#參數-2" class="headerlink" title="參數"></a>參數</h5><h6 id="heap-Heap-1"><a href="#heap-Heap-1" class="headerlink" title="heap (Heap*)"></a>heap (Heap*)</h6><p>本參數為目標堆積。</p>
<h5 id="回傳值-2"><a href="#回傳值-2" class="headerlink" title="回傳值"></a>回傳值</h5><p>本函式無回傳值。</p>
<h3 id="其他"><a href="#其他" class="headerlink" title="其他"></a>其他</h3><h4 id="HEAPSIZ"><a href="#HEAPSIZ" class="headerlink" title="HEAPSIZ"></a>HEAPSIZ</h4><p>此巨集用來定義元素的數量上限。</p>
<h3 id="實例"><a href="#實例" class="headerlink" title="實例"></a>實例</h3><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> HEAPSIZ 1024</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> Node;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> Node val[HEAPSIZ];</span><br><span class="line"> <span class="keyword">int</span> _last;</span><br><span class="line">}Heap;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> <span class="title">cmp</span><span class="params">(<span class="keyword">register</span> <span class="keyword">const</span> Node* lhs, <span class="keyword">register</span> <span class="keyword">const</span> Node* rhs)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> *lhs - *rhs;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">swap</span><span class="params">(<span class="keyword">register</span> Node* lhs, <span class="keyword">register</span> Node* rhs)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> Node tmp = *lhs;</span><br><span class="line"> *lhs = *rhs, * rhs = tmp;</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">insNode</span><span class="params">(<span class="keyword">register</span> Heap* heap, <span class="keyword">register</span> Node val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> heap->val[++heap->_last] = val;</span><br><span class="line"> <span class="keyword">int</span> now = heap->_last, base = now >> <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span> (base && cmp(&heap->val[base], &heap->val[now]) < <span class="number">0</span>)</span><br><span class="line"> swap(&heap->val[now], &heap->val[base]), now >>= <span class="number">1</span>, base >>= <span class="number">1</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function">Node <span class="title">delNode</span><span class="params">(<span class="keyword">register</span> Heap* heap)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> swap(&heap->val[<span class="number">1</span>], &heap->val[heap->_last--]);</span><br><span class="line"> <span class="keyword">int</span> now = <span class="number">1</span>, derived = <span class="number">2</span>;</span><br><span class="line"> <span class="keyword">while</span> (derived <= heap->_last)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (cmp(&heap->val[derived], &heap->val[derived + <span class="number">1</span>]) < <span class="number">0</span> && derived < heap->_last) derived++;</span><br><span class="line"> <span class="keyword">if</span> (cmp(&heap->val[derived], &heap->val[now]) < <span class="number">0</span>) <span class="keyword">break</span>;</span><br><span class="line"> swap(&heap->val[derived], &heap->val[now]), now <<= <span class="number">1</span>, derived <<= <span class="number">1</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"><span class="function"></span>{</span><br><span class="line"> Heap heap = { <span class="number">0</span> };</span><br><span class="line"> insNode(&heap, <span class="number">5</span>);</span><br><span class="line"> insNode(&heap, <span class="number">9</span>);</span><br><span class="line"> insNode(&heap, <span class="number">1</span>);</span><br><span class="line"> insNode(&heap, <span class="number">9</span>);</span><br><span class="line"> insNode(&heap, <span class="number">7</span>);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, heap.val[<span class="number">1</span>]);</span><br><span class="line"> delNode(&heap);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, heap.val[<span class="number">1</span>]);</span><br><span class="line"> delNode(&heap);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, heap.val[<span class="number">1</span>]);</span><br><span class="line"> delNode(&heap);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, heap.val[<span class="number">1</span>]);</span><br><span class="line"> delNode(&heap);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, heap.val[<span class="number">1</span>]);</span><br><span class="line"> delNode(&heap);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h5 id="編譯運行結果"><a href="#編譯運行結果" class="headerlink" title="編譯運行結果"></a>編譯運行結果</h5><blockquote>
<p>9<br>9<br>7<br>5<br>1</p>
</blockquote>
<h2 id="注意事項"><a href="#注意事項" class="headerlink" title="注意事項"></a>注意事項</h2><ul>
<li><p>在區域變數裡宣告新的 Heap 時必須將其初始化</p>
<blockquote>
<p>Heap heap = { 0 };</p>
</blockquote>
<p>否則會因為存取違規而出現 runtime error;</p>
</li>
<li><p>測試階段，謹慎使用。</p>
</li>
</ul>
<h2 id="更新紀錄"><a href="#更新紀錄" class="headerlink" title="更新紀錄"></a>更新紀錄</h2><p>無</p>
</div>
</div>
<div class="more">
<a class="more-button" onclick="readMore()">閱讀更多</a>
</div>
</div>
</article>
<article id="[模板] Queue(佇列)" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/模板庫/" title="模板庫 (8)">
<div class="meta-list-link-text">
模板庫
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
[模板] Queue(佇列)
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/模板庫/Queue/">
<h1 class="title-text" title="[模板] Queue(佇列)">[模板] Queue(佇列)</h1>
</a>
<div class="separator"></div>
<div class="info">
<i class="fas fa-tags"></i>
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Queue/">Queue</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/模板/">模板</a></li></ul>
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-09-21
</time>
</div>
</header>
<div class="content toc-article">
<h2 id="模板"><a href="#模板" class="headerlink" title="模板"></a>模板</h2><h3 id="Queue-主結構"><a href="#Queue-主結構" class="headerlink" title="Queue 主結構"></a>Queue 主結構</h3><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ENTSIZ 1024</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">Data</span></span></span><br><span class="line"><span class="class"> {</span></span><br><span class="line"> <span class="comment">/* your data here */</span></span><br><span class="line"> };</span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">Node</span>* _<span class="title">next</span>;</span></span><br><span class="line">}Node;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> Node* front, * last;</span><br><span class="line">}Queue;</span><br><span class="line"></span><br><span class="line">Node entries[ENTSIZ], * entry = entries, * freeBuk;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">register</span> Queue* que, <span class="keyword">register</span> Node val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span> (freeBuk)</span><br><span class="line"> {</span><br><span class="line"> Node* tmp = freeBuk->_next;</span><br><span class="line"> *freeBuk = val, freeBuk->_next = <span class="literal">NULL</span>;</span><br><span class="line"> <span class="keyword">if</span> (que->last) que->last = que->last->_next = freeBuk;</span><br><span class="line"> <span class="keyword">else</span> que->front = que->last = freeBuk;</span><br><span class="line"> freeBuk = tmp;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> {</span><br><span class="line"> *entry = val;</span><br><span class="line"> <span class="keyword">if</span> (que->last) que->last = que->last->_next = entry++;</span><br><span class="line"> <span class="keyword">else</span> que->front = que->last = entry++;</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">inline</span> Node <span class="title">pop</span><span class="params">(<span class="keyword">register</span> Queue* que)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> Node* tmp = que->front;</span><br><span class="line"> que->front = que->front->_next;</span><br><span class="line"> tmp->_next = freeBuk;</span><br><span class="line"> <span class="keyword">return</span> *(freeBuk = tmp);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<div class="hidden-content">
<hr>
<h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><p>本組模板為佇列模板，在已知元素數量上限時使用此模板可以省去動態宣告記憶體的時間，本模板可同時宣告並使用複數個 <a href="/模板庫/Stack/">stack</a> 和 queue，而只須保證資料結構相同且元素總數不超過定義上限即可。</p>
<h3 id="結構"><a href="#結構" class="headerlink" title="結構"></a>結構</h3><h4 id="Node"><a href="#Node" class="headerlink" title="Node"></a>Node</h4><p>本結構為資料的進入點，其中 struct Data 為供使用者存取資料的結構，_next 則是保證結構正運作的必要參數，請不要任意更改它除非你清楚了解它的作用。</p>
<h4 id="Queue"><a href="#Queue" class="headerlink" title="Queue"></a>Queue</h4><p>本結構為佇列的主結構，使用他來宣告一個新的佇列，結構中的 front 和 last 指標分別恆指向該佇列的最前和最末端元素。</p>
<h3 id="函式"><a href="#函式" class="headerlink" title="函式"></a>函式</h3><h4 id="push"><a href="#push" class="headerlink" title="push()"></a>push()</h4><p>本函式會新增一筆資料至目標堆疊的最末端。</p>
<h5 id="參數"><a href="#參數" class="headerlink" title="參數"></a>參數</h5><h6 id="stk-Queue"><a href="#stk-Queue" class="headerlink" title="stk (Queue*)"></a>stk (Queue*)</h6><p>本參數為目標佇列。</p>
<h6 id="val-Node"><a href="#val-Node" class="headerlink" title="val (Node)"></a>val (Node)</h6><p>本參數為存入目標佇列最末端的元素。</p>
<h5 id="回傳值"><a href="#回傳值" class="headerlink" title="回傳值"></a>回傳值</h5><p>本函式無回傳值。</p>
<h4 id="pop"><a href="#pop" class="headerlink" title="pop()"></a>pop()</h4><p>本函式會將目標佇列最前端的資料取出並回傳該元素。</p>
<h6 id="stk-Queue-1"><a href="#stk-Queue-1" class="headerlink" title="stk (Queue*)"></a>stk (Queue*)</h6><p>本參數為目標佇列。</p>
<h5 id="回傳值-1"><a href="#回傳值-1" class="headerlink" title="回傳值"></a>回傳值</h5><p>本函式回傳目標佇列最前端的元素。</p>
<h3 id="其他"><a href="#其他" class="headerlink" title="其他"></a>其他</h3><h4 id="ENTSIZ"><a href="#ENTSIZ" class="headerlink" title="ENTSIZ"></a>ENTSIZ</h4><p>此巨集用來定義元素的數量上限。</p>
<h2 id="實例"><a href="#實例" class="headerlink" title="實例"></a>實例</h2><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ENTSIZ 1024</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">Data</span></span></span><br><span class="line"><span class="class"> {</span></span><br><span class="line"> <span class="keyword">int</span> a, b;</span><br><span class="line"> };</span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">Node</span>* _<span class="title">next</span>;</span></span><br><span class="line">}Node;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> Node* front, * last;</span><br><span class="line">}Queue;</span><br><span class="line"></span><br><span class="line">Node entries[ENTSIZ], * entry = entries, * freeBuk;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">register</span> Queue* que, <span class="keyword">register</span> Node val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span> (freeBuk)</span><br><span class="line"> {</span><br><span class="line"> Node* tmp = freeBuk->_next;</span><br><span class="line"> *freeBuk = val, freeBuk->_next = <span class="literal">NULL</span>;</span><br><span class="line"> <span class="keyword">if</span> (que->last) que->last = que->last->_next = freeBuk;</span><br><span class="line"> <span class="keyword">else</span> que->front = que->last = freeBuk;</span><br><span class="line"> freeBuk = tmp;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> {</span><br><span class="line"> *entry = val;</span><br><span class="line"> <span class="keyword">if</span> (que->last) que->last = que->last->_next = entry++;</span><br><span class="line"> <span class="keyword">else</span> que->front = que->last = entry++;</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">inline</span> Node <span class="title">pop</span><span class="params">(<span class="keyword">register</span> Queue* que)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> Node* tmp = que->front;</span><br><span class="line"> que->front = que->front->_next;</span><br><span class="line"> tmp->_next = freeBuk;</span><br><span class="line"> <span class="keyword">return</span> *(freeBuk = tmp);</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="function"></span>{</span><br><span class="line"> Queue <span class="built_in">queue</span> = { <span class="number">0</span> };</span><br><span class="line"> Node n = { <span class="number">0</span>, <span class="number">1</span> };</span><br><span class="line"> push(&<span class="built_in">queue</span>, n);</span><br><span class="line"> n.b = <span class="number">2</span>;</span><br><span class="line"> push(&<span class="built_in">queue</span>, n);</span><br><span class="line"> push(&<span class="built_in">queue</span>, pop(&<span class="built_in">queue</span>));</span><br><span class="line"> n.b = <span class="number">3</span>;</span><br><span class="line"> push(&<span class="built_in">queue</span>, n);</span><br><span class="line"> n = pop(&<span class="built_in">queue</span>);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d,%d\n"</span>, n.a, n.b);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d,%d\n"</span>, <span class="built_in">queue</span>.front->a, <span class="built_in">queue</span>.front->b);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d,%d\n"</span>, <span class="built_in">queue</span>.last->a, <span class="built_in">queue</span>.last->b);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h5 id="編譯運行結果"><a href="#編譯運行結果" class="headerlink" title="編譯運行結果"></a>編譯運行結果</h5><blockquote>
<p>0,2<br>0,1<br>0,3</p>
</blockquote>
<h2 id="注意事項"><a href="#注意事項" class="headerlink" title="注意事項"></a>注意事項</h2><ul>
<li><p>如果自定義資料較大，你應該將存取方式改為使用指標，並透過映射的方式存取資料來減少記憶體的操作次數。</p>
</li>
<li><p>在區域變數裡宣告新的 Queue 時必須將其初始化</p>
<blockquote>
<p>Queue queue = { 0 };</p>
</blockquote>
<p>否則會因為存取違規而出現 runtime error;</p>
</li>
<li><p>如果要同時使用 Stack 和 Queue，請將兩者的 push() 和 pop() 函式用不同名字區隔開來。</p>
</li>
<li><p>測試階段，謹慎使用。</p>
</li>
</ul>
<h2 id="更新紀錄"><a href="#更新紀錄" class="headerlink" title="更新紀錄"></a>更新紀錄</h2><p>無</p>
</div>
</div>
<div class="more">
<a class="more-button" onclick="readMore()">閱讀更多</a>
</div>
</div>
</article>
<article id="[模板] Stack(堆疊)" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/模板庫/" title="模板庫 (8)">
<div class="meta-list-link-text">
模板庫
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
[模板] Stack(堆疊)
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/模板庫/Stack/">
<h1 class="title-text" title="[模板] Stack(堆疊)">[模板] Stack(堆疊)</h1>
</a>
<div class="separator"></div>
<div class="info">
<i class="fas fa-tags"></i>
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Stack/">Stack</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/模板/">模板</a></li></ul>
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-09-20
</time>
</div>
</header>
<div class="content toc-article">
<h2 id="模板"><a href="#模板" class="headerlink" title="模板"></a>模板</h2><h3 id="Stack-主結構"><a href="#Stack-主結構" class="headerlink" title="Stack 主結構"></a>Stack 主結構</h3><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ENTSIZ 1024</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">Data</span></span></span><br><span class="line"><span class="class"> {</span></span><br><span class="line"> <span class="comment">/* your data here */</span></span><br><span class="line"> };</span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">Node</span>* _<span class="title">next</span>;</span></span><br><span class="line">}Node;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> Node* top;</span><br><span class="line">}Stack;</span><br><span class="line"></span><br><span class="line">Node entries[ENTSIZ], * entry = entries, * freeBuk;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">register</span> Stack* stk, <span class="keyword">register</span> Node val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span> (freeBuk)</span><br><span class="line"> {</span><br><span class="line"> Node* tmp = freeBuk->_next;</span><br><span class="line"> *freeBuk = val, freeBuk->_next = stk->top;</span><br><span class="line"> stk->top = freeBuk;</span><br><span class="line"> freeBuk = tmp;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> {</span><br><span class="line"> *entry = val, entry->_next = stk->top;</span><br><span class="line"> stk->top = entry++;</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">inline</span> Node <span class="title">pop</span><span class="params">(<span class="keyword">register</span> Stack* stk)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> Node* tmp = stk->top;</span><br><span class="line"> stk->top = stk->top->_next;</span><br><span class="line"> tmp->_next = freeBuk;</span><br><span class="line"> <span class="keyword">return</span> *(freeBuk = tmp);</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<div class="hidden-content">
<hr>
<h2 id="概述"><a href="#概述" class="headerlink" title="概述"></a>概述</h2><p>本組模板為堆疊模板，在已知元素數量上限時使用此模板可以省去動態宣告記憶體的時間，本模板可同時宣告並使用複數個 stack 和 <a href="/模板庫/Queue/">queue</a>，而只須保證資料結構相同且元素總數不超過定義上限即可。</p>
<h3 id="結構"><a href="#結構" class="headerlink" title="結構"></a>結構</h3><h4 id="Node"><a href="#Node" class="headerlink" title="Node"></a>Node</h4><p>本結構為資料的進入點，其中 struct Data 為供使用者存取資料的結構，_next 則是保證結構正運作的必要參數，請不要任意更改它除非你清楚了解它的作用。</p>
<h4 id="Stack"><a href="#Stack" class="headerlink" title="Stack"></a>Stack</h4><p>本結構為堆疊的主結構，使用他來宣告一個新的堆疊，結構中的 top 指標恆指向該堆疊最頂端的元素。</p>
<h3 id="函式"><a href="#函式" class="headerlink" title="函式"></a>函式</h3><h4 id="push"><a href="#push" class="headerlink" title="push()"></a>push()</h4><p>本函式會新增一筆資料至目標堆疊的頂端。</p>
<h5 id="參數"><a href="#參數" class="headerlink" title="參數"></a>參數</h5><h6 id="stk-Stack"><a href="#stk-Stack" class="headerlink" title="stk (Stack*)"></a>stk (Stack*)</h6><p>本參數為目標堆疊。</p>
<h6 id="val-Node"><a href="#val-Node" class="headerlink" title="val (Node)"></a>val (Node)</h6><p>本參數為存入目標堆疊頂層的元素。</p>
<h5 id="回傳值"><a href="#回傳值" class="headerlink" title="回傳值"></a>回傳值</h5><p>本函式無回傳值。</p>
<h4 id="pop"><a href="#pop" class="headerlink" title="pop()"></a>pop()</h4><p>本函式會將目標堆疊頂層的資料取出並回傳該元素。</p>
<h6 id="stk-Stack-1"><a href="#stk-Stack-1" class="headerlink" title="stk (Stack*)"></a>stk (Stack*)</h6><p>本參數為目標堆疊。</p>
<h5 id="回傳值-1"><a href="#回傳值-1" class="headerlink" title="回傳值"></a>回傳值</h5><p>本函式回傳目標堆疊頂層元素。</p>
<h3 id="其他"><a href="#其他" class="headerlink" title="其他"></a>其他</h3><h4 id="ENTSIZ"><a href="#ENTSIZ" class="headerlink" title="ENTSIZ"></a>ENTSIZ</h4><p>此巨集用來定義元素的數量上限。</p>
<h3 id="實例"><a href="#實例" class="headerlink" title="實例"></a>實例</h3><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ENTSIZ 1024</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">Data</span></span></span><br><span class="line"><span class="class"> {</span></span><br><span class="line"> <span class="keyword">int</span> a, b;</span><br><span class="line"> };</span><br><span class="line"> <span class="class"><span class="keyword">struct</span> <span class="title">Node</span>* _<span class="title">next</span>;</span></span><br><span class="line">}Node;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> Node* top;</span><br><span class="line">}Stack;</span><br><span class="line"></span><br><span class="line">Node entries[ENTSIZ], * entry = entries, * freeBuk;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">push</span><span class="params">(<span class="keyword">register</span> Stack* stk, <span class="keyword">register</span> Node val)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span> (freeBuk)</span><br><span class="line"> {</span><br><span class="line"> Node* tmp = freeBuk->_next;</span><br><span class="line"> *freeBuk = val, freeBuk->_next = stk->top;</span><br><span class="line"> stk->top = freeBuk;</span><br><span class="line"> freeBuk = tmp;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> {</span><br><span class="line"> *entry = val, entry->_next = stk->top;</span><br><span class="line"> stk->top = entry++;</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">inline</span> Node <span class="title">pop</span><span class="params">(<span class="keyword">register</span> Stack* stk)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> Node* tmp = stk->top;</span><br><span class="line"> stk->top = stk->top->_next;</span><br><span class="line"> tmp->_next = freeBuk;</span><br><span class="line"> <span class="keyword">return</span> *(freeBuk = tmp);</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="function"></span>{</span><br><span class="line"> Stack stack1 = { <span class="number">0</span> }, stack2 = { <span class="number">0</span> };</span><br><span class="line"> Node n = { <span class="number">0</span>, <span class="number">1</span> };</span><br><span class="line"> push(&stack1, n);</span><br><span class="line"> n.b = <span class="number">2</span>;</span><br><span class="line"> push(&stack2, n);</span><br><span class="line"> push(&stack1, pop(&stack2));</span><br><span class="line"> n = pop(&stack1);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d,%d\n"</span>, n.a, n.b);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d,%d\n"</span>, stack1.top->a, stack1.top->b);</span><br><span class="line"> n = pop(&stack1);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d,%d"</span>, n.a, n.b);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h5 id="編譯運行結果"><a href="#編譯運行結果" class="headerlink" title="編譯運行結果"></a>編譯運行結果</h5><blockquote>
<p>0,2<br>0,1<br>0,1</p>
</blockquote>
<h2 id="注意事項"><a href="#注意事項" class="headerlink" title="注意事項"></a>注意事項</h2><ul>
<li>如果自定義資料較大，你應該將存取方式改為使用指標，並透過映射的方式存取資料來減少記憶體的操作次數。</li>
<li>如果要同時使用 Stack 和 Queue，請將兩者的 push() 和 pop() 函式用不同名字區隔開來。</li>
<li>測試階段，謹慎使用。</li>
</ul>
<h2 id="更新紀錄"><a href="#更新紀錄" class="headerlink" title="更新紀錄"></a>更新紀錄</h2><h5 id="2019-9-21"><a href="#2019-9-21" class="headerlink" title="2019-9-21"></a>2019-9-21</h5><ul>
<li>調整運作結構使其能和 Queue 混用同一塊記憶體 (在資料結構相同的情況)</li>
<li>優化 pop()，現在比之前少執行一行命令。</li>
</ul>
</div>
</div>
<div class="more">
<a class="more-button" onclick="readMore()">閱讀更多</a>
</div>
</div>
</article>
<article id=" 模板列表" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/模板庫/" title="模板庫 (8)">
<div class="meta-list-link-text">
模板庫
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
模板列表
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/模板庫/模板列表/">
<h1 class="title-text" title=" 模板列表"> 模板列表</h1>
</a>
<div class="separator"></div>
<div class="info">
<i class="fas fa-tags"></i>
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/模板/">模板</a></li></ul>
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-08-27
</time>
</div>
</header>
<div class="content">
<h2 id="字串處理"><a href="#字串處理" class="headerlink" title="字串處理"></a>字串處理</h2><h5 id="字串取值"><a href="#字串取值" class="headerlink" title="字串取值"></a><a href="/模板庫/字串取值/">字串取值</a></h5><p>本組模板為字串轉數字模板，使用此模板取代 sscanf() 可以大幅減少從字串取得數組的時間，此外本模板內建指針偏移，可以節省使用 strlen() 偏移指針的開銷。</p>
<h5 id="字串賦值"><a href="#字串賦值" class="headerlink" title="字串賦值"></a><a href="/模板庫/字串賦值/">字串賦值</a></h5><p>本組模板為整數轉字串模板，使用此模板取代 sprintf() 可以大幅將整數打印到字串的時間，此外本模板內建指針偏移，可以節省使用 strlen() 偏移指針的開銷。</p>
<h2 id="IO-優化"><a href="#IO-優化" class="headerlink" title="IO 優化"></a>IO 優化</h2><h5 id="輸入優化"><a href="#輸入優化" class="headerlink" title="輸入優化"></a><a href="/模板庫/輸入優化/">輸入優化</a></h5><p>本組模板為輸入優化模板，使用此模板取代 scanf() 可以大幅減少從資料流取得數組的時間。</p>
<h5 id="輸出優化"><a href="#輸出優化" class="headerlink" title="輸出優化"></a><a href="/模板庫/輸出優化/">輸出優化</a></h5><p>本組模板為輸出優化模板，使用此模板取代 printf() 可以大幅印出資料的時間。</p>
<h2 id="資料結構"><a href="#資料結構" class="headerlink" title="資料結構"></a>資料結構</h2><h5 id="Stack-堆疊"><a href="#Stack-堆疊" class="headerlink" title="Stack(堆疊)"></a><a href="/模板庫/Stack/">Stack(堆疊)</a></h5><p>本組模板為堆疊模板，在已知元素數量上限時使用此模板可以省去動態宣告記憶體的時間。</p>
<h5 id="Queue-佇列"><a href="#Queue-佇列" class="headerlink" title="Queue(佇列)"></a><a href="/模板庫/Queue/">Queue(佇列)</a></h5><p>本組模板為佇列模板，在已知元素數量上限時使用此模板可以省去動態宣告記憶體的時間。</p>
</div>
</div>
</article>
<article id="Win10 改變標題列顏色" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
Win10 改變標題列顏色
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/uncategorized/Win10 改變標題列顏色/">
<h1 class="title-text" title="Win10 改變標題列顏色">Win10 改變標題列顏色</h1>
</a>
<div class="separator"></div>
<div class="info">
<i class="fas fa-tags"></i>
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/Windows/">Windows</a></li></ul>
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-09-18
</time>
</div>
</header>
<div class="content">
<p>重灌完電腦發現以前用的登錄檔不見了，google 又充滿了只能改聚焦視窗標題列顏色的複製文，嚇得我趕緊寫一篇文章備份壓壓驚。</p>
<h2 id="步驟"><a href="#步驟" class="headerlink" title="步驟"></a>步驟</h2><ol>
<li><p>Win + R 輸入 regedit 開啟登錄檔編輯程式</p>
</li>
<li><p>移動至 HKEY_CURRENT_USER\Software\Microsoft\Windows\DWM</p>
</li>
<li><p>找到 AccentColor 和 AccentColorInactive，這兩個值分別代表聚焦視窗和非聚焦視窗的標題列顏色，如果沒有就新增一個同名的 dword。</p>
</li>
<li><p>修改數值成喜歡的顏色即可。</p>
</li>
</ol>
<h2 id="經典藍登錄檔"><a href="#經典藍登錄檔" class="headerlink" title="經典藍登錄檔"></a>經典藍登錄檔</h2><p>這裡提供一個回復成 WIN10 早期標題列皆為藍色的登錄檔，將以下文字複製進記事本並將副檔名儲存為.reg，雙擊該登錄檔(.reg)即可。</p>
<figure class="highlight plain"><table><tr><td class="code"><pre><span class="line">Windows Registry Editor Version 5.00</span><br><span class="line"></span><br><span class="line">[HKEY_CURRENT_USER\Software\Microsoft\Windows\DWM]</span><br><span class="line">"Composition"=dword:00000001</span><br><span class="line">"ColorizationColor"=dword:c40078d7</span><br><span class="line">"ColorizationColorBalance"=dword:00000059</span><br><span class="line">"ColorizationAfterglow"=dword:c40078d7</span><br><span class="line">"ColorizationAfterglowBalance"=dword:0000000a</span><br><span class="line">"ColorizationBlurBalance"=dword:00000001</span><br><span class="line">"ColorizationGlassAttribute"=dword:00000001</span><br><span class="line">"AccentColor"=dword:ffd77800</span><br><span class="line">"ColorPrevalence"=dword:00000001</span><br><span class="line">"EnableAeroPeek"=dword:00000001</span><br><span class="line">"EnableWindowColorization"=dword:00000001</span><br><span class="line">"AccentColorInactive"=dword:ffd77800</span><br></pre></td></tr></table></figure>
<p>參考資料：<a href="https://www.winhelponline.com/blog/change-inactive-title-bar-color-windows-10/" target="_blank" rel="noopener">https://www.winhelponline.com/blog/change-inactive-title-bar-color-windows-10/</a></p>
</div>
</div>
</article>
<article id="b237: CSAPC'09 迷宮任務" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/" title="線上解題 (252)">
<div class="meta-list-link-text">
線上解題
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/ZeroJudge/" title="ZeroJudge (251)">
<div class="meta-list-link-text">
ZeroJudge
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
b237: CSAPC'09 迷宮任務
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/線上解題/ZeroJudge/b237/">
<h1 class="title-text" title="b237: CSAPC'09 迷宮任務">b237: CSAPC'09 迷宮任務</h1>
</a>
<div class="separator"></div>
<div class="info">
<i class="fas fa-tags"></i>
<ul class="tag-list"><li class="tag-list-item"><a class="tag-list-link" href="/tags/DFS/">DFS</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/LCA/">LCA</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/Tarjan/">Tarjan</a></li><li class="tag-list-item"><a class="tag-list-link" href="/tags/並查集/">並查集</a></li></ul>
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-09-11
</time>
</div>
</header>
<div class="content toc-article">
<h2 id="內容"><a href="#內容" class="headerlink" title="內容"></a>內容</h2><p>在一個 n 乘以 m 大小的迷宮當中，你必須依序執行很多項搬東西的任務。每一個任務都有起始點 A 以及終點 B 。行動的時候如果手上沒有搬東西，就不會耗費任何體力，但是如果手上有東西，那麼耗費的體力就是以移動「一格」消耗一單位的體力來計算。而所謂移動「一格」是指從目前迷宮中的位置往東、南、西、北四個方向前進一步的長度。有趣的是，經過你的縝密觀察，儘管迷宮內部相當複雜，它一定會遵守「右手定則」，也就是說，只要摸著右手邊的牆壁不斷地往前行走，終究可以踏遍迷宮中的每一塊空地，並且連所有空地周圍看得到的圍牆部分都被你摸過了。聰明的你在執行每一個任務的時候，都會挑選最短路徑搬運指定物品。請問執行完所有任務以後你所需要耗費的最少體力總和是多少？</p>
<hr>
<h2 id="輸入"><a href="#輸入" class="headerlink" title="輸入"></a>輸入</h2><p>輸入的第一行包含三個正整數 n, m, Q 。接下來我們用 n 列(rows)每一列以 m 個字元來表示迷宮。迷宮內部標註 ‘.’ 的部份是空地，標記 ‘#’ 的部份是牆。迷宮最外圍一定都是牆壁。接下來有 Q 列分別代表 Q 項任務的起點和終點，每一列包含四個整數 x, y, z, w ，代表每一項任務從 (x, y) 出發，並且在 (z, w) 結束。注意到迷宮的編號方式以左上角為 (0, 0) ，右下角為 (n-1, m-1) 。你可以假設輸入的所有座標都會是空地的座標。 迷宮裡面不會有 2x2 的空地出現。 (edit: 11/16 10:17am)</p>
<blockquote>
<p>10 10 6<br>##########<br>#......#.#<br>#####.#..#<br>#####...##<br>###.#.#.##<br>###.#.#..#<br>##...#..##<br>##.#..#.##<br>#...#....#<br>##########<br>1 1 1 1<br>3 6 1 3<br>3 6 6 3<br>2 8 2 5<br>2 5 2 8<br>7 4 6 2</p>
</blockquote>
<h2 id="輸出"><a href="#輸出" class="headerlink" title="輸出"></a>輸出</h2><p>請輸出依序執行完所有任務後所需要耗費的最小體力。</p>
<blockquote>
<p>30</p>
</blockquote>
<hr>
<h2 id="解題思路"><a href="#解題思路" class="headerlink" title="解題思路"></a>解題思路</h2><p>因為題目保證"迷宮裡面不會有 2x2 的空地出現"所以可以將這個迷宮視為一個樹，而在一個樹狀結構中點到點的距離會是</p>
<blockquote>
<p>點 a 到 LCA<sup><a href="#1">[1]</a></sup>(a,b) 的距離 + 點 b 到 LCA(a,b) 的距離</p>
</blockquote>
<p>而這兩者相加亦會等於</p>
<blockquote>
<p>點 a 到 根的距離 + 點 B 到 根的距離 - LCA(a,b)到根的距離 * 2</p>
</blockquote>
<p>所以說只要知道 a , b 和 LCA(a,b) 與根的相對深度就能求出答案了。</p>
<p>但由於本題詢問量很大，如果每次詢問都一個一個找時間複雜度為</p>
<blockquote>
<p>O(q*(a+b))) q = 詢問數， a(b) = 各詢問中點 a(b) 到 LCA(a,b) 的距離</p>
</blockquote>
<p>這樣會花費太多時間，所以改用離線 Tarjan 演算法配合並查集先找出所有點對點的 LCA ，之後只需要 O(1) 的時間就可以完成查詢。</p>
<p>但是本題範圍較大，建立 LCA 表記憶體會不夠用，所以改成先把所有查詢紀錄起來，之後再一邊遍歷節點一邊計算答案，遍歷結束後輸出答案即可。</p>
<ul>
<li>本題各測資點皆只有一筆測資，輸入量不小</li>
<li>程式碼中 tarjan() 不需判斷是否被遍歷過是因為在建立的時候已經將多餘的情況給過濾掉了。</li>
</ul>
<h3 id="註解"><a href="#註解" class="headerlink" title="註解"></a>註解</h3><ol>
<li><span id="1">LCA = Lowest Common Ancestor = 最低共同祖先</span></li>
</ol>
<h3 id="參考資料"><a href="#參考資料" class="headerlink" title="參考資料"></a>參考資料</h3><ul>
<li>Tarjan 演算法 : <a href="https://www.itread01.com/content/1562417763.html" target="_blank" rel="noopener">演算法詳解之最近公共祖先(LCA)</a></li>
</ul>
<div class="hidden-content">
<hr>
<h2 id="完整程式碼"><a href="#完整程式碼" class="headerlink" title="完整程式碼"></a>完整程式碼</h2><h3 id="正常版"><a href="#正常版" class="headerlink" title="正常版"></a>正常版</h3><h6 id="AC-22ms-3-6MB"><a href="#AC-22ms-3-6MB" class="headerlink" title="AC (22ms, 3.6MB)"></a>AC (22ms, 3.6MB)</h6><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX 255</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX2 62500</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> val[<span class="number">4</span>], * top;</span><br><span class="line">}Stack;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> val, next;</span><br><span class="line">}Query;</span><br><span class="line"></span><br><span class="line">Stack <span class="built_in">list</span>[MAX2];</span><br><span class="line">Query qList[<span class="number">50005</span>];</span><br><span class="line"><span class="keyword">int</span> <span class="built_in">map</span>[MAX][MAX], parent[MAX2], query[MAX2], depth[MAX2],sum, len, qTop;</span><br><span class="line"><span class="keyword">char</span> input[MAX][MAX];</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> i, <span class="keyword">int</span> j, <span class="keyword">int</span> dep)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> idx = ++len;</span><br><span class="line"> parent[idx] = <span class="built_in">map</span>[i][j] = idx;</span><br><span class="line"> depth[idx] = dep;</span><br><span class="line"> <span class="built_in">list</span>[idx].top = <span class="built_in">list</span>[idx].val;</span><br><span class="line"> <span class="keyword">if</span> (input[i + <span class="number">1</span>][j] == <span class="string">'.'</span> && !<span class="built_in">map</span>[i + <span class="number">1</span>][j])</span><br><span class="line"> dfs(i + <span class="number">1</span>, j, dep + <span class="number">1</span>), * <span class="built_in">list</span>[idx].top++ = <span class="built_in">map</span>[i + <span class="number">1</span>][j];</span><br><span class="line"> <span class="keyword">if</span> (input[i - <span class="number">1</span>][j] == <span class="string">'.'</span> && !<span class="built_in">map</span>[i - <span class="number">1</span>][j])</span><br><span class="line"> dfs(i - <span class="number">1</span>, j, dep + <span class="number">1</span>), * <span class="built_in">list</span>[idx].top++ = <span class="built_in">map</span>[i - <span class="number">1</span>][j];</span><br><span class="line"> <span class="keyword">if</span> (input[i][j + <span class="number">1</span>] == <span class="string">'.'</span> && !<span class="built_in">map</span>[i][j + <span class="number">1</span>])</span><br><span class="line"> dfs(i, j + <span class="number">1</span>, dep + <span class="number">1</span>), * <span class="built_in">list</span>[idx].top++ = <span class="built_in">map</span>[i][j + <span class="number">1</span>];</span><br><span class="line"> <span class="keyword">if</span> (input[i][j - <span class="number">1</span>] == <span class="string">'.'</span> && !<span class="built_in">map</span>[i][j - <span class="number">1</span>])</span><br><span class="line"> dfs(i, j - <span class="number">1</span>, dep + <span class="number">1</span>), * <span class="built_in">list</span>[idx].top++ = <span class="built_in">map</span>[i][j - <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">inline</span> <span class="keyword">void</span> <span class="title">setDepth</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < n; j++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (input[i][j] == <span class="string">'.'</span>)</span><br><span class="line"> {</span><br><span class="line"> dfs(i, j, <span class="number">0</span>);</span><br><span class="line"> <span class="keyword">return</span>;</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><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">addQuery</span><span class="params">(<span class="keyword">int</span> from, <span class="keyword">int</span> to)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> qTop++;</span><br><span class="line"> qList[qTop].val = to;</span><br><span class="line"> qList[qTop].next = query[from];</span><br><span class="line"> query[from] = qTop;</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">find</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> i == parent[i] ? i : (parent[i] = find(parent[i]));</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">tarjan</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span> (Query* j = &qList[query[i]]; j->val; j = &qList[j->next])</span><br><span class="line"> sum += depth[i] + depth[j->val] - (depth[find(j->val)] << <span class="number">1</span>);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span>* j = <span class="built_in">list</span>[i].val; j < <span class="built_in">list</span>[i].top; j++)</span><br><span class="line"> {</span><br><span class="line"> tarjan(*j);</span><br><span class="line"> parent[*j] = 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"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m, q, sX, sY, eX, eY, s, e;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">" %d %d %d"</span>, &n, &m, &q);</span><br><span class="line"> getchar();</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>, idx = <span class="number">0</span>; i < n; i++)</span><br><span class="line"> gets(input[i]);</span><br><span class="line"> setDepth(n, m);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < q; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">" %d %d %d %d"</span>, &sX, &sY, &eX, &eY);</span><br><span class="line"> s = <span class="built_in">map</span>[sX][sY], e = <span class="built_in">map</span>[eX][eY];</span><br><span class="line"> <span class="keyword">if</span> (s < e)</span><br><span class="line"> addQuery(e, s);</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> addQuery(s, e);</span><br><span class="line"> }</span><br><span class="line"> tarjan(<span class="number">1</span>);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, sum);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h3 id="輸入優化版"><a href="#輸入優化版" class="headerlink" title="輸入優化版"></a>輸入優化版</h3><h6 id="AC-8ms-4-3MB"><a href="#AC-8ms-4-3MB" class="headerlink" title="AC (8ms, 4.3MB)"></a>AC (8ms, 4.3MB)</h6><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX 255</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX2 62500</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> BUFSIZ 1048576</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> val[<span class="number">4</span>], * top;</span><br><span class="line">}Stack;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> val, next;</span><br><span class="line">}Query;</span><br><span class="line"></span><br><span class="line">Stack <span class="built_in">list</span>[MAX2];</span><br><span class="line">Query qList[<span class="number">50005</span>];</span><br><span class="line"><span class="keyword">int</span> <span class="built_in">map</span>[MAX][MAX], parent[MAX2], query[MAX2], depth[MAX2], sum, len, qTop;</span><br><span class="line"><span class="keyword">char</span> input[MAX][MAX];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">char</span> <span class="title">readChar</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">static</span> <span class="keyword">char</span> buffer[BUFSIZ], * now = buffer + BUFSIZ, * end = buffer + BUFSIZ;</span><br><span class="line"> <span class="keyword">if</span> (now == end)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (end < buffer + BUFSIZ)</span><br><span class="line"> <span class="keyword">return</span> EOF;</span><br><span class="line"> end = (buffer + fread(buffer, <span class="number">1</span>, BUFSIZ, <span class="built_in">stdin</span>));</span><br><span class="line"> now = buffer;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> *now++;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">char</span> <span class="title">readString</span><span class="params">(<span class="keyword">register</span> <span class="keyword">unsigned</span> <span class="keyword">char</span>* dst)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">register</span> <span class="keyword">char</span> ch;</span><br><span class="line"> <span class="keyword">while</span> ((ch = readChar()) <= <span class="string">' '</span>)</span><br><span class="line"> <span class="keyword">if</span> (ch == EOF) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> *dst++ = ch;</span><br><span class="line"> <span class="keyword">while</span> ((ch = readChar()) > <span class="string">' '</span>)</span><br><span class="line"> * dst++ = ch;</span><br><span class="line"> <span class="keyword">return</span> <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">inline</span> <span class="keyword">char</span> <span class="title">readUInt</span><span class="params">(<span class="keyword">register</span> <span class="keyword">unsigned</span> <span class="keyword">int</span>* dst)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">register</span> <span class="keyword">char</span> ch;</span><br><span class="line"> <span class="keyword">while</span> ((ch = readChar()) < <span class="string">'0'</span>)</span><br><span class="line"> <span class="keyword">if</span> (ch == EOF) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> *dst = ch ^ <span class="string">'0'</span>;</span><br><span class="line"> <span class="keyword">while</span> ((ch = readChar()) >= <span class="string">'0'</span>)</span><br><span class="line"> * dst = (*dst << <span class="number">3</span>) + (*dst << <span class="number">1</span>) + (ch ^ <span class="string">'0'</span>);</span><br><span class="line"> <span class="keyword">return</span> <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">dfs</span><span class="params">(<span class="keyword">int</span> i, <span class="keyword">int</span> j, <span class="keyword">int</span> dep)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> idx = ++len;</span><br><span class="line"> parent[idx] = <span class="built_in">map</span>[i][j] = idx;</span><br><span class="line"> depth[idx] = dep;</span><br><span class="line"> <span class="built_in">list</span>[idx].top = <span class="built_in">list</span>[idx].val;</span><br><span class="line"> <span class="keyword">if</span> (input[i + <span class="number">1</span>][j] == <span class="string">'.'</span> && !<span class="built_in">map</span>[i + <span class="number">1</span>][j])</span><br><span class="line"> dfs(i + <span class="number">1</span>, j, dep + <span class="number">1</span>), * <span class="built_in">list</span>[idx].top++ = <span class="built_in">map</span>[i + <span class="number">1</span>][j];</span><br><span class="line"> <span class="keyword">if</span> (input[i - <span class="number">1</span>][j] == <span class="string">'.'</span> && !<span class="built_in">map</span>[i - <span class="number">1</span>][j])</span><br><span class="line"> dfs(i - <span class="number">1</span>, j, dep + <span class="number">1</span>), * <span class="built_in">list</span>[idx].top++ = <span class="built_in">map</span>[i - <span class="number">1</span>][j];</span><br><span class="line"> <span class="keyword">if</span> (input[i][j + <span class="number">1</span>] == <span class="string">'.'</span> && !<span class="built_in">map</span>[i][j + <span class="number">1</span>])</span><br><span class="line"> dfs(i, j + <span class="number">1</span>, dep + <span class="number">1</span>), * <span class="built_in">list</span>[idx].top++ = <span class="built_in">map</span>[i][j + <span class="number">1</span>];</span><br><span class="line"> <span class="keyword">if</span> (input[i][j - <span class="number">1</span>] == <span class="string">'.'</span> && !<span class="built_in">map</span>[i][j - <span class="number">1</span>])</span><br><span class="line"> dfs(i, j - <span class="number">1</span>, dep + <span class="number">1</span>), * <span class="built_in">list</span>[idx].top++ = <span class="built_in">map</span>[i][j - <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">inline</span> <span class="keyword">void</span> <span class="title">setDepth</span><span class="params">(<span class="keyword">int</span> n, <span class="keyword">int</span> m)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < n; j++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (input[i][j] == <span class="string">'.'</span>)</span><br><span class="line"> {</span><br><span class="line"> dfs(i, j, <span class="number">0</span>);</span><br><span class="line"> <span class="keyword">return</span>;</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><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">addQuery</span><span class="params">(<span class="keyword">int</span> from, <span class="keyword">int</span> to)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> qTop++;</span><br><span class="line"> qList[qTop].val = to;</span><br><span class="line"> qList[qTop].next = query[from];</span><br><span class="line"> query[from] = qTop;</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">find</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> i == parent[i] ? i : (parent[i] = find(parent[i]));</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">tarjan</span><span class="params">(<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">for</span> (Query* j = &qList[query[i]]; j->val; j = &qList[j->next])</span><br><span class="line"> sum += depth[i] + depth[j->val] - (depth[find(j->val)] << <span class="number">1</span>);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span>* j = <span class="built_in">list</span>[i].val; j < <span class="built_in">list</span>[i].top; j++)</span><br><span class="line"> {</span><br><span class="line"> tarjan(*j);</span><br><span class="line"> parent[*j] = 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"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n, m, q, sX, sY, eX, eY, s, e;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">" %d %d %d"</span>, &n, &m, &q);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>, idx = <span class="number">0</span>; i < n; i++)</span><br><span class="line"> readString(input[i]);</span><br><span class="line"> setDepth(n, m);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < q; i++)</span><br><span class="line"> {</span><br><span class="line"> readUInt(&sX), readUInt(&sY);</span><br><span class="line"> readUInt(&eX), readUInt(&eY);</span><br><span class="line"> s = <span class="built_in">map</span>[sX][sY], e = <span class="built_in">map</span>[eX][eY];</span><br><span class="line"> <span class="keyword">if</span> (s < e)</span><br><span class="line"> addQuery(e, s);</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> addQuery(s, e);</span><br><span class="line"> }</span><br><span class="line"> tarjan(<span class="number">1</span>);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, sum);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
</div>
<div class="more">
<a class="more-button" onclick="readMore()">閱讀更多</a>
</div>
</div>
</article>
<article id="b519: 撲克牌遊戲-商競103" class="post">
<div class="post-meta">
<ul class="meta-list">
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/" title="線上解題 (252)">
<div class="meta-list-link-text">
線上解題
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link" href="/categories/線上解題/ZeroJudge/" title="ZeroJudge (251)">
<div class="meta-list-link-text">
ZeroJudge
</div>
</a>
</li>
<li class="meta-list-item">
<a class="meta-list-link current-link">
<div class="meta-list-link-text">
b519: 撲克牌遊戲-商競103
</div>
</a>
</li>
</ul>
</div>
<div class="post-inner">
<header class="title">
<a class="title-link" href="/線上解題/ZeroJudge/b519/">
<h1 class="title-text" title="b519: 撲克牌遊戲-商競103">b519: 撲克牌遊戲-商競103</h1>
</a>
<div class="separator"></div>
<div class="info">
<time class="time">
<i class="far fa-calendar-alt"></i>
2019-09-16
</time>
</div>
</header>
<div class="content toc-article">
<h2 id="內容"><a href="#內容" class="headerlink" title="內容"></a>內容</h2><p>許多人常喜歡玩撲克牌，一副牌共有 52 張牌，有四種花色：黑桃、紅桃、方塊、和梅花。在撲克牌的玩法中，A 可作 1 點或 14 點，而 2-10 則為該牌之點數，另外 J、Q、K 分別為 11、12、13 點。在測試檔案中，每位玩家只會分到 5 張牌。下表將 52 張牌分別對應到數字 1~52，在測試檔案中，將以下表的數字代表某張牌。</p>
<pre><code>點數
花色 A 2 3 4 5 6 7 8 9 10 J Q K
黑桃 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</code></pre><p>五張牌的相關的牌型如下：<br>「同花順」為同花色五張連續數字，相同花色的「順子」，得分 7 分；<br>「四條」為四張同數字的牌，外加任一單張的五張牌，得分 6 分；<br>「葫蘆」為三張同數字，另兩張同數字的牌；一個「一對」和「三條」所組成的五張牌；得分 5 分；<br>「順子」為五張數字連續的牌，數字各差１點的連續牌，從 A-2-3-4-5(1-2-3-4-5)，到 10-J-Q-K-A(有 10-11-12-13-14，但沒有 J-Q-K-A-2)，得分 4 分；<br>「三條」五張牌中包含三張同數字的牌，得分 3 分；<br>「兩對」五張牌中包含兩對兩同數字的牌，但不是四張相同數字的牌(非四條)，得分 2 分；<br>「一對」五張牌中包含只有兩張同數字的牌，得分 1 分；<br>「雜牌」指不屬於以上任何一種組合，得分 0 分。<br>本題目的是判斷手上的五張牌是屬於以上那一種牌型，以得分代替牌型。</p>
<hr>
<h2 id="輸入"><a href="#輸入" class="headerlink" title="輸入"></a>輸入</h2><p>每個輸入資料含多個玩家取得的撲克牌資料，在檔案 in1.txt 和 in2.txt 中，每個玩家分別各使用一副牌，第 1 列的數字 n 代表有幾筆玩家資料要測試， ，第二列起為測試資料，之後每列為每筆的測試資料，代表每個玩家拿到的五張撲克牌，五張牌所代表的數間以空白隔開，而空白不限定一個。如上表所示，每張牌以一個數字(1~52)代表，例如：以 18 代表紅桃 5。</p>
<blockquote>
<p>6<br>3 44 4 19 7<br>6 12 1 32 45<br>26 25 2 38 39<br>15 18 2 28 41<br>14 21 22 23 24<br>1 13 26 27 39</p>
</blockquote>
<h2 id="輸出"><a href="#輸出" class="headerlink" title="輸出"></a>輸出</h2><p>按照每個玩家手上的 5 張牌，判斷每個玩家手上的五張牌是那一種牌型；以得分代替牌型。</p>
<p>5 張牌的數字所對應到的牌型分別如下：<br>3 44 4 19 7 -> 順子；得分 4 分<br>6 12 1 32 45 -> 三條；得分 3 分<br>26 25 2 38 39 -> 兩對；得分 2 分<br>15 18 2 28 41 -> 四條；得分 6 分<br>14 21 22 23 24 -> 雜牌；得分 0 分<br>1 13 26 27 39 -> 葫蘆；得分 5 分</p>
<blockquote>
<p>4<br>3<br>2<br>6<br>0<br>5</p>
</blockquote>
<hr>
<h2 id="解題思路"><a href="#解題思路" class="headerlink" title="解題思路"></a>解題思路</h2><p>先將數字分別除上和取於 13 得到該牌的花色和數字並記錄下來。</p>
<p>再來分成兩部分解，第一部分判斷對子類，也就數字有是重複的部分，如果有產生任一種對子(含三條葫蘆等) 就必定不會產生順子類，因為順子要 5 張都不同。</p>
<p>第二部分判斷順子類，如果上面沒有產生任何對子類，那就只可能是同花順、順子或雜牌，再進行一次判斷即可。</p>
<div class="hidden-content">
<hr>
<h2 id="完整程式碼"><a href="#完整程式碼" class="headerlink" title="完整程式碼"></a>完整程式碼</h2><h6 id="AC-2ms-104KB"><a href="#AC-2ms-104KB" class="headerlink" title="AC (2ms, 104KB)"></a>AC (2ms, 104KB)</h6><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><stdlib.h></span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> suit, num;</span><br><span class="line">}Poker;</span><br><span class="line"></span><br><span class="line">cmp(<span class="keyword">const</span> Poker* lhs, <span class="keyword">const</span> Poker* rhs)</span><br><span class="line">{</span><br><span class="line"> <span class="keyword">return</span> lhs->num - rhs->num;</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="function"></span>{</span><br><span class="line"> Poker <span class="built_in">list</span>[<span class="number">5</span>];</span><br><span class="line"> <span class="keyword">int</span> kase, tmp, count, s, n;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">" %d"</span>, &kase);</span><br><span class="line"> <span class="keyword">while</span> (kase--)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> pair[<span class="number">5</span>] = { <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 < <span class="number">5</span>; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">" %d"</span>, &tmp);</span><br><span class="line"> count = <span class="number">1</span>, tmp--;</span><br><span class="line"> <span class="built_in">list</span>[i].suit = tmp / <span class="number">13</span>;</span><br><span class="line"> <span class="built_in">list</span>[i].num = tmp % <span class="number">13</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = i - <span class="number">1</span>; ~j; j--)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">list</span>[j].num == <span class="built_in">list</span>[i].num)</span><br><span class="line"> count++;</span><br><span class="line"> }</span><br><span class="line"> pair[count]++, pair[count - <span class="number">1</span>]--;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (pair[<span class="number">4</span>]) <span class="built_in">puts</span>(<span class="string">"6"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (pair[<span class="number">3</span>])</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (pair[<span class="number">2</span>]) <span class="built_in">puts</span>(<span class="string">"5"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">puts</span>(<span class="string">"3"</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (pair[<span class="number">2</span>])</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (pair[<span class="number">2</span>] == <span class="number">2</span>) <span class="built_in">puts</span>(<span class="string">"2"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">puts</span>(<span class="string">"1"</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> {</span><br><span class="line"> qsort(<span class="built_in">list</span>, <span class="number">5</span>, <span class="keyword">sizeof</span>(Poker), cmp);</span><br><span class="line"> s = n = <span class="number">1</span>;</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">4</span>; i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">list</span>[i].num - <span class="number">1</span> != <span class="built_in">list</span>[i - <span class="number">1</span>].num)</span><br><span class="line"> {</span><br><span class="line"> n = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (<span class="built_in">list</span>[i].suit != <span class="built_in">list</span>[i - <span class="number">1</span>].suit)</span><br><span class="line"> s = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (n)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span> (s) <span class="built_in">puts</span>(<span class="string">"7"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">puts</span>(<span class="string">"4"</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">puts</span>(<span class="string">"0"</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
</div>
<div class="more">
<a class="more-button" onclick="readMore()">閱讀更多</a>
</div>
</div>
</article>
<div class="index-pagination">
<span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="page-number" href="/page/3/">3</a><span class="space">…</span><a class="page-number" href="/page/27/">27</a><a class="extend next" rel="next" href="/page/2/">»</a>
</div>
</main>
<aside id="sidebar" class="sidebar">
<div class="widget">
<div class="tag-cloud">
<a class="title">
標籤雲
</a>
<div class="content">
<a href="/tags/BFS/" style="font-size: 11.25px;">BFS</a> <a href="/tags/BST/" style="font-size: 10px;">BST</a> <a href="/tags/C-C/" style="font-size: 10px;">C/C++</a> <a href="/tags/DFS/" style="font-size: 20px;">DFS</a> <a href="/tags/DP/" style="font-size: 16.25px;">DP</a> <a href="/tags/Dijkstra/" style="font-size: 11.25px;">Dijkstra</a> <a href="/tags/EPS/" style="font-size: 10px;">EPS</a> <a href="/tags/Hash/" style="font-size: 13.75px;">Hash</a> <a href="/tags/Heap/" style="font-size: 10px;">Heap</a> <a href="/tags/IO優化/" style="font-size: 18.75px;">IO優化</a> <a href="/tags/LCA/" style="font-size: 10px;">LCA</a> <a href="/tags/Mod/" style="font-size: 10px;">Mod</a> <a href="/tags/Queue/" style="font-size: 10px;">Queue</a> <a href="/tags/Stack/" style="font-size: 10px;">Stack</a> <a href="/tags/Tarjan/" style="font-size: 10px;">Tarjan</a> <a href="/tags/Windows/" style="font-size: 10px;">Windows</a> <a href="/tags/並查集/" style="font-size: 10px;">並查集</a> <a href="/tags/位元運算/" style="font-size: 17.5px;">位元運算</a> <a href="/tags/函式指標/" style="font-size: 10px;">函式指標</a> <a href="/tags/基數排序/" style="font-size: 12.5px;">基數排序</a> <a href="/tags/堆積排序/" style="font-size: 10px;">堆積排序</a> <a href="/tags/大數/" style="font-size: 11.25px;">大數</a> <a href="/tags/字串處理/" style="font-size: 20px;">字串處理</a> <a href="/tags/建表/" style="font-size: 13.75px;">建表</a> <a href="/tags/後序式/" style="font-size: 10px;">後序式</a> <a href="/tags/快速冪/" style="font-size: 10px;">快速冪</a> <a href="/tags/插入排序/" style="font-size: 10px;">插入排序</a> <a href="/tags/映射/" style="font-size: 11.25px;">映射</a> <a href="/tags/模板/" style="font-size: 15px;">模板</a> <a href="/tags/河內塔/" style="font-size: 13.75px;">河內塔</a> <a href="/tags/流程控制/" style="font-size: 12.5px;">流程控制</a> <a href="/tags/短路求值/" style="font-size: 10px;">短路求值</a> <a href="/tags/背包問題/" style="font-size: 11.25px;">背包問題</a> <a href="/tags/質數/" style="font-size: 11.25px;">質數</a>
</div>
</div>
</div>
<div class="widget">
<div class="categories">
<a class="title">
分類目錄
</a>
<div class="content">
<ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/模板庫/">模板庫</a><span class="category-list-count">8</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/線上解題/">線上解題</a><span class="category-list-count">252</span><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/線上解題/ZeroJudge/">ZeroJudge</a><span class="category-list-count">251</span></li><li class="category-list-item"><a class="category-list-link" href="/categories/線上解題/本地測試模組/">本地測試模組</a><span class="category-list-count">1</span></li></ul></li></ul>
</div>
</div>
</div>
</aside>
</div>
<footer id="footer">
<div class="wrapper">
<div class="copyright">
© 2019 Theme by <a href="https://github.com/naukri7707/hexo-theme-naukri">Naukri</a> -
Powered by <a href="https://hexo.io/">Hexo</a>.
</div>
</div>
</footer>
</body>
</html>