这道题很恶心，我们只要对a数组处理一位，对b数组处理一位，如果异或值相同就是只有2位为1，然后我们减去两两重合的数量即可。 但是unordered_map爆了，下面的代码就过了10的点，于是我们要手写一个hash表，就可以愉快地AC了。 #include <bits/stdc++.h> int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); int n, m; std::cin >> n >> m; std::vector <int> a...

一个很标准的淀粉质题。 题目所给的式子，我们可以看做一个树的重心，然后周围点与这个重心的贡献和，然后继续找这个重心的子树的重心，重复上述过程，就是淀粉质了。 但是我们需要注意一点，如果我们在计算贡献时，没有对所给式子的第一项进行从小到大的排序的话，时间复杂度是要退化为N^2的。关于贡献的求法，就是一个点所有子树的距离和，加上这些点的个数乘于该点到重心的距离就是贡献。 那么我们很愉快地解决了这道题，下次再见！！！ #include <bits/stdc++.h> const int P = 998244353; int main() { std::cin.tie(0); ...

C 题一个线性递推，但由于n数值过大，无法进行继续，我们只要给n取余100019即可！！！ 成立的理由大致如下： 递推100019次，而且还是一个和式，那么一定是100019的倍数！ 代码如下： #include <bits/stdc++.h> using namespace std; const int P = 100019; int main() { cin.tie(0); ios::sync_with_stdio(false); int n; cin>>n; n%=P; vector <vector <int>...

这个题数据范围较大，我没看到数据，想直接来一发莫队（好傻的想法）。 很明显，不能直接暴力，我们需要一个O(nlogn)的算法。 这道题通过观察可得，它的任意子集的Mex(x)必定小于等于n+1。 如果不能枚举回忆，那么我们可以去枚举回忆值，正好是1——n+1，再加一个快速幂正好是(nlogn)的算法。 枚举回忆值，很明显分成了比这个数小的一部分，和比这个数大的一部分。 比这个数大的一部分很好求，就是集合2^p(p为大的一部分)，难道小的也是这样求吗？ 如果真的是这样子求那么前面部分是1，2，3，枚举值是4，前面难道真的等于8，不是，前面只有取1，2，3时才是4。 我们就可以发现前面数字至少有一...

区间DP，要用高精。我不会写高精，比赛python不太熟，调了半天最后都没有调出来。补一发题解。 思路：凸边形，取两个点，形成的一条边，我们把那条边形成的多边形中按顺序取点，区间DP。（好像说的有点抽象，看图就行） 转移式：f[i][j] = min(f[i][j], f[i][k] + f[k][j] + a[i] * a[j] * a[k]) 代码如下： a = [] T = int(input()) f = [([99999999999999999999999999999] * (T+10)) for i in range(T+10)] for case in range(T): ...