Training:Hash及应用

HDU 1425:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21604
排序输出前几个数,没什么难度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<cstdio>
#include<cstring>
const int maxn=500010;
int a[maxn*2];
int Scan(){
int res=0,ch,flag=0;
if((ch=getchar())=='-') flag=1;
else if(ch>='0'&&ch<='9') res=ch-'0';
while((ch=getchar())>='0'&&ch<='9') res=res*10+ch-'0';
return flag?-res:res;
}
void Out(int a){
if(a<0){putchar('-');a=-a;}
if(a>=10) Out(a/10);
putchar(a%10+'0');
}
int main(){
int n,m;
while(~scanf("%d%d",&n,&m)){
memset(a,0,sizeof(a));
getchar();
while(n--){
int k=Scan();
++a[maxn+k];
}
int pos=maxn*2-1;
bool first=true;
while(m){
while(!a[pos]) --pos;
if(first) first=false;
else putchar(' ');
Out(pos-maxn),--a[pos],--m;
}
putchar('\n');
}
return 0;
}

HDU 1800:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21605
输入可能带有前导0的 n 个数,输出数量最多的数。数据范围很大,用Hash表做。然而直接用int读入用map做也可以通过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
map<int,int> a;
int main(){
int n;
while(~scanf("%d",&n)){
a.clear();
while(n--){
int k;
scanf("%d",&k);
if(!a.count(k)) a[k]=0;
++a[k];
}
int ans=0;
for(map<int,int>::iterator it=a.begin();it!=a.end();++it)
ans=max(ans,it->second);
printf("%d\n",ans);
}
return 0;
}

HDU 1496:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18464
给出方程 a ∗ x 1 2 + b ∗ x 2 2 + c ∗ x 3 2 + d ∗ x 4 2
= 0 ,解的范围是[-100,100]。
方程中都是 x 2 ,所以在[0,100]内,进行折半搜索,求得的答案每个变量都有2种可能,所以最后乘16。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include<cstdio>
#include<cstring>
const int maxn=1000010;
int s[maxn*2];
int main(){
int a,b,c,d;
while(~scanf("%d%d%d%d",&a,&b,&c,&d)){
if((a>0&&b>0&&c>0&&d>0)||(a<0&&b<0&&c<0&&d<0)){puts("0");continue;}
memset(s,0,sizeof(s));
int ans=0;
for(int i=1;i<=100;++i)
for(int j=1;j<=100;++j)
++s[a*i*i+b*j*j+maxn];
for(int i=1;i<=100;++i)
for(int j=1;j<=100;++j)
ans+=s[maxn-(c*i*i+d*j*j)];
printf("%d\n",ans<<4);
}
return 0;
}

HDU 1228:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=21606
给出英文等式求和,很早之前ACM协会练过这道题,没有难度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<sstream>
#include<string>
#include<map>
using namespace std;
map<string,int> a;
void pre(){
a["one"]=1;
a["two"]=2;
a["three"]=3;
a["four"]=4;
a["five"]=5;
a["six"]=6;
a["seven"]=7;
a["eight"]=8;
a["nine"]=9;
a["zero"]=0;
return;
}
int main(){
pre();
string s0;
while(getline(cin,s0)){
stringstream ss(s0);
string s;
int aa=0,bb=0;
while(ss>>s){
if(!a.count(s)) break;
aa*=10,aa+=a[s];
}
while(ss>>s){
if(!a.count(s)) break;
bb*=10,bb+=a[s];
}
if(aa+bb==0) break;
cout<<aa+bb<<endl;
}
return 0;
}

HDU 1043:
http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=17579
给出八数码初始状态,输出到标准状态的移动方法,多组输入。类似于紫书上的八数码问题,但是是多组输入,固定终止状态,所以进行BFS时要反向进行,然后对每次输入的
状态直接打印路径。
对于状态判重,紫书上的编码方式被称为康托展开,使用 n ! 对状态编码。

1
2
3
4
5
6
7
8
9
10
11
const int fact[]={1,1,2,6,24,120,720,5040,40320,362880};
int Cantor(int s[]){
int sum=0;
for(int i=0;i<9;i++){
int cnt=0;
for(int j=i+1;j<9;j++)
if(s[i]>s[j]) cnt++;
sum+=cnt*fact[8-i];
}
return sum;
}

再利用数组记录当前状态当下一个状态的走法和下个状态的编号。打印路径时遍历链表不需要进行BFS。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn=1000000;
const int fact[]={1,1,2,6,24,120,720,5040,40320,362880};
const int go[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
const char dir[]="durl";
const int aim=46233;
bool vis[maxn];
int fa[maxn];
char h[maxn];
struct node{
int s[9],z,id;
};
node st;
int Cantor(int s[]){
int sum=0;
for(int i=0;i<9;i++){
int cnt=0;
for(int j=i+1;j<9;j++)
if(s[i]>s[j]) cnt++;
sum+=cnt*fact[8-i];
}
return sum;
}
void bfs(){
memset(fa,-1,sizeof(fa));
memset(vis,0,sizeof(vis));
node cur,next;
for(int i=0;i<8;i++)cur.s[i]=i+1;
cur.s[8]=0;
cur.z=8;
cur.id=aim;
vis[aim]=true;
queue<node> q;
q.push(cur);
while(!q.empty()){
cur=q.front();q.pop();
int x=cur.z/3;
int y=cur.z%3;
for(int i=0;i<4;i++){
int tx=x+go[i][0],ty=y+go[i][1];
if(tx<0||tx>2||ty<0||ty>2)continue;
next=cur;
next.z=tx*3+ty;
next.s[cur.z]=next.s[next.z];
next.s[next.z]=0;
next.id=Cantor(next.s);
if(!vis[next.id]){
vis[next.id]=true;
fa[next.id]=cur.id;
h[next.id]=dir[i];
q.push(next);
}
}
}
return;
}
int main(){
char c;
bfs();
while(cin>>c){
if(c=='x') st.s[0]=0,st.z=0;
else st.s[0]=c-'0';
for(int i=1;i<9;++i){
cin>>c;
if(c=='x') st.s[i]=0,st.z=i;
else st.s[i]=c-'0';
}
int k=Cantor(st.s);
if(vis[k]){
while(k!=-1){
putchar(h[k]);
k=fa[k];
}
putchar('\n');
}
else puts("unsolvable");
}
return 0;
}

本文迁移自我的 CSDN博客 ,格式可能有所偏差。

支付宝扫码领红包