二分

共 2 篇文章

题解 CF1051E Vasya and Big Integers

May 28, 2019

首先看到题面，很容易想到一个 $DP$ ，令 $f[i]$ 为划分到 $i$ 为止的方案数。

然后朴素的暴力转移是 $O(n^2)$ 的，非常显然一个状态 $i$ 能够转移到的 $j$ 是一段连续的，进而想到使用前缀和优化。

April 14, 2019

我们考虑一件事情

如果我们询问的矩形中有一个端点

那么答案 $\mod 2 = 1$

否则答案 $\mod 2 = 0$

换句话说，就是如果询问到的答案 $\mod 2 = 0$ ，那么这个矩形内要么没有端点，要么有两个端点

Codeforces

Luogu

Github
本站由 Hexo 驱动，使用 Azurus 作为主题。