PAT 1001-1004
2021-01-13 本文已影响0人
YellowTag
1001 A+B Format
分析:
基础题
在处理正负号问题上要注意下，可以借鉴计算机组成原理中浮点数符号的处理的思想——单独讨论符号
代码:
/*
Author:HWL
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
int a,b;
cin>>a>>b;
int c = abs(a+b);
//处理digits
/*
1.转成字符串 使用string的相关函数
2.手动专成字符串
*/
//1.使用string相关函数
string str = to_string(c);
if(a+b<0)
cout<<"-";
int len = str.size();
for(int i=0;i<len%3;i++)
cout<<str[i];
if(len%3>0&&len>3)
cout<<",";
for(int i=0;i<len-len%3;i++)
{
cout<<str[i+len%3];
if((i+1)%3==0&&(i+len%3)!=len-1)
cout<<",";
}
//2.手动转
// char str[30];
// int cnt = 0;
// int x = 0;
// if(c==0)
// {
// cout<<0<<endl;
// return 0;
// }
// while(c)
// {
// str[cnt++] = c%10+'0';
// if((x+1)%3==0&&c/10!=0)
// str[cnt++]=',';
// x++;
// c/=10;
// }
// char ans[30];
// int j=0;
// for(int i=cnt-1;i>=0;i--)
// ans[j++]=str[i];
// ans[j]='\0';
// if(a+b<0)
// cout<<"-";
// cout<<ans<<endl;
return 0;
}
1002 A+B for Polynomials
分析:
基础题
注意项系数为0的情况，也注意浮点数判0的方法(这题==也可以过)
代码:
/*
Author:HWL
*/
#include<bits/stdc++.h>
using namespace std;
int main(){
//下标是幂，值为系数
double A[2001];
double B[2001];
int vis[2001]={0};//标志哪个下标有效
int sum = 0;
int k;
cin>>k;
while(k--)
{
int expo;
double coef;
cin>>expo>>coef;
A[expo]=coef;
if(!vis[expo])
sum++;
vis[expo]=1;
}
cin>>k;
while(k--)
{
int expo;
double coef;
cin>>expo>>coef;
B[expo]=coef;
if(!vis[expo])
sum++;
else{
if(fabs(A[expo]+B[expo])<0.000000001)
sum--;
}
vis[expo]=1;
}
cout<<sum;
for(int i=2000;i>=0;i--)
{
if(vis[i])
{
if(fabs(A[i]+B[i])<0.000000001)
continue;
cout<<" "<<i<<" ";
printf("%.1f",A[i]+B[i]);
}
}
return 0;
}
1003 Emergency
分析
考察点:图的遍历(DFS)
图的存储:邻接矩阵
这题用DFS就可以过，有几个地方注意:
1.用剪枝的方式，快速筛掉不必要的递归
2.如果想要进一步优化时间，可以用邻接表来存储图
3."在相同最短路径下找最大的"类型题可以用的技巧：
请看代码递归原子操作的部分
时间复杂度:O(n2)
空间复杂度:O(n2)
代码
/*
Author:HWL
*/
#include<bits/stdc++.h>
using namespace std;
int mincost = 100000000;
int maxres = 0;
int sum = 0;
int resteam[501];
int mat[501][501];//邻接矩阵
int vis[501] = {0};
void dfs(int start,int end,int cost,int resnum)
{
if(start==end)
{
if(cost==mincost)
{
//相同最短路径下找最大的救援，并且最短路的种数加一
sum++;
maxres = max(maxres,resnum);
}
else if(cost<mincost)
{
//最短路发生更新，则种数和最大救援都要更新
sum = 1;
mincost = cost;
maxres = resnum;
}
}
for(int i=0;i<500;i++)
{
if(mat[start][i]!=100000000&&!vis[i])
{
if(mat[start][i]+cost>mincost)
continue; //这里做一个剪枝，不然会有一个case超时
vis[i]=1;
dfs(i,end,cost+mat[start][i],resnum+resteam[i]);
vis[i]=0; //注意回溯这一步
}
}
}
int main(){
for(int i=0;i<501;i++)
for(int j=0;j<501;j++)
mat[i][j]=100000000;
int n,m,c1,c2;
cin>>n>>m>>c1>>c2;
for(int i=0;i<n;i++)
cin>>resteam[i];
for(int i=0;i<m;i++)
{
int f,t,c;//from,to,cost
cin>>f>>t>>c;
mat[f][t]=c;
mat[t][f]=c;//注意是无向图
}
dfs(c1,c2,0,resteam[c1]);
cout<<sum<<" "<<maxres<<endl;
}
1004 Counting Leaves
分析
考察点:
树的层次遍历，使用BFS即可
基础题
代码:
/*
Author:HWL
*/
#include<bits/stdc++.h>
using namespace std;
struct node{
vector<int> child;
};
int main(){
int n,m;
cin>>n>>m;
if(n==0)
return 0;
vector<node> nodes(100);
while(m--)
{
int root,num;
cin>>root>>num;
while(num--)
{
int tmp2;
cin>>tmp2;
nodes[root].child.push_back(tmp2);
}
}
vector<int> ans;
int leaf_num=0; //某层的叶子节点数目
//BFS
queue<node> q;
q.push(nodes[1]);
int floor = 1; //第1层
int number = 1; //某层的节点数
while(!q.empty())
{
node tmp = q.front();
q.pop();
number--;
if(tmp.child.size()==0)
{
leaf_num++;
}
for(int i=0;i<tmp.child.size();i++)
{
q.push(nodes[tmp.child[i]]);
}
if(number==0)
{
floor++; //切换到下一层
ans.push_back(leaf_num);
leaf_num=0;
number = q.size();
}
}
cout<<ans[0];
for(int i=1;i<ans.size();i++)
cout<<" "<<ans[i];
return 0;
}
