L2-029 特立独行的幸福

题目 L2-029 特立独行的幸福

思路分析

• 每个数字 i 进行 DFS 路径模拟，记录所有中间值。
• 如果最后成功到达 1，说明是幸福数。
• 如果其他幸福数出现在路径中，则这些中间值是依附于 i 的。
• 不依附于他人的幸福数就是特立独行的幸福数，输出其独立性。

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
using ull = unsigned long long;
using PII = pair<int ,int>;
using Pll = pair<ll,ll>;
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

unordered_map<int,bool> isHappy;
unordered_map<int,bool> notIndependent;
unordered_map<int,int> indepCount;

bool isPrime(int n){
	if(n<=1)	return false;
	for(int i=2;i<=n/i;i++){
		if(n%i==0)	return false;
	}
	return true;
}

int nextNum(int n){
	int sum=0;
	while(n){
		sum+=(n%10)*(n%10);
		n/=10;
	}
	return sum;
}

bool dfs(int cur,unordered_set<int>& path,vector<int>& route){
	if(cur==1)	return true;
	if(path.count(cur))	return false;
	path.insert(cur);
	route.push_back(cur);

	int nxt=nextNum(cur);
	bool result=dfs(nxt,path,route);
	return result;
}

int main(){
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int l,r;cin>>l>>r;
	vector<int> happyNums;
	for(int i=l;i<=r;i++){
		unordered_set<int> visited; // 判断是否死循环
		vector<int> route; // 记录路径（得到依赖于当前数的幸福数个数）
		bool happy = dfs(i,visited,route);

		if(happy){
			isHappy[i]=true;
			for(int j:route){
				if(j!=i){
					notIndependent[j]=true; //除第一个外 其他都不独立
				}
				indepCount[i]++;
			}
			happyNums.push_back(i);
		}
	}

	bool found=false;
	sort(happyNums.begin(),happyNums.end());
	for(int n:happyNums){
		if(!notIndependent[n]){
			int score = indepCount[n];
			if(isPrime(n))	score*=2;
			cout<<n<<" "<<score<<endl;
			found=true;
		}
	}

	if(!found)	cout<<"SAD"<<endl;

	return 0;
}

#include<bits/stdc++.h>

using namespace std;

#define endl '\n'

using ll = long long;

using ull = unsigned long long;

using PII = pair<int,int>;

using Pll = pair<ll,ll>;

int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

const int inf = 0x3f3f3f3f;

unordered_map<int,bool> isNotdependent;

unordered_map<int,int> dependentCnt;

bool is_prime(int n){

	if(n<2)	return false;

	for(int i=2;i<=n/i;i++){

		if(n%i==0){

			return false;

		}

	}

	return true;

}

int nextNum(int i){

	ll sum=0;

	while(i){

		int cur=i%10;

		sum+=cur*cur;

		i/=10;

	}

	return sum;

}

bool dfs(int cur,unordered_set<int>& visited,vector<int>& route){

	if(cur==1)	return true;

	if(visited.find(cur)!=visited.end())	return false;

	visited.insert(cur);

	route.push_back(cur);

	int nxt=nextNum(cur);

	return dfs(nxt,visited,route);

}

int main(){

	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

	int l,r;cin>>l>>r;

	vector<int> happyNums;

	for(int i=l;i<=r;i++){

		unordered_set<int> visited;

		vector<int> route;

		bool happy=dfs(i,visited,route);

		if(happy){

			for(auto j:route){

				if(j!=i){

					isNotdependent[j]=true;

				}

				dependentCnt[i]++;

			}

			happyNums.push_back(i);

		}

	}

	bool found=false;

	sort(happyNums.begin(),happyNums.end());

	for(int n:happyNums){

		if(!isNotdependent[n]){

			int score=dependentCnt[n];

			if(is_prime(n))

				score*=2;

			cout<<n<<" "<<score<<endl;

			found=true;

		}

	}

	if(!found)	cout<<"SAD"<<endl;

	return 0;

}

同类题型

视频讲解

⬅️ L2-028 秀恩爱分得快 🏠 00-天梯赛 ➡️ L2-030 冰岛人