企业官网建设流程全解析

CF2201A1 Lost Civilization (Easy Version)

第一眼，哇，这题好简单，WA了，题目错了吧。还是嫩了点啊。我的思路是将连续的相邻自然数归为一组，求组数，但是实际上就算中间隔了一组数，前后依旧有可能有父子关系。举个例子，样例1中的最后一个就是很好的例子。9 8 9 2 3 4 4 5 3，末尾的3与第四个数2，其实也有父子关系，就是2其实也是3的根，只要我们把中间的45合并了就可直观的看出了。

所以这体的正确思路应该是，构造一片树林，这个位置的元素只可能是跟或者前面根的儿子，那么我们就可以用栈来模拟这篇森林形成的过程，在这个过程中，我们统计根的数量，就是答案。

遍历每个值，x，当栈不空且x-1与栈顶的值不相等时，说明这个栈顶不是x的根，需要弹出。当这个栈空时，说明这个数时根，反之这个数时根的儿子。

用样例1的最后一片森林来证明，第一个数9，此时栈空，那么9就是根，ans++，9入栈；下一个数8，满足弹出条件，栈顶9弹出，现在栈又空了，那么8就是根，ans++，8入栈；下一个数9，不满足弹出条件，栈顶8不弹出，此时栈不空，说明9是8的儿子，9入栈；下一个数2，满足弹出条件，栈顶9弹出，此时栈未空，继续判断，又满足，栈顶8弹出，此时栈空，ans++，2入栈；下一个数字3，入栈；4入栈；4，弹出栈顶4，4入栈；5入栈；3，弹出栈顶5，继续弹出栈顶4，3，然后不满足，3入栈。就是3，根先后为9，8，2。

CF2175B XOR Array

我以为只要在l与r之间的数相等就好了，但是，这个理解是错误的，这样并不能满足题目的要求，就是l，r之间某些值异或就会为零，矛盾。

我们真正要满足的是只有l到r之间异或和为0，其他所有非空子集异或和都不为0。正确的思路应该是用前缀异或和去做，令pi等于a1异或a2一直到ai，那么al异或到ar就可以用pl-1异或pr来表示，所以就相当于构造pl-1与pr相等，其他不等。

这里有可能l-1等于0，所以这种情况我们分出来看，当l=1的时候，p0等于0此时pr也要等于0。其余不等于0即可。然后当l大于1的时候，只要令那两个位置都是n+1，然后剩下，第i个位置等于i好就好。

CF2165A Cyclic Merging

题目的意思我看懂了，在一个环形的数组里，环形就意味着an与a1是相邻的，这题要做的事情是减少数组长度，直到剩下1个数，所以操作的次数为n-1次。具体的操作是找到两个数个数，用较大的替换，代价加上这个数。所以我们要使代价最小的话，贪心思路应该是，每次找到数组中最小的数，然后比较其相邻两个数，令较小的那个为y，我一开始的思路也是这样，我是从样例中看出的，计算一个样例，然后从中找到规律。

将思路转化为代码的过程我就卡住了。因为，代码中要用到小根堆和环形链表，这些我练的都比较少。代码可行性的证明，环形链表可以让我们快速找到数组中的最小值，贪心的思路是找到最小值之后再找到相邻的较小值与他合并。环在不停的变化，最小值也有可能变化，所以我们需要一个东西帮助我们快速找到这个最小值，小根堆正好可以。

CF2143C Max Tree

要是我对树更加了解，也不至于一点思路也没有，我我甚至不知道这个树的顶点怎么规划，样例中，三角形说不通，直线型也说不通。而且这个关联值我也不理解有什么作用，树的节点上的数不是我定的吗，从序列p中选择吗？

因为，这道题的图形，没有方向，没有环形，因此我们不妨用拓扑来做，拓扑是什么，利用队列，让初始入度等于零的的点入队，每次将第一个点加入顺序排列order，然后将这个点周围的点入度减一，若减为零一样加入排序。这样就像是先修课，要想学这门课，如果有要先修的课程，那么就得先修那门课，就像是这题里的入度，只有入度为零才能加入排序，若不是则需要减去n。这也就说明了拓扑在这题里的正确性。得到order序列之后，按照先后顺序，给值n，第二个给值n-1，以此类推，最后输出即可。

这么做还要加上一个细节，要规定树枝的方向，依据就是x和y的大小，因为要使得贡献之和最大，所以，当x大于y时，我们要令u指向v，也就是让u排前面，若是y大于x，俺么我们就要令v排在前面。正确性证明，这样排序，可以确保每条边的贡献值都是最大的。

CF2129A Double Perspective

对于这题，我的想法是对每一条边尽量都选，然后不选那些会形成环的。因为题目要我们求最大的f-g，f的本质就是有几条边，而g的本质是环中的定点数量。

我的思路方向是对的，但是我对f的理解出现了问题。正确的理解应该是，f是区间并覆盖的长度。所以正确的贪心思路应该是选择所有边，删掉那些不会改变f值但是会破坏环的边。

问题来了，那么我们该如何确定删掉这条边会破坏这个环，其实删除与不加入是一致的，我们只要在加入这条边的时候做一个并查集的判断即可。那么不加入的边不会影响我们的f吗？我的理解是我们删掉的边都是环中一边，触及不到边界，所以f的值不变。

在写代码的时候，有个细节需要注意，输出ans数组的时候，循环器的边界不是n，因为我删了一些边，正确的应该是size（）。

CF2124C Subset Multiplication

这有道翻译真是，明明是ai整除ai+1，翻译成除以，真是抽象。

但是我还是搞不太懂，这漂亮数组，到底是钱一个数是后一个数的倍数，还是反过来，还有，bob不是嫉妒alice，那输入的数组是不是应该都不是漂亮数组。题解思路我想了个大概，因为漂亮数组的后一位一定是前一位的倍数，也就是ai×k=ai+1。当题目给我们的数组里出现这个位置 i 的数被后面的数取mod不等于0的时候，说明这个位置是被bob改动过的，并且我们可以用bi与bi+1求出这个x。说明ai✖x=bi，而bi+1肯定是没动过的，所以bi+1=ai+1=ai✖k（k表示漂亮数组中前后数的倍数关系系数）。根据以上等式，我们可以转化因数，要求x，我们要将bi拆开，bi由ai与x组成，所以我们要让bi除以bi与bi+1的最大公因数（gcd），这样能得出x的一个因数（不是x，是r），我们无法直接得出x，需要构造，知道x的一个因子了，那我们不妨如法炮制，将数组中的所有像这样的数对都计算出来，然后求所有r的最小公倍数。此为最优解。

还有一些补充，为什么bi除以bi和bi+1的最大公因数就是x的因子？其实是我上面得出等式后没有写完，再在上面补充实属冗余，故另起一行。我们将式子的bi用ai✖x替换，bi+1用ai✖k替换，那么式子就变成了，ai✖x/gcd（ai✖x，ai✖k），ai在gcd中可以提取出来与分子中的ai约分，故式子只剩x/gcd（x，k）。又因为gcd（x，k）肯定能整除x，所以这个式子的值一定是整数，并且为x的一个因子。还有就是得出最终答案之前还有一步，虽然，我说了，就是取所有r的最小公倍数，但是这里也是涉及到知识点的，就是最小公倍数的公式，lcm（a，b）=a✖b/gcd（a，b）。完结。

CF2200D Portal

这道题我有一个很大的疑问点，就是判断字典最小是咋判断的呢？据我观察，两者之间能比较的只有当i位置与1之间的某个位置j，使得aj等于bj，然后i位置上元素比较小的那个数组为字典较小。可是这么严格的条件，该怎么判断这个组合是所有组合中最小的那一个呢？

我对字典最小数组的定义理解没错，但是我思考问题的角度不对，正确的思考角度是我们会有一次操作使得这个排列字典最小，所以我们应该用贪心的思路去构造一个最小排列，思考这样一个问题，加入有这么些个空位，我们应该在第一位填什么才能使其最小，当然是最小的数，例如从3，5里选填，我们选3，就可以在第一步取得更小的字典。

但是这题的关键不是在这里，真正的关键是这题的排序方式比较特殊，一个数组被传送门分为三个部分。然后两个部分有各自的特征，在传送门的两侧，不包含传送门之间的数组的顺序不能改变。然后就是传送门之间的数组，他们的性质是他们可以循环变化，就是将最左边的数移到最右边，可以重复多次这样的操作或是将最右边的数移到最左边。这样的性质可以帮助我们解决问题。

因为我们要使得数组的字典最小，贪心地认为前面的数字尽可能得小。那么我们要做的就是在性质的限制之下，找到这个这个位置可达到的最小值。我的思路是，因为外围的顺序是不会改变的，那么我们可以找到内部最小的数字然后将其作为中间数组的代表，以其为首位重新，以它前一个数作为末尾，重新排列中间的序列。然后以这个代表去与外围的数进行比较，现在左区间找，找到第一个比这个代表大的数，在这个数之前作个标记，之后的重新排序的中间数组就放在这里，右区间同理。有个细节需要注意，在左区间发现的就就让它呆在左区间，右边就呆在右边。也就是说，我们输出的时候最好是左右分开输出，这样不容易出错，否则一不小心就会出现边界错误的问题。

CF2119C A Good Problem

这道题要我们灵活运用xor以及&的性质，我应该就是受困于此，我们知道，xor算法就像是不进位的二进制加法，那么如果奇数个一样的数异或，那么这个结果会等于原先的数，而&运算只有当两个数这个位置都是1的时候才是1，所以如果数组所有数一样，那么他们&运算后的结果也就不变。所以n为奇数的情况就显而易见了，我们只需让数组所有数都等于l即可。

偶数情况的话，我看完题解，再根据样例6688，我对此也有了理解。6的二进制：0110，8的二进制：1000。有什么样的特征，最后两个数前面的数两两相等，最后两个数相等，并且他们的二进制与前面最大数的二进制也有一定的关系，首先，他们应该只有一个1，这个1的位置恰好在前面最大数的前导零上。为什么这样是最优解？当数组所有数都相等的时候，他们的xor就等于零，但是他们的&不等于零，与题目的要求矛盾。所以我们需要做出改变，这个改变不会改变xor的值，但是可以让&等于零，我们可以直接将最后两个数变成零，这样xor的值不会变，而&的值会等于零，但是这种情况不一定满足，所以我们可以在零前面加个1，因为这个1只有后面两个数到达，所以前面所有数在这位的&只能是0，所以加了1后&最后的结果还是零，成立。

有些地方需要补充，第二段中为什么选最后两位，这其实与贪心也有关系，因为我们要使得字典最小，那么我们应该让前面的数尽可能多的等于l（l是数组最小值），所以我们只改变最后两个数是为了满足贪心思路。

代码里有一个新的知识点我觉得挺有用的——" __builtin_clzll() "。这个方法可以判断long long（也就是64位）括号里的数有多少零，在这题的作用是判断t是否可以在l，r之间，妙哉。

CF2108B SUMdamental Decomposition

这道题我的问题主要是代码的问题，题目的思路我懂了，（你真的懂了吗）但是代码里的情况分类的逻辑完全不对。题目的思路主要是根据x中1的个数进行分类。x等于0的话，如果n为偶数，那么答案就是n，如果n是奇数，n是1则无解，若不是，则答案为n+3。若x大于0，当x等于1时，若n为奇数，答案就是n，若n为偶数，答案则是n+3。当x大于1，统计x的二进制中1的个数，比如说43，二进制为101011，1的数量为4，相当于32、8、4、2，这四个数异或就是42。那么如果n小于等于这个数量，那么就可以将这些二进制分配进n个数中，那么答案，和就是x。假如，n大于cnt，那么还差n-cnt，如果这个值是个偶数，那么答案就是x+n-cnt，因为在二进制一位放入偶数个1并不改变数组异或和，并且这个方法是最小的办法。若n-cnt是个奇数，那么就要在x+n-cnt的基础上多付出1的值，也就是x+n-cnt+1，为什么当n-cnt为奇数的时候要多加1？把问题留给以后的我。

接下来盘点代码的问题。我的代码核心问题就是没有依据x中1的数量这一方向来分类。其他我基本都在点上。

CF2196A Game with a Fraction

我看完这题，我发现了一个规律，首先我们要使p=2/3q，也就是说我们要使得3p=2q。这时候进行p--的操作，那么获得的贡献值为3p-3，q同理。那么我就将p和q一开始×3、×2，然后，bob和alice都可以对这两个数进行-3-2，然后alice为了使差距更大会选择更小的那一个减，已达到拉开差距的目的，然后bob则要缩小差距，所以我认为如果初始差距小于3，那么bob一定能缩小差距。

虽然我的思路触及博弈论，但是我这样太模糊了导致我最后的判断错误，差距小于3的范围太小。那我们该怎么做？题解给出了方案，令d为3p-2q。这样的话，问题就变成了，bob要是d变成0，而alice要阻止。这样又有什么效果，此时如果对p--，那么d会-3，若q--，则d会+2。那么Alice对任意操作都离不开d的-3或+2，下一轮，Bob只要对另一个数进行操作，那么经过两轮后d必定-1，也就是说d有向零的趋势，所以只要d大于等于0，那么bob就有可能win。有可能？对的，因为只有大于等于0，还是不够，Alice的获胜条件可以说成p=0，q=1，虽然这是结束的条件。所以说，当d大于p的时候，我们会发现在到达0之前p已经为0了，Alice win。所以要使得bob取胜，d还要小于p。然后根据左右边界推导出p小于q，3p大于等于2q。