牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共29篇）

bzoj2839 集合计数组合计数容斥原理|题解

集合计数题目描述一个有N个元素的集合有2^N个不同子集（包含空集），现在要在这2^N个集合中取出若干集合（至少一个），使得它们的交集的元素个数为K，求取法的方案数，答案模1000000007。（是质数喔~）输入格式 ...

组合计数容斥数学

2019-07-02

0 360

记忆的轮廓期望四边形不等式dp|题解

记忆的轮廓题目描述通往贤者之塔的路上，有许多的危机。我们可以把这个地形看做是一颗树，根节点编号为1，目标节点编号为n，其中1-n的简单路径上，编号依次递增，在[1,n]中，一共有n个节点。我们把编号在[1,n]的叫做正确节点，[n+1,m]的叫做错误节点。一个叶...

期望四边形不等式数学 dp

2019-07-02

0 349

赛艇题解

一颗赛艇 https://www.lydsy.com/JudgeOnline/problem.php?id=4584 虽然名字听起来很暴力（+1s），却是组合计数好题，在考试时都没有看出来是组合计数。对于子任务1/2 区间的总长度不超过1e6，可以将区间内的每个数离散化到一个区间里。...

数学组合计数 dp

2019-07-15

0 318

远古杂题 2

Base基站选址(线段树优化dp) 首先写dp转移式， $dp(i，j)$表示在第i位修建第j个基站。定义$l(i)$为能覆盖i的最靠左的基站，$r(i)$为能覆盖i的最靠右的基站， l和r数组均可以用二分求出， $dp(i，j)=min( dp(u，j-1)+cost(u，i)...

dp 数学高斯消元期望图论状压

2019-07-17

0 673

模拟5 题解

星际旅行题中很特殊的给出，恰好2条边1次经过，m-2条边2次经过，让我有一点想到了欧拉路。然而考试中还是没有想到拆边这个巧妙的方法，只打了一个dfs。正解是将每条边拆为两条，问题转化为删去两条不同的边，使图中存在欧拉路。判断每个点的度即可。在每个边拆为两条之后，每个点的度一定是偶...

dp 组合计数图论欧拉路数论分块数学

2019-07-18

0 275

模拟7 题解

A. 方程的解 a，b均为正整数，exgcd求出x最小和最大的解。作差后除公差再加一，就是方程的解的数量。对于a，b，c中存在0或负数的情况，疯狂加特判。 B. visit 共走t步，要求到达坐标$(n,m)$。即总共向上走了n步，向右走了m步。设u为向上走步数，d为向下...

exgcd 数学组合计数 lucas定理中国剩余定理模拟 set

2019-07-22

0 315

矩阵求逆

设逆矩阵为$P$，该矩阵为$A$，单位矩阵为$E$ 则有$P*A=E$ $P*E=P$ 因为做初等行变换等价于被对应的初等矩阵左乘。在$A$化为$E$过程中，对$E$做相同操作，就可以得到$P$。初始化另一个矩阵为单位矩阵，将本矩阵用高斯消元尝试消为单位矩阵。注意该过程不...

数学矩阵线性代数

2019-07-23

0 463

模拟9 题解

A. 随 (rand) 尽量不要重载乘法，真的很慢。 50分算法因为重载乘法被卡常卡成20分，真的很伤。 $void$函数，传入希望存储答案的指针，使用$memcpy$快速传递。 1 void mult(const matrix &a,const matrix &...

组合计数 dp 数学期望矩阵线性代数树上差分原根

2019-07-27

0 240

模拟10 题解

A. 辣鸡(ljh) 模拟。对于同一块内的答案，直接统计。对于不同块内的，枚举i和大于i的$j=i+1～n$，一个有效的剪枝：以$x_1$为第一维排序，当$x_{1j}>x_{2i}+1$时break退出循环。然而如果用纵向链状的数据还是会被卡成$O(n^2)$，然而...

数学期望启发式合并线段树模拟

2019-07-30

0 239

模拟15 题解

A. 建设城市（city）相较于那一天我们许下约定，数据范围有所改变。如果不考虑k的限制，是显然的插板法。枚举至少超过限制的个数，大力容斥就完了。 B. 轰炸行动（bomb）论如何看懂题。如果能够理解题意，缩了scc，拓扑排序求个点带权最长链就完...

容斥组合计数数学 tarjan 图论 dp 期望

2019-08-10

0 255