折花有时亦有时
折花有时亦有时
全部文章
分类
题解(5)
归档
标签
去牛客网
登录
/
注册
折花有时亦有时的博客
全部文章
(共5篇)
题解 | #小G的LY数对#
这道题很恶心,我们只要对a数组处理一位,对b数组处理一位,如果异或值相同就是只有2位为1,然后我们减去两两重合的数量即可。 但是unordered_map爆了,下面的代码就过了10的点,于是我们要手写一个hash表,就可以愉快地AC了。 #include <bits/stdc++.h> ...
容斥
哈希表
2021-05-04
1
545
题解 | # 小 Q 与树#
一个很标准的淀粉质题。 题目所给的式子,我们可以看做一个树的重心,然后周围点与这个重心的贡献和,然后继续找这个重心的子树的重心,重复上述过程,就是淀粉质了。 但是我们需要注意一点,如果我们在计算贡献时,没有对所给式子的第一项进行从小到大的排序的话,时间复杂度是要退化为N^2的。关于贡献的求法,就是一...
2021-05-03
1
551
题解 | #加密#
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
505
E题题解
区间DP,要用高精。我不会写高精,比赛python不太熟,调了半天最后都没有调出来。补一发题解。 思路:凸边形,取两个点,形成的一条边,我们把那条边形成的多边形中按顺序取点,区间DP。(好像说的有点抽象,看图就行) 转移式:f[i][j] = min(f[i][j], f[i][k] + f[k...
高精
区间DP
2020-06-02
2
557