Good Problems

好题

• ARC068E: Snuke Line
  • 题意：有一趟列车有M+1个车站，从0到M编号。有N种商品，第i种只在编号[l_i,r_i]的车站出售。一辆列车有一个预设好的系数d，从0出发，只会在d的倍数车站停车。对于d从1到M的列车，求最多能买到多少种商品。
  • 题解：我们首先能想到的做法是枚举d，2d，3d，然后看每个点被多少商品覆盖，但是这么做有一个问题，相邻点之间会有重复的，重复的部分没法计算。这里有个关键的性质，我们注意到，对于某个d，如果商品的区间大于这个d，那么这个一定可以买这个商品，对于<=d的商品，只会被停一次，嗯，所以sort一下区间的大小，然后一边枚举d，一边update商店，用线段树维护区间更新，单点查询。
  • 代码：https://github.com/phonism/notes/blob/master/AlgorithmQuestions/AtCoder/arc068/e.cpp
• ARC105C: Camels and Bridge
• CF1136E: Complicated Computations
• CF1408D: Searchlights
• ARC101D: Median of Medians
• ARC092D: Two Sequences
• AGC038C: LCMs
• ARC067E: Grouping
• ARC067F: Yakiniku Restaurants
• ABC239F: Construct Highway
  • 题意：给N个点，和每个点的度数，然后给m条边，问是否可以构造出这么一棵树？
  • 题解：重做一次！
• ABC237E: Skiing
  • 题意：n个点，电有点权，m条边，从1出发初始值为A，u->v如果cost[u]>cost[v]，A+cost[u]-cost[v]，else A-2*(cost[v]-cost[u])，问到达所有的点最大的A是多少
  • 题解：重做
• ABC236D: Dance
  • 题意：1-2n个数，分成n个pair，定义每个pair的value是A[i][j]，问n个pair异或和最大是多少
  • 题解：TODO 还不会做。。。