牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共26篇）

模拟12 题解

A. 斐波那契(fibonacci) 首先想到a,b<=1e6的暴力：建树，直接向上标记求lca。建树的过程中发现一个性质。斐波那契第n代兔子，是n-2代及以前的兔子的儿子。因为编号连续且与父亲编号大小有关，设该节点的编号为$x$，在第$k$代，则$f(x)=x-fib(...

数列线段树 dp 单调队列贪心拓展域并查集

2019-08-03

0 399

模拟16 题解

A. Blue 贪心完了。这道题学到了很多使用stl set的技巧。 B. Weed 线段树维护栈的操作。一个重要的操作是递归结束时$O(logn)$复杂度的向下寻找分界点。因为延伸出的一定是一条链，复杂度是$O(nlog^2n)$ ...

线段树贪心十字链表

2019-08-10

0 328

模拟17 题解

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

差分 dp 贪心桶

2019-08-11

0 821

模拟28 题解

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

容斥贪心 dp 矩阵

2019-08-21

0 344

模拟42 题解

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

bitset 拓扑排序 set 贪心数位dp

2019-09-13

0 384

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

模拟44 题解

A. D 显然对于每一个点，它左侧的区间gcd是单调不增的。因为gcd一旦减少至少减半，不同取值不超过log个。从左到右扫一遍的过程中，维护一个单调的pair数组。第一维为区间gcd值，第二维为左端点下标。显然我们只关心同一个gcd值最小的左端点。不断维护一下这个元素个数不超过...

dp 线段树贪心单调栈

2019-09-17

0 303

模拟62 题解

A. Graph 在树的情况下，答案是显然的。一次dfs，尽量将子树内不同的边合并就可以了。考虑非树的情况，可以生成一棵树。将非树边任意加在一个端点上，视作点权加一。对于树上的每一个点，先考虑它的子节点，子节点的父边尽量在子节点处作连接节点使用。如果子节点的父边还没有被使用，那...

线段树结论题贪心最小生成树拓扑排序

2019-10-06

0 365

模拟63 题解

A. Median 线性筛完质数，就会发现给的时间已经快没了。所以只能$O(n)$求$n-k$个中位数？不会做，所以打权值线段树。在权值线段树上二分找第k大值，可以做到$O(nlogn)$。打$zkw$线段树，比传统线段树快一倍，然而并没有什么用，仍然T70。题中确实给出了一些...

dp 桶贪心

2019-10-07

0 407

模拟64 题解

A. trade 暴力dp，复杂度$O(n^2)$。然后70分等死。考试快结束的时候，突发奇想。快速改了滚动数组，将第二维的上界设为1000。即只考虑同时存1000个货物，然后突然过了大样例。其实只是想多偷一点分，然后就A了，就非常偷税。所以正解其实是基于堆操作的反悔贪心。...

贪心莫队组合计数并查集

2019-10-08

0 350