隆重介绍骗分黑科技 map
能水过不少题，且能极大缩短代码
A,B均为数据类型
map<A,B>a; A为a数组下标，B为a数组存储
水题（不一定AC，但可以获得极可观的分数）
P3370 【模板】字符串哈希 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 正经想学哈希的不要偷懒哦
P2814 家谱 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P1032 [NOIP2002 提高组] 字串变换 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
P3879 [TJOI2010]阅读理解 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
后缀代码
一.字符串哈希
1 #include<bits/stdc++.h>
2 using namespace std;
3 namespace _xzy
4 {
5 typedef long long ll;
6 inline int read()
7 {
8 ll sm=0,flag=1;
9 char ch=getchar();
10 while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();}
11 while(ch>='0'&&ch<='9'){sm=(sm<<1)+(sm<<3)+(ch^48);ch=getchar();}
12 return sm*flag;
13 }
14 ll n,ans;
15 map<string,int>vis;
16 void My_main()
17 {
18 n=read();
19 for(ll i=1;i<=n;++i)
20 {
21 string s;
22 cin>>s;
23 if(!vis[s])ans++;
24 vis[s]=1;
25 }
26 cout<<ans;
27 }
28 }
29 int main()
30 {
31 _xzy::My_main();
32 return 0;
33 }
View Code
二.家谱
1 //与并查集结合的题，注意理清思路
2 #include<bits/stdc++.h>
3 using namespace std;
4 namespace _xzy
5 {
6 typedef long long ll;
7 inline int read()
8 {
9 ll sm=0,flag=1;
10 char ch=getchar();
11 while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();}
12 while(ch>='0'&&ch<='9'){sm=(sm<<1)+(sm<<3)+(ch^48);ch=getchar();}
13 return sm*flag;
14 }
15 string s,s_father;
16 map<string,string>f;
17 string find(string x)
18 {
19 if(x==f[x])return x;
20 else return f[x]=find(f[x]);
21 }
22 void My_main()
23 {
24 char ch;
25 while(1)
26 {
27 ch=getchar();
28 if(ch=='#')
29 {
30 cin>>s_father;
31 if(f[s_father]=="")
32 f[s_father]=s_father;
33 }
34 else if(ch=='+')
35 {
36 cin>>s;
37 f[s]=s_father;
38 }
39 else if(ch=='?')
40 {
41 cin>>s;
42 cout<<s<<" "<<find(s)<<endl;
43 }
44 else if(ch=='$')break;
45 }
46 }
47 }
48 int main()
49 {
50 _xzy::My_main();
51 return 0;
52 }
View Code
三.字串变换
1 //该题其实用map是可以得满分的，但懒散的我第一次用map得了80，就完了......
2 #include<bits/stdc++.h>
3 using namespace std;
4 namespace _xzy
5 {
6 typedef long long ll;
7 inline int read()
8 {
9 ll sm=0,flag=1;
10 char ch=getchar();
11 while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();}
12 while(ch>='0'&&ch<='9'){sm=(sm<<1)+(sm<<3)+(ch^48);ch=getchar();}
13 return sm*flag;
14 }
15 ll num=1,ans=11;
16 string start,end;
17 string a[7],b[7];
18 struct node
19 {
20 string s;
21 int sum;
22 };
23 map<string,bool>vis;
24 queue<node>q;
25 void bfs()
26 {
27 if(start==end)
28 {
29 ans=0;return;
30 }
31 q.push((node){start,0});
32 while(!q.empty())
33 {
34 node u=q.front();
35 string now=u.s;
36 ll dis=u.sum;
37 string::size_type point;
38 q.pop();
39 for(ll i=1;i<=num;++i)
40 {
41 point=now.find(a[i]);
42 if(point!=string::npos&&dis<10)
43 {
44 string middle=now;
45 middle.replace(point,a[i].size(),b[i]);
46 point=now.find(a[i],point+1);
47 if(vis[middle]==1)continue;
48 vis[middle]=1;
49 q.push((node){middle,dis+1});
50 if(middle==end)
51 {
52 ans=dis+1;return;
53 }
54 }
55 }
56 }
57 }
58 void My_main()
59 {
60 cin>>start>>end;
61 while(cin>>a[num],cin>>b[num])
62 num++;
63 num--;
64 bfs();
65 if(ans>10)
66 cout<<"NO ANSWER!";
67 else
68 cout<<ans;
69 }
70 }
71 int main()
72 {
73 _xzy::My_main();
74 return 0;
75 }
View Code
四.阅读理解
1 //精妙的链表
2 #include<bits/stdc++.h>
3 using namespace std;
4 namespace _xzy
5 {
6 typedef long long ll;
7 inline int read()
8 {
9 ll sm=0,flag=1;
10 char ch=getchar();
11 while(ch<'0'||ch>'9'){if(ch=='-')flag=-1;ch=getchar();}
12 while(ch>='0'&&ch<='9'){sm=(sm<<1)+(sm<<3)+(ch^48);ch=getchar();}
13 return sm*flag;
14 }
15 const ll M=1e6+2;
16 ll n,m;
17 ll total,cnt;
18 ll head[M*5],ans[M*5];
19 map<string,int>num;
20 struct node
21 {
22 ll nex,to;
23 }e[M*5];
24 void add(ll x,ll y)
25 {
26 e[++cnt]=(node){head[x],y};
27 head[x]=cnt;
28 }
29 void My_main()
30 {
31 n=read();
32 for(ll i=1;i<=n;++i)
33 {
34 ll l=read();
35 string s;
36 for(ll j=1;j<=l;++j)
37 {
38 cin>>s;
39 if(!num[s])num[s]=++total;
40 add(num[s],i);
41 }
42 }
43 m=read();
44 for(ll i=1;i<=m;++i)
45 {
46 string s;
47 cin>>s;
48 cnt=0;
49 for(ll i=head[num[s]];i;i=e[i].nex)
50 if(ans[cnt]!=e[i].to)
51 ans[++cnt]=e[i].to;
52 for(ll i=cnt;i>=1;--i)
53 {
54 if(i>1)
55 cout<<ans[i]<<" ";
56 else
57 cout<<ans[i];
58 }
59 cout<<endl;
60 }
61 }
62 }
63 int main()
64 {
65 _xzy::My_main();
66 return 0;
67 }
View Code