2017 Multi-University Training Contest - Team 3

acm 2017年8月 hdu 多校 组队训练

入口：2017 Multi-University Training Contest - Team 3

1003. Kanade's sum

我们只要求出对于一个数$x$左边最近的$k$个比他大的和右边最近$k$个比他大的，扫一下就可以知道有几个区间的$k$大值是$x$.

我们考虑从小到大枚举$x$，每次维护一个链表，链表里只有$\leq x$的数，那么往左往右找只要暴力跳$k$次，删除也是$O(1)$的。

时间复杂度：$O(nk)$

• 比赛的时候用$set$维护，做法类似。

1005. RXD and dividing

• 考虑每条边，他的贡献等于$val * min(sz[v], k)$
• $v$为该边深度较大的节点，$sz[v]$表示以$v$为根的子树大小

1006. RXD and functions

• hdu6061
  
  
  

1008. RXD and math

注意到一个数字xx必然会被唯一表示成$a^2\times b$的形式.其中$|\mu(b)|=1∣\mu(b)∣=1$。

所以这个式子会把$[1, n^k]$的每个整数恰好算一次. 所以答案就是n^k，快速幂即可. 时间复杂度$O(\log k)$

• 比赛时，打了一个错表，盯了大半天...

1011. RXD's date

• 是时候展现真正的手速了。
• runID 14