三分

给定平面内 $n <= 2000$ 个节点，求平面内一点使得到所有点的欧几里得距离和最小

确定 $y$ 轴时 $x$ 轴满足单峰函数

$x$ 轴同理

三分套三分即可

深度优先搜索

从起始状态少的一侧开始搜索更优

例题

给你一副扑克中的 $n$ 张牌，出的下一张牌需要为前面出牌点数之和的约数，求一种合法的方案

此题正向搜索代码如下：

void dfs(int depth, int sum){

    if(depth == n){

        output();

        return ;

        }

    REP(i, 1, n){

    if(!vis[i] && sum % a[i] == 0){

        vis[i] = 1;

        dfs(depth + 1, sum + a[i]);

        vis[i] = 0;

        }

    }

}

显然初始分支很多，考虑逆向搜索

void dfs(int depth, int left){

    if(depth == 0){output();return ;}

    REP(i, 1, n){

    if(!vis[i] && (left - a[i]) % a[i] == 0){

        vis[i] = 1;

        dfs(depth - 1, left - a[i]);

        vis[i] = 0;

        }

    }

}

//调用

dfs(n, sum[a[i]]);

初始分支减少，搜索量减少

meet-in-the-middle

在指数级别复杂度显然无法承受时，分别从两侧开始搜索，在中间相遇，减少搜索量

一般分别做 $dfs$ 后，在左边利用二分查找（或各种数据结构）寻找对应右边的值，得到解的个数（用 $STL\ map$ 也是很好的选择）

当发现有 $\%$ 的时候大大降低搜索次数

通常降低次数的方式是

减少调用量（整除才进入）
枚举因子

数学部分

exgcd

\[gcd(a,b) = !b ? a : gcd(b, a \% b)
\]

当 $$b == 0$$ 时，有 $$gcd(a, 0) = a$$

令 $$ax_{0} + by_{0} = gcd(a, b)$$

此时 $$a * 1 + 0 * 0 = gcd(a, 0) = a$$ 显然有

\[x_{0} = 1, y_{0} = 0
\]

现已递归求得 $$bx_{0} + (a % b)y_{0} = d$$

而$$(a%b) = a - \lfloor \frac{a}{b} \rfloor * b$$

构造成 $$ax + by = d$$ 形式得

\[ay_{0} + b(x_{0} - \lfloor \frac{a}{b} \rfloor * y_{0}) = d
\]

故 $$x = y_{0}, y = x_{0} - \lfloor \frac{a}{b} \rfloor * y_{0}$$

Code

int exgcd(int a, int b, int &x, int &y){

    if(!b){x = 1, y = 0;return a;}

    int d = exgcd(b, a % b, x, y);

    int temp = x;x = y;y = temp - (a / b) * y;

    return d;

    }

有关于线段树和树剖

线段树标记下推记得考虑对子节点标记的影响

若是多组询问，初始化时记得考虑如下几个方面

    nume = 1;//原图边编号

    memset(head, 0, sizeof(head));//初始化原图

    tot = 0;//树剖节点

    lazytag = -1;//线段树懒标记

秒客网

Tony的口胡呼呼(。-ω-)zzz

三分