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就是根ans9入栈下一个数8满足弹出条件栈顶9弹出现在栈又空了那么8就是根ans8入栈下一个数9不满足弹出条件栈顶8不弹出此时栈不空说明9是8的儿子9入栈下一个数2满足弹出条件栈顶9弹出此时栈未空继续判断又满足栈顶8弹出此时栈空ans2入栈下一个数字3入栈4入栈4弹出栈顶44入栈5入栈3弹出栈顶5继续弹出栈顶43然后不满足3入栈。就是3根先后为982。CF2175B XOR Array我以为只要在l与r之间的数相等就好了但是这个理解是错误的这样并不能满足题目的要求就是lr之间某些值异或就会为零矛盾。我们真正要满足的是只有l到r之间异或和为0其他所有非空子集异或和都不为0。正确的思路应该是用前缀异或和去做令pi等于a1异或a2一直到ai那么al异或到ar就可以用pl-1异或pr来表示所以就相当于构造pl-1与pr相等其他不等。这里有可能l-1等于0所以这种情况我们分出来看当l1的时候p0等于0此时pr也要等于0。其余不等于0即可。然后当l大于1的时候只要令那两个位置都是n1然后剩下第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-gf的本质就是有几条边而g的本质是环中的定点数量。我的思路方向是对的但是我对f的理解出现了问题。正确的理解应该是f是区间并覆盖的长度。所以正确的贪心思路应该是选择所有边删掉那些不会改变f值但是会破坏环的边。问题来了那么我们该如何确定删掉这条边会破坏这个环其实删除与不加入是一致的我们只要在加入这条边的时候做一个并查集的判断即可。那么不加入的边不会影响我们的f吗我的理解是我们删掉的边都是环中一边触及不到边界所以f的值不变。在写代码的时候有个细节需要注意输出ans数组的时候循环器的边界不是n因为我删了一些边正确的应该是size。CF2124C Subset Multiplication这有道翻译真是明明是ai整除ai1翻译成除以真是抽象。但是我还是搞不太懂这漂亮数组到底是钱一个数是后一个数的倍数还是反过来还有bob不是嫉妒alice那输入的数组是不是应该都不是漂亮数组。题解思路我想了个大概因为漂亮数组的后一位一定是前一位的倍数也就是ai×kai1。当题目给我们的数组里出现这个位置 i 的数被后面的数取mod不等于0的时候说明这个位置是被bob改动过的并且我们可以用bi与bi1求出这个x。说明ai✖xbi而bi1肯定是没动过的所以bi1ai1ai✖kk表示漂亮数组中前后数的倍数关系系数。根据以上等式我们可以转化因数要求x我们要将bi拆开bi由ai与x组成所以我们要让bi除以bi与bi1的最大公因数gcd这样能得出x的一个因数不是x是r我们无法直接得出x需要构造知道x的一个因子了那我们不妨如法炮制将数组中的所有像这样的数对都计算出来然后求所有r的最小公倍数。此为最优解。还有一些补充为什么bi除以bi和bi1的最大公因数就是x的因子其实是我上面得出等式后没有写完再在上面补充实属冗余故另起一行。我们将式子的bi用ai✖x替换bi1用ai✖k替换那么式子就变成了ai✖x/gcdai✖xai✖kai在gcd中可以提取出来与分子中的ai约分故式子只剩x/gcdxk。又因为gcdxk肯定能整除x所以这个式子的值一定是整数并且为x的一个因子。还有就是得出最终答案之前还有一步虽然我说了就是取所有r的最小公倍数但是这里也是涉及到知识点的就是最小公倍数的公式lcmaba✖b/gcdab。完结。CF2200D Portal这道题我有一个很大的疑问点就是判断字典最小是咋判断的呢据我观察两者之间能比较的只有当i位置与1之间的某个位置j使得aj等于bj然后i位置上元素比较小的那个数组为字典较小。可是这么严格的条件该怎么判断这个组合是所有组合中最小的那一个呢我对字典最小数组的定义理解没错但是我思考问题的角度不对正确的思考角度是我们会有一次操作使得这个排列字典最小所以我们应该用贪心的思路去构造一个最小排列思考这样一个问题加入有这么些个空位我们应该在第一位填什么才能使其最小当然是最小的数例如从35里选填我们选3就可以在第一步取得更小的字典。但是这题的关键不是在这里真正的关键是这题的排序方式比较特殊一个数组被传送门分为三个部分。然后两个部分有各自的特征在传送门的两侧不包含传送门之间的数组的顺序不能改变。然后就是传送门之间的数组他们的性质是他们可以循环变化就是将最左边的数移到最右边可以重复多次这样的操作或是将最右边的数移到最左边。这样的性质可以帮助我们解决问题。因为我们要使得数组的字典最小贪心地认为前面的数字尽可能得小。那么我们要做的就是在性质的限制之下找到这个这个位置可达到的最小值。我的思路是因为外围的顺序是不会改变的那么我们可以找到内部最小的数字然后将其作为中间数组的代表以其为首位重新以它前一个数作为末尾重新排列中间的序列。然后以这个代表去与外围的数进行比较现在左区间找找到第一个比这个代表大的数在这个数之前作个标记之后的重新排序的中间数组就放在这里右区间同理。有个细节需要注意在左区间发现的就就让它呆在左区间右边就呆在右边。也就是说我们输出的时候最好是左右分开输出这样不容易出错否则一不小心就会出现边界错误的问题。CF2119C A Good Problem这道题要我们灵活运用xor以及的性质我应该就是受困于此我们知道xor算法就像是不进位的二进制加法那么如果奇数个一样的数异或那么这个结果会等于原先的数而运算只有当两个数这个位置都是1的时候才是1所以如果数组所有数一样那么他们运算后的结果也就不变。所以n为奇数的情况就显而易见了我们只需让数组所有数都等于l即可。偶数情况的话我看完题解再根据样例6688我对此也有了理解。6的二进制01108的二进制1000。有什么样的特征最后两个数前面的数两两相等最后两个数相等并且他们的二进制与前面最大数的二进制也有一定的关系首先他们应该只有一个1这个1的位置恰好在前面最大数的前导零上。为什么这样是最优解当数组所有数都相等的时候他们的xor就等于零但是他们的不等于零与题目的要求矛盾。所以我们需要做出改变这个改变不会改变xor的值但是可以让等于零我们可以直接将最后两个数变成零这样xor的值不会变而的值会等于零但是这种情况不一定满足所以我们可以在零前面加个1因为这个1只有后面两个数到达所以前面所有数在这位的只能是0所以加了1后最后的结果还是零成立。有些地方需要补充第二段中为什么选最后两位这其实与贪心也有关系因为我们要使得字典最小那么我们应该让前面的数尽可能多的等于ll是数组最小值所以我们只改变最后两个数是为了满足贪心思路。代码里有一个新的知识点我觉得挺有用的—— __builtin_clzll() 。这个方法可以判断long long也就是64位括号里的数有多少零在这题的作用是判断t是否可以在lr之间妙哉。CF2108B SUMdamental Decomposition这道题我的问题主要是代码的问题题目的思路我懂了你真的懂了吗但是代码里的情况分类的逻辑完全不对。题目的思路主要是根据x中1的个数进行分类。x等于0的话如果n为偶数那么答案就是n如果n是奇数n是1则无解若不是则答案为n3。若x大于0当x等于1时若n为奇数答案就是n若n为偶数答案则是n3。当x大于1统计x的二进制中1的个数比如说43二进制为1010111的数量为4相当于32、8、4、2这四个数异或就是42。那么如果n小于等于这个数量那么就可以将这些二进制分配进n个数中那么答案和就是x。假如n大于cnt那么还差n-cnt如果这个值是个偶数那么答案就是xn-cnt因为在二进制一位放入偶数个1并不改变数组异或和并且这个方法是最小的办法。若n-cnt是个奇数那么就要在xn-cnt的基础上多付出1的值也就是xn-cnt1为什么当n-cnt为奇数的时候要多加1把问题留给以后的我。接下来盘点代码的问题。我的代码核心问题就是没有依据x中1的数量这一方向来分类。其他我基本都在点上。CF2196A Game with a Fraction我看完这题我发现了一个规律首先我们要使p2/3q也就是说我们要使得3p2q。这时候进行p--的操作那么获得的贡献值为3p-3q同理。那么我就将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的获胜条件可以说成p0q1虽然这是结束的条件。所以说当d大于p的时候我们会发现在到达0之前p已经为0了Alice win。所以要使得bob取胜d还要小于p。然后根据左右边界推导出p小于q3p大于等于2q。