最近一段时间有点忙，先就补一道，剩余的以后再补啦 H.小鸡的排列构造 题干：给定组约束，构造一个长度的排列，满足对于每对约束，区间内的元素从小到大排序后，位于处的元素位置将会改变。特别地，对于每组测试，保证的奇偶性相同（？） 最后这句话赛时其实挺疑惑的，实在是想不出奇偶性与这题有什么联系。不过，可以肯定的是，奇偶性与该题的构造方法必定强相关，即区间长度全为奇数是一种构造，全为偶数则又是一种构造。 那么怎么构造这样的序列出来呢？如果一个个区间考虑，那这些区间的重叠等情况将会很不好处理，所以我们干脆直接将约束加到最强： 如果所有区间长度为偶数，则我们直接约束所有长度为的区间，必须保证这些区间中，每...

这场由于赛时写错暴力+思路出现偏差（看到区间问题下意识离线处理，结果根本不需要），致使自己在L题卡了太久，总体发挥不太好 L.Tokitsukaze and XOR-Triangle 给定两个长度皆为的数组，需要多次求解指定的. 首先对于位运算的题，拆位是必然的。我们可以先对于每个，求解区间的贡献。然后考虑，可以通过的贡献减去的贡献、再额外减去区间内与区间内产生的贡献。时间复杂度。 #include <bits/stdc++.h> using namespace std; #define int long long #define PI3 array<int, 3> #...

感觉这场题目的难题难度都差不多，不过都是窝做不出的好题就对了 G.智乃与模数 给定，求这个集合中前大的元素和。 赛时因为没时间了，痛失这道数论分块。其实分块数肯定不超过，每个块里面都是等差数列，双二分就完事了。 #include <bits/stdc++.h> using namespace std; #define int long long #define PII array<int, 2> const int inf = 4e18; const int N = 1e6 + 5; int t = 1, k, n; int tot; int red[N], start...

I.一起看很美的日落！ 求解树中所有联通块的两两异或和。这道题直接看不太好处理，所以要一边写一边分析： 首先拆位必然。设dp[i]为当前子树中的总贡献。则对于i中的每个子树j，其对dp[i]贡献都将是dp[j]乘以其他子树的构造种类数。据此，设op[i]为该子树中联通块的选择方案数。 但上述这些没有考虑i中的不同子树之间01组合的贡献。于是，我们再设hav[i][0/1]，表示子树内0/1所能提供的贡献（注意这个贡献不是点数，官方题解里也有提及）。 最后的答案即为每个子树内dp（贡献）之和。时间复杂度：。 #include <bits/stdc++.h> using namespa...

喵蛋原来写的题解被知乎吞了，所以来牛客发一发 K.硝基甲苯之魇 求满足gcd和异或和相等的区间个数。注意到gcd减少次数有限，所以可以每次去二分查找断点（即gcd变化的位置），然后用map维护区间所有异或前缀和的结果，找到对应的就可以（设原数组为a，异或前缀和数组为b，则对于满足条件的，只需要即可）。时间复杂度。 #include <bits/stdc++.h> using namespace std; // #define int long long const int N = 2e5 + 5; const int LogN = 19; int t, n; int brr[N];...