技巧论 QAQ




凡事要讲究技巧,无技不成巧,先将遇到的技巧记录下来..

对的…这特么就是一个远古巨坑

中途相遇法(又称折半枚举,双向搜索)

思想论

如果纬度特别高时,比如数据量为N,总情况数为N^4,全部遍历一遍是肯定不可以的,不过可以将它们折半成AB和CD再考虑,就可以快速解决了.

从两个数列中考虑的话,就只剩下N^2种情况了,因此对两半枚举完以后排一下序,就可以用二分搜索了.

例题:山东第一届省赛 D

右侧标签云中找一下第一节山东省塞即可

爬梯法

尺取法

思想:

规定那个两个点,先固定左端点,如果小于答案,则右端点向右走,否则左端点向左走
POJ 3061

分块法

51nod 1225

倍增算法

康托展开