CF #345 div.2


打div2和咸鱼有什么区别……

滚粗太久了只能打打div.2了

  • A: DP, 乱搞,注意f(1,1)=0
  • B: 维护一个map<key, cnt>,每次删掉cnt ==0的点,ans += map.size() -1,然后给所有的都-1
  • C: 容斥原理,long long
  • D: 四种情况:全右,全左,右后左,左后右。预处理出到达左边、右边第若干个点的时间,对于1) 2)直接二分查找<=T的最远点。对于3) 4)枚举右边/左边的折返点,然后计算出从出发到回到原点的时间cur,之后二分查找一下另一方向的T – cur。注意最多只能遍历n个点,重复不算。
  • E: 建图,拓扑排序。不需要搞很多边:只要对每一排、列排序一下,把大小相邻的连边就行了