Codeforces Round 895 (Div. 3)（A-G）思路讲解（上学文字版）

开头介绍：这场比赛感觉还不错，本人写出来前六题，最后一题确实想歪了。首先前面的题目很正常，属于是标准的div3题目。

然后到e题，很多同学刚看到e题一般都会认为是什么线段树之类的维护更新，这确实可以做，但是div3一般不会这么早让你去用线段树，所以可以往简单的方向考虑。

然后f题是一个基环树那种感觉，只要找到环就很好做。

最后这个g题，乍一看感觉很难，但是其实是一个诈骗题目。

A题：

题目大意：现在有两个容量无限的杯子1,2，还有一个容量为c的杯子3，杯子1中装有克水，杯子2装有克水，杯子3中开始无水，现在告知你的值，你可以进行一个操作，操作描述为下：

1. 选择克水，，注意可以不为整数。

2. 将升水从一个杯子移动到另外一个杯子里面。

请计算最少需要多少步操作，才能使得杯子1和杯子2中的水相等。

输入描述：第一行输出，含义见题面介绍。

输出描述：输出最少的操作次数。

（实际上杯子3是中转用的，不过我也不清楚为什么都可以随便选择倒多少了，还搞个杯子出来，反正题目也不是我出的（doge））

思路分析：

可以发现，每次操作使得两边杯子的差值变化最大为，如果差值少于2*c的话那我们可以通过一次操作去解决，因为移动的水可以不是整数，那么一次取一半，一定可以使得平衡。

代码部分：

B题：

题目大意：现在有个走廊，从坐标1开始到无穷远处，每在坐标上移动一个位置便会过去一秒钟，你的目标是走的尽可能远，然后再返回1点，现在有个陷阱，第个陷阱的位置为，然后在经过该陷阱的秒之后，会将陷阱所放置的位置直接封死，即不可以通过。

请计算出你从1位置开始，最远可以走到哪一个位置。

输入描述：第一行输出描述陷阱的数量，之后的行，每行输入。

输出描述：输出可以到达的最远位置。

思路分析：

首先我们可以发现，陷阱之间是独立的，只有我们到达陷阱之后，陷阱才会启动，而且每个陷阱的触发时间决定了我们应该什么时候回到这个位置，所以我们可以算出来每个陷阱最远可以到达哪里，然后再选择最近的那个点，因为不能跑更远了。

代码部分：

C题：

题目大意：给你，现在你需要找到，满足一下要求：

1、

2、

若a,b有多组答案，你可以输出其中任意一种，若不存在解输出-1。

输入描述：第一行输入和，含义如上文。，最多500组测试样例

输出描述：请输出一组和作为答案。

思路分析：

分类讨论做法：我们可以发现对于一个偶数，我们可以选择这个偶数，然后在选择2，这样得到的gcd就是2，那么这样的组合只要存在一个大于4的偶数，我们就可以凑出来，显然当和都小于4的时候，肯定无解，而当时，一定可以找到一个大于4的偶数，那么剩下就是l和r相同的情况，我们可以将其分解因子去找到答案。

暴力做法：我们其实不用去慢慢分析答案，可以直接枚举中的数字，由于大于4的偶数一定可以分解，所以可以发现这样的枚举最多枚举两个，哪怕小于4，那么枚举到4实际上就可以算出答案了，那么我们可以枚举数字，然后分解因子，找到答案就输出。

代码部分：

分类讨论：

暴力做法：

D题：

题目大意：给你，现在你需要计算：

用语言描述，就是所有下标为的值总和减去所有下标为的值总和。你需要找到一个排列，使得这样得到的结果，答案尽可能大。

输入描述：第一行输出，其含义见上文。，最多1e4组测试样例

输出描述：输出你可以得到的最大值。

思路分析：

可以发现对于数组中有多少个被加的值，有多少个被减的值我们都知道，那么实际上我们也可以算出来有多少个是同样被加被减的，这些值无影响，然后剩下的加值尽可能大，减值尽可能小。可以计算得到是增加的值，是减少的值，是又增加减少的值，注意在计算答案的时候需要用等差数列的求和公式，直接暴力添加时间会超时。

注：lcm为最小公倍数

代码部分：

E题：

题目大意：给你一个长度为的数组，然后你得到一个01字符串，然后有q次询问，询问类型分为两种：

1、，将之间的字符串全部翻转，指0变为1，1变为0。

2、，若等于0，则需要输出值为0的下标对应的中值的异或和，同理，等于1也是一样。

输入描述：第一行输出表示数组长度，第二行输出数组，第三行输出01字符串，第四行输出询问次数，后续行输出询问内容。

输出描述，对于询问中每个计算询问，输出答案。

样例解释可以去看原题，解释部分所占篇幅较多。

思路分析：

这题有疑问的同学很多，我们来说一下这题的想法是怎么想出来的。

首先我们忽略复杂度考虑一下暴力做法的过程，我们以计算0的异或和为例子，首先每次更新我们从更新的区间中找到0的位置，然后往0的异或和中删除当前0位置这个点的贡献，然后将当前点变为1，再将当前点的贡献加给1的异或和。那么计算1的异或和也是一样的，这个每次更新的时间复杂度为O(n)。

那么显然上述的做法是一个n2的做法不足够通过这道题目，那么问题来到了如何优化这个区间更新，常有的区间查询数据结构有线段树，我们考虑通过用线段树去维护区间中0和1的异或和，然后在更新的时候添加的时候0的给1,1的给0，再消除之前的影响，那么这个过程可以使用懒标记来节省时间，总体复杂度为O(logn)，那么这样子的做法是足够解决问题的。

最后来到了最快的做法，异或前缀和。首先我们得要理解前面暴力和线段树部分对答案进行的操作，我们可以发现一个区间中1的异或和在翻转后不仅要添加给0的异或和，还要添加给1的异或和。为什么呢？因为这段区间1的异或和需要被消除，好比现在这个区间1的异或和是，但是这个同样存在1的异或和这个答案里面，他没有被删去，而考虑到异或有着的性质，所以我们可以直接把这个异或到1异或和的答案里面去消除这个影响。现在我们其实就发现，我们不需要理清楚一个区间内到底谁是1，谁是0，理由也就是上述的样子，因为不存在要添加，需要加进来异或，存在的话要消除，也需要加进来异或，所以我们只用知道区间的异或和为多少就好，那么这个做法是O(1)的更新，可以很快速地解决问题。

代码部分：

F题：

题目大意：现在动物园一共有n个动物，每个动物都有自己害怕的天敌，当然一个自己的天敌的天敌也可能是自己。但是动物园破产了，需要卖出所有的动物，那么自然每个动物都有自己的价格，现在规定如果你卖出一个动物，该动物的天敌还在动物园里面，那么该动物会卖出双倍价钱也就是，现在你需要找到使得动物园收益最高的卖动物顺序。

输入描述：第一行输入n，第二行输出数组，代表第个动物害怕的天敌，第三行输出数组，代表第个动物的价格。

输出描述：输出一个答案代表最多动物园可以获得的钱。

思路分析：首先我们发现一共有n个点，以及n个边，那么这样的图我们称为基环树，这种树一般长这个样子。

这种树一般是有个环，然后环上的每个点会有一个子树。

由于这题没有规定所有的天敌关系形成一个图，所以这个题目的天敌关系是多个基环树，然后再思考我们要求得的答案，我们发现，每一个叶子节点，在卖出的时候一定可以卖到双倍价格，这其实我们就可以做一个拓扑排序，然后我们最终会得到一个环。然后我们考虑环从哪一个点出发，我们发现最后卖出的点一定没法卖出双倍价格，而其他的点都可以卖出最高价格，所以我们可以找到环中最小的点，然后找到卖出方式。

注：拓扑排序是十分重要的知识点，算法在于找到所有没有入度的点，然后计算，然后删除有关这个点的边，在重复上述操作。

代码部分：

用了jiangly大佬的代码，我自己的代码写的很冗余，写了三遍while循环。

如果大家不知道内部函数怎么开的话，可以看看这个实现的过程，其实所有代码都是删叶子节点，找环上最小点，然后拆掉整个环。

G题：

题目大意：给你一个长度为的数组，然后你进行一次操作，操作描述为：

1、选择，然后区间中的所有值，全部相乘得到。

2、将剩余没有被选择的值全部相加得到。

3、。

要求请输出操作的区间，使得我们得到的值最大，如果有多个区间，可以输出任意一种。

输入描述：第一行输入，第二行输入数组，。

输出描述：请输出使得答案最大的区间，若有多组可以输出任意一组。

例子解释：

思路分析：

首先直觉的感受，1这个数字很重要，因为乘1不会改变答案，那么我们可以发现两端的连续1一定是不会在相乘区间的，因为不改变区间答案，还让答案最后少加了几个1。然后继续思考问题，我们考虑非1点，显然非1点只要有20个就能很容易打到2e5这个值，这个时候一定是要让所有非1点都乘起来的，因为乘起来的增加的答案远比中间浪费的几个1提供的多，我们特判掉这种情况，之后就可以发现剩下的情况非1点一定很少，最多也就20个左右，那么考虑一下暴力做法，每次的左右区间边界一定是这20个点的下标，那么我们可以考虑直接枚举出所有答案去比较计算。

代码部分：