Sellaris

分类

题解(3)

/ 注册

全部文章（共3篇）

牛客小白月赛115G

决策单调性分治容易发现将询问离线排序之后，值更大的询问能取到的最优决策点是递增的。这是因为考虑a数组，如果出现一个逆序对，那么右边那个位置一定是不优的；因此决策点一定是一个下标递增，值也递增的数列。决策单调性考虑分治，对于一个询问的值，只需枚举当前决策区间内的每个点，答案是中比...

C++ 决策单调性分治

2025-09-15

0 23

牛客周赛 Round 104 F

注意到不动点个数等价于数组的Mex，使用树上启发式合并(DSU on Tree) 统计每个子树的Mex累加即可。 ///*****Sellaris*****/// #include <bits/stdc++.h> #define ll long long #define x first...

C++ 树上启发式合并

2025-09-15

0 21

牛客周赛 Round 103F

已经看到出题人的trie+二分哈希做法，以及前排大佬根号分治，长串Z函数，短串暴力trie。给出一种AC自动机做法：对于一个的后缀，答案为，其中代表是多少个的前缀。因为题目要求的是 "每个字符串的最长公共前缀的长度之和。" 那么的每个长度的前缀若能匹配上个 ...

拓扑排序字符串匹配

2025-08-03

2 79