[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, , max*sizeof(int));
    // 1. 计数
    for(i = ; i < n; i++)
        buckets[a[i]]++;
    // 2. 排序
    for (i = , j = ; i < max; i++)
    {
        while( (buckets[i]--) > )
            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[]={,,,,,,,,,,,};
number1 num1[]={,,,,,,,,,,,};
number2 num2[]={,,,,,,,,,,,};  

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=;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=;num1[i].x;i++)
        que5.push(num1[i]);
    for(i=;num2[i].x;i++)
        que6.push(num2[i]);  

    printf("采用默认优先关系:\n(priority_queue<int>que;)\n");
    printf("Queue 0:\n");
    while(!que.empty()){
        printf("%3d",que.top());
        que.pop();
    }
    puts("");
    puts("");  

    printf("采用结构体自定义优先级方式一:\n(priority_queue<int,vector<int>,cmp>que;)\n");
    printf("Queue 1:\n");
    while(!que1.empty()){
        printf("%3d",que1.top());
        que1.pop();
    }
    puts("");
    printf("Queue 2:\n");
    while(!que2.empty()){
        printf("%3d",que2.top());
        que2.pop();
    }
    puts("");
    puts("");
    printf("采用头文件\"functional\"内定义优先级:\n(priority_queue<int,vector<int>,greater<int>/less<int> >que;)\n");
    printf("Queue 3:\n");
    while(!que3.empty()){
        printf("%3d",que3.top());
        que3.pop();
    }
    puts("");
    printf("Queue 4:\n");
    while(!que4.empty()){
        printf("%3d",que4.top());
        que4.pop();
    }
    puts("");
    puts("");
    printf("采用结构体自定义优先级方式二:\n(priority_queue<number>que)\n");
    printf("Queue 5:\n");
    while(!que5.empty()){
        printf("%3d",que5.top());
        que5.pop();
    }
    puts("");
    printf("Queue 6:\n");
    while(!que6.empty()){
        printf("%3d",que6.top());
        que6.pop();
    }
    puts("");
    return ;
}  

Set

#include <iostream>
#include <set>

using namespace std;

int main()
{
    set<int> s;
    s.insert();
    s.insert();
    s.insert();
    s.insert();
    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 ;
}

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'] = ;
    mapTest['b'] = ;
    mapTest['c'] = ;
    mapTest['a'] = ;

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

    // 当使用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 ;
}

Hash

#include <iostream>
#include <cstring>

using namespace std;

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

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

int hash(long long p,int prime=)
{
    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 ;
        u=next[u];
    }
    next[s]=head[h];
    head[h]=s;
    return ;
}

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 ;
        u=next[u];
    }
    return ;
}

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

双向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 = ;
const int maxn =  + ;
vector <int> e[maxn];
int vis[maxn] , dist[maxn];

void solve(int x)
{
    int num[] , i , tmp , y;
    i = ;
    tmp = x;
    while(tmp) {
        num[i++] = tmp % ;
        tmp /= ;
    }
    for(i =  ; i <  ; i++)
        if(num[i] == )
            return;
    for(i =  ; i <  ; i++) {
        if(i < ) {
            swap(num[i] , num[i + ]);
            y = num[] *  + num[] *  + num[] *  + num[];
            e[x].push_back(y);
            e[y].push_back(x);
            swap(num[i] , num[i + ]);
        }
        tmp = num[i];
        if(num[i] == )
            num[i] = ;
        else
            num[i]++;
        y = num[] *  + num[] *  + num[] *  + num[];
        e[x].push_back(y);
        e[y].push_back(x);
        num[i] = tmp;

        if(num[i] == )
            num[i] = ;
        else
            num[i]--;
        y = num[] *  + num[] *  + num[] *  + num[];
        e[x].push_back(y);
        e[y].push_back(x);
        num[i] = tmp;
    }
}
int BFS_2(int start , int end)
{
    if(start == end)
        return ;
    memset(vis ,  , sizeof(vis));
    queue <int> que[];
    vis[start] = ;
    vis[end] = ;
    que[].push(start);
    que[].push(end);
    dist[start] = dist[end] = ;
    while(!que[].empty() && !que[].empty()) {
        int k = ;
        if(que[].size() < que[].size())
            k++;
        int u = que[k].front();
        que[k].pop();
        for(int i =  ; 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] + ;
            } else if(vis[j] == vis[u]) {
                continue;
            } else {
                return dist[j] + dist[u] + ;
            }
        }
    }
    return -;
}
int main()
{
    int T , a , b;
    for(int i =  ; i <=  ; i++)
        solve(i);
    cin >> T;
    while(T--) {
        scanf("%d %d" , &a , &b);
        printf("%d\n" , BFS_2(a , b));
    }
    return ;
}

Time: 2017-10-28