[SinGuLaRiTy] 复习模板-搜索

【SinGuLaRiTy-1043】 Copyright (c) SinGuLaRiTy 2017. All Rights Reserved.

桶排序

void bucketSort(int a[], int n, int max)//a[]为待排序数组,n为数组长度,max为数组中的最大值范围
{
    int i,j;
    int buckets[max];
    // 将buckets中的所有数据都初始化为0。
    memset(buckets, 0, max*sizeof(int));
    // 1. 计数
    for(i = 0; i < n; i++) 
        buckets[a[i]]++; 
    // 2. 排序
    for (i = 0, j = 0; i < max; i++) 
    {
        while( (buckets[i]--) >0 )
            a[j++] = i;
    }
}

优先队列

#include<stdio.h>  
#include<functional>  
#include<queue>  
#include<vector>  
using namespace std;  
//定义结构，使用运算符重载,自定义优先级1  
struct cmp1{  
    bool operator ()(int &a,int &b){  
        return a>b;//最小值优先  
    }  
};  
struct cmp2{  
    bool operator ()(int &a,int &b){  
        return a<b;//最大值优先  
    }  
};  
//定义结构，使用运算符重载,自定义优先级2  
struct number1{  
    int x;  
    bool operator < (const number1 &a) const {  
        return x>a.x;//最小值优先  
    }  
};  
struct number2{  
    int x;  
    bool operator < (const number2 &a) const {  
        return x<a.x;//最大值优先  
    }  
};  
int a[]={14,10,56,7,83,22,36,91,3,47,72,0};  
number1 num1[]={14,10,56,7,83,22,36,91,3,47,72,0};  
number2 num2[]={14,10,56,7,83,22,36,91,3,47,72,0};  
  
int main()  
{   priority_queue<int>que;//采用默认优先级构造队列  
  
    priority_queue<int,vector<int>,cmp1>que1;//最小值优先  
    priority_queue<int,vector<int>,cmp2>que2;//最大值优先  
  
    priority_queue<int,vector<int>,greater<int> >que3;//注意“>>”会被认为错误，  
                                                      //这是右移运算符，所以这里用空格号隔开  
    priority_queue<int,vector<int>,less<int> >que4;////最大值优先  
  
    priority_queue<number1>que5;  
    priority_queue<number2>que6;  
  
    int i;  
    for(i=0;a[i];i++){  
        que.push(a[i]);  
        que1.push(a[i]);  
        que2.push(a[i]);  
        que3.push(a[i]);  
        que4.push(a[i]);  
    }  
    for(i=0;num1[i].x;i++)  
        que5.push(num1[i]);  
    for(i=0;num2[i].x;i++)  
        que6.push(num2[i]);  
  
  
    printf("采用默认优先关系:
(priority_queue<int>que;)
");  
    printf("Queue 0:
");  
    while(!que.empty()){  
        printf("%3d",que.top());  
        que.pop();  
    }  
    puts("");  
    puts("");  
  
    printf("采用结构体自定义优先级方式一:
(priority_queue<int,vector<int>,cmp>que;)
");  
    printf("Queue 1:
");  
    while(!que1.empty()){  
        printf("%3d",que1.top());  
        que1.pop();  
    }  
    puts("");  
    printf("Queue 2:
");  
    while(!que2.empty()){  
        printf("%3d",que2.top());  
        que2.pop();  
    }  
    puts("");  
    puts("");  
    printf("采用头文件"functional"内定义优先级:
(priority_queue<int,vector<int>,greater<int>/less<int> >que;)
");  
    printf("Queue 3:
");  
    while(!que3.empty()){  
        printf("%3d",que3.top());  
        que3.pop();  
    }  
    puts("");  
    printf("Queue 4:
");  
    while(!que4.empty()){  
        printf("%3d",que4.top());  
        que4.pop();  
    }  
    puts("");  
    puts("");  
    printf("采用结构体自定义优先级方式二:
(priority_queue<number>que)
");  
    printf("Queue 5:
");  
    while(!que5.empty()){  
        printf("%3d",que5.top());  
        que5.pop();  
    }  
    puts("");  
    printf("Queue 6:
");  
    while(!que6.empty()){  
        printf("%3d",que6.top());  
        que6.pop();  
    }  
    puts("");  
    return 0;  
}  

Set

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    s.insert(1);
    s.insert(2);
    s.insert(3);
    s.insert(1);
    cout<<"set 的 size 值为 ："<<s.size()<<endl;
    cout<<"set 的 maxsize的值为 ："<<s.max_size()<<endl;
    cout<<"set 中的第一个元素是 ："<<*s.begin()<<endl;
    cout<<"set 中的最后一个元素是:"<<*s.end()<<endl;
    s.clear();
    if(s.empty())
    {
        cout<<"set 为空 ！！！"<<endl;
    }
    cout<<"set 的 size 值为 ："<<s.size()<<endl;
    cout<<"set 的 maxsize的值为 ："<<s.max_size()<<endl;
    return 0;
}

Map

#include <iostream>
#include <map>

using namespace std;

int main()
{
    // map是一种关联容器类，里面存储的元素类型为pair<const KEY, DATA>。不同的元素KEY值不同。    
    // 定义map及其对应的迭代器
    map<char, int> mapTest;
    map<char, int>::iterator iterTest;
    
    // 在map中插入元素
    // 这种利用下标值的插入方式，当map中没有对应键值的元素时，插入。当map中存在对应键值的元素时，修改其值或者获取其值。
    mapTest['a'] = 10;
    mapTest['b'] = 20;
    mapTest['c'] = 30;
    mapTest['a'] = 15;

    // 这种使用insert的插入方式，当map中没有对应键值的元素时，插入。当map中存在对应键值的元素时，不插入元素。
    pair<map<char, int>::iterator, bool> ret;
    mapTest.insert(map<char, int>::value_type('d', 40));
    ret = mapTest.insert(make_pair('d', 50));
    mapTest.insert(make_pair('e', 50));

    // 当使用insert函数后会返回pair<map<char, int>::iterator, bool>类型的值，bool值表示是否插入成功。迭代器指向插入的元素。
    cout << ret.second << endl;
    

    // map中查找某个指定键值的元素,查找成功则返回对应的迭代器。查找失败则返回.end()对应的容器边界迭代器。
    iterTest = mapTest.find('f');
    cout << (iterTest == mapTest.end()) << " find: 0 means success, 1 means failure"<< endl;

    // 正向遍历
    cout << "正向" << endl;
    for (iterTest = mapTest.begin(); iterTest != mapTest.end(); iterTest++)
    {
        cout << iterTest->first << " " << iterTest->second << endl;
    }
    
    // 反向遍历
    cout << "反向" << endl;
    map<char, int>::reverse_iterator iter;
    for (iter = mapTest.rbegin(); iter != mapTest.rend(); iter++)
    {
        cout << iter->first << " " << iter->second << endl;
    }

    // 使用size获取容器中元素个数
    int num;
    num = (int)mapTest.size();
    cout << num << endl;

    // 使用clear清空容器
    mapTest.clear();

    // 使用empty判断容器是否为空
    if (mapTest.empty())
    {
        cout << "The map is empty" << endl;
    }
    
    return 0;
}

Hash

#include <iostream>
#include <cstring>

using namespace std;

const int maxn=11111;
const int maxh=10000019;
int head[maxh];
int next[maxh];
long long st[maxn];

void hash_init()
{
    memset(head,0,sizeof(head));
}

int hash(long long p,int prime=10000019)
{
    int h;
    //hash操作
    h=p%prime;
    return h;
}

bool add_hash(int s)
{
    int h=hash(st[s]);
    int u=head[h];
    while(u)
    {
        //if (memcmp(st[u],st[s],sizeof(st[s]))==0) return 0;
        //if (strcmp(st[u],st[s])==0) return 0;
        if (st[u]==st[s]) return 0;
        u=next[u];
    }
    next[s]=head[h];
    head[h]=s;
    return 1;
}

bool search_hash(long long p)
{
    int h=hash(p);
    int u=head[h];
    while (u)
    {
        //if (memcmp(st[u],p,sizeof(st[u]))==0) return 1;
        //if (strcmp(st[u],str)==0) return 1;
        if (st[u]==p) return 1;
        u=next[u];
    }
    return 0;
}

IDA* (以 埃及分数 为例)

#include <cstdio>
#include <cstring>
#include <iostream>
#define MAXN 10000
typedef long long LL;
using namespace std;

int maxd;
LL ans[MAXN];
LL v[MAXN];
LL gcd(LL a,LL b){
    return b==0?a:gcd(b,a%b);
}
int get_first(int a,int b){
    if(b%a==0) return b/a;
    else return (b/a+1);
}
bool better(int d){
    return ans[d]==-1||v[d]<ans[d];
}
bool dfs(int d,int from,LL aa,LL bb){
    if(d==maxd){
        if(bb%aa) return false;
        v[d]=bb/aa;
        if(better(d)) memcpy(ans,v,sizeof(LL)*(d+1));
        return true;
    }
    bool ok=false;
    from=max(from,get_first(aa,bb));
    for(int i=from;;i++){
        if(bb*(maxd+1-d)<=i*aa) break;
        v[d]=i;
        LL b2=bb*i;
        LL a2=aa*i-bb;
        LL g=gcd(a2,b2);
        if(dfs(d+1,i+1,a2/g,b2/g)) ok=true;
    }
    return ok;
}
int main(){
    int a,b;
    while(scanf("%d%d",&a,&b)==2){
        for(maxd=1;;maxd++){///ID
            memset(ans,-1,sizeof(ans));
            if(dfs(1,get_first(a,b),a,b)) break;
        }
        for(int i=1;ans[i]!=-1;i++)
            printf("%lld ",ans[i]);
        printf("
");
    }
    return 0;
}

双向BFS (以 HDU-1195 为例)

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cmath>
#include <string>
#include <string.h>
#include <algorithm>
using namespace std;
#define LL __int64
#define eps 1e-8
#define INF 1e8
#define lson l , m , rt << 1
#define rson m + 1 , r , rt << 1 | 1
const int MOD = 2333333; 
const int maxn = 10000 + 5;
vector <int> e[maxn];
int vis[maxn] , dist[maxn];

void solve(int x)
{
    int num[4] , i , tmp , y;
    i = 0;
    tmp = x;
    while(tmp) {
        num[i++] = tmp % 10;
        tmp /= 10;
    }
    for(i = 0 ; i < 4 ; i++)
        if(num[i] == 0)
            return;
    for(i = 0 ; i < 4 ; i++) {
        if(i < 3) {
            swap(num[i] , num[i + 1]);
            y = num[3] * 1000 + num[2] * 100 + num[1] * 10 + num[0];
            e[x].push_back(y);
            e[y].push_back(x);
            swap(num[i] , num[i + 1]);
        }
        tmp = num[i];
        if(num[i] == 9)
            num[i] = 1;
        else
            num[i]++;
        y = num[3] * 1000 + num[2] * 100 + num[1] * 10 + num[0];
        e[x].push_back(y);
        e[y].push_back(x);
        num[i] = tmp;

        if(num[i] == 1) 
            num[i] = 9;
        else
            num[i]--;
        y = num[3] * 1000 + num[2] * 100 + num[1] * 10 + num[0];
        e[x].push_back(y);
        e[y].push_back(x);
        num[i] = tmp;
    }
}
int BFS_2(int start , int end)
{
    if(start == end)
        return 0;
    memset(vis , 0 , sizeof(vis));
    queue <int> que[2];
    vis[start] = 1;
    vis[end] = 2;
    que[0].push(start);
    que[1].push(end);
    dist[start] = dist[end] = 0;
    while(!que[0].empty() && !que[1].empty()) {
        int k = 0;
        if(que[0].size() < que[1].size())
            k++;
        int u = que[k].front();
        que[k].pop();
        for(int i = 0 ; i < e[u].size() ; i++) {
            int j = e[u][i];
            if(!vis[j]) {
                vis[j] = vis[u];
                que[k].push(j);
                dist[j] = dist[u] + 1;
            } else if(vis[j] == vis[u]) {
                continue;
            } else {
                return dist[j] + dist[u] + 1;
            }
        }
    }
    return -1;
}
int main()
{
    int T , a , b;
    for(int i = 1111 ; i <= 9999 ; i++)
        solve(i);
    cin >> T;
    while(T--) {
        scanf("%d %d" , &a , &b);
        printf("%d
" , BFS_2(a , b));
    }
    return 0;
}

Time: 2017-10-28