2021-team06-C210815

从 Trac 迁移的文章

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

原文章内容如下：

[/wiki/2021-team6 返回]

== Ranklist ==

[[Image(210815-standing.png,800px)]]

== submission ==

[[Image(210815-submission3.png,800px)]]
[[Image(210815-submission2.png,800px)]]
[[Image(210815-submission1.png,800px)]]


== 概述 ==

solved: 10/11  dirt: 60%

rank: 7



==  ==

== 总结 ==

whn:
yja又出现签到失误了，以至于最后又需要顽强拼搏。如果运气稍微差一点点可能校内榜就直接掉的很难看了。
队友需要多练练icpc类型的题了。。


== 题解 ==

A: 签到

B: 利用好凸联通的性质，先枚举行，然后二分找最远的1区间范围为这一行扩展的行并结算答案；也可以双指针扫。 yja由于二分没写对在考场自闭。

C："words are given by dictionary"使得这题可以直接一个个格子搜索确定。建好行字典树和列字典树以后，全局变量记录四列字典树指针，局部变量记录行字典树指针，搜索即可。

D：有意义的点就是每列最上和最下的点，取中位数即可。

E：签到

F：对每个点极角排序以后，双指针，对每个左端点枚举最长的区间更新答案即可。

G：建一棵主席树，边界节点为所有的子串，对于SUB操作需要在对应字符串的树上找，对于ADD操作就开一个新根，左右儿子分别为对应的原根。

H：转化后就是一个三维偏序，实战写的十分稳健。

I：模拟题，yja由于噪音点判错再次自闭。

J：一种可行的办法：由于可以认为随机数生成器是均匀随机的(unbiased), 四个随机数生成器先取出足够的多(2000个）的保证前bound位全0的位置，然后前两个两重循环枚举所有组合用map记录，后面两个随机找能否对上n-bound位。”足够多“取2047个，bound取10可通过此题。

K：区间DP，预处理每个子串的哈希值，如果两个区间可以合并则新区间哈希值更新为子区间哈希值即可。

[/wiki/2021-team6 返回]