算法训练30

编程练习 机考
算法与数据结构
发布日期:   2022-07-26
更新日期:   2022-07-26
文章字数:   2.4k
阅读时长:   13 分
阅读次数:  

1. 知识点总结

90/100

这次卡在第一题，主要是考察思维（如何遍历确定边界来减少时间复杂度）

题目 难度 知识点
Forever 🎯🎯 时间复杂度+数组
Merging Linked Lists 🎯 链表
Postfix Expression 🎯 二叉树后序遍历
Dijkstra Sequence 🎯 Dij算法

2. 分题题解

2.1 Forever

第一版，只过了一个测试点，估计是只过了样例，思路如代码，自认为注释还是很容易看懂的

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A;
ll m,n;
int K; 
int N;
//最大公因数
ll gcd(ll a,ll b){
	ll temp;
	while(a){
		temp=a;
		a=b%a;
		b=temp;
	}
	return b;
} 
bool flag=false; 
int tail;
void dfs(ll num,int len,ll sum,int tlen,ll tsum){
	//num是当前的数字，len是当前数字长度,sum是当前数字各位之和 
	//printf("当前数字：%lld 长度：%d 和：%lld 目标长度：%d 目标和：%lld\n",num,len,sum,tlen,tsum);
	if(len>tlen||sum>tsum){
		return;
	}
	if(sum<tsum&&len>=tlen){
		return;
	}
	if(sum==tsum&&len==tlen){
		printf("%lld %lld",n,num);
		for(int i=0;i<tail;i++){
			printf("9");
		}
		printf("\n");
	}else{
		for(int i=0;i<=9;i++){
			//剪枝
			if((tlen-len-1)*9+sum+i<tsum)continue; 
			if(sum+i<=tsum){
				dfs(num*10+i,len+1,sum+i,tlen,tsum);
			}
		}
	}
	return ;
}

int main(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		flag=false;
		scanf("%d%lld",&K,&m);
		printf("Case %d\n",i);
		//枚举可以末尾放9的个数
		for(int tail_9=K;tail_9>=1;tail_9--){
			//首先判断能否构成一个数字
			int head=K-tail_9;
			tail=tail_9;
			if((head&&m-tail_9*9>=1&&(m-tail_9*9)/head<=9)||(head==0&&m-tail_9*9==0)){
				//如果能构成一个数字的话
				n=m+1-tail_9*9;
				ll sum=m-tail_9*9;
				if(gcd(n,m)>2){
					//输出答案
					if(head){
						for(ll j=1;j<=9;j++){
							if(j<=sum){
								dfs(j,1,j,head,sum); 
							}
						}
					}else{
						printf("%lld ",n);
						for(int c=0;c<tail;c++){
							printf("9");
						}
						printf("\n");
					}
					flag=true;
				}
			}
		}
		if(!flag){
			printf("No Solution\n");
		}
	}
	
	return 0;
}

第二版

怀疑是直接输出的时候没有考虑重复输出的情况，所以加上了限制，即用set过滤重复的样本，结果还是10/20;

稍微复习了一下结构体重载运算符的写法

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll A;
ll m,n;
int K; 
int N;
//答案
struct Ans{
	int n;
	string str;
	//重写结构体== 
	bool operator ==(const Ans a)const{
		return this->n==a.n&&this->str==a.str;
	}
	bool operator <(const Ans a)const{
		if(this->n!=a.n){
			return this->n<a.n;
		}else{
			return this->str<a.str;
		}
	}
}; 
set<Ans>ans; 
//最大公因数
ll gcd(ll a,ll b){
	ll temp;
	while(a){
		temp=a;
		a=b%a;
		b=temp;
	}
	return b;
} 
bool flag=false; 
int tail;

void dfs(ll num,int len,ll sum,int tlen,ll tsum){
	//num是当前的数字，len是当前数字长度,sum是当前数字各位之和 
	//printf("当前数字：%lld 长度：%d 和：%lld 目标长度：%d 目标和：%lld\n",num,len,sum,tlen,tsum);
	if(len>tlen||sum>tsum){
		return;
	}
	if(sum<tsum&&len>=tlen){
		return;
	}
	if(sum==tsum&&len==tlen){
		//存储答案
		Ans temp;
		temp.n=n;
		temp.str=to_string(num);
		for(int i=0;i<tail;i++){
			temp.str+="9";
		}
		ans.insert(temp);
	}else{
		for(int i=0;i<=9;i++){
			//剪枝
			if((tlen-len-1)*9+sum+i<tsum)continue; 
			if(sum+i<=tsum){
				dfs(num*10+i,len+1,sum+i,tlen,tsum);
			}
		}
	}
	return ;
}

int main(){
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		flag=false;
		scanf("%d%lld",&K,&m);
		printf("Case %d\n",i);
		//枚举可以末尾放9的个数
		for(int tail_9=K;tail_9>=1;tail_9--){
			//首先判断能否构成一个数字
			int head=K-tail_9;
			tail=tail_9;
			if((head&&m-tail_9*9>=1&&(m-tail_9*9)/head<=9)||(head==0&&m-tail_9*9==0)){
				//如果能构成一个数字的话
				n=m+1-tail_9*9;
				ll sum=m-tail_9*9;
				if(gcd(n,m)>2){
					//输出答案
					if(head){
						for(ll j=1;j<=9;j++){
							if(j<=sum){
								dfs(j,1,j,head,sum); 
							}
						}
					}else{
						Ans temp;
						temp.str="";
						temp.n=n;
						for(int c=0;c<tail;c++){
							temp.str+="9";
						}
						ans.insert(temp);
					}
					flag=true;
				}
			}
		}
		if(!flag){
			printf("No Solution\n");
		}else{
			//输出答案
			//printf("答案个数%d\n",ans.size());
			for(set<Ans>::iterator it=ans.begin();it!=ans.end();it++){
				printf("%d %s\n",(*it).n,(*it).str.c_str());
			} 
		}
	}
	return 0;
}

2.2 Merging Linked Lists

PAT和力扣最大的区别在于，输出正确即可，其实不必将链表结构实现，只需要数组替代一下，注意输出的时候对应的逻辑关系即可。

#include<bits/stdc++.h>
using namespace std;
//排序
struct Node{
	int val;
	int addr;
	int nxt;
}; 

map<int,Node>nodes;
vector<Node>list1,list2,list3;
int head1,head2,n;
int addr,val,nxt;
void Merge(vector<Node>list1,vector<Node>list2){
	int len1=list1.size(); 
	int len2=list2.size();
	int p1=0;
	int p2=len2-1;
	while(1){
		if(p1<len1){
			list3.push_back(list1[p1]);
		}
		if(p1+1<len1){
			list3.push_back(list1[p1+1]);
		}
		if(p2>=0){
			list3.push_back(list2[p2]);
		}
		p1+=2;
		p2-=1;
		if(p1>=len1&&p2<0){
			break;
		}
	}
}
int main(){
	scanf("%d%d%d",&head1,&head2,&n);
	for(int i=0;i<n;i++){
		scanf("%d%d%d",&addr,&val,&nxt);
		nodes[addr].addr=addr;
		nodes[addr].val=val;
		nodes[addr].nxt=nxt;
	}
	//遍历，得到链表 
	int p=head1;
	while(p!=-1){
//		printf("1:%d\n",nodes[p].val);
		list1.push_back(nodes[p]);
		p=nodes[p].nxt;
		
	}
	p=head2;
	while(p!=-1){
//		printf("2:%d\n",nodes[p].val);
		list2.push_back(nodes[p]);
		p=nodes[p].nxt;
		
	}
	//输出结果
	if(list1.size()>=2*list2.size()){
		Merge(list1,list2);
	}else{
		Merge(list2,list1);
	}
	//输出答案
	for(int i=0;i<list3.size();i++){
		if(i){
			printf("%05d\n",list3[i].addr);
		}
		printf("%05d %d ",list3[i].addr,list3[i].val);
	} 
	printf("-1");
	return 0;
}

2.3 Postfix Expression

这题的难点在于，对于某一个结点，如果它的值为“+”或者“-”且左节点为空，输出的时候需要特殊考虑，也就是需要将后序遍历改成前序遍历，样例中只给了“-”,所以“+”容易被忘掉(最后两个测试点)

#include<bits/stdc++.h>
using namespace std;
struct Node{
	char data[12];
	int left;
	int right;
}; 
vector<Node>nodes;
vector<bool>isChild;
int n;
void postTravel(int root){
	if(root==-1){
		return ;
	}else if((nodes[root].data[0]=='-'||nodes[root].data[0]=='+')&&strlen(nodes[root].data)==1&&nodes[root].left==-1){
		printf("(");
		printf("%s",nodes[root].data);
		postTravel(nodes[root].left);
		postTravel(nodes[root].right);
		printf(")");
	}else{
		printf("(");
		postTravel(nodes[root].left);
		postTravel(nodes[root].right);
		printf("%s",nodes[root].data);
		printf(")");
	}
}
int main(){
	scanf("%d",&n);
	nodes.resize(n+1);
	isChild.resize(n+1);
	fill(isChild.begin(),isChild.end(),false);
	for(int i=1;i<=n;i++){
		scanf("%s %d %d",nodes[i].data,&nodes[i].left,&nodes[i].right);
		if(nodes[i].left!=-1){
			isChild[nodes[i].left]=true;
		}
		if(nodes[i].right!=-1){
			isChild[nodes[i].right]=true;
		}
	}
	//找到根节点 
	int root=-1;
	for(int i=1;i<=n;i++){
		if(!isChild[i]){
			root=i;
			break;
		}
	}
	//后序遍历
	postTravel(root);
	return 0;
}

2.4 Dijkstra Sequence

这题就是DIj的板子变式，对时间复杂度抓得不是很狠，需要利用给的seq去判断，四舍五入算是做了简单的剪枝，不合法的时候直接返回false

#include<bits/stdc++.h>
using namespace std;
//Dij路径
const int inf=INT_MAX;
int Nv,Ne;
vector<vector<int>>graph; 
vector<int>seq;
int u,v,d;
bool isDijSeq(int st,int ed){
	vector<int>dis(Nv+1,inf);
	vector<bool>vis(Nv+1,false);
	dis[st]=0;
	int index=0;
	while(1){
		//printf("当前：%d 距离：%d\n",seq[index],dis[seq[index]]);
		if(index>=Nv){
			//printf("gameover\n");
			break;
		}
		int u=seq[index],min_dis=dis[u];
		for(int i=1;i<=Nv;i++){
			if(dis[i]<min_dis&&!vis[i]){
				min_dis=dis[i];
				u=i;
			}
		}
		if(u!=seq[index]){
			//printf("应该是:%d\n",u);
			return false;
		}else{
			index++;
		}
		vis[u]=true;
		//更新
		for(int v=1;v<=Nv;v++){
			if(graph[u][v]!=inf&&dis[v]>=dis[u]+graph[u][v]){
				dis[v]=dis[u]+graph[u][v];
			}
		} 
	}
	return true;
} 
int main(){
	scanf("%d%d",&Nv,&Ne);
	//初始化 
	graph.resize(Nv+1);
	seq.resize(Nv);
	for(int i=1;i<=Nv;i++){
		graph[i].resize(Nv+1);
		fill(graph[i].begin(),graph[i].end(),inf);
	}
	for(int i=0;i<Ne;i++){
		scanf("%d%d%d",&u,&v,&d);
		graph[u][v]=d;
		graph[v][u]=d;
	}
	int q;
	scanf("%d",&q);
	while(q--){
		for(int i=0;i<Nv;i++){
			scanf("%d",&seq[i]);
		}
		if(isDijSeq(seq[0],seq[Nv-1])){
			printf("Yes\n");
		}else{
			printf("No\n");
		}
	}
	return 0;
}

3. 参考资料

  1. 第一题大佬题解：PAT甲级 1160 Forever (20 分)_夜淡的博客-CSDN博客
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e4+10;

vector<pair<int, int> > res;
int needlen, n, num9;
int now;

void dfs(int len, int sum)
{
	if (len*9 < sum) return; //剪枝，加不加无所谓 
	if (len == 0)
	{
		if (sum == 0)
		{
			int temp = now;
			for (int i = 0; i < num9; i++) temp = temp*10+9;
			res.push_back(make_pair(n, temp));
		}
		return ;
	}
	if (sum < 0 || len <= 0) return ; //剪枝，加不加无所谓 
	for (int i = 0; i <= 9; i++)
	{
		if (i == 0 && len == needlen || i == 9 && len == 1) continue;
		now = now*10+i;
		dfs(len-1, sum-i);
		now = now/10;
	}
}

int main(void)
{
	int i, j, temp;
	int q; scanf("%d", &q);
	for (j = 1; j <= q; j++)
	{
		printf("Case %d\n", j);
		int k, m; scanf("%d%d", &k, &m);
		set<int> se;
		temp = m;
		for (i = 2; i <= temp; i++)
		{
			if (temp % i == 0)
			{
				se.insert(i);
				temp /= i;
				i--;
			}
		}
		if (*se.rbegin() <= 2)
		{
			printf("No Solution");
			continue;
		}
		res.clear();
		for (auto it = se.begin(); it != se.end(); ++it)
		{
			if (*it > 2)
			{
				int prime = *it;
				for (i = 1; ; i++)
				{
					n = i*prime; if (n >= m) break;
					if ((m-n-8)%9 != 0) continue;
					num9 = (m-n-8)/9+1;
					int len = k-num9, sum = m-num9*9; //将问题转换为长度为len, 数字和为sum的问题
					needlen = len;
					dfs(len, sum);
				}
			}
		}
		sort(res.begin(), res.end());
		if (res.size() == 0) printf("No Solution\n");
		else
		{
			for (i = 0; i < res.size(); i++)
			{
				printf("%d %d\n", res[i].first, res[i].second);
			}
		}
	}
}
文章作者: Gao
文章链接: https://ghy0202.github.io/2022/07/26/suan-fa-xun-lian-30/
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 Gao !
编程练习 机考
赏
评论
  目录