牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟32 题解

A. chinese 要求的答案是所有情况总的炼字个数。观察到题中k的范围比较小，所以对k下手。枚举炼字的大小，限制与它同一行同一列的数的大小，其它数随便选就可以了。直接快速幂，$O(klogmod)$可过。写的帅一点，弄个线性筛，直接推一些东西，复杂度就变成$O(\frac{kl...

单调队列期望组合计数

2019-09-03

0 307

bzoj5461 Minimax 题解

https://www.lydsy.com/JudgeOnline/problem.php?id=5461 看到题目，必将m种权值离散化。首先是一个显然的dp设计。设$f(i,j)$表示第i个节点，最终取值为j（已离散化）的概率。因为树上的节点儿子数不超过2，不妨设值k出现在左儿子上。...

dp 线段树

2019-09-02

0 366

bzoj4868 期末考试题解

https://www.lydsy.com/JudgeOnline/problem.php?id=4868 显然我们只关注最后出分的学科。刚开始想的是dp，然而不知道如何记录状态。突然就想到了正解。首先对于每一个最后出分的日期，所有的不愉快度一定来自两个方面： $n$个同学的期待，这...

三分

2019-08-28

0 358

模拟31 题解

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

dp trie树单调栈

2019-08-25

0 360

模拟30A 题解

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

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

2019-08-25

0 306

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

模拟28 题解

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

容斥贪心 dp 矩阵

2019-08-21

0 344

模拟27 题解

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

位运算结论题 dp

2019-08-20

0 352

模拟26A 题解

A. marshland 考试时想到了网络流，然而不会建图，就死了。正解是最大费用可行流。比较容易想到的是将每个点拆为两个点， s连没有危险值的入点，没有危险值的入点连有危险值的入点，入点出点之间限流有费用，出点再连没有危险值的出点，这些出点连向t。不断跑spfa，通过有流量...

二分答案网络流后缀数组 bitset 树链剖分

2019-08-20

0 385

模拟25A 题解

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

容斥欧拉路点分治线段树

2019-08-19

0 436