Home

前去做题 题意 我们有一个序列 a[n] 求问如果将这个序列分裂为两个山峰序列会有几个最大值对的。 其中山峰序列表示对于一组数列满足 $a_1<a_2< \dots < a_r > a_{r + 1} >\dots > a_n$ 思路 首先，由于这个序列中的所有的数字都是唯一出现的，那么我们最大值的位置一定时唯一的。 我们不妨定我们的另外一个山顶出现在我们最大值的右端。 假定最大值的端点在 p 另一个山顶在 q 那么其中数字的大小变化如下。 [1,p] 两个数组都单调递增 (p,q] 第一个数组单调递减，第二个数组单调递增 (q,n] 两个数组都单调递减 由于该题目的单调性是确定的。 如果我们在 q 点，对于从...

前去做题 题意 给定连个长为 $n$ 的数组a[n] ,b[n]。我们可以任意次交换 a[i] 与 b[i]。 最后求取最小的 $\sum_{i = 1} ^ n \sum_{j = i + 1} ^ n (a_i + a_j) ^ 2 + \sum_{i = 1} ^ n \sum_{j = i + 1} ^ n (b_i + b_j) ^ 2$ 思路 首先我们尝试化简其中一个式子。 首先我们有 $(x + y) ^ 2 = x^2 + y^2 + 2xy$ 那么带入原来的式子就有 $\sum_{i = 1} ^ n \sum_{j = i + 1} ^ n (a_i + a_j) ^ 2 = (n - 1) \sum_{i = 1}^n a_i^2 + 2\times...

前往做题 题意 给定两个长为 $n$ 的 0\1 序列 a 和 b \[f(l,r) = \begin{cases} 1, if \sum\limits_{i = l} ^ r a_i > \frac{r - l + 1}{ 2} \\ 0 , otherwise \end{cases}\] 输出一个零一序列，c[k] 的值如果为 1 ,那么对于所有的 $i\in [1,n]$ $f(max(i - k + 1) , i) = b_i$ 成立。 思路 首先，如果 a[i] 的值为 0 ，那么我们将其变换为 -1 , 然后我们对这个数组求取前缀和 S 。 那么我们就得到一个简单的转换如果对于 b[i] = 1 的情况而言其所有满足 S[i] - S[i - k] &g...

Key 的重设 由来 由于长时间没有进行更新博客，并且打算迁移一下近期题解，所以我更改以前的博客，于是乎现在的样子就是最终的结果。 在配置的时候我曾遇到过几个不太好用的地方，其中最突出的就是它所使用的评论系统与访问量的设置。 按照作者的设置，我们成功设置了这些东西。 不过作者放在文档中的方法似乎有些不太好用。 而 key 的值如下 如果每篇文章都需要我们手动设置的话那么对我们来说，特别是批量导入的人来说，这是极为不方便的。 修改 我们不妨根据 jekyll 网站的生成规则自己定义一个可能不随着博客的改变的 key 首先唯一确定的东西有哪些呢？ 我们考虑网址，对于我们的博客来说，它是唯一的，如果我们有两个重复的地址，那么我们将无法定义该页面显示的东西是什么。...

https://codeforces.com/contest/1660/problem/F2 题意 给出一个仅仅包含’+’ ‘-‘的字符串，我们可以将两个连续的’-‘,合并为’+’。 求其所有子串经历变换后 ‘+’ 的数量等于 ‘-‘ 的数量的个数。 思路 假若，我们有一段连续的序列了，其中有 x 个 ‘+’ , y 个 ‘-‘。 那么我们如果想要成立的话，那么我们需要以下几个条件成立。 y >= x x + k = y - k * 2 即 y - x = 3 * k 也就是说，我们只需要 (y - x) % 3 = 0 情况下的答案。 首先，如果，我们用 -+ 把所有的 + 排完。那么我们就得到 k >= (y - x) / 2。而我们需要的...

https://codeforces.com/gym/103470/problem/D 题意 如下所示的循环中 1 2 3 4 5 for (int i = 1 ; i<= n ; i ++ ) { for (int j = 1 ; j <= n ; j ++ ) { if(a[i] < a[j]) swap(a[i] , a[j]); } } 对于给定序列 $A[N]$ 分别求其前缀 [1 , N] swap的次数 思路 我们不妨观察以下我们的序列。 首先，对于第一次循环。 我们会发现，我们将找到所有刚好比上一个最大值大的那个数。 然后我们第一次循环就是把最后一个数提到第一个，然后其余的数在找到的位置上往后挪了一...

https://codeforces.com/gym/103470/problem/C 题意 给出一个数组，我们可以选择一段区间加上 k (或者不加)。求出现次数最多的数出现了几次。 思路 对于一段区间加上 k 的话。 我们不妨考虑最多的数为 a[i] + k 的情形。 我们敲定区间 [L , R] 我们最优的方案一定是刚好 a[L] = a[R] = k。这很容易想出，因为只有这种情况下，我们才可以保证 L 左边的和 R 右边的 a[i] + k 没被改掉。 我们不妨用 cnt[i] 表示区间 [1 , i] 内 a[i] 出现的次数，ckt[i] 表示区间 [1 , i] 内， a[i] + k 出现的次数。 由于 k == 0 时我们直接统计即可，因此我们不再考...

题意 有 n 个人站成一排，每个人的身上都有一个数字 c。求问区间 [l,r] 范围内共有多少个颜色一样的对。 思路 这题大概是一个裸的莫队 采取另外一种方法。 首先，我们采取离线的方式进行写题。 我们通过前缀和的方式进行更新我们的答案，并且我们的前缀和 pre 表示 pre[l] 表示区间 [l ,i] 上的答案位多少。 假如我们更新到了 i = 10 。并且 pos[] = [1 ,3 ,4 ,7 ,9] 。 假如我们将 i = 10 添加进去的话，那么如下几个区间的答案被更新了。 [8,9] | [4,4] | [2,3]。 因此我们可以得到如下的代码 1 2 3 4 5 6 7 8 9 int sz = pos[a[i]].size() - 1; pos[...