2022-team8-005

从 Trac 迁移的文章

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

原文章内容如下：

= 概览 =

通过数：10/11 Rank：2/15

== Rank和提交情况 ==


= 流水账 =
这场比赛其实并不是特别顺，但是中程大家的思路都比较流畅，囤了比较多的可写的题，最后靠着通过数取得了一个不差的排名。

= 总结 =

=== xqj： ===
~~这里是总结~~

=== rtx： ===
~~这里是总结~~

=== wch： ===
开场非常想抢一血，K题在比赛开始一分钟的时候就开始写了，结果出了好多小错误，有点不应该。
其实这种事发生好多次了，不应该把一血看得那么重要的。


= 题解 =

 * A：

 * B：枚举△j，这样题目就变成了：按一个顺序循环拼接每一行，使得字典序最小。解决这个问题，可以先用Hash求LCP之后Sort一遍，求出每一行的字典序排名，再用后缀数组寻找排名最靠前的后缀，即找到了△i。最后暴力比较一遍所有的（△i，△j），找到最小的就好了。

 * C：思路：先找出离原点最近的点，这个点一定是好点。然后再把在（原点与当前点连线的垂线）之外的点都删掉，因为它们都不是好点。在此之后，再找剩下的离原点最近的点，以此类推，直到全部找完。想实现这个思路，可以用李超树动态维护关于原点的上凸包和下凸包，这样就可以O（logn）判断一个点在不在凸包内，也可以O（logn）给凸包插入一条直线了。

 * D：因为l很小，考虑容斥。枚举一个选集合的状态，计算出（这个状态内所有集合都一定不合法，其他随意）的方案数，然后便可以容斥计算出（这个状态内所有集合一定不合法，其他一定合法）的方案数，这样就计算出答案了。

 * E：

 * F：我们选择一个集合，把集合内的字符放到最前面在翻转，可以发现这种做法一定对应一种选择若干前缀再翻转的方案。那么我们只需要倒着扫一遍再正着扫一遍，寻找能转换出的字典序最小的字符串就好了。

 * G：

 * H：枚举每一条边假设它连接了(u,v)。假如u和v拥有都没用过的颜色，那么可以直接给这条边染色。否则，可以选择一个u拥有但是v没有的颜色，然后递归判断能否把连接u的这种颜色的边换成别的颜色。因为不知道正确性所以打的random_shuffle枚举颜色。

 * I：

 * J：对于一个前缀，它只可能有五种有效的状态：（完全匹配；多了一个<i>；多了一个<b>；两个都有且<i>在前面；两个都有且<b>在前面）。dp转移这些状态，假如到n的时候存在第一种状态，那么就存在答案。

 * K：每个数的具体值并没有影响，存在影响的只是这个数二进制位1的个数。设dp[i][j]表示（前i个数，有j位的异或和位1）这个状态是否存在。从i转移到i+1的时候，枚举第i+1个数在这j个位中的k个放1，其他放在异或和为0的位。dp[n][0]=1则存在答案，过程中记一下前驱和当前数值即可得到方案。

概览

通过数：10/11 Rank：2/15

Rank和提交情况

流水账

这场比赛其实并不是特别顺，但是中程大家的思路都比较流畅，囤了比较多的可写的题，最后靠着通过数取得了一个不差的排名。

总结

xqj：

这里是总结

rtx：

这里是总结

wch：

开场非常想抢一血，K题在比赛开始一分钟的时候就开始写了，结果出了好多小错误，有点不应该。

其实这种事发生好多次了，不应该把一血看得那么重要的。

题解

  • A：
  • B：枚举△j，这样题目就变成了：按一个顺序循环拼接每一行，使得字典序最小。解决这个问题，可以先用Hash求LCP之后Sort一遍，求出每一行的字典序排名，再用后缀数组寻找排名最靠前的后缀，即找到了△i。最后暴力比较一遍所有的（△i，△j），找到最小的就好了。
  • C：思路：先找出离原点最近的点，这个点一定是好点。然后再把在（原点与当前点连线的垂线）之外的点都删掉，因为它们都不是好点。在此之后，再找剩下的离原点最近的点，以此类推，直到全部找完。想实现这个思路，可以用李超树动态维护关于原点的上凸包和下凸包，这样就可以O（logn）判断一个点在不在凸包内，也可以O（logn）给凸包插入一条直线了。
  • D：因为l很小，考虑容斥。枚举一个选集合的状态，计算出（这个状态内所有集合都一定不合法，其他随意）的方案数，然后便可以容斥计算出（这个状态内所有集合一定不合法，其他一定合法）的方案数，这样就计算出答案了。
  • E：
  • F：我们选择一个集合，把集合内的字符放到最前面在翻转，可以发现这种做法一定对应一种选择若干前缀再翻转的方案。那么我们只需要倒着扫一遍再正着扫一遍，寻找能转换出的字典序最小的字符串就好了。
  • G：
  • H：枚举每一条边假设它连接了(u,v)。假如u和v拥有都没用过的颜色，那么可以直接给这条边染色。否则，可以选择一个u拥有但是v没有的颜色，然后递归判断能否把连接u的这种颜色的边换成别的颜色。因为不知道正确性所以打的random_shuffle枚举颜色。
  • I：
  • J：对于一个前缀，它只可能有五种有效的状态：（完全匹配；多了一个；多了一个；两个都有且在前面；两个都有且在前面）。dp转移这些状态，假如到n的时候存在第一种状态，那么就存在答案。
  • K：每个数的具体值并没有影响，存在影响的只是这个数二进制位1的个数。设dp[i][j]表示（前i个数，有j位的异或和位1）这个状态是否存在。从i转移到i+1的时候，枚举第i+1个数在这j个位中的k个放1，其他放在异或和为0的位。dp[n][0]=1则存在答案，过程中记一下前驱和当前数值即可得到方案。
附加文件