6.15训练日记

烦心事很多,但打代码一定要心静不能焦躁。平静平静. 惯例,先打卡cf先。

D. Required Length

链接 思路:naive地想,一开始找一个最大的数字嗯乘上去,比如说有一个9,就一直乘9,可能是最优的.但考虑到不是每次都有9,可能需要一些路径先生成一些更大的单个数字.然后考虑到每次都是x*个位数. 那么这个个位数做唯一分解 d i g i t = 2 a ∗ 3 b ∗ 5 c ∗ 7 d digit=2^a*3^b*5^c*7^d digit=2a∗3b∗5c∗7d 可以发现,可能的组合并不多,考虑直接bfs去暴力它.

#include
using namespace std;
const int maxn = 1e6+5;
const int INF = 1e9+7;
typedef long long ll;
typedef pair pii;
int main(){
    ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll n,x;
	cin>>n>>x;
	map dis;
	dis[x] = 0;
	queue q;q.push(x);
	int ans = -1;
	while(!q.empty()){
		ll y = q.front();
		q.pop();
		string str = to_string(y);
		if(str.length()==n){
			ans = dis[y];
			break; 
		}
		for(auto ch : str){
			if(ch=='0') continue;
			ll nxt = (int)(ch-'0')*y;
			if(!dis.count(nxt)){
				dis[nxt] = dis[y] +1;
				q.push(nxt);
			}
		}
	}
	coutn>>k;
		map cntt;
		for(int i=1;i>x;cntt[x]++;
		}
		vector vec;
		for(auto [x,y]:cntt){
			vec.push_back({x,y});
		}
		sort(vec.begin(),vec.end());
		reverse(vec.begin(),vec.end());
		ll ans = 1;
		for(auto [x,cnt]:vec){
			if(k>=cnt) k-=cnt;
			else {
				ans=(C(cnt,k)%mod);
				break;
			}
		}
		coutuu>>vv){
		if(uu==0&&vv==0) break;
		G[uu].push_back(vv);
		G[vv].push_back(uu);
	}
	cin>>s>>t;
	dfs(s,0);
	int ans = -1;
	for(int i=1;i