牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共29篇）

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

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

组合计数容斥数学

2019-07-02

0 473

模拟15 题解

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

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

2019-08-10

0 337

模拟23 题解

A. mine 设dp(i,0/1/2/3,0/1)表示前i位，且第i位填入0/1/2/炸弹的方案数。当第i位填入1的时候，需要关注炸弹在1的左侧或者右侧，故加半维表示炸弹在1的哪一侧，当i为不为1，最后一维无意义。简单转移。 B. water 第一眼：直接考虑临...

dp 最小生成树莫比乌斯函数桶容斥

2019-08-16

0 407

模拟25A 题解

A. Lighthouse m的范围极小，显然的容斥。总的方案数，减去受任意一个限制的方案数，加回受两个限制的方案数。就能得到受所有限制的的方案数。将选择的一些边所指向的点放在同一个联通块里。方案数其实就是这些联通块的圆排列，再乘上$2^{不为1的联通块个数}$，因为每个联通块...

容斥欧拉路点分治线段树

2019-08-19

0 436

模拟28 题解

A. 虎比较显然的贪心。儿子中存在偶数个不符合条件的，直接全部连在一起。存在奇数个，最后剩下的一个能上传则上传，否则也撞死在这里。容易证明，将更多的不符合条件的情况上传，不会使答案更优。 B. 阴阳观察题目两个性质： 0/1为联通块同行同列1之间...

容斥贪心 dp 矩阵

2019-08-21

0 344

模拟50 题解

A. 施工又是利用了一些结论的题，因为想不到结论，经常做不出这种题。枚举两个不变的边界，那么中间的建筑必定被提高成相同的小于等于边界的高度。于是设$f_i$表示考虑前i个建筑，并且第i个建筑高度不变的最优答案。设对于转移（i，j），中间建筑的最优高度为t，可以写出dp转移方程。拆...

单调栈 dp 分块容斥直径

2019-09-23

0 469

模拟57 题解

A. 天空龙一个很好的性质是：最优方案可以不存在一个颜色A，转化为B再转化为C。因为将A直接转化为C一定更优。所以无需分类讨论，直接用一个sum判断正负就可以了。 B. 巨神兵有向图无环，所以存在拓扑序，所以用分层图dp。设f(i,j)表示已经考虑点集i，并且...

dp 容斥状压拓扑排序

2019-10-03

0 410

模拟59 题解

A. Reverse 手玩第二个样例，发现可以dp。但是似乎没有显然的拓扑序，所以直接跑最短路。然而暴力建图$n^2$，解决方法是线段树优化建图。利用$bfs$每个点只在第一次被更新时最优的性质，直接用$set$或者链表维护也是可以的。 B. Silhouette ...

dp set 最短路容斥

2019-10-04

0 436

模拟77 题解

A. 位运算位运算，显然可以按位处理。所以大力分类讨论就完了。 B. 集合论通过维护一个$add$标记，直接进行全体的加减法。因为值域只有$10^6$，直接维护一个桶。求并集的操作是简单的，直接尝试加入。求交集涉及到删除的操作，然而在桶中删掉元素并不是简单...

容斥位运算

2019-10-17

0 359

模拟107 题解

A. 字符交换枚举最终出现的字符，那么答案具有单调性。之后枚举相同字符的起点，可以计算出终点。最优策略显然是换到中间的字符旁边，所以用前缀和维护一下就完了。 B. 平方数考虑怎样的两个数相乘可以构成平方数：将两个数分别质因数分解，如果二者奇数的质因子集合相同，...

二分答案 dp 容斥

2019-11-10

0 361