【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