2017-Sp141-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,600px)]]
== 流水账 ==
开场cjb和yzc有点迟到，到了之后sub丢了个lct给大家，cjb上机敲了一下，yzc上机敲了一下'''I1y31'''，cjb秒了H，丢给yzc '''H1y51'''，胜利倒开。之后开始签到，sub上机tle了，卡了卡常'''E2y70'''，cjb丢了假算法给yzc，tle了，sub上机写J，'''J1y115'''，继续写K，'''K1y136'''，之后三个人讨论了一下A，换了做法又wa了，对拍后'''A4y170'''，之后sub '''F1y214'''，cjb和yzc讨论B，之后yzc和sub又讨论了一下，上机'''B1y244'''，最后sub rush D，赛后通过，比赛rk12。
== 总结 ==
=== chenjb ===
nju居然是三台电脑打的，无语，感觉uestc的题风就是喜欢堆积一堆算法，最后有点松懈，不太应该，不然第9题可以有更加充裕时间来完成，赛后才过就很可惜。
=== oipotato ===
=== subconscious  ===
== 题解 ==
 * A：spfa暴力即可。

 * B：枚举循环节长度，将每一段长度区间的每种字母出现位置都拿出来，分类讨论得到结果。

 * C：考虑如果没有pop，那么分5棵线段树维护时间戳，打上+1和-1的标记，询问的时候查询一下他们>0的位置，求最接近的一个即可。现在有了pop操作，等于把询问区间分段了，每次把pop变成一个对应值的-1，pop总共不超过5个。

 * D：大力分段积分，注意积分式子的边界。

 * E：可以发现是个积性函数，大力用莫比乌斯容斥即可。

 * F：只与1的数量有关，f[i][j]代表用了i个，目前1的数量是j，推式子dp即可。

 * G：线段树维护列区间的并查集，暴力合并。每次修改相当于线段树的单点修改，计算答案时额外考虑第1列和第n列的相邻即可。

 * H：取一条边出来就变成树上修改边权，询问两点路径长度，分类考虑取出来的那条边在不在答案路径即可。

 * I：每个点的权值相当于给他定了个真实的父亲，询问的答案就是他在树上的深度，lct维护。

 * J：常数只有根号种，分段矩乘。

 * K：开个5个堆，第i个堆里是1到i-1全满足，i不满足的怪物，暴力动态维护即可。

流水账

开场cjb和yzc有点迟到，到了之后sub丢了个lct给大家，cjb上机敲了一下，yzc上机敲了一下I1y31，cjb秒了H，丢给yzc H1y51，胜利倒开。之后开始签到，sub上机tle了，卡了卡常E2y70，cjb丢了假算法给yzc，tle了，sub上机写J，J1y115，继续写K，K1y136，之后三个人讨论了一下A，换了做法又wa了，对拍后A4y170，之后sub F1y214，cjb和yzc讨论B，之后yzc和sub又讨论了一下，上机B1y244，最后sub rush D，赛后通过，比赛rk12。

总结

chenjb

nju居然是三台电脑打的，无语，感觉uestc的题风就是喜欢堆积一堆算法，最后有点松懈，不太应该，不然第9题可以有更加充裕时间来完成，赛后才过就很可惜。

oipotato

subconscious

题解

  • A：spfa暴力即可。
  • B：枚举循环节长度，将每一段长度区间的每种字母出现位置都拿出来，分类讨论得到结果。
  • C：考虑如果没有pop，那么分5棵线段树维护时间戳，打上+1和-1的标记，询问的时候查询一下他们>0的位置，求最接近的一个即可。现在有了pop操作，等于把询问区间分段了，每次把pop变成一个对应值的-1，pop总共不超过5个。
  • D：大力分段积分，注意积分式子的边界。
  • E：可以发现是个积性函数，大力用莫比乌斯容斥即可。
  • F：只与1的数量有关，f[i][j]代表用了i个，目前1的数量是j，推式子dp即可。
  • G：线段树维护列区间的并查集，暴力合并。每次修改相当于线段树的单点修改，计算答案时额外考虑第1列和第n列的相邻即可。
  • H：取一条边出来就变成树上修改边权，询问两点路径长度，分类考虑取出来的那条边在不在答案路径即可。
  • I：每个点的权值相当于给他定了个真实的父亲，询问的答案就是他在树上的深度，lct维护。
  • J：常数只有根号种，分段矩乘。
  • K：开个5个堆，第i个堆里是1到i-1全满足，i不满足的怪物，暴力动态维护即可。
附加文件