牛客237787563号

未归档

/ 注册

全部文章 / 未归档（共15篇）

省选模拟44 题解

A. 跑步对于每次修改，$O(n^2)$ 的 dp 是显然的。然后发现每次修改这个 dp 的变化量只有 $+1,-1$ 两种取值。继续观察性质，可以发现，对于每一行，变化的位置是连续的。对于不同行，变化的左端点和右端点都是单调的。所以通过树状数组差分实现区间修改，单调指针确定每一...

dp 树状数组数学线段树

2020-03-13

0 368

省选模拟60 题解

A. 摧毁图状树考虑一个暴力做法。维护一个堆，每次取出深度最大的点，如果他还没有覆盖，那么就给答案增加 $1$。否则直接跳过，然后直接跳到他的 $k$ 级祖先加入堆中，复杂度是 $O(n^2log)$ 的。然后发现这样一个事情，这个复杂度肯定是不满的。比如说对于单次操作，复杂度大...

树状数组期望 dp

2020-04-03

0 746

省选模拟61 题解

A. GTM 考虑一个点 $(x,v)$ ，能够碰到的点 $(x',v')$。有 $(x',v')$ 满足 $x'<x,v'>v$ 或者 $x'>x,v'<v$。然后有这样一个结论，我们将所有的点按照 $v$ 排序，然后在每个点能影响到的是一个连续区间。区间的左...

结论题树状数组容斥线段树

2020-04-03

0 800

省选模拟62 题解

A. Fable 虽然没打 noi online，但是大概看了一眼题。其中 T2 就用到了一个结论是：设 $p_{i,k}$ 表示 $i$ 次冒泡排序之后，第 $k$ 个点与之前的点形成的逆序对个数。则有每次冒泡排序之后，$p_{i+1,k}=\max{p_{i,k+1},0}$。 ...

结论题高斯消元多项式 set 矩阵平衡树启发式合并树状数组线性代数

2020-04-04

0 415

省选模拟83 题解

A. table 首先考虑怎么暴力 dp，然后发现难点在于怎么知道不受影响的格点的个数。其实特殊之处在于碰到矩形边界之后没办法计数，所以考虑枚举在哪个位置碰到了矩形边界。然后发现每次转移是类似的，只要求 $a$ 次向下走，$b$ 次向右走，$c$ 次在边界上走能贡献的总的权值。其实等价...

组合计数树状数组 dp

2020-04-29

0 413