-
Notifications
You must be signed in to change notification settings - Fork 1
Expand file tree
/
Copy pathindex.html
More file actions
960 lines (723 loc) · 127 KB
/
Copy pathindex.html
File metadata and controls
960 lines (723 loc) · 127 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
<!DOCTYPE html>
<html>
<head><meta name="generator" content="Hexo 3.8.0">
<meta charset="utf-8">
<title>Fish's Blog</title>
<meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
<meta property="og:type" content="website">
<meta property="og:title" content="Fish's Blog">
<meta property="og:url" content="https://li-fish.github.io/index.html">
<meta property="og:site_name" content="Fish's Blog">
<meta property="og:locale" content="zh-Hans">
<meta name="twitter:card" content="summary">
<meta name="twitter:title" content="Fish's Blog">
<link rel="alternate" href="/atom.xml" title="Fish's Blog" type="application/atom+xml">
<link rel="icon" href="/favicon.png">
<link href="//fonts.googleapis.com/css?family=Source+Code+Pro" rel="stylesheet" type="text/css">
<link rel="stylesheet" href="/css/style.css">
</head>
</html>
<body>
<div id="container">
<div id="wrap">
<header id="header">
<div id="banner"></div>
<div id="header-outer" class="outer">
<div id="header-title" class="inner">
<h1 id="logo-wrap">
<a href="/" id="logo">Fish's Blog</a>
</h1>
</div>
<div id="header-inner" class="inner">
<nav id="main-nav">
<a id="main-nav-toggle" class="nav-icon"></a>
<a class="main-nav-link" href="/">Home</a>
<a class="main-nav-link" href="/archives">Archives</a>
</nav>
<nav id="sub-nav">
<a id="nav-rss-link" class="nav-icon" href="/atom.xml" title="RSS Feed"></a>
<a id="nav-search-btn" class="nav-icon" title="Search"></a>
</nav>
<div id="search-form-wrap">
<form action="//google.com/search" method="get" accept-charset="UTF-8" class="search-form"><input type="search" name="q" class="search-form-input" placeholder="Search"><button type="submit" class="search-form-submit"></button><input type="hidden" name="sitesearch" value="https://li-fish.github.io"></form>
</div>
</div>
</div>
</header>
<div class="outer">
<section id="main">
<article id="post-依图研发工程师面试经历" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2019/03/15/cjtk4cs5j007504c2z2js6g54/" class="article-date">
<time datetime="2019-03-15T11:42:51.000Z" itemprop="datePublished">2019-03-15</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/历程/">历程</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2019/03/15/cjtk4cs5j007504c2z2js6g54/">依图研发工程师面试经历</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="一面"><a href="#一面" class="headerlink" title="一面"></a>一面</h1><p>依图是真的只面算法题，感觉回答的不太好，凉凉。</p>
<ul>
<li>先自我介绍一下吧</li>
<li>比赛中印象中比较深的题？</li>
<li>快排、归并、堆排那个快？</li>
<li>基环树找环上的一个点（写代码）。</li>
<li>给出两个非负整数 a 和 b ($a, b \le 10^9$)，进行 $10^{18}$ 次操作，每次操作让小的数变为二倍，并且让大的数变为 a + b - 2 * a (假设 a 为较小的数)。</li>
</ul>
<p>最后一个题知道解法后很简单，考虑最大的那个数做的变化，就是在 a + b 同余系下的乘二运算。</p>
<h1 id="二面"><a href="#二面" class="headerlink" title="二面"></a>二面</h1><p>没想到一面居然过了，之前面试完感觉凉凉，第二个问题疯狂提示才做出来。</p>
<ul>
<li><p>算法题</p>
<ul>
<li><p>N 个数，其中一个只出现一次，其他出现两次，找出出现一次的数。</p>
<p>异或和。</p>
</li>
<li><p>N 个数，其中两个只出现一次，其他出现两次。</p>
<p>异或和后，按二进制的任意一个非零位划分，然后再求异或和。</p>
</li>
</ul>
</li>
<li><p>从 cache 的角度优化矩阵乘法。</p>
<ul>
<li><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></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">mat_mul</span><span class="params">(<span class="keyword">float</span> *A, <span class="keyword">float</span> *B, <span class="keyword">float</span> *C, <span class="keyword">int</span> N)</span> </span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < N; i++) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < N; j++) {</span><br><span class="line"> C[i * N + j] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">0</span>; k < N; k++) {</span><br><span class="line"> C[i * N + j] += A[i * N + k] * B[k * N + j];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
<li><p>考虑访问 B 数组时，下标不是连续访问，进行优化。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">mat_mul</span><span class="params">(<span class="keyword">float</span> *A, <span class="keyword">float</span> *B, <span class="keyword">float</span> *C, <span class="keyword">int</span> N)</span> </span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < N; i++) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j < N; j++) {</span><br><span class="line"> C[i * N + j] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">0</span>; k < N; k++) {</span><br><span class="line"> C[i * N + k] += A[i * N + j] * B[j * N + k];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</li>
<li><p>考虑对于每一个 i 每次要遍历整个 B 数组，如果 cache 不能完整存下整个 B 数组时，cache 命中率可能会比较低。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">mat_mul</span><span class="params">(<span class="keyword">float</span> *A, <span class="keyword">float</span> *B, <span class="keyword">float</span> *C, <span class="keyword">int</span> N)</span> </span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> jj = <span class="number">0</span>; jj < N, jj += BLOCK) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < N; i++) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = jj; j < min(jj + BLOCK, N); j++) {</span><br><span class="line"> C[i * N + j] = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> k = <span class="number">0</span>; k < N; k++) {</span><br><span class="line"> C[i * N + k] += A[i * N + j] * B[j * N + k];</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<p>加入分块优化，每次只计算 B 矩阵的 BLOCK 行对答案的贡献。（这里被面试官疯狂提示才理解）</p>
</li>
</ul>
</li>
<li><p>聊下你的项目吧，你选择聊哪一个？</p>
<p>Web 聊天室，主要用到了多线程，线程间通信，网络编程技术。主要功能是客户端向服务器发送消息，服务器对所有客户端进行广播消息。服务器维护一个消息队列，存储客户端发送的消息，并使用互斥锁保证安全。</p>
<ul>
<li><p>你的服务器大概能承载多少用户，如何扩大承载量？</p>
<p>我认为关键要优化服务器中的消息队列，多个线程对同一个元素进行互斥访问的效率特别差，我们考虑对每一个客户端开一个消息队列进行优化。（面试官提示了为了保证消息的顺序加一个时间戳比较好）</p>
</li>
<li><p>你认为你这个项目中遇到的最难的问题是什么？</p>
<p>WebSocket 协议的实现，刚开始我以为 WebSocket 协议和 TCP socket 一样，两者可以直接通信，后来才了解到 WebSocket 是一个应用层协议，需要对 TCP 协议进行分组，然后差了许多资料，包括 WebSocket 协议的数据帧，如何从 HTTP 协议升级到 WebSocket 协议等。</p>
</li>
</ul>
</li>
<li><p>我没有问题了，你有问题问我吗？</p>
<ul>
<li>进入公司后，我大概能学到什么东西，公司有什么培养计划？</li>
<li>依图里是不是有好多 ACM 竞赛选手？</li>
</ul>
</li>
</ul>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2019/03/15/cjtk4cs5j007504c2z2js6g54/" data-id="cjtk4cs5j007504c2z2js6g54" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-腾讯-IEG-后台开发面试" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2019/03/07/cjtk4csgc00fy04c20b0udoco/" class="article-date">
<time datetime="2019-03-07T13:04:22.000Z" itemprop="datePublished">2019-03-07</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/历程/">历程</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2019/03/07/cjtk4csgc00fy04c20b0udoco/">腾讯 IEG 后台开发面试</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="一面"><a href="#一面" class="headerlink" title="一面"></a>一面</h1><p>其实前一天就接到了电话，问了一下 ACM 获奖情况，对游戏开发的了解，最后问了一个 interesting 的问题，「王者荣耀怎么实现同步」，因为之前了解过同步机制并且实现过一个状态同步，于是稍微讲了一下，然后当晚在外面吃饭于是说明天下午面试了。</p>
<p>面试官刚开始就直接说了，我这几年几乎都在打 ACM-ICPC 比赛，于是先面数据结构和算法了。</p>
<ul>
<li><p>STL 容器使用过吗，deque 了解吗，他支持在首位插入删除和随机访问，你考虑过怎么实现吗？</p>
<p>我在竞赛中实现过，开一个特别大的数组，并且使用指针指向数组的中央，一个首指针一个尾指针，并且通过首指针加一个偏移量实现随机访问。</p>
</li>
<li><p>当储存空间不够时怎么办？</p>
<p>使用类似于 vector 的方式进行扩容。</p>
</li>
<li><p>如果按你这种方式，如果一直插入到首部，后面的好多空间没有用到，有优化方式吗？</p>
<p>写一个循环队列，例如当首指针达到边界时，让他移到尾部，这样就可以利用全部的存储空间。</p>
</li>
<li><p>考虑游戏服务器的高并发场景，假设这个容器我 push 了许多元素之后又 pop 了许多元素，怎么回收空闲的内存？</p>
<p>因为直接申请一整块内存的话，不容易直接回收部分内存，可以考虑牺牲一部分效率，使用一种块状链表的结构去实现 deque。</p>
</li>
<li><p>那你考虑过可以不使用链表这种结构去实现这个功能吗？</p>
<p>emmm 接下来的问题没有答上来。</p>
</li>
<li><p>考虑有一个定时器，他到达某个时刻的时候会执行某个 callback，假设我现在需要一个容器去储存这些定时器，并且一直要查询有没有定时器需要执行，你会使用什么样的数据结构？</p>
<p>可以用一个小根堆，并且把时间当作 key 来排序，那么堆顶的元素就是时刻最早的，每次可以 $O(1)$ 的查询堆顶。或者使用二叉平衡树也可以实现这个功能，查询是 $O(\log n)$的。</p>
</li>
<li><p>讲一下堆和二叉平衡树的删除操作吧，假设我有一个指向堆 or 平衡二叉树的指针，怎么高效的删除这个节点？</p>
<p>emmm，因为比赛很少遇到这种情况，我只好和面试官讲了下 Splay 这种数据结构…感觉回答的不是很好。</p>
</li>
<li><p>sort 了解过吗，你们比赛中怎么使用 sort，关于他的 < 语义或者比较函数有什么要求吗？</p>
<p>基本上就用 std::sort 了，如果要求稳定排序的话把下标当作第二关键字用就好咯。关于比较函数的要求，数学上是要求定义一个严格的弱序关系，我当时说的是两个条件，可传递，并且非对称，a < b and b < c then a < c, a < b 和 b < a 有且只有一个条件成立。</p>
</li>
<li><p>map 使用过吗，unordered_map 和 map 有什么区别？</p>
<p>map 使用红黑树来实现的，我只了解过各种接口的复杂度，不清楚内部实现。unorder_map 使用哈希表来实现。</p>
</li>
<li><p>你可以自己实现一个 unordered_map 吗，讲一下怎么实现？</p>
<p>最简单的一种实现就是开一个桶，然后用桶的大小对 hash 后的 value 取模，然后放入桶里面。</p>
</li>
<li><p>如果有 hash 碰撞怎么解决？</p>
<p>开一张链表。</p>
</li>
<li><p>如果 hash 碰撞太高了怎么优化？</p>
<p>可以从两方面入手，一个是 hash 函数本身的优化要做好。另外一点面试官提示了我一下，其实就是鸽巢定理，10 个抽屉放 11 个球，那么至少有一个抽屉有两个及以上的球。当我放入 100 个元素到 大小为 10 的 hash 表中，那么是很容易 hash 碰撞的。这时候我考虑了用之前的方法，对桶进行扩容，这里继续沿用 vector 的方式就 ok 了。</p>
</li>
<li><p>你了解过多线程吗，怎么实现一个线程安全的 hash 表？</p>
<p>我了解过互斥锁，可以考虑给每个元素加一个互斥锁。</p>
</li>
<li><p>那我插入时，需要修改一个链表的结构，发生了冲突怎么办？</p>
<p>给每个链表加一个互斥锁…</p>
</li>
<li><p>那我插入的时候，hash 表需要扩容怎么办？</p>
<p>增加一个变量，用来标志当前是否正在扩容，如果扩容就让所有的插入查询操作阻塞。</p>
</li>
<li><p>这样扩容会阻塞掉所有的访问，有更好的做法吗？</p>
<p>可以将扩容的锁放到每个链表上，然后这样扩容时只阻塞掉正在移动的元素。</p>
</li>
<li><p>好的接下来做一个编程题吧，逆转一个字符串？</p>
<p>水题…</p>
</li>
<li><p>逆转单词？ hello world -> world hello</p>
<p>水题，面试官要看如何分割字符串，于是简单的写了一下，被吐槽代码不规范了 orz。</p>
</li>
<li><p>加权随机数？给定一个权重表 [2, 1, 3, 5, 4]，编写一个输入函数 rand_select(weight[])，返回一个 1 - len(weight) 的整数，这个数是随机的，并且保证出现 0, 1, 2 ,3 ,4 , 5 的概率之比为 2, 1, 3, 5, 4。</p>
<p>写了两个做法，思路都是把权重当作一个区间，然后根据权重区间长度不同，random 从总区间长度中选一个数，落到那个区间中，就把那个区间的编号当作随机的答案。</p>
</li>
<li><p>你有什么问题问我吗？</p>
<ul>
<li>假设我能实习的话，我能学到什么内容，在后台开发岗位的话？</li>
<li>我的表现怎么样，有什么不足的地方？</li>
<li>有什么开源项目推荐吗，或者好数推荐？</li>
</ul>
</li>
</ul>
<h1 id="二面"><a href="#二面" class="headerlink" title="二面"></a>二面</h1><p>感觉二面回答的不是很 OK，感觉凉凉的，但是官网上没给挂。</p>
<p>整体面试官问的问题比一面的多，并且贴近底层和基础，节奏也比较快，最后自己被问的有点懵，后面也没问面试官什么问题就结束了。</p>
<ul>
<li><p>vector 怎么实现？</p>
<p>动态申请内存，然后倍增扩容。</p>
</li>
<li><p>考虑过怎么收缩空间吗？</p>
<p>提供一个接口函数，重新分配一块恰好的空间。</p>
</li>
<li><p>如何使用这个 vector 储存不同大小的数据？</p>
<p>vector 不直接储存数据，储存指针。</p>
</li>
<li><p>怎么用你实现的 vector 实现一个 queue ?</p>
<p>queue 不用随机访问，我感觉使用链表来实现比较好，使用两个首尾指针。</p>
</li>
<li><p>sort 算法了解过吗，std::sort 怎么实现的？</p>
<p>因为 quick sort 是平均复杂度比较好，最差情况能退化到 $O(n^2)$，具体 STL 源码我没有看过，了解过他使用多种排序结合的方式，比如对于大区间使用什么排序，小区间怎么排序，并且进行随机化，避免最差情况。</p>
</li>
<li><p>C++ 了解吗，我在两个文件中定义了两个完全相同的函数有没有错？</p>
<p>编译不会报错，当链接的时候会发生 redefine 错误。</p>
</li>
<li><p>怎么避免这个错误？</p>
<p>使用命名空间或者 static 关键字。</p>
</li>
<li><p>模板了解过吗？</p>
<p>了解过，但没怎么写过代码（然后面试官不继续问了…其实我想让他问一些的）。</p>
</li>
<li><p>extern 关键字了解过吗？</p>
<p>可以引用其他文件的变量，具体没怎么用过，竞赛一直写的单文件。（然后面试官不问 C++ 了 orz）</p>
</li>
<li><p>操作系统熟悉吗？</p>
<p>熟悉，最近刚看完 CSAPP 感觉收获很多。</p>
</li>
<li><p>解释一下程序如何执行的吧，从命令行输入可执行文件开始。</p>
<p>首先操作系统分配好程序运行的上下文环境，例如虚拟内存、页表、CPU 寄存器、堆栈等，将文件映射到内存中，然后处理器找到程序的入口地址，并且运行，通常刚开始执行第一行代码时发生缺页中断，然后 CPU 将硬盘中数据载入主存中。</p>
</li>
<li><p>可执行文件格式了解过吗？</p>
<p>了解过 Unix 系统的 ELF 文件格式，影响比较深的有可重定向目标文件和可执行目标文件，通常编译后生成可重定向目标文件，链接后生成可执行文件。这两类文件大同小异，内部通常分为许多个段，主要有符号表，程序代码，全局变量等。对于可重定向目标文件，还会有一些需要重定向的变量、代码段。</p>
</li>
<li><p>解释一下链接过程吧？</p>
<p>我认为链接过程就是将许多可重定向文件或静态库文件合并成一个可执行文件的过程，会把各个文件的代码、全局变量等数据段合并到一起。链接过程中会依次扫描每个文件，并且为引用但为定义的代码定位地址。</p>
</li>
<li><p>下面问你一个开放性问题，考虑有 100 个 10 万人的服务器，如何维护一个实时的全服排名？</p>
<p>首先肯定要考虑并行，不能单线程处理所有服务器的访问的。这样我们根据排名划分成不同的数据段，用不同的服务器来维护，并且设置一个容易并行的代理服务器转发请求到下级储存数据的服务器。考虑到并发的话可以继续让服务器分级，直到划分为一个可以接受的程度。</p>
</li>
<li><p>假设有一个人反复改变自己的排名，考虑如何优化？</p>
<p>这个好难啊…（然后面试官直接不问了…感觉应该随便说一下比较好的）</p>
</li>
<li><p>下面问个算法题，给 1000 万个手机号排序？</p>
<p>直接基数排序吧，手机号 11 位的话时间复杂度就是 $O(11 \times 1000)$ 咯。或者插入到字典树中，然后遍历一遍也 ok。</p>
</li>
<li><p>好的我没有其他问题问你了，那….</p>
<p>直接被问的自闭了，这里抢答了，“那，再见”。然后面试官就说了下再见就结束了。（感觉他可能是要说 “那你有什么问题问我吗”）</p>
</li>
</ul>
<h1 id="三面"><a href="#三面" class="headerlink" title="三面"></a>三面</h1><p>隔了两周才接到了电话，面试官说大概只用二十分钟就 ok，然后就直接开始面试了。</p>
<ul>
<li><p>你为什么参加 ACM 竞赛?</p>
<p>一是为了可以和别的学校更更强的人同台竞技，二是本身就喜欢算法和数据结构。</p>
</li>
<li><p>你认为 ACM 竞赛中那些可以应用到工程中？</p>
<p>应该是经典的数据结构和算法吧，对于一个工程的需求，我可以考虑用哪种算法和数据结构，可以实现怎样的时间复杂度和空间复杂度。</p>
</li>
<li><p>你学校课程中比较喜欢那几个?</p>
<p>操作系统和计算机网络。</p>
</li>
<li><p>你认为编译原理中的知识对你有用吗？</p>
<p>我认为我最受用的知识是状态机，在竞赛中就用到了 AC 自动机，SAM 等字符串自动机。另外工程中，服务器 IO 复用可以建立状态机的模型进行编程。</p>
</li>
<li><p>你讲一下从客户端发送一个 TCP 包到 服务器吧。</p>
<p>首先先给需要发送的数据加上 TCP 首部，其中包含端口号、序列号等信息；然后将 TCP 包递交给网络层，网络层会加入 IP 首部，其中包括 IP 地址、校验和等信息；然后通过数据链路层发送出去。</p>
<p>服务器收到数据包后递交给网络层，网络层拆掉 IP 首部，并且进行简单的校验，并且递交给传输层；传输层收到后拆掉 TCP 首部，并且验证数据包的是否正确（损坏、失序等），验证通过后讲数据包递交给对应端口号的程序。</p>
</li>
<li><p>子网掩码和网关了解吗？</p>
<p>解释了一下子网掩码，因为之前都在看运输层，</p>
</li>
<li><p>那聊一下操作系统吧，介绍一下进程和线程吧？</p>
<p>进程是操作系统进行分配资源的基本单位，线程是 CPU 调度的基本单位。（面试官问了一下用户态线程了解吗…直接没听说过）</p>
<p>然后聊了下虚拟内存，进程间通信和线程通信。</p>
</li>
<li><p>总结</p>
<p>面试官就直接说你基础不怎么好，如果我这过了的话，下一次就是 HR 面了。如果来实习的话一定要多看看基础知识，Unix 网络编程和 Unix 环境高级编程不错你可以看一下。剩下如果来的话需要补很多基础知识很费时间。</p>
<p>这两本书正好前几天刚买，面试官说的东西正好是最近刚看的，如果能有实习的话，就安心啃书了。</p>
</li>
</ul>
<h1 id="HR-面"><a href="#HR-面" class="headerlink" title="HR 面"></a>HR 面</h1><ul>
<li>自我介绍一下。</li>
<li>为什么参加 ACM 竞赛？</li>
<li>参加比赛的时候怎么学习？</li>
<li>印象最深的比赛？</li>
<li>聊聊你的项目。</li>
<li>为什么选择我们事业群？</li>
<li>喜欢游戏吗？</li>
<li>个人状况 balbalbala…</li>
<li>你有什么问题问我吗？<ul>
<li>我的岗位大概是什么事业群？</li>
</ul>
</li>
</ul>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2019/03/07/cjtk4csgc00fy04c20b0udoco/" data-id="cjtk4csgc00fy04c20b0udoco" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-吉比特实习面试经历" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2019/02/26/cjtk4cs6m007c04c2hfdnwt9r/" class="article-date">
<time datetime="2019-02-26T07:29:53.000Z" itemprop="datePublished">2019-02-26</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/历程/">历程</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2019/02/26/cjtk4cs6m007c04c2hfdnwt9r/">吉比特实习面试</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="一面"><a href="#一面" class="headerlink" title="一面"></a>一面</h1><p><strong>一定要找一个稳定的网络面试！！！</strong></p>
<p>通过牛客网进行的视频面试，本地测试的时候特别稳定，然后和面试官面试的时候网络就特别差，之后让面试官等了一下才开始的正式面试。</p>
<p>首先面试官先说要自我介绍一下，就说了一下自己的姓名、学校、学院、专业班级之类的，提了下从大一开始打 ACM 的经历。</p>
<p>然后面试官就开始问我 C++ 学的怎么样，我说还可以，然后就开始问对 C++11 了解吗，我提到了比赛中只用到过 auto 关键字和范围 for 遍历，又说了一下智能指针、lambda 表达式只了解过但是没实际用过。</p>
<p>接下来就开始问我智能指针有三种，分别介绍一下他们，这里我忘记了第三种的 weak_prt 了，就直接开始介绍 shared_ptr 和 unique_ptr ，提了下 unique 和 shared 的最大区别在于 unique 不能拷贝，然后面试官问我怎么实现不能拷贝，就是直接把拷贝构造函数和拷贝运算符删掉就 ok 了。</p>
<p>之后我提了一下右值引用（我也忘记是怎么提到的了），然后面试官问我右值引用大概是什么东西，为什么要用得到右值引用。我感觉右值引用就是引用右值吧，介绍了下右值的特点。</p>
<p>之后问了我学校集训队的情况，人数和队内的情况怎么样，自己擅长哪方面的算法之类的。我提到我擅长数据结构、动态规划，然后接下来就给我了一道算法题。</p>
<p>给出一个 n 行 m 列的矩阵，每个位置有 1 或 0，1 代表可以放棋子，0 不能放，任意两个棋子不能相邻放（四连通），问有多少种放的方案。 $n, m < 13$</p>
<p>数据范围这么小，考虑从左上往右下依次放的话，每个棋子只考虑他上方和他左方的棋子就好了，然后考虑转移的话，只需要维护一条轮廓线的状态，大概 $O(n \cdot m \cdot 2^m)$</p>
<p>但是写起来太麻烦了，当时没写出来，和面试官说了一下思路就开始接下来的问题了。</p>
<p>因为我简历中写了一个通过 WebSocket 实现的聊天室，然后面试官问了一下我 WebScoket 协议的工作原理，以及实现方式。使用 WebSocket 协议首先通过发送一个 HTTP 请求将当前协议切换成 WebSocket 协议，大概类似于握手的一个过程，前端我是直接使用的 JavaScript 的 Socket.io 库，后端通过 Python 的 Socket 实现了 WebSocket 协议。</p>
<p>随后问了多线程了解的怎么样，我和他说了一下我上面聊天室项目中多线程的应用，提了下为什么 Python 多线程只对 IO 密集型有用，顺便提了下之前使用多线程优化 Sort。</p>
<p>然后问我编译原理学的好吗，我就直接说考的挺好，但是学的不怎么样，然后就没继续问了。</p>
<p>之后问我对游戏开发感兴趣了，我就聊了一下之前做过一个 H5 的飞机大战游戏，并且看了一下游戏如何实现同步。</p>
<p>最后面试官问我有什么问题问他吗，我就问了他们公司后端开发需要学那些技术，他告诉我他们后端基本上都是自己写的，不用什么框架，甚至开发了自己的一套脚本语言。然后我问了下厦门和深圳那个地方好，薪资啥的。</p>
<h1 id="二面（HR-面）"><a href="#二面（HR-面）" class="headerlink" title="二面（HR 面）"></a>二面（HR 面）</h1><p>很意外这次直接是 HR 面，感觉一般要有个三面甚至到四面才到 HR 面的样子，面试的昨晚我还担心一面的时候没有问多少基础问题，二面的时候会不会着重问很多基础问题，又翻了一晚上书…</p>
<ul>
<li><p>大学期间都在做什么情况，全部都在参加 ACM 比赛吗？</p>
<p>从大一就开始打比赛，一直持续到大三上学期打完最后一个赛季。</p>
</li>
<li><p>你认为参加 ACM 比赛，最大的收获是什么？</p>
<p>我认为最大的收获是锻炼了自己的自学能力，比如好多高级算法都是要自己去翻博客，啃论文。</p>
</li>
<li><p>你当时为什么要参加 ACM 比赛？</p>
<ul>
<li>第一点因为 ACM 是一个竞赛，参加这样一个竞赛，就有很多次机会去和其他高校非常厉害的人去切磋竞争，能够认识到自己的水平和不足。</li>
<li>我喜欢算法和难题，并且在竞赛中能思考并解决一些很有意思的问题。</li>
<li>我喜欢 ACM 集训队的氛围，大家一起讨论难题、学习算法，以及可以认识很多厉害的人。</li>
</ul>
</li>
<li><p>关于你的第一个投票系统，有没有考虑过各种用户需求等？</p>
<p>没有，只是一个简单的 demo。</p>
</li>
<li><p>你喜欢游戏吗，最近在玩什么游戏？</p>
<p>特别喜欢，从小就开始玩……直到现在玩……（省略好多字，讲道理如果和我聊游戏的话，我能聊一上午的）</p>
</li>
<li><p>你大概可以持续工作多长时间？</p>
<p>从暑假开始可以实习，理论上持续多久都可以。</p>
</li>
<li><p>你希望进入一家怎么样的公司？</p>
<p>喜欢公司的办事效率高一些，自己身边的同事都喜欢热爱技术。</p>
</li>
<li><p>有没有投其他公司？</p>
<p>投了，腾讯，头条等。</p>
</li>
<li><p>有没有女朋友？</p>
<p>没有（然后 HR 说就不用考虑异地的问题了）。</p>
</li>
<li><p>你有什么问题问我吗？</p>
<ul>
<li><p>如果我获得实习机会，我会在什么岗位？</p>
</li>
<li><p>至少工作几个月，每周工作时长？</p>
</li>
<li><p>有没有转正机会？</p>
</li>
<li><p>实习工资？</p>
<p>（可能涉及公司信息，以上 HR 回答不写了，感觉实习的时候一定要问清楚上面四个问题）</p>
</li>
</ul>
</li>
</ul>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2019/02/26/cjtk4cs6m007c04c2hfdnwt9r/" data-id="cjtk4cs6m007c04c2hfdnwt9r" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-概率论笔记" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2019/01/15/cjtk4cs7x008804c2md0758yf/" class="article-date">
<time datetime="2019-01-15T02:29:48.000Z" itemprop="datePublished">2019-01-15</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/CS课程/">CS课程</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2019/01/15/cjtk4cs7x008804c2md0758yf/">概率论笔记</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h2 id="01分布"><a href="#01分布" class="headerlink" title="01分布"></a>01分布</h2><p>$$P{X = k} = p^k(1-p)^{1-k}, k=0,1$$</p>
<p>$$E(X) = p$$</p>
<p>$D(X) = p(1 - p)$</p>
<h2 id="二项分布-X-sim-b-n-p"><a href="#二项分布-X-sim-b-n-p" class="headerlink" title="二项分布 $X\sim b(n, p)$"></a>二项分布 $X\sim b(n, p)$</h2><p>$$P(X = k) = \binom{n}{k}p^k(1 - p)^{n - k}, k = 0, 1, 2\cdots n.$$</p>
<p>$E(X) = n p$</p>
<p>$D(X) = np(1 - p) $</p>
<h2 id="泊松分布-X-sim-pi-lambda"><a href="#泊松分布-X-sim-pi-lambda" class="headerlink" title="泊松分布 $X\sim \pi(\lambda)$"></a>泊松分布 $X\sim \pi(\lambda)$</h2><p>$$P(X = k) = \frac{\lambda^ke^{-\lambda}}{k!}, k = 0, 1, 2\cdots$$</p>
<p>$$E(X) = \lambda$$</p>
<p>$$D(X) = \lambda$$</p>
<h2 id="均匀分布-X-sim-U-a-b"><a href="#均匀分布-X-sim-U-a-b" class="headerlink" title="均匀分布 $X\sim U(a, b)$"></a>均匀分布 $X\sim U(a, b)$</h2><p>$$f(x)=\begin{cases}\frac{1}{b-a},&a<x<b \0,&else \end{cases}$$<br>$$E(X)=\frac{a+b}{2}$$<br>$$D(X)=\frac{(b-a)^2}{12}$$<br>$$F(X)=\begin{cases}0,&x<a\\frac{x-a}{b-a},&a\le x<b\1,&x\ge b\end{cases}$$</p>
<h2 id="指数分布"><a href="#指数分布" class="headerlink" title="指数分布"></a>指数分布</h2><p>$$f(x)=\begin{cases}\frac{1}{\theta}e^{-x/\theta},&x>0 \0,&else \end{cases}$$</p>
<p>$$E(X) = \theta$$</p>
<p>$$D(X) = \theta^2$$</p>
<p>$$F(X)=\begin{cases}1-e^{-x/\theta},&x>0\0,&else\end{cases}$$</p>
<h2 id="正态分布-X-sim-mu-sigma-2"><a href="#正态分布-X-sim-mu-sigma-2" class="headerlink" title="正态分布 $X\sim (\mu, \sigma^2)$"></a>正态分布 $X\sim (\mu, \sigma^2)$</h2><p>$f(x) = \frac{1}{\sqrt{2\pi}\sigma}e^{-\frac{(x-\mu)^2}{2\sigma^2}}, -\infty<x<+\infty$</p>
<p>$F(X) = \frac{1}{\sqrt{2\pi}\sigma}\int^x_{-\infty}e^{-\frac{(t-\mu)^2}{2\sigma^2}}\text{d} t$</p>
<p>$E(X) = \mu$</p>
<p>$D(X) = \sigma^2$</p>
<p>$F(X) = P(X \le x) = \Phi(\frac{x-\mu}{\sigma})$</p>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2019/01/15/cjtk4cs7x008804c2md0758yf/" data-id="cjtk4cs7x008804c2md0758yf" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-二维ST表" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2018/11/16/cjtk4cs5d007204c26oslbpd4/" class="article-date">
<time datetime="2018-11-15T20:04:11.000Z" itemprop="datePublished">2018-11-16</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/ACM/">ACM</a>►<a class="article-category-link" href="/categories/ACM/数据结构/">数据结构</a>►<a class="article-category-link" href="/categories/ACM/数据结构/ST表/">ST表</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/11/16/cjtk4cs5d007204c26oslbpd4/">二维ST表</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="ST表"><a href="#ST表" class="headerlink" title="ST表"></a>ST表</h1><p>ST 表可以 $O(N\log N)$ 的预处理一位的区间信息，然后 $O(1)$ 的进行查询。</p>
<p>二维 ST 表类似，可以 $O(nm\log n \log m)$ 的预处理一个二维矩阵的子矩阵信息，并且 $O(1)$ 的查询。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><p>下面拿 <a href="https://cn.vjudge.net/problem/CodeForces-713D" target="_blank" rel="noopener">CF713D</a> 为例，题目需要维护二维的区间最大值。</p>
<p><code>ans[i][j][a][b]</code>的含义为以 $(i, j)$ 为左上角 $(i + 2^a - 1, j + 2^n - 1)$ 为右下角的子矩阵的区间信息。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><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></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><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><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAX = <span class="number">1005</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> INF = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> data[MAX][MAX], dp[MAX][MAX], csum[MAX][MAX], rsum[MAX][MAX];</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n, m;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">solve</span><span class="params">()</span> </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="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j <= m; j++) {</span><br><span class="line"> <span class="keyword">if</span> (data[i][j]) {</span><br><span class="line"> rsum[i][j] += rsum[i - <span class="number">1</span>][j] + <span class="number">1</span>;</span><br><span class="line"> csum[i][j] += csum[i][j - <span class="number">1</span>] + <span class="number">1</span>;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> rsum[i][j] = csum[i][j] = <span class="number">0</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j <= m; j++) {</span><br><span class="line"> dp[i][j] = data[i][j] ? <span class="number">1</span> : <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">if</span> (dp[i - <span class="number">1</span>][j - <span class="number">1</span>]) {</span><br><span class="line"> <span class="keyword">int</span> v = dp[i - <span class="number">1</span>][j - <span class="number">1</span>];</span><br><span class="line"> <span class="keyword">int</span> c = csum[i][j];</span><br><span class="line"> <span class="keyword">int</span> r = rsum[i][j];</span><br><span class="line"> dp[i][j] = min(v + <span class="number">1</span>, min(r, c));</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> low_log[MAX];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> cnt = <span class="number">0</span>, now = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i < MAX; i++) {</span><br><span class="line"> <span class="keyword">if</span> (now * <span class="number">2</span> <= i) cnt++, now *= <span class="number">2</span>;</span><br><span class="line"> low_log[i] = cnt;</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> ans[MAX][MAX][<span class="number">10</span>][<span class="number">10</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">cal</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> x = <span class="number">0</span>; x < <span class="number">10</span>; x++) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> y = <span class="number">0</span>; y < <span class="number">10</span>; y++) {</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="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j <= m; j++) {</span><br><span class="line"> <span class="keyword">if</span> (x + y == <span class="number">0</span>) {</span><br><span class="line"> ans[i][j][<span class="number">0</span>][<span class="number">0</span>] = dp[i][j];</span><br><span class="line"> <span class="keyword">continue</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">int</span> dx = x > <span class="number">0</span> ? (<span class="number">1</span> << (x - <span class="number">1</span>)) : <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">int</span> dy = y > <span class="number">0</span> ? (<span class="number">1</span> << (y - <span class="number">1</span>)) : <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">int</span> ox = max(<span class="number">0</span>, x - <span class="number">1</span>);</span><br><span class="line"> <span class="keyword">int</span> oy = max(<span class="number">0</span>, y - <span class="number">1</span>);</span><br><span class="line"></span><br><span class="line"> <span class="keyword">int</span> A = ans[i][j][ox][oy];</span><br><span class="line"> <span class="keyword">int</span> B = i + dx > n ? <span class="number">0</span> : ans[i + dx][j][ox][oy];</span><br><span class="line"> <span class="keyword">int</span> C = j + dy > m ? <span class="number">0</span> : ans[i][j + dy][ox][oy];</span><br><span class="line"> <span class="keyword">int</span> D = (i + dx > n || j + dy > m) ? <span class="number">0</span> : ans[i + dx][j + dy][ox][oy];</span><br><span class="line"></span><br><span class="line"> ans[i][j][x][y] = max(max(A, B), max(C, D));</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">query</span><span class="params">(<span class="keyword">int</span> x1, <span class="keyword">int</span> y1, <span class="keyword">int</span> x2, <span class="keyword">int</span> y2)</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> px = low_log[x2 - x1 + <span class="number">1</span>];</span><br><span class="line"> <span class="keyword">int</span> py = low_log[y2 - y1 + <span class="number">1</span>];</span><br><span class="line"> <span class="keyword">int</span> dx = (<span class="number">1</span> << px) - <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">int</span> dy = (<span class="number">1</span> << py) - <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">return</span> max(max(ans[x1][y1][px][py], ans[x2 - dx][y1][px][py]),</span><br><span class="line"> max(ans[x1][y2 - dy][px][py], ans[x2 - dx][y2 - dy][px][py]));</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">bool</span> <span class="title">ok</span><span class="params">(<span class="keyword">int</span> mid, <span class="keyword">int</span> x1, <span class="keyword">int</span> y1, <span class="keyword">int</span> x2, <span class="keyword">int</span> y2)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (mid == <span class="number">0</span>) <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line"> <span class="keyword">return</span> query(x1 + mid - <span class="number">1</span>, y1 + mid - <span class="number">1</span>, x2, y2) >= mid;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> init();</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d %d"</span>, &n, &m);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">1</span>; i <= n; i++) {</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">1</span>; j <= m; j++) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &data[i][j]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> solve();</span><br><span class="line"> <span class="keyword">int</span> q;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &q);</span><br><span class="line"> cal();</span><br><span class="line"> <span class="keyword">while</span> (q--) {</span><br><span class="line"> <span class="keyword">int</span> x1, y1, x2, y2;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d %d %d %d"</span>, &x1, &y1, &x2, &y2);</span><br><span class="line"> <span class="keyword">int</span> l = <span class="number">0</span>, r = min(y2 - y1 + <span class="number">1</span>, x2 - x1 + <span class="number">1</span>), ans = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">while</span> (l <= r) {</span><br><span class="line"> <span class="keyword">int</span> mid = (l + r) / <span class="number">2</span>;</span><br><span class="line"> <span class="keyword">if</span> (ok(mid, x1, y1, x2, y2)) {</span><br><span class="line"> l = mid + <span class="number">1</span>;</span><br><span class="line"> ans = mid;</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> r = mid - <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, ans);</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2018/11/16/cjtk4cs5d007204c26oslbpd4/" data-id="cjtk4cs5d007204c26oslbpd4" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-SDUTACM十周年题解（Fish出题部分）" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2018/10/16/cjtk4cs0n005004c2xpsanvay/" class="article-date">
<time datetime="2018-10-15T19:48:54.000Z" itemprop="datePublished">2018-10-16</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/ACM/">ACM</a>►<a class="article-category-link" href="/categories/ACM/命题/">命题</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/10/16/cjtk4cs0n005004c2xpsanvay/">SDUTACM十周年题解（Fish出题部分）</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="区间第K大"><a href="#区间第K大" class="headerlink" title="区间第K大"></a>区间第K大</h1><p>题目完全没有弯，就是区间修改，询问第 K 大。</p>
<p>但是 K 特别小，我们考虑用线段树去维护这个东西，线段树每个节点维护当前区间的前 K 大的数。</p>
<p>首先区间修改操作还是用 Lazy 去做就 OK，打 Lazy 标记的时候把前 K 大的值同时修改，然后我们考虑第 K 大怎么维护。</p>
<p>考虑左右两个区间的信息合并，假设左右区间已经维护了前 K 大的数，那么左右区间合并后的前 K 大的数显然等于这两个区间前 K 大的数降序排序取前 K 个。</p>
<p>然后这个题就做完了，复杂度$O(k\cdot q\cdot \log(n))$</p>
<h2 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><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></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><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><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAX = <span class="number">1e5</span> + <span class="number">100</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> INF = <span class="number">0x3f3f3f3f</span>;</span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Node</span> {</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="keyword">int</span> lazy;</span><br><span class="line"></span><br><span class="line"> Node() {</span><br><span class="line"> lazy = <span class="number">0</span>;</span><br><span class="line"> v = <span class="built_in">vector</span><<span class="keyword">int</span>>();</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">maintain</span><span class="params">(<span class="keyword">int</span> d)</span> </span>{</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">auto</span> &x : v) x += d;</span><br><span class="line"> lazy += d;</span><br><span class="line"> }</span><br><span class="line"></span><br><span class="line"> Node <span class="keyword">operator</span>+(<span class="keyword">const</span> Node &t) {</span><br><span class="line"> Node rst;</span><br><span class="line"> rst.lazy = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">auto</span> x : v) rst.v.push_back(x);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">auto</span> x : t.v) rst.v.push_back(x);</span><br><span class="line"> sort(rst.v.begin(), rst.v.end(), greater<>());</span><br><span class="line"> <span class="keyword">if</span> (rst.v.size() > <span class="number">5</span>) rst.v.erase(rst.v.begin() + <span class="number">5</span>, rst.v.end());</span><br><span class="line"> <span class="keyword">return</span> rst;</span><br><span class="line"> }</span><br><span class="line">} tree[MAX << <span class="number">4</span>];</span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> lson (o<<1)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> rson (o<<1|1)</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MID int m = (l + r) >> 1</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">push_down</span><span class="params">(<span class="keyword">int</span> o)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (!tree[o].lazy) <span class="keyword">return</span>;</span><br><span class="line"> <span class="keyword">int</span> &lazy = tree[o].lazy;</span><br><span class="line"> tree[lson].maintain(lazy);</span><br><span class="line"> tree[rson].maintain(lazy);</span><br><span class="line"> lazy = <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">update</span><span class="params">(<span class="keyword">int</span> o, <span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> ql, <span class="keyword">int</span> qr, <span class="keyword">int</span> v)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (qr < l || r < ql) <span class="keyword">return</span>;</span><br><span class="line"> <span class="keyword">if</span> (ql <= l && r <= qr) {</span><br><span class="line"> tree[o].maintain(v);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> push_down(o);</span><br><span class="line"> MID;</span><br><span class="line"> update(lson, l, m, ql, qr, v);</span><br><span class="line"> update(rson, m + <span class="number">1</span>, r, ql, qr, v);</span><br><span class="line"> tree[o] = tree[lson] + tree[rson];</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function">Node <span class="title">query</span><span class="params">(<span class="keyword">int</span> o, <span class="keyword">int</span> l, <span class="keyword">int</span> r, <span class="keyword">int</span> ql, <span class="keyword">int</span> qr)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (qr < l || r < ql) <span class="keyword">return</span> Node();</span><br><span class="line"> <span class="keyword">if</span> (ql <= l && r <= qr) <span class="keyword">return</span> tree[o];</span><br><span class="line"> push_down(o);</span><br><span class="line"> MID;</span><br><span class="line"> <span class="keyword">return</span> query(lson, l, m, ql, qr) + query(rson, m + <span class="number">1</span>, r, ql, qr);</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> A[MAX];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">build</span><span class="params">(<span class="keyword">int</span> o, <span class="keyword">int</span> l, <span class="keyword">int</span> r)</span> </span>{</span><br><span class="line"> tree[o] = Node();</span><br><span class="line"> <span class="keyword">if</span> (l == r) {</span><br><span class="line"> tree[o].v.push_back(A[l]);</span><br><span class="line"> <span class="keyword">return</span>;</span><br><span class="line"> }</span><br><span class="line"> MID;</span><br><span class="line"> build(lson, l, m);</span><br><span class="line"> build(rson, m + <span class="number">1</span>, r);</span><br><span class="line"> tree[o] = tree[lson] + tree[rson];</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> n, q;</span><br><span class="line"> <span class="keyword">while</span> (~<span class="built_in">scanf</span>(<span class="string">"%d %d"</span>, &n, &q)) {</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">"%d"</span>, A + i);</span><br><span class="line"> build(<span class="number">1</span>, <span class="number">1</span>, n);</span><br><span class="line"> <span class="keyword">while</span> (q--) {</span><br><span class="line"> <span class="keyword">int</span> o, l, r, v;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d %d %d %d"</span>, &o, &l, &r, &v);</span><br><span class="line"> <span class="keyword">if</span> (o == <span class="number">1</span>) update(<span class="number">1</span>, <span class="number">1</span>, n, l, r, v);</span><br><span class="line"> <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, query(<span class="number">1</span>, <span class="number">1</span>, n, l, r).v[v - <span class="number">1</span>]);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h1 id="QAQ子串"><a href="#QAQ子串" class="headerlink" title="QAQ子串"></a>QAQ子串</h1><p>我们考虑至少包含 QAQ 的子串比较难求，所以我们反过来考虑，求不包含 QAQ 子串的字符串。</p>
<p>那么这是一个常见的动态规划问题。</p>
<p>我们定义 $dp[i][j]$的含义长度为 $i$，并且结尾的状态为 $j$ 的方案数。</p>
<p>定义状态 $0$ 为不构成 QAQ 任何前缀的结尾，比如 “QAAA”、“bLue”、“UMR” 等。</p>
<p>定义状态 $1$ 为以 Q 字符为结尾，比如 “QWQ”、“QvQ” 等。</p>
<p>定义状态 $2$ 为以 “QA” 为结尾，比如 AQA”，“AQQA” 等。</p>
<p>状态 $0$ 可由状态 $0$ 或状态 ‘2’ 加上任意非 ‘Q’ 的字符转移而来，或由状态 $1$ 加上任意非 ‘Q’ 且非 ‘A’ 的字符转移而来。</p>
<p>状态 $1$ 可由状态 $0$ 或状态 $1$ 加上 ‘Q’ 字符转移而来。</p>
<p>状态 2 仅有状态 1 加上 ‘A’ 转移而来。</p>
<p>即</p>
<p>$dp[i][0] = 25\times dp[i - 1][0] + 24 \times dp[i - 1][1] + 25\times dp[i - 1][2]$</p>
<p>$dp[i][1] = dp[i - 1][0] + dp[i - 1][1]$</p>
<p>$dp[i][2] = dp[i][1]$</p>
<p>初始值 $dp[i][0] = 1, dp[i][1] = dp[i][2] = 0$</p>
<h2 id="代码-1"><a href="#代码-1" class="headerlink" title="代码"></a>代码</h2><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br></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><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><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">long</span> <span class="keyword">long</span> ll;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAX = <span class="number">1e5</span> + <span class="number">100</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MOD = <span class="number">1e9</span> + <span class="number">7</span>;</span><br><span class="line"></span><br><span class="line">ll dp[MAX][<span class="number">3</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(ll &x, ll y)</span> </span>{</span><br><span class="line"> x = (x + y) % MOD;</span><br><span class="line">}</span><br><span class="line"></span><br><span class="line">ll cnt[MAX];</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"> dp[<span class="number">0</span>][<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"> cnt[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < <span class="number">1e5</span>; i++) {</span><br><span class="line"> cnt[i + <span class="number">1</span>] = cnt[i] * <span class="number">26</span> % MOD;</span><br><span class="line"> add(dp[i + <span class="number">1</span>][<span class="number">0</span>], dp[i][<span class="number">0</span>] * <span class="number">25</span>);</span><br><span class="line"> add(dp[i + <span class="number">1</span>][<span class="number">0</span>], dp[i][<span class="number">1</span>] * <span class="number">24</span>);</span><br><span class="line"> add(dp[i + <span class="number">1</span>][<span class="number">0</span>], dp[i][<span class="number">2</span>] * <span class="number">25</span>);</span><br><span class="line"></span><br><span class="line"> add(dp[i + <span class="number">1</span>][<span class="number">1</span>], dp[i][<span class="number">0</span>]);</span><br><span class="line"> add(dp[i + <span class="number">1</span>][<span class="number">1</span>], dp[i][<span class="number">1</span>]);</span><br><span class="line"></span><br><span class="line"> add(dp[i + <span class="number">1</span>][<span class="number">2</span>], dp[i][<span class="number">1</span>]);</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">while</span> (~<span class="built_in">scanf</span>(<span class="string">"%d"</span>, &n)) {</span><br><span class="line"> ll ans = (cnt[n] - (dp[n][<span class="number">0</span>] + dp[n][<span class="number">1</span>] + dp[n][<span class="number">2</span>]) % MOD + MOD) % MOD;</span><br><span class="line"></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><br></pre></td></tr></table></figure>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2018/10/16/cjtk4cs0n005004c2xpsanvay/" data-id="cjtk4cs0n005004c2xpsanvay" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-LCT-模板-待填坑" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2018/09/25/cjtk4crwi003804c2q1itznvs/" class="article-date">
<time datetime="2018-09-25T13:02:34.000Z" itemprop="datePublished">2018-09-25</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/ACM/">ACM</a>►<a class="article-category-link" href="/categories/ACM/数据结构/">数据结构</a>►<a class="article-category-link" href="/categories/ACM/数据结构/LCT/">LCT</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/09/25/cjtk4crwi003804c2q1itznvs/">LCT(模板-待填坑)</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="题目链接："><a href="#题目链接：" class="headerlink" title="题目链接："></a>题目链接：</h1><p><a href="https://www.lydsy.com/JudgeOnline/problem.php?id=2002" target="_blank" rel="noopener">bzoj2002</a></p>
<h1 id="题目大意："><a href="#题目大意：" class="headerlink" title="题目大意："></a>题目大意：</h1><p>某天，Lostmonkey发明了一种超级弹力装置，为了在他的绵羊朋友面前显摆，他邀请小绵羊一起玩个游戏。游戏一开始，Lostmonkey在地上沿着一条直线摆上n个装置，每个装置设定初始弹力系数ki，当绵羊达到第i个装置时，它会往后弹ki步，达到第i+ki个装置，若不存在第i+ki个装置，则绵羊被弹飞。绵羊想知道当它从第i个装置起步时，被弹几次后会被弹飞。为了使得游戏更有趣，Lostmonkey可以修改某个弹力装置的弹力系数，任何时候弹力系数均为正整数。</p>
<p>第一行包含一个整数n，表示地上有n个装置，装置的编号从0到n-1,接下来一行有n个正整数，依次为那n个装置的初始弹力系数。第三行有一个正整数m，接下来m行每行至少有两个数i、j，若i=1，你要输出从j出发被弹几次后被弹飞，若i=2则还会再输入一个正整数k，表示第j个弹力装置的系数被修改成k。对于20%的数据n,m<=10000，对于100%的数据n<=200000,m<=100000</p>
<h1 id="题目分析："><a href="#题目分析：" class="headerlink" title="题目分析："></a>题目分析：</h1><h1 id="AC代码："><a href="#AC代码：" class="headerlink" title="AC代码："></a>AC代码：</h1><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br></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><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><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAX = <span class="number">212345</span>;</span><br><span class="line"> </span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Node</span> {</span></span><br><span class="line"> <span class="keyword">int</span> fa, son[<span class="number">2</span>];</span><br><span class="line"> <span class="keyword">int</span> siz;</span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> &<span class="title">l</span><span class="params">()</span> </span>{ <span class="keyword">return</span> son[<span class="number">0</span>]; }</span><br><span class="line"> <span class="function"><span class="keyword">inline</span> <span class="keyword">int</span> &<span class="title">r</span><span class="params">()</span> </span>{ <span class="keyword">return</span> son[<span class="number">1</span>]; }</span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">()</span> </span>{</span><br><span class="line"> fa = son[<span class="number">0</span>] = son[<span class="number">1</span>] = <span class="number">0</span>;</span><br><span class="line"> siz = <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">maintain</span><span class="params">()</span></span>;</span><br><span class="line">} node[MAX];</span><br><span class="line"> </span><br><span class="line"><span class="keyword">void</span> Node::maintain() {</span><br><span class="line"> siz = <span class="number">1</span> + node[l()].siz + node[r()].siz;</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ori</span><span class="params">(<span class="keyword">int</span> st)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (node[st].fa < <span class="number">0</span>) <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">return</span> st == node[node[st].fa].r();</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">f</span><span class="params">(<span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> <span class="keyword">return</span> node[x].fa;</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">setc</span><span class="params">(<span class="keyword">int</span> st, <span class="keyword">int</span> sn, <span class="keyword">int</span> d)</span> </span>{</span><br><span class="line"> <span class="keyword">if</span> (st > <span class="number">0</span>) {</span><br><span class="line"> node[st].son[d] = sn;</span><br><span class="line"> node[st].maintain();</span><br><span class="line"> }</span><br><span class="line"> <span class="keyword">if</span> (sn > <span class="number">0</span>) node[sn].fa = st;</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">zg</span><span class="params">(<span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> st = f(x);</span><br><span class="line"> <span class="keyword">int</span> p = f(st);</span><br><span class="line"> <span class="keyword">int</span> d = ori(x), dst = ori(st);</span><br><span class="line"> setc(st, node[x].son[d^<span class="number">1</span>], d);</span><br><span class="line"> setc(x, st, d^<span class="number">1</span>);</span><br><span class="line"> setc(p, x, dst);</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">splay</span><span class="params">(<span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> <span class="keyword">while</span> (f(x) > <span class="number">0</span>) {</span><br><span class="line"> <span class="keyword">if</span> (f(f(x)) <= <span class="number">0</span>) zg(x);</span><br><span class="line"> <span class="keyword">else</span> {</span><br><span class="line"> <span class="keyword">if</span> (ori(x) == ori(f(x))) zg(f(x));</span><br><span class="line"> <span class="keyword">else</span> zg(x);</span><br><span class="line"> zg(x);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">access</span><span class="params">(<span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> splay(x);</span><br><span class="line"> <span class="keyword">while</span> (node[x].fa < <span class="number">0</span>) {</span><br><span class="line"> <span class="keyword">int</span> fa = -node[x].fa;</span><br><span class="line"> splay(fa);</span><br><span class="line"> node[node[fa].r()].fa *= <span class="number">-1</span>;</span><br><span class="line"> setc(fa, x, <span class="number">1</span>);</span><br><span class="line"> splay(x);</span><br><span class="line"> }</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">findroot</span><span class="params">(<span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> access(x);</span><br><span class="line"> <span class="keyword">while</span> (node[x].l()) x = node[x].l();</span><br><span class="line"> splay(x);</span><br><span class="line"> <span class="keyword">return</span> x;</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">link</span><span class="params">(<span class="keyword">int</span> st, <span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> access(x);</span><br><span class="line"> node[x].fa = -st;</span><br><span class="line"> access(x);</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">cut</span><span class="params">(<span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> access(x);</span><br><span class="line"> node[node[x].l()].fa = <span class="number">0</span>;</span><br><span class="line"> node[x].son[<span class="number">0</span>] = <span class="number">0</span>;</span><br><span class="line">}</span><br><span class="line"> </span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="keyword">int</span> n, m;</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &n);</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i <= n; i++) node[i].init();</span><br><span class="line"> node[<span class="number">0</span>].siz = <span class="number">0</span>;</span><br><span class="line"> </span><br><span class="line"> <span class="keyword">int</span> x;</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>, &x);</span><br><span class="line"> <span class="keyword">if</span> (i + x <= n) link(i + x, i);</span><br><span class="line"> }</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &m);</span><br><span class="line"> <span class="keyword">int</span> ord, v;</span><br><span class="line"> <span class="keyword">while</span> (m--) {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d %d"</span>, &ord, &x);</span><br><span class="line"> x++;</span><br><span class="line"> <span class="keyword">if</span> (ord == <span class="number">1</span>) {</span><br><span class="line"> access(x);</span><br><span class="line"> <span class="built_in">printf</span>(<span class="string">"%d\n"</span>, node[node[x].l()].siz + <span class="number">1</span>);</span><br><span class="line"> } <span class="keyword">else</span> {</span><br><span class="line"> <span class="built_in">scanf</span>(<span class="string">"%d"</span>, &v);</span><br><span class="line"> cut(x);</span><br><span class="line"> <span class="keyword">if</span> (x + v <= n) link(x + v, x);</span><br><span class="line"> }</span><br><span class="line"> }</span><br><span class="line">}</span><br></pre></td></tr></table></figure>
<h1 id="解题过程："><a href="#解题过程：" class="headerlink" title="解题过程："></a>解题过程：</h1>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2018/09/25/cjtk4crwi003804c2q1itznvs/" data-id="cjtk4crwi003804c2q1itznvs" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-回文树模板" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2018/09/11/cjtk4cs75007k04c2mrff7ao7/" class="article-date">
<time datetime="2018-09-11T13:29:48.000Z" itemprop="datePublished">2018-09-11</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/ACM/">ACM</a>►<a class="article-category-link" href="/categories/ACM/字符串/">字符串</a>►<a class="article-category-link" href="/categories/ACM/字符串/回文树/">回文树</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/09/11/cjtk4cs75007k04c2mrff7ao7/">回文树模板</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="参考资料"><a href="#参考资料" class="headerlink" title="参考资料"></a>参考资料</h1><p><a href="https://blog.csdn.net/u013368721/article/details/42100363" target="_blank" rel="noopener">一篇特别棒的博客</a></p>
<h1 id="回文树"><a href="#回文树" class="headerlink" title="回文树"></a>回文树</h1><p>回文树又叫回文自动机，算是和 AC 自动机、后缀自动机、KMP 相似的算法。</p>
<p>首先有这样一个定理，一个字符串的不同的回文子串的数量和字符串的长度是同阶的。</p>
<p>回文树上的每一个节点储存的是一个原字符串的回文子串，并且他像 AC 自动机一样有 fail 指针和转移边，一个节点的父亲表示的回文串是当前节点表示的回文串的子串。fail 指针指向的是当前节点表示的回文串的最长回文子串，并且这个回文子串同时是他的前缀和后缀，并且不是他本身。</p>
<h1 id="BZOJ-3676"><a href="#BZOJ-3676" class="headerlink" title="BZOJ 3676"></a>BZOJ 3676</h1><p><a href="https://www.lydsy.com/JudgeOnline/problem.php?id=3676" target="_blank" rel="noopener">题目链接</a></p>
<p>考虑一个只包含小写拉丁字母的字符串s。我们定义s的一个子串t的“出<br>现值”为t在s中的出现次数乘以t的长度。请你求出s的所有回文子串中的最<br>大出现值。 </p>
<p>数据满足1≤字符串长度≤300000。</p>
<h1 id="代码"><a href="#代码" class="headerlink" title="代码"></a>代码</h1><figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br></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><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> MAX = <span class="number">512345</span>;</span><br><span class="line"><span class="keyword">const</span> <span class="keyword">int</span> ALP = <span class="number">26</span>;</span><br><span class="line"> </span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Palindromic_Tree</span> {</span></span><br><span class="line"> <span class="keyword">int</span> son[MAX][ALP]; <span class="comment">//转移边</span></span><br><span class="line"> <span class="keyword">int</span> fail[MAX]; <span class="comment">//fail 指针</span></span><br><span class="line"> <span class="keyword">int</span> cnt[MAX]; <span class="comment">//当前节点表示的回文串在原串中出现了多少次</span></span><br><span class="line"> <span class="keyword">int</span> num[MAX]; <span class="comment">//当前节点 fail 可以向前跳多少次</span></span><br><span class="line"> <span class="keyword">int</span> len[MAX]; <span class="comment">//当前节点表示的回文串的长度</span></span><br><span class="line"> <span class="keyword">int</span> S[MAX]; <span class="comment">//插入的字符串</span></span><br><span class="line"> <span class="keyword">int</span> last; <span class="comment">//最后一次访问到的节点，类似 SAM</span></span><br><span class="line"> <span class="keyword">int</span> n; <span class="comment">//插入的字符串长度</span></span><br><span class="line"> <span class="keyword">int</span> p; <span class="comment">//自动机的总状态数</span></span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">int</span> <span class="title">newnode</span><span class="params">(<span class="keyword">int</span> l)</span> </span>{</span><br><span class="line"> <span class="built_in">memset</span>(son[p], <span class="number">0</span>, <span class="keyword">sizeof</span>(son[p]));</span><br><span class="line"> cnt[p] = <span class="number">0</span>;</span><br><span class="line"> num[p] = <span class="number">0</span>;</span><br><span class="line"> len[p] = l;</span><br><span class="line"> <span class="keyword">return</span> p++;</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">init</span><span class="params">()</span> </span>{</span><br><span class="line"> p = <span class="number">0</span>;</span><br><span class="line"> newnode(<span class="number">0</span>);</span><br><span class="line"> newnode(<span class="number">-1</span>);</span><br><span class="line"> last = <span class="number">0</span>;</span><br><span class="line"> n = <span class="number">0</span>;</span><br><span class="line"> S[n] = <span class="number">-1</span>;</span><br><span class="line"> fail[<span class="number">0</span>] = <span class="number">1</span>;</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">int</span> <span class="title">get_fail</span><span class="params">(<span class="keyword">int</span> x)</span> </span>{</span><br><span class="line"> <span class="keyword">while</span> (S[n - len[x] - <span class="number">1</span>] != S[n]) x = fail[x];</span><br><span class="line"> <span class="keyword">return</span> x;</span><br><span class="line"> }</span><br><span class="line"> </span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">add</span><span class="params">(<span class="keyword">int</span> c)</span> </span>{</span><br><span class="line"> c -= <span class="string">'a'</span>;</span><br><span class="line"> S[++n] = c;</span><br><span class="line"> <span class="keyword">int</span> cur = get_fail(last); <span class="comment">//通过上一次访问的位置去扩展</span></span><br><span class="line"> <span class="keyword">if</span> (!son[cur][c]) { <span class="comment">//如果没有对应的节点添加一个新节点</span></span><br><span class="line"> <span class="keyword">int</span> now = newnode(len[cur] + <span class="number">2</span>);</span><br><span class="line"> fail[now] = son[get_fail(fail[cur])][c]; <span class="comment">//通过当前节点的 fail 去扩展出新的 fail</span></span><br><span class="line"> son[cur][c] = now;</span><br><span class="line"> num[now] = num[fail[now]] + <span class="number">1</span>; <span class="comment">//记录 fail 跳多少次</span></span><br><span class="line"> }</span><br><span class="line"> last = son[cur][c];</span><br><span class="line"> cnt[last]++; <span class="comment">//表示当前节点访问了一次</span></span><br><span class="line"> }</span><br><span class="line"> <span class="function"><span class="keyword">void</span> <span class="title">count</span><span class="params">()</span> </span>{</span><br><span class="line"> <span class="comment">//如果某个节点出现一次，那么他的 fail 也一定会出现一次，并且在插入的时候没有计数</span></span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = p - <span class="number">1</span>; i >= <span class="number">0</span>; i--) cnt[fail[i]] += cnt[i];</span><br><span class="line"> }</span><br><span class="line">} AUT;</span><br><span class="line"> </span><br><span class="line"><span class="keyword">char</span> data[MAX];</span><br><span class="line"><span class="keyword">int</span> n;</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">"%s"</span>, data);</span><br><span class="line"> n = <span class="built_in">strlen</span>(data);</span><br><span class="line"> AUT.init();</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < n; i++) AUT.add(data[i]);</span><br><span class="line"> AUT.count();</span><br><span class="line"> <span class="keyword">long</span> <span class="keyword">long</span> ans = <span class="number">0</span>;</span><br><span class="line"> <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i < AUT.p; i++) {</span><br><span class="line"> ans = max(ans, <span class="number">1l</span>l * AUT.len[i] * AUT.cnt[i]);</span><br><span class="line"> }</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></pre></td></tr></table></figure>
<p> </p>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2018/09/11/cjtk4cs75007k04c2mrff7ao7/" data-id="cjtk4cs75007k04c2mrff7ao7" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-2018年暑假集训" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2018/09/04/cjtk4csfg00fr04c2qiectjbg/" class="article-date">
<time datetime="2018-09-04T10:48:35.000Z" itemprop="datePublished">2018-09-04</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/历程/">历程</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/09/04/cjtk4csfg00fr04c2qiectjbg/">2018年暑假集训（应付学校社会实践）</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="一、时间内容"><a href="#一、时间内容" class="headerlink" title="一、时间内容"></a>一、时间内容</h1><p>2018 年暑假，山东理工大学信息楼，2018 年 7 月 29 日至 2018 年 8 月 30 日，共记 33 天，评价每天 8 小时，约 33 × 8 = 264 小时。</p>
<p>主要以学习算法提高自己的能力为目的，另外要负责17级新生的训练计划安排和辅导工作。</p>
<h1 id="二、体验和经历"><a href="#二、体验和经历" class="headerlink" title="二、体验和经历"></a>二、体验和经历</h1><p>不出意外的话应该是最后一次参加的 ACM 集训了，集训后接下来就要参加下半年的 ICPC 区域赛和 CCPC 了，经过前两年的学习，这次集训的内容基本上是查缺补漏和学习一些比较难的算法了。</p>
<p>首先经过 14 级的学长指导，需要学一下后缀自动机、虚树、Link-Cut-Tree 等算法。</p>
<h2 id="后缀自动机"><a href="#后缀自动机" class="headerlink" title="后缀自动机"></a>后缀自动机</h2><p>后缀自动机首先是一类自动机，他可以识别一个串的所有子串。自动机上的每一个节点表示着一个状态，但是又不像 AC 自动机那样，每个节点记录着一个前缀。后缀自动机的每个节点维护的是一个整数的集合，可以叫做<strong>子串的结束位置集合</strong>。</p>
<p>例如字符串 <code>S = "aabbabd"</code> ，那么对于子串 <code>"ab"</code> 的结束位置集合就是 <code>{3, 6}</code>。</p>
<p>后缀自动机将结束位置集合相同的子串归于一个等价类中，并只在自动机上表示为一个状态，有证明给出，这样自动机上的状态数是和字符串的长度同阶的。</p>
<p>接下来就是需要考虑后缀自动机如何识别一个字符串，给出一个字符串，需要从后缀自动机的初始状态开始转移，依次添加一个新的字符，如果转移中添加了一个新的字符串但是没有对应的状态，那么这个字符串是后缀自动机识别不了的，也就是说这个字符串不是字符串 S 的子串。</p>
<p>后缀自动机还有诸多的性质，例如如果沿着 Parents 边走的话，Right 集合会不断的合并变大，Parents 上方节点能表示的字符串均是下面字符串的一个后缀等…</p>
<h2 id="虚树"><a href="#虚树" class="headerlink" title="虚树"></a>虚树</h2><p>据说虚树的英文是叫 Auxiliary tree，简单的来说是维护树上仅于题目有关的信息，除去掉冗余信息以保证时间复杂度的一种算法。为什么说是虚树呢，是因为他是在原来树的基础上建出的一颗全新的树，需要重新建边或分配点权等信息。</p>
<p>虚树的题目通常是这样的，给出一颗大小为 n 有边权或点权的树，然后有 q 次询问，每次给出 $k_i$ 个关键点，要求计算关于这 k 个点的问题（通常和 LCA 有关），但是 $\sum k_i$ 又比较小（通常和树的大小同阶）。</p>
<p>假设你可以 $O(n)$ 的在树上解决单次的询问，那么总时间复杂度是 $O(nq)$ 的，问题的 n 和 q 一般为 $10^5$ 显然这样是不可以过这道题的。这时候就需要用到虚树了，使用虚树我们对于每个询问都可以 $O(k_i)$ 的建出一颗有 $O(k_i)$ 个节点的树，并且可以通过这棵树 $O(k_i)$ 的计算出答案。</p>
<h2 id="Link-Cut-Tree"><a href="#Link-Cut-Tree" class="headerlink" title="Link-Cut-Tree"></a>Link-Cut-Tree</h2><p>LCT（Link-Cut-Tree） 又叫动态树，支持让一颗树删除一条边分裂成两颗树，或者两棵树合并成一颗树，并且维护一条链或子树的信息。</p>
<p>LCT 和树链剖分差不多，树链剖分大概是将一棵树划分成若干条链，然后对每条链映射成连续的区间，就可以用线段树去维护每条链的区间信息。LCT 也是把一棵树拆成若干条链来维护，不过 LCT 是直接把一条链用一颗 Splay 当做一个序列来维护，序列按照节点的深度当做关键字排序。</p>
<p>LCT 主要支持三种操作，Access 操作，将一个节点 u 到根节点的路打通（类比树链剖分里的重链），并且将 u 节点设置为其所在的 Splay 的根。Link 操作，将 u 设置成 v 的儿子，先 Access u，给 u 加一条虚边到 v，然后 Access u。Cut 操作，将一个节点 u 和其父亲断开，先 Access u，然后断开 u 与其左儿子的连接，再 Access u。</p>
<p>有证明给出，LCT 的每一个操作都是 $O(\log n)$ 的。</p>
<p>接下来说一下前半年参加的比赛的总结。</p>
<h2 id="CCCC-天梯赛"><a href="#CCCC-天梯赛" class="headerlink" title="CCCC 天梯赛"></a>CCCC 天梯赛</h2><p>感觉一直是一项以考察基本数据结构为主的比赛，今年比赛缩水了一下，没有选拔赛直接只有一场决赛了。老师说按照 SDUT 的经验每次都是初赛打的不太好，然后决赛打的不错。不过这次没有初赛，于是决赛相比前几年打的不怎么好。</p>
<p>比赛是在青岛的中国石油大学进行，不得不说中石油的校区环境是真的不错，不过这次不像区域赛那样有个热身赛之类的，所以当天去当天就回学校了，少了几分乐趣。中石油提供伙食的自助餐厅是真的棒，饭菜样式多，肉菜多，又挺好吃的，中午吃饭的时候老师在催要去比赛了我们还在吃…</p>
<p>比赛不知道为什么，前一个半小时整个机房的电脑都不能正常上比赛的网址，本来时间就不太充裕，先锋奖励肯定是放弃了，只能用剩下时间去尽可能的做了会做的题目…</p>
<p>和往届一样，前面几道题都是基础题，大概程序设计基础的难度，后面几道也就涉及到并查集这种基本的数据结构，比赛的核心是考察代码能力，做起来根本不用动脑子，这一点和 ICPC、CCPC、Codeforces 之类的比赛非常不同。然后后面几道题有特别难，一道是写一个格式化代码的程序，一道是一个非常难的字符串题，另外一个是计算几何。基本上也都能写一个暴力程序骗不少分。</p>
<p>最后好像是 226 分滚粗（去年都能打到 236），感觉难题是比去年难，简单题也都没什么感觉，也算是尽力了。</p>
<h2 id="山东省省赛"><a href="#山东省省赛" class="headerlink" title="山东省省赛"></a>山东省省赛</h2><p>首先先看的 C，标准的签到题，让队友敲的，结果 WA 了两次才 A，可以说是开局非常爆炸了，于是导致我后面交题也不怎么看罚时了（不知道算不算什么破釜沉舟背水一战），想着只能靠题数取胜了。</p>
<p>然后看的 B，理解错了题意，正确的题意是符合贪心性质的，可以写贪心，我大概是做了个 Hard Version，写了个最小费用流，非常熟练的抄完自己总结的板子，保存边的数量的变量没初始化 RE 了一发，然后由于不考虑罚时，于是改完就立刻交了一发就 A 了。</p>
<p>在我写 B 的时候队友就已经在看 F 题了（数据出错的那个题），等我写完他告诉了我一下容斥的做法，我觉得没什么问题就开始敲了，不过写的过程中感觉非常难写…看到榜单上 6 分钟就 AC 的，怀疑自己的做法是不是不对…然后让队友写了个对拍自己去重新想了一下思路，发现还是得写容斥，于是回来继续写，写完后又对拍了几组数据改了改就交了，然后肯定是 A 的，最后也不知道这个题有没有写对 ORZ</p>
<p>这时候另一个队友一直在读题，我敲完一道题基本上就可以接着看下一道题了，这时候一个队友在想 E 题，我去写 G 题，然后一眼看过去就是 NIM 博弈加 DP 记录方案数，不过这里数据越界改了好几次才过，不过改完一次就交一次不在乎罚时，所幸改的还算快。</p>
<p>在我改 G 题的时候让队友敲了下 E 题，NlogN 的复杂度 TLE 了，感觉必须得线性的算法才能过，这时候封榜还有半个小时，榜上已经有六题的了，于是决定让队友去其他的题了（B 和 D），然后我考虑这个题的答案限制条件比较少，应该用不到队友敲得逆序数之类的，于是正好我们都想到单调队列，于是先写了个单调队列，然后测了下样例对了，要交的时候还是不放心，因为如果这个 WA 的话我不能确定是算法错了还是代码细节错了，于是让队友出了下样例果然错了，后来多考虑了一个条件就 OK 了，然后提交 AC。</p>
<p>这时候队友说 B 题有思路了，不过是图论题还是让我敲，我一直感觉 1e8 的时间复杂度过不去，于是先让队友把板子抄上，然后自己想了下细节怎么处理，感觉没问题之后就开始上手做了，写完 debug 了 20 多分钟，队友板子抄错了两个地方，改完过了另一个队友出的特别强的样例（反转他说是比较强），提交就 AC 了。</p>
<p>这时候比赛结束还有四十分钟，榜上已经有七题的队伍了，加上我们罚时比较高，夺冠要在这 40 分钟 A 两题感觉希望不太大了，有点失望…队友在我写 B 题的时候已经想了下大概的 D 题做法，我问了他一下，感觉加上树链剖分就可以写了，于是拿过来之前直接整理的树链剖分板子就超了起来，心情比较差加上又特别累了，中间电脑还重启耽误了十多分钟，最后还有十分钟结束才写完，总共 200 多行代码，我当时就和队友说，这么长的代码要是不出点 Bug 什么的我都不信，结果运行没编译错误，然后输入样例结果却都是 0 … 非常紧急的改完之后还剩五分钟了，最终居然过了样例，当时 PC ^ 2 显示结束还有三分钟立刻就交了，之后就赶紧看代码还有没有错误。然后看着看着队友说有评测结果了，看了一下返回了一个 Yes，可以说是非常开心了。</p>
<h2 id="西安邀请赛"><a href="#西安邀请赛" class="headerlink" title="西安邀请赛"></a>西安邀请赛</h2><p>首先看的 E 题，很显然的一个几何的结论三分钟 A 了。</p>
<p>然后看的 A 题，猜了个显然不对的做法，WA 一次，然后和 szq 讨论后又写了一个优化版的做法，还是 WA，最后又讨论了下，算是推出来了出题人认为的正解，不过这个题目出错了，在我们推出来正解后讨论区裁判公布了正解。算是可惜了两发罚时，不过裁判组处理也是比较得当，如果不这样的话会有好多有水平的队伍卡在 A 题。</p>
<p>在我敲 A 题的时候 szq 就已经在看 D 题，看上去就是 nim 博弈的变种，推出来 SG 函数就基本上做出来的了，不过他没有打好表，还是我上去记忆化搜索一波后打出来表，规律非常显然，出了个小失误 WA 一发后就 AC 了。</p>
<p>然后 lxw 告诉我了下 B 题（最后也没写出来）的题意后我就去看 K 了，这里我大概敲了一个小时，思路越敲越乱，大概浪费了一个多小时，最后 szq 说他有一个比较简单的做法，我就让开机位去让他敲了，自己去洗了把脸清醒一下…最后 szq 写完调试了半个小时多才 A 掉这个题，算是这次比赛里面最大的失误了。</p>
<p>之前看榜上有好多人过了 G 题，并且 szq 和 lxw 已经讨论出来了这是一个简单的板子题，于是 A 完 K 题后直接去做 G 题了，敲完板子后一直 WA，最后我打印代码让他们两个看，去敲了 C 题，C 题在 szq 敲 K 题的时候我已经和 lxw 讨论的差不多了。</p>
<p>最后实在没找到其他的错误，于是只好试试改精度，然后改完之后 G 题居然 AC 了，随后我敲完 C 题过了样例也顺利 1A 了。</p>
<p>这时候刚好封榜，只有一个小时剩余的时间了，看榜上其他有人做出来的题只有 B 和 H 题，F 题只有 GDUT 穷游中国做出来了，感觉可能比较难，于是就去做 B 题了（后来发现这个是错误选择）。</p>
<p>最后让 lxw 读出来了 H 题的题目，B 和 H 最后也没有思路。</p>
<p>比赛后听他们讨论说封榜前没人过的 I 和 J 题都是数据结构的模板题，感觉自己没看有点可惜。</p>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2018/09/04/cjtk4csfg00fr04c2qiectjbg/" data-id="cjtk4csfg00fr04c2qiectjbg" class="article-share-link">Share</a>
</footer>
</div>
</article>
<article id="post-斜率DP小结" class="article article-type-post" itemscope="" itemprop="blogPost">
<div class="article-meta">
<a href="/2018/09/04/cjtk4cs7h007w04c2octhuvrl/" class="article-date">
<time datetime="2018-09-03T21:11:05.000Z" itemprop="datePublished">2018-09-04</time>
</a>
<div class="article-category">
<a class="article-category-link" href="/categories/ACM/">ACM</a>►<a class="article-category-link" href="/categories/ACM/DP/">DP</a>►<a class="article-category-link" href="/categories/ACM/DP/斜率优化/">斜率优化</a>
</div>
</div>
<div class="article-inner">
<header class="article-header">
<h1 itemprop="name">
<a class="article-title" href="/2018/09/04/cjtk4cs7h007w04c2octhuvrl/">斜率DP小结（待填坑）</a>
</h1>
</header>
<div class="article-entry" itemprop="articleBody">
<h1 id="斜率优化"><a href="#斜率优化" class="headerlink" title="斜率优化"></a>斜率优化</h1>
</div>
<footer class="article-footer">
<a data-url="https://li-fish.github.io/2018/09/04/cjtk4cs7h007w04c2octhuvrl/" data-id="cjtk4cs7h007w04c2octhuvrl" class="article-share-link">Share</a>
</footer>
</div>
</article>
<nav id="page-nav">
<span class="page-number current">1</span><a class="page-number" href="/page/2/">2</a><a class="page-number" href="/page/3/">3</a><span class="space">…</span><a class="page-number" href="/page/15/">15</a><a class="extend next" rel="next" href="/page/2/">Next »</a>
</nav>
</section>
<aside id="sidebar">
<div class="widget-wrap">
<h3 class="widget-title">Categories</h3>
<div class="widget">
<ul class="category-list"><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/">ACM</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/DP/">DP</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/DP/区间DP/">区间DP</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/DP/数位DP/">数位DP</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/DP/斜率优化/">斜率优化</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/DP/树型DP/">树型DP</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/DP/状压DP/">状压DP</a></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/二分/">二分</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/二进制/">二进制</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/命题/">命题</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/图论/">图论</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/图论/2-SAT/">2-SAT</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/图论/匹配/">匹配</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/图论/差分约束/">差分约束</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/图论/最短路/">最短路</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/图论/网络流/">网络流</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/图论/连通性/">连通性</a></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/字符串/">字符串</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/字符串/AC自动机/">AC自动机</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/字符串/后缀数组/">后缀数组</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/字符串/回文树/">回文树</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/字符串/字符串Hash/">字符串Hash</a></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/搜索/">搜索</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/搜索/BFS/">BFS</a></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数学/">数学</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数学/数论/">数论</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数学/矩阵快速幂/">矩阵快速幂</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数学/线性基/">线性基</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数学/高斯消元/">高斯消元</a></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/">数据结构</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/K-D树/">K-D树</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/LCT/">LCT</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/ST表/">ST表</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/Splay/">Splay</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/主席树/">主席树</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/并查集/">并查集</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/栈/">栈</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/树/">树</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/树链剖分/">树链剖分</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/线段树/">线段树</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/数据结构/虚树/">虚树</a></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/模拟/">模拟</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/知识小结/">知识小结</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/计算几何/">计算几何</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/ACM/贪心/">贪心</a></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/categories/CS课程/">CS课程</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/历程/">历程</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/命题/">命题</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/想法/">想法</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/杂物/">杂物</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/游戏/">游戏</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/爬虫-数据处理/">爬虫&数据处理</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/编程语言/">编程语言</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/编程语言/C/">C++</a></li><li class="category-list-item"><a class="category-list-link" href="/categories/编程语言/Java/">Java</a></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/categories/网页设计/">网页设计</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/网页设计/Web服务器/">Web服务器</a></li></ul></li><li class="category-list-item"><a class="category-list-link" href="/categories/音乐/">音乐</a><ul class="category-list-child"><li class="category-list-item"><a class="category-list-link" href="/categories/音乐/乐理/">乐理</a></li></ul></li></ul>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Archives</h3>
<div class="widget">
<ul class="archive-list"><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/03/">March 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/02/">February 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2019/01/">January 2019</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/11/">November 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/10/">October 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/09/">September 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/05/">May 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/03/">March 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/02/">February 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2018/01/">January 2018</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/12/">December 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/11/">November 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/10/">October 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/09/">September 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/08/">August 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/07/">July 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/06/">June 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/05/">May 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/04/">April 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/03/">March 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/02/">February 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2017/01/">January 2017</a></li><li class="archive-list-item"><a class="archive-list-link" href="/archives/2016/12/">December 2016</a></li></ul>
</div>
</div>
<div class="widget-wrap">
<h3 class="widget-title">Recent Posts</h3>
<div class="widget">
<ul>
<li>
<a href="/2019/03/15/cjtk4cs5j007504c2z2js6g54/">依图研发工程师面试经历</a>
</li>
<li>
<a href="/2019/03/07/cjtk4csgc00fy04c20b0udoco/">腾讯 IEG 后台开发面试</a>
</li>
<li>
<a href="/2019/02/26/cjtk4cs6m007c04c2hfdnwt9r/">吉比特实习面试</a>
</li>
<li>
<a href="/2019/01/15/cjtk4cs7x008804c2md0758yf/">概率论笔记</a>
</li>
<li>
<a href="/2018/11/16/cjtk4cs5d007204c26oslbpd4/">二维ST表</a>
</li>
</ul>
</div>
</div>
</aside>
</div>
<footer id="footer">
<div class="outer">
<div id="footer-info" class="inner">
© 2019 Fish<br>
Powered by <a href="http://hexo.io/" target="_blank">Hexo</a>
</div>
</div>
</footer>
</div>
<nav id="mobile-nav">
<a href="/" class="mobile-nav-link">Home</a>
<a href="/archives" class="mobile-nav-link">Archives</a>
</nav>
<script src="//ajax.googleapis.com/ajax/libs/jquery/2.0.3/jquery.min.js"></script>
<link rel="stylesheet" href="/fancybox/jquery.fancybox.css">
<script src="/fancybox/jquery.fancybox.pack.js"></script>
<script src="/js/script.js"></script>
<!-- MathJax -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
showProcessingMessages: false,
tex2jax: {
inlineMath: [["$", "$"], ["\\\\(", "\\\\)"]],
processEscapes:true
},
menuSettings: {
zoom: "Hover"
}
});
</script>
<script src="//cdn.bootcss.com/mathjax/2.6.0/MathJax.js?config=TeX-AMS_HTML"></script>
</div>
</body>
</html>