いくつかの基礎アルゴリズム

サブセットのサブセットを列挙

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))がすべての集合を列挙する.通常の方法でサブセットを列挙する場合は、(S 1)を(S)から1回ずつ減算し、合法性を判断する必要があります.しかし&(S)の結果は減少しないだけであるため、(S 1)は(−1)から&(S)によって直接最近の合法状態に達することができる.
複雑さは証明できませんが、(O(3^n))だと知っています.
より詳細な説明

検索

万悪の先生が基本的な検索を言わなかったので、私もここでXDをスキップしました.

反復検索

検索ツリーの深さが不明な場合は、反復を使用して検索を深めることができます((iterativedeepening))

列挙(maxd)は、最も深い列挙深さ

を表す.

現在の深さが(g(n))であり、少なくとも(h(n))層がリーフノードに到達すると楽観的に推定される場合、(g(n)+h(n)>maxd)の場合、これは(IDA*)(反復深さに基づく(A*)アルゴリズム)である.)

エジプト点数問題

トランスファゲート
最小のx分の1を求める形式を与え,個数が同じであれば最小の数字が最大であることを要求する.
検索を考慮すると、レイヤ数が不定であるため、反復を使用して検索を深める
詳細については注意が必要です

#include 
#include 
#include 
#include 
#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 << '
';
        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

双方向検索

双方向検索は半値検索とも呼ばれます.探索の複雑さが指数級にある場合,指数を半分に折る方法で探索の複雑さを低減できる.
具体的には,初期状態と最終状態からそれぞれ半分の状態を探索し,2つの深さが半減した探索木を生成し,2つの木が交差して最終的な答えを形成し,(O(n^k))を(O(n^{k/2}+n^{k/2+1}))の複雑さに低減する.

と0の4つの値

トランスファゲート
与えられた各n個の整数の数列(A),(B),(C),(D)は、各数列から4個の数を加算して(0)に等しくする数を取り、このようなシナリオ数を尋ねる.
(n^4)の列挙は必ずタイムアウトするので、(n^2)は(A[i]+B[i])の値を処理して(sum)配列に加算し、(sum)配列をソートして、各グループ((-C[i]-D[j])が(sum)に何回現れたかを探して、これらの回数を加算し、加算した結果が答えです
っていうか全然検索できないhhh

#include
#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
", ans);
        if(T) printf("
");
    }
    return 0;
}