PAT-List

生活艰难。。。
柳神博客
大部分参考大神博客

单词记录

consecutive 连续的
prime number 质数
non-increasing order 从大到小(降序)
vertices 顶点
incompatible 不相容的

little note

结构体定义

note s = {a,b};

初始化二维数组

只可对部分元素初始化未初始化元素为0。

string 用法

  1. 切片 s.substr(pos,n)[启始位置,数量]
  2. sort(a.begin(),a.end(),cmp)–>cmp(const note &a const note &b) => return a.value>b.vlaue; 最后回从大到小排列。

unsorted_map

  1. include<unordered_map>
  2. unordered_map<type,type>
  3. auto(it : m) ans.push_back({it.first,it.second})

set

  1. include
  2. set s;s.insert(a[m])–>可以去重排序
  3. s.size(),s.find()

vector

  1. 顺序储存
  2. 动态数组
  3. resize(size_type n);

map

  1. a dictionary ; map<int,CString>,map<int,vector>;
  2. 关于考试

    2.4我感觉考试本身深度搜索广度搜索和最短路径为常考必考。
    ##PAT-1
    1001 A+B Format (20分)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
int a,b,c,flag = 0;
scanf("%d %d",&a,&b);
c = a+b;
if(c < 0){
c= -c;
printf("-");
}
string s = to_string(c);
int j =1;
reverse(s.begin(),s.end());
for(int i = s.size()-1;i>=0;i--){
printf("%c",s[i]);
if(i % 3 == 0 && i!=0){
printf(",");
}
}
return 0;
}

##PAT-2

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
#include<iostream>
#include<algorithm>

using namespace std;

int main(){
int K,n,flag=0;
float a[1001]={0},m;
scanf("%d",&K);
for(int i = 0;i<K;i++){
scanf("%d",&n);
scanf("%f",&a[n]);
}
scanf("%d",&K);
for(int i = 0;i<K;i++){
scanf("%d",&n);
scanf("%f",&m);
a[n]+=m;
}
for(int i = 0;i<1001;i++){
if(a[i] != 0){
flag+=1;
}
}
printf("%d",flag);
for(int i = 1000;i>=0;i--){
if(a[i] != 0){
printf(" %d %0.1f",i,a[i]);
}
}
return 0;
}

##PAT-3
测试点一直没过,原因是d这个地方存在方法一个d[j] 写成了不变的d[s]
测试点2和测试点5是表示其为无向图。

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
#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
#define MAX 501
int N,M,G[MAX][MAX];
int d[501];
int w[501] = {0};
int weight[501] = {0};
bool visi[501] = {false};
int num[501] = {0};
int Dijaik(int s){
d[s] = 0;
w[s] = weight[s];
num[s] = 1;
for(int i = 0;i<N;i++){
int u =-1,MIN = 1000000;
for(int j = 0;j<N;j++){
if(visi[j] == false && d[js] < MIN){
u = j;
MIN = d[j];
}
}
if(u == -1) return 0;
visi[u] = true;
for(int v =0;v<N;v++){
if(visi[v]==false && G[u][v] != 999999){
if(d[v] > d[u]+G[u][v]){
d[v] = d[u]+G[u][v];
w[v] = w[u]+weight[v];
num[v] = num[u];
}else if (d[v] == d[u]+G[u][v])
{
if(w[u]+weight[v] > w[v]){
w[v] = w[u]+weight[v];
}
/* code */
num[v] += num[u];
}

}
}
}

}
int main(){
fill(G[0],G[0]+MAX*MAX,999999);
fill(d,d+MAX,1000000);
int source,target,a,b,c;
scanf("%d %d %d %d",&N,&M,&source,&target);
for(int i = 0;i<N;i++){
scanf("%d",&weight[i]);
}
for(int i = 0;i<M;i++){
scanf("%d %d %d",&a,&b,&c);
G[a][b]=G[b][a] = c;
}
Dijaik(source);
printf("%d %d\n",num[target],w[target]);
return 0;

}

PAT-1152

测试点6为时间测试判断质数时需要开根号。
测试点4,5边界条件。当质数在边界时。
测试点2 是否以0023输出而不是23。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
using namespace std;


bool is(long m){
if(m == 0 || m==1){
return false;
}
for(int j = 2;j*j<=m;j++){
if(m % j == 0){
return false;
}
}
return true;
}
int main(){
string s;
int L,K;
long t;
scanf("%d %d",&L,&K);
cin >> s;
int i;
for(i = 0;i<=L-K;i++){
string m = s.substr(i,K);
t = stol(m);
if(is(t)){
cout << m;
return 0;
}
}
printf("404");
return 0;
}

#PAT-1153
遇到的问题主要是在输入上,然后就是容器的使用,应该正确的使用sort函数啊,map之类的容器。

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
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<unordered_map>

using namespace std;

struct note
{
string t;
int value;
};
bool cmp(const note &a ,const note &b){
return a.value != b.value ? a.value > b.value : a.t < b.t;
}
int main(){
int N,M;
int idx;
string s;
scanf("%d %d",&N,&M);
vector<note> v(N);
for(int i = 0; i<N;i++){
cin>>v[i].t>>v[i].value;
}

for(int i =0;i<M;i++){
cin>>idx>>s;
vector<note> ans;
int num=0;
int number = 0;
printf("Case %d: %d %s\n",i+1,idx,s.c_str());
if(idx == 1){
for(int i =0; i < N;i++){
if(s[0] == v[i].t[0]) ans.push_back(v[i]);
}
}else if (idx == 2)
{
for(int i = 0;i < N;i++){
if(v[i].t.substr(1,3) == s){
num += v[i].value;
number +=1;
}
}
if(number != 0) printf("%d %d\n",number,num);
}else if (idx == 3)
{
unordered_map<string,int> m;
for(int i = 0;i<N;i++){
if(v[i].t.substr(4,6) == s){
m[v[i].t.substr(1,3)]++;
}
}
for(auto it = m.begin();it!=m.end();it++)
{
note f = {it->first,it->second};
ans.push_back(f);
}
}
sort(ans.begin(),ans.end(),cmp);
for(int i = 0;i<ans.size();i++){
printf("%s %d\n",ans[i].t.c_str(),ans[i].value);
}
if(((idx == 1 || idx == 3) && ans.size() == 0) || (idx == 2 && number == 0)) printf("NA\n");
}
return 0;
}

##PAT-1154
愣是题目看了半天没看懂我佛了呀,不过这里应该要学会set这个强大的工具用法,这个迭代器可以用来去重排序哦。

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdio>
struct note
{
int t1,t2;
};
using namespace std;
int main(){
int N,M;
int K;
scanf("%d %d",&N,&M);
vector<note> v(N);
for(int i =0;i<M;i++){
scanf("%d %d",&v[i].t1,&v[i].t2);
}
scanf("%d",&K);
for(int i = 0;i<K;i++){
int num =0;
bool flag = true;
int a[10010]={0};
set<int> s;
for(int j = 0;j<N;j++){
scanf("%d",&a[j]);
s.insert(a[j]);
}
for(int j =0;j<M;j++){
if(a[v[j].t1] == a[v[j].t2]){
flag = false;
break;
}
}
if(!flag){
printf("No\n");
}else{
printf("%lu-coloring\n",s.size());
}
}
return 0;
}

PAT-1155

树,dfs

难点:题目太难读懂了。
利用dfs来读出每个从右到左到leaf

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
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
int a[1010],n,isMax =1,isMin =1;
vector<int> v;
void dfs(int index){
if((index * 2) > n && (index*2+1) > n){
if(index <= n){
for(int i = 0;i<v.size();i++){
printf("%d%c",v[i],i != v.size()-1 ? ' ':'\n');
}
}
}else{
v.push_back(a[index * 2 +1]);
dfs(index * 2 +1);
v.pop_back();
v.push_back(a[index*2]);
dfs(index * 2);
v.pop_back();
}
}

int main(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
scanf("%d",&a[i]);
}
v.push_back(a[1]);
dfs(1);
for(int i = 2;i<=n;i++){
if(a[i/2] < a[i]) isMax = 0;
if(a[i/2] > a[i]) isMin = 0;
}
if(isMin){
printf("Min Heap\n");
}else{
printf("%s",isMax == 1 ? "Max Heap\n" : "Not Heap\n");
}
return 0;
}

##PAT-1148

狼人杀,遍历假设两个人说谎,用a数组记录的是狼人还是好人,然后遍历v数组,进行对比,说谎就将lies数组加一,v*a可以判断是否和实际情况相符。

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<cmath>
using namespace std;

int main(){
int n;
cin >> n;
vector<int> v(n+1);
for(int i=1;i<n+1;i++) cin >> v[i];
for(int i=1;i<n+1;i++){
for(int j=i+1;j<n+1;j++){
vector<int> lies,a(n+1,1);
a[i] = a[j] = -1;
for(int m = 1;m<n+1;m++){
if(v[m]*a[abs(v[m])] < 0) lies.push_back(m);
}
if((lies.size() == 2) && (a[lies[0]]+ a[lies[1]] == 0)){
cout << i << ' ' << j;
return 0;
}
}
}
cout << "No Solution";
return 0;
}

PAT-1149

么得办法最后还是看柳神的代码。。还又因为循环参数的问题又弄错了。自己写的超时了,应该研究下为什么超时。。

研究后发现,思考角度的不同,我把N作为循环变量而N的基数很大,柳神将M作为查找的根据,利用map方便快速的找到其对应的map。

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;


int main(){
int N,M;
scanf("%d %d",&N,&M);
map<int,vector<int> > m;
int t1,t2;
for(int i=0;i<N;i++){
scanf("%d %d",&t1,&t2);
m[t1].push_back(t2);
m[t2].push_back(t1);
}
for(int i =0;i<M;i++){
int K,flag=0,a[100000] = {0};
scanf("%d",&K);
vector<int> v(K);
for(int j=0;j<K;j++){
scanf("%d",&v[j]);
a[v[j]] = 1;
}
for(int j = 0;j<v.size();j++){
for(int f=0;f<m[v[j]].size();f++){
if(a[m[v[j]][f]] == 1) flag = 1;
}
}
printf("%s\n",flag ? "No" : "Yes");
}
}

##PAT-1150
这是一道我靠着自己就ac的题目,我感动了。。。。
比较关键的个人觉得是利用set做到去重复。

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
#include<iostream>
#include<algorithm>
#include<vector>
#include<set>
#include<map>
#include<cstring>
using namespace std;
int main(){
int v[210][210];
memset(v,0,sizeof(v));
int N,M;
scanf("%d %d",&N,&M);
for(int i = 1;i<M+1;i++){
int a,b,c;
scanf("%d %d %d",&a,&b,&c);
v[a][b] = c;
v[b][a] = c;
}
int K;
scanf("%d",&K);
map<int,vector<int> > s;
int t;
for(int i = 1;i<K+1;i++){
int m;
scanf("%d",&m);
for(int j = 0;j<m;j++){
scanf("%d",&t);
s[i].push_back(t);
}
}
int min = 999999;
int flag = 0;
for(int i = 1;i<K+1;i++){
int distance = 0;
bool tim = false;
set<int> f;
int a,b;
f.insert(s[i][0]);
for(int j = 0;j<s[i].size()-1;j++){
a = s[i][j];b = s[i][j+1];
if(v[a][b] != 0){
distance += v[a][b];
f.insert(a);
}else{
tim = true;
}
}
if((f.size() < N && !tim) || (f.size() == N && s[i][0] != s[i][s[i].size()-1])){
printf("Path %d: %d (Not a TS cycle)\n",i,distance);
}else if(s[i].size()-1 == N && !tim){
printf("Path %d: %d (TS simple cycle)\n",i,distance);
}else if(!tim){
printf("Path %d: %d (TS cycle)\n",i,distance);
}else{
printf("Path %d: NA (Not a TS cycle)\n",i);
}
if(distance < min && f.size() == N && s[i][0] == s[i][s[i].size()-1] && !tim){
min = distance;
flag = i;
}
}
printf("Shortest Dist(%d) = %d",flag,min);
return 0;
}