合肥需要做网站的公司,单位网站链接怎样做,网站内的搜索是怎么做的,学网站开发的书7-4 完美十进制数 对于一个十进制正整数 x#xff0c;其包含 k 个位#xff0c;每个数位的数字累加和为 sum 。如果 sum%k0#xff0c;那么这个十 进制数就是完美的。 例#xff1a;对于数 12340#xff0c;包含 5 位#xff0c;数位累加和为 10#xff0c;10%50#x…7-4 完美十进制数 对于一个十进制正整数 x其包含 k 个位每个数位的数字累加和为 sum 。如果 sum%k0那么这个十 进制数就是完美的。 例对于数 12340包含 5 位数位累加和为 1010%50所以 12340 是完美十进制数。 给定一个十进制正整数 N可以任意删除 N 的一些十进制位求得到最大的完美十进制数是多少。 删除后剩余的数可以包含前导零并且每个前导零都算作一位例如1063删除最高位 1 后变成 063包含 3 位累加和为 9是完美十进制数。如果删除 10 后变成 63包含 2 位累加和为 9此时 就不是完美十进制数。 需要注意的是前导零虽然占位但不会改变十进制数值的大小例如 06363≤73。 如果最终答案的完美十进制数包含了前导零前导零不用输出。 输入格式 输入包含一行表示十进制整数 N (1≤N≤1020)保证 N 不含前导零。 输出格式 输出包含一行表示得到的最大完美十进制数。不需要输出前导零。 3 输入样例1:6096 输出样例1:696 输入样例2:1063 输出样例2:63 样例解释: 063 是完美十进制数前导零无需输出。
想法
直接用dfs搜用vis数组的0和1表示这一位的数字是否删除。然后存到数组v中求最大值
#includebits/stdc.h
using namespace std;
string a;
int len;
int vis[10]{0};
vectorint v;
void dfs(int x){//位数if(xlen){int sign0,num0,sum0;for(int i0;ilen;i) {if(vis[i]) {suma[i]-0;num;sign1;}}if(sign0) return ;//数字全都不选if(sum%num0){int n0;for(int i0;ilen;i) {if(vis[i])nn*10a[i]-0;}v.push_back(n);}return ;}for(int i1;i0;i--){//0是不选1是选 vis[x]i;// dfs(x1);}
}
int main(){cina;lena.size();dfs(0);int ans-1;for(int i0;iv.size();i){ansmax(ans,v[i]);}coutans;return 0;
} 结果没想到时间复杂度数据范围是1n10e20,long long都爆了这样的话就不能这么去最大值了我还以为是1020hhh。题解那说的是“字符串模拟十进制数比较大小”本来我就弄个sort必字符串的结果我发现这样的话就是“9”“696”了。所以要先看一下字符串长度。
#includebits/stdc.h
using namespace std;
string a;
int len;
int vis[10]{0};
vectorstring v;//不用开个vector的v[]人家本来都是数组
bool cmp(string a,string b){if(a.size()b.size()) return ab;return a.size()b.size();
}
void dfs(int x){if(xlen){int sign0,num0,sum0;for(int i0;ilen;i) {if(vis[i]) {suma[i]-0;num;sign1;}}if(sign0) return ;if(sum%num0){string n;for(int i0;ilen;i) {if(vis[i]){na[i];}}v.push_back(n);}return ;}for(int i1;i0;i--){//0是不选1是选 vis[x]i;// dfs(x1);}
}
int main(){cina;lena.size();dfs(0);sort(v.begin(),v.end(),cmp);int flag0;for(int i0;iv[0].size();i){if(v[0][i]!0flag0){coutv[0][i];flag1;}else if(flag) coutv[0][i];}return 0;
}
