时间戳

首页 > 技术文章 > 「笔记」一些“基础”算法

「笔记」一些“基础”算法

loceaner 2019-08-13 18:05 原文

一些“基础”算法

枚举子集的子集

给定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;
}

推荐阅读