每日小结

发表于 更新于 分类于 ， ， 阅读次数： 本文字数： 160 阅读时长 ≈ 1 分钟

#C++ STL 中 unique 的用法

1
2
3
4
5
6
template <class ForwardIterator>
  ForwardIterator unique ( ForwardIterator first, ForwardIterator last );

template <class ForwardIterator, class BinaryPredicate>
  ForwardIterator unique ( ForwardIterator first, ForwardIterator last,
                           BinaryPredicate pred );

将[first, last)之间, 相邻的多个相同元素合并为一个, 返回指向不重复部分末尾的迭代器. 多和 sort 函数一起使用

例: 使用 unique 实现离散化:

1
2
3
4
5
6
7
8
9
10
// vector<int> array;
// ...
auto disc = array;
sort(disc.begin(), disc.end());
disc.erase(unique(disc.begin(), disc.end()), disc.end())
for(int i = 0; i < disc.size(); i++) {
  disc[i] = lower_bound(array.begin(), array.end(), disc[i]) - array.begin();
}
// 那么disc就可以作为离散化之后的索引
// disc[i] = array中第i种元素的最小下标

#CCFCSP

今天考了 CCF CSP.

#区间树(Interval Tree)和线段树(Segment Tree)