CVBB ACM Team

模拟退火算法

[https://atcoder.jp/contests/abc174 ]

有n个点，每一个点有一种颜色，有q个询问，问一个区间中有多少种不同的颜色
解法：将n询问按r排序，同时用一个last数组在线记录每种颜色最后一次出现的位置
询问的结果为1-r中不同的颜色数减去当前最后一次出现在l之前的颜色数
用一个树状数组维护这个last就可以了（然而我愚蠢的用了一个treap）

无

[https://atcoder.jp/contests/abc174 ]

无

无

[https://codeforces.com/contest/1399]

题意：可付出一定代价（1或2）将树上的一条边长度减半，求最小的代价使所有叶子节点到根的距离小于S

题解：对于简单版本（每条边的代价均为1）,可以统计每一条边减半后的贡献，然后放入优先队列维护，每次选贡献最大，即可。
然后对于复杂版本，与简单版类似，使用同样的贪心分别记录成本为1和2的边移动多少次后最小距离和，然后枚举成本为1的边移动了多少次即可