首页 > 代码库 > CSDN 轻松周赛赛题：能否被8整除
CSDN 轻松周赛赛题：能否被8整除
轻松周赛赛题：能否被8整除
题目详情
给定一个非负整数，问能否重排它的全部数字，使得重排后的数能被8整除。
输入格式：
多组数据，每组数据是一个非负整数。非负整数的位数不超过10000位。
输出格式
每组数据输出一行,YES或者NO，表示能否重排它的全部数字得到能被8整除的数。注意： 重排可以让0开头。
答题说明
输入样例
610
122
输出样例
YES
NO
解释
第一个数可以变为016 , 160
解题：很水的一道题。。。思路很简单，1000是能被8整除的，所以一千的倍数都能被8整除，假设输入的大数为x，把x分解成x = a*1000+b
很明显a*1000能够被8整除，所以只要判断b能不能被8整除即可。
三位数能够被8整除的直接枚举就可以了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib>10 #include <string>11 #include <set>12 #include <stack>13 #define LL long long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 using namespace std;17 const int maxn = 10010;18 char str[maxn];19 int cnt[10],table[200][10],len,tot;20 bool vis[maxn];21 bool dfs(int sum,int d,int cur){22 if(cur >= d) return sum%8 == 0;23 for(int i = 0; i < len; ++i){24 int tmp = str[i] - ‘0‘;25 if(!vis[i]){26 vis[i] = true;27 if(dfs(sum*10 + tmp,d,cur+1)) return true;28 vis[i] = false;29 }30 }31 return false;32 }33 void create(){34 memset(table,0,sizeof(table));35 for(int i = tot = 0; i<<3 < 1000; ++i){36 int db = 0,tmp = i<<3;37 while(tmp){38 int u = tmp%10;39 table[tot][u]++;40 tmp /= 10;41 db++;42 }43 table[tot++][0] += 3 - db;44 }45 }46 bool check(){47 int i,j;48 memset(cnt,0,sizeof(cnt));49 for(i = 0; i < len; ++i) cnt[str[i]-‘0‘]++;50 for(i = 0; i < tot; ++i){51 for(j = 0; j < 10; ++j)52 if(cnt[j] < table[i][j]) break;53 if(j == 10) return true;54 }55 return false;56 }57 int main() {58 create();59 while(~scanf("%s",str)){60 len = strlen(str);61 if(len <= 3){62 memset(vis,false,sizeof(vis));63 if(dfs(0,len,0)) puts("YES");64 else puts("NO");65 }else if(check()) puts("YES");66 else puts("NO");67 }68 return 0;69 }
CSDN 轻松周赛赛题：能否被8整除
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。