折花有时亦有时

题解

/ 注册

全部文章 / 题解（共5篇）

题解 | #小G的LY数对#

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

容斥哈希表

2021-05-04

1 547

题解 | # 小 Q 与树#

一个很标准的淀粉质题。题目所给的式子，我们可以看做一个树的重心，然后周围点与这个重心的贡献和，然后继续找这个重心的子树的重心，重复上述过程，就是淀粉质了。但是我们需要注意一点，如果我们在计算贡献时，没有对所给式子的第一项进行从小到大的排序的话，时间复杂度是要退化为N^2的。关于贡献的求法，就是一...

2021-05-03

1 553

题解 | #加密#

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

2021-04-10

12 669

C生涯回忆录题解

这个题数据范围较大，我没看到数据，想直接来一发莫队（好傻的想法）。很明显，不能直接暴力，我们需要一个O(nlogn)的算法。这道题通过观察可得，它的任意子集的Mex(x)必定小于等于n+1。如果不能枚举回忆，那么我们可以去枚举回忆值，正好是1——n+1，再加一个快速幂正好是(nlogn)的算法...

思维组合数学

2020-11-22

5 506

E题题解

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

高精区间DP

2020-06-02

2 558