CF1452D Radio Towers

MayFlyyh | DP | 2020-11-21
CF1452D Radio Towers 有 $n +2$ 个点,编号从 $0$ 开始,线性排列,从点 $1$点 $n$ 每个点被取到的概率为$ \large \frac{1}{2}$ ,求能产生合法覆盖的概率对 $998244353$ 取模。 每个点若向左覆盖了 $x$个点,则他必须同时向右覆盖 $x$ 个点,即覆盖范围 $[i - x,i + x]$ ( $x$ 由自己决定) 当每个点仅被覆盖一次,且点 $0$ 和点 $n-1$ ... [阅读全文]

CF1446C Xor Tree

MayFlyyh | Trie | 2020-11-18
CF1446C Xor Tree 对于每个点$i$,找到$j≠i$且$a_j$ $xor$ $ a_i$最小,连边$(i,j)$。 如果连边之后形成一棵树,那么称${a_i}$为合法的。 给出${a_i}$,求至少删掉多少个点才合法。 $n≤2∗10^5$ $a_i$互不相同 考虑到序列中 $n$ 个点产生的 $n$ 条边,必然有重合的两条边(异或值最小的点对产生的两条边),故一个序列不可能... [阅读全文]

CF1442A Extreme Subtraction

MayFlyyh | 其他 | 2020-11-11
CF1442A Extreme Subtraction 你有一个序列 $a$,你可以进行 $2$ 种操作: 选择前 $k$ 个数,将它们全部减 $1$ 选择后 $k$ 个数,将它们全部减 $1$ $k$ 由你自己定,并且每次操作可以不同。 问是否可以把通过若干次操作整个序列变为全是 $0$ 的序列 本题多测,有 $t$ 组数据 $t \le 30000$ $\sum n \le 30000$ $a_i \le... [阅读全文]

Luogu P6185 [NOI Online #1 提高组]序列

MayFlyyh | 图论 | 2020-11-04
Luogu P6185 [NOI Online #1 提高组]序列
Luogu P6185 [NOI Online #1 提高组]序列 小 D 有一个长度为 $n$ 的整数序列 $a_{1 \dots n}$,她想通过若干次操作把它变成序列 $b_i$。 小 D 有 $m$ 种可选的操作,第 $i$种操作可使用三元组 $(t_i,u_i,v_i)$描述:若$ t_i=1$,则她可以使 $a_{u_i}$ 与$ a_{v_i}$都加一或都减一;若$ t_i$=2,则她可以使 $a_{u_i}$ 减一、$a_{v_i}$ 加一,或... [阅读全文]

CF1437E Make It Increasing

MayFlyyh | DP | 2020-11-03
CF1437E Make It Increasing 给你一个数列 a ,一个集合 b , 对于每个 b 中的元素x, $a_x$ 不能修改,其他都可以修改,问最少多少次可以将 a 修改为严格单调递增的。如果不存在,输出 -1 。 a 中的所有元素在任意时刻必须都是整数。 首先先判断是否合法,要保证两个不能改变的数$a_{b_i}$和$a_{b_{i+1}}$之间够不够放下$b_{i+1}-b_i$个数 i... [阅读全文]

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自动机对于普通暴力的优化方式即是在与当前模式串失... [阅读全文]
Ɣ回顶部