Min-Max容斥 公式： 应用： 常用来求“每次选一个数，使每个数被选的次数至少到达某个值的期望次数” 首先我们要知道对于一个局面（比如第一个数选1次，第二个数选2次）的期望步数就是这个局面的概率分之一。 证明：设期望为，概率为，那么，化简得 普遍情况： 个数，每个数有个权重，那么每一次选中第个数的概率就为，问每个数被选的次数至少到达的期望次数。 公式： 解释: 是得到一个指定集合内元素的期望时间,有重复元素的排列下,是对于集合内每个数的概率。这个式子是怎么推出来的呢？可以发现答案可以转化为每种状态的持续期望时间之和。那么就是状态改变的期望时间，就是每一种状态出现的概率。 例题： E - ...

题意： 给出个点的树，对于所有点对求它们在两棵树中公共的公共祖先数量之和。 题解： 不考虑求点对的贡献，考虑求祖先的贡献。 枚举一个祖先，假设两棵树上点的公共子孙个数为，那么这个点的贡献就是 难点就在如何求两棵树上点的公共子孙个数。 解法一： 求出两棵树的，发现就是求满足和的的个数。这里就是的，就是 这不就是一个的矩阵，进行次单点加，次矩阵求和。我们可以用树套树解决。 时间复杂度: 解法二： 把和看成两维。 第一维我们用莫队，然后分块维护第二维。 时间复杂度: #include<bits/stdc++.h> using namespace std; #define next Ne...

牛客练习赛60 A.大吉大利 考虑每一位对答案的贡献。 如果两个数的第位都是，那么就会对答案产生的贡献。 所以答案就是。就是第位是的个数。 #include<bits/stdc++.h> using namespace std; #define next Next #define gc getchar #define int long long const int N=1e6+5; int n,m,k,ans,a[N]; char s[N]; //char buf[1<<21],*p1=buf,*p2=buf; //inline int gc(){return p1==...

提高模拟赛 图 题目描述 一张无自环、无重边的图，每个点有一个点权，对于每条边，点和点的点权必须不同。假设这张图有种不同的点权，那么这张图就是一种色图。 定义函数的值为所有个点的色图中的边数最大值。 现在给出三个整数,求： 输入描述: 第一行输入一个整数，表示数据组数。对于每组数据，输入三个整数。 输出描述: 对于每组数据，输出一行一个整数表示答案。 输入 5 3 1 1 3 2 2 5 2 4 10 3 9 1000 123 789输出 0 2 23 280 332539617数据范围 对于 30% 的数据，对于 60% 的数据，对于 100% 的数据， , 位运算 题目描述 定义 为在二...

提高模拟赛题解 图 对于一张颜色已知的图，为了最大化图的边数，我们会在不同颜色的点之间连上一条边。 边数为（为颜色总数，是颜色为的点数）: 30分: 枚举每个点选什么颜色，然后计算一下边数。时间复杂度 明显平均分最优。 60分: 枚举m，然后计算上述式子。时间复杂度 100分: 发现可以除法分块，对于上取整和下取整分开来计算即可。 然后就是除法分块裸题。 位运算 30分: 枚举，然后计算二进制下的个数。 或 先预处理出，表示在二进制下的个数。时间复杂度 不用计算的话可能被卡。 60分 在30分的基础上分段打表，时间复杂度。 先考虑一下,的情况。发现答案相当于是有位可以随意选的和 加上。 位可...

F - Modularness 题解 前言： E题不知道为啥一眼秒，rk18。F题不知道为啥想不出，rk193。 题目描述 先给k个数，a[0]~a[k-1]。然后q次询问，每次给出n,x,m。b[0]=x,b[i]=b[i-1]+a[(i-1)%k]。问有多少i满足b[i]%m<b[i+1]%m。k,q<=5000n,x,m<=1e9 题解 首先很好想到,b[i]%m<b[i+1]%m的话，需要b[i]%m+a[i%k]<m。我们不求<的个数而求>=的个数，=一定是a[i%k]%m=0，>就是b[i]%m<m且b[i]%m+a[i%k]&...

牛客小白月赛21题解 A 题目：给你三个点，求到三个点距离相等的点。 题解：三角形两条中垂线的交点，垂直直线k1*k2=-1 代码： #include<bits/stdc++.h> using namespace std; #define next Next #define gc getchar #define int long long #define x1 x[1] #define x2 x[2] #define x3 x[3] #define y1 y[1] #define y2 y[2] #define y3 y[3] const int N=1e6+5; int n,m,...