sunrise__sunrise

题解

未归档(12) 读书笔记(1)

/ 注册

全部文章 / 题解（共372篇）

2021牛客暑期多校训练营10 来自专栏

A、Browser Games 题目大意给出个字符串，你需要输出行。对于第个字符串来说，你需要在这些字符串里面分别找到一个前缀，并且满足这些前缀去重之后长度最小。其次就是你曾经选择过的前缀不能做为前缀出现在这些字符串里面。卡了空间只允许。 Solution 考点：字符串hash 如果是正序的...

暑假多校训练营

2021-09-17

1 1338

2021牛客暑期多校训练营10 G、Game of Death 来自专栏

G、Game of Death 题目大意场上共有个人，现在每个人都会随机选择一个其他人开枪，并且成功命中其他人的概率为。你需要输出场上留下个人的概率，分式对取模。 Solution 考点：子集反演+NTT 首先考虑状态设计，我们让代表被击中的是集合的概率，我们让代表被击中的是子集的概率。所以我...

子集反演 NTT

2021-09-16

0 873

2021牛客暑期多校训练营10 F、Train Wreck 来自专栏

题目大意给你一个长度为的出栈入栈序列，你现在有辆列车，第辆列车颜色为，你要让每次停留在栈中颜色排列是唯一的。问是否可行，如果可行输出进栈颜色方案。 Solution 考点：堆我们可以把出栈入栈转换成一棵树来考虑，初始栈为空的时候假设我们有一个节点的树并且这个结点编号为，接下来入栈就是当前节点新开...

堆

2021-09-15

2 681

2021牛客暑期多校训练营10 A、Browser Games 来自专栏

A、Browser Games 题目大意给出个字符串，你需要输出行。对于第个字符串来说，你需要在这些字符串里面分别找到一个前缀，并且满足这些前缀去重之后长度最小。其次就是你曾经选择过的前缀不能做为前缀出现在这些字符串里面。卡了空间只允许。 Solution 考点：字符串hash 如果是正序的...

字符串hash

2021-09-14

1 707

2021牛客暑期多校训练营9 来自专栏

C、Cells 参考过的题解题目大意你有一张无穷大的二维矩阵，你的出发点在格点，并且保证了出发点横坐标依次递增：。你的目标点分别是，你有几个出发点就有几个目标点，求从出发点去目标点走过的路径没有任何交点的方案数。 Solution 考点：LGV引理+多项式卷积这题第一个难点就是要会转换模型，...

2021暑假多校训练营

2021-09-14

0 808

2021牛客暑期多校训练营9 G、Glass Balls 来自专栏

G、Glass Balls 题目大意你有一颗以为根的有向树，一共有个节点，对于每个节点初始都有一个小球，它存在的每一秒都会向父亲节点滚动一次，然后节点又分为可存储节点和不可存储节点。小球如果到了可存储节点它会掉入节点中，如果有两个小球同时掉入同一个存储节点游戏直接结束答案贡献为。否则对于起点在的小...

期望dp 逆元

2021-09-07

0 688

2021牛客暑期多校训练营9 E、Eyjafjalla 来自专栏

E、Eyjafjalla 题目大意你有一颗以111为根的n(1≤n≤105)n(1\le n\le 10^5)n(1≤n≤105)个节点的有根树，每个点都有一个温度ti(1≤ti≤109)t_i(1\le t_i\le 10^9)ti(1≤ti≤109)，并且保证每个父亲到儿子的温度一定是递减...

树上启发式合并树状数组

2021-09-07

3 705

2021牛客暑期多校训练营9 C、Cells 来自专栏

C、Cells 参考过的题解题目大意你有一张无穷大的二维矩阵，你的出发点在格点，并且保证了出发点横坐标依次递增：。你的目标点分别是，你有几个出发点就有几个目标点，求从出发点去目标点走过的路径没有任何交点的方案数。 Solution 考点：LGV引理+多项式卷积这题第一个难点就是要会转换模型，...

LGV引理 ntt/fft 行列式

2021-09-06

2 618

2021牛客暑期多校训练营8 来自专栏

A、Ares, Toilet Ares 说题目意思前先吐槽一下这题，这题面完完全全不清不楚，纯靠猜，果然厕所战神还是太强大了。虽然出题人表示只想要出个简答题+讲个故事，最终导致了赛中每队基本人均一，战况惨烈。题目大意你原本的得分是，你可以去次厕所，每次去厕所有的概率拿到可以让你的得分加一的卡片...

2021暑假多校训练营

2021-08-30

1 911

2021牛客暑期多校训练营8 J、Tree 来自专栏

题目大意二人现在站在一棵树上的不同点，现在有成员得分等于这个人走过的路径长度，并且在这棵树上行走有一个特殊的性质，就是从之后点将会被删除，并且与相连的全部边都会被删除。现在他们双方都想让自己的得分减掉对方得分最大化，起始站在点，起始站在点，问游戏结束的得分减掉的得分结果是多少？ Solution ...

ST表 DFS

2021-08-30

1 889