MagicNumber
https://ac.nowcoder.com/acm/contest/13175/F
A需要满足任意的前导p个数能p|a1a2...ap
给火柴个数,问能拼出的最大的个数是多少
参考题解:https://blog.nowcoder.net/n/1a8a5d3d54e947c485ac6e1b4726ee9f?f=comment
实测组成的最大数字会达到25位,能被枚举完。
需要数组开__int128,但是题解没开到也能过。。。不知道为啥
#include <bits/stdc++.h> #define ll long long using namespace std; const int N = 3e5 + 7; __int128 ans[N];//给定花费所能组成的最大数字 int c[] = {6, 2, 5, 5, 4, 5, 6, 3, 7, 6};//数字的花费 void dfs(__int128 x,__int128 now,string s,__int128 cost){//位数 当前数字 当前数字 当前花费 if(x>0){ ans[cost]=max(ans[cost],now); } int st=0;if(x==0)st++; for(int i=st;i<=9;++i){ if((now*10+i)%(x+1)==0){ char ch = i+'0'; dfs(x+1,now*10+i,s+ch,cost+c[i]); } } } inline void write(__int128 x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x / 10); putchar(x % 10 + '0'); } string q; int main() { memset(ans,-1,sizeof(ans)); dfs(0,0,"",0); cin>>q; if(q.length()>5){ printf("-1 "); } else{ write( ans[ atoi(q.c_str()) ] ); } return 0; }