牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共241篇）

模拟42 题解

A. 世界线毒瘤出题人，bitset题卡空间。于是将所有的点分成两份，做两次拓扑排序，bitset只用开一半，空间就能够了。 B. 时间机器似乎是很显然的贪心，然而没想到。只会打更加显然的网络流暴力。按左端点排序，set维护一下不断取后继就行了，当没有后继即为无解。...

bitset 拓扑排序 set 贪心数位dp

2019-09-13

0 384

模拟41 题解

A. 夜莺与玫瑰与题解中的定义类似：枚举每个斜率，设为向量$(a,b)$ 如果$gcd(a,b)!=1$，那么直接跳过。考虑每个点(x,y)，它的前趋为(x-a,y-b)，后继为(x+a,y+b)。一个点是合法的当且仅当不存在前趋，存在后继。于是$ans=\sum \limit...

点分治组合计数线段树

2019-09-10

0 346

模拟40 题解

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

dp 树状数组线段树离线

2019-09-08

0 358

模拟39 题解

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

dp 基环树组合计数

2019-09-07

0 364

模拟38 题解

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

wqs二分 dp 桶

2019-09-07

0 354

模拟37 题解

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

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

2019-09-06

0 502

模拟36 题解

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

最短路 ST表区间dp dp

2019-09-05

0 381

模拟35 题解

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

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

2019-09-03

0 308

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

模拟33 题解

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

dp 数学结论题单调指针

2019-09-03

0 348