pat 散列题目代码详解()

1002:

 1 //思路很简单,存哈希表直接计算就可以了
 2 //需要注意的几个点
 3 //求最高次数的时候判断当前的系数是否为0
 4 //倒着输出的时候注意格式
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long 
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 const int N=1e3+10;
10 double a[N];
11 double b[N];
12 double s[N];
13 int k;
14 int cnt;
15 char c;
16 int cs;
17 double tmp;
18 signed main()
19 {
20     IOS;
21     cin>>k;
22     for(int i=1;i<=k;i++)
23     {
24         cin>>cs>>tmp;
25         //maxx=max(maxx,cs);
26         a[cs]=tmp;
27     }
28     cin>>k;
29     for(int i=1;i<=k;i++)
30     {
31         cin>>cs>>tmp;
32        // maxx=max(maxx,cs);
33         b[cs]=tmp;
34     }
35        for(int i=0;i<N;i++)
36        {
37            s[i]=a[i]+b[i];
38            if(s[i]!=0)
39            cnt++;
40        }
41        cout<<cnt;
42        for(int i=N-1;i>=0;i--)
43        {
44            if(s[i]!=0)
45            {
46                printf(" %d %.1f",i,s[i]);
47            }
48        }
49     return 0;
50 }

1009:

 1 //同1002,是多项式系列的乘法
 2 //注意的几个点,这个题是模拟多项式的乘法,按照系数和次数的运算法则运算即可
 3 //还是要注意输出
 4 //注意乘法运算至少会产生N*N项,所以说开数组和运算的时候需要注意
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long 
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 const int N=1e3+10;
10 double a[N];
11 double b[N];
12 double s[N*N];
13 int k;
14 int cnt;
15 signed main()
16 {
17     IOS;
18     cin>>k;
19     int cs;
20     double tmp;
21     for(int i=1;i<=k;i++)
22     {
23         cin>>cs>>tmp;
24         a[cs]+=tmp;
25     }
26     cin>>k;
27     for(int i=1;i<=k;i++)
28     {
29         cin>>cs>>tmp;
30         b[cs]+=tmp;
31     }
32     for(int i=0;i<N;i++)
33     {
34         for(int j=0;j<N;j++)
35         {
36             s[i+j]+=a[i]*b[j];
37         }
38     }
39     for(int i=0;i<N*N;i++)
40     {
41         if(s[i]!=0)
42         cnt++;
43     }
44     cout<<cnt;
45     for(int i=N*N-1;i>=0;i--)
46     {
47         if(s[i]!=0.0)
48         {
49             printf(" %d %.1f",i,s[i]);
50         }
51     }
52     return 0;
53 }

1084:

 1 //还得是柳神写的代码
 2 //大体思路,在s2中查找s1,如果没有出现,并且存ans的串中也没有发现s1的大写
 3 //就存入
 4 //再次感叹,柳神是真强啊,代码简洁且精妙
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long 
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 string s1;
10 string s2;
11 string ans;
12 signed main()
13 {
14     IOS;
15     cin>>s1>>s2;
16     for(int i=0;i<s1.length();i++)
17     {
18         if(s2.find(s1[i])==string::npos&&ans.find(toupper(s1[i]))==string::npos)
19         {
20                ans+=toupper(s1[i]);
21         }
22     }
23     cout<<ans;
24     return 0;
25 }//还得是柳神写的代码
26 //大体思路,在s2中查找s1,如果没有出现,并且存ans的串中也没有发现s1的大写
27 //就存入
28 //再次感叹,柳神是真强啊,代码简洁且精妙
29 #include<bits/stdc++.h>
30 using namespace std;
31 #define int long long 
32 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
33 string s1;
34 string s2;
35 string ans;
36 signed main()
37 {
38     IOS;
39     cin>>s1>>s2;
40     for(int i=0;i<s1.length();i++)
41     {
42         if(s2.find(s1[i])==string::npos&&ans.find(toupper(s1[i]))==string::npos)
43         {
44                ans+=toupper(s1[i]);
45         }
46     }
47     cout<<ans;
48     return 0;
49 }

1092:

 1 //需要注意的点是在q中查找s2
 2 //大体思路是用map存索引字符串,键值++
 3 //然后匹配要求串,如果有且大于0--,没有就表明缺失一个
 4 #include<bits/stdc++.h>
 5 using namespace std;
 6 #define int long long 
 7 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 8 const int N=1e2+10;
 9 string s1;
10 string s2;
11 map<char,int>q;
12 int ans;
13 signed main()
14 {
15     IOS;
16     cin>>s1>>s2;
17     for(int i=0;i<s1.length();i++)
18     {
19         q[s1[i]]++;
20     }
21     for(int i=0;i<s2.length();i++)
22     {
23         if(q.find(s2[i])!=q.end()&&q[s2[i]]>0)//tip
24         {
25             q[s2[i]]--;
26         }
27         else
28             ans++;
29     }
30     if(!ans)
31     {
32         cout<<"Yes"<<" "<<(s1.length()-s2.length());
33     }
34     else{
35          cout<<"No"<<" "<<ans;
36     }
37     return 0;
38 }

1116:

 1 //常规思路常规做法
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define int long long 
 5 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 6 const int N=1e4+10;
 7 int vis[N];
 8 int k;
 9 map<int,string>q;
10 int id;
11 bool is_prime(int x)
12 {
13     if(x<2)
14         return false;
15     for(int i=2;i<=sqrt(x);i++)
16     {
17         if(x%i==0)
18             return false;
19     }
20     return true;
21 }
22 signed main()
23 {
24        //IOS;
25     cin>>k>>id;
26     q[id]+="Mystery Award";
27     vis[id]=1;
28     for(int i=2;i<=k;i++)
29     {
30         cin>>id;
31         if(is_prime(i))
32         {
33             q[id]+="Minion";
34         }
35         else{
36             q[id]+="Chocolate";
37         }
38         vis[id]=1;
39         }
40     cin>>k;
41     while(k--)
42     {
43         cin>>id;
44         if(vis[id]==0)
45         {
46             printf("%04lld: ",id);
47            cout<<"Are you kidding?"<<endl;
48         }
49         else{
50             vis[id]++;
51             if(vis[id]>2)
52             {
53                 printf("%04lld: ",id);
54                 cout<<"Checked"<<endl;
55                 continue;
56             }
57             printf("%04lld: ",id);
58             cout<<q[id]<<endl;
59         }
60     }
61     return 0;
62 }

1121:

 1 //大体思路
 2 //利用哈希两边的情侣,并且在输入m之后依次存入输入的人并标记为true
 3 //遍历哈希表如果情侣双方都存在(都是true)就都置为false
 4 //然后从0~99999依次查找剩下的为true的,要么是没对象要么对象没来
 5 //存到set里输出即可
 6 //注意输出格式
 7 #include<bits/stdc++.h>
 8 using namespace std;
 9 #define int long long 
10 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
11 const int N=1e5+10;
12 bool vis[N]={false};
13 unordered_map<int,int>q;
14 int n,m;
15 set<int>s;
16 int cnt;
17 int ip;
18 int id;
19 signed main()
20 {
21     //IOS;
22     cin>>n;
23     int id1,id2;
24     for(int i=1;i<=n;i++)
25     {
26         cin>>id1>>id2;
27         q.insert(make_pair(id1,id2));
28     }
29     cin>>m;
30     for(int i=1;i<=m;i++)
31     {
32         cin>>id;
33         vis[id]=true;
34     }
35     for(auto &it:q)
36     {
37         if(vis[it.first]&&vis[it.second])
38         {
39             vis[it.first]=false;
40             vis[it.second]=false;
41         }
42     }
43     for(int i=0;i<=99999;i++)
44     {
45         if(vis[i])    
46         {
47             s.insert(i);
48         }
49     }
50     cout<<s.size()<<endl;
51     for(auto &it:s)
52     {
53         printf("%05lld",it);
54         ip++;
55         if(ip<s.size())
56         cout<<" ";
57     }
58     return 0;
59 }
————————

1002:

 1 //思路很简单,存哈希表直接计算就可以了
 2 //需要注意的几个点
 3 //求最高次数的时候判断当前的系数是否为0
 4 //倒着输出的时候注意格式
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long 
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 const int N=1e3+10;
10 double a[N];
11 double b[N];
12 double s[N];
13 int k;
14 int cnt;
15 char c;
16 int cs;
17 double tmp;
18 signed main()
19 {
20     IOS;
21     cin>>k;
22     for(int i=1;i<=k;i++)
23     {
24         cin>>cs>>tmp;
25         //maxx=max(maxx,cs);
26         a[cs]=tmp;
27     }
28     cin>>k;
29     for(int i=1;i<=k;i++)
30     {
31         cin>>cs>>tmp;
32        // maxx=max(maxx,cs);
33         b[cs]=tmp;
34     }
35        for(int i=0;i<N;i++)
36        {
37            s[i]=a[i]+b[i];
38            if(s[i]!=0)
39            cnt++;
40        }
41        cout<<cnt;
42        for(int i=N-1;i>=0;i--)
43        {
44            if(s[i]!=0)
45            {
46                printf(" %d %.1f",i,s[i]);
47            }
48        }
49     return 0;
50 }

1009:

 1 //同1002,是多项式系列的乘法
 2 //注意的几个点,这个题是模拟多项式的乘法,按照系数和次数的运算法则运算即可
 3 //还是要注意输出
 4 //注意乘法运算至少会产生N*N项,所以说开数组和运算的时候需要注意
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long 
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 const int N=1e3+10;
10 double a[N];
11 double b[N];
12 double s[N*N];
13 int k;
14 int cnt;
15 signed main()
16 {
17     IOS;
18     cin>>k;
19     int cs;
20     double tmp;
21     for(int i=1;i<=k;i++)
22     {
23         cin>>cs>>tmp;
24         a[cs]+=tmp;
25     }
26     cin>>k;
27     for(int i=1;i<=k;i++)
28     {
29         cin>>cs>>tmp;
30         b[cs]+=tmp;
31     }
32     for(int i=0;i<N;i++)
33     {
34         for(int j=0;j<N;j++)
35         {
36             s[i+j]+=a[i]*b[j];
37         }
38     }
39     for(int i=0;i<N*N;i++)
40     {
41         if(s[i]!=0)
42         cnt++;
43     }
44     cout<<cnt;
45     for(int i=N*N-1;i>=0;i--)
46     {
47         if(s[i]!=0.0)
48         {
49             printf(" %d %.1f",i,s[i]);
50         }
51     }
52     return 0;
53 }

1084:

 1 //还得是柳神写的代码
 2 //大体思路,在s2中查找s1,如果没有出现,并且存ans的串中也没有发现s1的大写
 3 //就存入
 4 //再次感叹,柳神是真强啊,代码简洁且精妙
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long 
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 string s1;
10 string s2;
11 string ans;
12 signed main()
13 {
14     IOS;
15     cin>>s1>>s2;
16     for(int i=0;i<s1.length();i++)
17     {
18         if(s2.find(s1[i])==string::npos&&ans.find(toupper(s1[i]))==string::npos)
19         {
20                ans+=toupper(s1[i]);
21         }
22     }
23     cout<<ans;
24     return 0;
25 }//还得是柳神写的代码
26 //大体思路,在s2中查找s1,如果没有出现,并且存ans的串中也没有发现s1的大写
27 //就存入
28 //再次感叹,柳神是真强啊,代码简洁且精妙
29 #include<bits/stdc++.h>
30 using namespace std;
31 #define int long long 
32 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
33 string s1;
34 string s2;
35 string ans;
36 signed main()
37 {
38     IOS;
39     cin>>s1>>s2;
40     for(int i=0;i<s1.length();i++)
41     {
42         if(s2.find(s1[i])==string::npos&&ans.find(toupper(s1[i]))==string::npos)
43         {
44                ans+=toupper(s1[i]);
45         }
46     }
47     cout<<ans;
48     return 0;
49 }

1092:

 1 //需要注意的点是在q中查找s2
 2 //大体思路是用map存索引字符串,键值++
 3 //然后匹配要求串,如果有且大于0--,没有就表明缺失一个
 4 #include<bits/stdc++.h>
 5 using namespace std;
 6 #define int long long 
 7 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 8 const int N=1e2+10;
 9 string s1;
10 string s2;
11 map<char,int>q;
12 int ans;
13 signed main()
14 {
15     IOS;
16     cin>>s1>>s2;
17     for(int i=0;i<s1.length();i++)
18     {
19         q[s1[i]]++;
20     }
21     for(int i=0;i<s2.length();i++)
22     {
23         if(q.find(s2[i])!=q.end()&&q[s2[i]]>0)//tip
24         {
25             q[s2[i]]--;
26         }
27         else
28             ans++;
29     }
30     if(!ans)
31     {
32         cout<<"Yes"<<" "<<(s1.length()-s2.length());
33     }
34     else{
35          cout<<"No"<<" "<<ans;
36     }
37     return 0;
38 }

1116:

 1 //常规思路常规做法
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define int long long 
 5 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 6 const int N=1e4+10;
 7 int vis[N];
 8 int k;
 9 map<int,string>q;
10 int id;
11 bool is_prime(int x)
12 {
13     if(x<2)
14         return false;
15     for(int i=2;i<=sqrt(x);i++)
16     {
17         if(x%i==0)
18             return false;
19     }
20     return true;
21 }
22 signed main()
23 {
24        //IOS;
25     cin>>k>>id;
26     q[id]+="Mystery Award";
27     vis[id]=1;
28     for(int i=2;i<=k;i++)
29     {
30         cin>>id;
31         if(is_prime(i))
32         {
33             q[id]+="Minion";
34         }
35         else{
36             q[id]+="Chocolate";
37         }
38         vis[id]=1;
39         }
40     cin>>k;
41     while(k--)
42     {
43         cin>>id;
44         if(vis[id]==0)
45         {
46             printf("%04lld: ",id);
47            cout<<"Are you kidding?"<<endl;
48         }
49         else{
50             vis[id]++;
51             if(vis[id]>2)
52             {
53                 printf("%04lld: ",id);
54                 cout<<"Checked"<<endl;
55                 continue;
56             }
57             printf("%04lld: ",id);
58             cout<<q[id]<<endl;
59         }
60     }
61     return 0;
62 }

1121:

 1 //大体思路
 2 //利用哈希两边的情侣,并且在输入m之后依次存入输入的人并标记为true
 3 //遍历哈希表如果情侣双方都存在(都是true)就都置为false
 4 //然后从0~99999依次查找剩下的为true的,要么是没对象要么对象没来
 5 //存到set里输出即可
 6 //注意输出格式
 7 #include<bits/stdc++.h>
 8 using namespace std;
 9 #define int long long 
10 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
11 const int N=1e5+10;
12 bool vis[N]={false};
13 unordered_map<int,int>q;
14 int n,m;
15 set<int>s;
16 int cnt;
17 int ip;
18 int id;
19 signed main()
20 {
21     //IOS;
22     cin>>n;
23     int id1,id2;
24     for(int i=1;i<=n;i++)
25     {
26         cin>>id1>>id2;
27         q.insert(make_pair(id1,id2));
28     }
29     cin>>m;
30     for(int i=1;i<=m;i++)
31     {
32         cin>>id;
33         vis[id]=true;
34     }
35     for(auto &it:q)
36     {
37         if(vis[it.first]&&vis[it.second])
38         {
39             vis[it.first]=false;
40             vis[it.second]=false;
41         }
42     }
43     for(int i=0;i<=99999;i++)
44     {
45         if(vis[i])    
46         {
47             s.insert(i);
48         }
49     }
50     cout<<s.size()<<endl;
51     for(auto &it:s)
52     {
53         printf("%05lld",it);
54         ip++;
55         if(ip<s.size())
56         cout<<" ";
57     }
58     return 0;
59 }