Madoka And Laziness
前去做题
题意
我们有一个序列 a[n] 求问如果将这个序列分裂为两个山峰序列会有几个最大值对的。
其中山峰序列表示对于一组数列满足 $a_1<a_2< \dots < a_r > a_{r + 1} >\dots > a_n$
思路
首先,由于这个序列中的所有的数字都是唯一出现的,那么我们最大值的位置一定时唯一的。
我们不妨定我们的另外一个山顶出现在我们最大值的右端。
假定最大值的端点在 p 另一个山顶在 q 那么其中数字的大小变化如下。
[1,p] 两个数组都单调递增
(p,q] 第一个数组单调递减,第二个数组单调递增
(q,n] 两个数组都单调递减
由于该题目的单调性是确定的。
如果我们在 q 点,对于从...
Yet Another Minimization Problem
前去做题
题意
给定连个长为 $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...
Two binary strings problem
前往做题
题意
给定两个长为 $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...
teXt主题下-key的重设&leancloud转国际版
Key 的重设
由来
由于长时间没有进行更新博客,并且打算迁移一下近期题解,所以我更改以前的博客,于是乎现在的样子就是最终的结果。
在配置的时候我曾遇到过几个不太好用的地方,其中最突出的就是它所使用的评论系统与访问量的设置。
按照作者的设置,我们成功设置了这些东西。
不过作者放在文档中的方法似乎有些不太好用。
而 key 的值如下
如果每篇文章都需要我们手动设置的话那么对我们来说,特别是批量导入的人来说,这是极为不方便的。
修改
我们不妨根据 jekyll 网站的生成规则自己定义一个可能不随着博客的改变的 key
首先唯一确定的东西有哪些呢?
我们考虑网址,对于我们的博客来说,它是唯一的,如果我们有两个重复的地址,那么我们将无法定义该页面显示的东西是什么。...
Promising String
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。而我们需要的...
Paimon sorting
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的次数
思路
我们不妨观察以下我们的序列。
首先,对于第一次循环。
我们会发现,我们将找到所有刚好比上一个最大值大的那个数。
然后我们第一次循环就是把最后一个数提到第一个,然后其余的数在找到的位置上往后挪了一...
C. Klee in Solitary Confinement
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 时我们直接统计即可,因此我们不再考...
G - Range Pairing Query
题意
有 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[...
54 post articles, 7 pages.