-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathindex.html
More file actions
1723 lines (1379 loc) · 165 KB
/
index.html
File metadata and controls
1723 lines (1379 loc) · 165 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<!DOCTYPE html>
<html lang="zh-CN">
<head>
<meta charset="UTF-8">
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=2">
<meta name="theme-color" content="#222">
<meta name="generator" content="Hexo 5.3.0">
<link rel="apple-touch-icon" sizes="180x180" href="/images/Raining64.png">
<link rel="icon" type="image/png" sizes="32x32" href="/images/Raining32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/images/Raining16.png">
<link rel="mask-icon" href="/images/Raining64.png" color="#222">
<link rel="stylesheet" href="/css/main.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free@5.15.2/css/all.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css">
<script class="hexo-configurations">
var NexT = window.NexT || {};
var CONFIG = {"hostname":"conver334.github.io","root":"/","images":"/images","scheme":"Muse","version":"8.2.1","exturl":false,"sidebar":{"position":"left","display":"post","padding":18,"offset":12},"copycode":false,"bookmark":{"enable":false,"color":"#222","save":"auto"},"fancybox":false,"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"motion":{"enable":true,"async":false,"transition":{"post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":"ture","trigger":"auto","top_n_per_article":1,"unescape":false,"preload":false}};
</script>
<meta name="description" content="又叒开小号了 ^ _ ^">
<meta property="og:type" content="website">
<meta property="og:title" content="Conver">
<meta property="og:url" content="https://conver334.github.io/index.html">
<meta property="og:site_name" content="Conver">
<meta property="og:description" content="又叒开小号了 ^ _ ^">
<meta property="og:locale" content="zh_CN">
<meta property="article:author" content="Conver">
<meta name="twitter:card" content="summary">
<link rel="canonical" href="https://conver334.github.io/">
<script class="page-configurations">
// https://hexo.io/docs/variables.html
CONFIG.page = {
sidebar: "",
isHome : true,
isPost : false,
lang : 'zh-CN'
};
</script>
<title>Conver</title>
<noscript>
<style>
body { margin-top: 2rem; }
.use-motion .menu-item,
.use-motion .sidebar,
.use-motion .post-block,
.use-motion .pagination,
.use-motion .comments,
.use-motion .post-header,
.use-motion .post-body,
.use-motion .collection-header {
visibility: visible;
}
.use-motion .header,
.use-motion .site-brand-container .toggle,
.use-motion .footer { opacity: initial; }
.use-motion .site-title,
.use-motion .site-subtitle,
.use-motion .custom-logo-image {
opacity: initial;
top: initial;
}
.use-motion .logo-line {
transform: scaleX(1);
}
.search-pop-overlay, .sidebar-nav { display: none; }
.sidebar-panel { display: block; }
</style>
</noscript>
<!-- hexo injector head_end start -->
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/katex@0.12.0/dist/katex.min.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/hexo-math@4.0.0/dist/style.css">
<!-- hexo injector head_end end -->
<style>.github-emoji { position: relative; display: inline-block; width: 1.2em; min-height: 1.2em; overflow: hidden; vertical-align: top; color: transparent; } .github-emoji > span { position: relative; z-index: 10; } .github-emoji img, .github-emoji .fancybox { margin: 0 !important; padding: 0 !important; border: none !important; outline: none !important; text-decoration: none !important; user-select: none !important; cursor: auto !important; } .github-emoji img { height: 1.2em !important; width: 1.2em !important; position: absolute !important; left: 50% !important; top: 50% !important; transform: translate(-50%, -50%) !important; user-select: none !important; cursor: auto !important; } .github-emoji-fallback { color: inherit; } .github-emoji-fallback img { opacity: 0 !important; }</style>
</head>
<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
<div class="headband"></div>
<main class="main">
<header class="header" itemscope itemtype="http://schema.org/WPHeader">
<div class="header-inner"><div class="site-brand-container">
<div class="site-nav-toggle">
<div class="toggle" aria-label="切换导航栏" role="button">
<span class="toggle-line"></span>
<span class="toggle-line"></span>
<span class="toggle-line"></span>
</div>
</div>
<div class="site-meta">
<a href="/" class="brand" rel="start">
<i class="logo-line"></i>
<h1 class="site-title">Conver</h1>
<i class="logo-line"></i>
</a>
</div>
<div class="site-nav-right">
<div class="toggle popup-trigger">
<i class="fa fa-search fa-fw fa-lg"></i>
</div>
</div>
</div>
<nav class="site-nav">
<ul class="main-menu menu">
<li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li>
<li class="menu-item menu-item-about"><a href="/about/" rel="section"><i class="fa fa-user fa-fw"></i>关于</a></li>
<li class="menu-item menu-item-tags"><a href="/tags/" rel="section"><i class="fa fa-tags fa-fw"></i>标签</a></li>
<li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li>
<li class="menu-item menu-item-schedule"><a href="/schedule/" rel="section"><i class="fa fa-calendar fa-fw"></i>日程表</a></li>
<li class="menu-item menu-item-search">
<a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
</a>
</li>
</ul>
</nav>
<div class="search-pop-overlay">
<div class="popup search-popup"><div class="search-header">
<span class="search-icon">
<i class="fa fa-search"></i>
</span>
<div class="search-input-container">
<input autocomplete="off" autocapitalize="off" maxlength="80"
placeholder="搜索..." spellcheck="false"
type="search" class="search-input">
</div>
<span class="popup-btn-close" role="button">
<i class="fa fa-times-circle"></i>
</span>
</div>
<div class="search-result-container no-result">
<div class="search-result-icon">
<i class="fa fa-spinner fa-pulse fa-5x"></i>
</div>
</div>
</div>
</div>
</div>
<div class="toggle sidebar-toggle" role="button">
<span class="toggle-line"></span>
<span class="toggle-line"></span>
<span class="toggle-line"></span>
</div>
<aside class="sidebar">
<div class="sidebar-inner sidebar-overview-active">
<ul class="sidebar-nav">
<li class="sidebar-nav-toc">
文章目录
</li>
<li class="sidebar-nav-overview">
站点概览
</li>
</ul>
<div class="sidebar-panel-container">
<!--noindex-->
<div class="post-toc-wrap sidebar-panel">
</div>
<!--/noindex-->
<div class="site-overview-wrap sidebar-panel">
<div class="site-author site-overview-item animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
<img class="site-author-image" itemprop="image" alt="Conver"
src="/images/conver.jpg">
<p class="site-author-name" itemprop="name">Conver</p>
<div class="site-description" itemprop="description">又叒开小号了 ^ _ ^</div>
</div>
<div class="site-state-wrap site-overview-item animated">
<nav class="site-state">
<div class="site-state-item site-state-posts">
<a href="/archives">
<span class="site-state-item-count">9</span>
<span class="site-state-item-name">日志</span>
</a>
</div>
<div class="site-state-item site-state-categories">
<a href="/categories/">
<span class="site-state-item-count">3</span>
<span class="site-state-item-name">分类</span></a>
</div>
<div class="site-state-item site-state-tags">
<a href="/tags/">
<span class="site-state-item-count">5</span>
<span class="site-state-item-name">标签</span></a>
</div>
</nav>
</div>
<div class="links-of-author site-overview-item animated">
<span class="links-of-author-item">
<a href="https://github.com/conver334" title="GitHub → https://github.com/conver334" rel="noopener" target="_blank"><i class="fab fa-github fa-fw"></i>GitHub</a>
</span>
<span class="links-of-author-item">
<a href="/conver334@gmail.com" title="E-Mail → conver334@gmail.com"><i class="fa fa-envelope fa-fw"></i>E-Mail</a>
</span>
</div>
<div class="links-of-blogroll site-overview-item animated">
<div class="links-of-blogroll-title"><i class="fa fa-globe fa-fw"></i>
友链
</div>
<ul class="links-of-blogroll-list">
<li class="links-of-blogroll-item">
<a href="https://zzy991212.github.io/" title="https://zzy991212.github.io/" rel="noopener" target="_blank">zzy</a>
</li>
<li class="links-of-blogroll-item">
<a href="https://blog.csdn.net/weixin_43811226/" title="https://blog.csdn.net/weixin_43811226/" rel="noopener" target="_blank">YuanSnowing</a>
</li>
<li class="links-of-blogroll-item">
<a href="http://maomaoyu804.github.io/" title="http://maomaoyu804.github.io" rel="noopener" target="_blank">毛毛雨</a>
</li>
<li class="links-of-blogroll-item">
<a href="http://kongjune.com/" title="http://kongjune.com" rel="noopener" target="_blank">kongjune</a>
</li>
<li class="links-of-blogroll-item">
<a href="http://epeenofront.com/" title="http://epeenofront.com" rel="noopener" target="_blank">epeenofront</a>
</li>
<li class="links-of-blogroll-item">
<a href="https://cardiffle.github.io/" title="https://cardiffle.github.io/" rel="noopener" target="_blank">Vicente</a>
</li>
<li class="links-of-blogroll-item">
<a href="http://www.callmelare.cn/blog/" title="http://www.callmelare.cn/blog/" rel="noopener" target="_blank">Lare</a>
</li>
</ul>
</div>
</div>
</div>
</div>
</aside>
<div class="sidebar-dimmer"></div>
</header>
<div class="back-to-top" role="button">
<i class="fa fa-arrow-up"></i>
<span>0%</span>
</div>
<noscript>
<div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>
<div class="main-inner index posts-expand">
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://conver334.github.io/2021/04/30/aliinterview/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/conver.jpg">
<meta itemprop="name" content="Conver">
<meta itemprop="description" content="又叒开小号了 ^ _ ^">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Conver">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/04/30/aliinterview/" class="post-title-link" itemprop="url">阿里国际化中台校园招聘-研发工程师JAVA-面经</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-04-30 15:18:03" itemprop="dateCreated datePublished" datetime="2021-04-30T15:18:03+08:00">2021-04-30</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2021-05-08 00:27:49" itemprop="dateModified" datetime="2021-05-08T00:27:49+08:00">2021-05-08</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E6%97%A5%E5%B8%B8%E8%AE%B0%E5%BD%95/" itemprop="url" rel="index"><span itemprop="name">日常记录</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h1 id="面试流程">面试流程</h1>
<p>阿里的面试持续了1月左右，一共四轮，十分漫长。校招投递时间3月中旬，期间因为有考试麻烦了考官帮我延期3周，如果按照正常进度一周一面的话应该4月初结束。</p>
<p>一面（电话面）→笔试（在线测试）→二面（电话面）→三面（电话面）→四面（视频面）</p>
<h2 id="一面">一面</h2>
<p>1小时，在笔试之前先面试是万万没想到的，可能因为是内推</p>
<p>问题：</p>
<ol type="1">
<li><p>自我介绍</p></li>
<li><p>描述TCP和UDP区别</p></li>
<li><p>进程和线程区别</p></li>
<li><p>java内线程通信如何实现</p></li>
<li><p>能讲一下数据库索引吗</p></li>
<li><p>讲一下JVM虚拟机</p></li>
<li><p>两道算法题，用阿里的伯乐系统在线做</p>
<ul>
<li>7-1 找一棵树中距离最远的两点距离</li>
<li>7-2 给你n个数，表示一列并排的矩形，他们的宽度为1，高度为第i个数的值。问这堆矩形能形成的最大长方形面积</li>
</ul></li>
</ol>
<h2 id="笔试">笔试</h2>
<p>1小时，两道算法题</p>
<ol type="1">
<li>忘记了，用到了栈</li>
<li>一棵带边权的树，三个人每个人都有几个中意的点，在中意的点中居住的概率相同，三个人会选择距离和最近的点集合，问期望路程是多少。数据范围树的点数n<2e5，偏好酒店个数k<n, 时限3s。</li>
</ol>
<h2 id="二面">二面</h2>
<ol type="1">
<li>自我介绍</li>
<li>做过的项目介绍，会问简历中具体做过项目的细节，详细到你的思路，建模过程，实现过程中的难点</li>
<li>有什么你在简历中没写的吗？会根据回答具体讨论，关于我的回答问题是
<ul>
<li>3-1 产品经理需要有什么特质</li>
<li>3-2 如果开发一款创新性的产品，例如发明微信，需要具备什么产品思维</li>
</ul></li>
<li>JAVA的基本变量类型</li>
<li>TCP协议和IP协议的区别</li>
<li>应用层有哪些协议</li>
</ol>
<h2 id="三面">三面</h2>
<ol type="1">
<li>自我介绍</li>
<li>职业规划</li>
<li>数据库事务</li>
<li>数据库的并发一致性问题，例如丢失修改，读脏数据，不可重复读，幻影读</li>
<li>你本科最擅长的科目？根据回答会问相应问题，我回答了操作系统和数据结构，接下来用在线评测系统写代码
<ul>
<li>5-1 实现生产者消费者</li>
<li>5-2 每步可以走1 或 2 级台阶，有 n个台阶，问多少种走法</li>
</ul></li>
</ol>
<h2 id="四面">四面</h2>
<ol type="1">
<li>自我介绍</li>
<li>根据简历项目，询问项目细节</li>
<li>大学中做过的这些项目，印象最深刻的是，代表性的开发作品，锻炼了你什么</li>
<li>解决一个问题，如何实现：淘宝中有很多商品，有些商品会被经常访问，就把他放到缓存中而不是数据库中，但是商品很多，如何决定把哪些商品放在缓存中？</li>
<li>英文自我介绍</li>
<li>英文3年职业规划</li>
</ol>
<h1 id="答案">答案</h1>
<p>答案是根据自己学的回答的，不是一定的标准答案，各种项目细节更是仅供参考描述。</p>
<p>写答案的主要原因是因为我在准备的过程中，参考了大量开源社区的整理，还有b站up主的视频，所以希望自己也能够帮到别人。</p>
<h2 id="一面-1">一面</h2>
<ol type="1">
<li><p>自我介绍</p></li>
<li><p>描述TCP和UDP区别</p>
<blockquote>
<ul>
<li>用户数据报协议 UDP（User Datagram Protocol）是无连接的，尽最大可能交付，没有拥塞控制，面向报文（对于应用程序传下来的报文不合并也不拆分，只是添加 UDP 首部），支持一对一、一对多、多对一和多对多的交互通信。</li>
<li>传输控制协议 TCP（Transmission Control Protocol）是面向连接的，提供可靠交付，有流量控制，拥塞控制，提供全双工通信，面向字节流（把应用层传下来的报文看成字节流，把字节流组织成大小不等的数据块），每一条 TCP 连接只能是点对点的（一对一）。</li>
</ul>
</blockquote></li>
<li><p>进程/线程/协程区别</p>
<blockquote>
<p>进程是资源管理单位，线程程序执行单位（这个执行程序是指kernel thread，才能真正的去执行程序，应用程序的thread和kernel thread 存在映射关系）为了提高routine切换成本比较低，协程是routine的一种实现</p>
<p>Ⅰ 拥有资源</p>
<p>进程是资源分配的基本单位，但是线程不拥有资源，线程可以访问隶属进程的资源。</p>
<p>Ⅱ 调度</p>
<p>线程是独立调度的基本单位，在同一进程中，线程的切换不会引起进程切换，从一个进程中的线程切换到另一个进程中的线程时，会引起进程切换。</p>
<p>Ⅲ 系统开销</p>
<p>由于创建或撤销进程时，系统都要为之分配或回收资源，如内存空间、I/O 设备等，所付出的开销远大于创建或撤销线程时的开销。类似地，在进行进程切换时，涉及当前执行进程 CPU 环境的保存及新调度进程 CPU 环境的设置，而线程切换时只需保存和设置少量寄存器内容，开销很小。</p>
<p>Ⅳ 通信方面</p>
<p>线程间可以通过直接读写同一进程中的数据进行通信，但是进程通信需要借助 IPC。</p>
</blockquote></li>
<li><p>java内线程通信如何实现</p>
<blockquote>
<p>多种方法，详情见：https://redspider.gitbook.io/concurrent/di-yi-pian-ji-chu-pian/5</p>
<p>利用锁与同步、等待通知机制、信号量、管道和其他方法等</p>
</blockquote></li>
<li><p>能讲一下数据库索引吗</p>
<blockquote>
<p>索引是加快了查询。</p>
<p>数据库的索引实现是数据结构b+ 树。b+树非叶子结点不存储data，只存储索引，可以存放更多的索引叶子结点包含所有索引字段叶子结点用指针连接，提高区间访问的性能。</p>
<p>innodb的索引是聚簇索引，主索引的叶子节点 data 域记录着完整的数据记录，这种索引方式被称为聚簇索引。因为无法把数据行存放在两个不同的地方，所以一个表只能有一个聚簇索引。辅助索引的叶子节点的 data 域记录着主键的值，因此在使用辅助索引进行查找时，需要先查找到主键值，然后再到主索引中进行查找。</p>
</blockquote></li>
</ol>
<figure>
<img src="/images/210430_2.jpg" alt="image1"><figcaption aria-hidden="true">image1</figcaption>
</figure>
<blockquote>
<p>MyISAM是非聚簇索引，叶子节点上不存储数据。</p>
<p>关于联合索引，要注意建立索引时遵循左匹配原理。将区分度高的字段放在前面，区分度低的字段放后面。像性别、状态这种字段区分度就很低，我们一般放后面。</p>
</blockquote>
<ol start="6" type="1">
<li><p>讲一下JVM虚拟机</p>
<blockquote>
<p>java成为跨平台语言的关键</p>
<p>所有线程共享的部分有：java堆，方法区</p>
<p>每个线程私有的是：pc寄存器，java虚拟机栈，本地方法栈</p>
<p>各部分的功能详情见：</p>
<p><a target="_blank" rel="noopener" href="http://www.cyc2018.xyz/Java/Java%20%E8%99%9A%E6%8B%9F%E6%9C%BA.html#%E4%B8%80%E3%80%81%E8%BF%90%E8%A1%8C%E6%97%B6%E6%95%B0%E6%8D%AE%E5%8C%BA%E5%9F%9F">链接</a></p>
</blockquote></li>
</ol>
<p><img src="/images/210430_1.jpg"></p>
<ol start="7" type="1">
<li><p>两道算法题，用阿里的伯乐系统在线做</p>
<ul>
<li><p>7-1 找一棵树中距离最远的两点距离</p>
<blockquote>
<p>dfs。</p>
<p>方法一：对每个结点，维护子节点的最长链和次长链，最远点的距离就是对某个结点的最长链+次长链长度</p>
<p>方法二：实际上是求树的直径。第一遍dfs找到最远点，然后把这个结点作为根节点再跑一次dfs找到最远点。两次找到的点都是直径的端点</p>
</blockquote></li>
<li><p>7-2 给你n个数，表示一列并排的矩形，他们的宽度为1，高度为第i个数的值。问这堆矩形能形成的最大长方形面积</p>
<blockquote>
<p>栈</p>
<p>暴力想法：我们肯定对每个高度，都尽量找它向左和向右最远到哪</p>
<p>可以用高度递增的栈维护上面的边界，记录结点的位置和高度，栈中保证结点高度是非递减的，这样每当一个新节点加入时，栈内的点如果高度小于等于它就压进去，大于它的话就把栈顶弹(hi,xi)掉。弹掉时维护答案，它的高度*（当前要加入栈数位置-它栈下一个数的位置）</p>
</blockquote></li>
</ul></li>
</ol>
<h2 id="笔试-1">笔试</h2>
<p>1小时，两道算法题</p>
<ol type="1">
<li><p>简单题，忘记了，用到了栈</p></li>
<li><p>一棵带边权的树，三个人每个人都有几个中意的点，在中意的点中居住的概率相同，三个人会选择距离和最近的点集合，问期望路程是多少。数据范围树的点数n<2e5，偏好酒店个数k<n, 时限3s。</p>
<blockquote>
<p>一条边对答案的贡献是他左右两边的不同人的方案数， 因为这条边必须被经过才能在这些选点方式中将三个点连通 且三个点连通的最短情况下每条路径上的边只会被经过一次</p>
<p>核心代码</p>
</blockquote>
<figure class="highlight c++"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line">tmp=cou[v][<span class="number">1</span>]*(num[<span class="number">2</span>]-cou[v][<span class="number">2</span>])*(num[<span class="number">3</span>]-cou[v][<span class="number">3</span>]);</span><br><span class="line">tmp+=cou[v][<span class="number">2</span>]*(num[<span class="number">1</span>]-cou[v][<span class="number">1</span>])*(num[<span class="number">3</span>]-cou[v][<span class="number">3</span>]);</span><br><span class="line">tmp+=cou[v][<span class="number">3</span>]*(num[<span class="number">2</span>]-cou[v][<span class="number">2</span>])*(num[<span class="number">1</span>]-cou[v][<span class="number">1</span>]);</span><br><span class="line">tmp+=cou[v][<span class="number">2</span>]*cou[v][<span class="number">3</span>]*(num[<span class="number">1</span>]-cou[v][<span class="number">1</span>]);</span><br><span class="line">tmp+=cou[v][<span class="number">1</span>]*cou[v][<span class="number">3</span>]*(num[<span class="number">2</span>]-cou[v][<span class="number">2</span>]);</span><br><span class="line">tmp+=cou[v][<span class="number">1</span>]*cou[v][<span class="number">2</span>]*(num[<span class="number">3</span>]-cou[v][<span class="number">3</span>]);</span><br></pre></td></tr></tbody></table></figure></li>
</ol>
<h2 id="二面-1">二面</h2>
<ol type="1">
<li><p>自我介绍</p></li>
<li><p>做过的项目介绍，会问简历中具体做过项目的细节，详细到你的思路，建模过程，实现过程中的难点</p></li>
<li><p>有什么你在简历中没写的吗？会根据回答具体讨论，关于我的回答问题是</p>
<ul>
<li>3-1 产品经理需要有什么特质</li>
<li>3-2 如果开发一款创新性的产品，例如发明微信，需要具备什么产品思维</li>
</ul></li>
<li><p>JAVA的基本变量类型</p>
<blockquote>
<ul>
<li>byte/8</li>
<li>char/16</li>
<li>short/16</li>
<li>int/32</li>
<li>float/32</li>
<li>long/64</li>
<li>double/64</li>
<li>boolean/~</li>
</ul>
</blockquote></li>
<li><p>TCP协议和IP协议的区别</p>
<blockquote>
<p>tcp是运输层协议，IP是网络层协议。</p>
<p>运输层是解决进程之间基于网络的通信问题，是端到端通信。</p>
<p>网络层是解决分组在多个网络上传输的问题</p>
</blockquote></li>
<li><p>应用层有哪些协议</p>
<blockquote>
<p>https、ftp、smtp等</p>
</blockquote></li>
</ol>
<h2 id="三面-1">三面</h2>
<ol type="1">
<li><p>自我介绍</p></li>
<li><p>职业规划</p></li>
<li><p>数据库事务</p>
<blockquote>
<p>事务指的是满足 ACID 特性的一组操作，可以通过 Commit 提交一个事务，也可以使用 Rollback 进行回滚。</p>
<ul>
<li>1.数据库事务可以包含一个或多个数据库操作,但这些操作构成一个逻辑上的整体。</li>
<li>2.构成逻辑整体的这些数据库操作,要么全部执行成功,要么全部不执行。</li>
<li>3.构成事务的所有操作,要么全都对数据库产生影响,要么全都不产生影响,即不管事务是否执行成功,数据库总能保持一致性状态。</li>
<li>4.以上即使在数据库出现故障以及并发事务存在的情况下依然成立。</li>
</ul>
<p>例如：</p>
<figure class="highlight plain"><table><tbody><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">>BEGIN TRANSACTION </span><br><span class="line">>A账户减少100元</span><br><span class="line">>B账户增加100元</span><br><span class="line">>COMMIT</span><br></pre></td></tr></tbody></table></figure>
<p>事务使系统能够更方便的进行故障恢复以及并发控制,从而保证数据库状态的一致性。</p>
</blockquote></li>
<li><p>数据库的并发一致性问题，例如丢失修改，读脏数据，不可重复读，幻影读</p></li>
<li><p>你本科最擅长的科目？根据回答会问相应问题，我回答了操作系统和数据结构，接下来用在线评测系统写代码</p>
<ul>
<li><p>5-1 实现生产者消费者。是多线程通信的例子</p></li>
<li><p><a target="_blank" rel="noopener" href="http://www.cyc2018.xyz/Java/Java%20%E5%B9%B6%E5%8F%91.html#%E6%97%A0%E5%90%8C%E6%AD%A5%E6%96%B9%E6%A1%88">链接</a></p>
<p>哎。当时没写出来，好难啊。先鸽了，以后补上！</p></li>
<li><p>5-2 每步可以走1 或 2 级台阶，有 n个台阶，问多少种走法。要求写注释，排版好看点。。。</p>
<blockquote>
<p>递归</p>
</blockquote>
<figure class="highlight c++"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//问题：每步可以走1 或 2 级台阶，有 n个台阶，问多少种走法</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><iostream></span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><cstdio></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> maxn=<span class="number">10000</span>;</span><br><span class="line"><span class="comment">//总方案数</span></span><br><span class="line"><span class="keyword">int</span> tot = <span class="number">0</span>;</span><br><span class="line"><span class="comment">//方案记录数组</span></span><br><span class="line"><span class="keyword">int</span> v[maxn],num;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">dfs</span><span class="params">(<span class="keyword">int</span> cou)</span></span>{</span><br><span class="line"> <span class="keyword">if</span>(cou == n){</span><br><span class="line"> <span class="comment">//输出方案</span></span><br><span class="line"> <span class="comment">//总方案数+1</span></span><br><span class="line"> tot++; </span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"现在是第%d 种方案，走法是："</span>,tot);</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i = <span class="number">1</span>;i <= num;i++)<span class="built_in">printf</span>(<span class="string">"%d "</span>,v[i]);</span><br><span class="line"> <span class="built_in">cout</span><<<span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">return</span> ;</span><br><span class="line"> }</span><br><span class="line"> <span class="comment">//不能构成方案，返回</span></span><br><span class="line"> <span class="keyword">if</span>(cou > n)<span class="keyword">return</span>;</span><br><span class="line"> <span class="comment">//这一步走一级台阶</span></span><br><span class="line"> v[++num]=<span class="number">1</span>;</span><br><span class="line"> dfs(cou+<span class="number">1</span>);</span><br><span class="line"> <span class="comment">//回溯</span></span><br><span class="line"> num--;</span><br><span class="line"> <span class="comment">//这一步走两级台阶</span></span><br><span class="line"> v[++num]=<span class="number">2</span>;</span><br><span class="line"> dfs(cou+<span class="number">2</span>);</span><br><span class="line"> num--;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> dfs(<span class="number">0</span>);</span><br><span class="line"> <span class="comment">//输出总方案数</span></span><br><span class="line"> <span class="built_in">cout</span><<tot<<<span class="built_in">endl</span>;</span><br><span class="line">}</span><br></pre></td></tr></tbody></table></figure></li>
</ul></li>
</ol>
<h2 id="四面-1">四面</h2>
<ol type="1">
<li>自我介绍</li>
<li>根据简历项目，询问项目细节</li>
</ol>
<blockquote>
<p>化学建筑项目。</p>
<p>光能转化模型</p>
<ol type="1">
<li>太阳能电池最佳倾角</li>
<li>向光材料接受率分析</li>
<li>编程原理</li>
</ol>
<p>问了模型设计的难点，考虑将建模与AI结合，创新点，学到了什么，建模过程</p>
</blockquote>
<ol type="1">
<li>大学中做过的这些项目，印象最深刻的是，代表性的开发作品，锻炼了你什么</li>
</ol>
<blockquote>
<p>产品经理</p>
<p>微北洋，轻北洋。设计的特点，两者区别。</p>
<p>产品的创新点！突出特点</p>
<p>定位</p>
</blockquote>
<ol type="1">
<li><p>解决一个问题，如何实现：淘宝中有很多商品，有些商品会被经常访问，就把他放到缓存中而不是数据库中，但是商品很多，如何决定把哪些商品放在缓存中？</p>
<blockquote>
<p>实际是缓存淘汰算法</p>
<p>1.LRU 最近最久未使用</p>
<p>LRU 近最久未使用的页面换出。</p>
<p>第一种实现方式直接用链表。 当一个页面被访问时，将这个页面移到链表表头。但是每次都要遍历链表，代价较高。</p>
<p>第二种实现方式hashmap+链表。查询数据是否在链表中用hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。</p>
<ol start="2" type="1">
<li>NRU 最近未使用</li>
</ol>
<p>两个标记R/M。R标记被访问，M标记被修改。R位会定时清零。页面分为4类：</p>
<p>R=0, M=0</p>
<p>R=0, M=1</p>
<p>R=1, M=0</p>
<p>R=1, M=1</p>
<p>发生缺页中断，随机从编号最小的非空类中选一个页面换出。</p>
<p>NRU优先换出已被修改的脏页面（R=0,M=1)，而不是被频繁使用的干净页面（R=1,M=0)</p>
</blockquote></li>
<li><p>英文自我介绍</p></li>
<li><p>英文3年职业规划</p></li>
</ol>
<h1 id="感受">感受</h1>
<p>第一面是最懵逼的，因为是第一次投实习，第一次面试，根本不知道还有面经这种东西存在。没有准备，以为凭着本科所学直接上，实际上证明了——我本科什么都没有学的深入，或者说没学到能记住细节，几乎所有被问的问题都是对这个问题在哪堂课见过有个印象，但是答不上来，万幸的是面试官见我基础太差就直接开始考算法题。果然只有大学打过的acm印在了脑子里。基础太差又薄弱，也没有项目支撑。</p>
<p>还有阿里的面试官非常准时，一般跟你约好的时间会准时出现，后来我就在约好的时间提前半小时提前准备了。</p>
<p>第一面结束后很受挫，开始认真准备面试。大体分为三步：</p>
<p>1.基础知识学习。</p>
<p>2.看视频，理解技术细节。</p>
<p>3.刷面经，对着题目回答。</p>
<p>基础知识复习参考：</p>
<p>http://www.cyc2018.xyz/#%E7%AE%97%E6%B3%95</p>
<p>细节讲解，有很多不错的b站教程：</p>
<p>https://www.bilibili.com/video/BV1c4411d7jb?p=44&t=661</p>
<p>https://www.bilibili.com/video/BV14z4y1d7Wa?t=912</p>
<p>https://www.bilibili.com/video/BV1aE41117sk?p=8&t=1023</p>
<p>https://www.bilibili.com/video/BV1Wr4y1A7DS</p>
<p>面经：牛客网，很多面经。</p>
<p>https://www.nowcoder.com/discuss/620617?channel=-1&source_id=discuss_terminal_discuss_history_nctrack&ncTraceId=0de4c2957e304ce1b6b8fb84384fbd59.956.16182236949048605</p>
<p>复习了1周左右，难受的是感觉东西越学越多，java不咋会写，还要学spring框架，操作系统的算法看了就忘。期间收藏了不少好课，十足的好课，可惜我大学前两年学基础时没有干脆自己看网课学这些。例如湖科的b站计网课，还有清华向勇老师的操作系统，可惜当年不知道，想今年有机会把这些看完。</p>
<p>第二、三、四面都意识流偏多，考官很喜欢聊科研中的细节，因为2年产品经理，每个考官都有和我聊到产品，还有4场面试中，3场都有算法题，感谢大学加入了天外天和acm，大一不经意做出的选择悄然间改变了发展的轨迹。</p>
<p>参加实习面试的还有一件影响就是它让我开始回顾自己。一是，接受自己很菜的事实，从高中起身边就已经有了让我仰慕的学术idol，都是在自己领域做的闪闪发光的人，他们的很多博客，记录都有影响到我追着脚步一点点前进；二是，感谢和珍重曾经做的每一次选择，大一刚入学的时候真的很迷茫，那时候我甚至一口气在百团大战报过10个社团，我大概属于对自己的未来规划有方向，却对具体实施不太清醒的人，大二的时候才明白，重点在于做减法而不是做加法，做好一件事足矣，只留下了天外天和acm，回想9.1日开学喻老师把我们召集起来开始布置acm训练，和9.31日坐在天外天的面试官前什么都不懂的我，肯定不知道悄然改变了3年后的自己。</p>
<p>更希望在阿里做开发可以学到很多东西，希望明年想起来发现这一年学会了更多的东西！</p>
<p>好吧其实这一阵子焦虑的很。</p>
<p>hahah</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://conver334.github.io/2021/04/23/cf1514/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/conver.jpg">
<meta itemprop="name" content="Conver">
<meta itemprop="description" content="又叒开小号了 ^ _ ^">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Conver">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/04/23/cf1514/" class="post-title-link" itemprop="url">[CF1514] Codeforces Round #716 (Div. 2)</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-04-23 09:55:53 / 修改时间：11:37:51" itemprop="dateCreated datePublished" datetime="2021-04-23T09:55:53+08:00">2021-04-23</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="a.-perfectly-imperfect-array">A. Perfectly Imperfect Array</h2>
<p><strong>题解</strong></p>
<p>只要任意一个数不是平方数就可以</p>
<figure class="highlight c++"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">int</span> <span class="keyword">const</span> maxn=<span class="number">2e5</span>+<span class="number">10</span>;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"></span><br><span class="line"> <span class="keyword">int</span> t,n,a,v;</span><br><span class="line"> <span class="built_in">cin</span>>>t;</span><br><span class="line"> <span class="keyword">while</span>(t--){</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&n);</span><br><span class="line"> <span class="keyword">bool</span> flag=<span class="literal">false</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++){</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&a);</span><br><span class="line"> v=<span class="built_in">sqrt</span>(a);</span><br><span class="line"> <span class="keyword">if</span>(v*v!=a)flag=<span class="literal">true</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span>(flag)<span class="built_in">printf</span>(<span class="string">"YES\n"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"NO\n"</span>);</span><br><span class="line"> } </span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></tbody></table></figure>
<h2 id="b-.-and-0-sum-big">B . AND 0, Sum Big</h2>
<p><strong>题意</strong>：</p>
<p>给你N和K, 问有多少长度为n的数组满足：</p>
<ul>
<li>所有元素在[0,<span class="math inline">\(2^k-1\)</span> ]范围内</li>
<li>所有元素AND值为0</li>
<li>所有元素之和尽可能大</li>
</ul>
<p><strong>题解</strong>：</p>
<p>快速幂：二进制k位，只要每一位有一个0就能满足条件2，为了满足条件3每一位只能在数组中的一个数中为0，所以每一位的选择有n个数，答案为<span class="math inline">\(n^k\)</span></p>
<figure class="highlight c++"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">long</span> <span class="keyword">long</span> p=<span class="number">1e9</span>+<span class="number">7</span>;</span><br><span class="line"><span class="keyword">long</span> <span class="keyword">long</span> n,k,t;</span><br><span class="line"><span class="function"><span class="keyword">long</span> <span class="keyword">long</span> <span class="title">pow_fast</span><span class="params">(<span class="keyword">long</span> <span class="keyword">long</span> a,<span class="keyword">long</span> <span class="keyword">long</span> b,<span class="keyword">long</span> <span class="keyword">long</span> mod)</span></span>{</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> num=<span class="number">1</span>%mod;</span><br><span class="line"> <span class="keyword">for</span>(;b;b>>=<span class="number">1</span>,a=a*a%mod)</span><br><span class="line"> <span class="keyword">if</span>(b&<span class="number">1</span>)num=num*a%mod;</span><br><span class="line"> <span class="keyword">return</span> num;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="built_in">cin</span>>>t;</span><br><span class="line"> <span class="keyword">while</span>(t--){</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%lld%lld"</span>,&n,&k);</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> ans=pow_fast(n,k,p);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>,ans);</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></tbody></table></figure>
<h2 id="c-.-product-1-modulo-n">C . Product 1 Modulo N</h2>
<p><strong>题意</strong>：</p>
<p>给定n，问[1,n-1]范围内，最多可以取多少数，使其乘积取模n为1</p>
<p><strong>数据范围</strong>：</p>
<p><span class="math display">\[\left( 2 \leq n \leq 10^{5}\right)\]</span></p>
<p><strong>题解</strong>：</p>
<p>首先知道一个结论：如果a，b的最大公约数g=gcd(a,b)不为1，则a%b大于1，因为a%b的余数一定是g的倍数。</p>
<p>（1） a%b = (a/g) % (b/g) * g</p>
<p>所以只能选与n互质的数，他们的乘积取余n的结果x也与n互质，x就在刚刚所取的数中，只要把x删掉就行了</p>
<blockquote>
<p>证明1： a%b = (a/g) % (b/g) * g</p>
<p><img src="/images/210423_1.jpg"></p>
<p><img src="/images/210423_2.jpg"></p>
<p>证明:2：与b互质的数乘积取余b的余数与b互质</p>
<p>设 <span class="math inline">\(a_1,a_2,a_3..a_m\)</span> 与b互质 z=a_1<em>a_2</em>a_3 z=n*b+p g=gcd(n,p) n=cg , p=dg z=gcb+dg=g(cb+d) 则 g是 z 的因子，如果g ≠ 1,则n与 z不互质，与题设矛盾</p>
</blockquote>
<figure class="highlight c++"><table><tbody><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="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="built_in">vector</span><<span class="keyword">int</span>> v;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">gcd</span><span class="params">(<span class="keyword">int</span> a,<span class="keyword">int</span> b)</span><span class="comment">//最大公约数，辗转相除 </span></span></span><br><span class="line"><span class="function"></span>{</span><br><span class="line"> <span class="keyword">return</span> b?gcd(b,a%b):a;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="keyword">int</span> n;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&n);</span><br><span class="line"> v.push_back(<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> tmp=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">long</span> <span class="keyword">long</span> i=<span class="number">2</span>;i<n;i++){</span><br><span class="line"> <span class="keyword">if</span> (gcd(i,n)==<span class="number">1</span>){<span class="comment">//只能选与n互质的数</span></span><br><span class="line"> v.push_back(i);</span><br><span class="line"> tmp=(<span class="number">1ll</span>*tmp*i)%n;</span><br><span class="line"> } </span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (tmp==<span class="number">1ll</span>) <span class="built_in">cout</span><<v.size()<<<span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">cout</span><<v.size()<span class="number">-1</span><<<span class="built_in">endl</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">long</span> <span class="keyword">long</span> i=<span class="number">0</span>;i<v.size();i++){</span><br><span class="line"> <span class="keyword">if</span> (v[i]==tmp&&tmp!=<span class="number">1</span>) <span class="keyword">continue</span>;</span><br><span class="line"> <span class="built_in">cout</span><<v[i]<<<span class="string">" "</span>;<span class="comment">//余数>1时，把余数删</span></span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">cout</span><<<span class="built_in">endl</span>;</span><br><span class="line">}</span><br></pre></td></tr></tbody></table></figure>
<p>网上看到的另一种不错证明，<a target="_blank" rel="noopener" href="https://blog.csdn.net/weixin_44178736/article/details/115918245">原文链接</a></p>
<blockquote>
<p>不能选与n不互质的数, 因为选了之后%n一定不为1,因为gcd(乘积,n)!=1. 证明: 设gcd(p,n)=z,则p=xz,n=yz, 设选的其他数乘积为q, 则pq%n=1,设pq=kn+1, 那么qxz=kyz+1, (qx-ky)z=1, 当且仅当z=1时式子才有可能成立, 而gcd=z>1,因此式子不可能成立, 所以如果选择了gcd!=1的数,一定不满足条件.</p>
<p>因此只能选与n互质的数, 设s为所有与n互质的数的积对n取模的结果, 如果s=1,那么这些数全部可以选择, 如果s!=1,此时s一定与n互质,因此s也在这些数中, 那么选除了s的其他数就行了</p>
</blockquote>
<h2 id="d.-cut-and-stick">D. Cut and Stick</h2>
<p><strong>题意</strong>：</p>
<p>给出长度为n的序列a，q个询问，每次询问[l,r]区间。</p>
<p>问至少把区间内的数重新组合成几段，才能满足每段众数的次数不超过 <span class="math inline">\(\left \lceil len \right \rceil\)</span> , len为区间长度</p>
<p><strong>数据范围</strong>：</p>
<p><span class="math inline">\(\left( 1 \leq n,q \leq 3*10^{5}\right)\)</span></p>
<p><span class="math inline">\(a_{1}, a_{2, \ldots,} a_{n}\left(1 \leq a_{i} \leq n\right)\)</span></p>
<p><span class="math inline">\((1 \leq l \leq r \leq n)\)</span></p>
<p><strong>题解</strong>：</p>
<ol type="1">
<li>如果初始区间众数个数< <span class="math inline">\(\left \lceil len \right \rceil\)</span> , 则不用拆，答案为1。否则就要拆，关于每段如何拆分。</li>
</ol>
<p>偶→奇+奇 ，可容纳数增加1；奇→偶+奇，可容纳数不变。于是每次就是尽量拆偶数，变化如下</p>
<p>初始偶→奇+奇→偶+奇+奇→奇+奇+奇+奇→偶+奇++奇+奇+奇...</p>
<p>初始奇→偶+奇→奇+奇+奇→偶+奇++奇+奇...</p>
<p>实际上就是初始为偶数多了一步，后面跟奇数一样拆法。每多1个，段数+2。</p>
<ol start="2" type="1">
<li>莫队求区间众数，时间复杂度n*sqrt(n)。开一个数组num记录每个数的个数，<strong>数组cou[x]记录数量为x的数有几个</strong>。</li>
</ol>
<p>每次区间增加时，增加这个数的个数，维护cou。还有判断增加后是否变成区间众数</p>
<p>区间变小时，减少这个数的个数，维护cou。看当前众数个数值的cou是否变为0，如果变为0说明当前数为唯一众数，众数个数应该-1。</p>
<figure class="highlight python"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">#include<bits/stdc++.h></span></span><br><span class="line">using namespace std;</span><br><span class="line">// <span class="comment">#define debug(x,i) cout<<"haha"<<i<<' '<<x<<endl;</span></span><br><span class="line"><span class="built_in">int</span> const MAXN = <span class="number">3e5</span>+<span class="number">7</span>;</span><br><span class="line"><span class="built_in">int</span> a[MAXN],unit,n,m,nowmax,cnt[MAXN],ans[MAXN],num[MAXN];</span><br><span class="line">struct query1{</span><br><span class="line"> <span class="built_in">int</span> L,R,<span class="built_in">id</span>;</span><br><span class="line">}qu[MAXN];</span><br><span class="line"><span class="built_in">bool</span> cmp(query1 a,query1 b){</span><br><span class="line"> <span class="keyword">if</span>(a.L/unit == b.L/unit) //相同块，对R排序</span><br><span class="line"> <span class="keyword">return</span> a.R < b.R;</span><br><span class="line"> <span class="keyword">else</span> <span class="keyword">return</span> a.L/unit <b.L/unit; //不同块，对块排序</span><br><span class="line">}</span><br><span class="line">void mo_add(<span class="built_in">int</span> x){</span><br><span class="line"> cnt[num[a[x]]]--;</span><br><span class="line"> num[a[x]]++;</span><br><span class="line"> cnt[num[a[x]]]++;</span><br><span class="line"> <span class="keyword">if</span>(num[a[x]]>nowmax)nowmax=num[a[x]];</span><br><span class="line">}</span><br><span class="line">void mo_del(<span class="built_in">int</span> x){</span><br><span class="line"> cnt[num[a[x]]]--;</span><br><span class="line"> num[a[x]]--;</span><br><span class="line"> cnt[num[a[x]]]++;</span><br><span class="line"> <span class="keyword">if</span>(cnt[nowmax]==<span class="number">0</span>)nowmax--;</span><br><span class="line">}</span><br><span class="line">void work(){</span><br><span class="line"> <span class="built_in">int</span> L = <span class="number">1</span>,R = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="built_in">int</span> i=<span class="number">0</span>;i<m;i++){</span><br><span class="line"> <span class="keyword">while</span>(R < qu[i].R){</span><br><span class="line"> R++;</span><br><span class="line"> mo_add(R);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span>(R > qu[i].R){</span><br><span class="line"> mo_del(R);</span><br><span class="line"> R--;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span>(L < qu[i].L){</span><br><span class="line"> mo_del(L);</span><br><span class="line"> L++;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span>(L > qu[i].L){</span><br><span class="line"> L--;</span><br><span class="line"> mo_add(L);</span><br><span class="line"> }</span><br><span class="line"> // debug(nowmax,<span class="number">1</span>);</span><br><span class="line"> <span class="keyword">if</span>(nowmax<=ceil((R-L+<span class="number">1</span>)/<span class="number">2.0</span>))ans[qu[i].<span class="built_in">id</span>]=<span class="number">1</span>;</span><br><span class="line"> <span class="keyword">else</span>{//奇偶不同拆法</span><br><span class="line"> <span class="built_in">int</span> z=<span class="number">1</span>,<span class="built_in">len</span>=R-L+<span class="number">1</span>,u=nowmax-ceil((R-L+<span class="number">1</span>)/<span class="number">2.0</span>);</span><br><span class="line"> <span class="keyword">if</span>(<span class="built_in">len</span>%<span class="number">2</span>==<span class="number">0</span>){z++;u--;}</span><br><span class="line"> <span class="keyword">while</span>(u){</span><br><span class="line"> z+=<span class="number">2</span>;u--;</span><br><span class="line"> }</span><br><span class="line"> ans[qu[i].<span class="built_in">id</span>]=z;</span><br><span class="line"> } </span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="built_in">int</span> main(){</span><br><span class="line"> scanf(<span class="string">"%d%d"</span>,&n,&m);</span><br><span class="line"> <span class="keyword">for</span>(<span class="built_in">int</span> i=<span class="number">1</span>;i<=n;i++)scanf(<span class="string">"%d"</span>,&a[i]);</span><br><span class="line"> unit=sqrt(n);</span><br><span class="line"> <span class="keyword">for</span>(<span class="built_in">int</span> i=<span class="number">0</span>;i<m;i++){ //读入查询</span><br><span class="line"> scanf(<span class="string">"%d%d"</span>,&qu[i].L,&qu[i].R);</span><br><span class="line"> qu[i].<span class="built_in">id</span> = i;</span><br><span class="line"> }</span><br><span class="line"> sort(qu,qu+m,cmp);</span><br><span class="line"> work();</span><br><span class="line"> <span class="keyword">for</span>(<span class="built_in">int</span> i=<span class="number">0</span>;i<m;i++){</span><br><span class="line"> printf(<span class="string">"%d\n"</span>,ans[i]);</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></tbody></table></figure>
<p><strong>比赛时</strong>：</p>
<p>想到了莫队，但是当莫队区间变小时卡住了，忘记了只要再维护一个众数的个数有多少就行了。</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://conver334.github.io/2021/03/21/cf1496/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/conver.jpg">
<meta itemprop="name" content="Conver">
<meta itemprop="description" content="又叒开小号了 ^ _ ^">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Conver">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/03/21/cf1496/" class="post-title-link" itemprop="url">[CF1496] Codeforces Round #706 (Div. 2)</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-03-21 10:31:01 / 修改时间：11:35:58" itemprop="dateCreated datePublished" datetime="2021-03-21T10:31:01+08:00">2021-03-21</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<h2 id="a-.-split-it">A . Split it!</h2>
<p><strong>题解</strong></p>
<p>从开头和结尾向中间找最长的相同长度</p>
<figure class="highlight c++"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> maxn=<span class="number">110</span>;</span><br><span class="line"><span class="keyword">int</span> t,n,k;</span><br><span class="line"><span class="keyword">char</span> s[maxn];</span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">work</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="keyword">if</span>(n<=k*<span class="number">2</span>)<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">int</span> l=<span class="number">-1</span>,r=n;</span><br><span class="line"> <span class="keyword">while</span>(l+<span class="number">1</span><r<span class="number">-1</span> && s[l+<span class="number">1</span>]==s[r<span class="number">-1</span>]){</span><br><span class="line"> l++;r--;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span>(l+<span class="number">1</span>>=k)<span class="keyword">return</span> <span class="number">1</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 class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&t);</span><br><span class="line"> <span class="keyword">while</span>(t--){</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d%d"</span>,&n,&k);</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%s"</span>,s);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">if</span>(work())<span class="built_in">printf</span>(<span class="string">"YES\n"</span>);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"NO\n"</span>);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></tbody></table></figure>
<h2 id="b-.-max-and-mex">B . Max and Mex</h2>
<p><strong>题解</strong>：</p>
<ol type="1">
<li>如果mex为n，则每次向后插入mex，k次之后不同的值为n+k个</li>
<li>如果mex不为n，则每次插入的都是同一个值，如果这个值出现过，k次之后不同的值为n个；如果没出现过，k次之后不同的值为n+1个</li>
</ol>
<figure class="highlight c++"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> maxn=<span class="number">1e5</span>+<span class="number">10</span>;</span><br><span class="line"><span class="keyword">int</span> t;</span><br><span class="line"><span class="keyword">long</span> <span class="keyword">long</span> n,k,a[maxn];</span><br><span class="line"><span class="function"><span class="keyword">long</span> <span class="keyword">long</span> <span class="title">getmex</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="keyword">int</span> v=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++,v++){</span><br><span class="line"> <span class="keyword">if</span>(v!=a[i])<span class="keyword">return</span> v;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> v;</span><br><span class="line">}</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&t);</span><br><span class="line"> <span class="keyword">while</span>(t--){</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%lld%lld"</span>,&n,&k);</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++)<span class="built_in">scanf</span>(<span class="string">"%lld"</span>,&a[i]);</span><br><span class="line"> sort(a+<span class="number">1</span>,a+<span class="number">1</span>+n);</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> mex=getmex();</span><br><span class="line"> <span class="keyword">if</span>(mex==n)<span class="built_in">printf</span>(<span class="string">"%lld\n"</span>,n+k);</span><br><span class="line"> <span class="keyword">else</span>{</span><br><span class="line"> <span class="keyword">if</span>(k==<span class="number">0</span>){</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>,n);</span><br><span class="line"> <span class="keyword">continue</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> mid = <span class="built_in">ceil</span>((mex+a[n])/<span class="number">2.0</span>);</span><br><span class="line"> <span class="keyword">if</span>(a[lower_bound(a+<span class="number">1</span>,a+n+<span class="number">1</span>,mid)-a]==mid)<span class="built_in">printf</span>(<span class="string">"%lld\n"</span>,n);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"%lld\n"</span>,n+<span class="number">1</span>);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">}</span><br></pre></td></tr></tbody></table></figure>
<h2 id="c-.-diamond-miner">C . Diamond Miner</h2>
<p><strong>题意</strong>：</p>
<p>n个矿工在y轴上，n个矿在x轴上，一个人挖一个，花费的力气是点之间的欧几里得距离。问如何分配使得总花费最小</p>
<p><strong>数据范围</strong>：</p>
<p><span class="math display">\[\left( 1 \leq n \leq 10^{5}\right)\]</span></p>
<p><strong>题解</strong>：</p>
<p>绝对值相同的点是等价的，直接用|x||y|来代替x,y</p>
<p>会发现两个数组排序后，顺着配的值最小，即小的和小的，大的和大的。</p>
<p>证明方法是<strong>排序不等式</strong>：</p>
<p>定理：设 <span class="math inline">\(0<a_{1} \leqslant a_{2} \leqslant \cdots \leqslant a_{n}, 0<b_{1} \leqslant b_{2} \leqslant \cdots\leqslant b_{n}\)</span> 为两组实数, <span class="math inline">\(c_{1}, c_{2}, \cdots, c_{n}\)</span> 为 <span class="math inline">\(b_{1}, b_{2}, \cdots, b_{n}\)</span> 的任一排列，则有 <span class="math display">\[
\begin{array}{l}
\sqrt{a_{1}^{2}+b_{n}^{2}}+\sqrt{a_{2}^{2}+b_{n-1}^{2}}+\cdots+\sqrt{a_{\mathrm{n}}^{2}+b_{1}^{2}} \\
\geqslant \sqrt{a_{1}^{2}+c_{1}^{2}}+\sqrt{a_{2}^{2}+c_{2}^{2}}+\cdots+\sqrt{a_{n}^{2}+c_{n}^{2}} \\
\geqslant \sqrt{a_{1}^{2}+b_{1}^{2}}+\sqrt{a_{2}^{2}+b_{2}^{2}}+\cdots+\sqrt{a_{n}^{2}+b_{n}^{2}}
\end{array}
\]</span> 其中全相等 <span class="math inline">\(\Leftrightarrow a_{1}=a_{2}=\cdots=a_{n}\)</span> 或 <span class="math inline">\(b_{1}=b_{2}=\cdots=b_{n} .\)</span></p>
<p>证明方法，把两个排列相减呗</p>
<figure class="highlight c++"><table><tbody><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string"><bits/stdc++.h></span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> maxn=<span class="number">1e5</span>+<span class="number">10</span>;</span><br><span class="line"><span class="keyword">int</span> t, n;</span><br><span class="line"><span class="keyword">long</span> <span class="keyword">long</span> a[maxn],b[maxn];</span><br><span class="line"><span class="keyword">double</span> dis;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>{</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&t);</span><br><span class="line"> <span class="keyword">while</span>(t--){</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>,&n);</span><br><span class="line"> dis=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">int</span> tot=n*<span class="number">2</span>,tot1=<span class="number">0</span>,tot2=<span class="number">0</span>;</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> x,y;</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=tot;i++){</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%lld%lld"</span>,&x,&y);</span><br><span class="line"> <span class="keyword">if</span>(x==<span class="number">0</span>)a[++tot1]=<span class="built_in">abs</span>(y);</span><br><span class="line"> <span class="keyword">else</span> b[++tot2]=<span class="built_in">abs</span>(x);</span><br><span class="line"> }</span><br><span class="line"> sort(a+<span class="number">1</span>,a+<span class="number">1</span>+n);</span><br><span class="line"> sort(b+<span class="number">1</span>,b+<span class="number">1</span>+n);</span><br><span class="line"> <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">1</span>;i<=n;i++){</span><br><span class="line"> dis+=<span class="built_in">sqrt</span>(a[i]*a[i]+b[i]*b[i]);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%.10lf\n"</span>,dis);</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></tbody></table></figure>
<p>补充下关于 <span class="math inline">\(\sum_{i=1}^{n} \sqrt{a_{i}^{2}+b_{i}^{2}}\left(a_{i}, b_{i} \in \mathbf{R}\right)\)</span> 的不等式定理</p>
<p>柯西不等式： 设 <span class="math inline">\(a_{1}, a_{2}, \cdots, a_{n} ; b_{1}, b_{2}, \cdots, b_{n}\)</span> 为实数, <span class="math inline">\(n \in \mathbf{N}\)</span>,<span class="math inline">\(n \geqslant 2,\)</span> 则 <span class="math inline">\(\sqrt{a_{1}^{2}+b_{1}^{2}}+\sqrt{a_{2}^{2}+b_{2}^{2}}+\cdots+\sqrt{a_{n}^{2}+b_{n}^{2}} \geqslant\)</span> <span class="math inline">\(\sqrt{\left(a_{1}+a_{2}+\cdots+a_{n}\right)^{2}+\left(b_{1}+b_{2}+\cdots+b_{n}\right)^{2}}\)</span> 其中等号成立 <span class="math inline">\(\Leftrightarrow\)</span> 存在非负实数 <span class="math inline">\(\lambda\)</span> 及 <span class="math inline">\(\mu(\lambda, \mu\)</span> 不同时为0)<span class="math inline">\(,\)</span> 使得 <span class="math inline">\(\lambda a_{i}=\mu b_{i}(i=1,2, \cdots, n) .\)</span></p>
<h2 id="d-.-lets-go-hiking">D . Let's Go Hiking</h2>
<p>先丢一个队友题解链接：https://blog.csdn.net/weixin_43877657/article/details/114933752</p>
<p><strong>题意</strong>：</p>
<p>给出一个长度为n的排列，a先选一个位置，然后b再选一个位置，两人每次都可以向周围移动1位，满足移动后的位置a的值比原来小，b的值比原来小。两人都会采取最优策略，问初始时a选位置能赢的个数</p>
<p><strong>数据范围</strong>：</p>
<p><span class="math display">\[\left( 2 \leq n \leq 10^{5}\right)\]</span></p>
<p><strong>题解</strong>：</p>
<ol type="1">
<li>首先a要选在坡顶，坡腰b能把它堵死</li>
<li>a要选在最大峰的坡顶，否则b能选能大峰的坡地开始走</li>
<li>这个破必须长度为奇数，a会与b对着走，奇数才能在相会时让b无法走</li>
<li>不能有其他坡和这个坡长度相同，也就会说这个破不仅最大还唯一，否则b可以走那个</li>
</ol>
<p>画个示意图，注意上面4点坑</p>
<figure>
<img src="/images/210321_1.jpg" alt="image1"><figcaption aria-hidden="true">image1</figcaption>
</figure>
<figure class="highlight python"><table><tbody><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></pre></td><td class="code"><pre><span class="line">a,b,k=<span class="built_in">map</span>(<span class="built_in">int</span>,<span class="built_in">input</span>().split())</span><br><span class="line"><span class="keyword">if</span>(k==<span class="number">0</span>):</span><br><span class="line"> s=<span class="string">'1'</span>*b+<span class="string">'0'</span>*a</span><br><span class="line"> print(<span class="string">"Yes\n"</span>+s+<span class="string">"\n"</span>+s)</span><br><span class="line"><span class="keyword">elif</span>(a==<span class="number">0</span>):</span><br><span class="line"> print(<span class="string">"No"</span>);</span><br><span class="line"><span class="keyword">else</span>:</span><br><span class="line"> <span class="keyword">if</span> a+b-<span class="number">2</span><k <span class="keyword">or</span> b==<span class="number">1</span>:</span><br><span class="line"> print(<span class="string">"No"</span>)</span><br><span class="line"> <span class="keyword">else</span>:</span><br><span class="line"> s=<span class="string">'1'</span>*(b-<span class="number">1</span>)+<span class="string">'0'</span>*(a-<span class="number">1</span>)</span><br><span class="line"> print(<span class="string">"Yes"</span>)</span><br><span class="line"> print(s[:a+b-k-<span class="number">1</span>]+<span class="string">'1'</span>+s[a+b-k-<span class="number">1</span>:]+<span class="string">'0'</span>)</span><br><span class="line"> print(s[:a+b-k-<span class="number">1</span>]+<span class="string">'0'</span>+s[a+b-k-<span class="number">1</span>:]+<span class="string">'1'</span>)</span><br><span class="line"> </span><br></pre></td></tr></tbody></table></figure>
<p><strong>比赛时</strong>：</p>
<p>那个破不能超过一个没想到qwq</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://conver334.github.io/2021/03/12/tip/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/conver.jpg">
<meta itemprop="name" content="Conver">
<meta itemprop="description" content="又叒开小号了 ^ _ ^">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Conver">
</span>
<header class="post-header">
<h2 class="post-title" itemprop="name headline">
<a href="/2021/03/12/tip/" class="post-title-link" itemprop="url">tip</a>
</h2>
<div class="post-meta-container">
<div class="post-meta">
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar"></i>
</span>
<span class="post-meta-item-text">发表于</span>
<time title="创建时间：2021-03-12 20:59:17" itemprop="dateCreated datePublished" datetime="2021-03-12T20:59:17+08:00">2021-03-12</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-calendar-check"></i>
</span>
<span class="post-meta-item-text">更新于</span>
<time title="修改时间：2021-03-13 08:48:14" itemprop="dateModified" datetime="2021-03-13T08:48:14+08:00">2021-03-13</time>
</span>
<span class="post-meta-item">
<span class="post-meta-item-icon">
<i class="far fa-folder"></i>
</span>
<span class="post-meta-item-text">分类于</span>
<span itemprop="about" itemscope itemtype="http://schema.org/Thing">
<a href="/categories/%E7%AE%97%E6%B3%95/" itemprop="url" rel="index"><span itemprop="name">算法</span></a>
</span>
</span>
</div>
</div>
</header>
<div class="post-body" itemprop="articleBody">
<p>常见写代码错误</p>
<ol type="1">
<li>long long 数据非常大的时候！ 再大用 int128</li>
<li>多组数据清空！记得把栈、set也清空</li>
</ol>
<p>哈哈哈哈</p>
</div>
<footer class="post-footer">
<div class="post-eof"></div>
</footer>
</article>
</div>
<div class="post-block">
<article itemscope itemtype="http://schema.org/Article" class="post-content" lang="">
<link itemprop="mainEntityOfPage" href="https://conver334.github.io/2021/03/12/2019icpcnorthwest/">
<span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
<meta itemprop="image" content="/images/conver.jpg">
<meta itemprop="name" content="Conver">
<meta itemprop="description" content="又叒开小号了 ^ _ ^">
</span>
<span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
<meta itemprop="name" content="Conver">
</span>
<header class="post-header">