Rikka with Intersection of Paths 题解

MayFlyyh | LCA, 容斥, 组合 | 2020-10-07
Rikka with Intersection of Paths 题解 Rikka有一棵包含$ n(1≤n≤3×10^5) $个节点的树 $T$,节点编号为 $1$ 到 $n$ 。树上也标记了$ m (2≤m≤3×10^5)$ 条简单路径,第i条路径连接 $x_i$ 和 $y_i$ $ (1≤x_i,y_i≤n)$,这些路径可能会有重复的。如果要在其中选择 $k$ 条路径,要求这 $k$ 条路径至少有一个公共点,计算有多少种选择方案。输出其... [阅读全文]

异象石 题解

MayFlyyh | LCA | 2020-10-07
异象石 题解
异象石 题解 在 Adera 的异时空中有一张地图。这张地图上有 N 个点,有 N−1 条双向边把它们连通起来。起初地图上没有任何异象石,在接下来的 M个时刻中,每个时刻会发生以下三种类型的事件之一: 地图的某个点上出现了异象石(已经出现的不会再次出现); 地图某个点上的异象石被摧毁(不会摧毁没有异象石的点); 向玩家询问使所有异... [阅读全文]

ACM重新再来过~ ——近期感想

MayFlyyh | 其他, 未分类 | 2020-10-05
2020年10月4日,打了2019~2020的第一场CF,上次打还是Good bye 2018,感觉很淦,题又看错了,又少字了,就像回到了NOIP2018一样。 高考来了SCU,进了算实验班的一个班,遇到了各路大佬Orz,也结识了很多好朋友。 上了大学,方向更多了,未来的路走的都是更贴近专业的道路,希望自己能把握好机会。 高中钟意的女生,跟自己上了一所大学,也是缘分,可... [阅读全文]
ė 6 2条评论 0

ARC 67F Yakiniku Restaurants 题解

MayFlyyh | 未分类 | 2018-12-28
ATCODER ARC 67F Yakiniku Restaurants 题解 有编号从$1$到$N$的$N$家烧烤店,烧烤店在一条线上按照编号顺序排序,第$i$家烧烤店与第$i + 1$家烧烤店的距离是$A_i$ 。 你有编号从$1$到$M$的$M$张烧烤券,不管是在哪一家烧烤店都可用烧烤券来吃烧烤,在第$i$家烧烤店用烧烤券$j$可以吃到一顿美味度为$B_{i,j}$的烧烤,每一张烧烤券只能使用一... [阅读全文]
ė 6 2条评论 0

AC自动机学习笔记

MayFlyyh | 字符串 | 2018-12-22
AC自动机学习笔记 用途 一个常见的例子就是给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。 思想 要搞懂AC自动机,先得有模式树(Trie树)Trie和KMP模式匹配算法的基础知识。AC自动机算法分为3步:构造一棵Trie树,构造失败指针和模式匹配过程。 与KMP类似,AC自动机对于普通暴力的优化方式即是在与当前模式串失... [阅读全文]

Luogu P2569 [SCOI2010]股票交易

MayFlyyh | DP | 2018-12-19
[SCOI2010]股票交易 最近lxhgww又迷上了投资股票,通过一段时间的观察和学习,他总结出了股票行情的一些规律。 通过一段时间的观察,lxhgww预测到了未来T天内某只股票的走势,第i天的股票买入价为每股APi,第i天的股票卖出价为每股BPi(数据保证对于每个i,都有APi>=BPi),但是每天不能无限制地交易,于是股票交易所规定第i天的一次买入至多只能购... [阅读全文]
ė 6 没有评论 0

Luogu P1640 [SCOI2010]连续攻击游戏

MayFlyyh | 并查集 | 2018-12-19
Luogu P1640 [SCOI2010]连续攻击游戏 题目描述 lxhgww最近迷上了一款游戏,在游戏里,他拥有很多的装备,每种装备都有2个属性,这些属性的值用[1,10000]之间的数表示。当他使用某种装备时,他只能使用该装备的某一个属性。并且每种装备最多只能使用一次。游戏进行到最后,lxhgww遇到了终极boss,这个终极boss很奇怪,攻击他的装备所使用的属性... [阅读全文]

Luogu P2567 [SCOI2010]幸运数字

MayFlyyh | 容斥 | 2018-12-19
题目描述 在中国,很多人都把6和8视为是幸运数字!lxhgww也这样认为,于是他定义自己的“幸运号码”是十进制表示中只包含数字6和8的那些号码,比如68,666,888都是“幸运号码”!但是这种“幸运号码”总是太少了,比如在[1,100]的区间内就只有6个(6,8,66,68,86,88),于是他又定义了一种“近似幸运号码”。lxhgww规定,凡是“幸运号码”的倍数都是“近... [阅读全文]

BZOJ 1858 [Scoi2010]序列操作

MayFlyyh | 线段树 | 2018-12-19
lxhgww最近收到了一个01序列,序列里面包含了n个数,这些数要么是0,要么是1,现在对于这个序列有五种变换操作和询问操作: 0 a b 把[a, b]区间内的所有数全变成0 1 a b 把[a, b]区间内的所有数全变成1 2 a b 把[a,b]区间内的所有数全部取反,也就是说把所有的0变成1,把所有的1变成0 3 a b 询问[a, b]区间内总共有多少个1 ... [阅读全文]

好题记录

MayFlyyh | 未分类 | 2018-10-26
CF487B 双指针好题 CF983E 树上问题 CF959E 异或问题 [阅读全文]
ė 6 没有评论 0
Ɣ回顶部