PAT-List

生活艰难。。。

单词记录

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

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()

##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;
}