Sellaris
Sellaris
全部文章
分类
题解(3)
归档
标签
去牛客网
登录
/
注册
Sellaris的博客
全部文章
(共3篇)
牛客小白月赛115G
决策单调性分治 容易发现将询问离线排序之后,值更大的询问能取到的最优决策点是递增的。 这是因为考虑a数组,如果出现一个逆序对,那么右边那个位置一定是不优的; 因此决策点一定是一个下标递增,值也递增的数列。 决策单调性考虑分治,对于一个询问的值 ,只需枚举当前决策区间内的每个点 ,答案是 中比...
C++
决策单调性
分治
2025-09-15
0
19
牛客周赛 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
16
牛客周赛 Round 103F
已经看到出题人的trie+二分哈希做法,以及前排大佬根号分治,长串Z函数,短串暴力trie。 给出一种AC自动机做法: 对于一个的后缀 , 答案为 ,其中 代表 是多少个 的前缀。因为题目要求的是 "每个字符串的最长公共前缀的长度之和。" 那么的每个长度的前缀 若能匹配上 个 ...
拓扑排序
字符串匹配
2025-08-03
2
74