-
数据结构与算法训练：第二十七、二十八弹
1. 知识点总结
昨天毕业实习开会耽误一下进度了，好消息是硬件课设成功显示出波形了，坏消息是毕业实习又要急吼吼展开——
这两天做的题目都是基础，数据结构涉及较少，但是总是卡在精度上，应该是这个问题⑧，就挺头疼的。
昨天
耗时：2h40min
得分：96/100
知识点：Dijkstra、字符串、链表、科学计数法和简单模拟
题目 难度 知识点 1072 Gas Station 🎯🎯😅 Dijkstra 1073 Scientific Notation 🎯 字符串处理 1074 Reversing Linked List 🎯 链表 1075 PAT Judge 🎯 简单模拟 今天
耗时：1h40min
得分：98/100
知识点：DFS+剪枝、字符串处理、贪心和精度问题（也许叫英语阅读能力更妥当）
题目 难度 知识点 1068 Find More Coins 🎯🎯 DFS+剪枝 1069 The Black Hole of Numbers 🎯 字符串 1070 Mooncake 🎯|✨ 贪心+精度 1071 Speech Patterns 🎯 字符串处理 2. 分题题解
2.1 1072 Gas Station
最短路径，不知道为什么卡了一个测试点过不去,看了柳神的代码也没有找到问题所在，闹心ing,如果有好心人希望指点一下(￣▽￣)*
#includeusing namespace std; const int inf=999999999; int N,M,K,Ds; vector<vector<int> >graph; vector<bool>vis; vector<int>dis; string a,b; int aa,bb,d; int ans_id=-1; double ans_min_avg=inf; double ans_max_min=-1; void Dij(int st){ fill(vis.begin(),vis.end(),false); fill(dis.begin(),dis.end(),inf); dis[st]=0; while(1){ int u=-1; int min_dis=inf; for(int i=1;i<=N+M;i++){ if(!vis[i]&&dis[i]<min_dis){ min_dis=dis[i]; u=i; } } if(u==-1){ break; } vis[u]=true; for(int v=1;v<=N+M;v++){ if(!vis[v]){ if(dis[v]>dis[u]+graph[u][v]){ dis[v]=dis[u]+graph[u][v]; } } } } double mini=inf; double sum=0; for(int i=1;i<=N;i++){ if(dis[i]<mini){ mini=dis[i]; }else if(dis[i]>Ds){ return; } sum+=1.0*dis[i]; } if(mini>ans_max_min){ ans_id=st; ans_max_min=mini; ans_min_avg=sum/N; }else if(mini==ans_max_min){ if(sum/N<ans_min_avg){ ans_id=st; ans_min_avg=sum/N; } } } int main(){ scanf("%d%d%d%d",&N,&M,&K,&Ds); graph.resize(1+N+M,vector<int>(1+N+M,inf)); for(int i=0;i<1+N+M;i++){ graph[i][i]=0; } vis.resize(1+N+M,false); dis.resize(1+N+M,inf); for(int i=0;i<K;i++){ cin>>a>>b>>d; if(a[0]=='G'){ aa=atoi(a.substr(1,a.length()).c_str()); aa+=N; }else{ aa=atoi(a.c_str()); } if(b[0]=='G'){ bb=atoi(b.substr(1,b.length()).c_str()); bb+=N; }else{ bb=atoi(b.c_str()); } graph[aa][bb]=min(graph[aa][bb],d); graph[bb][aa]=graph[aa][bb]; } for(int i=1+N;i<1+N+M;i++){ Dij(i); } if(ans_id==-1){ printf("No Solution"); }else{ printf("G%d\n",ans_id-N); printf("%.1f %.1f",ans_max_min,ans_min_avg); } return 0; } - 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
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
2.2 1073 Scientific Notation
字符串处理，需要一点耐心
#includeusing namespace std; //科学计数法-数学计数 string str,num1,num2,ans=""; int ep; void Solution(){ int len=str.length(); if(str[0]=='-'){ ans+=str[0]; } int posPoint=str.find('.'); int posE=str.find('E'); num1=str.substr(1,posPoint-1); num2=str.substr(posPoint+1,posE-posPoint-1); ep=atoi(str.substr(posE+1,len).c_str()); int len1=num1.length(); int len2=num2.length(); //下面开始操作 if(ep>0){ //小数点右移 ans+=num1; int i; for(i=0;i<ep;i++){ if(i<len2){ ans+=num2[i]; }else{ ans+='0'; } } for(i=ep;i<len2;i++){ if(i==ep)ans+='.'; ans+=num2[i]; } }else{ //左移 string num; reverse(num2.begin(),num2.end()) ; num=num2; int cnt=0; int i; for(i=len1-1;i>=0;i--){ if(cnt==-ep){ break; }else{ num+=num1[i]; cnt++; } } if(cnt==-ep){ num+="."; bool flag=false; for(;i>=0;i--){ num+=num1[i]; flag=true; } if(!flag){ num+='0'; } }else{ while(1){ cnt++; num+='0'; if(cnt==-ep){ break; } } num+=".0"; } reverse(num.begin(),num.end()); ans+=num; } printf("%s",ans.c_str()); } int main(){ cin>>str; Solution(); return 0; } - 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
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
2.3 1074 Reversing Linked List
基础题，按分组反转链表
#includeusing namespace std; struct Node{ int addr; int val; int nxt; }; vector<Node>nodes; map<int,Node>mp; Node temp; int head,N,K; int main(){ scanf("%d%d%d",&head,&N,&K); for(int i=0;i<N;i++){ scanf("%d%d%d",&temp.addr,&temp.val,&temp.nxt); mp[temp.addr]=temp; } while(head!=-1){ nodes.push_back(mp[head]); head=mp[head].nxt; } int len=nodes.size(); for(int i=0;i<len/K;i++){ reverse(nodes.begin()+i*K,nodes.begin()+(i+1)*K); } //reverse(nodes.begin()+len/K*K,nodes.end()); for(int i=0;i<len;i++){ if(i){ printf("%05d\n",nodes[i].addr); } printf("%05d %d ",nodes[i].addr,nodes[i].val); } printf("-1"); return 0; } - 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
2.4 1075 PAT Judge
简单模拟【吐槽我自己：好敷衍的题解~】
对于从来没有成功编译的队员不显示
对于一个队员而言，只要他显示，则所有提交过的题需要给分，只要没提交过的标记为’-’
#includeusing namespace std; int N,K,M; int uid,pid,s; vector<int>full_score; struct User{ vector<int>score; int total=0; int id; bool ok=false; int cnt=0; }; vector<User>users,ans; bool cmp(User a,User b){ if(a.total!=b.total){ return a.total>b.total; }else if(a.cnt!=b.cnt){ return a.cnt>b.cnt; }else{ return a.id<b.id; } } int main(){ scanf("%d%d%d",&N,&K,&M); full_score.resize(K+1); users.resize(N+1); for(int i=0;i<=N;i++){ users[i].id=i; users[i].score.resize(K+1,-2); } for(int i=1;i<=K;i++){ scanf("%d",&full_score[i]); } for(int i=0;i<M;i++){ scanf("%d%d%d",&uid,&pid,&s); if(s>=0){ users[uid].ok=true; } users[uid].score[pid]=max(users[uid].score[pid],s); } for(int i=0;i<=N;i++){ if(users[i].ok){ for(int j=1;j<=K;j++){ if(users[i].score[j]>=0){ users[i].total+=users[i].score[j]; if(users[i].score[j]==full_score[j]){ users[i].cnt++; } } } ans.push_back(users[i]); } } sort(ans.begin(),ans.end(),cmp); int rk=1; for(int i=0;i<ans.size();i++){ if(i&&ans[i].total!=ans[i-1].total){ rk=i+1; } printf("%d %05d %d",rk,ans[i].id,ans[i].total); for(int j=1;j<=K;j++){ if(ans[i].score[j]==-2){ printf(" -"); }else if(ans[i].score[j]>=0){ printf(" %d",ans[i].score[j]); }else{ printf(" 0"); } } printf("\n"); } return 0; } - 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
- 68
- 69
- 70
- 71
- 72
- 73
2.5 1068 Find More Coins
DFS基础题，主要难点在于剪枝，最后一个测试点比较特殊，需要特判（即，当本身总和小于M时，没必要继续DFS，直接返回“No solution”）。
#includeusing namespace std; int N,M; vector<int>coins; bool flag=false; vector<int>ans,temp; vector<bool>vis; void dfs(int id,int sum,vector<int>temp){ vis[id]=true; sum+=coins[id]; temp.push_back(coins[id]); if(flag){ return; } if(sum==M){ flag=true; ans=temp; }else if(sum<M&&id+1<N){ for(int i=id+1;i<N;i++){ if(!vis[i]){ dfs(i,sum,temp); } } } //回溯 vis[id]=false; temp.pop_back(); } int sum=0; int main(){ scanf("%d%d",&N,&M); coins.resize(N); vis.resize(N,false); //提前剪枝 for(int i=0;i<N;i++){ scanf("%d",&coins[i]); sum+=coins[i]; } if(sum<M){ printf("No Solution"); return 0; } sort(coins.begin(),coins.end()); for(int i=0;i<N;i++){ if(coins[i]<=M){ dfs(i,0,temp); } if(flag){ break; } } if(!flag){ printf("No Solution"); }else{ for(int i=0;i<ans.size();i++){ if(i){ printf(" "); } printf("%d",ans[i]); } } return 0; } - 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
2.6 1069 The Black Hole of Numbers
这题主要是停止迭代的条件：
- 当结果为6174
- 当被减数所有位数上的数字一致
考察字符串和数字的转化，
to_string不能用真的好伤人。#includeusing namespace std; string a,b,c; int temp; bool cmp(char a,char b){ return a>b; } bool isSame(string a){ for(int i=1;i<4;i++){ if(a[i]!=a[0]){ return false; } } return true; } int main(){ cin>>c; int len=c.length(); for(int i=len;i<4;i++){ c="0"+c; } while(1){ sort(c.begin(),c.end()); b=c; sort(c.begin(),c.end(),cmp); a=c; temp=atoi(a.c_str())-atoi(b.c_str()); printf("%s - %s = %04d\n",a.c_str(),b.c_str(),temp); if(temp==6174||isSame(a)){ break; } //temp转化成c c=""; while(temp){ c+=temp%10+'0'; temp/=10; } len=c.length(); for(int i=len;i<4;i++){ c+="0"; } reverse(c.begin(),c.end()); } return 0; } - 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
2.7 1070 Mooncake
简单贪心，排序然后尽可能选择单价高的产品销售。
非常恶心的一道题，emmm把数量
ton的类型改成int就卡死在第二个测试点过不去，题目中==positive inventory amounts (in thousand tons)==真的超有迷惑性……inventory不是integer,注意审题，样例也在这里挖坑了#includeusing namespace std; int N,D; struct Cake{ double ton; double price; double p; }; double temp,ans=0; int sum; vector<Cake>cakes; bool cmp(Cake a,Cake b){ return a.p>b.p; } //不知道是不是精度问题 int main(){ scanf("%d%d",&N,&D); cakes.resize(N); for(int i=0;i<N;i++){ scanf("%lf",&cakes[i].ton); } for(int i=0;i<N;i++){ scanf("%lf",&cakes[i].price); cakes[i].p=cakes[i].price/cakes[i].ton; } sort(cakes.begin(),cakes.end(),cmp); sum=D; for(int i=0;i<N;i++){ if(sum>=cakes[i].ton){ ans+=cakes[i].price; sum-=cakes[i].ton; }else{ ans+=cakes[i].p*sum; sum=0; } if(sum<=0){ break; } } printf("%.2f",ans); return 0; } - 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
2.8 1071 Speech Patterns
字符串处理，切分字符后统计出现次数最多的字符并输出，不区分大小写~
#includeusing namespace std; string str; vector<string>words; string ans; int max_cnt=0; int main(){ getline(cin,str); str+=" "; //首先切词 string temp=""; for(int i=0;i<str.length();i++){ if(str[i]<='Z'&&str[i]>='A'){ temp+=str[i]-'A'+'a'; }else if(!(str[i]<='z'&&str[i]>='a'||str[i]>='0'&&str[i]<='9')){ if(temp!=""){ words.push_back(temp); temp=""; } }else{ temp+=str[i]; } } sort(words.begin(),words.end()); max_cnt=0; int cnt=1;temp=words[0]; for(int i=1;i<words.size();i++){ if(words[i]==temp){ cnt++; }else{ if(cnt>max_cnt){ max_cnt=cnt; ans=temp; } cnt=1; temp=words[i]; } } if(cnt>max_cnt){ max_cnt=cnt; ans=temp; } printf("%s %d",ans.c_str(),max_cnt); return 0; } - 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
3.参考资料
柳神的1070和1072
-
相关阅读:
制药企业液体制剂生产设备管理利器：中央设备状态监控系统CMS
日语等级J.TEST的自测卷
Thinkphp 5.0.24变量覆盖漏洞导致RCE分析
Shell动态条进度
python使用pandas中的read_csv函数读取csv数据为dataframe、使用map函数和strip函数去除指定字符串数据列的左右空格
Python Setuptools的 setup.py
机组运行约束对机组节点边际电价的影响研究（Matlab代码实现）
初识Java 18-2 泛型
【C++】之const
多主复制下处理写冲突(4)-多主复制拓扑
- 原文地址：https://blog.csdn.net/qq_45751990/article/details/126530059
