Training：Hash及应用

发表于 分类于 Disqus：

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博客，格式可能有所偏差。 **

相关文章