1. 题目总结
然后重新注册了一个账号重新开始刷，主要是如果不是模拟为背景的话，俺的效率真的一言难尽😶；可能刷过一次叭，还挺顺利的今天，一扫期末阴影啊哈哈哈
| 题目传送门 | 难度 | 知识点 |
|---|---|---|
| 1001 | 🎈 | 字符串 |
| 1002 | 🎈 | 字符串+STL |
| 1003 | 🎈🎈 | Dijkstra |
| 1004 | 🎈🎈 | 二叉树 |
2. 分题题解
2.1 A+B Format
送分题,字符串处理
#include<bits/stdc++.h>
using namespace std;
int a ,b,sum;
string nans="";
bool flag=false;
int main(){
scanf("%d%d",&a,&b);
sum=a+b;
if(sum<0){
flag=true;
sum=-sum;
}
string ans=to_string(sum);
//输出答案
int len=ans.length();
int cnt=0;
for(int i=len-1;i>=0;i--){
cnt++;
nans+=ans[i];
if(cnt%3==0&&i){
nans+=",";
}
}
reverse(nans.begin(),nans.end());
if(flag){
printf("-");
cout<<nans;
}else{
cout<<nans;
}
return 0;
}2.2 A+B for Polynomials
多项式英文：Polynomials
也不卡时间空间，起始可以无脑开数组
#include<stdio.h>
#include<vector>
#include<set>
#include<map>
using namespace std;
map<int,double>pa,pb,pc;
set<int>Exps;
vector<int>ans_exps_sort;
int k,exp;
double num;
int main(){
scanf("%d",&k);
for(int i=0;i<k;i++){
scanf("%d%lf",&exp,&num);
pa[exp]=num;
Exps.insert(exp);
}
scanf("%d",&k);
for(int i=0;i<k;i++){
scanf("%d%lf",&exp,&num);
pb[exp]=num;
Exps.insert(exp);
}
//接下来是
for(set<int>::iterator it=Exps.begin();it!=Exps.end();it++){
if(pa.find(*it)==pa.end()){
pc[*it]=pb[*it];
ans_exps_sort.push_back(*it);
}else if(pb.find(*it)==pb.end()){
pc[*it]=pa[*it];
ans_exps_sort.push_back(*it);
}else{
//下面就是加
if(pa[*it]+pb[*it]==0){
continue;
} else{
pc[*it]=pa[*it]+pb[*it];
ans_exps_sort.push_back(*it);
}
}
}
int len=ans_exps_sort.size();
printf("%d",len);
for(int i=len-1;i>=0;i--){
printf(" %d %.1f",ans_exps_sort[i],pc[ans_exps_sort[i]]);
}
return 0;
}2.3 Emergency
Dijkstra比较经典的题目，变式体现在每更新需要添加上一个结点pre的信息，按照题目要求回溯pre即可得到答案
#include<bits/stdc++.h>
using namespace std;
const int maxn=501;
const int inf=INT_MAX;
int N,M,st,ed;//城市个数、道路个数、起始、终止
vector<int>city;//存每个城市的人数
//输出最短路径的个数，输出最多可以找多少人
int dis[maxn];
int graph[maxn][maxn];
bool vis[maxn]={false};
vector<vector<int> >pre;
int a,b,d;
void Dijkstra(int st,int ed){
fill(dis,dis+N,inf);
dis[st]=0;//起点到起点的距离最短
int u,min_dis;
for(int i=0;i<N;i++){
u=-1;
min_dis=inf;
for(int j=0;j<N;j++){
if(!vis[j]&&dis[j]<min_dis){
u=j;
min_dis=dis[j];
}
}
if(u==-1){
return;
}
vis[u]=true;
//更换中继节点
for(int v=0;v<N;v++){
if(!vis[v]&&graph[u][v]!=inf){
if(dis[u]+graph[u][v]<dis[v]){
pre[v].clear();
pre[v].push_back(u);
dis[v]=dis[u]+graph[u][v];//优化
}else if(dis[v]==dis[u]+graph[u][v]){
pre[v].push_back(u);
}
}
}
}
}
int num=0,maxp=0;//最短路径个数、最大人头
//回溯前面的道路
void dfs(int id,int people){
if(id==st){
num++;
if(people>maxp){
maxp=people;
}
}else{
for(int i=0;i<pre[id].size();i++){
dfs(pre[id][i],people+city[pre[id][i]]);
}
}
return;
}
int main(){
scanf("%d%d%d%d",&N,&M,&st,&ed);
city.resize(N);
pre.resize(N);
for(int i=0;i<N;i++){
scanf("%d",&city[i]);
}
fill(graph[0],graph[0]+maxn*maxn,inf);
for(int i=0;i<M;i++){
scanf("%d%d%d",&a,&b,&d);
graph[a][b]=d;
graph[b][a]=d;
}
Dijkstra(st,ed);
dfs(ed,city[ed]);
printf("%d %d",num,maxp);
return 0;
}2.4 Counting Leaves
数组版本的二叉树层次遍历，实际上比上一题简单
#include<bits/stdc++.h>
using namespace std;
int N,M;//N个结点，M个有子孙的结点
bool isC[100]={false};
vector<vector<int> >nodes(100);
int level[100]={0};
int cnts[100]={0};
int k,id;
int sum=1;//记录总层数
void levelTravel(int root){
queue<int>q;
q.push(root);
level[root]=1;
while(!q.empty()){
int top=q.front();
sum=max(level[top],sum);
q.pop();
if(nodes[top].size()==0){
cnts[level[top]]++;
}
for(int i=0;i<nodes[top].size();i++){
q.push(nodes[top][i]);
level[nodes[top][i]]=level[top]+1;
}
}
}
int temp;
int main(){
scanf("%d%d",&N,&M);
if(N==0){
return 0;
}
for(int i=0;i<M;i++){
scanf("%d%d",&id,&k);
for(int j=0;j<k;j++){
scanf("%d",&temp);
nodes[id].push_back(temp);
isC[temp]=true;
}
}
levelTravel(1);
for(int i=1;i<=sum;i++){
if(i!=1)printf(" ");
printf("%d",cnts[i]);
}
return 0;
} 3. 参考资料
- 《算法笔记》Dij
