牛客237787563号

分类

未归档(241)

/ 注册

全部文章（共5篇）

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

关于lct维护动态生成树问题

水管局长数据加强版题意是要求维护一棵最小生成树，支持删边操作。删边操作比较难处理，因为如果删掉树上的边，很难从已经有备选集合中找出连接不同联通块的最小的边。然而题目并没有要求在线。所以离线。问题由删边转化为加边。考虑加的每一条边：如果两个点没有联通，直接联通。如果两...

主席树 lct 最小生成树

2019-09-17

0 435

模拟68 题解

考试过程大概是：上来看T1，看懂了题但是丝毫没有思路，甚至没有想到第一步贪心，心态稍崩。接着看T2，发现似乎可以直接上主席树上树，然后想了想复杂度，直接找前趋后继，复杂度似乎很正确。 T3只会暴力。然后就回去把T2切了，一遍过大样例自信不对拍。结果忘了在线这回事，一个小时之后才发现...

trie树主席树贪心位运算二分答案

2019-10-11

0 401

省选模拟4 题解

A. 点点的圈圈因为题中保证的特殊性质，容易发现圆之间的关系形成树形结构。对于每棵子树，选择树的根或者累计所有子树的答案。问题在于建图，容易发现这个可以用KDTree优化。考虑将所有的点建在KDTree上。用每个点的圆覆盖KDTree，当完全覆盖时直接塞入对应点的vector中。...

结论题 set 扫描线 lct 主席树线段树 tarjan KD-Tree 计算几何

2020-01-12

0 875

省选模拟5 题解

A. 青蛙因为每个青蛙都可以一步跳到终点。所以二分几个青蛙可以无消耗跳到终点，只要让最贵的几个青蛙跳过去。之后特判一下一个青蛙都跳不过去的情况就好了。 B. 一起自习的日子伯努利数练习题。不断的把自然数幂和用伯努利数展开，顺便二项式展开一下就好了。另外分析可知原式可以...

贪心主席树 lct 二分答案伯努利数后缀自动机

2020-01-12

0 418