一些“基础”算法
枚举子集的子集
给定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\)）
- 枚举\(maxd\)表示最深枚举深度
- 假设当前深度为\(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;
}
查看5道真题和解析
