-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path20240314192415-2023年蓝桥杯省赛_c_b组题解.html
1683 lines (1591 loc) · 188 KB
/
20240314192415-2023年蓝桥杯省赛_c_b组题解.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="zh">
<head>
<!-- 2024-03-15 五 15:15 -->
<meta charset="utf-8" />
<meta name="viewport" content="width=device-width, initial-scale=1" />
<title>2023年蓝桥杯省赛 C++ B组题解</title>
<meta name="author" content="shirui" />
<meta name="generator" content="Org Mode" />
<style>
#content { max-width: 60em; margin: auto; }
.title { text-align: center;
margin-bottom: .2em; }
.subtitle { text-align: center;
font-size: medium;
font-weight: bold;
margin-top:0; }
.todo { font-family: monospace; color: red; }
.done { font-family: monospace; color: green; }
.priority { font-family: monospace; color: orange; }
.tag { background-color: #eee; font-family: monospace;
padding: 2px; font-size: 80%; font-weight: normal; }
.timestamp { color: #bebebe; }
.timestamp-kwd { color: #5f9ea0; }
.org-right { margin-left: auto; margin-right: 0px; text-align: right; }
.org-left { margin-left: 0px; margin-right: auto; text-align: left; }
.org-center { margin-left: auto; margin-right: auto; text-align: center; }
.underline { text-decoration: underline; }
#postamble p, #preamble p { font-size: 90%; margin: .2em; }
p.verse { margin-left: 3%; }
pre {
border: 1px solid #e6e6e6;
border-radius: 3px;
background-color: #f2f2f2;
padding: 8pt;
font-family: monospace;
overflow: auto;
margin: 1.2em;
}
pre.src {
position: relative;
overflow: auto;
}
pre.src:before {
display: none;
position: absolute;
top: -8px;
right: 12px;
padding: 3px;
color: #555;
background-color: #f2f2f299;
}
pre.src:hover:before { display: inline; margin-top: 14px;}
/* Languages per Org manual */
pre.src-asymptote:before { content: 'Asymptote'; }
pre.src-awk:before { content: 'Awk'; }
pre.src-authinfo::before { content: 'Authinfo'; }
pre.src-C:before { content: 'C'; }
pre.src-C\+\+:before { content: 'C++'; }
pre.src-clojure:before { content: 'Clojure'; }
pre.src-css:before { content: 'CSS'; }
pre.src-D:before { content: 'D'; }
pre.src-ditaa:before { content: 'ditaa'; }
pre.src-dot:before { content: 'Graphviz'; }
pre.src-calc:before { content: 'Emacs Calc'; }
pre.src-emacs-lisp:before { content: 'Emacs Lisp'; }
pre.src-fortran:before { content: 'Fortran'; }
pre.src-gnuplot:before { content: 'gnuplot'; }
pre.src-haskell:before { content: 'Haskell'; }
pre.src-hledger:before { content: 'hledger'; }
pre.src-java:before { content: 'Java'; }
pre.src-js:before { content: 'Javascript'; }
pre.src-latex:before { content: 'LaTeX'; }
pre.src-ledger:before { content: 'Ledger'; }
pre.src-lisp:before { content: 'Lisp'; }
pre.src-lilypond:before { content: 'Lilypond'; }
pre.src-lua:before { content: 'Lua'; }
pre.src-matlab:before { content: 'MATLAB'; }
pre.src-mscgen:before { content: 'Mscgen'; }
pre.src-ocaml:before { content: 'Objective Caml'; }
pre.src-octave:before { content: 'Octave'; }
pre.src-org:before { content: 'Org mode'; }
pre.src-oz:before { content: 'OZ'; }
pre.src-plantuml:before { content: 'Plantuml'; }
pre.src-processing:before { content: 'Processing.js'; }
pre.src-python:before { content: 'Python'; }
pre.src-R:before { content: 'R'; }
pre.src-ruby:before { content: 'Ruby'; }
pre.src-sass:before { content: 'Sass'; }
pre.src-scheme:before { content: 'Scheme'; }
pre.src-screen:before { content: 'Gnu Screen'; }
pre.src-sed:before { content: 'Sed'; }
pre.src-sh:before { content: 'shell'; }
pre.src-sql:before { content: 'SQL'; }
pre.src-sqlite:before { content: 'SQLite'; }
/* additional languages in org.el's org-babel-load-languages alist */
pre.src-forth:before { content: 'Forth'; }
pre.src-io:before { content: 'IO'; }
pre.src-J:before { content: 'J'; }
pre.src-makefile:before { content: 'Makefile'; }
pre.src-maxima:before { content: 'Maxima'; }
pre.src-perl:before { content: 'Perl'; }
pre.src-picolisp:before { content: 'Pico Lisp'; }
pre.src-scala:before { content: 'Scala'; }
pre.src-shell:before { content: 'Shell Script'; }
pre.src-ebnf2ps:before { content: 'ebfn2ps'; }
/* additional language identifiers per "defun org-babel-execute"
in ob-*.el */
pre.src-cpp:before { content: 'C++'; }
pre.src-abc:before { content: 'ABC'; }
pre.src-coq:before { content: 'Coq'; }
pre.src-groovy:before { content: 'Groovy'; }
/* additional language identifiers from org-babel-shell-names in
ob-shell.el: ob-shell is the only babel language using a lambda to put
the execution function name together. */
pre.src-bash:before { content: 'bash'; }
pre.src-csh:before { content: 'csh'; }
pre.src-ash:before { content: 'ash'; }
pre.src-dash:before { content: 'dash'; }
pre.src-ksh:before { content: 'ksh'; }
pre.src-mksh:before { content: 'mksh'; }
pre.src-posh:before { content: 'posh'; }
/* Additional Emacs modes also supported by the LaTeX listings package */
pre.src-ada:before { content: 'Ada'; }
pre.src-asm:before { content: 'Assembler'; }
pre.src-caml:before { content: 'Caml'; }
pre.src-delphi:before { content: 'Delphi'; }
pre.src-html:before { content: 'HTML'; }
pre.src-idl:before { content: 'IDL'; }
pre.src-mercury:before { content: 'Mercury'; }
pre.src-metapost:before { content: 'MetaPost'; }
pre.src-modula-2:before { content: 'Modula-2'; }
pre.src-pascal:before { content: 'Pascal'; }
pre.src-ps:before { content: 'PostScript'; }
pre.src-prolog:before { content: 'Prolog'; }
pre.src-simula:before { content: 'Simula'; }
pre.src-tcl:before { content: 'tcl'; }
pre.src-tex:before { content: 'TeX'; }
pre.src-plain-tex:before { content: 'Plain TeX'; }
pre.src-verilog:before { content: 'Verilog'; }
pre.src-vhdl:before { content: 'VHDL'; }
pre.src-xml:before { content: 'XML'; }
pre.src-nxml:before { content: 'XML'; }
/* add a generic configuration mode; LaTeX export needs an additional
(add-to-list 'org-latex-listings-langs '(conf " ")) in .emacs */
pre.src-conf:before { content: 'Configuration File'; }
table { border-collapse:collapse; }
caption.t-above { caption-side: top; }
caption.t-bottom { caption-side: bottom; }
td, th { vertical-align:top; }
th.org-right { text-align: center; }
th.org-left { text-align: center; }
th.org-center { text-align: center; }
td.org-right { text-align: right; }
td.org-left { text-align: left; }
td.org-center { text-align: center; }
dt { font-weight: bold; }
.footpara { display: inline; }
.footdef { margin-bottom: 1em; }
.figure { padding: 1em; }
.figure p { text-align: center; }
.equation-container {
display: table;
text-align: center;
width: 100%;
}
.equation {
vertical-align: middle;
}
.equation-label {
display: table-cell;
text-align: right;
vertical-align: middle;
}
.inlinetask {
padding: 10px;
border: 2px solid gray;
margin: 10px;
background: #ffffcc;
}
#org-div-home-and-up
{ text-align: right; font-size: 70%; white-space: nowrap; }
textarea { overflow-x: auto; }
.linenr { font-size: smaller }
.code-highlighted { background-color: #ffff00; }
.org-info-js_info-navigation { border-style: none; }
#org-info-js_console-label
{ font-size: 10px; font-weight: bold; white-space: nowrap; }
.org-info-js_search-highlight
{ background-color: #ffff00; color: #000000; font-weight: bold; }
.org-svg { }
</style>
<link rel="stylesheet" href="/static/style.css" type="text/css"/>
<link rel="stylesheet" href="/static/org.css" type="text/css"/>
<script src="https://cdn.jsdelivr.net/npm/[email protected]/dist/jquery.min.js"></script>
<meta http-equiv="content-type" content="application/xhtml+xml; charset=UTF-8" />
<meta name="viewport" content="initial-scale=1,width=device-width,minimum-scale=1">
<script>
window.MathJax = {
tex: {
ams: {
multlineWidth: '85%'
},
tags: 'ams',
tagSide: 'right',
tagIndent: '.8em'
},
chtml: {
scale: 1.0,
displayAlign: 'center',
displayIndent: '0em'
},
svg: {
scale: 1.0,
displayAlign: 'center',
displayIndent: '0em'
},
output: {
font: 'mathjax-modern',
displayOverflow: 'overflow'
}
};
</script>
<script
id="MathJax-script"
async
src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js">
</script>
</head>
<body>
<div id="preamble" class="status">
<div class="header">
<a href="https://lampze.github.io">lampze's Blog</a>
<span id="post-date" style="float: right"></span>
</div>
</div>
<div id="content" class="content">
<header>
<h1 class="title">2023年蓝桥杯省赛 C++ B组题解</h1>
</header><div id="outline-container-org6816ecc" class="outline-2">
<h2 id="org6816ecc">日期统计</h2>
<div class="outline-text-2" id="text-org6816ecc">
</div>
<div id="outline-container-orge06e6f9" class="outline-3">
<h3 id="orge06e6f9">题目</h3>
<div class="outline-text-3" id="text-orge06e6f9">
</div>
<div id="outline-container-orgb8974cf" class="outline-4">
<h4 id="orgb8974cf">题目描述</h4>
<div class="outline-text-4" id="text-orgb8974cf">
<p>
小蓝现在有一个长度为 100 的数组，数组中的每个元素的值都在 0 到 9 的范围之内。<br>
数组中的元素从左至右如下所示：<br>
</p>
<pre class="example" id="orgb9601ff">
5 6 8 6 9 1 6 1 2 4 9 1 9 8 2 3 6 4 7 7 5 9 5 0 3 8 7 5 8 1 5 8 6 1 8 3 0 3 7 9 2
7 0 5 8 8 5 7 0 9 9 1 9 4 4 6 8 6 3 3 8 5 1 6 3 4 6 7 0 7 8 2 7 6 8 9 5 6 5 6 1 4 0 1
0 0 9 4 8 0 9 1 2 8 5 0 2 5 3 3
</pre>
<p>
现在他想要从这个数组中寻找一些满足以下条件的子序列：<br>
</p>
<ol class="org-ol">
<li>子序列的长度为 8；<br></li>
<li>这个子序列可以按照下标顺序组成一个 yyyymmdd 格式的日期，并且<br>
要求这个日期是 2023 年中的某一天的日期，例如 20230902，20231223。<br>
yyyy 表示年份，mm 表示月份，dd 表示天数，当月份或者天数的长度只有一位时需要一个前导零补充。<br>
请你帮小蓝计算下按上述条件一共能找到多少个不同的 2023 年的日期。<br>
对于相同的日期你只需要统计一次即可。<br>
本题的结果为一个整数，在提交答案时只输出这个整数，输出多余的内容将无法得分。<br></li>
</ol>
</div>
</div>
</div>
<div id="outline-container-orgf4e9521" class="outline-3">
<h3 id="orgf4e9521">解析</h3>
<div class="outline-text-3" id="text-orgf4e9521">
<p>
题目要求日期是 2023 年的某日期，那么我们肯定是需要生成这一年的所有合法日期，如果知道年份的生成规则可以自己手搓代码，但如果不知道呢？<br>
</p>
<p>
蓝桥杯比赛提供的可不止一个编程环境，还包括 office 全家桶，可以直接使用 excel 生成一年的日期。<br>
</p>
<p>
然后就是子序列的问题了，题目告诉了子序列的长度，那么直接写八个 for 循环也可以解决问题。高级一点的可以使用递归来生成子序列。<br>
</p>
<p>
最后不要忘记了去重，使用 set 保存数据即可。<br>
</p>
</div>
</div>
<div id="outline-container-orgc1ecae0" class="outline-3">
<h3 id="orgc1ecae0">代码</h3>
<div class="outline-text-3" id="text-orgc1ecae0">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><cstdio></span>
<span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><iostream></span>
<span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><set></span>
<span style="color: #3B6EA8;">using</span> <span style="color: #3B6EA8;">namespace</span> std<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">arr</span><span style="color: #3B6EA8; background-color: #E5E9F0;">[]</span> <span style="color: #3B6EA8;">=</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span><span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">2</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">4</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">2</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">3</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">4</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">7</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">7</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span>
<span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">3</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">7</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">3</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">3</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">7</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span>
<span style="color: #97365B;">2</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">7</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">7</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">4</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">4</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">3</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">3</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span>
<span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">3</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">4</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">7</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">7</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">2</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">7</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">6</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span>
<span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">4</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">4</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">9</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">2</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">2</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">5</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">3</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">3</span><span style="color: #3B6EA8; background-color: #E5E9F0;">}</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #9A7500;">set</span><span style="color: #3B6EA8;"><</span><span style="color: #29838D;">int</span><span style="color: #3B6EA8;">></span> <span style="color: #842879;">all</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #9A7500;">set</span><span style="color: #3B6EA8;"><</span><span style="color: #29838D;">int</span><span style="color: #3B6EA8;">></span> <span style="color: #842879;">date</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">void</span> <span style="color: #29838D;">srch</span><span style="color: #3B6EA8; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">idx</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #29838D;">int</span> <span style="color: #842879;">a</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #29838D;">int</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8; background-color: #E5E9F0;">)</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span>idx <span style="color: #3B6EA8;">>=</span> <span style="color: #97365B;">8</span><span style="color: #97365B; background-color: #E5E9F0;">)</span> <span style="color: #97365B; background-color: #E5E9F0;">{</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span>date<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">find</span><span style="color: #842879; background-color: #E5E9F0;">(</span>a<span style="color: #842879; background-color: #E5E9F0;">)</span> <span style="color: #3B6EA8;">!=</span> date<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">end</span><span style="color: #842879; background-color: #E5E9F0;">()</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span>
all<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">insert</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span>a<span style="color: #4F894C; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">return</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #97365B; background-color: #E5E9F0;">}</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span>idx <span style="color: #3B6EA8;">==</span> <span style="color: #97365B;">4</span> <span style="color: #3B6EA8;">&&</span> a <span style="color: #3B6EA8;">!=</span> <span style="color: #97365B;">2023</span><span style="color: #97365B; background-color: #E5E9F0;">)</span>
<span style="color: #3B6EA8;">return</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> i <span style="color: #3B6EA8;"><</span> <span style="color: #97365B;">100</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #97365B; background-color: #E5E9F0;">)</span>
<span style="color: #5d86b6; font-weight: bold;">srch</span><span style="color: #97365B; background-color: #E5E9F0;">(</span>idx <span style="color: #3B6EA8;">+</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> a <span style="color: #3B6EA8;">*</span> <span style="color: #97365B;">10</span> <span style="color: #3B6EA8;">+</span> arr<span style="color: #4F894C; background-color: #E5E9F0;">[</span>i<span style="color: #4F894C; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> i<span style="color: #97365B; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8; background-color: #E5E9F0;">}</span>
<span style="color: #29838D;">int</span> <span style="color: #29838D;">main</span><span style="color: #3B6EA8; background-color: #E5E9F0;">()</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">y</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">m</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">d</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">while</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #5d86b6; font-weight: bold;">scanf</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span><span style="color: #4F894C;">"%d-%d-%d"</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #3B6EA8;">&</span>y<span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #3B6EA8;">&</span>m<span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #3B6EA8;">&</span>d<span style="color: #4F894C; background-color: #E5E9F0;">)</span> <span style="color: #3B6EA8;">!=</span> <span style="color: #97365B;">EOF</span><span style="color: #97365B; background-color: #E5E9F0;">)</span> <span style="color: #97365B; background-color: #E5E9F0;">{</span>
date<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">insert</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span>y <span style="color: #3B6EA8;">*</span> <span style="color: #97365B;">10000</span> <span style="color: #3B6EA8;">+</span> m <span style="color: #3B6EA8;">*</span> <span style="color: #97365B;">100</span> <span style="color: #3B6EA8;">+</span> d<span style="color: #4F894C; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #97365B; background-color: #E5E9F0;">}</span>
<span style="color: #5d86b6; font-weight: bold;">srch</span><span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">-1</span><span style="color: #97365B; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
cout <span style="color: #3B6EA8;"><<</span> all<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">size</span><span style="color: #97365B; background-color: #E5E9F0;">()</span> <span style="color: #3B6EA8;"><<</span> endl<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">return</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8; background-color: #E5E9F0;">}</span>
</pre>
</div>
</div>
</div>
<div id="outline-container-orgecd5b68" class="outline-3">
<h3 id="orgecd5b68">答案</h3>
<div class="outline-text-3" id="text-orgecd5b68">
<p>
235<br>
</p>
</div>
</div>
</div>
<div id="outline-container-orgb0ebf6c" class="outline-2">
<h2 id="orgb0ebf6c">01 串的熵</h2>
<div class="outline-text-2" id="text-orgb0ebf6c">
</div>
<div id="outline-container-orgf0ea4e2" class="outline-3">
<h3 id="orgf0ea4e2">题目</h3>
<div class="outline-text-3" id="text-orgf0ea4e2">
</div>
<div id="outline-container-orgc08d995" class="outline-4">
<h4 id="orgc08d995">题目描述</h4>
<div class="outline-text-4" id="text-orgc08d995">
<p>
对于一个长度为 \(n\) 的 \(01\) 串 \(S = x_{1}x_{2}x_{3}\cdots x_{n}\).<br>
香农信息熵的定义为：<br>
\( H(S)=-\sum^{n}_{i=1}p(x_{i})\log_{2}(p(x_{i})) \)。<br>
其中 \(p(0)\), \(p(1)\) 表示在这个 \(01\) 串中 \(0\) 和 \(1\) 出现的占比。<br>
比如，对于 \(S = 100\) 来说，信息熵 \(H(S) = - 1/3 \log_2(1/3) - 2/3 \log_2(2/3) - 2/3 \log_2(2/3) = 1.3083\) 。<br>
对于一个长度为 \(23333333\) 的 \(01\) 串，如果其信息熵为 \(11625907.5798\) ，且 \(0\) 出现次数比 \(1\) 少，那么这个 \(01\) 串中 \(0\) 出现了多少次？<br>
本题的结果为一个整数，在提交答案时只输出这个整数，输出多余的内容将无法得分。<br>
</p>
</div>
</div>
</div>
<div id="outline-container-orgb298642" class="outline-3">
<h3 id="orgb298642">解析</h3>
<div class="outline-text-3" id="text-orgb298642">
<p>
首先简化公式， \(S\) 中只有 \(0\) 或 \(1\) 所以只有两个概率 \(p(0)\) 和 \(p(1)\)<br>
</p>
<p>
假设 \(0\) 有 \(x\) 个，\(1\) 有 \(y\) 个，总共有 \(n\) 个数<br>
</p>
<p>
所以 \(p(0) = \frac{x}{n} \)，\( p(1)=\frac{y}{n} \)<br>
</p>
<p>
\( H(S) = -(\frac{x^{2}}{n}\log_{2}{\frac{x}{n}}+\frac{y^{2}}{n}\log_{2}{\frac{y}{n}}) \)<br>
</p>
<p>
所以只需要两个循环，遍历 \(0\) 和 \(1\) 的个数即可。<br>
</p>
<p>
这种数值运算推荐使用 <code>python</code> 解决。<br>
</p>
</div>
</div>
<div id="outline-container-org14cd689" class="outline-3">
<h3 id="org14cd689">代码</h3>
<div class="outline-text-3" id="text-org14cd689">
<div class="org-src-container">
<pre class="src src-python"><span style="color: #3B6EA8;">import</span> math
<span style="color: #842879;">n</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">23333333</span>
<span style="color: #842879;">ans</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">11625907.5798</span>
<span style="color: #3B6EA8;">def</span> <span style="color: #29838D;">H</span>(<span style="color: #842879;">x</span>, <span style="color: #842879;">y</span>):
<span style="color: #842879;">logx</span> <span style="color: #3B6EA8;">=</span> math.<span style="color: #5d86b6; font-weight: bold; font-style: italic;">log</span>(x <span style="color: #3B6EA8;">/</span> n, <span style="color: #97365B;">2</span>)
<span style="color: #842879;">logy</span> <span style="color: #3B6EA8;">=</span> math.<span style="color: #5d86b6; font-weight: bold; font-style: italic;">log</span>(y <span style="color: #3B6EA8;">/</span> n, <span style="color: #97365B;">2</span>)
<span style="color: #3B6EA8;">return</span> <span style="color: #3B6EA8;">-</span>(x <span style="color: #3B6EA8;">*</span> x <span style="color: #3B6EA8;">/</span> n <span style="color: #3B6EA8;">*</span> logx <span style="color: #3B6EA8;">+</span> y <span style="color: #3B6EA8;">*</span> y <span style="color: #3B6EA8;">/</span> n <span style="color: #3B6EA8;">*</span> logy)
<span style="color: #3B6EA8;">for</span> <span style="color: #842879;">x</span> <span style="color: #3B6EA8;">in</span> <span style="color: #29838D; font-weight: bold;">range</span>(<span style="color: #97365B;">1</span>, <span style="color: #29838D; font-weight: bold;">int</span>(n <span style="color: #3B6EA8;">/</span> <span style="color: #97365B;">2</span>)):
<span style="color: #842879;">y</span> <span style="color: #3B6EA8;">=</span> n <span style="color: #3B6EA8;">-</span> x
<span style="color: #3B6EA8;">if</span> math.<span style="color: #5d86b6; font-weight: bold; font-style: italic;">fabs</span>(<span style="color: #97365B; font-weight: bold;">H</span>(x, y) <span style="color: #3B6EA8;">-</span> ans) <span style="color: #3B6EA8;"><</span> <span style="color: #97365B;">1e-4</span>:
<span style="color: #29838D; font-weight: bold;">print</span>(x)
</pre>
</div>
</div>
</div>
<div id="outline-container-org2ba4c01" class="outline-3">
<h3 id="org2ba4c01">答案</h3>
<div class="outline-text-3" id="text-org2ba4c01">
<p>
11027421<br>
</p>
</div>
</div>
</div>
<div id="outline-container-orgf6fba0a" class="outline-2">
<h2 id="orgf6fba0a">冶炼金属</h2>
<div class="outline-text-2" id="text-orgf6fba0a">
</div>
<div id="outline-container-orgef8577d" class="outline-3">
<h3 id="orgef8577d">题目</h3>
<div class="outline-text-3" id="text-orgef8577d">
</div>
<div id="outline-container-orgddf44ee" class="outline-4">
<h4 id="orgddf44ee">题目描述</h4>
<div class="outline-text-4" id="text-orgddf44ee">
<p>
小蓝有一个神奇的炉子用于将普通金属 \(O\) 冶炼成为一种特殊金属 \(X\)。这个炉子有一个称作转换率的属性 \(V\)，\(V\) 是一个正整数，这意味着消耗 \(V\) 个普通金属 \(O\) 恰好可以冶炼出一个特殊金属 \(X\)。<br>
</p>
<p>
当普通金属 \(O\) 的数目不足 \(V\) 时，无法继续冶炼。现在给出了 \(N\) 条冶炼记录，每条记录中包含两个整数 \(A\) 和 \(B\)，这表示本次投入了 \(A\) 个普通金属 \(O\)，最终冶炼出了 \(B\) 个特殊金属 \(X\)。<br>
</p>
<p>
每条记录都是独立的，这意味着上一次没消耗完的普通金属 \(O\) 不会累加到下一次的冶炼当中。根据这 \(N\) 条冶炼记录，请你推测出转换率 \(V\) 的最小值和最大值分别可能是多少。<br>
</p>
<p>
题目保证评测数据不存在无解的情况。<br>
</p>
</div>
</div>
<div id="outline-container-orge33003e" class="outline-4">
<h4 id="orge33003e">输入格式</h4>
<div class="outline-text-4" id="text-orge33003e">
<p>
第一行一个整数 \(N\) ，表示冶炼记录的数目。<br>
接下来输入 \(N\) 行，每行两个整数 \(A\)、\(B\)，含义如题目所述。<br>
</p>
</div>
</div>
<div id="outline-container-orgf26f156" class="outline-4">
<h4 id="orgf26f156">输出格式</h4>
<div class="outline-text-4" id="text-orgf26f156">
<p>
输出两个整数，分别表示 \(V\) 可能的最小值和最大值，中间用空格分开。<br>
</p>
</div>
</div>
<div id="outline-container-org1e2ff70" class="outline-4">
<h4 id="org1e2ff70">样例输入</h4>
<div class="outline-text-4" id="text-org1e2ff70">
<pre class="example" id="org2ccfcb1">
3
75 3
53 2
59 2
</pre>
</div>
</div>
<div id="outline-container-org37b038f" class="outline-4">
<h4 id="org37b038f">样例输出</h4>
<div class="outline-text-4" id="text-org37b038f">
<pre class="example" id="orgd7a9f28">
20 25
</pre>
</div>
</div>
<div id="outline-container-orge248992" class="outline-4">
<h4 id="orge248992">提示</h4>
<div class="outline-text-4" id="text-orge248992">
<p>
当 \(V = 20\) 时，有：\(\lfloor 75/20 \rfloor = 3, \lfloor 53/20 \rfloor = 2, \lfloor 59/20 \rfloor = 2\)，可以看到符合所有冶炼记录。<br>
当 \(V = 25\) 时，有：\(\lfloor 75/25\rfloor = 3, \lfloor 53/25 \rfloor = 2, \lfloor 59/25 \rfloor = 2\)，可以看到符合所有冶炼记录。<br>
且再也找不到比 20 更小或者比 25 更大的符合条件的 \(V\) 值了。<br>
</p>
<p>
对于 30% 的评测用例，\(1 \le N \le 10^2\)。<br>
对于 60% 的评测用例，\(1 \le N \le 10^3\) 。<br>
对于 100% 的评测用例，\(1 \le N \le 10^4, 1 \le B \le A \le 10^9\)。<br>
</p>
</div>
</div>
</div>
<div id="outline-container-org0fd27e0" class="outline-3">
<h3 id="org0fd27e0">解析</h3>
<div class="outline-text-3" id="text-org0fd27e0">
<p>
对于每对 \(A, B\) 它的价格区间为：\([ \lfloor \frac{A}{B+1} \rfloor + 1 , \lfloor \frac{A}{B} \rfloor ]\)，那么就把每对的区间算出来，他们的交就是答案了。<br>
</p>
</div>
</div>
<div id="outline-container-orgcde487c" class="outline-3">
<h3 id="orgcde487c">代码</h3>
<div class="outline-text-3" id="text-orgcde487c">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><iostream></span>
<span style="color: #3B6EA8;">using</span> <span style="color: #3B6EA8;">namespace</span> std<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #29838D;">main</span><span style="color: #3B6EA8; background-color: #E5E9F0;">()</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">n</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
cin <span style="color: #3B6EA8;">>></span> n<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">min_</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">max_</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">bool</span> <span style="color: #842879;">flag</span> <span style="color: #3B6EA8;">=</span> <span style="color: #29838D;">true</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">i</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> i <span style="color: #3B6EA8;"><</span> n<span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #97365B; background-color: #E5E9F0;">)</span> <span style="color: #97365B; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">x</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">y</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
cin <span style="color: #3B6EA8;">>></span> x <span style="color: #3B6EA8;">>></span> y<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">l</span> <span style="color: #3B6EA8;">=</span> x <span style="color: #3B6EA8;">/</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span>y <span style="color: #3B6EA8;">+</span> <span style="color: #97365B;">1</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span> <span style="color: #3B6EA8;">+</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">r</span> <span style="color: #3B6EA8;">=</span> x <span style="color: #3B6EA8;">/</span> y<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span>flag<span style="color: #4F894C; background-color: #E5E9F0;">)</span> <span style="color: #4F894C; background-color: #E5E9F0;">{</span>
<span style="color: #842879;">flag</span> <span style="color: #3B6EA8;">=</span> <span style="color: #29838D;">false</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #842879;">min_</span> <span style="color: #3B6EA8;">=</span> l<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #842879;">max_</span> <span style="color: #3B6EA8;">=</span> r<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #4F894C; background-color: #E5E9F0;">}</span>
<span style="color: #842879;">min_</span> <span style="color: #3B6EA8;">=</span> <span style="color: #5d86b6; font-weight: bold;">max</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span>min_<span style="color: #3B4252; background-color: #E5E9F0;">,</span> l<span style="color: #4F894C; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #842879;">max_</span> <span style="color: #3B6EA8;">=</span> <span style="color: #5d86b6; font-weight: bold;">min</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span>max_<span style="color: #3B4252; background-color: #E5E9F0;">,</span> r<span style="color: #4F894C; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #97365B; background-color: #E5E9F0;">}</span>
cout <span style="color: #3B6EA8;"><<</span> min_ <span style="color: #3B6EA8;"><<</span> <span style="color: #4F894C;">" "</span> <span style="color: #3B6EA8;"><<</span> max_ <span style="color: #3B6EA8;"><<</span> endl<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">return</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8; background-color: #E5E9F0;">}</span>
</pre>
</div>
</div>
</div>
</div>
<div id="outline-container-org387b2ee" class="outline-2">
<h2 id="org387b2ee">飞机降落</h2>
<div class="outline-text-2" id="text-org387b2ee">
</div>
<div id="outline-container-org4757d68" class="outline-3">
<h3 id="org4757d68">题目</h3>
<div class="outline-text-3" id="text-org4757d68">
</div>
<div id="outline-container-org291cf4c" class="outline-4">
<h4 id="org291cf4c">题目描述</h4>
<div class="outline-text-4" id="text-org291cf4c">
<p>
\(N\) 架飞机准备降落到某个只有一条跑道的机场。其中第 \(i\) 架飞机在 \(T_i\) 时刻到达机场上空，到达时它的剩余油料还可以继续盘旋 \(D_i\) 个单位时间。即它最早可以于 \(T_i\) 时刻开始降落，最晚可以于 \(T_i + D_i\) 时刻开始降落。<br>
</p>
<p>
降落过程需要\(L_i\)个单位时间。一架飞机降落完毕时，另一架飞机可以立即在同一时刻开始降落。但是不能在前一架飞机完成降落前开始降落。<br>
</p>
<p>
请你判断 \(N\) 架飞机是否可以全部安全降落。<br>
</p>
</div>
</div>
<div id="outline-container-org9f30cec" class="outline-4">
<h4 id="org9f30cec">输入格式</h4>
<div class="outline-text-4" id="text-org9f30cec">
<p>
输入包含多组数据。<br>
第一行包含一个整数 \(T\)，代表测试数据的组数。<br>
对于每组数据，第一行包含一个整数 \(N\)。<br>
以下 \(N\) 行，每行包含三个整数：\(T_i\)，\(D_i\) 和 \(L_i\)。<br>
</p>
</div>
</div>
<div id="outline-container-org95ebf03" class="outline-4">
<h4 id="org95ebf03">输出格式</h4>
<div class="outline-text-4" id="text-org95ebf03">
<p>
对于每组数据，输出 YES 或者 NO，代表是否可以全部安全降落。<br>
</p>
</div>
</div>
<div id="outline-container-orgc0803fb" class="outline-4">
<h4 id="orgc0803fb">样例输入</h4>
<div class="outline-text-4" id="text-orgc0803fb">
<pre class="example" id="org2afaf4c">
2
3
0 100 10
10 10 10
0 2 20
3
0 10 20
10 10 20
20 10 20
</pre>
</div>
</div>
<div id="outline-container-orgc2f8fe7" class="outline-4">
<h4 id="orgc2f8fe7">样例输出</h4>
<div class="outline-text-4" id="text-orgc2f8fe7">
<pre class="example" id="org77f5d2c">
YES
NO
</pre>
</div>
</div>
<div id="outline-container-orgcb4cef0" class="outline-4">
<h4 id="orgcb4cef0">提示</h4>
<div class="outline-text-4" id="text-orgcb4cef0">
<p>
对于第一组数据，可以安排第 3 架飞机于 0 时刻开始降落，20 时刻完成降落。安排第 2 架飞机于 20 时刻开始降落，30 时刻完成降落。安排第 1 架飞机于 30 时刻开始降落，40 时刻完成降落。<br>
对于第二组数据，无论如何安排，都会有飞机不能及时降落。<br>
</p>
<p>
对于 30% 的数据，\(N \le 2\)。<br>
对于 100% 的数据，\(1 \le T \le 10, 1 \le N \le 10, 0 \le T_i , D_i , L_i \le 10^5\)。<br>
</p>
</div>
</div>
</div>
<div id="outline-container-orgaa1b2be" class="outline-3">
<h3 id="orgaa1b2be">解析</h3>
<div class="outline-text-3" id="text-orgaa1b2be">
<p>
直接暴搜即可解，时间复杂度是 \(O(n!)\)，使用贪心算法不可解。<br>
</p>
</div>
</div>
<div id="outline-container-org326a533" class="outline-3">
<h3 id="org326a533">代码</h3>
<div class="outline-text-3" id="text-org326a533">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><iostream></span>
<span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><set></span>
<span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><vector></span>
<span style="color: #3B6EA8;">using</span> <span style="color: #3B6EA8;">namespace</span> std<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">struct</span> <span style="color: #9A7500;">air</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879; font-style: italic;">t</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879; font-style: italic;">d</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879; font-style: italic;">l</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8; background-color: #E5E9F0;">}</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">bool</span> <span style="color: #29838D;">dfs</span><span style="color: #3B6EA8; background-color: #E5E9F0;">(</span><span style="color: #9A7500;">vector</span><span style="color: #97365B;"><</span><span style="color: #9A7500;">air</span><span style="color: #97365B;">></span> <span style="color: #842879;">all</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #9A7500;">set</span><span style="color: #97365B;"><</span><span style="color: #29838D;">int</span><span style="color: #97365B;">></span> <span style="color: #842879;">in</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #29838D;">int</span> <span style="color: #842879;">t</span><span style="color: #3B6EA8; background-color: #E5E9F0;">)</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">n</span> <span style="color: #3B6EA8;">=</span> all<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">size</span><span style="color: #97365B; background-color: #E5E9F0;">()</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span>in<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">size</span><span style="color: #4F894C; background-color: #E5E9F0;">()</span> <span style="color: #3B6EA8;">==</span> n<span style="color: #97365B; background-color: #E5E9F0;">)</span>
<span style="color: #3B6EA8;">return</span> <span style="color: #29838D;">true</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">i</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> i <span style="color: #3B6EA8;"><</span> n<span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #97365B; background-color: #E5E9F0;">)</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span>in<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">find</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span>i<span style="color: #4F894C; background-color: #E5E9F0;">)</span> <span style="color: #3B6EA8;">==</span> in<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">end</span><span style="color: #4F894C; background-color: #E5E9F0;">()</span> <span style="color: #3B6EA8;">&&</span> t <span style="color: #3B6EA8;"><=</span> all<span style="color: #4F894C; background-color: #E5E9F0;">[</span>i<span style="color: #4F894C; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">t</span> <span style="color: #3B6EA8;">+</span> all<span style="color: #4F894C; background-color: #E5E9F0;">[</span>i<span style="color: #4F894C; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">d</span><span style="color: #97365B; background-color: #E5E9F0;">)</span> <span style="color: #97365B; background-color: #E5E9F0;">{</span>
in<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">insert</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span>i<span style="color: #4F894C; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span><span style="color: #5d86b6; font-weight: bold;">dfs</span><span style="color: #842879; background-color: #E5E9F0;">(</span>all<span style="color: #3B4252; background-color: #E5E9F0;">,</span> in<span style="color: #3B4252; background-color: #E5E9F0;">,</span> t <span style="color: #3B6EA8;">+</span> all<span style="color: #3B6EA8; background-color: #E5E9F0;">[</span>i<span style="color: #3B6EA8; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">l</span><span style="color: #842879; background-color: #E5E9F0;">)</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span>
<span style="color: #3B6EA8;">return</span> <span style="color: #29838D;">true</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
in<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">erase</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span>i<span style="color: #4F894C; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #97365B; background-color: #E5E9F0;">}</span>
<span style="color: #3B6EA8;">return</span> <span style="color: #29838D;">false</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8; background-color: #E5E9F0;">}</span>
<span style="color: #29838D;">int</span> <span style="color: #29838D;">main</span><span style="color: #3B6EA8; background-color: #E5E9F0;">()</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">t</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
cin <span style="color: #3B6EA8;">>></span> t<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">while</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #842879;">t</span><span style="color: #3B6EA8;">--</span><span style="color: #97365B; background-color: #E5E9F0;">)</span> <span style="color: #97365B; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">n</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
cin <span style="color: #3B6EA8;">>></span> n<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #9A7500;">vector</span><span style="color: #4F894C;"><</span><span style="color: #9A7500;">air</span><span style="color: #4F894C;">></span> <span style="color: #29838D;">all</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span><span style="color: #9A7500;">n</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">i</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> i <span style="color: #3B6EA8;"><</span> n<span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span>
cin <span style="color: #3B6EA8;">>></span> all<span style="color: #4F894C; background-color: #E5E9F0;">[</span>i<span style="color: #4F894C; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">t</span> <span style="color: #3B6EA8;">>></span> all<span style="color: #4F894C; background-color: #E5E9F0;">[</span>i<span style="color: #4F894C; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">d</span> <span style="color: #3B6EA8;">>></span> all<span style="color: #4F894C; background-color: #E5E9F0;">[</span>i<span style="color: #4F894C; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">l</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #9A7500;">set</span><span style="color: #4F894C;"><</span><span style="color: #29838D;">int</span><span style="color: #4F894C;">></span> <span style="color: #842879;">in</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">bool</span> <span style="color: #842879;">ans</span> <span style="color: #3B6EA8;">=</span> <span style="color: #5d86b6; font-weight: bold;">dfs</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span>all<span style="color: #3B4252; background-color: #E5E9F0;">,</span> in<span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span>ans<span style="color: #4F894C; background-color: #E5E9F0;">)</span>
cout <span style="color: #3B6EA8;"><<</span> <span style="color: #4F894C;">"YES"</span> <span style="color: #3B6EA8;"><<</span> endl<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">else</span>
cout <span style="color: #3B6EA8;"><<</span> <span style="color: #4F894C;">"NO"</span> <span style="color: #3B6EA8;"><<</span> endl<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #97365B; background-color: #E5E9F0;">}</span>
<span style="color: #3B6EA8;">return</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8; background-color: #E5E9F0;">}</span>
</pre>
</div>
</div>
</div>
</div>
<div id="outline-container-orge39c205" class="outline-2">
<h2 id="orge39c205">接龙数列</h2>
<div class="outline-text-2" id="text-orge39c205">
</div>
<div id="outline-container-orgd9dc7d9" class="outline-3">
<h3 id="orgd9dc7d9">题目</h3>
<div class="outline-text-3" id="text-orgd9dc7d9">
</div>
<div id="outline-container-orgbc5e526" class="outline-4">
<h4 id="orgbc5e526">题目描述</h4>
<div class="outline-text-4" id="text-orgbc5e526">
<p>
对于一个长度为 \(K\) 的整数数列：\(A_1, A_2, \cdots , A_K\)，我们称之为接龙数列：<br>
当且仅当 \(A_i\) 的首位数字恰好等于 \( A_{i-1} \) 的末位数字\((2 \le i \le K)\)。<br>
</p>
<p>
例如：12, 23, 35, 56, 61, 11 是接龙数列；12, 23, 34, 56 不是接龙数列，因为 56 的首位数字不等于 34 的末位数字。<br>
</p>
<p>
所有长度为 1 的整数数列都是接龙数列。<br>
</p>
<p>
现在给定一个长度为 \(N\) 的数列\(A_1, A_2, \cdots ,A_N\)，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？<br>
</p>
</div>
</div>
<div id="outline-container-org8669d60" class="outline-4">
<h4 id="org8669d60">输入格式</h4>
<div class="outline-text-4" id="text-org8669d60">
<p>
第一行包含一个整数 \(N\)。<br>
第二行包含 \(N\) 个整数 \(A_1, A_2, \cdots , A_N\)。<br>
</p>
</div>
</div>
<div id="outline-container-org74dc234" class="outline-4">
<h4 id="org74dc234">输出格式</h4>
<div class="outline-text-4" id="text-org74dc234">
<p>
一个整数代表答案。<br>
</p>
</div>
</div>
<div id="outline-container-orgcab5d19" class="outline-4">
<h4 id="orgcab5d19">样例输入</h4>
<div class="outline-text-4" id="text-orgcab5d19">
<pre class="example" id="org9c3699b">
5
11 121 22 12 2023
</pre>
</div>
</div>
<div id="outline-container-org8f4d6f5" class="outline-4">
<h4 id="org8f4d6f5">样例输出</h4>
<div class="outline-text-4" id="text-org8f4d6f5">
<pre class="example" id="org330e843">
1
</pre>
</div>
</div>
<div id="outline-container-orgcc6c2ac" class="outline-4">
<h4 id="orgcc6c2ac">提示</h4>
<div class="outline-text-4" id="text-orgcc6c2ac">
<p>
删除 22，剩余 11, 121, 12, 2023 是接龙数列。<br>
</p>
<p>
对于 20% 的数据，\(1 \le N \le 20\)。<br>
对于 50% 的数据，\(1 \le N \le 10000\)。<br>
对于 100% 的数据，\(1 \le N \le 10^5, 1 \le A_i \le 10^9\)。所有 \(A_i\) 保证不包含前导 0。<br>
</p>
</div>
</div>
</div>
<div id="outline-container-org4449898" class="outline-3">
<h3 id="org4449898">解析</h3>
<div class="outline-text-3" id="text-org4449898">
<p>
动态规划可解，定义 \( dp[i][j] \) 为第 \(i\) 位时，前 \(i\) 位结尾为 \(j\) 的最大长度。\(head[i]\) 表示第 \(i\) 个数字的首位，\(tail[i]\) 为未位。<br>
</p>
\begin{equation*}
dp[i][j] = \begin{cases}
max(dp[i-1][j], dp[i-1][head[i]] + 1) && if & j = tail[i] \\
dp[i-1][j] && else &
\end{cases}
\end{equation*}
<p>
因为前 \(i\) 位的数据不会再次被使用，所以可以做内存的优化，避免复制。<br>
最后优化成：\( dp[tail[i]]=max(dp[i-1][tail[j]], dp[i-1][head[i]]+1) \)<br>
</p>
</div>
</div>
<div id="outline-container-orgc8a9f3e" class="outline-3">
<h3 id="orgc8a9f3e">代码</h3>
<div class="outline-text-3" id="text-orgc8a9f3e">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><iostream></span>
<span style="color: #3B6EA8;">using</span> <span style="color: #3B6EA8;">namespace</span> std<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">res</span><span style="color: #3B6EA8; background-color: #E5E9F0;">[</span><span style="color: #97365B;">10</span><span style="color: #3B6EA8; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #29838D;">main</span><span style="color: #3B6EA8; background-color: #E5E9F0;">()</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">n</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
cin <span style="color: #3B6EA8;">>></span> n<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">i</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> i <span style="color: #3B6EA8;"><</span> n<span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #97365B; background-color: #E5E9F0;">)</span> <span style="color: #97365B; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">x</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
cin <span style="color: #3B6EA8;">>></span> x<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">tail</span> <span style="color: #3B6EA8;">=</span> x <span style="color: #3B6EA8;">%</span> <span style="color: #97365B;">10</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">head</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">while</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span>x<span style="color: #4F894C; background-color: #E5E9F0;">)</span> <span style="color: #4F894C; background-color: #E5E9F0;">{</span>
<span style="color: #842879;">head</span> <span style="color: #3B6EA8;">=</span> x <span style="color: #3B6EA8;">%</span> <span style="color: #97365B;">10</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #842879;">x</span> <span style="color: #3B6EA8;">/=</span> <span style="color: #97365B;">10</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #4F894C; background-color: #E5E9F0;">}</span>
<span style="color: #842879;">res</span><span style="color: #4F894C; background-color: #E5E9F0;">[</span>tail<span style="color: #4F894C; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">=</span> <span style="color: #5d86b6; font-weight: bold;">max</span><span style="color: #4F894C; background-color: #E5E9F0;">(</span>res<span style="color: #842879; background-color: #E5E9F0;">[</span>tail<span style="color: #842879; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> res<span style="color: #842879; background-color: #E5E9F0;">[</span>head<span style="color: #842879; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">+</span> <span style="color: #97365B;">1</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #97365B; background-color: #E5E9F0;">}</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">max_</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">i</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> i <span style="color: #3B6EA8;"><</span> <span style="color: #97365B;">10</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #97365B; background-color: #E5E9F0;">)</span>
<span style="color: #842879;">max_</span> <span style="color: #3B6EA8;">=</span> <span style="color: #5d86b6; font-weight: bold;">max</span><span style="color: #97365B; background-color: #E5E9F0;">(</span>max_<span style="color: #3B4252; background-color: #E5E9F0;">,</span> res<span style="color: #4F894C; background-color: #E5E9F0;">[</span>i<span style="color: #4F894C; background-color: #E5E9F0;">]</span><span style="color: #97365B; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
cout <span style="color: #3B6EA8;"><<</span> n <span style="color: #3B6EA8;">-</span> max_ <span style="color: #3B6EA8;"><<</span> endl<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">return</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8; background-color: #E5E9F0;">}</span>
</pre>
</div>
</div>
</div>
</div>
<div id="outline-container-org4865f2c" class="outline-2">
<h2 id="org4865f2c">岛屿个数</h2>
<div class="outline-text-2" id="text-org4865f2c">
</div>
<div id="outline-container-org5e77928" class="outline-3">
<h3 id="org5e77928">题目</h3>
<div class="outline-text-3" id="text-org5e77928">
</div>
<div id="outline-container-org21f8c36" class="outline-4">
<h4 id="org21f8c36">题目描述</h4>
<div class="outline-text-4" id="text-org21f8c36">
<p>
小蓝得到了一副大小为 \(M \times N\) 的格子地图，可以将其视作一个只包含字符‘0’（代表海水）和 ‘1’（代表陆地）的二维数组，地图之外可以视作全部是海水，每个岛屿由在上/下/左/右四个方向上相邻的 ‘1’ 相连接而形成。<br>
</p>
<p>
在岛屿 A 所占据的格子中，如果可以从中选出 \(k\) 个不同的格子，使得他们的坐标能够组成一个这样的排列：\((x_0, y_0),(x_1, y_1), \cdots ,(x_{k-1}, y_{k-1})\)，其中\((x_{(i+1)} \% k , y_{(i+1)}\% k)\) 是由 \((x_i , y_i)\) 通过上/下/左/右移动一次得来的 \((0 \le i \le k - 1)\)，此时这 \(k\) 个格子就构成了一个 “环”。如果另一个岛屿 \(B\) 所占据的格子全部位于这个 “环” 内部，此时我们将岛屿 \(B\) 视作是岛屿 \(A\) 的子岛屿。若 \(B\) 是 \(A\) 的子岛屿，\(C\) 又是 \(B\) 的子岛屿，那 \(C\) 也是 \(A\) 的子岛屿。<br>
</p>
<p>
请问这个地图上共有多少个岛屿？在进行统计时不需要统计子岛屿的数目。<br>
</p>
</div>
</div>
<div id="outline-container-org6fe33af" class="outline-4">
<h4 id="org6fe33af">输入格式</h4>
<div class="outline-text-4" id="text-org6fe33af">
<p>
第一行一个整数 \(T\)，表示有 \(T\) 组测试数据。<br>
接下来输入 \(T\) 组数据。对于每组数据，第一行包含两个用空格分隔的整数\(M, N\) 表示地图大小；接下来输入 \(M\) 行，每行包含 \(N\) 个字符，字符只可能是‘0’ 或 ‘1’。<br>
</p>
</div>
</div>
<div id="outline-container-orgcd591da" class="outline-4">
<h4 id="orgcd591da">输出格式</h4>
<div class="outline-text-4" id="text-orgcd591da">
<p>
对于每组数据，输出一行，包含一个整数表示答案。<br>
</p>
</div>
</div>
<div id="outline-container-org2812852" class="outline-4">
<h4 id="org2812852">样例输入</h4>
<div class="outline-text-4" id="text-org2812852">
<pre class="example" id="org61cc5b6">
2
5 5
01111
11001
10101
10001
11111
5 6
111111
100001
010101
100001
111111
</pre>
</div>
</div>
<div id="outline-container-org6380061" class="outline-4">
<h4 id="org6380061">样例输出</h4>
<div class="outline-text-4" id="text-org6380061">
<pre class="example" id="orgaccb051">
1
3
</pre>
</div>
</div>
<div id="outline-container-org0801f87" class="outline-4">
<h4 id="org0801f87">提示</h4>
<div class="outline-text-4" id="text-org0801f87">
<p>
对于第一组数据，包含两个岛屿，下面用不同的数字进行了区分：<br>
</p>
<pre class="example" id="org58759c2">
01111
11001
10201
10001
11111
</pre>
<p>
岛屿 2 在岛屿 1 的 “环” 内部，所以岛屿 2 是岛屿 1 的子岛屿，答案为 1。<br>
对于第二组数据，包含三个岛屿，下面用不同的数字进行了区分：<br>
</p>
<pre class="example" id="orga70d66e">
111111
100001
020301
100001
111111
</pre>
<p>
注意岛屿 3 并不是岛屿 1 或者岛屿 2 的子岛屿，因为岛屿 1 和岛屿 2 中均没有“环”。<br>
对于 30% 的评测用例，\(1 \le M, N \le 10\)。<br>
对于 100% 的评测用例，\(1 \le T \le 10, 1 \le M, N \le 50\)。<br>
</p>
</div>
</div>
</div>
<div id="outline-container-orgddccf31" class="outline-3">
<h3 id="orgddccf31">解析</h3>
<div class="outline-text-3" id="text-orgddccf31">
<p>
使用广搜来写，关键是判断子岛屿，可以看岛周围的水域是否与外海连通，如果不连通就是子岛。<br>
</p>
</div>
</div>
<div id="outline-container-orgf3e5d16" class="outline-3">
<h3 id="orgf3e5d16">代码</h3>
<div class="outline-text-3" id="text-orgf3e5d16">
<div class="org-src-container">
<pre class="src src-cpp"><span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><iostream></span>
<span style="color: #3B6EA8; font-weight: bold;">#include</span> <span style="color: #4F894C;"><queue></span>
<span style="color: #3B6EA8;">using</span> <span style="color: #3B6EA8;">namespace</span> std<span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">typedef</span> <span style="color: #29838D;">long long</span> <span style="color: #9A7500;">ll</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">const</span> <span style="color: #29838D;">int</span> <span style="color: #842879;">dx</span><span style="color: #3B6EA8; background-color: #E5E9F0;">[</span><span style="color: #97365B;">8</span><span style="color: #3B6EA8; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">=</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span><span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">-1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">-1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">-1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B6EA8; background-color: #E5E9F0;">}</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">const</span> <span style="color: #29838D;">int</span> <span style="color: #842879;">dy</span><span style="color: #3B6EA8; background-color: #E5E9F0;">[</span><span style="color: #97365B;">8</span><span style="color: #3B6EA8; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">=</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span><span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">-1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">-1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">-1</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">1</span><span style="color: #3B6EA8; background-color: #E5E9F0;">}</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">n</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">m</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">char</span> graph<span style="color: #3B6EA8; background-color: #E5E9F0;">[</span><span style="color: #97365B;">60</span><span style="color: #3B6EA8; background-color: #E5E9F0;">][</span><span style="color: #97365B;">60</span><span style="color: #3B6EA8; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">bool</span> vis<span style="color: #3B6EA8; background-color: #E5E9F0;">[</span><span style="color: #97365B;">60</span><span style="color: #3B6EA8; background-color: #E5E9F0;">][</span><span style="color: #97365B;">60</span><span style="color: #3B6EA8; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">bool</span> <span style="color: #29838D;">fill</span><span style="color: #3B6EA8; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">A</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #29838D;">int</span> <span style="color: #842879;">B</span><span style="color: #3B6EA8; background-color: #E5E9F0;">)</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">i</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> i <span style="color: #3B6EA8;"><=</span> n <span style="color: #3B6EA8;">+</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #97365B; background-color: #E5E9F0;">)</span> <span style="color: #97365B; background-color: #E5E9F0;">{</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">j</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> j <span style="color: #3B6EA8;"><=</span> m <span style="color: #3B6EA8;">+</span> <span style="color: #97365B;">1</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">j</span><span style="color: #3B6EA8;">++</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span> <span style="color: #4F894C; background-color: #E5E9F0;">{</span>
vis<span style="color: #842879; background-color: #E5E9F0;">[</span>i<span style="color: #842879; background-color: #E5E9F0;">][</span>j<span style="color: #842879; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">=</span> <span style="color: #29838D;">false</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #4F894C; background-color: #E5E9F0;">}</span>
<span style="color: #97365B; background-color: #E5E9F0;">}</span>
<span style="color: #9A7500;">queue</span><span style="color: #97365B;"><</span><span style="color: #9A7500;">pair</span><span style="color: #4F894C;"><</span><span style="color: #29838D;">int</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #29838D;">int</span><span style="color: #4F894C;">></span><span style="color: #97365B;">></span> <span style="color: #842879;">q</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">emplace</span><span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #97365B;">A</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">B</span><span style="color: #97365B; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
vis<span style="color: #97365B; background-color: #E5E9F0;">[</span><span style="color: #97365B;">A</span><span style="color: #97365B; background-color: #E5E9F0;">][</span><span style="color: #97365B;">B</span><span style="color: #97365B; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">=</span> <span style="color: #29838D;">true</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">while</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #3B6EA8;">!</span>q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">empty</span><span style="color: #4F894C; background-color: #E5E9F0;">()</span><span style="color: #97365B; background-color: #E5E9F0;">)</span> <span style="color: #97365B; background-color: #E5E9F0;">{</span>
<span style="color: #9A7500;">auto</span> <span style="color: #842879;">cur</span> <span style="color: #3B6EA8;">=</span> q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">front</span><span style="color: #4F894C; background-color: #E5E9F0;">()</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">pop</span><span style="color: #4F894C; background-color: #E5E9F0;">()</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">x</span> <span style="color: #3B6EA8;">=</span> cur<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">first</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">y</span> <span style="color: #3B6EA8;">=</span> cur<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">second</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">i</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> i <span style="color: #3B6EA8;"><</span> <span style="color: #97365B;">8</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span> <span style="color: #4F894C; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">nx</span> <span style="color: #3B6EA8;">=</span> x <span style="color: #3B6EA8;">+</span> dx<span style="color: #842879; background-color: #E5E9F0;">[</span>i<span style="color: #842879; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">ny</span> <span style="color: #3B6EA8;">=</span> y <span style="color: #3B6EA8;">+</span> dy<span style="color: #842879; background-color: #E5E9F0;">[</span>i<span style="color: #842879; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #842879; background-color: #E5E9F0;">(</span>nx <span style="color: #3B6EA8;"><</span> <span style="color: #97365B;">1</span> <span style="color: #3B6EA8;">||</span> nx <span style="color: #3B6EA8;">></span> n <span style="color: #3B6EA8;">||</span> ny <span style="color: #3B6EA8;"><</span> <span style="color: #97365B;">1</span> <span style="color: #3B6EA8;">||</span> ny <span style="color: #3B6EA8;">></span> m<span style="color: #842879; background-color: #E5E9F0;">)</span>
<span style="color: #3B6EA8;">return</span> <span style="color: #29838D;">true</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #842879; background-color: #E5E9F0;">(</span>graph<span style="color: #3B6EA8; background-color: #E5E9F0;">[</span>nx<span style="color: #3B6EA8; background-color: #E5E9F0;">][</span>ny<span style="color: #3B6EA8; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">==</span> <span style="color: #97365B;">'0'</span> <span style="color: #3B6EA8;">&&</span> <span style="color: #3B6EA8;">!</span>vis<span style="color: #3B6EA8; background-color: #E5E9F0;">[</span>nx<span style="color: #3B6EA8; background-color: #E5E9F0;">][</span>ny<span style="color: #3B6EA8; background-color: #E5E9F0;">]</span><span style="color: #842879; background-color: #E5E9F0;">)</span> <span style="color: #842879; background-color: #E5E9F0;">{</span>
vis<span style="color: #3B6EA8; background-color: #E5E9F0;">[</span>nx<span style="color: #3B6EA8; background-color: #E5E9F0;">][</span>ny<span style="color: #3B6EA8; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">=</span> <span style="color: #29838D;">true</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">emplace</span><span style="color: #3B6EA8; background-color: #E5E9F0;">(</span>nx<span style="color: #3B4252; background-color: #E5E9F0;">,</span> ny<span style="color: #3B6EA8; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #842879; background-color: #E5E9F0;">}</span>
<span style="color: #4F894C; background-color: #E5E9F0;">}</span>
<span style="color: #97365B; background-color: #E5E9F0;">}</span>
<span style="color: #3B6EA8;">return</span> <span style="color: #29838D;">false</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8; background-color: #E5E9F0;">}</span>
<span style="color: #29838D;">void</span> <span style="color: #29838D;">bfs</span><span style="color: #3B6EA8; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">A</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #29838D;">int</span> <span style="color: #842879;">B</span><span style="color: #3B6EA8; background-color: #E5E9F0;">)</span> <span style="color: #3B6EA8; background-color: #E5E9F0;">{</span>
<span style="color: #9A7500;">queue</span><span style="color: #97365B;"><</span><span style="color: #9A7500;">pair</span><span style="color: #4F894C;"><</span><span style="color: #29838D;">int</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #29838D;">int</span><span style="color: #4F894C;">></span><span style="color: #97365B;">></span> <span style="color: #842879;">q</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">emplace</span><span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #97365B;">A</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #97365B;">B</span><span style="color: #97365B; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">while</span> <span style="color: #97365B; background-color: #E5E9F0;">(</span><span style="color: #3B6EA8;">!</span>q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">empty</span><span style="color: #4F894C; background-color: #E5E9F0;">()</span><span style="color: #97365B; background-color: #E5E9F0;">)</span> <span style="color: #97365B; background-color: #E5E9F0;">{</span>
<span style="color: #9A7500;">auto</span> <span style="color: #842879;">cur</span> <span style="color: #3B6EA8;">=</span> q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">front</span><span style="color: #4F894C; background-color: #E5E9F0;">()</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">pop</span><span style="color: #4F894C; background-color: #E5E9F0;">()</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">x</span> <span style="color: #3B6EA8;">=</span> cur<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">first</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">y</span> <span style="color: #3B6EA8;">=</span> cur<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #97365B; font-style: italic;">second</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">for</span> <span style="color: #4F894C; background-color: #E5E9F0;">(</span><span style="color: #29838D;">int</span> <span style="color: #842879;">i</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">0</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> i <span style="color: #3B6EA8;"><</span> <span style="color: #97365B;">4</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span> <span style="color: #842879;">i</span><span style="color: #3B6EA8;">++</span><span style="color: #4F894C; background-color: #E5E9F0;">)</span> <span style="color: #4F894C; background-color: #E5E9F0;">{</span>
<span style="color: #29838D;">int</span> <span style="color: #842879;">nx</span> <span style="color: #3B6EA8;">=</span> x <span style="color: #3B6EA8;">+</span> dx<span style="color: #842879; background-color: #E5E9F0;">[</span>i<span style="color: #842879; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">,</span> <span style="color: #842879;">ny</span> <span style="color: #3B6EA8;">=</span> y <span style="color: #3B6EA8;">+</span> dy<span style="color: #842879; background-color: #E5E9F0;">[</span>i<span style="color: #842879; background-color: #E5E9F0;">]</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
<span style="color: #3B6EA8;">if</span> <span style="color: #842879; background-color: #E5E9F0;">(</span>nx <span style="color: #3B6EA8;">>=</span> <span style="color: #97365B;">1</span> <span style="color: #3B6EA8;">&&</span> nx <span style="color: #3B6EA8;"><=</span> n <span style="color: #3B6EA8;">&&</span> ny <span style="color: #3B6EA8;">>=</span> <span style="color: #97365B;">1</span> <span style="color: #3B6EA8;">&&</span> ny <span style="color: #3B6EA8;"><=</span> m <span style="color: #3B6EA8;">&&</span> graph<span style="color: #3B6EA8; background-color: #E5E9F0;">[</span>nx<span style="color: #3B6EA8; background-color: #E5E9F0;">][</span>ny<span style="color: #3B6EA8; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">==</span> <span style="color: #97365B;">'1'</span><span style="color: #842879; background-color: #E5E9F0;">)</span> <span style="color: #842879; background-color: #E5E9F0;">{</span>
graph<span style="color: #3B6EA8; background-color: #E5E9F0;">[</span>nx<span style="color: #3B6EA8; background-color: #E5E9F0;">][</span>ny<span style="color: #3B6EA8; background-color: #E5E9F0;">]</span> <span style="color: #3B6EA8;">=</span> <span style="color: #97365B;">'0'</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>
q<span style="color: #3B4252; background-color: #E5E9F0;">.</span><span style="color: #5d86b6; font-weight: bold; font-style: italic;">emplace</span><span style="color: #3B6EA8; background-color: #E5E9F0;">(</span>nx<span style="color: #3B4252; background-color: #E5E9F0;">,</span> ny<span style="color: #3B6EA8; background-color: #E5E9F0;">)</span><span style="color: #3B4252; background-color: #E5E9F0;">;</span>