牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

模拟15 题解

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

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

2019-08-10

0 337

模拟17 题解

A. 入阵曲求每一行的前缀和，枚举左右端点，O(n)扫下去，顺便更新桶。维护栈清空桶中的内容。 B. 将军令 k=1，小胖守皇宫弱化版。与小胖守皇宫比较，发现特殊性质：点没有权值。考虑贪心。每次找出深度最深的点，点亮它的k级父亲。 1.点...

差分 dp 贪心桶

2019-08-11

0 821

模拟18 题解

A. 引子模拟完了 B. 可爱精灵宝贝注意到特殊性质： 1.对于每个位置，只关注第一次到达的时间。 2.人走的区间是连续的。问题转化为区间dp。设$dp(i,j,k,0/1)$表示在$k$时间走完区间$(i,j)$，当前在区间的左/右端点的最优答...

数位dp dp 模拟

2019-08-12

0 368

模拟22 题解

A. 数论一条性质：对于一个不良好的数$x$，$x*p^c$一定不是良好的。因为那些小于x，并且因数比x多的数，乘上$p^c$仍然更优。这个性质告诉我们：一个目前认为不优的数，不会贡献出良好的数。显然最大的质因子不会很大，良好的数也不会很多。 ...

dp 数位dp 位运算

2019-08-15

0 372

模拟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

模拟27 题解

A. 小奇挖矿2 看完题，小凯的诱惑？大于17的点可以直接转移，反之则暴力枚举。去一下重，记录前缀最大值转移就完了。 B. 小奇的矩阵(matrix) 题中要求输出答案的整数，然后就不理解。暴力化简式子。最终化为： $(n+m-1)\sum \limits_...

位运算结论题 dp

2019-08-20

0 352

模拟28 题解

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

容斥贪心 dp 矩阵

2019-08-21

0 344

模拟29 题解

A. 壕游戏不会做，以为是贪心。结果发现贪心是错的。正解是网络流中的费用流。将每条边$i$拆为$c_i$条边，将所有边建出来，每条边的费用为$a_i*j+b_i$，$1<=j<=c_i$。然后可以直接跑费用流。然而复杂度$O(mk^2)=O(跑不过)$，死了...

数位dp 网络流 AC自动机 dp 主席树

2019-08-22

0 357

模拟30A 题解

A. 树联想起远古考试时做的题记忆的轮廓。树上走一些步数的期望。显然可以直接解方程。然而复杂度$O(qn^3)$，利用树上的性质优化一下，直接一遍dfs过程中解出来，可以$O(qnlogmod)$，其中的log是求逆元。然而只有20分。预处理出每个点走到每个儿子的期望步...

dp 期望 Hash 二分答案字符串启发式合并

2019-08-25

0 306

模拟31 题解

A. math 考试时打的错解，取每个$a_i$与k的gcd，分别做背包由0直到k。但是复杂度有点问题，于是做了个筛。 $O(k sqrt(k))$一定没有问题，在不构造特殊数据下很优秀。考后突然被自己一个简单的数据hack掉了。 2 6...

dp trie树单调栈

2019-08-25

0 360