2017-Sp146-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,600px)]]
== 流水账 ==
开门各自看题，sub上机'''B1y22'''，yzc开了个斜率优化，敲了板子'''A2y50'''。之后sub开始写K，写了很久，wa了之后cjb上机写C，炸了之后高效地查了错，拍了一下就看到sb错误，'''C3y136'''。sub继续搞K，tle了，卡了卡清0 '''K4y142'''。之后yzc上机写J，wa两发。sub推好式子上机wa了，yzc继续搞J，之后sub '''D2y214'''。cjb和sub搞了F，疯狂assert和对拍，'''F4y282'''，之后疯狂补救J，赛后10min过了。
== 总结 ==
=== chenjb ===
如果口胡也算通过的话大概有9个题，感觉根本写不完...赛后10min过了J有点伤。自己定义了数组然后没用到就很傻逼了。。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：DP显然，斜率优化显然。由于有aj<=ai的约束，考虑用cdq分治，每一层将a排序进行转移，需要套一个动态斜率优化板子。

 * B：s=l-l mod q，如果l+1到r有q的倍数，s=gcd(s,q)的约数个数

 * C：把相邻的块合并，之后颜色节点之间建边，按度数<=sqrt(m)和>sqrt(m)维护答案，对于每个小点直接暴力，大点维护f[x]代表相邻亮的点的个数。

 * D：偶数时显然，奇数时答案是n/2个0到9组成n/4*9+0,+1..+4的方案数。

 * E：枚举body后大分类讨论(待补)

 * F：(x,y,z)=z找到0，(x,y,p[0])=y找到1，从1往上递推。

 * G：

 * H：

 * I：扫描线建树之后暴力trie上跑(待补)

 * J：注意到n是奇数时只有一种奇偶排放方式，n是偶数时有两种。枚举摆放方式之后最小cost显然是按照读入顺序填入，考虑怎么调整得到最小字典序。显然对于两个移动方向不同的元素不可能交换目的地，于是分别考虑每一段相同移动方向的元素，以向后移动为例，则显然每个元素重新分配的位置一定不能比自己当前位置靠前，否则移动方向就变了，于是模型转化为n个元素，每个元素有一个最小可放置位置，求一个字典序最小的放置。按照最小放置位置排序后用堆维护当前位置可放置的元素，每次取堆顶即可。向前移动的维护方式类似。

 * K：枚举中心点往外广搜得到所有边，然后广搜。

 * [http://www.cnblogs.com/clrs97/p/8667455.html Claris]

流水账

开门各自看题，sub上机B1y22，yzc开了个斜率优化，敲了板子A2y50。之后sub开始写K，写了很久，wa了之后cjb上机写C，炸了之后高效地查了错，拍了一下就看到sb错误，C3y136。sub继续搞K，tle了，卡了卡清0 K4y142。之后yzc上机写J，wa两发。sub推好式子上机wa了，yzc继续搞J，之后sub D2y214。cjb和sub搞了F，疯狂assert和对拍，F4y282，之后疯狂补救J，赛后10min过了。

总结

chenjb

如果口胡也算通过的话大概有9个题，感觉根本写不完...赛后10min过了J有点伤。自己定义了数组然后没用到就很傻逼了。。

oipotato

subconscious

题解

  • A：DP显然，斜率优化显然。由于有aj<=ai的约束，考虑用cdq分治，每一层将a排序进行转移，需要套一个动态斜率优化板子。
  • B：s=l-l mod q，如果l+1到r有q的倍数，s=gcd(s,q)的约数个数
  • C：把相邻的块合并，之后颜色节点之间建边，按度数<=sqrt(m)和>sqrt(m)维护答案，对于每个小点直接暴力，大点维护f[x]代表相邻亮的点的个数。
  • D：偶数时显然，奇数时答案是n/2个0到9组成n/4*9+0,+1..+4的方案数。
  • E：枚举body后大分类讨论(待补)
  • F：(x,y,z)=z找到0，(x,y,p[0])=y找到1，从1往上递推。
  • G：
  • H：
  • I：扫描线建树之后暴力trie上跑(待补)
  • J：注意到n是奇数时只有一种奇偶排放方式，n是偶数时有两种。枚举摆放方式之后最小cost显然是按照读入顺序填入，考虑怎么调整得到最小字典序。显然对于两个移动方向不同的元素不可能交换目的地，于是分别考虑每一段相同移动方向的元素，以向后移动为例，则显然每个元素重新分配的位置一定不能比自己当前位置靠前，否则移动方向就变了，于是模型转化为n个元素，每个元素有一个最小可放置位置，求一个字典序最小的放置。按照最小放置位置排序后用堆维护当前位置可放置的元素，每次取堆顶即可。向前移动的维护方式类似。
  • K：枚举中心点往外广搜得到所有边，然后广搜。
  • Claris
附加文件