609A

贪心 优先选大的USB flash drive

609B

先处理每个genre的书有多少本，然后直接枚举每次购买的是哪两种genre然后乘法原理即刻

609C

手下考虑balanced的长啥样。假设这n个数字的和为sum，那么应该有sum%n个数是sum/n上取整，其余是sum/n下取整。接着考虑把原数列改成这样的形式。可以发现如果我们把原数列和新数列都进行排序，这两个数列每位的差（绝对值）的和/2就是答案（这也算一个比较常用的贪心结论）

609D

很有趣的一道题！首先想到二分答案，因为显然天数越多越容易买到足够多的东西。接着就是怎么进行check。这里有两个需要考虑的问题：（1）哪几天买东西？（2）买哪些东西？
首先考虑（1），我们可以想到对于一种特定种类的物品，我们只在汇率最低的那天买。这个贪心显然是对的。
接着考虑（2），既然我们已经选择了固定的一天，那么汇率就是一个常数了，因此我们只要尽量选便宜的东西就好了。
同时我们注意到可以留给check的复杂度是O(N)左右，因次我们可以直接枚举k个物品的来源。对于（1）和（2）我们都可以预处理前缀和然后在check时直接调用

609E

也是一道个人很喜欢的题。考虑暴力做法，对于每条边跑mst。直觉上我们可以感觉到这样很浪费时间，因为这些mst应该都很像。因此我们想到，有没有可能只跑一遍没有任何限制的mst，然后对于每条边在这个mst上进行修改？思考如果我们想硬塞一条边(u,v)到一个树，我们需要先使u,v不连通。考虑到树的性质，两点之间的路径是唯一的，因此这等价于从u到v的路径之间删掉一条边。因为我们想要最小生成树，所以显然删权值最大的边最优。这样对于每条边(u,v)的查询就被转化成了在原图mst上找连接u，v的路径上最大的权值。这个值可以在倍增找lca的同时维护。

609F

哈哈哈哈这是一道我19年做的时候TLE 61然后这次theory solve了懒得写了就直接在源代码上debug了。居然是因为对set用lower_bound时候不能写lower_bound(s.begin(),s.end(),key)，必须要写成s.lower_bound(key)，不然会TLE。
搞一个线段树，对于每个蚊子可能出现的位置维护会吃它的青蛙是哪个。这样每有一个蚊子来可以直接单点查询。青蛙的舌头长度的更新也可以用线段树维护。首先我们用一个set存现有的蚊子，这样每个蚊子最多被放进去一次，被拿出去一次，这样吃蚊子的操作不会导致TLE。每当一个青蛙吃了一个蚊子，我们就继续往右找，直到没有更多的蚊子可以被吃掉。这时候根据青蛙新的舌头长度我们就可以在线段树上进行一个区间更新