Turgen

题解

/ 注册

全部文章 / 题解（共12篇）

题解 | #小红的数字查找#

前置知识唯一分解定理：一个大于1的正整数可以被表示为多个质数的乘积，一般表示为完全平方数：注意到完全平方数可以表示为，而根据唯一分解定理，k又是可以被表示为质因子乘积，因此我们有结论：即，一个完全平方数，每个不同质因子的幂次一定是偶数。另外：平方数×平方数还是平方数思路还是唯一分解定...

数学

2026-03-09

1 16

题解 | #倍数#

可以被5整除的充分必要条件是个位是0或5 由于排列可以随便排，所以只需要数字中有0或者有5就可以了 void solve(){ cin>>n; string s=to_string(n); if(s.find('5')!=-1 || s.find('0')!=-1...

2026-02-28

0 36

题解 | #小红统计区间（hard）只离散化S[i]

这题大部分题解都是和放进去，其实只离散化也是可以的. 每次查询目标值在离散化数组的排名，然后查询排名数量即可。这样做的时间复杂度是，常数应该是上面写法的2倍左右，不过实测速度挺快名列前茅代码如下： #include <iostream> #include <algori...

树状数组离散化

2026-02-24

0 30

题解 | #爱丽丝的人偶圆舞曲#

一道不算难，但写起来有点难的dp。记为前项中，最后一位一定为的最小开销显然，即第一个字符一定为第一个字符是不需要修改的。而，即第一个字符如果要修改为别的字符，就是花费1个代价。考虑如何转移，如果要考虑第项改为，那前一项可以是，其中是符合和谐条件的两个字母，二者取一个最小值，然...

动态规划

2026-02-09

2 66

题解 | #魔法人偶的十进制校准#

赛时为数不多做出来的数学题观察样例发现很难构造，因为第位要放一个数字，不可能真像那样这么好枚举，但是第二个样例提醒了我们，如果是无限循环小数，就不需要管位置。考公的时候学过百化分，注意到 ,那么就分为以下几种情况数字为0：如果要求放小数点后第一位，可以直接是，如果不是，可以直接是 ...

数学

2026-02-09

1 60

题解 | #恋恋的01串大冒险#

把0看做输了一把游戏，1看做赢了一把游戏，如果一个人连输k把就不想玩，然而我们有任意次机会可以让一个输了的游戏变成赢得，怎么变才能让他玩的把数最多。自然是等他输到第k把的时候就马上给他改成赢的。鉴于之前评论区有神人认为我没有及时，详细地，像保姆一样地解答他的疑惑，故评论区不开放，有疑问的小伙伴可...

贪心

2026-02-07

0 62

题解 | #进退的艺术#

排序后，对于一个数，寻找第一个满足的。此时左边的都是不会发生冲突的，对自己的贡献是此时和右边的都是会发生冲突的，对自己的贡献是但这里麻烦是，左右两边可能包含自己。然后可能有连续相同数字，注意处理就好当，寻找到的第一个满足冲突的，必定满足不大于，如果是等于，会是相同值的第一个元素，此时计...

二分查找

2026-01-31

0 60

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

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

二分查找

2026-01-28

0 56

题解 | 字典树做法

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

字典树

2026-01-28

0 47

题解 | #小红模5#

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

2026-01-28

0 48