-
Notifications
You must be signed in to change notification settings - Fork 0
/
index.html
1572 lines (1188 loc) · 186 KB
/
index.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.4.0">
<link rel="apple-touch-icon" sizes="180x180" href="/wuli-wang.github.io/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/wuli-wang.github.io/images/%E5%A5%B6%E8%8C%B6.png">
<link rel="icon" type="image/png" sizes="16x16" href="/wuli-wang.github.io/images/%E5%A5%B6%E8%8C%B6.png">
<link rel="mask-icon" href="/wuli-wang.github.io/images/logo.svg" color="#222">
<link rel="stylesheet" href="/wuli-wang.github.io/css/main.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.15.3/css/all.min.css" integrity="sha256-2H3fkXt6FEmrReK448mDVGKb3WW2ZZw35gI7vqHOE4Y=" crossorigin="anonymous">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">
<script class="next-config" data-name="main" type="application/json">{"hostname":"m0nesyol.github.io","root":"/wuli-wang.github.io/","images":"/wuli-wang.github.io/images","scheme":"Pisces","version":"8.7.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":true,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/wuli-wang.github.io/search.xml","localsearch":{"enable":true,"trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}}</script><script src="/wuli-wang.github.io/js/config.js"></script>
<meta property="og:type" content="website">
<meta property="og:title" content="wuli-wang'blog">
<meta property="og:url" content="https://m0nesyol.github.io/wuli-wang.github.io/index.html">
<meta property="og:site_name" content="wuli-wang'blog">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="wuli-wang">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="https://m0nesyol.github.io/wuli-wang.github.io/">
<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":true,"isPost":false,"lang":"zh-CN","comments":"","permalink":"","path":"index.html","title":""}</script>
<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>wuli-wang'blog</title>
<noscript>
<link rel="stylesheet" href="/wuli-wang.github.io/css/noscript.css">
</noscript>
<style>.darkmode--activated{--body-bg-color:#282828;--content-bg-color:#333;--card-bg-color:#555;--text-color:#ccc;--blockquote-color:#bbb;--link-color:#ccc;--link-hover-color:#eee;--brand-color:#ddd;--brand-hover-color:#ddd;--table-row-odd-bg-color:#282828;--table-row-hover-bg-color:#363636;--menu-item-bg-color:#555;--btn-default-bg:#222;--btn-default-color:#ccc;--btn-default-border-color:#555;--btn-default-hover-bg:#666;--btn-default-hover-color:#ccc;--btn-default-hover-border-color:#666;--highlight-background:#282b2e;--highlight-foreground:#a9b7c6;--highlight-gutter-background:#34393d;--highlight-gutter-foreground:#9ca9b6}.darkmode--activated img{opacity:.75}.darkmode--activated img:hover{opacity:.9}.darkmode--activated code{color:#69dbdc;background:0 0}button.darkmode-toggle{z-index:9999}</style></head>
<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
<div class="headband"></div>
<main class="main">
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切换导航栏" role="button">
<span class="toggle-line"></span>
<span class="toggle-line"></span>
<span class="toggle-line"></span>
</div>
</div>
<div class="site-meta">
<a href="/wuli-wang.github.io/" class="brand" rel="start">
<i class="logo-line"></i>
<h1 class="site-title">wuli-wang'blog</h1>
<i class="logo-line"></i>
</a>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger">
<i class="fa fa-search fa-fw fa-lg"></i>
</div>
</div>
</div>
<nav class="site-nav">
<ul class="main-menu menu">
<li class="menu-item menu-item-home"><a href="/wuli-wang.github.io/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li>
<li class="menu-item menu-item-tags"><a href="/wuli-wang.github.io/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li>
<li class="menu-item menu-item-categories"><a href="/wuli-wang.github.io/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li>
<li class="menu-item menu-item-archives"><a href="/wuli-wang.github.io/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
<li class="menu-item menu-item-albums"><a href="/wuli-wang.github.io/albums/" rel="section"><i class="fa fa-camera fa-fw"></i>相册</a></li>
<li class="menu-item menu-item-search">
<a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
</a>
</li>
</ul>
</nav>
<div class="search-pop-overlay">
<div class="popup search-popup"><div class="search-header">
<span class="search-icon">
<i class="fa fa-search"></i>
</span>
<div class="search-input-container">
<input autocomplete="off" autocapitalize="off" maxlength="80"
placeholder="搜索..." spellcheck="false"
type="search" class="search-input">
</div>
<span class="popup-btn-close" role="button">
<i class="fa fa-times-circle"></i>
</span>
</div>
<div class="search-result-container no-result">
<div class="search-result-icon">
<i class="fa fa-spinner fa-pulse fa-5x"></i>
</div>
</div>
</div>
</div>
</div>
<div class="toggle sidebar-toggle" role="button">
<span class="toggle-line"></span>
<span class="toggle-line"></span>
<span class="toggle-line"></span>
</div>
<aside class="sidebar">
<div class="sidebar-inner sidebar-overview-active">
<ul class="sidebar-nav">
<li class="sidebar-nav-toc">
文章目录
</li>
<li class="sidebar-nav-overview">
站点概览
</li>
</ul>
<div class="sidebar-panel-container">
<!--noindex-->
<div class="post-toc-wrap sidebar-panel">
</div>
<!--/noindex-->
<div class="site-overview-wrap sidebar-panel">
<div class="site-overview">
<div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
<img class="site-author-image" itemprop="image" alt="wuli-wang"
src="/wuli-wang.github.io/images/avatar1.jpg">
<p class="site-author-name" itemprop="name">wuli-wang</p>
<div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap site-overview-item animated">
<nav class="site-state">
<div class="site-state-item site-state-posts">
<a href="/wuli-wang.github.io/archives/">
<span class="site-state-item-count">19</span>
<span class="site-state-item-name">日志</span>
</a>
</div>
<div class="site-state-item site-state-categories">
<a href="/wuli-wang.github.io/categories/">
<span class="site-state-item-count">13</span>
<span class="site-state-item-name">分类</span></a>
</div>
<div class="site-state-item site-state-tags">
<a href="/wuli-wang.github.io/tags/">
<span class="site-state-item-count">25</span>
<span class="site-state-item-name">标签</span></a>
</div>
</nav>
</div>
<div class="links-of-author site-overview-item animated">
<span class="links-of-author-item">
<a href="https://github.com/wuli-wang" title="GitHub → https://github.com/wuli-wang" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
</span>
</div>
</div>
</div>
</div>
<div class="back-to-top animated" role="button" aria-label="返回顶部">
<i class="fa fa-arrow-up"></i>
<span>0%</span>
</div>
</div>
</aside>
<div class="sidebar-dimmer"></div>
</header>
<noscript>
<div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>
<div class="main-inner index posts-expand">
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://m0nesyol.github.io/wuli-wang.github.io/2024/06/27/Graph%20Theory/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/wuli-wang.github.io/images/avatar1.jpg">
<meta itemprop="name" content="wuli-wang">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="wuli-wang'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/wuli-wang.github.io/2024/06/27/Graph%20Theory/" class="post-title-link" itemprop="url">Graph Theory</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2024-06-27 12:49:06" itemprop="dateCreated datePublished" datetime="2024-06-27T12:49:06+08:00">2024-06-27</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2024-07-31 15:20:05" itemprop="dateModified" datetime="2024-07-31T15:20:05+08:00">2024-07-31</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/wuli-wang.github.io/categories/%E5%9B%BE%E8%AE%BA/" itemprop="url" rel="index"><span itemprop="name">图论</span></a>
</span>
</span>
<span class="post-meta-break"></span>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>15k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>28 分钟</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<blockquote>
<center><font size="4">“万象神宫?!!!”</font></center>
</blockquote>
<!--noindex-->
<div class="post-button">
<a class="btn" href="/wuli-wang.github.io/2024/06/27/Graph%20Theory/#more" rel="contents">
阅读全文 »
</a>
</div>
<!--/noindex-->
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://m0nesyol.github.io/wuli-wang.github.io/2022/02/08/%E8%93%9D%E6%A1%A5%E6%9D%AF%E8%AE%AD%E7%BB%83/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/wuli-wang.github.io/images/avatar1.jpg">
<meta itemprop="name" content="wuli-wang">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="wuli-wang'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/wuli-wang.github.io/2022/02/08/%E8%93%9D%E6%A1%A5%E6%9D%AF%E8%AE%AD%E7%BB%83/" class="post-title-link" itemprop="url">蓝桥杯训练</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2022-02-08 11:55:35" itemprop="dateCreated datePublished" datetime="2022-02-08T11:55:35+08:00">2022-02-08</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2022-06-16 16:55:33" itemprop="dateModified" datetime="2022-06-16T16:55:33+08:00">2022-06-16</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/wuli-wang.github.io/categories/%E8%93%9D%E6%A1%A5%E6%9D%AF%E8%AE%AD%E7%BB%83/" itemprop="url" rel="index"><span itemprop="name">蓝桥杯训练</span></a>
</span>
</span>
<span class="post-meta-break"></span>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>13k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>24 分钟</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<span id="more"></span>
<h2 id="垒骰子"><a href="#垒骰子" class="headerlink" title="垒骰子"></a>垒骰子</h2><ul>
<li>题意：赌圣atm晚年迷恋上了垒骰子，就是把骰子一个垒在另一个上边，不能歪歪扭扭，要垒成方柱体。<br>经过长期观察，atm 发现了稳定骰子的奥秘：有些数字的面贴着会互相排斥！<br>我们先来规范一下骰子：1 的对面是 4，2 的对面是 5，3 的对面是 6。<br>假设有 m 组互斥现象，每组中的那两个数字的面紧贴在一起，骰子就不能稳定的垒起来。<br>atm想计算一下有多少种不同的可能的垒骰子方式。<br>两种垒骰子方式相同，当且仅当这两种方式中对应高度的骰子的对应数字的朝向都相同。<br>由于方案数可能过多，请输出模 10^9 + 7 的结果。</li>
<li>输入：n，m（0< n <=1e9）</li>
<li>思路：通过设置最底层的初始状态，通过状态转移求得最终层的合理方案数。</li>
<li>状态定义dp[i][j]：在第i层顶层显示数字j的方案数，这里比较坑的地方时骰子可以旋转，也就是说在顶层数字确定的情况下会有四个方向也就是四种情况。而且骰子的数目也非常大，但是发现后一层的状态只与前一层的状态有关，因此可以用到滚动数组，但是值得注意的是在更新下一层的数据时记得进行初始化！</li>
<li>枚举该层骰子的顶面数与下一层骰子的底面数，判断是否会出现相斥，进行状态转移即可。<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">int</span> mp[<span class="number">10</span>][<span class="number">10</span>];</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> mod=<span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line"><span class="keyword">int</span> opp[<span class="number">100</span>];</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</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"> ios::<span class="built_in">sync_with_stdio</span>(<span class="literal">false</span>);</span><br><span class="line"> <span class="keyword">int</span> n,m;</span><br><span class="line"> opp[<span class="number">1</span>]=<span class="number">4</span>;</span><br><span class="line"> opp[<span class="number">4</span>]=<span class="number">1</span>;</span><br><span class="line"> opp[<span class="number">2</span>]=<span class="number">5</span>;</span><br><span class="line"> opp[<span class="number">5</span>]=<span class="number">2</span>;</span><br><span class="line"> opp[<span class="number">3</span>]=<span class="number">6</span>;</span><br><span class="line"> opp[<span class="number">6</span>]=<span class="number">3</span>;</span><br><span class="line"> cin>>n>>m;</span><br><span class="line"> <span class="keyword">int</span> x,y;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=m;i++)</span><br><span class="line"> {</span><br><span class="line"> cin>>x>>y;</span><br><span class="line"> mp[x][y]=<span class="number">1</span>;</span><br><span class="line"> mp[y][x]=<span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> ll dp[<span class="number">10</span>][<span class="number">10</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">1</span>;i<=<span class="number">6</span>;i++) dp[<span class="number">1</span>][i]=<span class="number">4</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n<span class="number">-1</span>;i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> p=<span class="number">1</span>;p<=<span class="number">6</span>;p++) dp[(i+<span class="number">1</span>)%<span class="number">2</span>][p]=<span class="number">0</span>;<span class="comment">//滚动数组再用到下一层数据时记得清零</span></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j<=<span class="number">6</span>;j++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> k=<span class="number">1</span>;k<=<span class="number">6</span>;k++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(!mp[j][k]) </span><br><span class="line"> {</span><br><span class="line"> dp[(i+<span class="number">1</span>)%<span class="number">2</span>][opp[k]]=(dp[(i+<span class="number">1</span>)%<span class="number">2</span>][opp[k]]+<span class="number">4</span>*dp[i%<span class="number">2</span>][j]%mod)%mod;</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"> ll res=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=<span class="number">6</span>;i++)</span><br><span class="line"> {</span><br><span class="line"><span class="comment">// cout<<dp[n][i]<<endl;</span></span><br><span class="line"> res=(res+dp[n%<span class="number">2</span>][i])%mod;</span><br><span class="line"> }</span><br><span class="line"> cout<<res<<endl;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h2 id="四平方和问题"><a href="#四平方和问题" class="headerlink" title="四平方和问题"></a>四平方和问题</h2></li>
</ul>
<p>题意：给定n，必定存在n=a * a+b * b+c * c+d * d,按照升序给出a，b，c，d的值</p>
<ul>
<li>思路：按照一般的思路，四个循环分别枚举a，b，c，d即可，但是显然时间复杂度不允许；因此可以分开计算a * a+b * b 与 c * c+d * d，这样时间复杂度大大降低。</li>
<li>方法：先求出所有可能的a * a+b * b的值存入map中，此时再枚举c，d，查看map中有无map[n-a * a-b * b]即可，存在即输出，不存在就跳过往下找。</li>
</ul>
<h2 id="剪邮票"><a href="#剪邮票" class="headerlink" title="剪邮票"></a>剪邮票</h2><p>题意：<img src="/images/loading.png" data-original="/wuli-wang.github.io/wuli-wang.github.io/2022/02/08/%E8%93%9D%E6%A1%A5%E6%9D%AF%E8%AE%AD%E7%BB%83/blog\betblog\source_posts\蓝桥杯训练\剪邮票.png" alt="image-20220407102341084"></p>
<ul>
<li>思路：由于数据量并不是很大，因此可以想到枚举检验的方式，那么便需要从12个数中任意选取5个数所有的方案中进行验证，并判断这五个数是否连续即可；从12个数中任取5个的枚举方式可以选择next_permutation()函数，先在数组中从小到大存储7个0以及5个1，这时候在这12个数进行全排列的过程中即能够覆盖所有选取五个数的情况，这时候在进行验证即可；验证可以采取判断是否只有一个连通通块的方式验证，枚举12个起始点，从标记为1的数字开始dfs，将搜到的点标记为0，跑完之后cnt++，即得到一个连通块，最后判断连通块的个数即可。</li>
</ul>
<h2 id="包子凑数（扩展欧几里得）"><a href="#包子凑数（扩展欧几里得）" class="headerlink" title="包子凑数（扩展欧几里得）"></a>包子凑数（扩展欧几里得）</h2><ul>
<li>题意：给定n个数，每个数都有任意个，问是否有可能让这些数任意组合使得只有有限个数这些数不能构成，如果能的话输出不能组成的数的个数，否则便会有无穷多个无法组成的数，输出INF即可。（1=< N,$x_i$ <=100）</li>
<li>思路：该n个数能够组成的数的表达式如下：$num=a_1 * x_1 + a_2 * x_2 + … + a_n * x_n$,跟据扩展欧几里得原理，该方程式有解的情况即为$num=k*gcd(x_1 … x_n)$,也就是说改n个数能够构成的数只要 k * gcd(x1,x2,…,xn),因此要想该n个数能够构成任意数，也就只有当gcd=1时才可能实现。</li>
<li>故当gcd！=1时会有无穷多个数无法构成，输出INF；当gcd=1时，虽然理论上能够构成任意数，但是当初始值x1 … xn足够大num很小时虽然有解但也是负数解与这里的实际情况不符，因此需要特殊考虑，考虑到100个xi的范围最多也是10000，那么就特殊考虑10000以内的数这n个数能够构成的数的情况即可。<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><unordered_map></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">1e5</span>+<span class="number">10</span>;</span><br><span class="line"><span class="keyword">int</span> a[N];</span><br><span class="line"><span class="comment">// int mp[N];</span></span><br><span class="line">unordered_map<<span class="keyword">int</span>,<span class="keyword">int</span>> mp;</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"> ios::<span class="built_in">sync_with_stdio</span>(<span class="literal">false</span>);</span><br><span class="line"> <span class="keyword">int</span> n,x;</span><br><span class="line"> <span class="keyword">int</span> gcd;</span><br><span class="line"> cin>>n;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++)</span><br><span class="line"> {</span><br><span class="line"> cin>>a[i];</span><br><span class="line"> x=a[i];</span><br><span class="line"> <span class="keyword">if</span>(i==<span class="number">1</span>) gcd=x;</span><br><span class="line"> <span class="keyword">else</span> gcd=__gcd(gcd,x);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span>(gcd!=<span class="number">1</span>) </span><br><span class="line"> {</span><br><span class="line"> cout<<<span class="string">"INF\n"</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"> mp[<span class="number">0</span>]=<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<=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<=<span class="number">10000</span>;j++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(mp[j])</span><br><span class="line"> {</span><br><span class="line"> mp[j+a[i]]=<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="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=<span class="number">10000</span>;i++) <span class="keyword">if</span>(!mp[i]) ans++;</span><br><span class="line"> cout<<ans<<endl;</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h2 id="出现奇数次的数"><a href="#出现奇数次的数" class="headerlink" title="出现奇数次的数"></a>出现奇数次的数</h2>题意：给定n个数，其中只有一个数的出现次数为奇数次，其余的数均出现偶数次，求该出现奇数次的数是多少？</li>
<li>思路：结合异或操作的特性知道：<ul>
<li>偶数个x进行异或其值为0</li>
<li>奇数个x进行异或其值为x</li>
<li>异或操作满足交换律</li>
</ul>
</li>
<li>那么知道，如果将这n个值进行异或操作后，那么偶数次的数全部异或成0了，只剩下出现奇数次的数，也就是答案。<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">1e2</span>+<span class="number">7</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> INF=<span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> p=<span class="number">1e9</span>+<span class="number">7</span>;</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"> ios::<span class="built_in">sync_with_stdio</span>(<span class="literal">false</span>);</span><br><span class="line"> <span class="keyword">int</span> n;</span><br><span class="line"> cin>>n;</span><br><span class="line"> <span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> x;</span><br><span class="line"> cin>>x;</span><br><span class="line"> ans^=x;</span><br><span class="line"> }</span><br><span class="line"> cout<<ans<<endl;</span><br><span class="line">} </span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h2 id="心的形状"><a href="#心的形状" class="headerlink" title="心的形状"></a>心的形状</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">1e2</span>+<span class="number">7</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> INF=<span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> p=<span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">print1</span><span class="params">(<span class="keyword">int</span> n)</span><span class="comment">//输出空格</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">1</span>;i<=n;i++) cout<<<span class="string">" "</span>;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">print2</span><span class="params">(<span class="keyword">int</span> n)</span><span class="comment">//输出*</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">1</span>;i<=n;i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(i==n) cout<<<span class="string">"*"</span>;</span><br><span class="line"> <span class="keyword">else</span> cout<<<span class="string">"* "</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> ios::<span class="built_in">sync_with_stdio</span>(<span class="literal">false</span>);</span><br><span class="line"> <span class="keyword">int</span> n;</span><br><span class="line"> cin>>n;</span><br><span class="line"> <span class="keyword">int</span> deep=(n+<span class="number">1</span>)/<span class="number">4</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=deep;i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">print1</span>((n+<span class="number">1</span>)/<span class="number">2</span>-(i<span class="number">-1</span>)*<span class="number">2</span>);</span><br><span class="line"> <span class="built_in">print2</span>(<span class="number">2</span>*i<span class="number">-1</span>);</span><br><span class="line"> <span class="built_in">print1</span>(<span class="number">4</span>*deep<span class="number">-1</span><span class="number">-4</span>*(i<span class="number">-1</span>));</span><br><span class="line"> <span class="built_in">print2</span>(<span class="number">2</span>*i<span class="number">-1</span>);</span><br><span class="line"> cout<<<span class="string">'\n'</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i+=<span class="number">2</span>)</span><br><span class="line"> { </span><br><span class="line"> <span class="built_in">print1</span>(i);</span><br><span class="line"> <span class="built_in">print2</span>(n-i+<span class="number">1</span>);</span><br><span class="line"> cout<<<span class="string">'\n'</span>;</span><br><span class="line"> }</span><br><span class="line">} </span><br></pre></td></tr></table></figure></li>
</ul>
<h2 id="简单却很难"><a href="#简单却很难" class="headerlink" title="简单却很难"></a>简单却很难</h2><ul>
<li>题意：给定a,b,c，求$a^{b^c}mod p$,(a,b,b<=$10^9$，p为质数)</li>
<li>提示：没错，题目就是这么简单明了，而且明确告诉你需要用到费马小定理（$a^{p-1} mod p=1$），你确定会吗？</li>
<li>思路：题目的意图也就是求$b^{c}$个a相乘然后模p，由费马小定理可知$a^{p-1}$ mod p 等于1,因此可以从$b^c$中分出所有的p-1,该部分模p等于1不影响答案，那么答案就在剩余部分的幂模p，即$a^{b^{c}%(p-1)} % p$。<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="keyword">const</span> ll N=<span class="number">1e2</span>+<span class="number">7</span>;</span><br><span class="line"><span class="keyword">const</span> ll INF=<span class="number">0x3f3f3f3f</span>;</span><br><span class="line"><span class="keyword">const</span> ll p=<span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line"><span class="function">ll <span class="title">qsm</span><span class="params">(ll a,ll k,ll p)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> ll res=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span>(k)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(k&<span class="number">1</span>) res=(ll)res*a%p;</span><br><span class="line"> a=(ll)a*a%p;</span><br><span class="line"> k>>=<span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> res;</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"> ios::<span class="built_in">sync_with_stdio</span>(<span class="literal">false</span>);</span><br><span class="line"> ll a,b,c;</span><br><span class="line"> cin>>a>>b>>c;</span><br><span class="line"> ll z=<span class="built_in">qsm</span>(b,c,p<span class="number">-1</span>);</span><br><span class="line"> ll y=<span class="built_in">qsm</span>(a,z,p);</span><br><span class="line"> cout<<y<<endl;</span><br><span class="line">} </span><br><span class="line"></span><br><span class="line"></span><br><span class="line"><span class="comment">// 818398173 491423852 785451404</span></span><br><span class="line"><span class="comment">// 751968174</span></span><br></pre></td></tr></table></figure>
<h2 id="删除字符"><a href="#删除字符" class="headerlink" title="删除字符"></a><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/544/learning/?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQyODI2MDIsImciOiJKcEs2VFFxNndjS1dXM1QzIiwiaWF0IjoxNjQ0MjgyMzAyLCJ1c2VySWQiOi0xNzM1MTUxNTcyfQ.4vWw1lb87P6kq3ghFvbUhJ4X99djkvE6bbE5RWW8wBE">删除字符</a></h2></li>
<li>题目：给定一个单词，请问在单词中删除 t 个字母后，能得到的字典序最小的单词是什么？<br></li>
<li>思路：从前往后看每一个字母，如果后面有更小的字典序字母，那么说明该字母可以被删除以得到更小字典序的字符串，反之则说明该处的字母已经是最小字典序，那么不用删除往后扫描即可，如果删除次数最终没有用完，那么从后往前删除对应个数的字母即可。<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><list></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</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> n;</span><br><span class="line"> string str;</span><br><span class="line"> cin>>str>>n;</span><br><span class="line"> <span class="keyword">while</span>(n--)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<str.<span class="built_in">size</span>();++i){</span><br><span class="line"> <span class="keyword">if</span>(str[i]>str[i+<span class="number">1</span>])</span><br><span class="line"> {</span><br><span class="line"> str.<span class="built_in">erase</span>(i,<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> cout<<str<<endl;</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></li>
</ul>
<h2 id="货物摆放"><a href="#货物摆放" class="headerlink" title="货物摆放"></a>货物摆放</h2><ul>
<li>题意：现有n个货物，需要在长、宽、高的方向上分别堆 L、W、H 的货物,满足 n=L×W×H,问当n=2021041820210418（16位数），有多少种摆放方式？</li>
<li>思路一：<br>暴力枚举三个因子，如果不考虑三个因子的排列来统计次数需要分别对三个因子进行1e^16 的枚举，显然时间复杂度上是不允许的。那么转换思路，通过设置枚举方式使得枚举出的因子L<=W<=H,这样第一个因子只需枚举至$^{3}\sqrt{n}$大概$1e^5$的位置,在往上枚举会出现L>W>H的局面，即会出现重复计算，最后通过三者的相等关系来统计方案数（L=W=H：方案数++；L=W!=H:方案数+3；L!=W!=H:方案数+6）。</li>
<li>注：虽然时间复杂度大幅降低，但是运算出结果任然需要一定的时间，不满足时限要求。<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><list></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</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"> ll n=<span class="number">2021041820210418</span>;</span><br><span class="line"> <span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(ll i=<span class="number">1</span>;i*i*i<=n;i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(n%i) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="keyword">for</span>(ll j=i;i*j*j<=n;j++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(n / i %j==<span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> ll k=n/i/j;</span><br><span class="line"> <span class="keyword">if</span>(i==j==k) ans++;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span>(i==j||j==k||i==k) ans+=<span class="number">3</span>;</span><br><span class="line"> <span class="keyword">else</span> ans+=<span class="number">6</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> cout<<ans<<endl;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></li>
<li>思路二：<br><br>求出所有的正因子，在所有因子中枚举L、W、H，找出合适的方案(该题中2021041820210418的因子只有128个)。</li>
<li>有感：<br><br>一个这么大的数，其因子才128个，因此在一些分解问题上，可以考虑利用$\sqrt{n}$的试除法来求出所有的因子并进行枚举！<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><vector></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line">vector<ll> v; </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"> ll n=<span class="number">2021041820210418</span>;</span><br><span class="line"> <span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(ll i=<span class="number">1</span>;i*i<=n;i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(n%i==<span class="number">0</span>) </span><br><span class="line"> {</span><br><span class="line"> v.<span class="built_in">push_back</span>(i);</span><br><span class="line"> ll k=n/i;</span><br><span class="line"> <span class="keyword">if</span>(k!=i) v.<span class="built_in">push_back</span>(k);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// cout<<v.size()<<endl;</span></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">auto</span> a:v)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">auto</span> b:v)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">auto</span> c:v)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(a*b*c==n) ans++;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> cout<<ans<<endl;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></li>
</ul>
<h2 id="空间"><a href="#空间" class="headerlink" title="空间"></a>空间</h2><ul>
<li>题意：小蓝准备用 256MB256MB 的内存空间开一个数组，数组的每个元素都是 3232 位 二进制整数，如果不考虑程序占用的空间和维护内存需要的辅助空间，请问 256MB256MB 的空间可以存储多少个 3232 位二进制整数？</li>
<li>思路：1B=8bit，直接计算就行。</li>
<li>注意：1024默认位int型，1024 * 1024 * 256 *8会超出int型范围，所以需要类型强制转换。<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><vector></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line">vector<ll> v; </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="comment">//int范围内的整数默认为int型</span></span><br><span class="line"> <span class="comment">//int 范围外的整数默认为long long</span></span><br><span class="line"> ll ans=<span class="number">1024LL</span>*<span class="number">1024</span>*<span class="number">256</span>*<span class="number">8</span>;</span><br><span class="line"> cout<<ans<<endl;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></li>
</ul>
<h2 id="最少砝码"><a href="#最少砝码" class="headerlink" title="最少砝码"></a>最少砝码</h2><ul>
<li>题意：你有一架天平。现在你要设计一套砝码，使得利用这些砝码可以称出任意 小于等于 N 的正整数重量，那么这套砝码最少需要包含多少个砝码？（注意砝码可以放在天平两边。）</li>
<li>思路：先写出前面几个的数所需最小砝码数，从而找出规律如下：<br><br>1 所需砝码 1 （3^0）<br><br>2-4 所需砝码 2 （3^1）<br><br>5-13 所需砝码 3 （3^2）<br><br>由此看出是一个等比数列，根据对用的N以及前n项和即可算出所需砝码数。<br>即$s_n=(3^n-1)/2 > N$,可得n=$log_3(2*N+1)$（向上取整）</li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</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="comment">// 请在此输入您的代码</span></span><br><span class="line"> <span class="keyword">int</span> n;</span><br><span class="line"> cin>>n;</span><br><span class="line"> cout<<<span class="built_in">ceil</span>(<span class="built_in">log10</span>(<span class="number">2</span>*n+<span class="number">1</span>)/<span class="built_in">log10</span>(<span class="number">3</span>))<<endl;</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>
<h2 id="寻找-2020"><a href="#寻找-2020" class="headerlink" title="寻找 2020"></a>寻找 2020</h2><ul>
<li>[题面]（<a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/1065/learning/?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQzNzM0NDEsImciOiJKcEs2VFFxNndjS1dXM1QzIiwiaWF0IjoxNjQ0MzczMTQxLCJ1c2VySWQiOi0xNzQxMDU5OTYxfQ.MK2NK26tG5drVFZO647aYoquWHR-jXzc1Js8n5vCKYU%EF%BC%89">https://www.lanqiao.cn/problems/1065/learning/?accessToken=eyJhbGciOiJIUzI1NiIsImtpZCI6ImRlZmF1bHQiLCJ0eXAiOiJKV1QifQ.eyJhdWQiOiJhY2Nlc3NfcmVzb3VyY2UiLCJleHAiOjE2NDQzNzM0NDEsImciOiJKcEs2VFFxNndjS1dXM1QzIiwiaWF0IjoxNjQ0MzczMTQxLCJ1c2VySWQiOi0xNzQxMDU5OTYxfQ.MK2NK26tG5drVFZO647aYoquWHR-jXzc1Js8n5vCKYU）</a></li>
<li>题意：在给定的0 2 矩阵中找到共有多少个横向、纵向、以及斜向的’2020’。</li>
<li>思路：对于矩阵中的每一个位置向右、向下、斜向下寻找2020，找到即答案加1.</li>
<li>特殊处理：对于矩阵每行向后增加三个空字符，并在最后面增加三行空字符。这样每个字符向右、向下、斜向下寻找三个字符时不需要进行越界判断。</li>
<li>注意：值得一提的是填空题没有输入，直接输出结果，否则会报运行错误！！！<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line">vector<string> v;</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="comment">// 请在此输入您的代码</span></span><br><span class="line"> string s;</span><br><span class="line"> <span class="keyword">int</span> ans=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span>(cin>>s&&s!=<span class="string">""</span>)</span><br><span class="line"> {</span><br><span class="line"> s+=<span class="string">" "</span>;</span><br><span class="line"> v.<span class="built_in">push_back</span>(s);</span><br><span class="line"> }</span><br><span class="line"> <span class="function">string <span class="title">s2</span><span class="params">(<span class="number">310</span>,<span class="string">' '</span>)</span></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">3</span>;i++)</span><br><span class="line"> {</span><br><span class="line"> v.<span class="built_in">push_back</span>(s2);</span><br><span class="line"> }</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">300</span>;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<<span class="number">300</span>;j++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(v[i][j]==<span class="string">'2'</span>&&v[i][j+<span class="number">1</span>]==<span class="string">'0'</span>&&v[i][j+<span class="number">2</span>]==<span class="string">'2'</span>&&v[i][j+<span class="number">3</span>]==<span class="string">'0'</span>) ans++;</span><br><span class="line"> <span class="keyword">if</span>(v[i][j]==<span class="string">'2'</span>&&v[i+<span class="number">1</span>][j]==<span class="string">'0'</span>&&v[i+<span class="number">2</span>][j]==<span class="string">'2'</span>&&v[i+<span class="number">3</span>][j]==<span class="string">'0'</span>) ans++;</span><br><span class="line"> <span class="keyword">if</span>(v[i][j]==<span class="string">'2'</span>&&v[i+<span class="number">1</span>][j+<span class="number">1</span>]==<span class="string">'0'</span>&&v[i+<span class="number">2</span>][j+<span class="number">2</span>]==<span class="string">'2'</span>&&v[i+<span class="number">2</span>][j+<span class="number">3</span>]==<span class="string">'0'</span>) ans++;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> cout<<ans<<endl;</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></li>
</ul>
<h2 id="子串分值和"><a href="#子串分值和" class="headerlink" title="子串分值和"></a>子串分值和</h2><p>题意：给定一个字符串s，定义f（s）为s中出现的不同的字符个数，求一个给定字符串s的所有子串y的f(y)之和。<br>思路：</p>
<ul>
<li>由于子串的构造具有规律性与继承性，因此可以先写出前几个子串寻找规律；</li>
<li>对于字符串”ababc”来说，其子串有：<br>a<br>ab b<br>aba ba a<br>abab abb ab b<br>ababc babc abc bc c<br>由此可以看出，每新增一个字符都是在前面的子串基础上增加一个字符，因此可以得到递推公式dp[i]=dp[i-1]+新增贡献量，不难发现新增的贡献量即为该字符与该字符上一次出现的位置的距离，于是可以求出答案。<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta"># <span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">1e5</span>+<span class="number">5</span>;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> debug(x) cout<<#x<<<span class="meta-string">": "</span><<x<<endl</span></span><br><span class="line"><span class="keyword">int</span> pre[<span class="number">100010</span>],last[<span class="number">100010</span>],tmp[<span class="number">30</span>];</span><br><span class="line">ll dp[<span class="number">100010</span>];</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"> ll ans=<span class="number">0</span>;</span><br><span class="line"> string s;</span><br><span class="line"> <span class="built_in">memset</span>(dp,<span class="number">0</span>,<span class="built_in"><span class="keyword">sizeof</span></span>(dp));</span><br><span class="line"> dp[<span class="number">0</span>]=<span class="number">1</span>;</span><br><span class="line"> cin>>s;</span><br><span class="line"> <span class="comment">//求出字符串每个字符上一次所出现的位置</span></span><br><span class="line"> <span class="built_in">memset</span>(tmp,<span class="number">-1</span>,<span class="built_in"><span class="keyword">sizeof</span></span>(tmp));</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<s.<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> pre[i]=tmp[s[i]-<span class="string">'a'</span>];</span><br><span class="line"> tmp[s[i]-<span class="string">'a'</span>]=i;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//求出字符串每个字符下一次所出现的位置</span></span><br><span class="line"> <span class="comment">// memset(tmp,s.size(),sizeof(tmp));</span></span><br><span class="line"> <span class="comment">// for(int i=0;i<s.size();i++)</span></span><br><span class="line"> <span class="comment">// {</span></span><br><span class="line"> <span class="comment">// last[i]=tmp[s[i]-'a'];</span></span><br><span class="line"> <span class="comment">// tmp[s[i]-'a']=i;</span></span><br><span class="line"> <span class="comment">// }</span></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<s.<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> dp[i]=dp[i<span class="number">-1</span>]+(ll)(i-pre[i]);</span><br><span class="line"> ans+=dp[i];</span><br><span class="line"> }</span><br><span class="line"> cout<<ans<<endl;</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure></li>
</ul>
<h2 id="平面切分"><a href="#平面切分" class="headerlink" title="平面切分"></a>平面切分</h2><ul>
<li>题意：平面上有n条直线，其中第i条直线是$y=a_i*x+b_i$,请计算这些直线将平面分成了几个部分。</li>
<li>思路：根据小范围的数据推算可以知道，每新增一条直线所新增平面数与形成的不同交点数有关，若存在n个不同的交点，那么便会新增n+1个平面，由此只需要计算后溪加入的直线与之前的不同交点个数便可以得到答案。</li>
<li>数据结构：<ul>
<li>交点坐标用pair<double,double>键值对来存储</li>
<li>交点坐标的去重通过set<pair<double,double> >来实现</li>
</ul>
</li>
<li>注意：<ul>
<li>可能会有重复的直线，重复的直线不会新增平面数</li>
<li>对于重复直线判断过后还需判断平行直线与相交直线，否则会漏掉情况<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta"># <span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">1e5</span>+<span class="number">5</span>;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> PDD pair<span class="meta-string"><double,double></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> debug(x) cout<<#x<<<span class="meta-string">": "</span><<x<<endl</span></span><br><span class="line"><span class="keyword">double</span> a[<span class="number">100010</span>],b[<span class="number">10010</span>],k[<span class="number">10010</span>];</span><br><span class="line">set<PDD> s;</span><br><span class="line">PDD p;</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;</span><br><span class="line"> cin>>n;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++)</span><br><span class="line"> {</span><br><span class="line"> cin>>a[i]>>b[i];</span><br><span class="line"> k[i]=a[i];</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> ans=<span class="number">2</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">2</span>;i<=n;i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">double</span> aa=a[i];</span><br><span class="line"> <span class="keyword">double</span> bb=b[i];</span><br><span class="line"> <span class="keyword">int</span> flag=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> j=<span class="number">1</span>;j<i;j++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(k[i]==k[j]&&b[i]==b[j]) {flag=<span class="number">1</span>;<span class="keyword">break</span>;}<span class="comment">//注意考虑所有的情况</span></span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span>(k[i]==k[j]) {<span class="keyword">continue</span>;}</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> {</span><br><span class="line"> p.first=(b[j]-bb)/(aa-a[j]);</span><br><span class="line"> p.second=(aa*b[j]-a[j]*bb)/(aa-a[j]);</span><br><span class="line"> s.<span class="built_in">insert</span>(p);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span>(flag==<span class="number">1</span>) {s.<span class="built_in">clear</span>();<span class="keyword">continue</span>;}</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> {</span><br><span class="line"> ans+=(s.<span class="built_in">size</span>()+<span class="number">1</span>);</span><br><span class="line"> s.<span class="built_in">clear</span>(); </span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> cout<<ans<<endl;</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure></li>
</ul>
</li>
</ul>
<h2 id="后缀表达式"><a href="#后缀表达式" class="headerlink" title="后缀表达式"></a>后缀表达式</h2><p>题意：给定n个加号、m个减号以及N+M+1个整数A1,A2,···,A(n+m+1),小明想知道在所有由这N个加号、M个减号以及N+M+1个整数凑出的合法的后缀表达式中，结果最大的是哪一个？</p>
<ul>
<li>思路：本来以为是简单的贪心，排序后加上n+1个大数减去m个小数即为答案，但是实际上如果是中缀表达式那么是这样没错，但是实际上是可以通过加上括号更改计算顺序从而尽可能多的消耗掉减号使答案最大，比如：a-（b-c-d-f-g）（假设都为正数），这样只需要减去一个b即可，那么处理的时候只需要减去最小值即可。</li>
<li>上面也提到了负数结合上减号会对结果有影响，而正数不会，因此需要对负数的个数进行分类：<ol>
<li>没有负数：只需将其他数相加减去最小值接口（若减号为0则不用减）</li>
<li>有负数：<ul>
<li>负数个数小于减号数目：一个负数消耗掉一个减号，多余的减号通过括号让正数添加至负数之后来消耗，这样正数不会是结果减小，如a-（b-c-d-e）（b为负数，c，d，e均为正数）</li>
<li>负数个数大于减号数目：负数从小到大消耗减号即可</li>
</ul>
</li>
</ol>
</li>
<li>注意：以下的方法为先求和再根据时间情况加上或减去应有的数值<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta"># <span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">2e5</span>+<span class="number">10</span>;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> debug(x) cout<<#x<<<span class="meta-string">": "</span><<x<<endl</span></span><br><span class="line">ll a[N];</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> n,m,k;</span><br><span class="line"> cin>>n>>m;</span><br><span class="line"> ll ans=<span class="number">0</span>;</span><br><span class="line"> k=n+m+<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<n+m+<span class="number">1</span>;i++)</span><br><span class="line"> {</span><br><span class="line"> cin>>a[i];</span><br><span class="line"> ans+=a[i];</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">sort</span>(a,a+<span class="number">1</span>+n+m);</span><br><span class="line"> <span class="keyword">if</span>(a[<span class="number">0</span>]>=<span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(m) ans-=<span class="number">2</span>*a[<span class="number">0</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"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<k&&a[i]<<span class="number">0</span>&&m><span class="number">0</span>;i++)</span><br><span class="line"> {</span><br><span class="line"> ans-=a[i]*<span class="number">2</span>;</span><br><span class="line"> m--;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> cout<<ans<<endl;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></li>
</ul>
<h2 id="递增三元组"><a href="#递增三元组" class="headerlink" title="递增三元组"></a>递增三元组</h2><ul>
<li>题意：给定三个整数数组A，B，C，每个数组均有N个数，请你统计有多少个三元组(i, j, k) 满足：<br> 1. 1 <= i, j, k <= N<br> 2. Ai < Bj < Ck<br>（1 <= N <= 100000 0 <= Ai, Bi, Ci <= 100000）</li>
<li>思路一：<br>分别找出A中小于每一个Bi的个数Xi，再找出C中大于于每一个Bi的个数Si,那么对于每一个i，$X_i$*$S_i$之和就是答案。</li>
<li>实现一：看似需要$n^2$的时间复杂度来实现该要求，但实际上通过排序后结合双指针就能够通过$o(N)$的时间复杂度算出上述结果。<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">int</span> a[<span class="number">100010</span>],b[<span class="number">100010</span>],c[<span class="number">100010</span>];</span><br><span class="line"><span class="keyword">int</span> x[<span class="number">100010</span>];</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</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><br><span class="line"> <span class="keyword">int</span> i,j,n;</span><br><span class="line"> ll count=<span class="number">0</span>;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&n);</span><br><span class="line"> <span class="keyword">for</span>(i=<span class="number">0</span>;i<n;i++)</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&a[i]);</span><br><span class="line"> <span class="keyword">for</span>(i=<span class="number">0</span>;i<n;i++)</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&b[i]);</span><br><span class="line"> <span class="keyword">for</span>(i=<span class="number">0</span>;i<n;i++)</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&c[i]);</span><br><span class="line"> <span class="built_in">sort</span>(a,a+n);</span><br><span class="line"> <span class="built_in">sort</span>(b,b+n);</span><br><span class="line"> <span class="built_in">sort</span>(c,c+n);</span><br><span class="line"> i=n<span class="number">-1</span>;</span><br><span class="line"> j=n<span class="number">-1</span>;</span><br><span class="line"> <span class="keyword">while</span>(i>=<span class="number">0</span>&&j>=<span class="number">0</span>)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(a[i]<b[j])<span class="comment">//如果a[i]<b[j]那么a[i]之前的树也全部小于b[j],那么a中小于b[j]的数目有i+1个（下标从0开始）</span></span><br><span class="line"> {</span><br><span class="line"> x[j]=i+<span class="number">1</span>;</span><br><span class="line"> j--;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> i--;</span><br><span class="line"> }</span><br><span class="line"> i=<span class="number">0</span>;</span><br><span class="line"> j=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span>(i<n&&j<n)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(b[i]<c[j])<span class="comment">//如果b[i]<c[j]那么a[i]之后的数也全部大于b[j],那么a中小于b[j]的数目有n-i个（下标从0开始）</span></span><br><span class="line"> {</span><br><span class="line"> count+=(ll)x[i]*(n-j);</span><br><span class="line"> i++;</span><br><span class="line"> } </span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> j++;</span><br><span class="line"> </span><br><span class="line"> } </span><br><span class="line"> cout<<count<<endl;</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></li>
</ul>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://m0nesyol.github.io/wuli-wang.github.io/2022/02/08/%E6%B1%89%E8%AF%BA%E5%A1%94/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/wuli-wang.github.io/images/avatar1.jpg">
<meta itemprop="name" content="wuli-wang">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="wuli-wang'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/wuli-wang.github.io/2022/02/08/%E6%B1%89%E8%AF%BA%E5%A1%94/" class="post-title-link" itemprop="url">汉诺塔</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2022-02-08 09:14:42 / 修改时间：10:04:51" itemprop="dateCreated datePublished" datetime="2022-02-08T09:14:42+08:00">2022-02-08</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/wuli-wang.github.io/categories/%E6%B1%89%E8%AF%BA%E5%A1%94/" itemprop="url" rel="index"><span itemprop="name">汉诺塔</span></a>
</span>
</span>
<span class="post-meta-break"></span>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>613</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>1 分钟</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<span id="more"></span>
<h2 id="汉诺塔问题分析"><a href="#汉诺塔问题分析" class="headerlink" title="汉诺塔问题分析"></a>汉诺塔问题分析</h2><p><img src="/images/loading.png" data-original="/wuli-wang.github.io/wuli-wang.github.io/2022/02/08/%E6%B1%89%E8%AF%BA%E5%A1%94/%E6%B1%89%E8%AF%BA%E5%A1%94.png" alt="汉诺塔"><br>1个盘子：直接移动， “N==1”是递归终结条件。<br>N个盘子：吧移动N个盘子的问题转化为移动N-1盘子的问题。<br>递归解决：<br>(1)把A上面的N-1个盘子移动B（借助C）；<br>(2)把第N个盘子一道C；<br>(3)把B上的N-1个盘子移到C（借助A）<br>结论：n个盘子需要移动2^n-1次便能转移完成</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">int</span> cnt=<span class="number">0</span>;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">hannuo</span><span class="params">(<span class="keyword">int</span> num,<span class="keyword">int</span> src,<span class="keyword">int</span> tmp,<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">if</span>(num==<span class="number">1</span>) </span><br><span class="line"> {</span><br><span class="line"> cnt++;</span><br><span class="line"> cout<<src<<<span class="string">"------>"</span><<dst<<endl;</span><br><span class="line"> <span class="keyword">return</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"> <span class="built_in">hannuo</span>( num<span class="number">-1</span>, src,dst,tmp);</span><br><span class="line"> cout<<src<<<span class="string">"------>"</span><<dst<<endl;</span><br><span class="line"> cnt++;</span><br><span class="line"> <span class="built_in">hannuo</span>( num<span class="number">-1</span>, tmp, src, dst);</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="built_in">hannuo</span>(<span class="number">5</span>,<span class="number">1</span>,<span class="number">2</span>,<span class="number">3</span>);</span><br><span class="line"> cout<<cnt<<endl;</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>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://m0nesyol.github.io/wuli-wang.github.io/2022/01/07/%E7%9F%A5%E8%AF%86%E7%82%B9%E9%80%9F%E8%AE%B0/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/wuli-wang.github.io/images/avatar1.jpg">
<meta itemprop="name" content="wuli-wang">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="wuli-wang'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/wuli-wang.github.io/2022/01/07/%E7%9F%A5%E8%AF%86%E7%82%B9%E9%80%9F%E8%AE%B0/" class="post-title-link" itemprop="url">日常笔记</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2022-01-07 20:08:50" itemprop="dateCreated datePublished" datetime="2022-01-07T20:08:50+08:00">2022-01-07</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2022-06-02 09:50:47" itemprop="dateModified" datetime="2022-06-02T09:50:47+08:00">2022-06-02</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/wuli-wang.github.io/categories/%E7%AC%94%E8%AE%B0/" itemprop="url" rel="index"><span itemprop="name">笔记</span></a>
</span>
</span>
<span class="post-meta-break"></span>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>1.8k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>3 分钟</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<span id="more"></span>
<h2 id="质数的大致数量范围"><a href="#质数的大致数量范围" class="headerlink" title="质数的大致数量范围"></a>质数的大致数量范围</h2><ul>
<li>50000以内的质数共5133个</li>
</ul>
<h2 id="闰年的判断"><a href="#闰年的判断" class="headerlink" title="闰年的判断"></a>闰年的判断</h2><ul>
<li>整百年（世纪年）要整除四百</li>
<li>非整百年（世纪年）只需整除4即可<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">if</span>((year%<span class="number">100</span>!=<span class="number">0</span>&&year%<span class="number">4</span>==<span class="number">0</span>)||(year%<span class="number">400</span>==<span class="number">0</span>))</span><br></pre></td></tr></table></figure></li>
</ul>
<h2 id="平方数规律"><a href="#平方数规律" class="headerlink" title="平方数规律"></a>平方数规律</h2><p>对于任意四个连续的数：$a,b,c,d$，则有$d^2+a^2-b^2-c^2=4$，如$1^2+4^2-2^2-3^2=4$。</p>
<h2 id="平方和公式"><a href="#平方和公式" class="headerlink" title="平方和公式"></a>平方和公式</h2><p>$ \sum _{i=1}^{n}i^2=n∗(n+1)∗(2*n+1)/6$</p>
<h2 id="约数个数（涨知识啦）"><a href="#约数个数（涨知识啦）" class="headerlink" title="约数个数（涨知识啦）"></a>约数个数（涨知识啦）</h2><ul>
<li><p>对于任意一个数W，他的约数个数是多少？假设W的质因子分解式是$W=a1^{p1}+a2^{p2}+……+an^{pn}$（a1…an均为质因子）,那么W的约数个数就是**(p1+1)*(p2+1)*……*(pn+1)**。</p>
</li>
<li><p><a target="_blank" rel="noopener" href="https://www.lanqiao.cn/problems/806/learning/">序列求和</a>:现已知约数个数n，求最小的具有n个约数的数$S_n$是是多少,求$S_1+…+S_{60}$？</p>
<ul>
<li>将n进行质因数分解$n=(p_1+1)<em>(p_2+1)</em>…(p_n+1)$,那么$p_1…p_n$即为$S_n$质因数分解后的质因子的指数，要保证X最小，那么只需要从最小的质数开始选择即可。如n=4,$4=(1+1)<em>(1+1)$,那么$S_4=2^1</em>3^1=6$。</li>
<li>故需要对n进行因式分解取其中使得$S_n$最小的情形，一开始认为每次取最小的因子将n分解，这样每一个指数就会越小，但同样质因子的个数会增加（如$24=2<em>2</em>2<em>3$ | $24=4</em>3*2$，此时取后一种情形更加），因此不能盲目的贪心，那么就只能通过搜索暴力求解了。</li>
</ul>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ll long long</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> pb push_back</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> db double</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> mp make_pair</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> lson l,mid,num<<1</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> rson mid+1,r,num<<1|1</span></span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> mod=<span class="number">1000000007</span>;</span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> N=<span class="number">5e5</span>+<span class="number">10</span>;</span><br><span class="line">vector<<span class="keyword">int</span>>prime;</span><br><span class="line"><span class="keyword">bool</span> ppp[<span class="number">5000010</span>];</span><br><span class="line"><span class="function">ll <span class="title">qpow</span><span class="params">(ll base,ll num)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> ll an=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span>(num)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(num&<span class="number">1</span>) an=an*base;</span><br><span class="line"> num>>=<span class="number">1</span>;</span><br><span class="line"> base=base*base;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> an;</span><br><span class="line">}</span><br><span class="line"><span class="function">ll <span class="title">gcd</span><span class="params">(ll a,ll b)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span>(b==<span class="number">0</span>) <span class="keyword">return</span> a;</span><br><span class="line"> <span class="keyword">return</span> <span class="built_in">gcd</span>(b,a%b);</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">get_prime</span><span class="params">(<span class="keyword">int</span> num)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> i,j;</span><br><span class="line"> <span class="keyword">for</span>(i=<span class="number">2</span>;i<=num;i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(!ppp[i])</span><br><span class="line"> prime.<span class="built_in">pb</span>(i);</span><br><span class="line"> <span class="keyword">for</span>(j=<span class="number">0</span>;j<prime.<span class="built_in">size</span>()&&i*prime[j]<=num;j++)</span><br><span class="line"> ppp[i*prime[j]]=<span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"><span class="keyword">int</span> k[<span class="number">6</span>];</span><br><span class="line">ll ans=<span class="number">1</span>;</span><br><span class="line">ll res[<span class="number">61</span>];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</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> coun=<span class="number">1</span>,i;</span><br><span class="line"> <span class="keyword">for</span>(i=<span class="number">0</span>;i<<span class="number">6</span>;i++)</span><br><span class="line"> coun*=(k[i]+<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">if</span>(coun><span class="number">60</span>) <span class="keyword">return</span>;</span><br><span class="line"> <span class="keyword">for</span>(i=<span class="number">1</span>;i<<span class="number">6</span>;i++)</span><br><span class="line"> <span class="keyword">if</span>(k[i]>k[i<span class="number">-1</span>]) <span class="keyword">return</span>;</span><br><span class="line"> ll sum=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(i=<span class="number">0</span>;i<<span class="number">6</span>;i++)</span><br><span class="line"> sum*=<span class="built_in">qpow</span>(prime[i],k[i]);</span><br><span class="line"> res[coun]=<span class="built_in">min</span>(res[coun],sum);</span><br><span class="line"> <span class="keyword">for</span>(i=<span class="number">0</span>;i<<span class="number">6</span>;i++)</span><br><span class="line"> {</span><br><span class="line"> k[i]++;</span><br><span class="line"> <span class="built_in">dfs</span>();</span><br><span class="line"> k[i]--;</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="built_in">get_prime</span>(<span class="number">16</span>);</span><br><span class="line"> k[<span class="number">0</span>]=<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">60</span>;i++) res[i]=<span class="number">1e18</span>;</span><br><span class="line"> <span class="built_in">dfs</span>();</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">2</span>;i<=<span class="number">60</span>;i++)</span><br><span class="line"> ans+=res[i];</span><br><span class="line"> cout<<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></li>
</ul>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://m0nesyol.github.io/wuli-wang.github.io/2021/11/26/%E7%82%B9%E5%88%86%E6%B2%BB/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/wuli-wang.github.io/images/avatar1.jpg">
<meta itemprop="name" content="wuli-wang">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="wuli-wang'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/wuli-wang.github.io/2021/11/26/%E7%82%B9%E5%88%86%E6%B2%BB/" class="post-title-link" itemprop="url">点分治</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-11-26 13:11:27 / 修改时间：20:48:50" itemprop="dateCreated datePublished" datetime="2021-11-26T13:11:27+08:00">2021-11-26</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/wuli-wang.github.io/categories/%E5%9B%BE%E8%AE%BA/" itemprop="url" rel="index"><span itemprop="name">图论</span></a>
</span>
</span>
<span class="post-meta-break"></span>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>7.8k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>14 分钟</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<span id="more"></span>
<h2 id="点分治前置知识"><a href="#点分治前置知识" class="headerlink" title="点分治前置知识"></a>点分治前置知识</h2><ol>
<li><p>点分治的基本思想</p>
<pre><code> 点分治，顾名思义就是基于树上的节点进行分治。
如果我们在深入一点呢？对于点的拆开其实就是对于树的拆开。
所以我认为点分治的本质其实是将一棵树拆分成许多棵子树处理，并不断进行。
这应该也是点分治的精髓。
</code></pre>
</li>
<li><p>分治点的选择</p>
<pre><code> 既然我们要将一个点进行分治，那么选点肯定最首要的。
思考下面一个问题：
如果树退化为一个链，我们选取链首作为分治点，理论时间复杂度？
而如果选择链的中心，它的理论时间复杂度又是多少？
答案其实还是挺简单的。
选择链首：O( n )
选择链心：O( logn )
通过这个例子,我们不难发现：
如果选点后左右子树越大，递归层数越多，时间越慢，反之则越快。
所以我们的选点标准就出来了，而我们把有这个性质的点叫做：树的重心！
</code></pre>
</li>
</ol>
<h2 id="重心"><a href="#重心" class="headerlink" title="重心"></a>重心</h2><ul>
<li>重心的性质及证明：<a target="_blank" rel="noopener" href="https://www.cnblogs.com/suxxsfe/p/13543253.html">大佬的博客</a></li>
</ul>
<ol>
<li>树的重心如果不唯一，则至多有两个，且这两个重心相邻</li>
</ol>
<ul>
<li><p>先假设有两个重心 u,v 不相邻，考虑它们之间的这条路径，则至少有三个节点（以下的 “它们之间的路径” 都是指 u,v 之间的路径）</p>
</li>
<li><p>设 u 的不包含它们之间的这条路径的若干子树中（就是有一个子树是以它们路径上与 u 相邻的那个点为根的，先排除那个子树），最小的子树大小是 sizeu，则 v 的包含它们路径的那个子树的大小为 sizeu+k,k≥2。那么这个子树不能是 u 的大小最大的子树，否则 v 的这个包含它们之间的路径的子树，大小比它还大，v 就不是重心了</p>
</li>
<li><p>对 v 进行相同的分析，得到同样结论</p>
</li>
<li><p>那么 u,v 最大的子树就只能分别是包含它们之间路径的那个子树，假设从它们之间的路径上（不包含它们）的点，延伸出去的点的个数为 size（这个 size 已经把路径上的点算上了），则它们这个最大的子树的大小就分别是 v,u 的不包含它们之间路径的子树的大小和，加 size+1，又因为它们都是重心，最大子树都最小，则上面所述的这个 “v,u 的不包含它们之间路径的子树的大小和” 应该相等，设其为 size′</p>
</li>
<li><p>但是发现，若从它们之间的路径上（不包含它们本身）取一点，则这个点沿着它们之间路径的两个子树应该都小于 size′+size+1，而其他子树显然都小于 size′，那么 u,v 都不是重心，矛盾</p>
</li>
<li><p>则重心必须相邻，又因为这是一个树，所以最多只有两个点相邻，最多两个重心.</p>
</li>
</ul>
<ol start="2">
<li>一个点是重心，等价于，以这个点为根，它的每个子树的大小，都不会超过整个树大小的一半</li>
</ol>
<ul>
<li><p>假设重心是 u，它的一个子树大小超过整个树大小的一半，设这个子树的根是 v（与 u 相邻）</p>
</li>
<li><p>用 sizei 表示以 i 为根的子树大小，则 sizev>sizeu2</p>
</li>
<li><p>那么，u 除了子树 v 以外的其它所有子树（把 u 本身也计算在内）的大小是 $size_u−size_v$</p>
</li>
<li><p>所以，如果以 v 为重心，则它的一个子树是 sizeu−sizev，这个子树就是以 u 为根的那个。$size_u−size_v<size_v$，此时，v “往上”的那个以 u 为根的子树小于 u 的最大子树大小，而其他“往下”的子树显然也小于，所以可以说明，也说明如果以 v 为重心，最大子树的大小小于以 u 为根最大子树的大小，则矛盾。得证</p>
</li>
<li><p>再来推若每个子树都不超过整个树的一半，那么一定是重心</p>
</li>
<li><p>设这个每个子树都不超过整个树一半的节点为 u，重心为 v，考虑 u,v 之间的路径<br>v 总会有一个子树包含 u，（就是包含它们之间路径的那一个），从而包含了，u 的除了包含这它们之间路径的那个子树，的所有其他子树，由于 u 任意子树大小小于总体的一半，所以 v 的这个子树，也就是 u 的剩余所有子树，大小 ≥sizeu2</p>
</li>
<li><p>那么显然 v 不是重心，矛盾。这样，对于任意的 v≠u，都不是重心，则 u 是重心（当然可能存在一个相邻的点，使得它们都有一个等于整体一半的子树，那么就是有两个重心的情况）</p>
</li>
<li><p>则也就顺带着说明了，只有在总点数为偶数时，才可能会出现有两个重心的情况，这两个重心相邻，且都只有两个子树，大小分别为 num2,num2−1</p>
</li>
</ul>
<ol start="3">
<li>树中所有点到某个点的距离和中，到重心的距离和是最小的。如果有两个重心，那么到它们的距离和一样。更进一步，距离和最小与是重心等价</li>
</ol>
<ul>
<li><p>一开始想大力推式子然后反证法证明，结果推了半天发现好像假了</p>
</li>
<li><p>实际上应该是用调整法</p>
</li>
<li><p>就是先假设当前选择一个点 u，然后看我们把选择的点调整到一个与 u 相邻的点，看能不能使得距离和更小</p>
</li>
<li><p>什么样的点能满足上面的性质？那就是以它为根的子树大小大于以 u 为根的大小的一半的点，这样让那些其他子树的一共小于一半的点多走 1，让这大于一半的点少走 1，总体少走了</p>
</li>
<li><p>直到所有相邻节点为根的子树都小于当前的 u 的一半，那么无论往哪个点上再进行移动，都只会使距离和更大，而这样的点，就是重心，得证</p>
</li>
</ul>
<ol start="4">
<li>如果一个树增添，或删去一个叶子，则整个树的同一个重心最多移动一个节点</li>
</ol>
<ul>
<li><p>如果是增加节点，那么如果需要移动的话，则是沿着重心和新增的节点之间的路径来移动，这种情况肯定是因为新增节点使得包含它们之间路径的那个子树过大（大于整个树的一半，根据第二条性质）。而往那移动一位，就会让这个子树减少的大小大于等于一，那么就又小于等于了这个树的一半，又由于树最多有两个重心且我们讨论的是“同一个重心”的移动，所以移动一次就够了，移动更多就又不是重心了</p>
</li>
<li><p>如果是删除节点，删除以后导致包含被删除的节点的子树大小减小，那么其他子树可能就大于整个树大小的一半了。则重心往这个子树上移动一位，至于为什么只移动一位，和上面的分析相似</p>
</li>
</ul>
<ol start="5">
<li>通过连接一条端点分别在两个树的边，来将两个树合并成一个，那么新的重心肯定是在原来这两个树的重心的路径上</li>
</ol>
<ul>
<li><p>不妨假设连接的两个点就是两个树原来的根</p>
</li>
<li><p>然后可以发现，仍然可以用一种不断调整的方法，假设原先两个重心分别是 u,v，从 u 开始调整，当目前仍在 u 所在的原先的那颗树中时，肯定是朝着根调整，因为是根那个方向被接入了另一个树导致大小变大</p>
</li>
<li><p>如果还没调整到原先的根，就符合了最大子树小于等于总结点数一半的条件，自然符合性质，这就说明了，如果新重心在原来 u 所在的那个子树上的话，一定在 u 到它原来的根的路径上</p>
</li>
<li><p>同理可以说明，如果新重心在 v 所在的那个子树上，一定在 u 到它原来那个根的路径上<br>把这两个合起来就是本条性质了</p>
</li>
</ul>
<h2 id="点分治入门"><a href="#点分治入门" class="headerlink" title="点分治入门"></a>点分治入门</h2><ul>
<li>题意：给定一棵带权树，求出树上长度小于等于k的路径树。</li>
</ul>
<p>Solution：</p>
<ul>
<li><p>选定树上一个点，那么树上所有的路径可以分为进过该点的路径和不经过该点的路径，那么便可以对该点进行<strong>点分治</strong>。那么应该选取哪个点呢？在了解了重心的概念及作用后便应该明白应该选择重心来作为分治点。</p>
</li>
<li><p>在选取分治点后应该分开求两种路径满足条件的有多少条路径。经过该点的路径求法：求出所有子树中的点到该分治点的距离d，用数组d保存，而经过该点的路径即为从任意两棵子树中选取某条路径进行拼接。这里可以用到树状数组记录个长度路径的条数，当求出一棵子树的所有路径后去树状数组中查找路径<=k-d[i]的路径树即getsum(k-d[i])，此时再将这棵子树的路径信息插入树状数组，对于该分治点的所有子树按顺序进行上述过程能够不重复的统计出所有路径信息。</p>
</li>
<li><p>需要注意的是当对其子树统计答案时树状数组的值应该重置，将其中直接全部置为0复杂度为o（数组长度），当子树较多时重置次数也随之上升，可能超出时限。因此可以通过再进行一次dfs扫描出上述的所有路径（因为求子树中所有点到分治点的距离也是跑一遍dfs），将其值-1更新，这样复杂度最多只有o（n（点的个数））。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br><span class="line">129</span><br><span class="line">130</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta"># <span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN=<span class="number">4e4</span>+<span class="number">10</span>;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> pair<<span class="keyword">int</span>,<span class="keyword">int</span>> PII;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> endl <span class="meta-string">'\n'</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> debug(x) cout<<#x<<<span class="meta-string">": "</span><<x<<endl</span></span><br><span class="line"><span class="keyword">int</span> n,K,cnt=<span class="number">0</span>,rt;<span class="comment">//rt全局变量记录重心</span></span><br><span class="line"><span class="keyword">int</span> tree[MAXN],sz[MAXN],d[MAXN];</span><br><span class="line"><span class="keyword">bool</span> vis[MAXN];</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">edge</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> v,w;</span><br><span class="line"> <span class="built_in">edge</span>(<span class="keyword">int</span> a,<span class="keyword">int</span> b){v=a;w=b;}</span><br><span class="line">};</span><br><span class="line">vector<edge> adj[MAXN];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">update</span><span class="params">(<span class="keyword">int</span> x,<span class="keyword">int</span> k)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">while</span>(x<=K)</span><br><span class="line"> {</span><br><span class="line"> tree[x]+=k;</span><br><span class="line"> x+=x&-x;</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">getsum</span><span class="params">(<span class="keyword">int</span> x)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> res=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span>(x)</span><br><span class="line"> {</span><br><span class="line"> res+=tree[x];</span><br><span class="line"> x-=x&-x;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> res;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs_rt</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> fa,<span class="keyword">int</span> tot)</span><span class="comment">//dfs求重心</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> sz[u]=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">int</span> maxn=<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<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> v=adj[u][i].v;</span><br><span class="line"> <span class="keyword">if</span>(v==fa||vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="built_in">dfs_rt</span>(v,u,tot);</span><br><span class="line"> sz[u]+=sz[v];</span><br><span class="line"> maxn=<span class="built_in">max</span>(maxn,sz[v]);<span class="comment">//记录最大子树的大小</span></span><br><span class="line"> }</span><br><span class="line"> maxn=<span class="built_in">max</span>(maxn,tot-sz[u]);<span class="comment">//因为是无根树，前面的子树也应该算进去取最大值</span></span><br><span class="line"> <span class="keyword">if</span>(maxn*<span class="number">2</span><=tot) rt=u;<span class="comment">//最大子树大小（点的数目）不超过tot/2即为重心</span></span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs_sz</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> fa)</span><span class="comment">//分治之后需要重新求一遍子树的大小</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> sz[u]=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> v=adj[u][i].v;</span><br><span class="line"> <span class="keyword">if</span>(v==fa||vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="built_in">dfs_sz</span>(v,u);</span><br><span class="line"> sz[u]+=sz[v];</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_dis</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> fa,<span class="keyword">int</span> dis)</span><span class="comment">//记录该子树所有点到分支点的距离</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> d[++cnt]=dis;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> v=adj[u][i].v;</span><br><span class="line"> <span class="keyword">int</span> w=adj[u][i].w;</span><br><span class="line"> <span class="keyword">if</span>(v==fa||vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="built_in">dfs_dis</span>(v,u,dis+w);</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_clear</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> fa,<span class="keyword">int</span> dis)</span><span class="comment">//清空树状数组</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">if</span>(dis) <span class="built_in">update</span>(dis,<span class="number">-1</span>);</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> v=adj[u][i].v;</span><br><span class="line"> <span class="keyword">int</span> w=adj[u][i].w;</span><br><span class="line"> <span class="keyword">if</span>(v==fa||vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="built_in">dfs_clear</span>(v,u,dis+w);</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">divide</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> tot)</span><span class="comment">//点分治</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> ans=<span class="number">0</span>,v,w;</span><br><span class="line"> <span class="built_in">dfs_rt</span>(u,<span class="number">0</span>,tot);<span class="comment">//找重心</span></span><br><span class="line"> u=rt;<span class="comment">//重心的值赋值给u，使变量统一</span></span><br><span class="line"> vis[u]=<span class="number">1</span>;<span class="comment">//将分治点进行标记，也相当于设置边界，分治之后不能再遍历分治点</span></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> v=adj[u][i].v;</span><br><span class="line"> w=adj[u][i].w;</span><br><span class="line"> <span class="keyword">if</span>(vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> cnt=<span class="number">0</span>;</span><br><span class="line"> <span class="built_in">dfs_dis</span>(v,u,w);<span class="comment">//遍历该子树，d数组存下该子树所有点到该分治点的距离</span></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=cnt;i++)<span class="comment">//统计答案</span></span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">if</span>(d[i]<=K) ans++;</span><br><span class="line"> ans+=<span class="built_in">getsum</span>(<span class="built_in">max</span>(<span class="number">0</span>,K-d[i]));</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=cnt;i++)<span class="comment">//更新树状数组</span></span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">update</span>(d[i],<span class="number">1</span>);<span class="comment">//长度为d[i]的路径条数+1</span></span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">dfs_clear</span>(u,<span class="number">0</span>,<span class="number">0</span>);<span class="comment">//清空</span></span><br><span class="line"> <span class="built_in">dfs_sz</span>(u,<span class="number">0</span>);<span class="comment">//以重心为根，跑出所有点的子树大小</span></span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> v=adj[u][i].v;</span><br><span class="line"> <span class="keyword">if</span>(vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> ans+=<span class="built_in">divide</span>(v,sz[v]);<span class="comment">//递归求子树中的答案</span></span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> ans;</span><br><span class="line">}</span><br><span class="line"><span 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> u,v,w;</span><br><span class="line"> ios::<span class="built_in">sync_with_stdio</span>(<span class="literal">false</span>);</span><br><span class="line"> cin>>n;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<n;i++)</span><br><span class="line"> {</span><br><span class="line"> cin>>u>>v>>w;</span><br><span class="line"> adj[u].<span class="built_in">push_back</span>(edge{v,w});</span><br><span class="line"> adj[v].<span class="built_in">push_back</span>(edge{u,w});</span><br><span class="line"> }</span><br><span class="line"> cin>>K;</span><br><span class="line"> cout<<<span class="built_in">divide</span>(<span class="number">1</span>,n)<<endl;</span><br><span class="line">}</span><br></pre></td></tr></table></figure></li>
</ul>
<h2 id="点分治-树形dp"><a href="#点分治-树形dp" class="headerlink" title="点分治+树形dp"></a>点分治+树形dp</h2><ul>
<li>题意：给定一棵n个点的树，每个点都有一个权值，求出所有连通子图的权值和在[1 - m]之间的权值和。</li>
</ul>
<p>Solution</p>
<ul>
<li>此题m值较小，可以利用bitset的性质快速维护权值和的信息。</li>
<li>对于每一个点来说，该树上的联通子图可以分为包含该点的联通子图和不包含该点的联通子图，因此可以想到选取该树的重心作为分治点进行分治。</li>
<li>对于每个分治点u来说，dp[u]表示包含点u的非联通子图的权值和，dp[u]|=dp[v]（v为u的邻接点，此时dp[v]表示既包含点u又包含点v的所有非联通子图的权值和，因为前提是求的包含点u的非联通子图的权值和）<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta"># <span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXN=<span class="number">3e3</span>+<span class="number">10</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAXSUM=<span class="number">1e5</span>+<span class="number">10</span>;</span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="keyword">typedef</span> pair<<span class="keyword">int</span>,<span class="keyword">int</span>> PII;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> endl <span class="meta-string">'\n'</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> debug(x) cout<<#x<<<span class="meta-string">": "</span><<x<<endl</span></span><br><span class="line"><span class="keyword">int</span> n,m,rt,sz[MAXN],val[MAXN],d[MAXN],cnt;</span><br><span class="line"><span class="keyword">bool</span> vis[MAXN];</span><br><span class="line">bitset<MAXSUM> ans,dp[MAXN];</span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">edge</span></span></span><br><span class="line"><span class="class">{</span></span><br><span class="line"> <span class="keyword">int</span> v,w;</span><br><span class="line"> <span class="built_in">edge</span>(<span class="keyword">int</span> a,<span class="keyword">int</span> b){v=a;w=b;}</span><br><span class="line">};</span><br><span class="line">vector<edge> adj[MAXN];</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> v)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> adj[u].<span class="built_in">push_back</span>(edge{v,<span class="number">0</span>});</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs_rt</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> fa,<span class="keyword">int</span> tot)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">int</span> maxn=<span class="number">0</span>;</span><br><span class="line"> sz[u]=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> v=adj[u][i].v;</span><br><span class="line"> <span class="keyword">if</span>(v==fa||vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="built_in">dfs_rt</span>(v,u,tot);</span><br><span class="line"> sz[u]+=sz[v];</span><br><span class="line"> maxn=<span class="built_in">max</span>(sz[v],maxn);</span><br><span class="line"> }</span><br><span class="line"> maxn=<span class="built_in">max</span>(maxn,tot-sz[u]);</span><br><span class="line"> <span class="keyword">if</span>(maxn*<span class="number">2</span><=tot) rt=u;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs_sz</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> fa)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> sz[u]=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> v=adj[u][i].v;</span><br><span class="line"> <span class="keyword">if</span>(v==fa||vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="built_in">dfs_sz</span>(v,u);</span><br><span class="line"> sz[u]+=sz[v];</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> fa)</span>求包含点u的非联通子图的权值和</span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> dp[u]<<=val[u];</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> v=adj[u][i].v;</span><br><span class="line"> <span class="keyword">if</span>(v==fa||vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> dp[v]=dp[u];<span class="comment">//复制父节点的权值和信息</span></span><br><span class="line"> <span class="built_in">solve</span>(v,u);</span><br><span class="line"> dp[u]|=dp[v];</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">divide</span><span class="params">(<span class="keyword">int</span> u,<span class="keyword">int</span> tot)</span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="built_in">dfs_rt</span>(u,<span class="number">0</span>,tot);</span><br><span class="line"> u=rt;</span><br><span class="line"> vis[u]=<span class="number">1</span>;<span class="comment">//用完分治点之后将该点标记并丢掉</span></span><br><span class="line"> dp[u].<span class="built_in">reset</span>();</span><br><span class="line"> dp[u][<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"> <span class="built_in">solve</span>(u,<span class="number">0</span>);</span><br><span class="line"> ans|=dp[u];<span class="comment">//包含点u的连通子图的所有权值和加入ans</span></span><br><span class="line"></span><br><span class="line"> <span class="built_in">dfs_sz</span>(u,<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<adj[u].<span class="built_in">size</span>();i++)</span><br><span class="line"> {</span><br><span class="line"> <span class="keyword">int</span> v=adj[u][i].v;</span><br><span class="line"> <span class="keyword">if</span>(vis[v]) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="built_in">divide</span>(v,sz[v]);</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"> ios::<span class="built_in">sync_with_stdio</span>(<span class="literal">false</span>);</span><br><span class="line"> <span class="keyword">int</span> t,u,v;</span><br><span class="line"> cin>>t;</span><br><span class="line"> <span class="keyword">while</span>(t--)</span><br><span class="line"> {</span><br><span class="line"> <span class="built_in">memset</span>(vis,<span class="number">0</span>,<span class="built_in"><span class="keyword">sizeof</span></span>(vis));</span><br><span class="line"> ans.<span class="built_in">reset</span>();</span><br><span class="line"> cin>>n>>m;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<n;i++)</span><br><span class="line"> {</span><br><span class="line"> cin>>u>>v;</span><br><span class="line"> <span class="built_in">add</span>(u,v);</span><br><span class="line"> <span class="built_in">add</span>(v,u);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) cin>>val[i];</span><br><span class="line"> <span class="built_in">divide</span>(<span class="number">1</span>,n);</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=m;i++) cout<<ans[i];</span><br><span class="line"> cout<<endl;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++) adj[i].<span class="built_in">clear</span>();</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">2</span></span><br><span class="line"><span class="comment">6 10</span></span><br><span class="line"><span class="comment">1 2</span></span><br><span class="line"><span class="comment">1 3</span></span><br><span class="line"><span class="comment">2 5</span></span><br><span class="line"><span class="comment">3 4</span></span><br><span class="line"><span class="comment">3 6</span></span><br><span class="line"><span class="comment">1 3 5 7 9 11</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment">4 10</span></span><br><span class="line"><span class="comment">1 2</span></span><br><span class="line"><span class="comment">2 3</span></span><br><span class="line"><span class="comment">3 4</span></span><br><span class="line"><span class="comment">3 2 7 5</span></span><br><span class="line"><span class="comment">*/</span></span><br></pre></td></tr></table></figure></li>
</ul>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://m0nesyol.github.io/wuli-wang.github.io/2021/11/24/Math/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/wuli-wang.github.io/images/avatar1.jpg">
<meta itemprop="name" content="wuli-wang">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="wuli-wang'blog">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/wuli-wang.github.io/2021/11/24/Math/" class="post-title-link" itemprop="url">Math</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-11-24 14:55:32" itemprop="dateCreated datePublished" datetime="2021-11-24T14:55:32+08:00">2021-11-24</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2022-06-05 10:21:40" itemprop="dateModified" datetime="2022-06-05T10:21:40+08:00">2022-06-05</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/wuli-wang.github.io/categories/Math/" itemprop="url" rel="index"><span itemprop="name">Math</span></a>
</span>
</span>
<span class="post-meta-break"></span>
<span class="post-meta-item" title="本文字数">
<span class="post-meta-item-icon">
<i class="far fa-file-word"></i>
</span>
<span class="post-meta-item-text">本文字数：</span>
<span>2.4k</span>
</span>
<span class="post-meta-item" title="阅读时长">
<span class="post-meta-item-icon">
<i class="far fa-clock"></i>
</span>
<span class="post-meta-item-text">阅读时长 ≈</span>
<span>4 分钟</span>