2017-Sp207-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，sub丢了算法给cjb，发现假了，yzc上机'''A1y13'''，然后cjb写D又假了，yzc上机'''B1y26'''，sub上机写G，'''G1y73'''。cjb上机写K，然后yzc和sub研究C和D，之后'''C1y104'''，'''D1y112'''。cjb写完了K，'''K1y153'''，yzc上机'''J1y175'''。之后cjb和yzc搞E，疯狂wa之后各种corner case，'''E6y251'''。sub想H和I，cjb想到H之后上机开始写，sub也想好了I，疯狂rush，最后赛后6min过I，27min过H。
== 总结 ==
=== chenjb ===
绝杀大失败，呜呜呜，nmd，wsm，nmd，wsl。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：根据题意模拟。

 * B：枚举。

 * C：算出所有人的最短时间，排序，每个人跟前一个人结果+1取max，输出最后一个人的时间。

 * D：广搜。

 * E：建出补图，在生成树上，如果x在原图度数是奇，则把x和fa[x]连边，之后根据联通块情况及是否是团或单点情况分类讨论，需细心处理。

 * F：sub

 * G：从小到大考虑，每次要么放在最左边，要么放在最右边，取较小的，注意相同数字，要先全部删除再计算距离。

 * H：从左上到右下的顺序依次染色，如果邻边颜色不足4个，则直接染色，否则一定只有4条邻边染色且颜色不相同，此时考虑按顺时针顺序编号，若1和3连通，则2和4不连通，此时考虑选择合法的一组把颜色反色即可减少一种颜色。

 * I：像逆矩阵一样后面添n个元素，高斯消元，问题转化为每次将第m+i列异或上第j列之后前m列的秩有无变化，可以根据m+i列的秩和前m列的秩分类讨论得到。

 * J：对于某种颜色，按照dfs序排成一个环，答案是深度和减去所有相邻两人lca的深度，用set维护即可。

 * K：显然sort之后可以通过贪心确定答案，考虑逐位二分答案，通过贪心检测最大答案是否发生变化，注意有两段合法区间需要分别二分，同时需小心保证复杂度为O(n^2^logn)。

流水账

出门各自看题，sub丢了算法给cjb，发现假了，yzc上机A1y13，然后cjb写D又假了，yzc上机B1y26，sub上机写G，G1y73。cjb上机写K，然后yzc和sub研究C和D，之后C1y104，D1y112。cjb写完了K，K1y153，yzc上机J1y175。之后cjb和yzc搞E，疯狂wa之后各种corner case，E6y251。sub想H和I，cjb想到H之后上机开始写，sub也想好了I，疯狂rush，最后赛后6min过I，27min过H。

总结

chenjb

绝杀大失败，呜呜呜，nmd，wsm，nmd，wsl。

oipotato

subconscious

题解

  • A：根据题意模拟。
  • B：枚举。
  • C：算出所有人的最短时间，排序，每个人跟前一个人结果+1取max，输出最后一个人的时间。
  • D：广搜。
  • E：建出补图，在生成树上，如果x在原图度数是奇，则把x和fa[x]连边，之后根据联通块情况及是否是团或单点情况分类讨论，需细心处理。
  • F：sub
  • G：从小到大考虑，每次要么放在最左边，要么放在最右边，取较小的，注意相同数字，要先全部删除再计算距离。
  • H：从左上到右下的顺序依次染色，如果邻边颜色不足4个，则直接染色，否则一定只有4条邻边染色且颜色不相同，此时考虑按顺时针顺序编号，若1和3连通，则2和4不连通，此时考虑选择合法的一组把颜色反色即可减少一种颜色。
  • I：像逆矩阵一样后面添n个元素，高斯消元，问题转化为每次将第m+i列异或上第j列之后前m列的秩有无变化，可以根据m+i列的秩和前m列的秩分类讨论得到。
  • J：对于某种颜色，按照dfs序排成一个环，答案是深度和减去所有相邻两人lca的深度，用set维护即可。
  • K：显然sort之后可以通过贪心确定答案，考虑逐位二分答案，通过贪心检测最大答案是否发生变化，注意有两段合法区间需要分别二分，同时需小心保证复杂度为O(n2logn)。
附加文件