Turgen

题解

/ 注册

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

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

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

动态规划

2026-02-09

2 26

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

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

数学

2026-02-09

1 26

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

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

贪心

2026-02-07

0 22

题解 | #进退的艺术#

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

二分查找

2026-01-31

0 33

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

假设当前数字是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 33

题解 | 滑动窗口做法

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

滑动窗口

2026-01-28

1 33

题解 | 一种双指针的写法

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

C++

2026-01-25

0 28