搜索专题

例题 1

给你$ n $张扑克牌，保证这$ n $张来自于同一副。你可以打若干次牌，第一次可以打任意数字，之后每次打的数字，必须是之前打过的数字之和的约数。问是否存在一种打牌方案，使得可以打出所有牌，输出方案。
$1 ≤ n ≤ 52$。

本题可以很简单得写出一个爆搜程序，但是如果正搜的话解答树会很大，因为前面的决策多后面的决策少，所以我们可以调换搜索顺序，这样使得前面的决策少后面的决策多。

本题心得：对于这种题目开始决策比较多的，可以考虑倒搜，使得初始决策变少。(就算没有明显的变化也可以尝试倒搜)

例题 2

给出一个由a, b, c组成的长度为$n$ 的字符串。定义一个子序列 $T$ 的价值为 $\frac {len^2_T}{c_T}$，其中$ lenT$ 表示$ T$ 的长度，$ c_T $表示$ T $的最小循环节长度。找出价值最大的子序列。
$1 ≤ n ≤ 10^4。$

尝试使用上下界剪枝 (可行性剪枝)。对于本题要关注”由a, b, c组成”的特殊条件。我们想一个理论最小价值。我们找到一个出现最多的字符，他的出现次数一定大于等于$\frac n3$。所以选择这个字符的价值为$(\frac n3)^2$，所以价值无论如何都能取到$\frac {n^2}9$
因为$n$比任何子序列长都大，所以循环节长度最大不能超过$9$，即找到一个下界。所以枚举最大不超过$9$的循环节来更新答案即可。

代码：Bzoj 5439

本题心得：对于这种没什么思路的题目可能有结论(比如只有某些情况有解/能剪大量枝(有上下界))来辅助。对于题目的特殊限制要加以思考。

例题 3

给出平面上$ n$ 个点$ (xi, yi)$，要求找到一个点$ (x, y)$，使得这个点到给出的那些点的欧几里得距离之和最短。
$1 ≤ n ≤ 1000。$
$−10^6 ≤ xi, yi ≤ 10^6。$

这题与搜索没什么关系。
考虑定下这个点的$x$，来找$y$的位置，发现答案与$y$的位置有单峰函数的关系，使用三分找到这个唯一的极值点即为答案。同理$x$的位置也与答案有单峰函数的关系。三分套三分即可。

本题心得：数学题几何题最优化问题二分无法解决可能是三分问题，并且可以用感性的思想来判断一个对应关系是不是单峰函数。

例题 4

定义$ ′ $运算如下：
如果 $p = 1， p′ = 0。$
如果 $p$ 是质数，$ p′ = 1$
否则 $p′ = (a \times b)′ = a′ \times b + a \times b′$
给出 $k, r$，求出所有满足 $x′ = kx, 1 ≤ x ≤ r $的$ x。$
$1 ≤ k ≤ 30， 1 ≤ r ≤ 2 × 10^{18}。$

关注”$p$ 是质数，$ p′ = 1$“，“$p′ = (a \times b)′ = a′ \times b + a \times b′$”，提示我们要分解质因数。
分解质因数得$p=\prod^t_{i=1} p_i^{q_i}$，则可以得到$p′ =\sum_{i=1}^t\frac{q_ip}{p_i}$
这一步可以找规律，设$p=\prod_{i=1}^k$发现$p′ =\sum_{i=1}^k \frac{\prod_{j=1}^k p_j}{p_i}$，易得上一个式子。乘$q_i$是因为每个相等质因子都要加一次。
然后就可以使$p′ =\sum_{i=1}^t\frac{q_ip}{p_i}=kp$，约掉$p$，变为
$\sum_{i=1}^t\frac{q_i}{p_i}=k$
然后我们考虑因为$p_i$都是质数，所以两个$\frac{q_i}{p_i}, \frac{q_j}{p_j}$最简形式是分数的不能合并成整数，所以$q_i$一定是$p_i$整数倍。
那么直接预处理质数$p_i$，然后用$p_i^{p_i}$来 DFS 拼 $p$ 即可。

本题心得：本题对于题目的特殊限制/特性加以思考。找规律也是很好的发现式子的方式，如果不能肉眼找，就打表找。

例题 5

给出$ n $杯糖水，第$ i $杯糖水的总质量为$ m_i$，其中糖的质量为$ t_i$。现在给出一个分数$ \frac ba$，问选出若干杯糖水，使得这些杯混合之后，糖的质量占总质量之比为$\frac ba$的方案数。
$2 ≤ n ≤ 35。$
$1 ≤ t_i ≤ m_i ≤ 10000。$
$1 ≤ a ≤ b ≤ 10000。$

本题可以枚举子集，但是时间复杂度$O(2^n)$，太大了。
考虑将子集分开两边枚举。设$m=\frac n2$, 然后再前$m$和后$m$的区间范围内枚举子集，考虑怎么才能快速合并两段答案。原题求$\frac {\sum t_i}{\sum m_i}=\frac ab$ 对于这种分数等式我们转化为乘积式，$a\sum m_i=b \sum t_i$
那么我们枚举的两个子集满足题意就是$a(\sum_{i \in S_1} m_i +\sum_{i \in S_2} m_i)=b(\sum_{i \in S_1} t_i +\sum_{i \in S_2} t_i)$
移项，则$a\sum_{i \in S_1} m_i-b\sum_{i \in S_1} t_i = -(a\sum_{i \in S_2} m_i-b\sum_{i \in S_2} t_i))$
所以我们就可以用 map 维护形如$a\sum_{i \in S_1} m_i-b\sum_{i \in S_1} t_i$的东西，前一半的存进 map，后一半在 map 中查询。然后统计即可。
这种方式叫折半搜索。

本题心得：对于这种题目直接搜索慢的，看能不能切成几块然后快速合并。并且这题将分式化为乘积式方便了计算。将关于$i$的式子放一边然后用数据结构维护这一坨的思想很重要。

标程：

#include <map>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <iostream>

const int MAXN = 40;

using namespace std;

int n, a, b, x[MAXN], y[MAXN];

long long work() {
  map<int, int> M;
  int p = n / 2, q = n - p;
  long long ans = 0;
  for(int i = 0; i < (1 << p); i++) {
    int curA = 0, curB = 0;
    for(int j = 1; j <= p; j++) {
      if(i >> (j - 1) & 1) {
        curA += x[j], curB += y[j];
      }
    }
    M[a * curB - b * curA]++;
  }
  for(int i = 0; i < (1 << q); i++) {
    int curA = 0, curB = 0;
    for(int j = p + 1; j <= n; j++) {
      if(i >> (j - p - 1) & 1) {
        curA += x[j], curB += y[j];
      }
    }
    int need = a * curB - b * curA;
    ans += M[-need];
  }
  return ans - 1;
}

int main() {
  scanf("%d %d %d", &n, &a, &b); // a / b
  for(int i = 1; i <= n; i++) {
    scanf("%d %d", &x[i], &y[i]); // x[i] / y[i]
  }
  long long ans = LLONG_MAX;
  ans = min(ans, work());
  printf("%lld\n", ans);
  return 0;
}

我的程序

例题 6

Bzoj 5445

Johnny 有若干个玩具，玩具的种类可能相同也可能不同。现在已知他的这些玩具有$ n $个本质不同的子集（包括空集），问玩具的个数可能是多少。输出所有的可能解。
$1 ≤ n ≤ 10^9$。

看样例解释可以找到规律，几个数乘起来等于$n$的几个数减一的和为一个答案。DFS 分解因数(用$n$除$n$约数方便快捷)。
数学方法证明：$n=\prod_{i=1}^t (a_i+1)$，所以DFS 分解因数(用$n$除$n$约数方便快捷)。

本题心得：要善于从题中找规律，并且 DFS 时也要考虑复杂度如何优化，正向思想和反向思想。

代码：

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

using namespace std;

namespace flyinthesky {  

    int n;
    vector<int > ans;

    void dfs(int tmp, int tot, int lst) {
        ans.push_back(tot + tmp - 1);//当前约数加上tmp因子
        int gg = (int)sqrt(tmp) + 1;
        for (int i = lst; i <= gg; i++) if (tmp % i == 0) dfs(tmp / i, tot + i - 1, i);
    }

    void clean() {
    }
    int solve() {
        scanf("%d", &n);
        clean();
        dfs(n, 0, 2);//n/i方向搜索快
        int whw; 
        sort(ans.begin(), ans.end()), whw = unique(ans.begin(), ans.end()) - ans.begin();
        printf("%d\n", whw);
        for (int i = 0; i < whw; i++) printf("%d ", ans[i]);
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

例题 8

Bzoj 5049

给出一个$ n$个点$ m $条边的随机生成的无权无向图，有$ q $次询问，每次给出 $x, y(1 ≤ x, y ≤ n, x ≠ y)$，询问$ x $到$ y$的最短路。
$n = 10^5, m = 3 × 10^5, q = 10^4。$

由于题目中随机生成，期望最短路小，所以直接从两点开始双向 BFS 即可。

本题心得：要敢于猜想敢于暴力，就算不知道结论也可以双向优化

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<stack>
#include<set>
#include<queue>
#include<climits>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double

using namespace std;

namespace flyinthesky {  

    const int MAXN = 100000 + 5, MAXM = 300000 + 5;

    struct edge {int v, nxt;} ed[MAXM * 2];
    struct data {int u, dis, isZ;};

    int n, m, Q, hd[MAXN], en, vis[MAXN], dis[MAXN], f[MAXN];

    void ins(int x, int y) {ed[++en] = (edge){y, hd[x]}, hd[x] = en;}
    int find(int x) {return (x == f[x]) ? x : (f[x] = find(f[x]));}

    int bfs(int ith, int s, int t) {
        queue<data > q;
        dis[s] = dis[t] = 0, vis[s] = ith, vis[t] = -ith;
        q.push((data){s, 0, ith}), q.push((data){t, 0, -ith});
        while (!q.empty()) {
            data p = q.front(); q.pop();
            for (int i = hd[p.u]; i > 0; i = ed[i].nxt) {
                edge &e = ed[i];
                if (vis[p.u] == -vis[e.v]) return dis[p.u] + dis[e.v] + 1;
                if (vis[e.v] != p.isZ) vis[e.v] = p.isZ, dis[e.v] = dis[p.u] + 1, q.push((data){e.v, dis[e.v], p.isZ});
            }
        }
        return -1;
    }

    void clean() {
        en = 0, ms(hd, -1), ms(vis, 0);
    }
    int solve() {
        scanf("%d%d%d", &n, &m, &Q);
        clean();
        for (int i = 1; i <= n; i++) f[i] = i;
        for (int u, v, i = 1; i <= m; i++) {
            scanf("%d%d", &u, &v), ins(u, v), ins(v, u);
            int x = find(u), y = find(v);
            if (x != y) f[x] = y;
        }
        for (int s, t, i = 1; i <= Q; i++) {
            scanf("%d%d", &s, &t);
            if (find(s) != find(t)) printf("-1\n"); else printf("%d\n", bfs(i, s, t));
        }
        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

例题 9

给出一个$ n $个点$ m $条边的无向图连通简单图。每条边的长度为$ 1$；第$ i $个点种有$ v_i $个金币。小偷住在$ 1$ 号点，王宫在$ 2 $号点，小偷需要沿着到王宫的最短路去进贡。在去进贡的途中，对于经过的每个点，他都可以选择偷或不偷。如果偷，他将获得这个点的金币，但是回程时将不能访问这个点。小偷想知道在他能回家的前提下，最多可以进贡多少金币。
$2 ≤ n ≤ 36, 1 ≤ m ≤ \frac{n(n^2−1)}{2}$

结论：对于一个简单无向图来说，两点间的最短路的条数约为$O(e^{\frac ne} ) $级别。
我们可以将选择问题转化为删除问题。即本题先搜到一条最短路，然后将所有节点选择，然后再想如何删除使得回程路径能连通。所有我们正向做最短路，然后反向以点权拆成两点一边来做最短路。

本题心得：选择问题转化为删除问题思想很重要，是这题解题的一个关键。以及简单无向图两点间的最短路的条数小。如果要用到点权作为最短路之类的算法，可以将点拆成两点一边，这样通过这条边相当于通过这个点，并且花费这个点的代价。

DP 专题

部分分专题

图论专题

第一场模拟赛

T1

水题，将一个数固定以后其他数可选可不选，所以这个数对答案的贡献为$2^{n-1} \cdot a_i$
或者根据样例解释找规律。

T2

求 $\sum_{i=1}^{n} n \mod i$，多组询问，$n \leq 10^7$

用$a\% b = a-\lfloor \frac ab \rfloor\cdot b$，得出原式等于$\sum_{i=1}^{n} n-\lfloor \frac ni \rfloor\cdot i$
即$n^2-\sum_{i=1}^{n} \lfloor \frac ni \rfloor\cdot i$，打表观察或者因为$ \lfloor \frac ni \rfloor$表示的是$n$最多由几个$i$相加而成，$\sum_{i=1}^{n} \lfloor \frac ni \rfloor=\sum_{i=1}^{n}d_0(i)$,$\sum_{i=1}^{n} \lfloor \frac ni \rfloor\cdot i=\sum_{i=1}^{n}d_1(i)$，线性筛$d_1(i)$前缀和即可。

本题心得：数论要会打表。$a\% b = a-\lfloor \frac ab \rfloor\cdot b$。线性筛的新知识

T3

毒瘤题。线段树扫描线+倍增处理

本题心得：倍增处理一些较长的距离但是单一能维护信息的操作。扫描线可以扫描平面内的一些东西来储存信息。

第二场模拟赛

T1

按题意可以将豆子按$x+y$排序(或者$x$为第一关键字，$y$第二关键字)，然后对于两两点之间求路径条数然后相乘。关键在于这个条数怎么求。可以用 DP 递推，也可以使用组合数，我们从$dx+dy$步中选$dx$步出来往下走(反着来也行)，答案为$C^{dx}_{dx+dy}$，然后组合数求解用预处理阶乘和阶乘逆元即可。

知识点：
1、数组大小想清楚开
2、注意题目中无解输出什么

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<climits>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky {

    const int MAXN = 100000 + 5, MO = 1000000000 + 7;

    int n, m, k;
    LL jc_inv[MAXN * 2], jc[MAXN * 2];
    pair<int, int > pnt[MAXN];

    LL ksm(LL a, LL b) {
        LL bs = a, ans = 1ll;
        while (b) {
            if (b & 1) ans = (ans * bs) % MO;
            bs = (bs * bs) % MO;
            b >>= 1;
        }
        return ans;
    }
    LL c(LL m, LL n) {
        if (m > n) return 0;
        LL tmp = jc[n];
        tmp = (tmp * jc_inv[m]) % MO;
        tmp = (tmp * jc_inv[n - m]) % MO;
        //cout << "m=" << m << ", n=" << n << ", tmp=" << tmp << "\n";
        return tmp;
    }

    void clean() {}
    int solve() {
        cin >> n >> m >> k;
        clean();

        jc_inv[0] = jc[0] = 1;
        jc_inv[1] = jc[1] = 1;
        for (int i = 2; i <= 200000; i++) {
            jc[i] = (jc[i - 1] * (LL)i) % MO;
            jc_inv[i] = (jc_inv[i - 1] * ksm((LL)i, MO - 2)) % MO;
        }

        //for (int i = 1; i <= 100; i++) cout << jc_inv[i] << " ";

        for (int i = 1; i <= k; i++) scanf("%d%d", &pnt[i].fir, &pnt[i].sec);

        pnt[k + 1] = mp(1, 1), pnt[k + 2] = mp(n, m), k += 2;

        sort(pnt + 1, pnt + 1 + k);

        LL ans = 1ll;

        for (int i = 2; i <= k; i++) {
            int dlx = pnt[i].fir - pnt[i - 1].fir;
            int dly = pnt[i].sec - pnt[i - 1].sec;
            if (dlx < 0 || dly < 0) return printf("0\n"), 0;
            //printf("dlx=%d, dly=%d\n", dlx, dly);
            ans = (ans * c(dlx, dlx + dly)) % MO;
        }

        cout << ans;

        return 0; 
    }
}
int main() {
    flyinthesky::solve();
    return 0;
}

jzoj 5397(Trie+LCA+离线)

jzoj 5396(单调栈)

jzoj 5394(LCA)

jzoj 5392(规律)

Luogu NOIP 2018 训练