-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy path0x3f的茶
11736 lines (9227 loc) · 419 KB
/
0x3f的茶
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
日期 题解请滑到右边 --> 样例 难度 题解 备注
2023年10月10日 https://codeforces.com/problemset/problem/1690/E
输入 T(≤1e4) 表示 T 组数据。所有数据的 n 之和 ≤2e5。
每组数据输入 n(2≤n≤2e5) k(1≤k≤1000) 和长为 n 的数组 a(0≤a[i]≤1e9)。
保证 n 是偶数。
你需要把这 n 个数两两一对。把 a[i] 和 a[j] 组成一对的得分为 floor((a[i]+a[j])/k)。
最大化这 n/2 个数对的得分之和。输出这个最大值。 输入
6
6 3
3 2 7 1 4 8
4 3
2 1 5 6
4 12
0 0 0 0
2 1
1 1
6 10
2 0 0 5 9 4
6 5
5 3 8 6 3 2
输出
8
4
0
2
1
5 1500 首先每个数的 floor(a[i]/k) 是必得的,加到答案中,然后更新 a[i] %= k。
为了继续得分,我们必须选尽量多的数对,满足 a[i]+a[j] >= k,这样可以多得一分。
怎么做?把 a 排序后,相向双指针:
- 如果 a[i] + a[j] < k,说明 a[i] 加上任何小于 a[j] 的数,都是小于 k 的,所以 a[i] 不能和其余数加在一起得分了,i++。
- 否则,可以得一分,i++ j--。如果 a[j] 不和 a[i] 匹配,那么后面 a[i] 可能无法和另一个数匹配了
https://codeforces.com/contest/1690/submission/227301239
相似题目:
881. 救生艇
2023年10月9日 https://atcoder.jp/contests/abc321/tasks/abc321_d
输入 n m(1≤n,m≤2e5) p(1≤p≤2e8),和长度分别为 n 和 m 的数组 a 和 b,元素范围 [1,1e8]。
输出如下程序打印的值:
sum = 0
for x in a:
for y in b:
sum += min(x + y, p)
print(sum) 输入
2 2 7
3 5
6 1
输出 24
输入
1 3 2
1
1 1 1
输出 6 806 把 a 和 b 从小到大排序。
倒着遍历 a,同时维护指针 j,它是满足 a[i]+b[j] >= p 的最小值。
那么对于 a[i] 来说:
b[0] 到 b[j-1] 中的任何数和 a[i] 相加都是 < p 的,把 a[i] * j + (b[0] + ... + b[j-1]) 加入答案。
b[j] 到 b[m-1] 中的任何数和 a[i] 相加都是 >= p 的,把 p * (m-j) 加入答案。
https://atcoder.jp/contests/abc321/submissions/46275700
2023年10月6日 https://atcoder.jp/contests/tenka1-2019/tasks/tenka1_2019_d
输入 n(3≤n≤300) 和长为 n 的数组 a(1≤a[i]≤300)。
把每个 a[i] 都涂成红/绿/蓝三种颜色中的一种。(相当于把 a 分成 3 个子序列)
记红色元素和为 R,绿色元素和为 G,蓝色元素和为 B。
问:有多少种涂色方案,使得 R,G,B 组成了一个非退化三角形的三条边。模 998244353。
注:非退化三角形即面积为正的三角形,或者说三顶点不共线的三角形。 输入
4
1
1
1
2
输出 18
输入
6
1
3
2
3
5
2
输出 150 2237 请看题解:
https://www.luogu.com.cn/blog/endlesscheng/solution-at-tenka1-2019-d
2023年10月5日 https://atcoder.jp/contests/abc279/tasks/abc279_f
输入 n(2≤n≤3e5) 表示有 n 个盒子,编号从 1 到 n。
每个盒子都放了一个小球,其中编号为 i 的盒子放了编号为 i 的小球。
然后输入 q(1≤q≤3e5) 和 q 个操作,格式如下:
"1 x y":把编号为 y 的盒子中的小球全部放入编号为 x 的盒子中。保证 x≠y。
"2 x":设所有盒子中一共有 k 个小球,现在把一个新的编号为 k+1 的小球放入编号为 x 的盒子中。
"3 x":输出编号为 x 的小球所在盒子的编号。保证 x 一定在某个盒子中。 输入
5 10
3 5
1 1 4
2 1
2 4
3 7
1 3 1
3 4
1 1 4
3 7
3 6
输出
5
4
3
1
3 1777 看上去是个并查集模板,但是把盒子 y 中的小球倒入盒子 x 后,盒子 y 是可以继续放入小球的。
这要怎么办?y 已经合并到 x 中了。
我们可以为 y 创建一个(大于 n 的)新的编号 z,表示一个新的空盒子。后续放入 y 的小球,就改为放在盒子 z 中。
但是这样做,要怎么输出小球所在的盒子编号呢?
记录编号为 z 的盒子的【原始盒子编号】为 y 即可。
具体细节见代码。
https://atcoder.jp/contests/abc279/submissions/46217952
2023年10月4日 https://atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b
输入 n(2≤n≤1000) k(1≤k≤n*(n+1)/2) 和长为 n 的数组 a(1≤a[i]≤1e9)。
a 一共有 n*(n+1)/2 个非空连续子数组,也有对应的 n*(n+1)/2 个子数组元素和。
从这 n*(n+1)/2 个元素和中,选择 k 个,计算这 k 个数的按位与(AND)。
按位与的最大值是多少?
不考虑输入的空间,你能做到 O(1) 额外空间吗? 输入
4 2
2 5 2 5
输出 12
输入
8 4
9 1 8 2 7 5 6 4
输出 32 1381 从高位到低位考虑。
如果所有子数组和的第 x 位有超过 k 个 1,那么答案的第 x 位可以是 1,且后续只需要考虑第 x 位是 1 的子数组和。
如果不足 k 个 1,那么答案的第 x 位只能是 0。
https://atcoder.jp/contests/dwacon5th-prelims/submissions/46029217
2023年10月3日 https://atcoder.jp/contests/abc222/tasks/abc222_d
输入 n(1≤n≤3000) 和两个长为 n 的数组 a b,元素范围在 [0,3000],且均为递增数组(允许有相同元素)。
构造递增数组 c(允许有相同元素),满足 a[i]<=c[i]<=b[i]。
输出你能构造多少个不同的 c,模 998244353。 输入
2
1 1
2 3
输出 5
输入
3
2 2 2
2 2 2
输出 1
输入
10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100
输出 978222082 865 有两种定义 DP 的方式。
定义 f[i][j] 表示考虑前 i 个数,其中第 i 个数填 j 的方案数
那么有 f[i][j] = f[i-1][0] + f[i-1][1] + ... + f[i-1][min(j, b[i-1])]
这可以用前缀和优化。
这启发我们,也可以直接定义 f[i][j] 表示考虑前 i 个数,其中第 i 个数填的数 <=j 的方案数。
考虑第 i 个数是否要填 j:
- 不填,那就是第 i 个数填的数 <=j-1 的方案数,即 f[i][j] = f[i][j-1]。
- 填,那么第 i-1 个数至多为 j,即 f[i][j] = f[i-1][min(j, b[i-1])]。
则有 f[i][j] = f[i][j-1] + f[i-1][min(j, b[i-1])]。
初始值 f[0][j] = j-a[0]+1,其中 a[0]<=j<=b[0]。
答案为 f[n-1][b[n-1]]。
https://atcoder.jp/contests/abc222/submissions/46028545
2023年10月2日 https://atcoder.jp/contests/abc125/tasks/abc125_d
输入 n(2≤n≤1e5) 和长为 n 的数组 a(-1e9≤a[i]≤1e9)。
你可以执行如下操作任意多次:
选择 a 中两个相邻数字,把它们俩都乘上 -1。
输出 sum(a) 的最大值。
思考:如果只能选择 a[i] 和 a[i+2] 呢?(间隔一个数)
思考:如果至多操作 k 次呢? 输入
3
-10 5 -4
输出 19
输入
5
10 -4 -8 -11 3
输出 30
输入
11
-1000000000 1000000000 -1000000000 1000000000 -1000000000 0 1000000000 -1000000000 1000000000 -1000000000 1000000000
输出 10000000000 833 操作不会改变负数个数的奇偶性。
如果有偶数个负数(或者存在 0),那么所有数都可以变成非负数。
如果有奇数个负数,并且没有 0,那么最后会剩下一个负数,我们可以让绝对值最小的那个数是负数。
https://atcoder.jp/contests/abc125/submissions/46144732
如果至多操作 k 次,可以用 DP 思考。
2023年9月29日 https://atcoder.jp/contests/agc015/tasks/agc015_d
输入 A B (1≤A≤B<2^60)。
问:有多少个数,可以由 [A,B] 内的一个或多个整数,通过按位或 (OR) 运算得到?
思考:改成 AND 要怎么做?改成 XOR 呢? 输入
7
9
输出 4
解释 除了 7,8,9 以外,还可以通过 7 OR 8 得到 15,所以一共有 4 个数。
输入
65
98
输出 63
输入
271828182845904523
314159265358979323
输出 68833183630578410 2655 请看题解:
https://www.luogu.com.cn/blog/endlesscheng/solution-at-agc015-d
2023年9月28日 https://atcoder.jp/contests/abc208/tasks/abc208_e
输入 n(1≤n≤1e18) 和 k(1≤k≤1e9)。
问:有多少个不超过 n 的正整数,其数位乘积不超过 k? 输入 13 2
输出 5
解释 1,2,10,11,12 共 5 个
输入 100 80
输出 99
输入 1000000000000000000 1000000000
输出 841103275147365677 2024 注意到乘积要么是 0,要么可以写成 2^a * 3^b * 5^c * 7^d 的形式。
所以只有 O(log^4 k) 个不同的数位乘积。
数位 DP 模板秒杀。记忆化用哈希表。
https://atcoder.jp/contests/abc208/submissions/45250040
2023年9月27日 https://atcoder.jp/contests/abc098/tasks/arc098_b
输入 n(1≤n≤2e5) 和长为 n 的数组 a(0≤a[i]<2^20)。
a 有多少个非空连续子数组,满足元素和等于元素异或和?
思考:改成子序列要怎么做? 输入
4
2 5 4 6
输出 5
输入
9
0 0 0 0 0 0 0 0 0
输出 45
输入
19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1
输出 37 1404 这个等式意味着什么?
意味着二进制加法不能有任何进位,否则等式右边一定大于左边。
没有任何进位相当于什么?
相当于子数组中的任意两个数,同一个比特位上不能都是 1,也就是说,任意两个数的按位与(AND)为 0。
这题就是:
2401. 最长优雅子数组
可以用滑动窗口做到 O(n),请看题解:
暴力枚举 / 双指针
https://atcoder.jp/contests/abc098/submissions/45104677
2023年9月26日 https://atcoder.jp/contests/abc202/tasks/abc202_d
输入 A B(1≤A,B≤30) K。
在所有由恰好 A 个 'a' 和恰好 B 个 'b' 组成的字符串中,输出字典序第 K 小的字符串。
例如 K=1 表示字典序最小的字符串。
K 的范围保证有解。 输入 2 2 4
输出 baab
输入 30 30 118264581564861424
输出 bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaa 966 如果第一个字母是 'b',那么 K 至少要是多少?
=> 第一个字母填 'a' 一共有多少种方案?
=> C(a+b-1, b)
=> 如果 K > C(a+b-1, b),那么第一个字母一定是 'b'
依此类推。
https://atcoder.jp/contests/abc202/submissions/45501705
2023年9月25日 https://atcoder.jp/contests/abc138/tasks/abc138_d
输入 n(2≤n≤2e5) q(1≤q≤2e5) 表示一个 n 个点的树(节点编号从 1 开始,根节点为 1)。
然后输入 n-1 条边(每行两个数)。
然后输入 q 个操作,每个操作输入 p(1≤p≤n) x(1≤x≤1e4),表示把子树 p 内的所有节点值都加 x。(一开始所有节点值均为 0)
输出最终每个节点的节点值。(按节点编号从小到大输出) 输入
4 3
1 2
2 3
2 4
2 10
1 100
3 1
输出 100 110 111 110
输入
6 2
1 2
1 3
2 4
3 6
2 5
1 10
1 10
输出 20 20 20 20 20 20 920 只需要记录节点 p 的节点值增加了多少。
然后从 1 开始 DFS 这棵树,DFS 的同时累加从 1 到当前节点 x 的这条路径上的节点值之和,即为节点 x 的最终节点值。
(类似 lazy 线段树的懒标记下传 push down)
https://atcoder.jp/contests/abc138/submissions/45500929
2023年9月22日 https://atcoder.jp/contests/diverta2019/tasks/diverta2019_e
输入 n(1≤n≤5e5) 和长为 n 的数组 a(0≤a[i]<2^20)。
把数组 a 划分成若干段连续子数组,一共有 2^(n-1) 种划分方案。
问:其中有多少种划分方案,可以让每段子数组的异或和都一样?
答案模 1e9+7。 输入
3
1 2 3
输出 3
解释 一共有四种划分方案:
[1,2,3]
[1],[2,3]
[1,2],[3]
[1],[2],[3]
除了最后一种不符合要求,其余三种都是符合要求的。
输入
3
1 2 2
输出 1
解释 只有一种合法划分方案,就是什么也不划分。 2423 请看题解:
https://www.luogu.com.cn/blog/endlesscheng/solution-at-diverta2019-e
2023年9月21日 https://atcoder.jp/contests/abc058/tasks/arc071_b
输入 n m(2≤n,m≤2e5),长为 n 的严格递增数组 x(-1e9≤x[i]≤1e9),长为 m 的严格递增数组 y(-1e9≤y[i]≤1e9)。
从 x 中选两个数,组成直线 X=x[i1], X=x[i2],其中 i1<i2。
从 y 中选两个数,组成直线 Y=y[j1], Y=y[j2],其中 j1<j2。
这四条直线包围的区域是一个矩形。
计算所有矩形的面积之和。模 1e9+7。 输入
3 3
1 3 4
1 3 6
输出 60
输入
6 5
-790013317 -192321079 95834122 418379342 586260100 802780784
-253230108 193944314 363756450 712662868 735867677
输出 835067060 1641 提示 1:手玩下 n=3, m=3 的情况(图形是一个田字)。把公式列出来。
矩形面积 = 长*宽,在 n=3, m=3 的情况下,可以有 3 种长,3 种宽。
所有矩形面积 = 长1*宽1 + 长1*宽2 + 长1*宽3 + 长2*宽1 + 长2*宽2 + 长2*宽3 + 长3*宽1 + 长3*宽2 + 长3*宽3
= (长1 + 长2 + 长3) * (宽1 + 宽2 + 宽3)
所以,长和宽可以分别计算。
对于 x,问题变成:所有 x[j]-x[i] 的和 (i<j)。
提示 2:贡献法,考虑 x[i] 在和式中的贡献是多少?
即:有多少个 +x[i]?有多少个 -x[i]?
解答:(i 从 0 开始)有 i 个 +x[i],有 n-1-i 个 -x[i]。
所以 x[i] 在和式中的贡献为 2*i-n+1。
这样,我们就得到了一个 O(n+m) 的算法。
https://atcoder.jp/contests/abc058/submissions/45464458
2023年9月20日 https://atcoder.jp/contests/arc158/tasks/arc158_b
输入 n(3≤n≤2e5) 和长为 n 的数组 a(-1e6≤a[i]≤1e6 且 a[i]≠0)。
从 a 中选 3 个下标不同的数 x y z。
输出 (x+y+z)/(x*y*z) 的最小值和最大值。
和答案的绝对/相对误差需要在 1e-12 内。 输入
4
-2 -4 4 5
输出
-0.175000000000000
-0.025000000000000
输入
4
1 1 1 1
输出
3.000000000000000
3.000000000000000
输入
5
1 2 3 4 5
输出
0.200000000000000
1.000000000000000 1446 如果知道 x 和 y,那么式子可以变形为
(x+y)/(xy) * (1/z) + 1/(xy)
由反比例函数的性质可知,当 z 取绝对值最小或最大的数时,可以让式子取到最值。
对于 x 和 y 也同理。
所以至多考虑 12 个数即可(负数中最小 3 个,最大 3 个,正数中最小 3 个,最大 3 个),在这里面枚举 x y z。
https://atcoder.jp/contests/arc158/submissions/45499928
2023年9月19日 https://atcoder.jp/contests/abc301/tasks/abc301_d
输入长度 ≤60 的字符串 s,只包含 '0','1' 和 '?'。
输入 n(1≤n≤1e18)。
你需要把 s 中的 ? 替换成 0 或 1,从而得到一个二进制数 x。
问:不超过 n 的最大 x 是多少?
以十进制形式输出这个最大值。
如果不存在这样的 x,输出 -1。 输入
?0?
2
输出 1
输入
101
4
输出 -1
输入
?0?
1000000000000000000
输出 5 885 把 ? 都替换成 0,如果此时 x > n,则输出 -1。
然后从左到右遍历每个 ?,如果把这个 ? 替换成 1,右侧 ? 替换成 0 后,满足 x <= n,那么这个 ? 一定要替换成 1,否则这个 ? 一定要替换成 0。
https://atcoder.jp/contests/abc301/submissions/45500660
2023年9月18日 https://atcoder.jp/contests/abc248/tasks/abc248_d
输入 n(1≤n≤2e5) 和长为 n 的数组 a(1≤a[i]≤n),下标从 1 开始。
然后输入 q 个询问,每个询问输入 L R (1≤L≤R≤n) 和 x(1≤x≤n)。
对每个询问,输出有多少个下标 i 在 [L,R] 内的 a[i],满足 a[i]=x。 输入
5
3 1 4 1 5
4
1 5 1
2 4 3
1 5 2
1 3 3
输出
2
0
0
1 793 遍历 a,把相同元素 x 的所有下标统计到列表 pos[x] 中。
每个询问的答案就是 <= R 的下标个数,减去 < L 的下标个数。
在 pos[x] 中二分查找即可算出。
https://atcoder.jp/contests/abc248/submissions/45034624
离线做法可以做到线性时间复杂度,见右图。@田永杰🍩
2023年9月15日 https://atcoder.jp/contests/arc136/tasks/arc136_d
输入 n(2≤n≤1e6) 和长为 n 的数组 a(0≤a[i]<1e6)。
输出满足【十进制加法 a[i]+a[j] 的每个数位都没有产生进位】的下标对 (i,j) 个数,其中 i<j。 输入
4
4 8 12 90
输出 3
输入
20
313923 246114 271842 371982 284858 10674 532090 593483 185123 364245 665161 241644 604914 645577 410849 387586 732231 952593 249651 36908
输出 6
输入
5
1 1 1 1 1
输出 10 1908 举例,如果一个数和 666 相加不进位,那么与 665 相加也不会进位。
定义 y 是 x 的「十进制子集」,当且仅当 y 的所有数位都小于等于 x 对应的数位。例如 666,566,656,665,123,66 都是 666 的十进制子集。
定义 f[i] 表示 i 的十进制子集的个数。
为什么要这样定义?对于 a[i] 来说,999999-a[i] 的任意十进制子集与 a[i] 相加都不会进位,所以 f[999999-a[i]] 就是与 a[i] 相加不进位的数字个数。
枚举 i 的第 j 个数位,如果这个数位大于 0,那么
f[i] += f[i-pow(10,j)]
初始值:f[x] = x 在数组 a 中的出现次数。
然后遍历 a[i],把 f[999999-a[i]] 加到答案中。
如果 a[i]+a[i] 没有进位,那么我们多统计了一个答案,ans--。
最后把答案除以 2,因为 (a[i],a[j]) 和 (a[j],a[i]) 我们都统计了一次。
https://atcoder.jp/contests/arc136/submissions/45039336
注:如果你之前学过二进制的 SOS DP,对于想出本题做法有帮助。
本题相当于是十进制的 SOS DP。
2023年9月14日 https://atcoder.jp/contests/abc155/tasks/abc155_d
输入 n(2≤n≤2e5) k(1≤k≤n*(n-1)/2) 和长为 n 的数组 a(-1e9≤a[i]≤1e9)。
从 a 中选两个数,相乘,一共可以得到 n*(n-1)/2 个结果。
输出这 n*(n-1)/2 个数中,第 k 小的数。
注:k=1 表示最小的数。
相似题目:
2040. 两个有序数组的第 K 小乘积 输入
4 3
3 3 -4 -2
输出 -6
输入
10 40
5 4 3 2 -1 0 0 0 0 0
输出 6 1845 说一个 O(nlogU) 的做法。U=1e18。
需要用到二分答案+同向双指针+相向双指针。
1. 对 a 从小到大排序。
2. 找到第一个 >= 0 的数的下标 p 和第一个 > 0 的数的下标 q。(下标从 0 开始)
3. 有 neg = p * (n-q) 个乘积是负数。
4. 设 c = q-p,那么有 zero = c*(n-c) + c*(c-1)/2 个乘积是 0。
5. 第一种情况:如果 k <= neg,那么答案是负数。可以二分答案的绝对值 kth,统计有多少数对相乘是负数且绝对值 <= kth,这可以用同向双指针完成。一个指针从 0 开始向右移动,另一个指针从 q 开始向右移动。
6. 第二种情况:如果 k <= neg + zero,那么答案为 0。
7. 第三种情况:如果 k > neg + zero,那么答案是正数。二分答案 kth,统计有多少个对数相乘是正数且 <= kth,这可以用相向双指针完成。对所有负数 a[i] 跑一遍相向双指针,对所有正数 a[i] 跑一遍相向双指针。
https://atcoder.jp/contests/abc155/submissions/45503273
注:二分和双指针是基础中的基础,如果你写这题卡壳了或者 WA 了,说明基本功还不够扎实,请在一个月后重新做这道题。
2023年9月13日 https://atcoder.jp/contests/code-festival-2016-qualc/tasks/codefestival_2016_qualC_c
输入 n(1≤n≤1e5) 和两个长为 n 的数组 b 和 c (1≤b[i],c[i]≤1e9)。
构造数组 a,满足 a[i] 都是正整数,且:
b[i] = max(a[0], a[1], ..., a[i]),即数组 a 的前缀最大值。
c[i] = max(a[i], a[i+1], ..., a[n-1]),即数组 a 的后缀最大值。
问:有多少个符合要求的数组 a?模 1e9+7。
如果不存在这样的数组 a,输出 0。 输入
5
1 3 3 3 3
3 3 2 2 2
输出 4
输入
5
1 1 1 2 2
3 2 1 1 1
输出 0 1404 如果 b[i]>b[i-1],那么 a[i] 一定是 b[i]。如果此时 c[i] < b[i],矛盾,输出 0。
同理,如果 c[i]>c[i+1],那么 a[i] 一定是 c[i]。如果此时 b[i] < c[i],矛盾,输出 0。
如果 b[i]=b[i-1] 且 c[i]=c[i+1],那么 a[i] 可以填不超过 min(b[i],c[i]) 的正整数,这有 min(b[i],c[i]) 种方案。
所有 a[i] 的方案数相乘即为答案。
https://atcoder.jp/contests/code-festival-2016-qualc/submissions/45329380
2023年9月12日 https://atcoder.jp/contests/arc137/tasks/arc137_b
输入 n(1≤n≤2e5) 和长为 n 的数组 a(0≤a[i]≤1)。
你需要执行如下操作恰好一次:
选择 a 的一个连续子数组(可以为空),把子数组内的 0 变成 1,1 变成 0。
设新数组为 a'。
问:你可以得到多少个不同的 sum(a')? 输入
4
0 1 1 0
输出 4
输入
5
0 0 0 0 0
输出 6
输入
6
0 1 0 1 0 1
输出 3 883 提示 1:sum(a') 最大是多少?最小是多少?
提示 2-1:sum(a') 在原来的 sum(a) 的基础上,最多可以增加多少?
提示 2-2:把子数组内的 0 视作 1,1 视作 -1。
最大子数组和就是最大增量 maxInc。
提示 2-3:把子数组内的 0 视作 -1,1 视作 1。
最大子数组和就是最大减少量 maxDec。
注:也可以在提示 2-2 的基础上计算最小子数组和。
提示 3:答案就是 maxInc+maxDec+1。
证明:我们可以在任意子数组的基础上「微调」,也就将子数组的长度加一或者减一。例如把 0 包含入子数组,那么变化量仅会 +1。同理,把 0 移出子数组,那么变化量仅会 -1。对于把 1 包含入/移出子数组的情况同理。
因此可以把变化量从 -maxDec 不断微调到 maxInc,所以变化量可以取到 [-maxDec, maxInc] 中的任意整数,这一共有 maxInc+maxDec+1 个数。
https://atcoder.jp/contests/arc137/submissions/45319475
相似题目:
https://codeforces.com/contest/1695/problem/C
2023年9月11日 https://atcoder.jp/contests/abc248/tasks/abc248_c
输入 n m(1≤n,m≤50) k(n≤k≤n*m)。
输出有多少个长为 n 的数组 a 满足 1≤a[i]≤m 且 sum(a)≤k。
模 998244353。
数据加强版 输入 2 3 4
输出 6
输入 31 41 592
输出 798416518 787 方法一:朴素 DP
f[i][j] 表示前 i 个数的元素和为 j 的方案数。i 从 1 开始。
f[i][j] = f[i-1][j-1] + f[i-1][j-2] + ... + f[i-1][max(j-m,0)]
初始值 f[0][0] = 1。
答案为 sum(f[n])。
https://atcoder.jp/contests/abc248/submissions/45034906
方法二:后缀和优化 DP
把转移方程中的和式用后缀和优化。
用后缀和的原因是可以一边计算状态一边计算后缀和,这样就不需要 f 数组了,只需要后缀和数组。
https://atcoder.jp/contests/abc248/submissions/45035045
2023年9月8日 https://atcoder.jp/contests/abc243/tasks/abc243_g
输入 T(≤20) 表示 T 组数据。
每组数据输入 X(1≤X≤9e18)。
请构造一个长为 10^100 的数组 a,满足:
1. a[i] 均为正整数。
2. a[0] = X。
3. a[i] * a[i] <= a[i-1]。
输出你可以构造出多少个不同的数组。 输入
4
16
1
123456789012
1000000000000000000
输出
5
1
4555793983
23561347048791096 2032 下标从 0 开始。
提示 1:
枚举 a[2],那么 a[1] 的范围就确定了。
设 m = floor(sqrt(a[0]))。
那么 a[1] 的范围就是 [a[2]*a[2], m],这一共有 m-a[2]*a[2]+1 个数,这些数都可以是 a[1]。
提示 2:
定义 f[i] 表示序列的首项为 i 时,可以构造出多少个不同的数组。
根据提示 1,有
f[i] = sum(f[j] * (m-j*j+1)),这里 1 <= j <= sqrt(m)。
提示 3:
预处理出 f[1] 到 f[54772],就可以直接用上式算出 f[X]。这里 54772 = floor(pow(9e18, 0.25))。
预处理可以不用像上式那样复杂,枚举 a[1],可以得到
f[i] = sum(f[j]),这里 1 <= j <= sqrt(i)。
这个式子又可以化简成
f[i] = f[i-1] + (i 是完全平方数 ? f[floor(sqrt(i))] : 0)
https://atcoder.jp/contests/abc243/submissions/45083883
2023年9月7日 https://atcoder.jp/contests/abc309/tasks/abc309_f
输入 n(2≤n≤2e5) 和 n 个盒子的长宽高,每行输入三个数,范围 [1,1e9]。
你可以随意旋转盒子,也可以保持不变。
问:是否存在一个盒子可以被另一个盒子装下,也就是一个盒子的长宽高都分别严格小于另一个盒子的长宽高。
输出 "Yes" 或 "No"。
相似题目:
1691. 堆叠长方体的最大高度 输入
3
19 8 22
10 24 12
15 25 11
输出 Yes
输入
3
19 8 22
10 25 12
15 24 11
输出 No
输入
2
1 1 2
1 2 2
输出 No 1619 请先阅读:
【图解】算法优化+详细证明
接着上面的题解说。对于每个盒子,把长宽高从小到大排序(排序后分别记作 a[i][0], a[i][1], a[i][2]),然后按照 a[i][0] 从小到大排序所有盒子。
接下来只需要考虑是否有 a[i][1] < a[j][1] 且 a[i][2] < a[j][2],这可以用树状数组解决(数据范围太大可以用离散化或者哈希表实现)。
把 (a[i][1], a[i][2]) 看成是二维平面的坐标点,我们可以维护 x=a[i][1] 这条线左侧的所有坐标点的纵坐标的最小值,即前缀最小值 preMin(a[i][1]-1)。
只要满足 preMin(a[i][1]-1) < a[i][2] 就可以输出 Yes。
具体细节见代码,注意为了满足严格小于,对于相同的 a[i][0] 需要先查询完再一并更新。
https://atcoder.jp/contests/abc309/submissions/45242148
2023年9月6日 https://atcoder.jp/contests/abc194/tasks/abc194_e
输入 n m(1≤m≤n≤1.5e6) 和长为 n 的数组 a(0≤a[i]<n)。
定义 mex(b) 为不在数组 b 中的最小非负整数。
遍历 a 的所有长为 m 的连续子数组 b,输出 mex(b) 的最小值。 输入
3 2
0 0 1
输出 1
输入
3 2
1 1 1
输出 0
输入
3 2
0 1 0
输出 2
输入
7 3
0 0 1 2 0 1 0
输出 2 1088 方法一:通用的做法是值域树状数组二分。(留给大家思考)
方法二:更巧妙的做法。
提示 1:先把前 m 个数的 mex 算出来,答案至多是它。
提示 2:我们只需要知道最小的 mex 是多少,因此当一个数滑出窗口时,只要窗口内没有这个数,那么就用这个数更新答案的最小值。
https://atcoder.jp/contests/abc194/submissions/45036824
2023年9月5日 https://atcoder.jp/contests/abc308/tasks/abc308_e
输入 n(3≤n≤2e5) 和长为 n 的数组 a(0≤a[i]≤2),以及长为 n 的字符串,仅包含 'M' 'E' 'X'。
遍历所有满足 i<j<k 且 s[i]=M 且 s[j]=E 且 s[k]=X 的下标三元组 (i,j,k),累加 mex(a[i],a[j],a[k]) 的值,输出这个累加值。
注:mex(a[i],a[j],a[k]) 表示不在 a[i],a[j],a[k] 中的最小非负整数。 输入
4
1 1 0 2
MEEX
输出 3
输入
3
0 0 0
XXX
输出 0
输入
15
1 1 2 0 0 2 0 2 0 0 0 0 0 2 2
EXMMXXXEMEXEXMM
输出 13 1042 方法一:前后缀分解
枚举中间的 j。我们需要知道左边满足 s[i]=M 的 0/1/2 的个数;右边满足 s[k]=X 的 0/1/2 的个数。
这可以预处理出来。
当 s[j]=E 时,枚举 j 左边的 0/1/2 和 j 右边的 0/1/2 的 9 种组合,再算上 a[j],得到 mex。
例如 a[j]=1,左边有 5 个 1,右边有 3 个 0,那么 mex(1,1,0)=2,对答案的贡献是 5*3=15 个 mex,也就是 30。
https://atcoder.jp/contests/abc308/submissions/45101686
方法二:状态机 DP
定义 f0[0/1/2] 表示当前统计的满足 s[i]=M 的 0/1/2 的个数。
定义 f1[1/2/3/4/5/6] 表示当前统计的满足 a[i]=M 且 a[j]=E 的 a[i] 和 a[j] 组成的集合(二进制表示)的个数,例如 f1[5] 表示集合 {0,2} 的个数。
遍历到 s[k]=X 时,枚举 mask=1/2/3/4/5/6,把答案加上 mex(mask 和 a[k] 组成的集合) * f1[mask]
https://atcoder.jp/contests/abc308/submissions/45102151
2023年9月4日 https://atcoder.jp/contests/diverta2019/tasks/diverta2019_c
输入 n(1≤n≤1e4) 和 n 个字符串,每个字符串只包含大写字母,长度在 [2,10] 中。
将这些字符串按照某种顺序相连,得到字符串 s。
问:s 中最多可以有多少个连续子串是 "AB"?
进阶:子串长度为 3
https://codeforces.com/gym/102431/problem/H 输入
3
ABCA
XBAZ
BAD
输出
2 922 首先把每个字符串中的 AB 个数加到答案中。
接着,如果只考虑以 A 结尾的字符串(个数记作 a),或者以 B 开头的字符串(个数记作 b),每一对拼起来可以得到一个 AB,那么答案额外加上 min(a,b)。
然后,考虑以 B 开头且以 A 结尾的字符串(个数记作 ba),这些字符串可以「插入」到上面拼起来的 AB 之间,那么答案额外加上 ba+min(a,b)。
除了一种特殊情况:ba > 0 且 a = 0 且 b = 0,此时答案只能加上 ba-1。
https://atcoder.jp/contests/diverta2019/submissions/45086403
2023年9月1日 https://atcoder.jp/contests/arc092/tasks/arc092_b
输入 n(1≤n≤2e5) 和两个长为 n 的数组 a b,元素范围在 [0,2^28)。
从 a 中选一个数 a[i],从 b 中选一个数 b[j],相加得到 a[i]+b[j]。这一共有 n^2 个数字。
输出这 n^2 个数的异或和。 输入
2
1 2
3 4
输出 2
输入
6
4 6 0 0 3 3
0 5 6 5 0 3
输出 8
输入
5
1 2 3 4 5
1 2 3 4 5
输出 2
输入
1
0
0
输出 0 2207 二进制题目,常用技巧之一是拆位,但这只能用于各个比特位互相独立的情况。
本题加法有进位,破坏了这种独立性,这要如何处理呢?
其实也可以拆位(我叫它加法拆位)。
按照 mod (2^k) 拆位,例如要计算从低到高第三个比特位,可以 mod 8(即 AND 7)。
记 s = a[i]%8 + b[j]%8。
要想知道这 n^2 个 s 中,从低到高第三个比特位有多少个 1,相当于求满足下式的 s 的个数:
100 <= s <= 111 或 1100 <= s <= 1111(数字为二进制)。
这可以在按照 mod 8 排序后,用五个指针做。一个指针遍历 a[i],另外 4 个指针在 b 上,对应着上式的 4 个区间端点。
注意:相加可能会进位到第 29 个比特位,在枚举的时候请注意上界。
https://atcoder.jp/contests/arc092/submissions/44922461
优化:
注意到 s <= 1<<(k+2)-1 是恒成立的,上面代码中的 q 恒等于 n-1。
而 n 个 n-1 的异或和一定是偶数(最低位一定是 0),所以可以完全去掉 q。
优化后
2023年8月31日 https://atcoder.jp/contests/abc300/tasks/abc300_f
输入 n(1≤n≤3e5) m(1≤m≤1e9) k 和长为 n 的字符串 s,只包含小写字母 'o' 和 'x'。
保证至少有一个 'x',保证 1≤k≤s.count('x')*m。
将 s 重复 m 次,得到字符串 t。例如 "abc" 重复 3 次得到 "abcabcabc"。
请你修改 t 中的恰好 k 个 'x'。修改后,输出 t 中最长连续 'o' 的长度。 输入
10 1 2
ooxxooooox
输出 9
输入
5 3 4
oxxox
输出 8
输入
30 1000000000 9982443530
oxoxooxoxoxooxoxooxxxoxxxooxox
输出 19964887064 1846 写了很多 if-else?
实际上有一种写法,完全不需要分类讨论!
设 pos 为所有 x 的下标列表(下标从 0 开始)。
设 pos 的长度为 cntX。
提示 1:把前 k 个 x 修改成 o,答案是多少?
min(k/cntX*n + pos[k%cntX], n*m)
提示 2:把前 2~k+1 个 x 修改成 o,答案是多少?
可以先算出「修改前 k+1 个 x」的答案,再减去「第一个 x 的下标 +1」。
把上面公式中的 k 替换成 k+1 就是「修改前 k+1 个 x」的答案。
依此类推,一直枚举到最后一个 x。
https://atcoder.jp/contests/abc300/submissions/44909568
2023年8月30日 https://atcoder.jp/contests/abc295/tasks/abc295_d
输入长度 ≤5e5 的字符串 s,只包含数字字符。
定义 f(t):如果字符串 t 中的每个字符都出现偶数次,则 f(t)=1,否则 f(t)=0。
枚举 s 的所有非空连续子串 t,输出 f(t) 之和。 输入 20230322
输出 4
输入 0112223333444445555556666666777777778888888889999999999
输出 185
输入 3141592653589793238462643383279502884197169399375105820974944
输出 9 939 用「前缀异或和」实现,具体请看我在力扣上的这篇题解:
题解
https://atcoder.jp/contests/abc295/submissions/44903277
2023年8月29日 https://atcoder.jp/contests/abc294/tasks/abc294_e
给你两个长度均 L 的数组 a 和 b,输出有多少个下标 i 满足 a[i]=b[i]。
由于 L 很大,输入用一种压缩格式表示,即 (元素值,连续出现次数)。
例如 [(10,2),(20,1),(10,3)] 表示数组 [10,10,20,10,10,10]。
具体输入格式和数据范围见题目链接。
进阶:
https://ac.nowcoder.com/acm/contest/62033/D 输入
8 4 3
1 2
3 2
2 3
3 1
1 4
2 1
3 3
输出
4 792 有思路但不一定好写的题目。
用双指针做。
通过引入「剩余连续长度」这一概念,可以简化代码逻辑,请看代码。
https://atcoder.jp/contests/abc294/submissions/44905290
2023年8月28日 https://atcoder.jp/contests/abc233/tasks/abc233_d
输入 n(1≤n≤2e5) k(-1e15≤k≤1e15) 和长为 n 的数组 a(-1e9≤a[i]≤1e9)。
输出元素和等于 k 的连续子数组个数。
如果你觉得本题太简单,请思考这个问题:
所有元素和等于 k 的连续子数组的长度之和。 输入
6 5
8 -3 5 7 0 -4
输出 3 726 用前缀和思考:
sum[R] - sum[L] = k
枚举 R,问题变成有多少个 sum[L],也就是 sum[R]-k 的个数。
这可以用哈希表统计,代码如下。
https://atcoder.jp/contests/abc233/submissions/44903090
关于思考题的提示:
举例:
(R-L1) + (R-L2) + (R-L3)
= 3*R - (L1+L2+L3)
所以除了维护前缀和的出现次数,还需要维护下标之和。
2023年8月25日 https://atcoder.jp/contests/arc137/tasks/arc137_c
输入 n(2≤n≤3e5) 和长为 n 的严格递增数组 a(0≤a[i]≤1e9)。
Alice 和 Bob 在玩一个回合制游戏,Alice 先手。
游戏规则如下:
1. 一开始,数轴上有 n 颗石子,第 i 颗石子的位置是 a[i]。
2. 每个回合,玩家只能移动最右边的那颗石子。且必须将它移动到在它左边的没有石子的非负整数空位上。例如 a=[2,4],你只能移动位置 4 上的石子到位置 0 或 1 或 3。
3. 移动石子后,轮到另一个玩家继续移动这 n 颗石子中的最右边的石子。如此交替。
4. 无法移动的玩家输掉游戏,另一位玩家获胜。
如果 Alice 必胜,输出 Alice,否则输出 Bob。 输入
2
2 4
输出 Alice
解释 Alice 把 4 移动到 3,就可以保证必胜。(手玩一下)
输入
3
0 1 2
输出 Bob 2043 题解已写好,欢迎点赞!
2023年8月24日 https://atcoder.jp/contests/abc298/tasks/abc298_f
输入 n(1≤n≤2e5) 和 n 行,每行三个数 x y v,表示一个二维坐标点 (x,y) 和这个坐标点上的数字 v (1≤x,y,v≤1e9)。
不在输入中的坐标点上的数字均为 0。
请你选择一个坐标点 (X,Y),累加所有横坐标为 X 的坐标点上的数字,以及所有纵坐标为 Y 的坐标点上的数字。
(X,Y) 上的数字只累加一次。
(X,Y) 不一定要在输入中。
输出累加值的最大值。 输入
4
1 1 2
1 2 9
2 1 8
3 2 3
输出 20
输入
1
1 1000000000 1
输出 1 1568 先预处理所有行和列的元素和(用两个哈希表)。
暴力做法:把所有横纵坐标都记录下来,写一个二重循环枚举所有横坐标和纵坐标的组合。
显然这个做法会超时。
但如果把纵坐标按照列的元素和从大到小排序,对于内层循环,只要当前枚举的 (x,y) 不在输入中,就可以退出内层循环了,因为后面算出的元素和只会更小。
这种做法可以保证至多遍历 n 个值为 0 的坐标。
https://atcoder.jp/contests/abc298/submissions/44850426
2023年8月23日 https://atcoder.jp/contests/abc300/tasks/abc300_e
输入 n(1≤n≤1e18)。
你有一个整数 x,初始值为 1。
你有一个六面的骰子,可以等概率地掷出 1~6。
不断重复如下操作,直到 x>=n 为止:
掷骰子。把 x 乘上骰子显示的数字。
问:当你停止操作时,x 恰好等于 n 的概率是多少?
设概率为 a/b,输出 a * pow(b,mod-2) % mod,其中 mod=998244353。 输入 6
输出 239578645
输入 7
输出 0
输入 300
输出 183676961
输入 979552051200000000
输出 812376310 1354 定义 P(n) 表示得到 n 的概率。
则有 P(n) = (1/6) * (P(n) + P(n/2) + P(n/3) + P(n/4) + P(n/5) + P(n/6))。
整理得到 P(n) = (1/5) * (P(n/2) + P(n/3) + P(n/4) + P(n/5) + P(n/6))。
如果 n%i>0,则 P(n/i)=0。
由于 n 很大,需要用 map+记忆化搜索。从 n 出发递归到 1。
递归边界:P(1)=1。
注:除以 5 等价于乘以 pow(5,998244353-2)%998244353 = 598946612。