牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共132篇）

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

模拟33 题解

A. 春思比较简单的一道题，甚至是见过的原题。约数和是积性函数，搞一搞等差数列求和，乘到一起就可以了。 B. 密州盛宴显然，方案合法的条件是苏轼每轮都能吃到菜。所以就发现任意后缀0,1个数必须满足，$sufcnt_0-sufcnt_1<=1$。所以当不满...

dp 数学结论题单调指针

2019-09-03

0 348

模拟34 题解

A. 次芝麻显然答案是$min(n*2^k$%$(n+m),(n+m)-n*2^k$%$(n+m))$ 因为每一次乘2，在取模意义下，选大选小是等价的。 B. 喝喝喝 $a_x$%$a_y=k$ $a_x-k=a_y*m$ 所以直接对$a_x-k$质因数分解，两个单调指针乱...

dp 中国剩余定理结论题单调指针

2019-09-03

0 367

模拟35 题解

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

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

2019-09-03

0 308

模拟38 题解

A. 金显然是问gcd是否为1 高精取模 B. 斯诺(snow) 考虑问题的逆问题。有多少区间是不合法的。显然一个区间，最多在考虑一种颜色的情况下不合法，所以不用容斥。推一下不合法条件的式子，然后发现要求一个前缀和。树状数组就一个log了。发现每次查询...

wqs二分 dp 桶

2019-09-07

0 354

模拟36 题解

A. 字符题中保证$p_i<=1e5$，还可以很显然地发现当总长度大于$p_{max}+c$，一定不会更优。于是枚举长度的大小。将每一个限制对长度取模。显然如果相邻两个字符所在的区间存在交集，就表示状态非法。于是得到$O(m*p_{max})$的暴力。发现在取模的过程中...

最短路 ST表区间dp dp

2019-09-05

0 381

模拟37 题解

A. 简单的区间看到这种题，一眼就是枚举最值，则确定左右区间，统计跨最值点的答案。维护前缀和后缀和就完了。于是自然地想到用个主席树，还是枚举小的区间，复杂度$O(nlog^2n)$。复杂度证明见模拟31 C.English 正确的算法一定无法避免枚举小区间，已经带了一个log， ...

启发式合并单调栈 ST表桶分治组合计数 dp

2019-09-06

0 502

模拟39 题解

A. 工业题手玩样例。然后发现就是到达所求点上面点的方案数乘一下a，b的次方。一个简单的组合数问题。 B. 卡常题一眼费用流，然而只有40分。考后才发现费用流是错的，不会建图。部分分中提示可能形成一个大环。 2n个点，2n条边，如果不是大环会形成什么...

dp 基环树组合计数

2019-09-07

0 364

模拟40 题解

A. 队长快跑非常显然的数据结构优化dp，线段树下标为a的最小值，要求支持区间最值，区间加，单点取max。随便写下转移方程就好了。 B. 影魔树上数颜色？但是要求了一个深度。我的做法是将询问离线，显然在一个询问中我们只关注每种颜色在该子树中出现的最...

dp 树状数组线段树离线

2019-09-08

0 358

模拟43 题解

A. A 发现不断加a，乘b。枚举将s乘k次b，则有 $t=s*b^k+\sum \limits_{i=0}^{k-1}used[i]*a*b^i$ 答案即是使得$\sum \limits_{i=0}^{k-1}used[i]$最小的方案。将s，t表示为b进制会比较好算。当a=1时...

dp 组合计数欧拉函数贪心三分

2019-09-15

0 284