郑州轻工业大学吕子明

分类

题解(9)

/ 注册

全部文章（共9篇）

题解

第五场 E.换根Dp 性质：只要有一个权为111 的边在点 u,vu,vu,v 之间在路径上，那么 u,vu,vu,v 之间的距离便是 111 , 否则是222。思路将所有能通过权为 222 的边相连的点放入一个集合中。对于一个点 uuu, 与其在相同集合中的点的距离为 222, 其所在集合大...

C++ 树

2023-08-10

4 358

题解 | #We love string#

I . We love string 分治容斥！！将所有长度相同和模式串分到一个组中，使用一个类对象来表示一个组； fSf_S fS 表示能于集合SSS内的所有正则表达式匹配的的字符串个数集合SSS 用二进制数表示考虑到所有模式串的长度之和不超过 400400400 ，所以当模式串的长度小...

C++ 字符串二进制枚举分治

2023-08-08

0 367

题解 | #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 411

题解 |

和高等代数有关注意事项集合中没有重复的元素。要特判 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 371

题解 | #小富的 idea#

小富的idea 题目链接可以先计算出任意两点间的融合时间, 时间复杂度 O(n2)O(n^2)O(n2)对融合时间排序，然后从小到大枚举，如果当前时间下对应的两个点不在一个连通块中则合并连通块的个数减一；对于时间1,10001,10001,1000，可以离线预处理出来每一个时间点的个数。实现技巧...

C++ 并查集

2023-08-03

0 392

题解 | 萌新向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 319

题解 | #E- Red and Blue and Green#

题目关题信息：所有区间是包络的(指一个区间被另一个区间完全覆盖)或者不交的（因此可看成树形结构进行dfs）相关知识交换两邻的两个数会改一个区间逆序对数量的奇偶性; 非降序的排列的逆序对儿的数量个数为 000; 思路：将区间化成树形结构每个叶子节点包含三个值 l,r,k{l,r,k}l,...

C++ 深度优先搜索

2023-08-03

1 598

题解 | 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 802

题解 | 动态规划加后缀和优化

牛客多校 jjj 题以 dpijdp_{ij}dpij 表示前 iii 个数中最小后缀和为 jjj 的方案数最小后缀和不会大于 mmm ,因为如果左边是连续的两个正数那么只会加一个，其最大值为 m 由于下标不能为负数所以将 [−m,m][-m,m][−m,m] 映射到 [0,2m][0,2m]...

C++ 动态规划前缀和

2023-07-31

2 616