2019-team2/Sp089

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

  
  总结

  Heltion写完C就跑去打Kotlin了,留下一堆bug的代码给lyk调到赛后半个多小时.

  题解

  A. 先对原序列搞个单调压缩映射变成值域1到m,然后相邻不连续的地方肯定断开,相邻连续的部分相当于是一个类似DP的东西,从i到i+1只能保留一个连接,并且如果有多于一个i,那么i-1到i和i到i+1的连接不能是同一段i.
  B. max(1,n-2)
  C. DP[i][x][y]表示到第i个数组,方向为(x,y)所需的转角数.方向只需要取[-30,30]之间(也许更少)的所有既约方向,复杂度是O(16d^2^).不平行只需要判射线交,重合的需要认真考虑.
  D. 签到
  E. 不会
  F. 先预处理出来每个点作为子树根对应的最大区间,从整个数组开始,每次选一个对应区间覆盖该区间的点,然后两边递归下去.注意到暴力两边往中间搜总复杂度是正确的.也可以用可持久化线段树对数时间求出任意区间的答案.
  G. 几何,随便算算
  H. d足够大全给一个人,d比较小暴力枚举.
  I. 根据d-s从大到小排序后DP.
  J. 找找规律,发现可以独立处理每个2,然后它自己变成1,这一段前后如果有0各加一,把与它对称位置的地方减一.
  K. 假设知道方案可以平方复杂度计算答案.最优解是将A看成最小的排序,然后第一轮让A和最小的那些人轮空.

总结

Heltion写完C就跑去打Kotlin了,留下一堆bug的代码给lyk调到赛后半个多小时.

题解

A. 先对原序列搞个单调压缩映射变成值域1到m,然后相邻不连续的地方肯定断开,相邻连续的部分相当于是一个类似DP的东西,从i到i+1只能保留一个连接,并且如果有多于一个i,那么i-1到i和i到i+1的连接不能是同一段i.

B. max(1,n-2)

C. DP[i][x][y]表示到第i个数组,方向为(x,y)所需的转角数.方向只需要取[-30,30]之间(也许更少)的所有既约方向,复杂度是O(16d²).不平行只需要判射线交,重合的需要认真考虑.

D. 签到

E. 不会

F. 先预处理出来每个点作为子树根对应的最大区间,从整个数组开始,每次选一个对应区间覆盖该区间的点,然后两边递归下去.注意到暴力两边往中间搜总复杂度是正确的.也可以用可持久化线段树对数时间求出任意区间的答案.

G. 几何,随便算算

H. d足够大全给一个人,d比较小暴力枚举.

I. 根据d-s从大到小排序后DP.

J. 找找规律,发现可以独立处理每个2,然后它自己变成1,这一段前后如果有0各加一,把与它对称位置的地方减一.

K. 假设知道方案可以平方复杂度计算答案.最优解是将A看成最小的排序,然后第一轮让A和最小的那些人轮空.