2017-C24-team8

从 Trac 迁移的文章

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

原文章内容如下：

AI 略去不提。
=== B ===
后缀suf[i]和suf[j]的比较可以视为pair(s[i], suf[i+1])和pair(s[j], suf[j+1])的比较。对于后缀数组sa[]，可以直接得出s[sa[i]]<=s[s[i+1]]。当且仅当suf[sa[i]+1]>suf[sa[i+1]+1]时，相邻后缀的大小关系依赖于s[sa[i]]和s[sa[i+1]]，此时这两位应该严格小于。求出严格小于的位置数量后求组合数。O(n+sigma*log^2n)。
=== C ===
枚举矩形上下边界转化为一维问题。枚举要修改的列，求向前向后的最大连续子序列和（可以用两边普通的最大连续子序列和实现）。注意特判解为整个矩形的情况。O(n^3^)。
=== D ===
2017 CTSC D1T2 削弱？
=== E ===
=== F ===
=== G ===
将格子的中心视为点，容易发现交错点（起终点和其他有两个方向线段经过的点）之间距离都是d=gcd(n-1,m-1)，可以将其压缩到((n-1)/d,(m-1)/d)的问题，这些非交错点的数量直接根据球通过距离（lcm）计算即可。边长互质之后的图形非常简单，可以推公式计算。O(logn)。
=== H ===
将两个数组分别降序排序。枚举其中一侧，用bitset维护另一侧与当前数之和大于w的位置，每轮bitset右移取或。O(n^2^/bitset)。
=== J ===
将pair(s, K)视为一个点，操作视为边。通过给每个点加入一个前置结点，将345操作的代价分解开来，使得可以用BFS解决（也可以用两个queue维护）。状态表示可以用类似康托展开的方法处理，用数组记录。或者压缩到一个 int（3+1+3*7=25，1 为前置节点的标志位），用map或unordered_map处理。后者的状态变换都可以用位运算实现而不需要来回转换，可能会更快。O(mlog(m!)*m!)，m=7。

AI 略去不提。

B

后缀suf[i]和suf[j]的比较可以视为pair(s[i], suf[i+1])和pair(s[j], suf[j+1])的比较。对于后缀数组sa[]，可以直接得出s[sa[i]]<=s[s[i+1]]。当且仅当suf[sa[i]+1]>suf[sa[i+1]+1]时，相邻后缀的大小关系依赖于s[sa[i]]和s[sa[i+1]]，此时这两位应该严格小于。求出严格小于的位置数量后求组合数。O(n+sigma*log^2n)。

C

枚举矩形上下边界转化为一维问题。枚举要修改的列，求向前向后的最大连续子序列和（可以用两边普通的最大连续子序列和实现）。注意特判解为整个矩形的情况。O(n³)。

D

2017 CTSC D1T2 削弱？

E

F

G

将格子的中心视为点，容易发现交错点（起终点和其他有两个方向线段经过的点）之间距离都是d=gcd(n-1,m-1)，可以将其压缩到((n-1)/d,(m-1)/d)的问题，这些非交错点的数量直接根据球通过距离（lcm）计算即可。边长互质之后的图形非常简单，可以推公式计算。O(logn)。

H

将两个数组分别降序排序。枚举其中一侧，用bitset维护另一侧与当前数之和大于w的位置，每轮bitset右移取或。O(n²/bitset)。

J

将pair(s, K)视为一个点，操作视为边。通过给每个点加入一个前置结点，将345操作的代价分解开来，使得可以用BFS解决（也可以用两个queue维护）。状态表示可以用类似康托展开的方法处理，用数组记录。或者压缩到一个 int（3+1+3*7=25，1 为前置节点的标志位），用map或unordered_map处理。后者的状态变换都可以用位运算实现而不需要来回转换，可能会更快。O(mlog(m!)*m!)，m=7。