牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共13篇）

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

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

期望四边形不等式数学 dp

2019-07-02

0 464

远古杂题 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 785

模拟9 题解

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

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

2019-07-27

0 338

模拟10 题解

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

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

2019-07-30

0 344

模拟15 题解

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

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

2019-08-10

0 337

模拟30A 题解

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

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

2019-08-25

0 306

模拟32 题解

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

单调队列期望组合计数

2019-09-03

0 307

模拟35 题解

A. 公园长度放不进状态，那就把遍历的点的个数放进状态，使长度最小。然后就变成了DAG上最短路问题。设个源点汇点，直接拓扑排序就完了。 B. 计划设$mn(i)$表示左端点选i，最小的愉快的旅行。显然$mn(i)$是单调的，单调指针扫过去就完了。然后对询问...

dp 拓扑排序单调指针分块期望高斯消元

2019-09-03

0 308

模拟53 题解

A. u 一眼差分，在斜线上加一减一。然后发现这样的复杂度是$O(nq)$的，似乎不是很好过。然后发现打差分标记的形式也是连续的，所以差分两次就完了。 B. v 最优决策问题，一般倒着转移，$O(n*2^n)$的dp是显然的。考试时一直在想能否改成三进制状压，只压...

差分期望搜索状压 dp

2019-09-28

0 411

省选模拟10 题解

A. 食物链在拓扑序上dp。 B. 选点游戏要求支持合并两棵树，并同时维护树上最大独立集。考虑特殊情况，每次只加一个标号最大的点，问题是一个简单的动态dp。离线出最终树的形态，考虑加入的一个叶子节点，更新该节点到1号节点的轻链上信息就可以了。其实想到这里，一个动态dp的做...

拓扑排序树链剖分 dp 期望动态dp

2020-01-29

0 365