九层循环梯云纵

Starsfocxy

2024-08-08 11:03:12

发布于：上海

71阅读

0回复

0点赞

753数题目：炫总题解，永久纪念！

#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
using namespace std; 
const int N = 1e5 + 5;
typedef long long LL;

struct node{
	long long next;
	bool a, b, c;
};

long long n, ans;
int dir[3] = {3, 5, 7};

void dfs(long long x, bool f3, bool f5, bool f7){
	if(x > n)	return ;
	if(f3 && f5 && f7)	ans++;
	dfs(x * 10 + 3, 1, f5, f7);
	dfs(x * 10 + 5, f3, 1, f7);
	dfs(x * 10 + 7, f3, f5, 1);
}

void bfs(int x){
	queue<node> q;
	q.push({0, 0, 0, 0});
	while(q.size()){
		node now = q.front();
		q.pop();
		
		if(now.a && now.b && now.c){
			ans++;
		}
		
		node p = now;
		p.next = now.next * 10 + 3;
		p.a = 1;
		if(p.next <= n)	q.push(p);
		
		p = now;
		p.next = now.next * 10 + 5;
		p.b = 1;
		if(p.next <= n)	q.push(p);
		
		p = now;
		p.next = now.next * 10 + 7;
		p.c = 1;
		if(p.next <= n)	q.push(p);
	}
}

int vis[5];
bool init(long long x){
//	cout << x << endl;
	if(x > n)	return 0;
	if(vis[0] && vis[1] && vis[2])	return 1;
	return 0;
}

void solve(){
	for(int i = 0; i < 3; i++){
		vis[i]++;
		for(int j = 0; j < 3; j++){
			vis[j]++;
			for(int k = 0; k < 3; k++){
				vis[k]++;
				ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100);
				for(int p = 0; p < 3; p++){
					vis[p]++;
					ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000);
					for(int l = 0; l < 3; l++){
						vis[l]++;
						ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000);
						for(int m = 0; m < 3; m++){
							vis[m]++;
							ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000 + dir[m] * 100000);
							for(int q = 0; q < 3; q++){
								vis[q]++;
								ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000 + dir[m] * 100000 + dir[q] * 1000000);
								for(int h = 0; h < 3; h++){
									vis[h]++;
									ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000 + dir[m] * 100000 + dir[q] * 1000000 + dir[h] * 10000000);
									for(int v = 0; v < 3; v++){
										vis[v]++;
										ans += init((LL)dir[i] + dir[j] * 10 + dir[k] * 100 + dir[p] * 1000 + dir[l] * 10000 + dir[m] * 100000 + dir[q] * 1000000 + dir[h] * 10000000 + dir[v] * 100000000);
										vis[v]--;
									}
									vis[h]--;
								}
								vis[q]--;
							} 
							vis[m]--;
						}
						vis[l]--;
					}
					vis[p]--;
				}
				vis[k]--;
			}
			vis[j]--;
		}
		vis[i]--;
	}
}

int main(){
	freopen("number.in", "r", stdin);
	freopen("number.out", "w", stdout);
	
	cin >> n;
//	dfs(0, 0, 0, 0);
//	bfs(0);
	solve();
	cout << ans;

	
	fclose(stdin);
	fclose(stdout);
	return 0;
}