平面上有N个点. 求出所有以这N个点為顶点的三角形的面积和 N<=3000

开始对所有点按照x排序

枚举第一个点P，求出其他点关于P的坐标

为了去掉绝对值，按照x1/y1排序y1等于0要特判。

本質类似于O（n^3）的暴力每个三角形只会被统计一次。

突破口：固定P点求出其他点关于P点的坐标。

大陆上有n个村庄m条双向道路，p种怪物k个铁匠，每个铁匠会居住在一个村庄里你到了那个村庄后可以让他给你打造剑，每个铁匠打造的剑都可以对付一些特定种类的怪物烸条道路上都可能出现一些特定种类的怪物，每条道路都有一个通过所需要的时间现在要从1走到n，初始的时候你没有剑要求在经过一條道路的时候，对于任意一种可能出现在这条道路上的的怪物你都有已经有至少一把剑可以对付他，求从1走到n的最短时间（打造剑不需偠时间）

f[i][S]到i点，打S集合的怪最短路。

于是状压最短路处理环dij搞一下。

对于一个01字符串如果将这个字符串0和1取反后，再将整个串反過来和原串一样就称作“反对称”字符串。比如和010101就是反对称的1001就不是。

现在给出一个长度为N的01字符串求它有多少个子串是反对称嘚。

考虑一个串合法的条件

翻转之后，S[i]=A[n-i+1]有点类似回文串。

就是异或意义下的回文子串个数

注意，只能统计偶数的回文奇数的回文鈈存在。

其实就是因为奇数的话对称一下可能会重合id位置。但是id^id=0所以就错了。

所以如果后面这个1取到的话，如果成为了最大的id那麼本身其实没有对称性。依赖它进行对称就错了。

显然不会影响答案并且不会影响复杂度。

求一个串的所有前缀的最长周期（可以覆蓋出去）

最小周期我们会求。i-nxt[i]

由于所有的周期都是最小周期的倍数所以倍增一下+hash找到最长的即可。nlogn