题目大意 你有一张个点条边的无向联通图，现在对于图中的连通分量产生的价值做出如下定义。 如果一个联通分量里面点的个数是偶数那么它的价值就是里面每个点权的和。 如果一个连通分量里面点的个数是奇数那么他的价值就是里面每个点权的和的相反数。 保证每个点的点权。 你现在可以选择一个点把它删去，并且它连的边也一并删去，问进行删除任意多个点之后整张图的权值和最大是多少？ Solution 考点：求割点 首先可以知道，当是偶数的时候，我们不需要进行删点，直接输出就行了。 当是奇数的时候，结论是只需要删掉最多一个点，接下来我们稍微验证一下这个结论。 首先我们去找不是割点的点，这些点是可以随意删除的，删掉它不会...

题目大意 小兔子在一个二维的格点图中跳跃，每次它都会沿着正负方向共个方向移动个单位长度。 现在地图中有个陷阱，陷阱是以矩阵的方式存在的，问你有没有一种方法让小兔子在某个起点随意乱跳的情况下都不会掉入任何一个陷阱，你要输出这个起点，或者。 Solution 考点：线段树维护扫描线 首先由于地图本质上是无穷大的，但是对于这样的任意一个矩阵来说，由于小兔子的步长一定为，所以都一定可以离散到这样的初始矩阵中，所以我们按照覆盖关系可以将个陷阱离散到初始矩阵里面，接下来就是要去这个初始矩阵里面找是不是有那个格点它没有被任何一个矩阵覆盖，如果我们固定轴那么轴就变成了一个扫描线问题。 但是显而易见的，如果我们...

题目大意 你有个汉堡代煎，每个汉堡要被煎制分钟，你现在只有口锅，每个汉堡可以分两次煎制也可以一次煎完。问完成块汉堡全部的煎制最小的完成时间是多少？ Solution 考点：思维题 因为你只有口锅，并且所有汉堡需要煎制的时间也给你了，那么你就可以知道对于工作时间最长的一口锅而言，它需要工作的最长时间。 首先，我们最小的完成时间都应该是，也就是对于锅而言最小的最长时间。 但是我们可以感觉到这个最长时间不一定就是锅的工作时间，例如，那么就一定有但是很显然这个式子是错误的，所以我们选择的最长工作时间是不一定是正确的，但是我们可以解出当前模式下的最大值应该是。 那么我们知道了每口锅需要工作的最大时间，那...

B、Boxes 题目大意 你有个盒子，每个盒子内存在可能有黑球和白球中的一种，打开每个盒子都有一个代价，你还有一次询问裁判的机会，当然询问裁判代价为，你需要告诉裁判这个盒子每个盒子里面的球颜色，你需要花费的最小代价是多少？ Solution 考点：思维 首先我们不询问裁判的话，我们就要把个盒子全部打开，代价为 如果我们询问裁判，那么想想我们是不是最多只需要打开个盒子，并且如果用代表白球代表黑球如下分析。 考虑开次盒子结束，如果裁判告诉我们有个白球或者个黑球用二进制表示那就是或这样的时候结束，那么我们这次代价就只有。 考虑开次盒子结束，那么我们要先开最小花费的那个，并且结束的要求是或者，并且还需...

题目大意 给你长度为的序列，并且有次查询，每次查询给出一个，询问在中有多少个区间的最大值减掉最小值严格大于。 Solution 考点：双指针+表 考虑到区间不会修改，那么查找区间最值这个问题就用表维护就可以。 然后再看最大值减掉最小值严格大于，如果在这个区间符合要求，那么是不是在这些右区间都是合法的，因为随着数的加入，区间最大值一定不会变小，区间最小值一定不会变大，所以并不会变得不符合要求。 那么我们从左到右枚举，可以看出这个也是单调的，我们用表维护这个就可以了。 时间复杂度。 const int N = 1e5 + 7; int st1[N][21], st2[N][21], Log2[N...

题目大意 给你，你要让的前提下，最小的是什么，并且给出的是分解质因数的形式，。 Solution 考点：二进制枚举 看到这个给的这么形式化，就要围绕这个去弄，而且幂次之和不超过，很明显的让我们去二进制枚举。 那么我们就可以暴力的预处理出当前状态，可以的全部花费，那么要更新还有一个前提，就是之前的最起码应该大于，才可以更新前半部分，大于才可以更新后半部分，我们这样暴力乱搞之后对于花费大于的全部状态的最小花费都可以找出来。 接下来我们只需要再把这些东西的子集更新一下，注意因为我们乱搞的时候有一个的条件，可能这个状态就无法大于等于，这时候保留的仍然是一个无穷大的值，但是我们用这个状态更新应该可以由...

题目大意 按逆时针给出凸包上的个点，你要在凸包里面找到一个点，让的最小值最大，然后输出这个最大的最小值。 Solution 考点：三分 比较明显的容易发现如果我们固定，那么的相关函数一定是一个单峰函数。 同理固定，那么的相关函数也一定是单峰函数。 那么就直接用三分套三分就可以求解了，复杂度。 const int INF = 0x3f3f3f3f; const int N = 100 + 7; const double PI = acos(-1); ll n, m; pai p[N]; double xmax = -INF, xmin = INF, ymax = -INF, ymin = IN...

题目大意 给你两个字符串，长度在级别，询问在两者的全部子序列中，长度相等，并且的数量有多少个？ Solution 考点：相同子序列数量 如果直接考虑，因为子序列并不知道第几个位置不同，所以这个并不好处理，但是我们一定可以把这个的子序列分成段。 第一段：子序列前个字符都相同。 第二段： 第三段：剩余长度任意挑选子序列。 先考虑如何求解任意两个位置相同子序列数量，这个用动态规划处理。 我们用代表以前个字符，前个字符的相同子序列数量，那么我们可以写出下面的转移方程。 当的时候减掉的是重复计算的，当的时候加上的是一定选他们结尾的时候前面相同的，加上前面一个不选。 好了我们已经预处理出了数组了，下面就...

题目大意 你和对手进行乒乓球比赛，你们原本进行了局比赛，代表你赢下了第局，代表你输掉了第局。 现在我可以操控这个比赛规则，让游戏赛制变成在赢下球制，也就是我在赢下球后，如果和对手比分差值大于等于我就拿下一个小分，否则就是对手拿下一个小分，如果差值为或者那么接着进行下一局，那么我在球赛制下，进行完局比赛我能赢得的小分用表示。 题目求 Solution 考点：预处理模拟题 首先我们可以预处理出从这些位置里面有多少个和多少个，这样用前缀和的形式就可以找到任意区间内和的数量。 并且我们可以知道第个出现的下标在哪里，以及第个出现的下标在哪里。 那么当我们枚举这个球赛制的时候，我们就可以知道上一次加小分的...

题目大意 你有个盒子，每个盒子内存在可能有黑球和白球中的一种，打开每个盒子都有一个代价，你还有一次询问裁判的机会，当然询问裁判代价为，你需要告诉裁判这个盒子每个盒子里面的球颜色，你需要花费的最小代价是多少？ Solution 考点：思维 首先我们不询问裁判的话，我们就要把个盒子全部打开，代价为 如果我们询问裁判，那么想想我们是不是最多只需要打开个盒子，并且如果用代表白球代表黑球如下分析。 考虑开次盒子结束，如果裁判告诉我们有个白球或者个黑球用二进制表示那就是或这样的时候结束，那么我们这次代价就只有。 考虑开次盒子结束，那么我们要先开最小花费的那个，并且结束的要求是或者，并且还需要对上裁判给你的...

B、Sample Game 题目大意 你有一个随机数生成器，他会随机生成到之间某个数，生成的概率为。 现在分为大体步操作： 随机生成一个。 如果这个​是已经生成的数中最大的，返回步骤一继续生成新的数，否则进入步骤三 游戏结束，本局游戏的得分为生成序列的长度的平方​。 现在要你求出这局游戏的得分期望。 Solution 考点：期望dp 这个期望不是很好求，我们优先考虑求出。 我们假设​​​是随机到​​​​后还能进行的期望抽取次数，那么我们知道​​，那么我们把之后的抽取分为​​​这三类，可以知道，抽到​​​之后就无法进行了这时候的期望次数就是​​​，如果抽到了相同的数​​​，这时候他带来的期望...

题目大意 题目重新定义了运算符： 并且给出长度为的，以及常数，定义 我们需要求解的异或和是多少？ Solution 参考题解 我们优先就要转换这个符号的定义，不然这个题目就没办法下手了。 从质因数幂次的关系转换到和他们对应之间的关系就更加容易处理这个关系式了。 那么我们重新写出的定义式 我们考虑枚举 这样由于最后一个求和条件还是涉及除法，我们再把这个除法消掉，我们设 然后可以发现最后面的可以提到前面去，最终把式子写成这样 计算答案的时候我们枚举，对于来说，可能的选择长度是，这个复杂度是，然后根据选择的，又可以确定的更新所以全部的都可以在的时间找到。 还需要注意的一点是，由于原先我们定...

题目大意 给出，你要构造的序列，对于其中一个序列来说他的贡献是，现在要你求出全部可能的序列贡献之和是多少？ Solution 考点：动态规划+容斥原理+组合数意义 我们首先要推出下面这样的一个式子，可以看出这是个球分成组的可能方案数，那么总的方案数就是，即每个球都可能在每一组。 好，我们回来看题目给出的式子，我们如果把看成一个整体带入我们刚刚上面推出的公式我们就会得到这样的式子。 但是很容易发现一个问题就是题目给出的范围是的但是我们公式的范围是的，这就会导致我们直接计算答案的话会出现很多非法的解，那么我们就要考虑把这些非法的解全部去掉，就要用到容斥原理了。 那么我们知道我们一共有组，那么...

题目大意 和两人在进行游戏，每轮游戏操作的玩家可以选择图中的一条边删去，或者找到图中的一棵树删去，最后无法进行操作的玩家就输掉了这局比赛，这张图是有个点条边的无向图。 Solution 我们分别考虑每个操作的势能函数（这个名词是讲题大佬直播的时候瞎编的）。 删边：，是删掉的点数，是删掉的边数，任何时候都为奇数。 删树：，可以看出任何时候也为奇数。 那么这局游戏双方轮流操作，每个人都只能选择或者，说明最终变成的操作次数是确定的，直接判断的奇偶性即可。 int solve() { n = read(), m = read(); return ((n + m) & 1); ...