G、Game of Death 题目大意 场上共有个人，现在每个人都会随机选择一个其他人开枪，并且成功命中其他人的概率为。 你需要输出场上留下个人的概率，分式对取模。 Solution 考点：子集反演+NTT 首先考虑状态设计，我们让代表被击中的是集合的概率，我们让代表被击中的是子集的概率。 所以我们可以得出。 接下来根据子集反演的公式，我们可以得出。 我们就把问题转变成求击中概率是子集的概率了，这个是比较好求的，如果我们假设代表开枪没打中人的概率。 集合中的人只能开枪没打中或者打中了中除自己以外的某个人，由于每个人都是独立的，概率直接做乘法即可；对于集合外的人，他们只能开枪没打中或者打中了...

题目大意 给你一个长度为的出栈入栈序列，你现在有辆列车，第辆列车颜色为，你要让每次停留在栈中颜色排列是唯一的。问是否可行，如果可行输出进栈颜色方案。 Solution 考点：堆 我们可以把出栈入栈转换成一棵树来考虑，初始栈为空的时候假设我们有一个节点的树并且这个结点编号为，接下来入栈就是当前节点新开辟一个儿子，出栈就是回到父亲，一直这样操作一个合理的出栈入栈顺序就会生成个节点。我们要做的就是给生成的个节点打上颜色，让每个点到的路径上构成的颜色序列唯一。 那么就很明显，我们每次让任意一个节点它的儿子节点们颜色互不相同就可以了。 我们用的方式填颜色，把同层次的颜色先选上不一样种颜色，并且每种颜色减...

A、Browser Games 题目大意 给出个字符串，你需要输出行。 对于第个字符串来说，你需要在这些字符串里面分别找到一个前缀，并且满足这些前缀去重之后长度最小。 其次就是你曾经选择过的前缀不能做为前缀出现在这些字符串里面。 卡了空间只允许。 Solution 考点：字符串hash 如果是正序的话比较容易考虑到字典树，但是字典树的空间这题卡空间过不去。 我们倒序的思考，对于最后一个字符串，只需要考虑前字符串里面第一个字符出现了几种就是答案了。 那么接下来如何处理加入的第个字符串。 我们把第个字符串的全部前缀都出来，接下来去一个里面把相同的前缀出现过的下标全部找出来，并且让这些下标在的位置前...

C、Cells 参考过的题解 题目大意 你有一张无穷大的二维矩阵，你的出发点在格点，并且保证了出发点横坐标依次递增：。 你的目标点分别是，你有几个出发点就有几个目标点，求从出发点去目标点走过的路径没有任何交点的方案数。 Solution 考点：LGV引理+多项式卷积 这题第一个难点就是要会转换模型，他的方案数本质上就是一个LGV引理的模板。 稍微提一下LGV引理，它讲的就是你有起点，目标点，那么你从个起点出发经过完全不相交的边去到个终点的方案数会等于下面的行列式。 对应的是从去往的方案数，那么对应到本题，从去往的方案数就是经典过河卒问题，它的方案数应该是。 写出本题的行列式： 求解阶方阵的常用...

G、Glass Balls 题目大意 你有一颗以为根的有向树，一共有个节点，对于每个节点初始都有一个小球，它存在的每一秒都会向父亲节点滚动一次，然后节点又分为可存储节点和不可存储节点。小球如果到了可存储节点它会掉入节点中，如果有两个小球同时掉入同一个存储节点游戏直接结束答案贡献为。否则对于起点在的小球来说，就是它在能往上滚的次数，求的期望是多少。 Solution 首先我们要找出全部存在贡献的游戏界面是什么。 我们知道任意一个节点它的全部孩子都会向上滚动到它那里去，所以对于合理的游戏局面来说，不能有任何一个节点它两个孩子都是非存储节点，那么这时候这两个孩子带来的球一定会造成崩溃。 所以对于单个...

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)，并且保证每个父亲到儿子的温度一定是递减的。 现在有Q(1≤Q≤105)Q(1\le Q\le10^5)Q(1≤Q≤105)次询问，每次询问在点xxx处有一个耐热性为[l,r][l,r][l,r]的病毒，问它最多可以散播到多少个点，它可以沿着路径向子孙节点也可以向父亲节点传播，当且仅当存在一个温度ti<l<mtext>&...

C、Cells 参考过的题解 题目大意 你有一张无穷大的二维矩阵，你的出发点在格点，并且保证了出发点横坐标依次递增：。 你的目标点分别是，你有几个出发点就有几个目标点，求从出发点去目标点走过的路径没有任何交点的方案数。 Solution 考点：LGV引理+多项式卷积 这题第一个难点就是要会转换模型，他的方案数本质上就是一个LGV引理的模板。 稍微提一下LGV引理，它讲的就是你有起点，目标点，那么你从个起点出发经过完全不相交的边去到个终点的方案数会等于下面的行列式。 对应的是从去往的方案数，那么对应到本题，从去往的方案数就是经典过河卒问题，它的方案数应该是。 写出本题的行列式： 求解阶方阵的常用...

A、Ares, Toilet Ares 说题目意思前先吐槽一下这题，这题面完完全全不清不楚，纯靠猜，果然厕所战神还是太强大了。 虽然出题人表示只想要出个简答题+讲个故事，最终导致了赛中每队基本人均一，战况惨烈。 题目大意 你原本的得分是，你可以去次厕所，每次去厕所有的概率拿到可以让你的得分加一的卡片的一小部分，这一小部分表示为，保证，就是完整卡片的长度，你只有在拿到全部长度的时候才能让你的得分加一，问你得分的期望是多？ Solution 我们不管的卡片长度，其余的求一次乘法逆元就行了。 ll n, m, k, a, l; int solve() { n = read(), m = r...

题目大意 二人现在站在一棵树上的不同点，现在有成员得分等于这个人走过的路径长度，并且在这棵树上行走有一个特殊的性质，就是从之后点将会被删除，并且与相连的全部边都会被删除。现在他们双方都想让自己的得分减掉对方得分最大化，起始站在点，起始站在点，问游戏结束的得分减掉的得分结果是多少？ Solution 考点：表+对抗搜索 第一我们知道对于之间的最短路径来说，如果有任何一个玩家脱离了这条路径上，那么这时候两名玩家就变成完全独立的两个部分分别走最大值了。 第二就是我们用同一个式子来表示双方都想最大化得分差值的式子。如果我们用代表的得分，代表的得分，所以也就是想要最大，想要最大，等价于想要最小。 对于具...

题目大意 你原本有个长度为的序列，现在我只告诉你两个长度为的序列，问合理的序列有多少种？ 我们定义。 Solution 由于给出的数组都是位运算得来的，我们就可以按位拆分，枚举的每一位，再去枚举不同的数。 我们首先看最低位，注意下面的代表着当前枚举的这一位二进制是还是，同理，映射到题目就是： 如果在最低位的情况下，这样的一共有个说明我们这一位存在两种构建方法，即或者这样交替进行。 我们把不足位我们可以分成下面的情况。 如果在最低位的某一个，说明它一定产生了进位，那么我们就把这次产生的进位消除，当我们每次都消除进位的时候就可以一直当作最低位处理了，例如，在我们消除最低位的带来的影响后它的第二位第...

B、xay loves monotonicity 题目大意 初始你有两个长度为的序列。 序列满足下面的要求：。接下来你有三种操作： 把赋值成。 把这一段区间全部按位取反，即互换。 求在这个区间中必选构成的最长不下降子序列，假设为，那么我们取出构成一个串，这个串中有多少个交接处就是这个区间的答案，你需要回答这样的操作答案是多少？ 操作最多有个。 Solution 考点：线段树区间合并 如果有写过用线段树维护最大连续子段和的读者可能会更好的理解这篇题解。 我们先看操作都是线段树的基础操作了，单点更新区间修改，打上标记即可，我们重点关注操作。 我们如何快速的找到区间的最长不下降子序列呢？ 首先我...

题目大意 有人把写成下面这样，请问这张有向图还有多少个是正确的？ 点数，边数，边权 for i from 1 to n for j from 1 to n for k from 1 to n dis[i][j] <- min(dis[i][j], dis[i][k] + dis[k][j]) Solution 考点：实现过程 我们可以在的时间内调用次算法求解到正确。 然后我们就要知道什么样的更新会让按照错误的做法也是正确的。 当存在一条边，有的时候。 当存在三点，有正确，正确，并且这个点在的最短路路径上。 我们用数组表示是正确的，我们用数组表示是正确的。 我们...

题目大意 给出棵以为根的树，你要在第一棵树上选择若干个点，并且在第二棵树上选择相同编号的点。 现在要求你在第一棵树上选择的点，把他们连接的边全部找出来必须构成一条链； 并且你在第二棵树上选择的点，不能存在任何两个点他们之间有祖先关系，换句话说就是某个点选了，它全部的子树节点都不能选了。 现在要你输出合理的点集最大的点数。 Solution 考点：时间戳+线段树 我们对第二棵树，打上时间戳，这样我就知道了每个节点他的全部子树在区间的什么范围内，时间戳它可以用这里面若干个子区间，并且时间戳可以让同一个节点的不同子树在完全不相交的区间里面，并且会包含它全部的子树区间。 接着我再去第一棵树上进行。 我...

题目大意 初始你有两个长度为的序列。 序列满足下面的要求：。接下来你有三种操作： 把赋值成。 把这一段区间全部按位取反，即互换。 求在这个区间中必选构成的最长不下降子序列，假设为，那么我们取出构成一个串，这个串中有多少个交接处就是这个区间的答案，你需要回答这样的操作答案是多少？ 操作最多有个。 Solution 考点：线段树区间合并 如果有写过用线段树维护最大连续子段和的读者可能会更好的理解这篇题解。 我们先看操作都是线段树的基础操作了，单点更新区间修改，打上标记即可，我们重点关注操作。 我们如何快速的找到区间的最长不下降子序列呢？ 首先我们把区间映射到线段树的区间上去看，对于线段树节点维...