2022-team8-001

从 Trac 迁移的文章

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

原文章内容如下：

= 概览 =

通过数：5/10 Rank：7/15 dirt: 80%

== Rank和提交情况 ==
[[Image(1.png, 1000px)]]

Ranking耻辱柱

提交记录太长了（因为WA的很多），就不贴了

= 流水账 =

开局迅速过掉A和H，然后同时开C和D。C一开始的想法是假的，一开始以为最后答案形如a...ab...bc...c...，这样没有考虑到前面已经用过的字母可以再次使用。最后才决定直接搜索。在此期间王楚淏想出G的做法，主体部分是对的，但是用了奇怪的枚举方式，导致一开始不停WA、TLE。直到3.5h左右才想到6^n^的做法并迅速通过。期间一直在思考D的做法，但一直未能想出O(pT)的做法（某种程度上来说也没有确定正解是O(pT)的），直到2h45min左右才确定了O(pT)的算法。但是因为写法过于暴力（甚至有显然会跑满nT的写法）以及在答案为-1时优化不足，TLE了很多次。最后1h15min左右开了E，写了一半最后发现有一些地方不可维护。直到最后五分钟王楚淏提出了一个可能是正确的分治做法（跟讲题时给出的算法很相似）。

= 总结 =

rtx: 
原根的应用依旧不熟练，记得暑假集训刚刚因为一道原根的题不会做翻大车，这次又复刻了。以后一定记得模意义下取幂要想一想原根。（而且问题也出在一直觉得O(PT)的复杂度不对，中间想到了原根，但是又想到没法求指标，所以直接否掉了）。  
然后C浪费了很多时间，主要因为忽略了要求字典序最小，谢罪。后来看到之后有点慌，稍微想想觉得之前的构造好像也对，但是实际上已经不对了，谢罪。  
然后还有老毛病，一旦前面有题卡着，后面就没法静下心来想题，想的不透彻就开码，导致后面的题也都出了问题（不管是不是我写的，但是都参与了），磕头谢罪。  
整体节奏很不对，大概是从C想假开始的，后半场就不敢看榜了。。。如果C早过一个小时，感觉后面可以比较顺利。  
E也要谢罪，也是想假了浪费了很多时间。分治依旧是考虑过然后直接否掉了，觉得一般分治能做的按顺序枚举都能做而且复杂度更好，看来是误区了。  

= 题解 =
 * A：一波条件概率推导，可以得到黑球个数位于[a, b]中的概率为\frac{\sum_{i=a}!^bC(i,l1)*C(n-i,l2)}{\sum_{i=0}\}!^nC(i,l1)*C(n-i,l2)}，然后暴力枚举区间长度和a即可。

 * B：

 * C：首先枚举长度，计算需要多少重复子串，然后爆搜。枚举每一位填哪个字母，为了保证字典序最小，只需要尝试所有之前出现过的字母和未出现过的第一个字母即可。计算这一位带来多少重复子串，然后搜索下一位。如果不需要更多重复子串，则接下来的每一位都填入之前未出现过的字母即可。

 * D：首先可知，如果有解，则必定存在一个x=1的解。于是问题转化为1+y^n^=z^n^(mod p)。如果用快速幂把所有y^n^ mod p都计算出来，那么时间复杂度是O(pTlogp)的。考虑怎样使时间复杂度降至O(pT)。可以发现，如果能找到模p的一个原根g，那么我们只需要每次乘g就能得到所有y。这样我们可以通过乘g^n^得到所有y^n^，就只需要一次快速幂了。注意优化：如果某个g^ni^已经出现过了就应该break，可以在答案为-1时提供非常有效的优化。

 * E：考虑分治，先按x分为左右两段，每一段内按照y排序，在右边扫的同时维护左边的一个关于x的单调栈，通过树状数组或者其他什么东西找到右边当前点合法的区间，在左边的单调栈里二分，统计答案。

 * F：取原图的补图，则两个点之间有边当且仅当他们属于同一个clause或他们是同一个变量的正反。由此可以得到补图的如下性质：1. 点数是3的倍数 2. 每个点属于且仅属于一个三元环 3. 去掉2中所有三元环的边后，剩下的图是一个完全二分图（意味着是一个二分图，且每个联通块所有左右部点之间都有边） 4. 该二分图中每个联通块中所有点属于不同的clause（也就是在2中位于不同的三元环内）。根据以上四个性质进行模拟即可。

 * G：如果多边形边数≥4，那么如果要使最后形成的多边形面积最小，我们肯定希望某些边重合直至成为三角形。我们可以任意选中两条长度分别为a和b的边重合起来，把它看作一条长为|a-b|的边。这其实相当于：已知最后是一个三角形，对于原来多边形的每一条边（设长度为a），我们可以将a或-a加入三条边中的任何一个。最后对于所有合法三角形求面积最小的。时间复杂度O(6^n^)。

 * H：首先可以发现，必然存在一种方案，使得所求的最短路的两个端点都在给定的k个点中。于是，两个端点必然是所有点中距离最远的两个点。由最短路树可知，两次Dijkstra即可找到两个端点。在Dijkstra时，需要记录方案。为了保证最后找到的最短路就是包含k个特殊点的，我们可以在路径长度相同时优先选择经过特殊点尽可能多的。

 * I：

 * J：

概览

通过数：5/10 Rank：7/15 dirt: 80%

Rank和提交情况

Ranking耻辱柱

提交记录太长了（因为WA的很多），就不贴了

流水账

开局迅速过掉A和H，然后同时开C和D。C一开始的想法是假的，一开始以为最后答案形如a...ab...bc...c...，这样没有考虑到前面已经用过的字母可以再次使用。最后才决定直接搜索。在此期间王楚淏想出G的做法，主体部分是对的，但是用了奇怪的枚举方式，导致一开始不停WA、TLE。直到3.5h左右才想到6ⁿ的做法并迅速通过。期间一直在思考D的做法，但一直未能想出O(pT)的做法（某种程度上来说也没有确定正解是O(pT)的），直到2h45min左右才确定了O(pT)的算法。但是因为写法过于暴力（甚至有显然会跑满nT的写法）以及在答案为-1时优化不足，TLE了很多次。最后1h15min左右开了E，写了一半最后发现有一些地方不可维护。直到最后五分钟王楚淏提出了一个可能是正确的分治做法（跟讲题时给出的算法很相似）。

总结

rtx:

原根的应用依旧不熟练，记得暑假集训刚刚因为一道原根的题不会做翻大车，这次又复刻了。以后一定记得模意义下取幂要想一想原根。（而且问题也出在一直觉得O(PT)的复杂度不对，中间想到了原根，但是又想到没法求指标，所以直接否掉了）。

然后C浪费了很多时间，主要因为忽略了要求字典序最小，谢罪。后来看到之后有点慌，稍微想想觉得之前的构造好像也对，但是实际上已经不对了，谢罪。

然后还有老毛病，一旦前面有题卡着，后面就没法静下心来想题，想的不透彻就开码，导致后面的题也都出了问题（不管是不是我写的，但是都参与了），磕头谢罪。

整体节奏很不对，大概是从C想假开始的，后半场就不敢看榜了。。。如果C早过一个小时，感觉后面可以比较顺利。

E也要谢罪，也是想假了浪费了很多时间。分治依旧是考虑过然后直接否掉了，觉得一般分治能做的按顺序枚举都能做而且复杂度更好，看来是误区了。

题解

• A：一波条件概率推导，可以得到黑球个数位于[a, b]中的概率为\frac{\sum_{i=a}!^{bC(i,l1)*C(n-i,l2)}{\sum_{i=0}\}!}nC(i,l1)*C(n-i,l2)}，然后暴力枚举区间长度和a即可。
• B：
• C：首先枚举长度，计算需要多少重复子串，然后爆搜。枚举每一位填哪个字母，为了保证字典序最小，只需要尝试所有之前出现过的字母和未出现过的第一个字母即可。计算这一位带来多少重复子串，然后搜索下一位。如果不需要更多重复子串，则接下来的每一位都填入之前未出现过的字母即可。
• D：首先可知，如果有解，则必定存在一个x=1的解。于是问题转化为1+yⁿ=zⁿ(mod p)。如果用快速幂把所有yⁿ mod p都计算出来，那么时间复杂度是O(pTlogp)的。考虑怎样使时间复杂度降至O(pT)。可以发现，如果能找到模p的一个原根g，那么我们只需要每次乘g就能得到所有y。这样我们可以通过乘gⁿ得到所有yⁿ，就只需要一次快速幂了。注意优化：如果某个gⁿⁱ已经出现过了就应该break，可以在答案为-1时提供非常有效的优化。
• E：考虑分治，先按x分为左右两段，每一段内按照y排序，在右边扫的同时维护左边的一个关于x的单调栈，通过树状数组或者其他什么东西找到右边当前点合法的区间，在左边的单调栈里二分，统计答案。
• F：取原图的补图，则两个点之间有边当且仅当他们属于同一个clause或他们是同一个变量的正反。由此可以得到补图的如下性质：1. 点数是3的倍数 2. 每个点属于且仅属于一个三元环 3. 去掉2中所有三元环的边后，剩下的图是一个完全二分图（意味着是一个二分图，且每个联通块所有左右部点之间都有边） 4. 该二分图中每个联通块中所有点属于不同的clause（也就是在2中位于不同的三元环内）。根据以上四个性质进行模拟即可。
• G：如果多边形边数≥4，那么如果要使最后形成的多边形面积最小，我们肯定希望某些边重合直至成为三角形。我们可以任意选中两条长度分别为a和b的边重合起来，把它看作一条长为|a-b|的边。这其实相当于：已知最后是一个三角形，对于原来多边形的每一条边（设长度为a），我们可以将a或-a加入三条边中的任何一个。最后对于所有合法三角形求面积最小的。时间复杂度O(6ⁿ)。
• H：首先可以发现，必然存在一种方案，使得所求的最短路的两个端点都在给定的k个点中。于是，两个端点必然是所有点中距离最远的两个点。由最短路树可知，两次Dijkstra即可找到两个端点。在Dijkstra时，需要记录方案。为了保证最后找到的最短路就是包含k个特殊点的，我们可以在路径长度相同时优先选择经过特殊点尽可能多的。
• I：
• J：

附加文件

• 1.png by rtxxx