2017-Sp192-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，yzc '''I1y16'''，cjb上机写D，wa了之后发现有corner case，wa了3发，sub上机写L，'''L1y27'''，之后'''D1y39'''。三人讨论A，'''A1y59'''。yzc上机写J，'''J3y122'''。cjb上机写K，'''K1y130'''。之后cjb继续上机写H，wa了两发很难受。yzc上机写G，'''G2y182'''。sub帮忙查H，终于查出问题，'''H5y189'''。sub和yzc讨论好F，上机'''F2y227'''。之后sub上机写C，'''C1y253'''。
== 总结 ==
=== chenjb ===
开出了B写不完，10题做的比较慢，罚时比较大，代码状态不太行。
=== oipotato ===

=== subconscious  ===

== 题解 ==
 * A：若1和0个数不同，则输出全0或者全1，若个数相同时，将第一位取反，其后所有全部输出与第一位不同的数。

 * B：把去掉一个齿轮想象成切出一棵根节点是虚点的子树。对于每一次修改，找到x所在子树根节点对应的那个儿子y，则所有操作都可以视为对子树y的操作。对于第一问，直接在树上维护子树大小即可。对于第二问，把询问根据点的深度的奇偶性取反，最后取答案时也根据奇偶性取正或负。维护一棵子树切掉一些子树的方法是先打上标记，之后齿轮回来时再计算需要转回去多少。最后把没转回去的齿轮都转回去即可。

 * C：若n>40直接输出随机串，否则写个动态开点的欧拉路径即可。

 * D：分类讨论，中间那块一定要填满且周围非四角的位置至少要有一个，有一维<=2的要特判构造。

 * E：考虑单个障碍，将双方的点与障碍端点连线延长，在x轴上截取的线段称为投影，两点被遮挡当且仅当投影包含，对多个障碍取投影交集即可，套用容斥。注意y轴要大于障碍才可能被遮挡。

 * F：二分答案，每一次显然是拿气球去影响能影响的题中用时最长的，这样贪心得到戳气球的方案，和对方是否能做到这个题数。

 * G：显然的贪心是每次连的边都是度数和最大的，从大到小考虑答案，每次把还没删的但是度数大于等于当前答案的边塞进队列，然后删，一直做下去直到没有边可以删。

 * H：先把所有位置都填成1，判是否合法。之后考虑逐位改为-1，将限制拆成事件，用线段树维护当前有效限制的标记与limit的差值，若min>=1才能将1改成-1。

 * I：模拟。

 * J：枚举每个名字可以取的子序列，从上一步字典序小于自己的答案转移过来，转移用trie树维护。

 * K：边数m为偶数的联通块一定可以分成m/2个，既是上限也是下限，若为奇数，可以无视掉任意一条边同样满足上下限。构造的时候随便一棵生成树，非树边当做随便一个端点额外的一条边即可。从下往上，先取(son1,x,son2)，之后如果还有则取(son,x,father)，dfs求解即可。

 * L：f[I][j]代表到第i位，删了j个数字能取到的最小值，注意不能前导0，最后扫一遍取答案即可。

流水账

出门各自看题，yzc I1y16，cjb上机写D，wa了之后发现有corner case，wa了3发，sub上机写L，L1y27，之后D1y39。三人讨论A，A1y59。yzc上机写J，J3y122。cjb上机写K，K1y130。之后cjb继续上机写H，wa了两发很难受。yzc上机写G，G2y182。sub帮忙查H，终于查出问题，H5y189。sub和yzc讨论好F，上机F2y227。之后sub上机写C，C1y253。

总结

chenjb

开出了B写不完，10题做的比较慢，罚时比较大，代码状态不太行。

oipotato

subconscious

题解

  • A：若1和0个数不同，则输出全0或者全1，若个数相同时，将第一位取反，其后所有全部输出与第一位不同的数。
  • B：把去掉一个齿轮想象成切出一棵根节点是虚点的子树。对于每一次修改，找到x所在子树根节点对应的那个儿子y，则所有操作都可以视为对子树y的操作。对于第一问，直接在树上维护子树大小即可。对于第二问，把询问根据点的深度的奇偶性取反，最后取答案时也根据奇偶性取正或负。维护一棵子树切掉一些子树的方法是先打上标记，之后齿轮回来时再计算需要转回去多少。最后把没转回去的齿轮都转回去即可。
  • C：若n>40直接输出随机串，否则写个动态开点的欧拉路径即可。
  • D：分类讨论，中间那块一定要填满且周围非四角的位置至少要有一个，有一维<=2的要特判构造。
  • E：考虑单个障碍，将双方的点与障碍端点连线延长，在x轴上截取的线段称为投影，两点被遮挡当且仅当投影包含，对多个障碍取投影交集即可，套用容斥。注意y轴要大于障碍才可能被遮挡。
  • F：二分答案，每一次显然是拿气球去影响能影响的题中用时最长的，这样贪心得到戳气球的方案，和对方是否能做到这个题数。
  • G：显然的贪心是每次连的边都是度数和最大的，从大到小考虑答案，每次把还没删的但是度数大于等于当前答案的边塞进队列，然后删，一直做下去直到没有边可以删。
  • H：先把所有位置都填成1，判是否合法。之后考虑逐位改为-1，将限制拆成事件，用线段树维护当前有效限制的标记与limit的差值，若min>=1才能将1改成-1。
  • I：模拟。
  • J：枚举每个名字可以取的子序列，从上一步字典序小于自己的答案转移过来，转移用trie树维护。
  • K：边数m为偶数的联通块一定可以分成m/2个，既是上限也是下限，若为奇数，可以无视掉任意一条边同样满足上下限。构造的时候随便一棵生成树，非树边当做随便一个端点额外的一条边即可。从下往上，先取(son1,x,son2)，之后如果还有则取(son,x,father)，dfs求解即可。
  • L：f[I][j]代表到第i位，删了j个数字能取到的最小值，注意不能前导0，最后扫一遍取答案即可。
附加文件