一些“基础”算法

枚举子集的子集

给定n个元素，问这n个元素组成的每一个集合的所有子集。

for(int S = 1; S < (1 << n); ++S) {
    for(int S1 = S; S1 != 0; S1 = (S1 - 1) & S) {
        //do something
    }
} 

最外层就是\(O(2^n)\)枚举所有集合。如果要按普通方法枚举子集，应该将\(S1\)从\(S\)开始每次减一，再判断合法性。然而由于&\(S\)的结果只减不增，\(S1\)可以通过\(-1\)然后&\(S\)来直接到达最近合法状态。

复杂度不会证，但是知道是\(O(3^n)\)

更详细的讲解

搜索

由于万恶的老师没有讲基本的搜索，于是我这里也跳过啦 XD

迭代加深搜索

如果搜索树的深度不确定，那么可以使用迭代加深搜索（\(iterative\ deepening\)）

1. 枚举\(maxd\)表示最深枚举深度
2. 假设当前深度为\(g(n)\)，乐观估计至少要\(h(n)\)层才能到达叶结点，那么\(g(n)+h(n)>maxd\)时，应该剪枝，这就是\(IDA*\)(基于迭代加深的\(A*\)算法。)

埃及分数问题

传送门

给出一个分数，要求求出最少的x分之1的形式，如果个数相同，要求最小的数字最大。

考虑搜索，因为层数不定，所以使用迭代加深搜索

细节问题需要注意

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#define ll long long
using namespace std;

ll a, b, ans[15], tmp[15], now, INF = 2147483647;

ll gcd(ll x, ll y) {
    if(y == 0) return x;
    return gcd(y, x % y);
}

int flag;

void dfs(ll dep, ll na, ll nb) {
    if(dep > now) return;
    if(na == 1 && nb > tmp[dep - 1]) {
        tmp[dep] = nb;
        if(!flag || tmp[dep] < ans[dep]) {
            memcpy(ans, tmp, sizeof(tmp));
        }
        flag = 1;
        return;
    }
    ll st = max(nb / na, tmp[dep - 1] + 1), ed = (now - dep + 1) * nb / na;
    if(ed > INF) ed = INF - 1;
    if(flag && ed >= ans[now]) ed = ans[now] - 1;
    for(ll i = st; i <= ed; i++) {
        tmp[dep] = i;
        ll ty = gcd(na * i - nb, nb * i);
        dfs(dep + 1, (na * i - nb) / ty, nb * i / ty);
    }
}

int main() {
    scanf("%lld%lld", &a, &b);
    ll c = gcd(a, b);
    a /= c, b /= c;
    if(a == 1) {
        cout << b << '\n';
        return 0;
    }
    tmp[0] = 1;
    for(now = 1; ;now++) {
        dfs(1, a, b);
        if(flag) {
            for(int i = 1; i <= now; i++) {
                cout << ans[i] << " ";
            }
            return 0;
        }
    }
    return 0;
}

A*

我们如果把“当前状态乐观估计还要\(h(n)\)层才能到达终点”这个\(idea\)用到\(bfs\)上，会不会有好效果？这就是\(A*\)

例如在\(dijkstra\)算法中，我们每次取的是\(d(v)\)最小的点。如果我们加上\(A*\)的思想，就可以每次取\(d(v)+h(v)\)最小的点。(例如说这里的\(h(v)\)可以是连接\(v\)的最小的边)
我们可以把常规\(bfs\)用的队列改成优先队列，每次选\(g(n)+h(n)\)最小的点来更新。

万圣节后的早晨

传送门

一个地图，有障碍不能走，要求所有小写字母到达自己对应的大写字母

这题可以用\(bfs\)来写，也可以加入\(A*\)，每个状态的\(H(n)\)可以估计为每个小写字母到大写字母的最短路之和。

代码先鸽着

练习题

hdu2234

双向搜索

双向搜索又名折半搜索。当搜索的复杂度在指数级的时候，我们可以通过将指数折半的方法降低搜索复杂度。

具体做法是从初态和终态出发各搜索一半状态，产生两颗深度减半的搜索树，两颗树交汇在一起形成最终答案，将\(O(n^k)\)降低到\(O(n^{k/2}+n^{k/2+1})\)的复杂度。

和为0的四个值

传送门

给定的各有n个整数的数列\(A\)，\(B\)，\(C\)，\(D\)，从每个数列中取一个数使得四个数加起来等于\(0\)，问这样的方案数。

\(n^4\)的枚举肯定会超时，所以我们先\(n^2\)处理\(A[i] + B[i]\)的值，并把它加到\(sum\)数组中，然后对\(sum\)数组进行排序，然后寻找每一组\((-C[i] - D[j])\)在\(sum\)出现了多少次，把这些次数都加起来，相加后的结果即是答案

话说根本用不到搜索的hhhh

#include<bits/stdc++.h>
#define N 4005
#define LL long long
using namespace std;

int T,n,A[N],B[N],C[N],D[N],sum[N*N];

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 0; i < n; i++) {
            scanf("%d%d%d%d", &A[i], &B[i], &C[i], &D[i]);
        }
        int c = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j< n; j++) {
                sum[c++] = A[i] + B[j];
            }
        }
        stable_sort(sum, sum + c);
        LL ans=0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                ans += upper_bound(sum, sum + c,-C[i]-D[j]) - lower_bound(sum, sum + c, -C[i]-D[j]);
            }
        }
        printf("%lld\n", ans);
        if(T) printf("\n");
    }
    return 0;
}