[国家集训队]排队 发表于 2022-04-30 | 分类于 默认分类 | 0 | 阅读次数 789 题目描述题目传送门思路对于交换 $i , j$ 的数字,我们考虑交换这两个数字(记这两个数字分别为 $a,b$)对答案的贡献。显然,对于区间 $[i+1,j-1]$ 中每一个大于 $a$ 的数字会产生 $+1$ 的贡献,每一个小于 $a$ 的数字会产生 $-1$ 的贡献,每一个小于 $b$ 的数字会 阅读全文 »
CF1082G Petya and Graph 发表于 2022-04-11 | 分类于 CF | 5 | 阅读次数 1727 题目描述题目传送门思路这道题和 [NOI2006] 最大获利 是一模一样的,做完记得去拿双倍经验这道题是一个经典的网络流模型:最大权闭合子图。先说做法:新建原点 $s$ 与汇点 $t$;将 $s$ 与图中每一个正权点相连,权值为该正权点点权;将 $t$ 与图中每一个负权点相连,权值为该负权点点权的绝 阅读全文 »
分块 发表于 2022-04-08 | 分类于 默认分类 | 0 | 阅读次数 1812 简介其实,分块是一种思想,而不是一种数据结构。从 NOIP 到 NOI 到 IOI,各种难度的分块思想都有出现。分块的基本思想是,通过对原数据的适当划分,并在划分后的每一个块上预处理部分信息,从而较一般的暴力算法取得更优的时间复杂度。分块的时间复杂度主要取决于分块的块长,一般可以通过均值不等式求出某 阅读全文 »
CF444C DZY Loves Colors 发表于 2022-03-12 | 分类于 默认分类 | 0 | 阅读次数 1067 题目描述题目传送门分析看到区间推平操作,可以写珂朵莉树。使用珂朵莉树维护区间的颜色,使用树状数组维护区间和。这道题的难点在于加上的数字是 $|y - x|$ ,所以我们要在推平操作里稍加改动。不使用 std::set 的区间 erase 操作,而是和其他的操作一样暴力推平,对相同的颜色做区间加操作即 阅读全文 »
P哥的桶 发表于 2022-02-27 | 分类于 默认分类 | 1 | 阅读次数 1543 题目简述题目传送门思路看到查询最大异或和,果断想到线性基,又看到了区间操作,果断想到线段树。于是就有了线段树套线性基。对于插入操作,我们可以对线段树上对应的点的线性基直接插入。对于询问操作,我们可以将区间内的线性基并在一块查询。然后代码就写完了,吸吸氧就过了。代码#include <bits/ 阅读全文 »
[COCI2009-2010#3] PATULJCI 发表于 2022-02-19 | 分类于 默认分类 | 0 | 阅读次数 1510 题目描述题目传送门思路由于我特别喜欢暴力数据结构,于是我就用分块 AC 了这道题。显然我们可以按照 $\sqrt n$ 为一块,将颜色分块,对每一块统计出每种颜色的数量,对于每一次询问,我们对完整块 $O(c)$ 累加,块外元素暴力累加。最后扫一遍结果得出答案。时间复杂度 $O(cm\sqrt n) 阅读全文 »
[ARC093A] Traveling Plan 发表于 2022-02-15 | 分类于 默认分类 | 0 | 阅读次数 1664 题意简述数轴上有 $N$ 个点,一开始在 $0$ 位置上,需要去 $N$ 个点(顺序从 $0$ 号点按顺序走完 $N$ 个点),最后回到 $0$ 位置。对于 $i=1, 2, \ldots, N$ 分别输出不需要去 i 号点的最小路程。思路又是一道水题。。。首先,我们考虑不走 $i$ 原路径会发生什 阅读全文 »
CF1638C Inversion Graph 发表于 2022-02-15 | 分类于 默认分类 | 0 | 阅读次数 1498 题面简述现在有一个序列 $p_1,p_2,\dots,p_n$,你需要构建一个无向图,规则是:当 $i < j$ 且 $p_i > p_j$ 时在 $i$ 和 $j$ 之间连一条无向边。问最后图中会有几个连通块。题目传送门思路我们考虑什么时候会形成一块。很显然,当 $\max\limit 阅读全文 »
CF1638B Odd Swap Sort 发表于 2022-02-15 | 分类于 默认分类 | 0 | 阅读次数 1480 题意简述现在有一个序列 $a_1 , a_2,\dots,a_n$ ,你可以交换相邻两个和为奇数的数,问是否能够使序列有序。可以输出 Yes , 不可以输出 No。题目传送门思路也是一道水题。显然这道题跟逆序对有关。由于交换排序,所以每一对逆序对都一定会被交换。所以只需检查逆序对中是否有和为偶数的就 阅读全文 »
CF1638A Reverse 发表于 2022-02-15 | 分类于 默认分类 | 0 | 阅读次数 1539 题意简述给你一个序列 $p_1,p_2,\dots,p_n$ ,保证序列中的数字不重复且为 $1$ ~ $n$ 。你可以选择反转序列中的一个区间(当然也可以不反转),求操作后字典序最小的序列。题目传送门思路首先我们可以检查该序列是否有序,有序(即 $p_i=i$)时则已经为字典序最小,则不用反转。在 阅读全文 »