CF444C DZY Loves Colors


题目描述题目传送门分析看到区间推平操作,可以写珂朵莉树。使用珂朵莉树维护区间的颜色,使用树状数组维护区间和。这道题的难点在于加上的数字是 $|y - x|$ ,所以我们要在推平操作里稍加改动。不使用 std::set 的区间 erase 操作,而是和其他的操作一样暴力推平,对相同的颜色做区间加操作即

P哥的桶


题目简述题目传送门思路看到查询最大异或和,果断想到线性基,又看到了区间操作,果断想到线段树。于是就有了线段树套线性基。对于插入操作,我们可以对线段树上对应的点的线性基直接插入。对于询问操作,我们可以将区间内的线性基并在一块查询。然后代码就写完了,吸吸氧就过了。代码#include <bits/

[COCI2009-2010#3] PATULJCI


题目描述题目传送门思路由于我特别喜欢暴力数据结构,于是我就用分块 AC 了这道题。显然我们可以按照 $\sqrt n$ 为一块,将颜色分块,对每一块统计出每种颜色的数量,对于每一次询问,我们对完整块 $O(c)$ 累加,块外元素暴力累加。最后扫一遍结果得出答案。时间复杂度 $O(cm\sqrt n)

[ARC093A] Traveling Plan


题意简述数轴上有 $N$ 个点,一开始在 $0$ 位置上,需要去 $N$ 个点(顺序从 $0$ 号点按顺序走完 $N$ 个点),最后回到 $0$ 位置。对于 $i=1, 2, \ldots, N$ 分别输出不需要去 i 号点的最小路程。思路又是一道水题。。。首先,我们考虑不走 $i$ 原路径会发生什

CF1638C Inversion Graph


题面简述现在有一个序列 $p_1,p_2,\dots,p_n$,你需要构建一个无向图,规则是:当 $i < j$ 且 $p_i > p_j$ 时在 $i$ 和 $j$ 之间连一条无向边。问最后图中会有几个连通块。题目传送门思路我们考虑什么时候会形成一块。很显然,当 $\max\limit

CF1638B Odd Swap Sort


题意简述现在有一个序列 $a_1 , a_2,\dots,a_n$ ,你可以交换相邻两个和为奇数的数,问是否能够使序列有序。可以输出 Yes , 不可以输出 No。题目传送门思路也是一道水题。显然这道题跟逆序对有关。由于交换排序,所以每一对逆序对都一定会被交换。所以只需检查逆序对中是否有和为偶数的就

CF1638A Reverse


题意简述给你一个序列 $p_1,p_2,\dots,p_n$ ,保证序列中的数字不重复且为 $1$ ~ $n$ 。你可以选择反转序列中的一个区间(当然也可以不反转),求操作后字典序最小的序列。题目传送门思路首先我们可以检查该序列是否有序,有序(即 $p_i=i$)时则已经为字典序最小,则不用反转。在

CF1634A Reverse and Concatenate


题目传送门分析实际上就是裸的分类讨论,手工枚举几轮便可以发现:当现在的字符串回文字符串时,那么进行;两种操作是相同的,会产生一种答案。若其不为回文穿,进行操作后会变为两个回文字符串。综上,当原字符串是回文字符串时答案为 $1$ , 不为回文字符串时答案为 $2$。最后,别忘了特判 $0$ 无法操作,

狄利克雷卷积与莫比乌斯函数


狄利克雷卷积 $f(x)$ 和 $g(x)$ 是定义在数论函数间的一种二元运算,可以定义为:

$$(f*g)(n) = \sum_{xy=n}f(x)g(x)$$ $$\Rightarrow\sum_{d \mid n}f(d)g(\frac{n}{d})$$

CF1203E Boxers


思路用一个类似桶的结构,存储每个体重存在的数量然后进行贪心即可每个体重有用的人数最多为三人并且能够加入 $Ans$ 与且仅与上一个体重的人和下一个体重的人有关那我们只需从小到大进行贪心,注意有个细节:要先判断当前位置的上一个(使其+1),然后再是当前体重(不变),最后是下一个体重(使其-1)【与贪心