Turgen

分类

题解(10)

/ 注册

全部文章（共22篇）

题解 | 小红的gcd

观察样例大胆猜测：答案是因为任意两个数的gcd一定有一个因子是总体的gcd，也就是这个数一定是总体的倍数，连续gcd后，最终的数必然都会变成全体的最大公约数，不可能比这个还小，因为gcd最小就能让一个数减少到全体的公约数，不会使得一个数比这个全体的公约数还要小，因此我们简单证明了这个答案是最小的，...

2026-01-30

4 45

题解 | #小红的完全平方数构造# 二分简单做法

假设当前数字是114514，我们得到的答案必定是114514abcd 枚举扩展位数，由于答案说明在18位以内，故扩展位数最多枚举18次获取扩展后的，例如我们扩展了2位，应该得到11451400 寻找第一个大于等于11451400的完全平方数，在二分的时候二分的是中的，由于最大答案不会...

二分查找

2026-01-28

0 33

题解 | 字典树做法

思路答案一定可以是输入的字符串中的一个，因为若答案字符串长这样（红色）完全可以去掉分割线右边多余的，不影响答案此时答案变成，是否能找到一个字符串，使得这个字符串包含了恰好K-1个其他字符串暴力枚举的时间复杂度是，但是看图可知，这个答案如果要包含其他字符串，一定其他字符串是他的前缀，于是可...

字典树

2026-01-28

0 29

题解 | #小红模5#

注意到十进制数的构成是形如，由于高位带了权重，所以一定可以被5整除，只需要看个位数。个位数有种取值范围，其对应的模5余数只在0~4，其中0没有贡献不计当最后一位取值为x时，我们也无需关心他拼在一起是怎么样的，只需要关心这个数字的个位数，也就是每个数都可以有(n-1)！个方案数，其贡献是x取...

2026-01-28

0 32

题解 | 滑动窗口做法

实际上就是问我们，能找出多少对区间，使满足这一段被挖去后，剩余的字符串中有一个子序列是。观察时间复杂度，大概是的级别，我们考虑这样一件事：如果是合法答案，那么往里缩也一样合法，因为往里缩会减少字符数量。如果不是答案，那么扩大一样不合法，因为往外扩会额外增加字符负担如果，...

滑动窗口

2026-01-28

1 33

题解 | 最通俗易懂，最详细的题解

思路：看一眼数据，回答最多，但很显然这题要求我们用，也就是推一个式子。由于必须O(1)回答，所以对于1到j的最短路径，一定是直接边结论1：两个不同的正整数异或结果一定非负，既。已知可以让原本偶数+1，奇数-1,假设有中间转点k，则其路径至少是。若，也就是至少，容易发现无论j是奇数还是偶数，都不比这...

2026-01-28

2 39

题解 | 离线询问+双指针做法

跟【小红的区间查询】这一题如出一辙，仍然可以离线查询，对查询进行排序后使用双指针优化。构建前缀和数组，原问题等价问，第k个时刻处于前几个区间，大众做法是每次二分前缀和数组，找出第一个大于等于的S[k]，k问答案。我们可以将每次询问保存起来，最后排序，排完序后是单调不减的，那么越往后的询问，对k的要...

2026-01-26

1 36

题解 | 一种双指针的写法

这题大多数人用的是二分查找，我想到了一个双指针的写法，虽然综合时间复杂度仍然是的，但二分写法实际上是，而该写法可以优化成，即对于T次询问，总时间复杂度是。首先先对区间左端点排序，对于一个询问x，我们不做在线回答，而是收集起来做离线回答。先对询问进行排序。记当前的询问是，当前的区间是，有以下几...

C++

2026-01-25

0 26

题解 | 好好好数组

CSDN看到的一个另外一种容易想到的解法，原文链接如果a[n]确定了，那么整个数组也就确定的，很容易发现，符合条件的数组一定是单调不降的，因为取模只会把数字变小，或者不变，不可能变大。故当a[n]越小时，其往前的数字的可取值范围就越小，就更容易取到相同值，使数组出现不同种类的数字就更难，因此答案具有...

2026-01-25

0 26

题解 | 邮递员送信

我们希望1到X和X到1都是最短路，有个难点是多个起点到终点的最短路，就要用到反向建边，反向建一个图，然后跑1到x的最短路，得到的结果就是x到1的最短路，因为这条路径是反着的，我们扭回来就正好是x到1了。在形式上不要写的像我一样，可以用vector模拟静态邻接链表。时间复杂度O(mlogn) #inc...

2026-01-23

0 33