xuxuxuxuxu

分类

未归档(20) 题解(24)

/ 注册

TA的专栏 39篇文章 0人订阅

39篇文章 2130人学习

全部文章（共43篇）

Min-Max容斥来自专栏

Min-Max容斥公式：应用：常用来求“每次选一个数，使每个数被选的次数至少到达某个值的期望次数” 首先我们要知道对于一个局面（比如第一个数选1次，第二个数选2次）的期望步数就是这个局面的概率分之一。证明：设期望为，概率为，那么，化简得普遍情况：个数，每个数有个权重，那么每一次选中第个...

Min-Max容斥

2020-07-29

0 945

[51Nod1681]公共祖先来自专栏

题意：给出个点的树，对于所有点对求它们在两棵树中公共的公共祖先数量之和。题解：不考虑求点对的贡献，考虑求祖先的贡献。枚举一个祖先，假设两棵树上点的公共子孙个数为，那么这个点的贡献就是难点就在如何求两棵树上点的公共子孙个数。解法一：求出两棵树的，发现就是求满足和的的个数。这里就是的，就...

莫队线段树合并树套树分块

2020-07-27

0 702

牛客练习赛60 来自专栏

牛客练习赛60 A.大吉大利考虑每一位对答案的贡献。如果两个数的第位都是，那么就会对答案产生的贡献。所以答案就是。就是第位是的个数。 #include<bits/stdc++.h> using namespace std; #define next Next #define gc ...

比赛题解

2020-03-27

3 840

提高模拟赛来自专栏

提高模拟赛图题目描述一张无自环、无重边的图，每个点有一个点权，对于每条边，点和点的点权必须不同。假设这张图有种不同的点权，那么这张图就是一种色图。定义函数的值为所有个点的色图中的边数最大值。现在给出三个整数,求：输入描述: 第一行输入一个整数，表示数据组数。对于每组数据，输入三个整数。 ...

比赛题解

2020-03-09

0 785

提高模拟赛题解来自专栏

提高模拟赛题解图对于一张颜色已知的图，为了最大化图的边数，我们会在不同颜色的点之间连上一条边。边数为（为颜色总数，是颜色为的点数）: 30分: 枚举每个点选什么颜色，然后计算一下边数。时间复杂度明显平均分最优。 60分: 枚举m，然后计算上述式子。时间复杂度 100分: 发现可以除法分块，...

比赛题解

2020-02-29

0 674

F - Modularness 题解来自专栏

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]...

思维

2020-02-23

0 840

牛客小白月赛21题解来自专栏

牛客小白月赛21题解 A 题目：给你三个点，求到三个点距离相等的点。题解：三角形两条中垂线的交点，垂直直线k1*k2=-1 代码： #include<bits/stdc++.h> using namespace std; #define next Next #define gc get...

比赛题解

2020-01-20

0 840

题解 CF1175D 【Array Splitting】来自专栏

题解 CF1175D 【Array Splitting】思维题当时比赛时一看到题还以为是dp，后发现不对。观察这题有什么奇怪的特征，就是每段乘的数是一次加1的。考虑一段区间比如说是形如:2A3B,现在要使这段区间整体后移一位，就变成了:3A4B。发现就是加上了一个区间和sum。那么答案可以...

思维

2020-01-17

1 718

题解 P2365 【任务安排】来自专栏

题解 P2365 【任务安排】算法:斜率优化动态规划由于题解里没有关于的斜率优化做法,我打算写一下这种特殊的斜率优化动态规划由于可以小于零,所以斜率不具有单调性,所以我们不能像原来一样维护下凸壳。我们不能只保留相邻两点斜率大于的部分,我们要把整个下凸壳都保留下来。这时队首也就不是最优解了，要二...

斜率优化

2020-01-17

0 682

题解 P3242 【[HNOI2015]接水果】来自专栏

题解 P3242 【[HNOI2015]接水果】题意：给你一棵个点的树和条路径，每条路径都有一个权值。有k组询问，每次询问给你一条路径和一个值。问你被这条路径包含的所有路径中的第K小的路径的值题解：我用的是树上莫队+平衡树(或分块)的方法平衡树的话是,分块的话就是稍微口胡一下树上莫队...

莫队分块

2020-01-17

0 689