【ZJOI2008】无序运动


如果不考虑翻转操作。

我们可以每\(3\)个相邻的点作为一个特征点来保存。

三个相邻点的特征值记为第一条向量和第二条向量模之比、以及角度。

为了避免浮点数误差,向量的模可以平方处理,角度分别记录点积和叉积(点积和叉积要注意除以模长,也用分数记录)。

这样把所有的模式串特征值作为一个字符位插入AC自动机。

由于是一个无法确定内容的AC自动机,所以用map来处理。

对于翻转问题,只需要把模式串翻转再插入就行(翻转以后和原串相同的,不重复插入)

map 写AC自动机,改的不彻底,带着队友一起自闭。

 

You may also like

【TJOI2015】弦论

【AHOI2013】差异

LEAVE A COMMENT

Statistics

  • 1
  • 8,100

Categories

Archive

Comments