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 }
标签：周赛,pat,AT276,int,IOS,cin,long,tie,define From： https://www.cnblogs.com/LQS-blog/p/16863377.html