2017-Sp115-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
开场各自看题，sub上机写K，搞了一会儿'''K1y20'''。之后sub继续搞B，wa了之后和暴力对拍找到问题，'''B2y91'''。yzc和cjb讨论后上机bitset冲了一发H，tle，cjb发现性质，'''H2y100'''。cjb上机敲了最小树形图板子，yzc上机补充，'''I1y114'''。sub开出了D，上机写D，'''D1y139'''。yzc继续写一万年前讨论出的A，'''A1y185'''。cjb和sub讨论了很久G，将信将疑上机冲了一发'''G1y207'''。cjb上机写F，yzc和sub开出了J，考虑了下时间，cjb敲了dinic板子让sub上机写J，wa了之后cjb继续写F，之后'''J2y269'''，'''F1y289'''。
== 总结 ==
=== chenjb ===
最后才做签到题有点亏？感觉被hdu搞怕了，太多小心翼翼，不过该出的题都出了，博弈题还是要多冲多试，今天这个过了之后我是挺懵逼的....NJU这套题有诚意，但是有几个题给了太多无用信息，这样不太好。[[BR]]
'''感觉今天最大收获可能是我们二分艹过去的最小树型图，感觉在满足最优条件情况下，如果需要满足一些额外的条件，加权这个思路应该纳入思考体系中，gdkoi的一个fft是这样做的，去年多校有个网络流是放到小数点里，还有今天这个题。'''
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：线段树维护启发式合并，需要回收内存。

 * B：用莫比乌斯去掉gcd的限制，然后里面的Σ是约数个数的前缀和，所以可以O(n)预处理前缀和和莫比乌斯前缀和，对每个询问可以sqrt(n)

 * C：二分答案，观察到di<dj的两人相遇当且仅当di+vi*t>dj+vj*t或di+vi*t<dj+vj*t-L,按d从小到大排序，cdq分治内部按w从大到小排序，维护当前最大最小终点即可处理。最后记录最终一个未解决点，大力枚举计算即可得到分数解。

 * D：能力值从大到小考虑，调整成第n个人，速度为0，站在坐标原点，从大到小对于每个人考察他和当前的最左和当前最右撞在一起的时间和第n个人的时间，取最大值即可。

 * E：听说是个知乎数学题....要贴个大整数NTT的板子，记得要用快速乘@zimpha，另外记得乘法后要基于base进一次位。其余如下：[[BR]][[Image(E.png,800px)]]

 * F：实际上是把AC自动机建出来后搞个fail树，对于询问两个串对应的点集S,T，求lca(S[x],T[y])在trie树上深度最大。对fail树跑dfn序，然后按照dfn序归并排序，每个点取与自己最近的异色点取lca更新答案即可，通过各种预处理可以做到O(Q*size)

 * G：观察思考，大胆猜测可得实际上里面给出的奇怪限制都没用，本质还是最基本的staircase nim的二维版，把与终点曼哈顿距离为奇数的钻石异或起来就得到sg值。

 * H：本质上用bitset维护合法区间即可，但是出题人强行搞T了，给了个奇怪的式子维护了以下性质：当大于0的时候，因为x<b，(a,b)会变成(a,b+x)，同理当小于0，因为x<a，所以会变成(a-x,b)，如果都可以，当x<min(a,b)，则可以(a-x,b+x)，扫一遍判断即可。

 * I：最小树形图模板题，既可以二分求出n号节点最小的父亲，也可以将编号塞进边权中，做两遍即可。

 * J：绝对值可以视为两点不同色的代价，后面的部分直接全部展开，可以变成染色的代价，然后对于三种限制，可以视为不同的依赖关系，跑最小割即可。

 * K：大力容斥得前n个字符使用了k种字母的方案数，然后组合数即可。

 * [http://bestcoder.hdu.edu.cn/blog/2017-multi-university-training-contest-8-solutions-by-南京大学/  Official]

流水账

开场各自看题，sub上机写K，搞了一会儿K1y20。之后sub继续搞B，wa了之后和暴力对拍找到问题，B2y91。yzc和cjb讨论后上机bitset冲了一发H，tle，cjb发现性质，H2y100。cjb上机敲了最小树形图板子，yzc上机补充，I1y114。sub开出了D，上机写D，D1y139。yzc继续写一万年前讨论出的A，A1y185。cjb和sub讨论了很久G，将信将疑上机冲了一发G1y207。cjb上机写F，yzc和sub开出了J，考虑了下时间，cjb敲了dinic板子让sub上机写J，wa了之后cjb继续写F，之后J2y269，F1y289。

总结

chenjb

最后才做签到题有点亏？感觉被hdu搞怕了，太多小心翼翼，不过该出的题都出了，博弈题还是要多冲多试，今天这个过了之后我是挺懵逼的....NJU这套题有诚意，但是有几个题给了太多无用信息，这样不太好。

感觉今天最大收获可能是我们二分艹过去的最小树型图，感觉在满足最优条件情况下，如果需要满足一些额外的条件，加权这个思路应该纳入思考体系中，gdkoi的一个fft是这样做的，去年多校有个网络流是放到小数点里，还有今天这个题。

oipotato

subconscious

题解

  • A：线段树维护启发式合并，需要回收内存。
  • B：用莫比乌斯去掉gcd的限制，然后里面的Σ是约数个数的前缀和，所以可以O(n)预处理前缀和和莫比乌斯前缀和，对每个询问可以sqrt(n)
  • C：二分答案，观察到didj+vj*t或di+vi*t
  • D：能力值从大到小考虑，调整成第n个人，速度为0，站在坐标原点，从大到小对于每个人考察他和当前的最左和当前最右撞在一起的时间和第n个人的时间，取最大值即可。
  • E：听说是个知乎数学题....要贴个大整数NTT的板子，记得要用快速乘@zimpha，另外记得乘法后要基于base进一次位。其余如下：
  • F：实际上是把AC自动机建出来后搞个fail树，对于询问两个串对应的点集S,T，求lca(S[x],T[y])在trie树上深度最大。对fail树跑dfn序，然后按照dfn序归并排序，每个点取与自己最近的异色点取lca更新答案即可，通过各种预处理可以做到O(Q*size)
  • G：观察思考，大胆猜测可得实际上里面给出的奇怪限制都没用，本质还是最基本的staircase nim的二维版，把与终点曼哈顿距离为奇数的钻石异或起来就得到sg值。
  • H：本质上用bitset维护合法区间即可，但是出题人强行搞T了，给了个奇怪的式子维护了以下性质：当大于0的时候，因为x
  • I：最小树形图模板题，既可以二分求出n号节点最小的父亲，也可以将编号塞进边权中，做两遍即可。
  • J：绝对值可以视为两点不同色的代价，后面的部分直接全部展开，可以变成染色的代价，然后对于三种限制，可以视为不同的依赖关系，跑最小割即可。
  • K：大力容斥得前n个字符使用了k种字母的方案数，然后组合数即可。
  • Official
附加文件