目录
1069 The Black Hole of Numbers （20 分）（数组处理）
1070 Mooncake （25 分）（排序一下就好）
1071 Speech Patterns （25 分）（字符串处理+细节问题）
1072 Gas Station （30 分）（dijkstra）
1069 The Black Hole of Numbers （20 分）（数组处理）
【题意】输入4位数，最大值与最小值相减，循环操作，最后差为6174 或 0 时结束循环
【分析】其实好简单的一道题啊... 我不知道为什么做了那么久
用了字符数组 定义了好多函数 还一直找不出来错误改不到满分
但是其实一个数组一个循环就好了啊...
菜死了
【代码】
#include<bits/stdc++.h>
using namespace std;int main()
{int n;scanf("%d",&n);int num[4];while(1){num[0]=n%10;n/=10;num[1]=n%10;n/=10;num[2]=n%10;num[3]=n/10;sort(num,num+4);int a=0,b=0;for(int i=0;i<4;++i)a=a*10+num[3-i];for(int i=0;i<4;++i)b=b*10+num[i];int x=a-b;printf("%04d - %04d = %04d\n",a,b,x);if(x==6174 || x==0)break;n=x;}
}1070 Mooncake （25 分）（排序一下就好）
【分析】求花费最小即可；数组排序一下然后处理
【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e3+10;
struct node{double kg,yuan;double x;
}a[maxn];
bool cmp(node a,node b){return a.x>b.x;}int n,D;
int main()
{scanf("%d%d",&n,&D);for(int i=0;i<n;++i)scanf("%lf",&a[i].kg);for(int i=0;i<n;++i)scanf("%lf",&a[i].yuan);for(int i=0;i<n;++i) a[i].x=a[i].yuan/a[i].kg;sort(a,a+n,cmp);double ans=0;for(int i=0;i<n;++i){if(a[i].kg<=D)ans+=a[i].yuan;else { ans+=a[i].x*D; break;} D-=a[i].kg;}printf("%.2lf\n",ans);
}1071 Speech Patterns （25 分）（字符串处理+细节问题）
【题意】统计单词数目（字母+数字组成）且输出出现次数最多的字母（小写输出），若有多个则输出字母序最小的那个
【分析】map存一下~ 然后注意就是，不是只有空格才不合法，如果两个字母或数字之间存在其他字符的话 也是不行的
比如输入[0-9 A-Z a-z] 输出应该是 a 2
【代码】
#include<bits/stdc++.h>
using namespace std;int main()
{string s;getline(cin,s);map<string,int>mp;mp.clear();int i=0;while(s[i]!='\0'){string str="";while((isalpha(s[i]) || isdigit(s[i])) && s[i]!='\0')str+=s[i++];while(!isalpha(s[i]) && !isdigit(s[i])){i++;if(s[i]=='\0')break;}// cout<<"str="<<str<<endl;int len=str.size();string ss="";for(int i=0;i<len;++i){if(!isdigit(str[i]) && !isalpha(str[i]))continue;if(isupper(str[i]))str[i]=tolower(str[i]);ss+=str[i];}// cout<<"ss="<<ss<<endl;if(ss!="")mp[ss]++;}int maxn=-1;string ans="";map<string,int>::iterator it;for(it=mp.begin();it!=mp.end();++it){ if(maxn< it->second)maxn=it->second,ans=it->first; else if(maxn==it->second)if(ans>it->first)ans=it->first;}cout<<ans;printf(" %d\n",maxn);
}1072 Gas Station （30 分）（dijkstra）
【题意】给出村庄数量、加油站数量、道路数量及最大路长，求加油站到所有村庄距离最小值的最大值（A gas station has to be built at such a location that the minimum distance between the station and any of the residential housing is as far away as possible.）和距离的平均值；
【分析】将加油站的编号从n开始编号进行下标统一，用dijkstra求出每个点的单源最短路径取最小值和平均值
【代码】
#include<bits/stdc++.h>
using namespace std;const int maxn=1e3+20;//这里大一点，N+M
const int inf=0x3f3f3f3f;
int e[maxn][maxn];
int dis[maxn],book[maxn];
int n,m,k,d;void dijkstra(int x)
{memset(dis,inf,sizeof(dis));memset(book,0,sizeof(book));dis[x+n]=0;for(int i=1;i<=m+n;++i){int now=-1;int mind=inf;for(int j=1;j<=m+n;++j){if(!book[j] && dis[j]<mind)mind=dis[j],now=j;} if(now==-1)break;book[now]=1;for(int j=1;j<=m+n;++j){if(!book[j] && dis[j]>dis[now]+e[now][j])dis[j]=dis[now]+e[now][j];}}
}int main()
{scanf("%d%d%d%d",&n,&m,&k,&d);memset(e,inf,sizeof(e));for(int i=0;i<k;++i){string s1,s2;int x,s11,s22;cin>>s1>>s2;scanf("%d",&x);if(s1[0]=='G')s11=stoi(s1.substr(1))+n;else s11=stoi(s1);if(s2[0]=='G')s22=stoi(s2.substr(1))+n;else s22=stoi(s2);e[s11][s22]=e[s22][s11]=x;}int minn=0;//最短路，是0！！！因为求最短路的最大值int sum=0;//总距离int f=0;//标记 int id;//indexfor(int i=1;i<=m;++i){dijkstra(i);f=0;int mind=inf,sum1=0;for(int j=1;j<=n;++j){if(dis[j]>d){sum1=-1;break;}sum1+=dis[j];mind=min(mind,dis[j]);}if(sum1!=-1){f=1;if(mind>minn)minn=mind,id=i,sum=sum1;else if(mind==minn && sum1<sum)sum=sum1,id=i;}// cout<<i<<","<<minn<<endl;}if(!f)puts("No Solution");elseprintf("G%d\n%.1lf %.1lf\n",id,minn*1.0,sum*1.0/n);return 0;
}