2021-team8-004

从 Trac 迁移的文章

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

原文章内容如下：

= 流水账 =
前三题签到挺好，L卡的时间有点长，期间F和J都会写了，然后yys先下机思考，F开始写，也卡了，xqj先下机思考，J开始写，调的过程中F看出错了（i写成j），随后J过了，不久后L也过了，成功摆脱垫底。然后上B，写出来了，大点很卡，偷偷用了之前的压缩表。此时K有思路，但是觉得很难写，没有信心，C讨论后出了一个完善的做法，rtx开始上机写，然后不停WA大点，最终调试无果。

= 总结 =
有可写的题时最好不要让机上的队友花太多时间调试，可以先下机思考细节。需要完善板子（如这场中的圆方树板子）。

= 题解 =
A: 签到

B: 性质：如果一个某个数不是bindecimal，那么以他为后缀的任何一个数都不是。所以每次在所有bindecimal数前加1即可。值得一提的是，如果进制转化是len^2的话，10000根本跑不过去，最后靠部分打表（还要压缩）才过去。

C: 若删非环边，则将两边联通块大小乘起来。若删环边，考虑将所有环边先去掉，成为森林，每棵树内部任意连边，只需要找出当前环的每个点所在的树大小之和。（写一下WA的原因：搜环的时候用一个栈存搜到的点，找到环就不断弹栈，注意到最前面的点不能弹出。但这样依旧是错的，因为中间的点也可能在其他的环中，也不一定能弹。较好的做法是每个点记录前驱点。）

D: （提前口胡，做完再补：一定可以找到一条边，很平均地将当前多边形分成两部分，所以可以求一些最短路然后分治下去，最后建成一个KD-tree，询问再上面跳即可）

E: 签到

F: 二分答案，bfs搜索

G: 先每个数组里选最大的，看和是不是k的倍数，如果是的话，就找“不和本数组最大数同余”的最大的数

H: 

I: 

J: 先不停随机找到一个n/2的回答（500次肯定够），然后在这个数列基础上一个1变0，一个0变1，询问后如果仍是n/2，那么这两位的数是不同的，否则是相同的，这样搞n-1次就能得到所有n个数的异或关系，两种情况都问一遍就好。

K: 链缩在一起，搜索。具体实现可以用并查集记录每个点不停沿唯一出边会走到哪个点，并记录走的距离（用来搜索时判断是否走过恰好n条边），搜索时向下递归时直接走到最前头，并加上走的距离，判断是否已经过只要判最前面的点就可以。~~数据好造，可以自己拍几组~~。

L: 二分高度，枚举中间的位置

流水账

前三题签到挺好，L卡的时间有点长，期间F和J都会写了，然后yys先下机思考，F开始写，也卡了，xqj先下机思考，J开始写，调的过程中F看出错了（i写成j），随后J过了，不久后L也过了，成功摆脱垫底。然后上B，写出来了，大点很卡，偷偷用了之前的压缩表。此时K有思路，但是觉得很难写，没有信心，C讨论后出了一个完善的做法，rtx开始上机写，然后不停WA大点，最终调试无果。

总结

有可写的题时最好不要让机上的队友花太多时间调试，可以先下机思考细节。需要完善板子（如这场中的圆方树板子）。

题解

A: 签到

B: 性质：如果一个某个数不是bindecimal，那么以他为后缀的任何一个数都不是。所以每次在所有bindecimal数前加1即可。值得一提的是，如果进制转化是len^2的话，10000根本跑不过去，最后靠部分打表（还要压缩）才过去。

C: 若删非环边，则将两边联通块大小乘起来。若删环边，考虑将所有环边先去掉，成为森林，每棵树内部任意连边，只需要找出当前环的每个点所在的树大小之和。（写一下WA的原因：搜环的时候用一个栈存搜到的点，找到环就不断弹栈，注意到最前面的点不能弹出。但这样依旧是错的，因为中间的点也可能在其他的环中，也不一定能弹。较好的做法是每个点记录前驱点。）

D: （提前口胡，做完再补：一定可以找到一条边，很平均地将当前多边形分成两部分，所以可以求一些最短路然后分治下去，最后建成一个KD-tree，询问再上面跳即可）

E: 签到

F: 二分答案，bfs搜索

G: 先每个数组里选最大的，看和是不是k的倍数，如果是的话，就找“不和本数组最大数同余”的最大的数

H:

I:

J: 先不停随机找到一个n/2的回答（500次肯定够），然后在这个数列基础上一个1变0，一个0变1，询问后如果仍是n/2，那么这两位的数是不同的，否则是相同的，这样搞n-1次就能得到所有n个数的异或关系，两种情况都问一遍就好。

K: 链缩在一起，搜索。具体实现可以用并查集记录每个点不停沿唯一出边会走到哪个点，并记录走的距离（用来搜索时判断是否走过恰好n条边），搜索时向下递归时直接走到最前头，并加上走的距离，判断是否已经过只要判最前面的点就可以。数据好造，可以自己拍几组。

L: 二分高度，枚举中间的位置