2456 Aggressive cows
和前几天做的WiFi差不多,二分+检验
不同的是求的是最大间隔,是个减函数,m可以,则m-1也可以,细节稍有不同
1145 Tree Summing
重写了此题,不建树,直接递归,0ms了
cin.putback真好用
google到一个ozy写的代码...超短..有兴趣可以研究下
2002 Squares
3432 Count Squares
做一题送一题
和昨天的a+b+c+d=0差不多,也是枚举一半再查找另外一半
枚举2个点i,j,得到他们的中点m,设i->j的向量为v,则交换v的x,y坐标,再把x坐标取相反数就得到了和他垂直的向量
接着很容易得到了以点i,j为对角线的正方形的另外一条对角线的点的坐标,再在set/hash中找一下就好了
总复杂度O(n^2 logn)
看了Discuss,处理上有个技巧就是把读进来的坐标*2,这样算中点的时候就不会出现小数从而保证了查找的精度!
set对于自定义类型也要做一个operator< 内部是RB-Tree
后天就省赛了,明天重写下2777和1389,复习线段树~