pat：
模考58分，相较夏季赛差了不少
1.模拟
给定一个字符串，要求按照得分点和失分点进行模拟，求最后得分即可
模拟比较难写
参考小柳学渣大神的代码，大神码风和思路都很好
1 #include <bits/stdc++.h> 2 using namespace std; 3 int main() 4 { 5 int l,t,n; 6 cin>>l>>t>>n; 7 while(n--) 8 { 9 int r=0,length1=1,length2=1; 10 string s; 11 cin>>s; 12 //字符串以`f`开头，则分数-2； 13 if(s[0]=='f')r-=2; 14 //字符串以`a`结尾，则分数-1； 15 if(s[l-1]=='a')r-=1; 16 for(int i=1;i<l;i++) 17 { 18 if(s[i]==s[i-1]) 19 { //如果当前字母和上一个字母相同，则length1加1 20 length1++; 21 } 22 else 23 { //如果连续相同字母的每个最长的片段长度大于5，则分数+3； 24 if(length1>5)r+=3; 25 //初始化length1为1 26 length1=1; 27 } 28 29 if(s[i]==s[i-1]+1) 30 { //如果当前字母比上一个字母大1，则length2加1 31 length2++; 32 } 33 else 34 { //如果连续递增的每个最长的片段长度大于3，则分数+5，例如`abcd`和`defgh`。 35 if(length2>3)r+=5; 36 //初始化length2为1 37 length2=1; 38 } 39 //如果`a`后紧跟`e`或`h`，则分数-4； 40 if(s[i-1]=='a'&&(s[i]=='e'||s[i]=='h'))r-=4; 41 } 42 //如果连续相同字母的每个最长的片段长度大于5，则分数+3； 43 if(length1>5)r+=3; 44 //如果连续递增的每个最长的片段长度大于3，则分数+5，例如`abcd`和`defgh`。 45 if(length2>3)r+=5; 46 //每组询问计算对应的分数 47 cout<<r; 48 //如果分数超过阈值K则在分数后输出`!!!` 49 if(r>t)cout<<"!!!"; 50 cout<<endl; 51 } 52 return 0; 53 }
2.sort区间维护或者是优先队列
给定n个数和一个k，要求输出前k个最大的数
用普通sort在输出会超内存
所以这里采取的策略是维护前k个数：
即开一个k+2的数组，先插入k个数进行排序，在输入后n-k+1个数，每插入一个便对数组进行排序，可以在不超内存的情况下实现优化
参考代码：
1 #include<bits/stdc++.h>//维护一个k数组做法 2 using namespace std; 3 #define int long long 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 5 const int N=6; 6 int n,k; 7 int a[N]; 8 signed main() 9 { 10 IOS; 11 cin>>n>>k; 12 int mi=min(n,k); 13 for(int i=1;i<=mi;i++) 14 { 15 cin>>a[i]; 16 } 17 sort(a+1,a+1+mi,greater<int>()); 18 for(int j=mi+1;j<=n;j++) 19 { 20 cin>>a[mi+1]; 21 sort(a+1,a+2+mi,greater<int>()); 22 } 23 for(int i=1;i<=mi;i++) 24 { 25 cout<<a[i]; 26 if(i<mi) 27 cout<<" "; 28 } 29 return 0; 30 }
当然也可以用优先队列，思想同上
参考代码：
1 #include<bits/stdc++.h>//优先队列做法 2 using namespace std; 3 #define int long long 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 5 int n; 6 const int N=1e6+10; 7 int a[N]; 8 priority_queue<int,vector<int>,greater<int>>q; 9 vector<int>ans; 10 int k; 11 signed main() 12 { 13 IOS; 14 cin>>n>>k; 15 for(int i=0;i<n;i++) 16 { 17 cin>>a[i]; 18 q.push(a[i]); 19 if(q.size()>k) 20 q.pop(); 21 } 22 while(!q.empty()) 23 { 24 ans.push_back(q.top()); 25 q.pop(); 26 } 27 for(int i=ans.size()-1;i>=0;i--) 28 { 29 cout<<ans[i]; 30 if(i>0) 31 cout<<" "; 32 } 33 return 0; 34 }
3.建一课树或者是模拟一颗树
给定一颗树的层序序列，要求判断这颗树是否是bst且输出其中序序列
所以根据bst的中序序列是递增的来判断是否是bst，然后在输出中序序列即可
参考代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 5 const int N=1e3+10; 6 int n; 7 int a[N]; 8 vector<int>in,ans; 9 bool flag=true; 10 void inorder(int root) 11 { 12 if(root<=n) 13 { 14 inorder(root*2); 15 if(a[root]!=-1) 16 in.push_back(a[root]); 17 inorder(root*2+1); 18 } 19 } 20 signed main() 21 { 22 IOS; 23 cin>>n; 24 for(int i=1;i<=n;i++) 25 { 26 cin>>a[i]; 27 } 28 inorder(1); 29 /*for(int i=0;i<in.size();i++) 30 { 31 if(in[i]!=-1) 32 ans.push_back(in[i]); 33 }*/ 34 for(int i=1;i<in.size();i++) 35 { 36 if(in[i]<in[i-1]) 37 { 38 flag=false; 39 break; 40 } 41 } 42 if(flag) 43 { 44 cout<<"YES"<<endl; 45 } 46 else 47 { 48 cout<<"NO"<<endl; 49 } 50 for(int i=0;i<in.size();i++) 51 { 52 cout<<in[i]; 53 if(i<in.size()-1) 54 cout<<" "; 55 } 56 57 return 0; 58 }
ACwing周赛：
1。判断是否是反转序列
即abcd是否等于dcba这种的
tip:注意两者的长度判断即可
参考代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 5 string a,b; 6 signed main() 7 { 8 IOS; 9 cin>>a>>b; 10 bool flag=true; 11 int cnt=0; 12 if(a.size()!=b.size()) 13 { 14 cout<<"NO"<<endl; 15 return 0; 16 } 17 for(int i=0;i<a.size();i++) 18 { 19 if(a[i]!=b[a.size()-1-i]) 20 { 21 flag=false; 22 break; 23 } 24 } 25 if(flag) 26 cout<<"YES"<<endl; 27 else 28 { 29 cout<<"NO"<<endl; 30 } 31 return 0; 32 }
2.数对
给定一个字符串
要求找出满足1<=i,j<=n且s[i]=s[j]的数对（i，j)有多少
暴力不行，试过
找规律可以，用哈希解决
如果出现过一次，就只有一对，如果不是就是出现次数的平方
参考代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 5 const int N=1e5+10; 6 int n; 7 string s; 8 unordered_map<char,int>q; 9 int ans; 10 signed main() 11 { 12 IOS; 13 cin>>s; 14 for(int i=0;i<s.length();i++) 15 { 16 q[s[i]]++; 17 } 18 for(auto x:q) 19 { 20 if(x.second == 1) 21 ans += 1; 22 else 23 ans += x.second * x.second; 24 } 25 cout<<ans<<endl; 26 return 0; 27 }
AT
A：给定一个字符串要求输出a出现了多少次
参考代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 5 signed main() 6 { 7 IOS; 8 string s; 9 cin>>s; 10 int index=0; 11 bool flag=false; 12 for(int i=0;i<s.size();i++) 13 { 14 if(s[i]=='a') 15 { 16 index=i; 17 flag=true; 18 } 19 } 20 if(!flag) 21 cout<<-1<<endl; 22 else 23 cout<<index+1<<endl; 24 return 0; 25 }
B：
给定一个图，用邻接表存储，要求输出连接道路的条数，并且按照升序输出连接道路的条数
按邻接表存之后对每一个一维内进行排序
然后输出即可
参考代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 5 const int N=1e5+10; 6 vector<int>g[N]; 7 int n,m; 8 map<vector<int>,int>q; 9 signed main() 10 { 11 IOS; 12 cin>>n>>m; 13 int s,t; 14 for(int i=1;i<=m;i++) 15 { 16 cin>>s>>t; 17 g[s].push_back(t); 18 g[t].push_back(s); 19 } 20 for(int i=1;i<=n;i++) 21 { 22 sort(g[i].begin(),g[i].end()); 23 cout<<g[i].size()<<" "; 24 for(auto it:g[i]) 25 { 26 cout<<it<<" "; 27 } 28 cout<<endl; 29 } 30 return 0; 31 }
C：
输出字典序前一个全排列序列
用prev_permutation来进行排序
参考代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 5 const int N=1e4+10; 6 //int a[N]; 7 int n; 8 vector<int>c; 9 vector<int>b[N]; 10 vector<int>a; 11 signed main() 12 { 13 IOS; 14 int maxx; 15 cin>>n; 16 int x; 17 for(int i=0;i<n;i++) 18 { 19 cin>>x; 20 a.push_back(x); 21 } 22 prev_permutation(a.begin(),a.end()); 23 for(int i=0;i<a.size();i++) 24 { 25 cout<<a[i]<<" "; 26 } 27 return 0; 28 }
D：
给定n个整数，a1到an，你可以做一下操作，让a1到an中的某个数除2，或者除3，这都算操作了一次
问能都最终把a1到an的值变为一样。如果可以输出最小的次数，否则输出-1。
参考自https://zhuanlan.zhihu.com/p/580786262，人家写的挺好的
参考代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define int long long 4 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); 5 const int N=1e3+10; 6 int n; 7 int a[N]; 8 int cm=1; 9 int ans; 10 signed main() 11 { 12 IOS; 13 cin>>n; 14 for(int i=1;i<=n;i++) 15 { 16 cin>>a[i]; 17 //cm=__gcd(cm,a[i]); 18 } 19 //cout<<cm<<endl; 20 cm=a[1]; 21 for(int i=2;i<=n;i++) 22 { 23 cm=__gcd(cm,a[i]); 24 } 25 26 bool flag=true; 27 for(int i=1;i<=n;i++) 28 { 29 a[i]=a[i]/cm; 30 while(a[i]%2==0) 31 { 32 a[i]=a[i]/2; 33 ans++; 34 } 35 while(a[i]%3==0) 36 { 37 a[i]=a[i]/3; 38 ans++; 39 } 40 if(a[i]!=1) 41 { 42 flag=false; 43 } 44 } 45 if(!flag) 46 cout<<"-1"<<endl; 47 else 48 cout<<ans<<endl; 49 return 0; 50 }
原文地址：http://www.cnblogs.com/LQS-blog/p/16863377.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
