2017-C05-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(day5board.png)]]

== 流水账 ==
开场sub从A开始看，cjb从D开始看，yzc从K开始看. sub看到C发现C是个简单的数学签到题开始写，cjb和yzc想了E的贪心，换下sub先写E，18分钟交了第一发wa，打印下去研究，sub24分钟写完C交了也获得wa，此时三脸懵逼. 最后cjb发现题意理解出现了偏差，修改之后'''E2y29'''.然后sub继续修改C，yzc在旁边看代码，又交了两发wa，yzc和cjb想了想F，决定强上线段树，cjb研究sub代码，发现abs很奇怪，sub突然醒悟，修改后'''C4y55'''. yzc继续写F，cjb和sub研究H，很快得到结论. 在yzc下机研究代码时cjb上机写H，'''H1y73'''. yzc发现自己代码的问题，上机调了一会儿提交，'''F1y77'''. 此时大家开始开坑，cjb和sub研究I题后得到了bfs的做法，sub上机写题，cjb和yzc开始看A和J. sub141分钟提交一发wa，感觉很奇怪，思考之后发现自己代码的错误，之后cjb给出了正确的做法，sub迅速改完之后提交'''I2y164'''. 此时只剩下两个多小时，三人先接力尝试了一下D，发现过不了样例，感觉理解有误，遂放弃. 两个小时的时候，决定最后全力开A和J，讨论之后，yzc先去写了一发J的贪心，在204分钟获得wa，决定转向网络流的思考. cjb把A题的dp方程优化到了可以过的程度，决定最后一个半小时，cjb把dinic板子写好，sub和yzc研究完建图的细节后上来敲建图，cjb把第一题的dp框架写好，yzc讨论好A题modify函数的细节后上来接力，按照这样的操作，一个半小时拿下两题应该不成问题. 但始料未及的是，直到比赛结束我们也未能再AC，J题共计交了4发都未能通过，期间cjb一人调试A，yzc和sub合力调J，也没有出现太过频繁的交换机位，但始终未能通过A和J任何一题.最后排名第7，这也是这段时间以来最差的一次排名，结合cf board的情况看，我们仅仅在154名，做出7题起码也有88名，今天三个人发挥十分不理想.
== 总结 ==
=== chenjb ===
今天很糟糕啊.....三个人状态都很差，都有各自的锅要背，但我想说：不要因为这一场失利就down下去啊，这不过是我们组队的第五场比赛，还是要有信心，我们的磨合还要继续努力，个人实力提升还任重道远，要看到目标，看到希望，不要刚出发就躺趴下了，训练训练 fighting！！！
=== oipotato ===
今天是集训以来我们队打的最差的一场，从前期的读错题，签到打错，到中期一度落后，中等难度题没想法，后期虽然大概弄出了两题想法但是没有理清细节双开一直到比赛结束一道题都没搞出来。别的不说了，多练练吧，还是太菜了。
=== subconscious  ===
今日血崩.理应1A的两道的两道签到题贡献了近100罚时(或者这才是常态?),中期由于跟榜落后加大罚时压力,在中等题算法上也没有大的突破.最严重的是AJ两题双开后接连WA,不断换人,进入焦躁状态,最终两题都没有调出来(其实网络流应该可以调出来?).这次比赛暴露了个人实力不足和代码能力不足的问题,在分配交流上也日益乏力.
== 题解 ==
 * A：因为最大操作数肯定不超过2*n，所以直接f[i][j]表示前i个串，进行j次操作后，第i个串变成的最小串，然后贪心转移，细节十分多，modify函数很难写...
 * B：因为原题题意中实际上只有大小不超过5的强连通分量，所以我们tarjan缩点之后，在DAG上求最长路径即可. cjb的写法是令f[i]表示从i出发，并且此前没有经过i所在scc上任何一个点的最长路径，这样转移起来非常方便，也不需要新建图，只需要对于每个scc保存其和其他scc连接的边即可.求f[x]时，先将x所在scc的所有出边指向的点都遍历完毕，然后以x为起点，暴力跑x所在scc(只走属于端点属于同一个scc的边)，求出x到scc里所有点的最长路径.对于scc里任一条出边(u,v)(x和u属于同一个scc)，f[x]=max(f[x],d[u]+1+f[v])转移即可，注意f[x]还要与max(d[u])(u和x属于同一个scc)取最优，不然会忽略环里的最长路径(cjb因为这里wa了一发)
 * D：建树每次随意取两点,考虑两点间的链,计算其余的点在这条链上的最近祖先和到它的距离,两个式子都形如(dis[x][y]+dis[y][z]-dis[z][x])/2.然后对于链上不存在的祖先点建出虚点,建出这条链,对于对应最近祖先相同的所有点和那个祖先一起递归下去建树即可.注意最后要判定是否合法.计算答案时可以考虑每一条长度为1的边的贡献,也可以考虑子树贡献.数字较大,要用double.
 * J：网络流，建图后跑dinic可过.
 * K
== 补题 ==
 * A(√)
 * B(√)
 * D(√)
 * J(√)
 * K

流水账

开场sub从A开始看，cjb从D开始看，yzc从K开始看. sub看到C发现C是个简单的数学签到题开始写，cjb和yzc想了E的贪心，换下sub先写E，18分钟交了第一发wa，打印下去研究，sub24分钟写完C交了也获得wa，此时三脸懵逼. 最后cjb发现题意理解出现了偏差，修改之后E2y29.然后sub继续修改C，yzc在旁边看代码，又交了两发wa，yzc和cjb想了想F，决定强上线段树，cjb研究sub代码，发现abs很奇怪，sub突然醒悟，修改后C4y55. yzc继续写F，cjb和sub研究H，很快得到结论. 在yzc下机研究代码时cjb上机写H，H1y73. yzc发现自己代码的问题，上机调了一会儿提交，F1y77. 此时大家开始开坑，cjb和sub研究I题后得到了bfs的做法，sub上机写题，cjb和yzc开始看A和J. sub141分钟提交一发wa，感觉很奇怪，思考之后发现自己代码的错误，之后cjb给出了正确的做法，sub迅速改完之后提交I2y164. 此时只剩下两个多小时，三人先接力尝试了一下D，发现过不了样例，感觉理解有误，遂放弃. 两个小时的时候，决定最后全力开A和J，讨论之后，yzc先去写了一发J的贪心，在204分钟获得wa，决定转向网络流的思考. cjb把A题的dp方程优化到了可以过的程度，决定最后一个半小时，cjb把dinic板子写好，sub和yzc研究完建图的细节后上来敲建图，cjb把第一题的dp框架写好，yzc讨论好A题modify函数的细节后上来接力，按照这样的操作，一个半小时拿下两题应该不成问题. 但始料未及的是，直到比赛结束我们也未能再AC，J题共计交了4发都未能通过，期间cjb一人调试A，yzc和sub合力调J，也没有出现太过频繁的交换机位，但始终未能通过A和J任何一题.最后排名第7，这也是这段时间以来最差的一次排名，结合cf board的情况看，我们仅仅在154名，做出7题起码也有88名，今天三个人发挥十分不理想.

总结

chenjb

今天很糟糕啊.....三个人状态都很差，都有各自的锅要背，但我想说：不要因为这一场失利就down下去啊，这不过是我们组队的第五场比赛，还是要有信心，我们的磨合还要继续努力，个人实力提升还任重道远，要看到目标，看到希望，不要刚出发就躺趴下了，训练训练 fighting！！！

oipotato

今天是集训以来我们队打的最差的一场，从前期的读错题，签到打错，到中期一度落后，中等难度题没想法，后期虽然大概弄出了两题想法但是没有理清细节双开一直到比赛结束一道题都没搞出来。别的不说了，多练练吧，还是太菜了。

subconscious

今日血崩.理应1A的两道的两道签到题贡献了近100罚时(或者这才是常态?),中期由于跟榜落后加大罚时压力,在中等题算法上也没有大的突破.最严重的是AJ两题双开后接连WA,不断换人,进入焦躁状态,最终两题都没有调出来(其实网络流应该可以调出来?).这次比赛暴露了个人实力不足和代码能力不足的问题,在分配交流上也日益乏力.

题解

  • A：因为最大操作数肯定不超过2*n，所以直接f[i][j]表示前i个串，进行j次操作后，第i个串变成的最小串，然后贪心转移，细节十分多，modify函数很难写...
  • B：因为原题题意中实际上只有大小不超过5的强连通分量，所以我们tarjan缩点之后，在DAG上求最长路径即可. cjb的写法是令f[i]表示从i出发，并且此前没有经过i所在scc上任何一个点的最长路径，这样转移起来非常方便，也不需要新建图，只需要对于每个scc保存其和其他scc连接的边即可.求f[x]时，先将x所在scc的所有出边指向的点都遍历完毕，然后以x为起点，暴力跑x所在scc(只走属于端点属于同一个scc的边)，求出x到scc里所有点的最长路径.对于scc里任一条出边(u,v)(x和u属于同一个scc)，f[x]=max(f[x],d[u]+1+f[v])转移即可，注意f[x]还要与max(d[u])(u和x属于同一个scc)取最优，不然会忽略环里的最长路径(cjb因为这里wa了一发)
  • D：建树每次随意取两点,考虑两点间的链,计算其余的点在这条链上的最近祖先和到它的距离,两个式子都形如(dis[x][y]+dis[y][z]-dis[z][x])/2.然后对于链上不存在的祖先点建出虚点,建出这条链,对于对应最近祖先相同的所有点和那个祖先一起递归下去建树即可.注意最后要判定是否合法.计算答案时可以考虑每一条长度为1的边的贡献,也可以考虑子树贡献.数字较大,要用double.
  • J：网络流，建图后跑dinic可过.
  • K

补题

  • A(√)
  • B(√)
  • D(√)
  • J(√)
  • K
附加文件