高度由习惯堆积

2018年12月

December 15, 2018

排序算法

稳先从最简单的计数排序开始吧。计数排序(O(n+k))#include<bits/stdc++.h> using namespace std; int n;int A[105],B[105]; int cnt[105]; int main(){ cin>>n; for(int i=1;i<=n;i++){ scanf("...
December 15, 2018

动态逆序对(CDQ分治)

题目对于序列 $A$ ,它的逆序对数定义为满足 $i<j$ ,且 $Ai>Aj$ 的数对 $(i,j)$ 的个数。给定 $1$ 到 $n$ 的一个排列,按照某种顺序依次删除 $m$ 个元素,你的任务是在每次删除一个元素之前统计整个序列的逆序对数。思路1我们反向来看,离线询问,将问题转变成一个一个往序列中加入元素。接着很容易发现这是一道三元组的题目,对于两个数来说,必须在满足题目条...
December 15, 2018

IOI2011-热带花园

题目植物学家 Somhed 带着几组学生去泰国最大的热带花园游玩。这个花园中有NN个喷泉(编号为 0,1,⋯,N−10,1,⋯,N−1)和MM条小路。每条小路连接一对不同的喷泉,两个喷泉间最多只有一条小路,小路是可以双向行走的。从任意一个喷泉出发至少有一条小路。每条小路的美丽程度决定了 Somhed 选择走该条小路的优先程度。每组学生可以从任何一个喷泉出发。在任何一个喷泉,Somhed 和他...