郑州轻工业大学吕子明
郑州轻工业大学吕子明
全部文章
分类
题解(9)
归档
标签
去牛客网
登录
/
注册
郑州轻工业大学吕子明的博客
一个来自数学院的计算机科学爱好者
全部文章
(共9篇)
题解
第五场 E.换根Dp 性质: 只要有一个权为111 的边在点 u,vu,vu,v 之间在路径上,那么 u,vu,vu,v 之间的距离便是 111 , 否则是222。 思路 将所有能通过权为 222 的边相连的点放入一个集合中。对于一个点 uuu, 与其在相同集合中的点的距离为 222, 其所在集合大...
C++
树
2023-08-10
4
352
题解 | #We love string#
I . We love string 分治 容斥!! 将所有长度相同和模式串分到一个组中,使用一个类对象来表示一个组; fSf_S fS 表示能于集合SSS内的所有正则表达式匹配的的字符串个数 集合SSS 用二进制数表示 考虑到所有模式串的长度之和不超过 400400400 ,所以当模式串的长度小...
C++
字符串
二进制枚举
分治
2023-08-08
0
362
题解 | #Beautiful Sequence#
牛客多校七 C 将每一个数看成是 303030 位二进制整数 只要确定了 a1a_1a1, 剩下的数就都确定了 , 因为 ai+1←bi⊕aia_{i+1} \gets b_i \oplus a_i ai+1←bi⊕ai a2←b1⊕a1a_2 \gets b_1 \oplus a_...
C++
位运算
2023-08-08
0
408
题解 |
和高等代数有关 注意事项 集合中没有重复的元素。 要特判 000 初始在集合中的情况 结论在 z≠z∧z≠y∧x≠0∧y≠0z \ne z \land z\ne y \land x \ne 0 \land y\ne 0z=z∧z=y∧x=0∧y=0 , 的情况下 可以通过一些...
C++
数学
2023-08-04
5
367
题解 | #小富的 idea#
小富的idea 题目链接 可以先计算出任意两点间的融合时间, 时间复杂度 O(n2)O(n^2)O(n2)对融合时间排序,然后从小到大枚举,如果当前时间下对应的两个点不在一个连通块中则合并连通块的个数减一;对于时间1,10001,10001,1000,可以离线预处理出来每一个时间点的个数。 实现技巧...
C++
并查集
2023-08-03
0
387
题解 | 萌新向D 题题解
萌新联赛D 要记得开 longlonglong long longlong 不然通过率 %0\%0%0 ! 方法一 多观察 2=2202 = 2^{2^0}2=220 2⋅2=2212 \cdot2 = 2^{2^1}2⋅2=221 221⋅221=2222^{2^1} \cdot 2^{2^1} ...
C++
数学
脑筋急转弯
2023-08-03
5
317
题解 | #E- Red and Blue and Green#
题目关题信息: 所有区间是包络的(指一个区间被另一个区间完全覆盖)或者不交的(因此可看成树形结构进行dfs) 相关知识 交换两邻的两个数会改一个区间逆序对数量的奇偶性; 非降序的排列的逆序对儿的数量个数为 000; 思路: 将区间化成树形结构每个叶子节点包含三个值 l,r,k{l,r,k}l,...
C++
深度优先搜索
2023-08-03
1
593
题解 | C 萌新向题解二分图匹配与竞赛图综合题
C 萌新向题解二分图匹配与竞赛图综合题 题目链接 经验教训 : 题中要求了 i,i+ni,i+ni,i+n 之间没有边也就是转化形成的图是竞赛图且没有自环; 要仔细看题 题中明确给出了是有 n⋅(n−1)÷2n\cdot(n-1) \div2n⋅(n−1)÷2 条边 相关前置知识 完全图 是指...
C++
图
2023-08-01
2
794
题解 | 动态规划加后缀和优化
牛客多校 jjj 题 以 dpijdp_{ij}dpij 表示前 iii 个数中最小后缀和为 jjj 的方案数 最小后缀和不会大于 mmm ,因为如果左边是连续的两个正数那么只会加一个,其最大值为 m 由于下标不能为负数所以将 [−m,m][-m,m][−m,m] 映射到 [0,2m][0,2m]...
C++
动态规划
前缀和
2023-07-31
2
612