2021-team02-004

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team02 返回]

[[Image(Rank.png,1000px)]]

= 概述 =

 solved: ??/??

 rank: ??

= 流水账 =

今天验题赛，所以没有大榜。

开场 cxt 跟榜签到 H，然后 cy 光速会了 A，可是 A 复杂又卡常卡空间。cy 在多次卡各种东西后通过。其间 pb 会了 F 并且穿插在 A 的调试之间通过了。

中期，cxt 过了 J，cy 边想边推过了 E，pb 推出了 G 的式子并且较快通过。

后期，cy 开始写非常难写的 E，cxt 在机下和 pb 讨论后发现了 C 的奇怪做法。最后22min，cy 发现少写了一棵线段树，于是 cxt 上机冲 C，运气不错在还有 7min 的时候一发过了

= 总结 =

=== pb： ===
G题开的很慢，自己没有在思路出现问题的时候快速跳出之前的思路，错误得估计了题目难度，往比较难的方向想了，但其实是很简单的题

另外决策上的小问题大概是没听懂cxt给的K的提示，可能有一半是对的，但是卡特兰数可能自己也没细想，导致K没有想到应该怎么算，所以可能我自己写G是更好的选择，这样cxt有更多的时间准备C

但是赛中很难想到C是个很可做的题，榜上根本没有，前面也没有明确的思路，感觉还是需要多做尝试

遗憾的是E留下的时间不太够，另外见识的还不够多吧

=== Creatix： ===
确实，后来想想 J 还是写慢了。
主要是当时抄代码抄的很~~（拖沓）~~细心，然后后面写的也不快。

样例倒是没怎么调直接过了。

可惜没能给 cy 省出更多时间写 E。
=== Eden_CY： ===

事实证明用string存字符串开的空间比用数组大不少。

最后写E的时候还是有点没想清楚。

最近经常写bug，要注意下细节。


= 题解 =

 * A：类似建虚树把缩点后的Trie树建出来，把父结点被标记且子树内没有标记的点计入答案。

 * B：sub哥哥的推理题。

 * C：考虑优化匈牙利算法。前 n - 100 个点可以按顺序直接匹配，不需要反悔，或者说增广路长为 1，所以简单set维护即可。最后 100 个点，模拟匈牙利算法：首先把待匹配的女士点的出边全部访问一遍，这样就只有 100 个点（即待匹配的女士不想匹配的男士）没有 vis 过，所以之后找出边的时候只需要考虑每个点的出边和那 100 个点的交集。于是，除了待匹配点，每个其它点的有意义的出边最多只有 100 条。这样的话，总边数是 O(n * 100) 级别的，直接套用匈牙利算法即可。因为要对100个点求增广路，总复杂度 O(n * 100 * 100)

 * D：对直径长度为奇数的点，枚举中间的边构造。对直径长度为偶数的点，枚举中间的点构造。

 * E：线段树。

 * F：签到，按儿子个数从大到小排序贪心即可。

 * G：广义容斥，直接算至少有k个人活着的概率

 * H：签到构造。

 * I：一个重要的思路是，看到根号上取整，就要想到可能是转换成一个 m * m 的矩阵然后把空余位置补全。很巧妙~~（奇怪）~~的构造。大概就是先转换成矩阵，然后稍微处理一下让奇偶个数不同。

 * J：抄个点到多边形的切线的板子就过了。另外，询问最少数量的环上的区间是否覆盖了整个环可以用倍增。

 * K：首先两维独立，要算ans(t)为走t步在[1,n]之内的方案数。考虑两个算法。1.f(i,j)代表走了i步在j的概率，就是朴素的dp，复杂度O(tn)。2.考虑ans(t)=2·ans(t-1)-f(t-1,1)-f(t-1,n)，计算f(t-1,1)可以用容斥，设L(i)为i关于0的对称点，R(i)为i关于n的对称点，g(i)为走到i的方案数，那么有f(t,1)=g(1)-g(L(1))-g(R(1))+g(R(L(1)))+g(L(R(1)))... 这部分每次对称距离会增加n，复杂度为O(t^2^/n)。 两种算法big small即可。

[/wiki/2021-team02 返回]

概述

solved: ??/??

rank: ??

流水账

今天验题赛，所以没有大榜。

开场 cxt 跟榜签到 H，然后 cy 光速会了 A，可是 A 复杂又卡常卡空间。cy 在多次卡各种东西后通过。其间 pb 会了 F 并且穿插在 A 的调试之间通过了。

中期，cxt 过了 J，cy 边想边推过了 E，pb 推出了 G 的式子并且较快通过。

后期，cy 开始写非常难写的 E，cxt 在机下和 pb 讨论后发现了 C 的奇怪做法。最后22min，cy 发现少写了一棵线段树，于是 cxt 上机冲 C，运气不错在还有 7min 的时候一发过了

总结

pb：

G题开的很慢，自己没有在思路出现问题的时候快速跳出之前的思路，错误得估计了题目难度，往比较难的方向想了，但其实是很简单的题

另外决策上的小问题大概是没听懂cxt给的K的提示，可能有一半是对的，但是卡特兰数可能自己也没细想，导致K没有想到应该怎么算，所以可能我自己写G是更好的选择，这样cxt有更多的时间准备C

但是赛中很难想到C是个很可做的题，榜上根本没有，前面也没有明确的思路，感觉还是需要多做尝试

遗憾的是E留下的时间不太够，另外见识的还不够多吧

Creatix：

确实，后来想想 J 还是写慢了。

主要是当时抄代码抄的很（拖沓）细心，然后后面写的也不快。

样例倒是没怎么调直接过了。

可惜没能给 cy 省出更多时间写 E。

Eden_CY：

事实证明用string存字符串开的空间比用数组大不少。

最后写E的时候还是有点没想清楚。

最近经常写bug，要注意下细节。

题解

• A：类似建虚树把缩点后的Trie树建出来，把父结点被标记且子树内没有标记的点计入答案。
• B：sub哥哥的推理题。
• C：考虑优化匈牙利算法。前 n - 100 个点可以按顺序直接匹配，不需要反悔，或者说增广路长为 1，所以简单set维护即可。最后 100 个点，模拟匈牙利算法：首先把待匹配的女士点的出边全部访问一遍，这样就只有 100 个点（即待匹配的女士不想匹配的男士）没有 vis 过，所以之后找出边的时候只需要考虑每个点的出边和那 100 个点的交集。于是，除了待匹配点，每个其它点的有意义的出边最多只有 100 条。这样的话，总边数是 O(n * 100) 级别的，直接套用匈牙利算法即可。因为要对100个点求增广路，总复杂度 O(n * 100 * 100)
• D：对直径长度为奇数的点，枚举中间的边构造。对直径长度为偶数的点，枚举中间的点构造。
• E：线段树。
• F：签到，按儿子个数从大到小排序贪心即可。
• G：广义容斥，直接算至少有k个人活着的概率
• H：签到构造。
• I：一个重要的思路是，看到根号上取整，就要想到可能是转换成一个 m * m 的矩阵然后把空余位置补全。很巧妙（奇怪）的构造。大概就是先转换成矩阵，然后稍微处理一下让奇偶个数不同。
• J：抄个点到多边形的切线的板子就过了。另外，询问最少数量的环上的区间是否覆盖了整个环可以用倍增。
• K：首先两维独立，要算ans(t)为走t步在[1,n]之内的方案数。考虑两个算法。1.f(i,j)代表走了i步在j的概率，就是朴素的dp，复杂度O(tn)。2.考虑ans(t)=2·ans(t-1)-f(t-1,1)-f(t-1,n)，计算f(t-1,1)可以用容斥，设L(i)为i关于0的对称点，R(i)为i关于n的对称点，g(i)为走到i的方案数，那么有f(t,1)=g(1)-g(L(1))-g(R(1))+g(R(L(1)))+g(L(R(1)))... 这部分每次对称距离会增加n，复杂度为O(t²/n)。 两种算法big small即可。

附加文件

• Rank.png by Creatix