memset0 发布的文章

容易发现答案与旗杆的顺序无关,我们可以把旗杆按照从矮到高的顺序排序,这样的话我们只需要维护两个操作:

  1. 插入一些 0
  2. 给一个前缀整体 +1

考虑每次 +1 操作,除了这个前缀中的最大值,每个数的相对位置不会改变。考虑放到线段树上,对于最大值二分出其区间,对其特殊处理后移即可。

READ MORE

现在每天一场模拟赛,考完还有一堆题目要订正。然而晚上回家后上不了学校 OJ ,要知道自己订正的对不对还得第二天跑来学校测 ......

前置条件

  • 一台位于学校的电脑,能保持长时间开机。
  • 一台位于公网的服务器,不需要太高的配置,推荐学生机。

这篇教程将会教你

  • 如何利用 SSH 建立反向连接
  • 如何利用 nginx 实现端口转发并配置
  • 如何利用 nginx 实现屏蔽特定页面的效果
  • 一些操作来保证安全性

READ MORE

本题中我们可以对机器人进行四种操作:

  • U ,即向量 (0, 1)
  • D ,即向量 (0, -1)
  • L ,即向量 (1, 0)
  • R ,即向量 (0, -1)

考虑正解,容易发现我们需要分开考虑 xy 轴的变化,然而上述四种操作对 xy 轴而言有 1 / 0 / -1 三种情况,较难考虑,且一边为 1-1 时,另一边只能为 0 ,较难判断。

于是有一个经典的 trick 就是旋转坐标轴。

考虑以 (\frac {\sqrt 2} 2 , \frac {\sqrt 2} 2)(-\frac {\sqrt 2} 2, \frac {\sqrt 2} 2) 为基底,考虑原来的四种操作:

  • U 变为向量 (1, 1)
  • D 变为向量 (-1, -1)
  • L 变为向量 (-1, 1)
  • R 变为向量 (1, -1)

那么就可以分开考虑 xy 轴的 \pm 1 变化。

假设最后所有向量的和为 \vec{S} ,则题目给出的坐标在时间模 L 后即可转换为一个关于 \vec S 的一次函数。列出不等式并判断下奇偶性即可。

READ MORE

与上一题相同的思路,考虑分块 + 凸包来维护。

  • 对于 1 操作,两端的块暴力查询,中间的取整块计算的结果

  • 对于 2 操作,暴力重构两个块

  • 对于 3 操作,两端的暴力重构,中间的同样用单调栈来维护。

READ MORE

非常好的分块 + 凸包题。

讲每个人按照 b 排序并依次插入,题目可以转换为维护

  • 插入一个数;
  • 查询从大到小排序后每个数的排名乘以自身的最大值。

考虑分块维护插入操作

  • 暴力重构当前块
  • 单调栈维护下凸壳维护整体排名 + 1 操作,对于当前块之后的块,执行这个操作。

查询时直接查询即可。

READ MORE

一道非常巧妙的哈希题。

假设我们枚举 j 使得 H_i - H_j = H_j - H_k 。可以发现题意要求的 i < j < kik 必须在 j 的两侧。

可以通过线段树 + 哈希维护

  • 哈希值使得第 k 位的哈希值为 1 当且仅当满足 H_i - H_j = kij 的左侧出现;
  • 哈希值使得第 k 位的哈希值为 0 当且仅当满足 H_j - H_i = kij 的右侧出现。

容易发现,若两哈希值不同,即存在一组 ijk 满足条件,我们直接输出 Yes 即可。

另外据称本地数据很弱,乱搞也能过 233 。

READ MORE

定义:给定两个 n 次多项式 F(x)G(x) ,若对于任意多项式 P(x) 都有 G(F(P)) = P 则称 G(x)F(x) 的复合逆在模 x^n 意义下的复合逆。可以证明,若两个多项式常数项为 0 且一次项不为 0 则复合逆唯一且满足 F(G(x)) = G(F(x)) = x

遗憾的是,多项式复合逆没有 o(n \log n) 的做法,但我们可以以 O(n \log n) 的复杂度求出某一项,或者 O(n^2) 的复杂度求出所有项。

拉格朗日反演即

[x^n]F(x) = \frac 1n [x^{-1}] \frac 1 {G^n(x)}

可以证明

[x^n]F(x) = \frac 1n [x^{n-1}] (\frac x {G(x)})^n

后者可以直接快速幂(两只 \log),或者转换为 \ln\exp ,可以参考 关于求多项式 k 次幂的一些思考

如果需要证明可以参考 zjt 大爷的博客 (我是不会)。

READ MORE

把询问拆分后直接莫队。

考虑

\begin{aligned} \sum_{i=0}^{\infty} get(l_1, r_1, x) \times get(l_2, r_2, x) = &\sum_{i=0}^{\infty} get(0, r_1, x) \times get(0, r_2, x)\\ - &\sum_{i=0}^{\infty} get(0, l_1-1, x) \times get(0, r_2, x)\\ - &\sum_{i=0}^{\infty} get(0, r_1, x) \times get(0, l_2-1, x) \\ + &\sum_{i=0}^{\infty} get(0, l_1-1, x) \times get(0, l_2-1, x) \end{aligned}

一个比较通俗的理解是 (A - C) (B - D) = AB - BC - AD + CD

READ MORE

前两天在楼下机房瞎逛,看到 EtaoinWu 哥哥的一通数据库操作,瞬间感觉很帅,不由心生崇拜之情,决定自己也要学一学这个东西 QAQ ....

这篇学习笔记将通过 UOJ 社区版后修改某用户的 rating 来介绍简单的 MySQL 数据库操作。

READ MORE