并查集+欧拉路
一道AC自动机的模板题,但是第一次敲真是苦逼。。
T T 过了测试数据和自己造的数据后始终WA。。和人家的动归数组完全一样。。不知道哪里没有想到。。mark一下,过两天再看下。。
其实有时候动归用集合会让思路更简洁,但是时间会多一些。。
这道题结合了结构体,还巧妙的利用结构体内部的对象记录了DP的前一状态的对象,感觉这种方法可以用在其他DP里,比如重建最长公共子序列。。
向量的运算,点到直线的距离,多边形面积,线线相交,已知不共线三点XYZ求其圆心和半径,求已知点X关于已知直线Ax+By=C的对称点,关于某点的旋转