四糸智乃

题解

算法(12)

/ 注册

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

题解 | #纯白地狱(hard version)#

纯白地狱这题是我自己一个人出的，成分比较复杂，没想到有人能AC。 89 63 78 69 98 58 51 48 31 24 60 50 59 2 57 56 28 52 45 22 55 29 53 32 26 75 80 99 96 79 4 33 25 19 42 38 15 3 16 6 ...

2024-06-01

6 756

题解 | #炸鸡块哥哥的粉丝题#

题解区公式会炸，请移步讨论区 https://ac.nowcoder.com/discuss/1298659 补丁，放抽楼 #include <bits/stdc++.h> using namespace std; const long long INF = 5e18; int n; i...

2024-04-26

0 322

题解 | #智乃的前缀、后缀、回文#

起因： https://zhuanlan.zhihu.com/p/681953843 题解里面虽然提了一嘴能用KMP做，但是我只是知道能求回文border这个结论，实际上我没写过。原因是它虽然能求，但是它求这玩意很麻烦，来回倒腾好几手，做题的时候不如直接上回文机之类的东西了。为什么kmp可以求回文...

KMP

2024-02-10

1 468

题解 | #智乃的数据库#

L、智乃的数据库按照题意进行模拟即可。分组的话可以使用并查集或者hash，如果使用hash进行数组元素分组的话有个小技巧，就是利用sort将分组转化成数组切段，这样写起来就比较清爽了。时间复杂度O(NMlogN)O(NMlogN)O(NMlogN)空间复杂度O(NM)O(NM)O(NM)。 #...

2022-01-28

3 702

题解 | #智乃的C语言模除方程(another version)#

K、智乃的C语言模除方程(another version) 首先可以按照上一道题的做法去做（直接改上一题的calcEx即可），但是实际上这道题在思维上更简单了，不需要转化成二维前缀和。首先你要知道一个叫做整除分块的数论板子。整除分块是处理形如Ni\frac{N}{i}iN，其中iii为循环变量...

2022-01-28

1 683

题解 | #智乃的C语言模除方程#

J、智乃的C语言模除方程这道题就分情况讨论随便算一算就行了。不过这道题的重点不在于数学计算，而是如何建模。首先第一个难点,[l,r][l,r][l,r],[L,R][L,R][L,R]区间都是包含数轴正负数轴，这个就很讨厌，所以第一步，首先把所有问题都移动到正半轴[1,r][1,r][1,r]...

2022-01-28

4 527

题解 | #智乃的密码#

I、智乃的密码首先把这几个条件拆开来看，也就是变成这样6个条件： 1、长度不小于LLL 2、长度不大于RRR 3、有小写英文字母 4、有大写英文字母 5、有数字 6、有特殊字符你发现这6个条件可以拆开分别考虑。同时这6个条件在固定所选子串的其中一个端点后，另一个端点的合法性是单调的。所以可以...

2022-01-28

2 622

题解 | #智乃的树旋转(hard version)#

H、智乃的树旋转(hard version) 还是注意这么一句话智乃最近学习了树旋转，树旋转的本质是二叉树旋转轴节点与其父节点父子关系的改变思考这么一个问题：如果对某一个非根节点，一直作为旋转轴进行旋转，那么最后会发生什么。显然，最终该节点一定被转到了整棵树的根部。当你意识到这个问题之后，此时...

2022-01-28

2 657

题解 | #智乃的树旋转(easy version)#

G、智乃的树旋转(easy version) 还是题解就写在了题目当中。认真读题，注意这么一句话智乃最近学习了树旋转，树旋转的本质是二叉树旋转轴节点与其父节点父子关系的改变所以二重循环枚节点，当发现在两颗树中某一对节点互为父子关系时，直接输出原本是父亲的节点。如果不存在这么一个节点，说明不用旋...

2022-01-28

0 620

题解 | #智乃的数字积木(hard version)#

F、智乃的数字积木(hard version) 启发式合并，每次选较小的颜色往大的块上面并。具体来讲，这道题要维护若干个颜色相同的“块”。对于每一个块，其实并不需要每一次都暴力排序，其实我们只需要知道其中有几个1，几个2，几个3... 使用桶排序的思路统计每个块中数字的个数。然后它一定是形如...

2022-01-28

4 856