-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathindex.html
1235 lines (811 loc) · 114 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="en">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 6.2.0">
<link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/favicon-32x32-next.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/favicon-16x16-next.png">
<link rel="mask-icon" href="/images/logo.svg" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="/lib/font-awesome/css/all.min.css">
<script id="hexo-configurations">
var NexT = window.NexT || {};
var CONFIG = {"hostname":"crer-lu.github.io","root":"/","scheme":"Pisces","version":"7.8.0","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12,"onmobile":false},"copycode":{"enable":false,"show_result":false,"style":null},"back2top":{"enable":true,"sidebar":false,"scrollpercent":true},"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":"valine","storage":true,"lazyload":false,"nav":null,"activeClass":"valine"},"algolia":{"hits":{"per_page":10},"labels":{"input_placeholder":"Search for Posts","hits_empty":"We didn't find any results for the search: ${query}","hits_stats":"${hits} results found in ${time} ms"}},"localsearch":{"enable":"enable","trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false},"motion":{"enable":false,"async":false,"transition":{"post_block":"fadeIn","post_header":"slideDownIn","post_body":"slideDownIn","coll_header":"slideLeftIn","sidebar":"slideUpIn"}},"path":"search.xml"};
</script>
<meta property="og:type" content="website">
<meta property="og:title" content="Blog by Crer_lu">
<meta property="og:url" content="https://crer-lu.github.io/index.html">
<meta property="og:site_name" content="Blog by Crer_lu">
<meta property="og:locale" content="en_US">
<meta property="article:author" content="Fengjie Lu">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="https://crer-lu.github.io/">
<script id="page-configurations">
// https://hexo.io/docs/variables.html
CONFIG.page = {
sidebar: "",
isHome : true,
isPost : false,
lang : 'en'
};
</script>
<title>Blog by Crer_lu</title>
<noscript>
<style>
.use-motion .brand,
.use-motion .menu-item,
.sidebar-inner,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-header { opacity: initial; }
.use-motion .site-title,
.use-motion .site-subtitle {
opacity: initial;
top: initial;
}
.use-motion .logo-line-before i { left: initial; }
.use-motion .logo-line-after i { right: initial; }
</style>
</noscript>
</head>
<body itemscope itemtype="http://schema.org/WebPage">
<div class="container">
<div class="headband"></div>
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="Toggle navigation bar">
<span class="toggle-line toggle-line-first"></span>
<span class="toggle-line toggle-line-middle"></span>
<span class="toggle-line toggle-line-last"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<span class="logo-line-before"><i></i></span>
<h1 class="site-title">Blog by Crer_lu</h1>
<span class="logo-line-after"><i></i></span>
</a>
<p class="site-subtitle" itemprop="description">recording my learning and life</p>
</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 id="menu" class="main-menu menu">
<li class="menu-item menu-item-home-page">
<a href="/" rel="section"><i class="fa fa-home fa-fw"></i>Home Page</a>
</li>
<li class="menu-item menu-item-about-&-life-saving">
<a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>About & Life Saving</a>
</li>
<li class="menu-item menu-item-tags">
<a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>Tags</a>
</li>
<li class="menu-item menu-item-archives">
<a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>Archives</a>
</li>
<li class="menu-item menu-item-guestbook">
<a href="/guestbook/" rel="section"><i class="fa fa-comment fa-fw"></i>Comment</a>
</li>
<li class="menu-item menu-item-search">
<a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>Search
</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"
placeholder="Searching..." spellcheck="false"
type="search" class="search-input">
</div>
<span class="popup-btn-close">
<i class="fa fa-times-circle"></i>
</span>
</div>
<div id="search-result">
<div id="no-result">
<i class="fa fa-spinner fa-pulse fa-5x fa-fw"></i>
</div>
</div>
</div>
</div>
</div>
</header>
<div class="back-to-top">
<i class="fa fa-arrow-up"></i>
<span>0%</span>
</div>
<main class="main">
<div class="main-inner">
<div class="content-wrap">
<div class="content index posts-expand">
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/3ad5a5a9/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/3ad5a5a9/" class="post-title-link" itemprop="url">C指针传参的一个陷阱</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-05-26 15:56:01" itemprop="dateCreated datePublished" datetime="2023-05-26T15:56:01+08:00">2023-05-26</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">Edited on</span>
<time title="Modified: 2023-11-06 16:56:58" itemprop="dateModified" datetime="2023-11-06T16:56:58+08:00">2023-11-06</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="C指针传参的一个陷阱"><a href="#C指针传参的一个陷阱" class="headerlink" title="C指针传参的一个陷阱"></a>C指针传参的一个陷阱</h1><p>今天写密码学的作业，调bug调了好久，原因是这样一个函数</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">aes_polynomial_mul</span><span class="params">(<span class="type">unsigned</span> <span class="type">char</span> x[<span class="number">4</span>], <span class="type">unsigned</span> <span class="type">char</span> y[<span class="number">4</span>], <span class="type">unsigned</span> <span class="type">char</span> z[<span class="number">4</span>])</span>;</span><br></pre></td></tr></table></figure>
<p>函数定义是 有限域GF(2^8)多项式乘法（具体细节不展开）</p>
<p>由于计算时是矩阵形式乘法，所以x，y的每一项都将参与到结果z的每一项的计算中</p>
<p>那当你计算一项就修改一项，四次循环退出，有没有什么问题呢？</p>
<p><strong>有！有大问题！</strong></p>
<p>比如我们考虑这样一个情况：aes_polynomial_mul（a, b, b）</p>
<p>那我们第一轮循环计算出b[1]，值做了更新后，后面三轮的结果就全都不对了</p>
<p>因此我们在实现的时候要重新声明一个unsigned char数组出来</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">aes_polynomial_mul</span><span class="params">(<span class="type">unsigned</span> <span class="type">char</span> x[<span class="number">4</span>], <span class="type">unsigned</span> <span class="type">char</span> y[<span class="number">4</span>], <span class="type">unsigned</span> <span class="type">char</span> z[<span class="number">4</span>])</span></span><br><span class="line">{</span><br><span class="line"> <span class="comment">/* 有限域GF(2^8)多项式乘法,</span></span><br><span class="line"><span class="comment"> 4</span></span><br><span class="line"><span class="comment"> 计算z = x * y mod (x + 1);</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="comment">/* 3 2</span></span><br><span class="line"><span class="comment"> 当被乘数为多项式3X + X + X + 2的4个系数{3, 1, 1, 2}时, 转化成矩阵为:</span></span><br><span class="line"><span class="comment"> 2 3 1 1</span></span><br><span class="line"><span class="comment"> 1 2 3 1</span></span><br><span class="line"><span class="comment"> 1 1 2 3</span></span><br><span class="line"><span class="comment"> 3 1 1 2</span></span><br><span class="line"><span class="comment"> 3 2</span></span><br><span class="line"><span class="comment"> 当被乘数为多项式0xB*X + 0xD*X + 0x9*X + 0xE的4个系数{0xB, 0xD, 0x9, 0xE}时, 转化成矩阵为:</span></span><br><span class="line"><span class="comment"> E B D 9</span></span><br><span class="line"><span class="comment"> 9 E B D</span></span><br><span class="line"><span class="comment"> D 9 E B</span></span><br><span class="line"><span class="comment"> B D 9 E</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment"> 乘数也是一个3次多项式, 它的4个系数保存在y中;</span></span><br><span class="line"><span class="comment"></span></span><br><span class="line"><span class="comment"> 4</span></span><br><span class="line"><span class="comment"> x * y mod (x + 1)的计算结果仍是一个3次多项式, 它的4个系数保存在z中.</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="comment">// x 被乘数</span></span><br><span class="line"> <span class="type">int</span> i, j;</span><br><span class="line"> <span class="type">unsigned</span> <span class="type">char</span> tmp[<span class="number">4</span>]; <span class="comment">// tmp[4]用于保存计算结果的四个系数的四个部分,</span></span><br><span class="line"> <span class="keyword">for</span>(i = <span class="number">0</span>; i < <span class="number">4</span>; ++ i){</span><br><span class="line"> tmp[i] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(j = <span class="number">0</span>; j < <span class="number">4</span>; ++ j){</span><br><span class="line"> tmp[i] = aes_add(tmp[i], (<span class="type">unsigned</span> <span class="type">char</span>)aes_8bit_mul_mod_0x11B(x[(j + <span class="number">3</span> - i) % <span class="number">4</span>], y[j]));</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span>(i = <span class="number">0</span>; i < <span class="number">4</span>; ++ i)</span><br><span class="line"> z[i] = tmp[i]; </span><br><span class="line"> <span class="keyword">return</span> ;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/dcdccc53/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/dcdccc53/" class="post-title-link" itemprop="url">C++异常处理学习</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-04-10 10:16:13 / Modified: 10:33:04" itemprop="dateCreated datePublished" datetime="2023-04-10T10:16:13+08:00">2023-04-10</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="C-异常处理"><a href="#C-异常处理" class="headerlink" title="C++异常处理"></a>C++异常处理</h1><h2 id="基本结构"><a href="#基本结构" class="headerlink" title="基本结构"></a>基本结构</h2><p>在我们的程序中，经常会遇到我们需要保证某一处的正确性的时候，如果成功则继续向后执行，如果没有则抛出异常，终止程序。</p>
<p>如果我们用if else来解决，当然没有什么问题，不过C++把这一类情况统一起来，可以更加方便的进行控制。</p>
<figure class="highlight c++"><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></pre></td><td class="code"><pre><span class="line"><span class="keyword">try</span> {</span><br><span class="line"> 语句组</span><br><span class="line"> <span class="keyword">if</span>(*) <span class="keyword">throw</span> *;</span><br><span class="line">}</span><br><span class="line"><span class="built_in">catch</span>(异常类型) {</span><br><span class="line"> 异常处理代码</span><br><span class="line">}</span><br><span class="line">...</span><br><span class="line"><span class="built_in">catch</span>(异常类型) {</span><br><span class="line"> 异常处理代码</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>这是异常处理的基本结构</p>
<p>try中放置的是需要执行的语句，if语句判断为真，则抛出异常</p>
<p>然后从上往下依次看能不能匹配catch中的异常类型，如果不能匹配则继续向下，如果可以匹配，则执行相应的异常处理代码，然后跳到所有的catch后，继续执行代码。</p>
<p><strong>要注意的是</strong>：如果当前函数不处理异常（即没有写catch语句），则会到上一层函数进行捕获异常。</p>
<p>如果我们想主动传递给上一层函数，我们可以用</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="built_in">catch</span>(){</span><br><span class="line"> 异常处理代码</span><br><span class="line"> <span class="keyword">throw</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>throw后什么都不写：<strong>返回上一个异常给上一层</strong></p>
<h2 id="catch捕获列表"><a href="#catch捕获列表" class="headerlink" title="catch捕获列表"></a>catch捕获列表</h2><p>在catch()的括号里可以放的有，C++基本类型、自定义的结构和类等。</p>
<p>如果我们写为这种形式</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">catch(...){</span><br><span class="line"> 异常处理代码</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>则表明捕获所有类型的异常</p>
<h2 id="函数的异常声明列表"><a href="#函数的异常声明列表" class="headerlink" title="函数的异常声明列表"></a>函数的异常声明列表</h2><figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">void func() throw (int, double, A, B, C){</span><br><span class="line"> 函数体</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>用这样的方式来声明原型和定义函数，则表明函数会抛出的异常有int, double, A, B, C五种类型</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">void func() throw (){...}</span><br></pre></td></tr></table></figure>
<p>这表明不会抛出异常</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">void func() {...}</span><br></pre></td></tr></table></figure>
<p>这表明可以抛出任何类型的异常</p>
<p>其实这种方式，在编译时不报错，编译时Dev会检查是否符合，并报错，但是VS不会，所以其实实际作用不大，更多是为了代码可读性</p>
<h2 id="参考链接"><a href="#参考链接" class="headerlink" title="参考链接"></a>参考链接</h2><p><a target="_blank" rel="noopener" href="http://c.biancheng.net/view/422.html">C++异常处理（try catch throw）完全攻略 (biancheng.net)</a></p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/1c7bb1cc/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/1c7bb1cc/" class="post-title-link" itemprop="url">Enigma加解密实现</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-03-28 22:58:53 / Modified: 23:12:59" itemprop="dateCreated datePublished" datetime="2023-03-28T22:58:53+08:00">2023-03-28</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="Enigma加解密实现"><a href="#Enigma加解密实现" class="headerlink" title="Enigma加解密实现"></a>Enigma加解密实现</h1><p>完成了密码学实验二的Enigma破解，这里对自己的思路做一些整理</p>
<h2 id="Enigma原理简介"><a href="#Enigma原理简介" class="headerlink" title="Enigma原理简介"></a>Enigma原理简介</h2><p>总的来看，Enigma有这么几个地方是存在随机性的</p>
<ol>
<li>plugboard</li>
<li>rotor</li>
<li>ring</li>
<li>key</li>
</ol>
<p>而且还有机械结构的<strong>double stepping</strong>，这个的原因是每次齿轮转动其实是靠三个柱子推动的：</p>
<ol>
<li>柱子一只推一号齿轮，保证每次都推动一个</li>
<li>柱子二推一号齿轮另一侧的卡口，保证齿轮一经历step_char时，就推动一、二号齿轮转动</li>
<li>柱子三推二号齿轮另一侧的卡口，保证齿轮二经历step_char时，就推动二、三号齿轮转动</li>
</ol>
<p>那么我们就能分析出stepping的规律</p>
<p>每次一号齿轮必转一次，如果二号齿轮在step_char，则二、三跟着转一次，如果没有，则判断一号齿轮在step_char，则只有二跟着转一次。</p>
<h2 id="源代码"><a href="#源代码" class="headerlink" title="源代码"></a>源代码</h2><figure class="highlight c"><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string"><stdlib.h></span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string"><string.h></span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string"><string></span></span></span><br><span class="line"><span class="type">char</span> rotor_table[<span class="number">5</span>][<span class="number">27</span>] = {</span><br><span class="line"> <span class="string">"EKMFLGDQVZNTOWYHXUSPAIBRCJ"</span>,</span><br><span class="line"> <span class="string">"AJDKSIRUXBLHWTMCQGZNPYFVOE"</span>,</span><br><span class="line"> <span class="string">"BDFHJLCPRTXVZNYEIWGAKMUSQO"</span>,</span><br><span class="line"> <span class="string">"ESOVPZJAYQUIRHXLNFTGKDCMWB"</span>,</span><br><span class="line"> <span class="string">"VZBRGITYUPSDNHLXAWMJQOFECK"</span></span><br><span class="line">};</span><br><span class="line"><span class="type">char</span> reflector[] = <span class="string">"YRUHQSLDPXNGOKMIEBFZCWVJAT"</span>; <span class="comment">/* ReflectorWide_B */</span></span><br><span class="line"><span class="type">char</span> step_char[<span class="number">6</span>] = <span class="string">"RFWKA"</span>; <span class="comment">/* Royal Flags Wave Kings Above */</span></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span> {</span><br><span class="line"> <span class="type">char</span> plug[<span class="number">0x20</span>] = <span class="string">"ABCDEFGHIJKLMNOPQRSTUVWXYZ"</span>;</span><br><span class="line"> <span class="comment">/* e.g. "ZBCDEFGHIJKLMNOPQRSTUVWXYA" means 'A' & 'Z' are swapped */</span></span><br><span class="line"> <span class="type">char</span> ring[<span class="number">0x20</span>] = <span class="string">"UJZ"</span>;<span class="comment">/* ring setting from left to right, e.g.</span></span><br><span class="line"><span class="comment"> "UJZ" means 'U' is the ring setting for the</span></span><br><span class="line"><span class="comment"> left most rotor, 'Z' is the ring setting for the right most rotor</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="type">char</span> key[<span class="number">0x20</span>] = <span class="string">"ABC"</span>;<span class="comment">/* message key from left to right, e.g.</span></span><br><span class="line"><span class="comment"> "CBA" means 'C' is the message key for the</span></span><br><span class="line"><span class="comment"> left most rotor, 'A' is the message key for the right most rotor</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="type">char</span> rotor[<span class="number">0x20</span>] = <span class="string">"321"</span>;<span class="comment">/* total 3 rotor numbers */</span></span><br><span class="line"> <span class="comment">/* e.g. rotor[0]=1, rotor[1]=2, rotor[2]=3 means</span></span><br><span class="line"><span class="comment"> the left most rotor number is 1, the right most rotor number is 3</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"> <span class="type">char</span> cipher[<span class="number">0x100</span>];</span><br><span class="line"> <span class="type">char</span> plain[<span class="number">0x100</span>];</span><br><span class="line"> gets_s(plain);</span><br><span class="line"> strupr(plain);</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i < <span class="built_in">strlen</span>(plain); ++i) {</span><br><span class="line"> plain[i] = plug[plain[i] - <span class="string">'A'</span>];</span><br><span class="line"> <span class="type">int</span> r1 = rotor[<span class="number">0</span>] - <span class="string">'1'</span>;</span><br><span class="line"> <span class="type">int</span> r2 = rotor[<span class="number">1</span>] - <span class="string">'1'</span>;</span><br><span class="line"> <span class="type">int</span> r3 = rotor[<span class="number">2</span>] - <span class="string">'1'</span>;</span><br><span class="line"></span><br><span class="line"> key[<span class="number">2</span>] = (key[<span class="number">2</span>] - <span class="string">'A'</span> + <span class="number">1</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> <span class="comment">//stepping</span></span><br><span class="line"> <span class="keyword">if</span> ((key[<span class="number">1</span>] - <span class="string">'A'</span> + <span class="number">1</span>) % <span class="number">26</span> + <span class="string">'A'</span> == step_char[r2]) {</span><br><span class="line"> key[<span class="number">1</span>] = (key[<span class="number">1</span>] - <span class="string">'A'</span> + <span class="number">1</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> key[<span class="number">0</span>] = (key[<span class="number">0</span>] - <span class="string">'A'</span> + <span class="number">1</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">if</span> (key[<span class="number">2</span>] == step_char[r3]) {</span><br><span class="line"> key[<span class="number">1</span>] = (key[<span class="number">1</span>] - <span class="string">'A'</span> + <span class="number">1</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="type">char</span> temp;</span><br><span class="line"> <span class="comment">//inner</span></span><br><span class="line"> <span class="type">int</span> delta2 = key[<span class="number">2</span>] - ring[<span class="number">2</span>];</span><br><span class="line"> temp = ((plain[i] - <span class="string">'A'</span>) + delta2 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> plain[i] = (rotor_table[r3][temp - <span class="string">'A'</span>] - <span class="string">'A'</span> - delta2 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> <span class="type">int</span> delta1 = key[<span class="number">1</span>] - ring[<span class="number">1</span>];</span><br><span class="line"> temp = ((plain[i] - <span class="string">'A'</span>) + delta1 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> plain[i] = (rotor_table[r2][temp - <span class="string">'A'</span>] - <span class="string">'A'</span> - delta1 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> <span class="type">int</span> delta0 = key[<span class="number">0</span>] - ring[<span class="number">0</span>];</span><br><span class="line"> temp = ((plain[i] - <span class="string">'A'</span>) + delta0 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> plain[i] = (rotor_table[r1][temp - <span class="string">'A'</span>] - <span class="string">'A'</span> - delta0 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> plain[i] = reflector[plain[i] - <span class="string">'A'</span>];</span><br><span class="line"> <span class="type">int</span> j;</span><br><span class="line"> temp = ((plain[i] - <span class="string">'A'</span>) + delta0 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> <span class="keyword">for</span> (j = <span class="number">0</span>; j < <span class="number">26</span>; ++j)</span><br><span class="line"> <span class="keyword">if</span> (rotor_table[r1][j] == temp) {</span><br><span class="line"> plain[i] = (j - delta0 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> temp = ((plain[i] - <span class="string">'A'</span>) + delta1 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> <span class="keyword">for</span> (j = <span class="number">0</span>; j < <span class="number">26</span>; ++j)</span><br><span class="line"> <span class="keyword">if</span> (rotor_table[r2][j] == temp) {</span><br><span class="line"> plain[i] = (j - delta1 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> temp = ((plain[i] - <span class="string">'A'</span>) + delta2 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> <span class="keyword">for</span> (j = <span class="number">0</span>; j < <span class="number">26</span>; ++j)</span><br><span class="line"> <span class="keyword">if</span> (rotor_table[r3][j] == temp) {</span><br><span class="line"> plain[i] = (j - delta2 + <span class="number">26</span>) % <span class="number">26</span> + <span class="string">'A'</span>;</span><br><span class="line"> <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> plain[i] = plug[plain[i] - <span class="string">'A'</span>];</span><br><span class="line"> cipher[i] = plain[i];</span><br><span class="line"> }</span><br><span class="line"> cipher[<span class="built_in">strlen</span>(plain)] = <span class="number">0</span>;</span><br><span class="line"> <span class="built_in">puts</span>(cipher);</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="结束语"><a href="#结束语" class="headerlink" title="结束语"></a>结束语</h2><p>总之还是收获了很多，十分佩服当时设计者的智慧！</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/f4275220/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/f4275220/" class="post-title-link" itemprop="url">CMake学习</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-03-18 11:05:29 / Modified: 23:20:09" itemprop="dateCreated datePublished" datetime="2023-03-18T11:05:29+08:00">2023-03-18</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="CMake学习"><a href="#CMake学习" class="headerlink" title="CMake学习"></a>CMake学习</h1><h2 id="CMake介绍"><a href="#CMake介绍" class="headerlink" title="CMake介绍"></a>CMake介绍</h2><p>我们平时使用的IDE都是集成过make的，只是不同平台、不同操作系统之间可能会存在差异，所以导致编写Makefile文件时需要遵循的规范就不同。因此，我们如果有一个工具能帮助我们自动生成符合条件的Makefile文件，这就会很方便。</p>
<p>因此CMake应运而生，它是一款可以自动生成Makefile的工具，可以便于我们开发。</p>
<h2 id="一个简单的例子"><a href="#一个简单的例子" class="headerlink" title="一个简单的例子"></a>一个简单的例子</h2><h3 id="1-安装配置Cmake和make"><a href="#1-安装配置Cmake和make" class="headerlink" title="1.安装配置Cmake和make"></a>1.安装配置Cmake和make</h3><p>在VScode内安装插件：“CMake” “CMake Tools” “Make” “Makefile Tools” 这四款插件</p>
<p>然后去安装mingw，可以参考下面这篇，配置好环境</p>
<p> <a target="_blank" rel="noopener" href="https://blog.csdn.net/qq_43460743/article/details/129203048"> MinGW Make CMake安装使用 —Windows 11系统_难拳的博客-CSDN博客</a></p>
<h3 id="2-创建main-c和CMakeLists-txt"><a href="#2-创建main-c和CMakeLists-txt" class="headerlink" title="2.创建main.c和CMakeLists.txt"></a>2.创建main.c和CMakeLists.txt</h3><p>首先创建一个空文件夹，然后创建</p>
<p>main.c内容如下</p>
<figure class="highlight c"><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><stdio.h></span></span></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span>{</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"hello"</span>);</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>CMakeLists.txt</p>
<figure class="highlight cmake"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">#CMakeLists.txt</span></span><br><span class="line"><span class="keyword">project</span>(HELLO)</span><br><span class="line"><span class="keyword">add_executable</span>(hello ./main.c)</span><br></pre></td></tr></table></figure>
<p>然后运行，在vscode下，ctrl + shift + · 启动一个终端</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line">mkdir build</span><br><span class="line">cd build</span><br><span class="line">cmake ../ -G "Unix Makefiles"</span><br></pre></td></tr></table></figure>
<p>然后我们发现在文件夹内多出了一个Makefile文件</p>
<p>然后我们直接输入以下make命令</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">make</span><br></pre></td></tr></table></figure>
<p>就会发现生成了hello.exe可执行文件</p>
<p>最后运行，发现输出成功</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">./hello</span><br></pre></td></tr></table></figure>
<p><img src="../imgs/20230318-1.png" alt="res"></p>
<h2 id="CMake语法简单介绍"><a href="#CMake语法简单介绍" class="headerlink" title="CMake语法简单介绍"></a>CMake语法简单介绍</h2><h3 id="刚刚例子的解释"><a href="#刚刚例子的解释" class="headerlink" title="刚刚例子的解释"></a>刚刚例子的解释</h3><p>在我们刚刚那个例子中</p>
<blockquote>
<h1 id="……-CMake语法的单行注释，如果要多行，可以写成以下这种"><a href="#……-CMake语法的单行注释，如果要多行，可以写成以下这种" class="headerlink" title="…… // CMake语法的单行注释，如果要多行，可以写成以下这种"></a>…… // CMake语法的单行注释，如果要多行，可以写成以下这种</h1><h1 id="…"><a href="#…" class="headerlink" title="[[…."></a>[[….</h1><p>…..</p>
<p>…..]] //多行注释的写法</p>
<p>project(“name”) // name为工程名，这一行可有可无，不影响最终结果，但是建议写一个，养成好习惯</p>
<p>add_executable(“exe_filename” “sourceFile”) //生成可执行文件，包含源文件</p>
</blockquote>
<p>再比如我们写另一个多文件的，比如main.c hello.c hello.h</p>
<p>然后我们的CMakeLists编写如下</p>
<blockquote>
<p>project(HELLO)</p>
<p>set(SRC_LIST main.c hello.c) //创建一个源文件集合变量/列表</p>
<p>add_executable(hello ${SRC_LIST})</p>
<p>// 如果我们想打印变量, 可以写成下面这个</p>
<p>message(“var = ${var}”)</p>
</blockquote>
<h3 id="一些可能用到的常量"><a href="#一些可能用到的常量" class="headerlink" title="一些可能用到的常量"></a>一些可能用到的常量</h3><blockquote>
<p>CMAKE_MAJOR_VERSION：cmake 主版本号<br>CMAKE_MINOR_VERSION：cmake 次版本号<br>CMAKE_C_FLAGS：设置 C 编译选项<br>CMAKE_CXX_FLAGS：设置 C++ 编译选项<br>PROJECT_SOURCE_DIR：工程的根目录<br>PROJECT_BINARY_DIR：运行 cmake 命令的目录<br>CMAKE_CURRENT_SOURCE_DIR：当前CMakeLists.txt 所在路径<br>CMAKE_CURRENT_BINARY_DIR：目标文件编译目录<br>EXECUTABLE_OUTPUT_PATH：重新定义目标二进制可执行文件的存放位置<br>LIBRARY_OUTPUT_PATH：重新定义目标链接库文件的存放位置<br>UNIX：如果为真，表示为UNIX-like的系统，包括AppleOSX和CygWin<br>WIN32：如果为真，表示为 Windows 系统，包括 CygWin<br>APPLE：如果为真，表示为 Apple 系统<br>CMAKE_SIZEOF_VOID_P：表示void*的大小（例如为4或者8），可以使用其来判断当前构建为32位还是64位<br>CMAKE_CURRENT_LIST_DIR：表示正在处理的CMakeLists.txt文件所在目录的绝对路径<br>CMAKE_ARCHIVE_OUTPUT_DIRECTORY：用于设置ARCHIVE目标的输出路径<br>CMAKE_LIBRARY_OUTPUT_DIRECTORY：用于设置LIBRARY目标的输出路径<br>CMAKE_RUNTIME_OUTPUT_DIRECTORY：用于设置RUNTIME目标的输出路径</p>
</blockquote>
<h3 id="一些其它常用命令"><a href="#一些其它常用命令" class="headerlink" title="一些其它常用命令"></a>一些其它常用命令</h3><blockquote>
<p>cmake_minimum_requried(VERSION 2.8.3) //设置cmake版本</p>
<p>aux_source_directory(${CMAKE_CURRENT_SOURCE_DIR}/src DIR_SRCS)</p>
<p>unset(var_name) //移除变量</p>
<p>add_library(Lib $(DIR_SRCS)) // 创建库文件，通常用于子目录，方便主文件引用</p>
<p>include_directories(dir) //包含目录</p>
<p>add_subdirectory(dir subdir) //指定需要进行构建的子目录 ，并且子目录中编译输出在<br> subdir，如果不设置，默认会建一个build目录作为输出<br> 当执行到add_subdirectory(xx)命令的时候会进入(xx)子<br> 目录并执行其中的CMakeLists.txt文件</p>
<p>target_link_libraries(Main Lib) // 链接可执行文件所需库文件</p>
</blockquote>
<p>参考文章：</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/geyichongchujianghu/article/details/124781090">CMake语法详解_shawn·xiao的博客-CSDN博客</a></p>
<p>【参考文章里提到的例子】</p>
<p>链接：<a target="_blank" rel="noopener" href="https://pan.baidu.com/s/1NcyiZBOWTDVy9bHv8jkQXQ">https://pan.baidu.com/s/1NcyiZBOWTDVy9bHv8jkQXQ</a><br>提取码：n0u2 </p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/fae83b3/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/fae83b3/" class="post-title-link" itemprop="url">ssh配置公钥私钥</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-03-16 09:39:56 / Modified: 09:52:36" itemprop="dateCreated datePublished" datetime="2023-03-16T09:39:56+08:00">2023-03-16</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>今天心血来潮，于是就想搞一台linux服务器玩玩<br>在阿里云的白嫖一波后，我拥有了第一台自己的服务器</p>
<p><img src="..\imgs\20230316-1.png" alt="image-20230316094701836"></p>
<p>然后就结合下面两个教程，方便地实现了远端登录linux</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/qq_63844103/article/details/127394389">【安全知识】——SSH的两种远程登录方法详解<em>ssh登录</em>白昼安全的博客-CSDN博客</a></p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_42907822/article/details/125237307">【设置ssh免密不起作用？彻底搞懂密钥】vscode在remote SSH免密远程登录<em>authorized_keys不存在</em>几叶知期的博客-CSDN博客</a></p>
<p>然后就可以方便地使用Linux啦！</p>
<p>阿里云的学生服务器可以白嫖七个月！</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/1b171b8e/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/1b171b8e/" class="post-title-link" itemprop="url">仿射密码破解</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-03-15 22:26:41" itemprop="dateCreated datePublished" datetime="2023-03-15T22:26:41+08:00">2023-03-15</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">Edited on</span>
<time title="Modified: 2023-11-06 16:58:26" itemprop="dateModified" datetime="2023-11-06T16:58:26+08:00">2023-11-06</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h3 id="题目介绍"><a href="#题目介绍" class="headerlink" title="题目介绍"></a>题目介绍</h3><blockquote>
<ol>
<li>本题是多文件题，先由judge程序生成输出，再把该输出作为用户程序的输入，用户程序根据输入进行计算产生输出，最后judge程序判断用户程序输出是否正确。</li>
<li>judge程序的工作流程如下:<br>❶ judge程序随机生成一对密钥<em>a</em>、<em>b</em>用于以下仿射密码加密算法:<br><em>y</em>=<em>a</em>∗<em>x</em>+<em>b</em> <em>mod</em> 26; 其中<em>x</em>为明文, <em>y</em>为密文。<br>该仿射加密算法中的密钥<em>a</em>、<em>b</em>均为正整数, <em>a</em>∈[2,25]，<em>b</em>∈[1,25], 并且<em>a</em>满足条件<em>g<strong>c</strong>d</em>(<em>a</em>,26)==1;<br>❷ judge程序随机生成一对整数<em>i</em>、<em>j</em>∈[0,25]，再按以下代码生成一个字符数组<em>s</em>:</li>
</ol>
<figure class="highlight plaintext"><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></pre></td><td class="code"><pre><span class="line">s[0] = i+'A';</span><br><span class="line">s[1] = (a * i + b) % 26 + 'A';</span><br><span class="line">s[2] = j+'A';</span><br><span class="line">s[3] = (a * j + b) % 26 + 'A';</span><br><span class="line">s[4] = '\0';</span><br></pre></td></tr></table></figure>
<p> 其中<em>s</em>包含的前4个元素满足以下条件:<br> <code>gcd((s[1]-s[3]+26) % 26, 26)==1 || gcd((s[0]-s[2]+26) % 26, 26)==1</code><br> ❸ judge程序用仿射密码加密算法对一个长度不超过100字节且内容全为大字字母的字符数组设为<em>p</em>进行加密生成另一个字符数组 设为<em>c</em>，<em>c</em>[<em>i</em>]的计算过程如下:</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">c[i] = ((p[i]-'A') * a + b) % 26 + 'A';</span><br></pre></td></tr></table></figure>
<p> ❹ judge程序用<em>p<strong>u</strong>t**s</em>()分别输出<em>s</em>和<em>c</em>作为用户程序的输入</p>
<ol>
<li>用户程序的工作流程如下:<br>① 用gets()输入一个字符串设为<em>s</em>，再用gets()输入另一个字符串设为c<br>② 用仿射密码解密算法对c中的字符进行解密生成另一个字符数组设为p<br>③ 用puts()输出p</li>
</ol>
<p>测试数据</p>
<p>输入:</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">ZWYB</span><br><span class="line">RKXBZVNZDENAZFHRKMZKZVNISRDK</span><br></pre></td></tr></table></figure>
<p>输出:</p>
<figure class="highlight plaintext"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">AREYOUGOINGTOSCARBOROUGHFAIR</span><br></pre></td></tr></table></figure>
</blockquote>
<h3 id="实现方法"><a href="#实现方法" class="headerlink" title="实现方法"></a>实现方法</h3><p><strong>方法一：枚举每种情况即可，没有什么特别的</strong></p>
<p>核心代码</p>
<figure class="highlight c"><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></pre></td><td class="code"><pre><span class="line"> <span class="type">int</span> s_num[<span class="number">4</span>];</span><br><span class="line"> <span class="type">char</span> s[<span class="number">5</span>], c[<span class="number">100</span>];</span><br><span class="line"> gets(s);</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i < <span class="built_in">strlen</span>(s); ++ i)</span><br><span class="line"> s_num[i] = s[i] - <span class="string">'A'</span>;</span><br><span class="line"> gets(c);</span><br><span class="line"> <span class="type">int</span> a, b, temp;</span><br><span class="line"> <span class="keyword">for</span>(a = <span class="number">2</span>; a <= <span class="number">25</span>; ++ a)</span><br><span class="line"> <span class="keyword">for</span>(b = <span class="number">1</span>; b <= <span class="number">25</span>; ++ b){</span><br><span class="line"> <span class="keyword">if</span>(xgcd(a,<span class="number">26</span>,&temp)==<span class="number">1</span> && ((s_num[<span class="number">1</span>]-b+<span class="number">26</span>)*temp)%<span class="number">26</span> == s_num[<span class="number">0</span>] && ((s_num[<span class="number">3</span>]-b+<span class="number">26</span>)*temp)%<span class="number">26</span> == s_num[<span class="number">2</span>]){</span><br><span class="line"> <span class="keyword">goto</span> done;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">done:</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i < <span class="built_in">strlen</span>(c); ++ i){</span><br><span class="line"> c[i]=((c[i]-<span class="string">'A'</span> - b + <span class="number">26</span>)*temp)%<span class="number">26</span>+<span class="string">'A'</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">puts</span>(c);</span><br></pre></td></tr></table></figure>
<p><strong>方法二：利用s的四个元素满足的条件</strong></p>
<p>我们根据条件和原来的式子进行推理</p>
<p>s[1] = (s[0]*a+b)%26</p>
<p>s[3] = (s[2]*a+b)%26</p>
<p>做差后我们发现变成了</p>
<p>s[1]-s[3]=( (s[0]-s[2])*a )%26</p>
<p>所以s[0]-s[2]与s[1]-s[3]必定是同时与26互质的</p>
<p>因此我们直接解出其中一个的逆元，然后就可以得到a，进而求出b，就避免了暴力枚举，十分优雅</p>
<p>核心代码</p>
<figure class="highlight c"><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></pre></td><td class="code"><pre><span class="line"> <span class="type">int</span> s_num[<span class="number">4</span>];</span><br><span class="line"> <span class="type">char</span> s[<span class="number">5</span>], c[<span class="number">100</span>];</span><br><span class="line"> gets(s);</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i < <span class="built_in">strlen</span>(s); ++ i)</span><br><span class="line"> s_num[i] = s[i] - <span class="string">'A'</span>;</span><br><span class="line"> gets(c);</span><br><span class="line"> <span class="type">int</span> a, b, temp;</span><br><span class="line"> xgcd((s_num[<span class="number">0</span>]-s_num[<span class="number">2</span>]+<span class="number">26</span>)%<span class="number">26</span>, <span class="number">26</span>, &temp);</span><br><span class="line"> a = ((s_num[<span class="number">1</span>]-s_num[<span class="number">3</span>]+<span class="number">26</span>)*temp)%<span class="number">26</span>;</span><br><span class="line"> b = (s_num[<span class="number">1</span>]-a*(s_num[<span class="number">0</span>])+<span class="number">26</span>)%<span class="number">26</span>;</span><br><span class="line"> xgcd(a, <span class="number">26</span>, &temp);</span><br><span class="line">done:</span><br><span class="line"> <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i < <span class="built_in">strlen</span>(c); ++ i){</span><br><span class="line"> c[i]=((c[i]-<span class="string">'A'</span> - b + <span class="number">26</span>)*temp)%<span class="number">26</span>+<span class="string">'A'</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">puts</span>(c);</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/4c6cc743/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/4c6cc743/" class="post-title-link" itemprop="url">红黑树、B树和B+树总结（附B+树实现）</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-03-15 20:19:29" itemprop="dateCreated datePublished" datetime="2023-03-15T20:19:29+08:00">2023-03-15</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">Edited on</span>
<time title="Modified: 2023-03-16 09:45:13" itemprop="dateModified" datetime="2023-03-16T09:45:13+08:00">2023-03-16</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>最近学习了红黑树、B树和B+树的一些知识，这里做一个简单的小结吧。<br>这两种数据结构都是用来改进二叉搜索的，比起原有的BST和splay Tree，虽然设计复杂了些，但是在增删改查的综合表现上有显著的提升，但是代价是理解和实现会比较困难。</p>
<p>关于红黑树，可以参考这两篇文章</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_44153921/article/details/123152622"> 红黑树的删除操作详解<em>红黑树删除</em>二月风格的博客-CSDN博客</a></p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/zzy893037505/article/details/115177354">死磕红黑树——聊聊红黑树的删除<em>红黑树删除</em>极客子羽的博客-CSDN博客</a></p>
<p>关于B树和B+树，可以参考这篇文章（甚至还有动图解释，简直不要太清楚）</p>
<p><a target="_blank" rel="noopener" href="https://blog.csdn.net/qq_33905217/article/details/121827393">B树和B+树详解_小肖同学哦的博客-CSDN博客</a></p>
<p>最后附上自己做的一道B+树练手题目：<a target="_blank" rel="noopener" href="https://pintia.cn/problem-sets/16/exam/problems/691">题目详情 - 7-29 Self-printable B+ Tree (pintia.cn)</a></p>
<p>实现源码</p>
<figure class="highlight c++"><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><span class="line">131</span><br><span class="line">132</span><br><span class="line">133</span><br><span class="line">134</span><br><span class="line">135</span><br><span class="line">136</span><br><span class="line">137</span><br><span class="line">138</span><br><span class="line">139</span><br><span class="line">140</span><br><span class="line">141</span><br><span class="line">142</span><br><span class="line">143</span><br><span class="line">144</span><br><span class="line">145</span><br><span class="line">146</span><br><span class="line">147</span><br><span class="line">148</span><br><span class="line">149</span><br><span class="line">150</span><br><span class="line">151</span><br><span class="line">152</span><br><span class="line">153</span><br><span class="line">154</span><br><span class="line">155</span><br><span class="line">156</span><br><span class="line">157</span><br><span class="line">158</span><br><span class="line">159</span><br><span class="line">160</span><br><span class="line">161</span><br><span class="line">162</span><br><span class="line">163</span><br><span class="line">164</span><br><span class="line">165</span><br><span class="line">166</span><br><span class="line">167</span><br><span class="line">168</span><br><span class="line">169</span><br><span class="line">170</span><br><span class="line">171</span><br><span class="line">172</span><br><span class="line">173</span><br><span class="line">174</span><br><span class="line">175</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><stdio.h></span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><stdlib.h></span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><queue></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">struct</span> <span class="title class_">BPlusNode</span>* BPlusTree;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">BPlusMediaNode</span> {</span><br><span class="line"> <span class="type">int</span> key;<span class="comment">//save data</span></span><br><span class="line"> BPlusTree left, right;<span class="comment">//save left and right pointer</span></span><br><span class="line">};</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">BPlusNode</span> {</span><br><span class="line"> <span class="type">int</span> flag = <span class="number">0</span>;<span class="comment">//flag = 0 -> leaf node || flag = 1 -> inner node</span></span><br><span class="line"> <span class="type">int</span> Num = <span class="number">0</span>;<span class="comment">//the number of nodes</span></span><br><span class="line"> BPlusMediaNode* media[<span class="number">4</span>];<span class="comment">//save index or leaf data</span></span><br><span class="line"> BPlusTree ParTree;<span class="comment">//save parent pointer</span></span><br><span class="line">};</span><br><span class="line">queue< pair<BPlusTree, <span class="type">int</span>> >pri;</span><br><span class="line">BPlusTree bpTree;</span><br><span class="line"><span class="function">BPlusTree <span class="title">GetRoot</span><span class="params">(BPlusTree tree)</span> </span>{</span><br><span class="line"> <span class="keyword">while</span> (tree->ParTree != <span class="literal">NULL</span>)</span><br><span class="line"> tree = tree->ParTree;</span><br><span class="line"> <span class="keyword">return</span> tree;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">UpdateBPlusTree</span><span class="params">(BPlusTree tree)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (tree->ParTree == <span class="literal">NULL</span>) {</span><br><span class="line"> BPlusTree par = (BPlusTree)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(BPlusNode));</span><br><span class="line"> BPlusTree sib = (BPlusTree)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(BPlusNode));</span><br><span class="line"> par->flag = <span class="number">1</span>;</span><br><span class="line"> par->media[<span class="number">0</span>] = (BPlusMediaNode*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(BPlusMediaNode));</span><br><span class="line"> par->media[<span class="number">0</span>]->key = tree->media[tree->Num/<span class="number">2</span>]->key;</span><br><span class="line"> par->Num = <span class="number">1</span>;</span><br><span class="line"> par->ParTree = <span class="literal">NULL</span>;</span><br><span class="line"> par->media[<span class="number">0</span>]->left = tree;</span><br><span class="line"> par->media[<span class="number">0</span>]->right = sib;</span><br><span class="line"> sib->media[<span class="number">0</span>] = tree->media[tree->Num/<span class="number">2</span>];</span><br><span class="line"> sib->media[<span class="number">1</span>] = tree->media[tree->Num/<span class="number">2</span>+<span class="number">1</span>];</span><br><span class="line"> sib->ParTree = par;</span><br><span class="line"> tree->ParTree = par;</span><br><span class="line"> sib->Num = <span class="number">2</span>;</span><br><span class="line"> <span class="keyword">if</span> (tree->flag) {</span><br><span class="line"> sib->flag = <span class="number">1</span>;</span><br><span class="line"> sib->Num = <span class="number">1</span>;</span><br><span class="line"> sib->media[<span class="number">0</span>] = sib->media[<span class="number">1</span>];</span><br><span class="line"> sib->media[<span class="number">0</span>]->left->ParTree = sib;</span><br><span class="line"> sib->media[<span class="number">0</span>]->right->ParTree = sib;</span><br><span class="line"> tree->Num = <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> sib->flag = <span class="number">0</span>;</span><br><span class="line"> tree->Num = <span class="number">2</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> BPlusTree par = tree->ParTree;</span><br><span class="line"> BPlusTree sib = (BPlusTree)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(BPlusNode));</span><br><span class="line"> <span class="type">int</span> t = tree->media[tree->Num / <span class="number">2</span>]->key;</span><br><span class="line"> sib->media[<span class="number">0</span>] = tree->media[tree->Num / <span class="number">2</span>];</span><br><span class="line"> sib->media[<span class="number">1</span>] = tree->media[tree->Num / <span class="number">2</span> + <span class="number">1</span>];</span><br><span class="line"> sib->ParTree = par;</span><br><span class="line"> sib->Num = <span class="number">2</span>;</span><br><span class="line"> <span class="keyword">if</span> (tree->flag) {</span><br><span class="line"> tree->Num = <span class="number">1</span>;</span><br><span class="line"> sib->flag = <span class="number">1</span>;</span><br><span class="line"> sib->Num = <span class="number">1</span>;</span><br><span class="line"> sib->media[<span class="number">0</span>] = sib->media[<span class="number">1</span>];</span><br><span class="line"> sib->media[<span class="number">0</span>]->left->ParTree = sib;</span><br><span class="line"> sib->media[<span class="number">0</span>]->right->ParTree = sib;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> tree->Num = <span class="number">2</span>;</span><br><span class="line"> sib->flag = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="type">int</span> v = sib->media[<span class="number">0</span>]->key;</span><br><span class="line"> <span class="type">int</span> i;</span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">0</span>; i < par->Num; ++i) {</span><br><span class="line"> <span class="keyword">if</span> (par->media[i]->key > v) <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> par->Num++;</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> j = par->Num - <span class="number">1</span>; j >= i + <span class="number">1</span>; --j)</span><br><span class="line"> par->media[j] = par->media[j - <span class="number">1</span>];</span><br><span class="line"> par->media[i] = (BPlusMediaNode*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(BPlusMediaNode));</span><br><span class="line"> par->media[i]->key = t;</span><br><span class="line"> par->media[i]->left = tree;</span><br><span class="line"> par->media[i]->right = sib;</span><br><span class="line"> <span class="keyword">if</span> (i != <span class="number">0</span>) par->media[i<span class="number">-1</span>]->right = tree;</span><br><span class="line"> <span class="keyword">if</span>(i != par->Num<span class="number">-1</span>) par->media[i+<span class="number">1</span>]->left = sib;</span><br><span class="line"> <span class="keyword">if</span> (par->Num == <span class="number">3</span>) <span class="built_in">UpdateBPlusTree</span>(par);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">BPlusInsert</span><span class="params">(BPlusTree bpTree, <span class="type">int</span> value)</span> </span>{</span><br><span class="line"> <span class="type">int</span> i;</span><br><span class="line"> <span class="keyword">for</span> (i = <span class="number">0</span>; i<bpTree->Num; ++i) {</span><br><span class="line"> <span class="keyword">if</span> (bpTree->media[i]->key > value) <span class="keyword">break</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">if</span> (bpTree->media[i]->key == value) {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"Key %d is duplicated\n"</span>, value);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">// i is the index of position to insert</span></span><br><span class="line"> <span class="keyword">if</span> (bpTree->flag == <span class="number">0</span>) {</span><br><span class="line"> <span class="comment">//Directly insert it into this node</span></span><br><span class="line"> bpTree->Num++;</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> j = bpTree->Num<span class="number">-1</span>; j >= i+<span class="number">1</span>; --j)</span><br><span class="line"> bpTree->media[j] = bpTree->media[j - <span class="number">1</span>];</span><br><span class="line"> bpTree->media[i] = (BPlusMediaNode*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(BPlusMediaNode));</span><br><span class="line"> bpTree->media[i]->left = bpTree->media[i]->right = <span class="literal">NULL</span>;</span><br><span class="line"> bpTree->media[i]->key = value;</span><br><span class="line"> <span class="keyword">if</span> (bpTree->Num == <span class="number">4</span>) {</span><br><span class="line"> <span class="built_in">UpdateBPlusTree</span>(bpTree);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="comment">//insert or find it into one of subtrees of this node</span></span><br><span class="line"> <span class="keyword">if</span> (i < bpTree->Num) <span class="comment">//left Tree to insert</span></span><br><span class="line"> <span class="built_in">BPlusInsert</span>(bpTree->media[i]->left, value);</span><br><span class="line"> <span class="keyword">else</span> <span class="comment">//Right Tree to insert{</span></span><br><span class="line"> <span class="keyword">if</span> (bpTree->media[i - <span class="number">1</span>]->right == <span class="literal">NULL</span>) {</span><br><span class="line"> bpTree->media[i - <span class="number">1</span>]->right = (BPlusTree)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(BPlusNode));</span><br><span class="line"> BPlusTree r = bpTree->media[i - <span class="number">1</span>]->right;</span><br><span class="line"> r->flag = <span class="number">0</span>;</span><br><span class="line"> r->media[<span class="number">0</span>] = (BPlusMediaNode*)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(BPlusMediaNode));</span><br><span class="line"> r->media[<span class="number">0</span>]->left = r->media[<span class="number">0</span>]->right = <span class="literal">NULL</span>;</span><br><span class="line"> r->media[<span class="number">0</span>]->key = value;</span><br><span class="line"> r->Num = <span class="number">1</span>;</span><br><span class="line"> r->ParTree = bpTree;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span></span><br><span class="line"> <span class="built_in">BPlusInsert</span>(bpTree->media[i - <span class="number">1</span>]->right, value);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">PrintBPlusNode</span><span class="params">(BPlusTree node)</span> </span>{</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"[%d"</span>, node->media[<span class="number">0</span>]->key);</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i < node->Num; ++i)</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">",%d"</span>, node->media[i]->key);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"]"</span>);</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">PrintBPlusTree</span><span class="params">()</span> </span>{</span><br><span class="line"> pri.<span class="built_in">push</span>(<span class="built_in">make_pair</span>(bpTree, <span class="number">1</span>));</span><br><span class="line"> <span class="type">int</span> last_level = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">while</span> (!pri.<span class="built_in">empty</span>()) {</span><br><span class="line"> BPlusTree node = pri.<span class="built_in">front</span>().first;</span><br><span class="line"> <span class="type">int</span> level = pri.<span class="built_in">front</span>().second;</span><br><span class="line"> pri.<span class="built_in">pop</span>();</span><br><span class="line"> <span class="keyword">if</span> (node == <span class="literal">NULL</span> || node->flag == <span class="number">-1</span>) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="keyword">if</span> (level - last_level) {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"\n"</span>);</span><br><span class="line"> last_level = level;</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">PrintBPlusNode</span>(node);</span><br><span class="line"> <span class="keyword">if</span> (node->flag) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i < node->Num; ++i)</span><br><span class="line"> pri.<span class="built_in">push</span>(<span class="built_in">make_pair</span>(node->media[i]->left, level+<span class="number">1</span>));</span><br><span class="line"> pri.<span class="built_in">push</span>(<span class="built_in">make_pair</span>(node->media[node->Num<span class="number">-1</span>]->right, level + <span class="number">1</span>));</span><br><span class="line"> }</span><br><span class="line"> node->flag = <span class="number">-1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="type">int</span> n, x;</span><br><span class="line"> <span class="built_in">scanf_s</span>(<span class="string">"%d"</span>, &n);</span><br><span class="line"> bpTree = (BPlusTree)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(BPlusNode));</span><br><span class="line"> bpTree->flag = <span class="number">0</span>;</span><br><span class="line"> bpTree->Num = <span class="number">0</span>;</span><br><span class="line"> bpTree->ParTree = <span class="literal">NULL</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i <= n; ++i) {</span><br><span class="line"> <span class="built_in">scanf_s</span>(<span class="string">"%d"</span>, &x);</span><br><span class="line"> <span class="built_in">BPlusInsert</span>(bpTree, x);</span><br><span class="line"> bpTree = <span class="built_in">GetRoot</span>(bpTree);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">PrintBPlusTree</span>();</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/dafcd8ee/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/dafcd8ee/" class="post-title-link" itemprop="url">扩展欧几里得算法的证明与实现</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2023-03-02 21:47:00 / Modified: 22:01:56" itemprop="dateCreated datePublished" datetime="2023-03-02T21:47:00+08:00">2023-03-02</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>今天有时间，就想起来把密码学课上提到的扩展欧几里得算法再好好思考一下</p>
<h1 id="扩展欧几里得算法"><a href="#扩展欧几里得算法" class="headerlink" title="扩展欧几里得算法"></a>扩展欧几里得算法</h1><h2 id="含义"><a href="#含义" class="headerlink" title="含义"></a>含义</h2><p><strong>扩展欧几里得算法</strong>是<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/欧几里得算法/1647675?fromModule=lemma_inlink">欧几里得算法</a>（又叫辗转相除法）的扩展。除了计算a、b两个整数的<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/最大公约数/869308?fromModule=lemma_inlink">最大公约数</a>，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/最大公因子/6760265?fromModule=lemma_inlink">最大公因子</a>时, 我们都会提到一个非常基本的事实: <strong>给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = gcd(a,b)</strong>。有两个数a,b，对它们进行<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/辗转相除法/4625352?fromModule=lemma_inlink">辗转相除法</a>，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。</p>
<p>【来源：<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/%E6%89%A9%E5%B1%95%E6%AC%A7%E5%87%A0%E9%87%8C%E5%BE%97%E7%AE%97%E6%B3%95/2029414">百度百科</a>】</p>
<h2 id="证明"><a href="#证明" class="headerlink" title="证明"></a>证明</h2><p>这里提一嘴<strong>裴蜀定理</strong></p>
<p>它得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/最大公约数/869308?fromModule=lemma_inlink">最大公约数</a>d，关于未知数x和y的线性<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/不定方程/6815217?fromModule=lemma_inlink">不定方程</a>（称为裴蜀等式）：若a,b是整数,且<a target="_blank" rel="noopener" href="https://baike.baidu.com/item/gcd/24166657?fromModule=lemma_inlink">gcd</a>(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。</p>
<p>上面也就间接地证明了扩展欧几里得算法的正确性，我们要做的就是如何去找到对应的x和y</p>
<h2 id="代码实现"><a href="#代码实现" class="headerlink" title="代码实现"></a>代码实现</h2><p>首先我们要有方法论的指导</p>
<p><img src="..\imgs\20230302-1.png" alt="20230302-1" style="zoom: 80%;" /></p>
<p>代码实现如下</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string"><iostream></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="type">int</span> <span class="title">GetExpandGCD</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b, <span class="type">int</span>& x, <span class="type">int</span>& y)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (b == <span class="number">0</span>) {</span><br><span class="line"> x = <span class="number">1</span>, y = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">return</span> a;</span><br><span class="line"> }</span><br><span class="line"> <span class="type">int</span> r = <span class="built_in">GetExpandGCD</span>(b, a % b, x, y);</span><br><span class="line"> <span class="type">int</span> temp_x = x;</span><br><span class="line"> x = y;</span><br><span class="line"> y = temp_x - (a / b) * y;</span><br><span class="line"> <span class="keyword">return</span> r;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="type">int</span> a, b;</span><br><span class="line"> cin >> a >> b;</span><br><span class="line"> <span class="keyword">if</span> (a < b) {</span><br><span class="line"> <span class="type">int</span> temp = b;</span><br><span class="line"> b = a;</span><br><span class="line"> a = temp;</span><br><span class="line"> }</span><br><span class="line"> <span class="type">int</span> x, y;</span><br><span class="line"> <span class="type">int</span> gcd = <span class="built_in">GetExpandGCD</span>(a, b, x, y);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d*%d+%d*%d=%d"</span>, a, x, b, y, gcd);</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>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/1041600e/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/1041600e/" class="post-title-link" itemprop="url">判断最小生成树是否唯一</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2022-11-21 09:40:13" itemprop="dateCreated datePublished" datetime="2022-11-21T09:40:13+08:00">2022-11-21</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">Edited on</span>
<time title="Modified: 2023-03-18 22:11:46" itemprop="dateModified" datetime="2023-03-18T22:11:46+08:00">2023-03-18</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>今天做DS作业的时候遇到了这样一个问题，如何判断最小生成树是否唯一</p>
<p>其实正常的最小生成树的判断方法就使用并查集 + sort排序即可，不过如何判断最小生成树唯一性</p>
<p>我分析这个问题，关键就在于找到一个充分条件：</p>
<p><strong>当前这条边可以添加到集合中 + 存在边长相等的边 + 且那一条边在这条边添加前可以添加，而添加后就不可以添加了</strong></p>
<p>如果可以满足这个条件，我们就用judge标志位记下来</p>
<p>最后也可以实现（差点就去写搜索了www</p>
<figure class="highlight c++"><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></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="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="meta">#<span class="keyword">define</span> N 510</span></span><br><span class="line"><span class="type">int</span> fa[N];</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">EDGE</span> {</span><br><span class="line"> <span class="type">int</span> u, v;</span><br><span class="line"> <span class="type">int</span> w;</span><br><span class="line">}edge[N*N];</span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">cmp</span><span class="params">(<span class="type">const</span> EDGE& a, <span class="type">const</span> EDGE& b)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> a.w < b.w;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">FIND</span><span class="params">(<span class="type">int</span> x)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (fa[x] == x) <span class="keyword">return</span> x;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">return</span> fa[x] = <span class="built_in">FIND</span>(fa[x]);</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="type">int</span> n, m;</span><br><span class="line"> <span class="built_in">scanf_s</span>(<span class="string">"%d%d"</span>, &n, &m);</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i <= n; ++i)</span><br><span class="line"> fa[i] = i;</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i < m; ++i)</span><br><span class="line"> <span class="built_in">scanf_s</span>(<span class="string">"%d%d%d"</span>, &edge[i].u, &edge[i].v, &edge[i].w);</span><br><span class="line"> <span class="built_in">sort</span>(edge, edge + m, cmp);</span><br><span class="line"> <span class="type">int</span> cnt = <span class="number">0</span>, k = <span class="number">0</span>, sum = <span class="number">0</span>;</span><br><span class="line"> <span class="type">bool</span> judge = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span> (k < m) {</span><br><span class="line"> <span class="type">int</span> fax = <span class="built_in">FIND</span>(edge[k].u);</span><br><span class="line"> <span class="type">int</span> fay = <span class="built_in">FIND</span>(edge[k].v);</span><br><span class="line"> <span class="keyword">if</span> (fax != fay) {</span><br><span class="line"> <span class="type">int</span> t = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">if</span> (edge[k].w == edge[k + <span class="number">1</span>].w) {</span><br><span class="line"> <span class="type">int</span> faxx = <span class="built_in">FIND</span>(edge[k+<span class="number">1</span>].u);</span><br><span class="line"> <span class="type">int</span> fayy = <span class="built_in">FIND</span>(edge[k+<span class="number">1</span>].v);</span><br><span class="line"> <span class="keyword">if</span> (faxx != fayy) t++;<span class="comment">//还可以合并</span></span><br><span class="line"> }</span><br><span class="line"> fa[fax] = fay;</span><br><span class="line"> sum += edge[k].w;</span><br><span class="line"> cnt++;</span><br><span class="line"> <span class="keyword">if</span> (edge[k].w == edge[k + <span class="number">1</span>].w) {</span><br><span class="line"> <span class="type">int</span> faxx = <span class="built_in">FIND</span>(edge[k + <span class="number">1</span>].u);</span><br><span class="line"> <span class="type">int</span> fayy = <span class="built_in">FIND</span>(edge[k + <span class="number">1</span>].v);</span><br><span class="line"> <span class="keyword">if</span> (faxx == fayy) t++;<span class="comment">//变得不能合并</span></span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (t == <span class="number">2</span>) judge = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">if</span> (cnt == n - <span class="number">1</span>) <span class="keyword">break</span>;</span><br><span class="line"> }</span><br><span class="line"> k++;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (cnt == n - <span class="number">1</span>) {</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, sum);</span><br><span class="line"> <span class="keyword">if</span> (!judge) <span class="built_in">printf</span>(<span class="string">"Yes"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"No"</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> cnt = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i <= n; ++i)</span><br><span class="line"> <span class="keyword">if</span> (fa[i] == i) cnt++;</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"No MST\n%d"</span>, cnt);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<article itemscope itemtype="http://schema.org/Article" class="post-block" lang="en">
<link itemprop="mainEntityOfPage" href="https://crer-lu.github.io/posts/849f6e42/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/mouse.jpg">
<meta itemprop="name" content="Fengjie Lu">
<meta itemprop="description" content="">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Blog by Crer_lu">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/posts/849f6e42/" class="post-title-link" itemprop="url">汇编语言结尾为什么是end main</a>
</h2>
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">Posted on</span>
<time title="Created: 2022-11-09 20:30:58 / Modified: 20:56:25" itemprop="dateCreated datePublished" datetime="2022-11-09T20:30:58+08:00">2022-11-09</time>
</span>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>今天学习汇编的时候发现了一个小细节<br>
<!--noindex-->
<div class="post-button">
<a class="btn" href="/posts/849f6e42/#more" rel="contents">
Read more »
</a>
</div>
<!--/noindex-->
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
<nav class="pagination">
<span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><span class="space">…</span><a class="page-number" href="/page/6/">6</a><a class="extend next" rel="next" href="/page/2/"><i class="fa fa-angle-right" aria-label="Next page"></i></a>
</nav>
</div>
<script>
window.addEventListener('tabs:register', () => {
let { activeClass } = CONFIG.comments;
if (CONFIG.comments.storage) {
activeClass = localStorage.getItem('comments_active') || activeClass;