6月杂题

代码康复训练2024.6.6.链接并查集板子。直接看代码。点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？打cf不要用umap！！！记住，rating是身外之物。该冲正解时冲正解！Problem:算法：思路：*/#include<b......

代码恢复2024.6.5。链接很简单。直接找循环节就行了。代码：点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？打cf不要用umap！！！记住，rating是身外之物。该冲正解时冲正解！Problem:算法：思路：*/#inc......

1.qoj8003Anti-Plagiarism不难想到dp，即\(dp_{x,a,b}\)表示第一棵树以\(x\)为根的子树能否和第二棵树中以\(a\)为根时\(b\)的子树匹配，其中\(a,b\)相邻。想想怎么转移，就是把子树的dp值算出来，然后对于\(x\)，枚举一对\(a,b\)，发现这里其实就是二分图匹配：右边的点是......

链接没啥好说的，直接看代码吧。点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？打cf不要用umap！！！记住，rating是身外之物。该冲正解时冲正解！Problem:算法：思路：*/#include<bits/stdc++.h>usingname......

链接(Link)一个好题。就是说，你直接先求出这个数列的异或和，然后发现之后就可以两两匹配，如果无法匹配就默认这个数为\(0\)，然后做完了。点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？打cf不要用umap！！！记住......

链接（luogu）链接（codeforces）有一个结论就是每次操作直接取一个存在目前最左边的最小值区间即可。但是我不会证啊......大家感性理解。点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？打cf不要用umap！！！记住，ra......

好题。直接上代码吧。点击查看代码/*Tips:你数组开小了吗？你MLE了吗？你觉得是贪心，是不是该想想dp？一个小时没调出来，是不是该考虑换题？打cf不要用umap！！！记住，rating是身外之物。该冲正解时冲正解！Problem:算法：思路：*/#include<bits/stdc++.h>usingnamespacest......

链接发现这东西就很根号分治。考虑两种情况：\(k\le1000\)，这部分直接用前缀和维护然后暴力做，时间复杂度\(O(kq)\)。\(k>1000\)，此时\(n\le500\)，这部分直接预处理答案，时间复杂度\(O(n^2k)\)。两个时间复杂度均正确，因此可以通过此题。代码：点击查看代码/*Tips......

题目链接CF1977B(luogu)CF1977B(codeforces)解题思路考虑通用做法。我们发现如果直接用二进制来表示的话这个数会只包含\(0,1\)这两个数字。发现这时阻碍我们构造的是连续的数字\(1\)。考虑消除连续的数字\(1\)。容易发现连续的数字\(1\)可以转化成将这一段最高位......

题目链接CF1977C(luogu)CF1977C(codeforces)解题思路首先这题有一个简单的思路，就是当这个序列的LCM大于\(10^9\)时，显然取所有数字数字是合法的。然后我们接下来考虑LCM小于等于\(10^9\)的情况。发现这种情况LCM很小，且有一个简单的结论，就是你在序列中任选一个子......