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整除的直接枚举就可以了。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <algorithm>

 #include <climits>

 #include <vector>

 #include <queue>

 #include <cstdlib>

 #include <string>

 #include <set>

 #include <stack>

 #define LL long long

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 using namespace std;

 const int maxn = ;

 char str[maxn];

 int cnt[],table[][],len,tot;

 bool vis[maxn];

 bool dfs(int sum,int d,int cur){

     if(cur >= d) return sum% == ;

     for(int i = ; i < len; ++i){

         int tmp = str[i] - '';

         if(!vis[i]){

             vis[i] = true;

             if(dfs(sum* + tmp,d,cur+)) return true;

             vis[i] = false;

         }

     }

     return false;

 }

 void create(){

     memset(table,,sizeof(table));

     for(int i = tot = ; i<< < ; ++i){

         int db = ,tmp = i<<;

         while(tmp){

             int u = tmp%;

             table[tot][u]++;

             tmp /= ;

             db++;

         }

         table[tot++][] +=  - db;

     }

 }

 bool check(){

     int i,j;

     memset(cnt,,sizeof(cnt));

     for(i = ; i < len; ++i) cnt[str[i]-'']++;

     for(i = ; i < tot; ++i){

         for(j = ; j < ; ++j)

             if(cnt[j] < table[i][j]) break;

         if(j == ) return true;

     }

     return false;

 }

 int main() {

     create();

     while(~scanf("%s",str)){

         len = strlen(str);

         if(len <= ){

             memset(vis,false,sizeof(vis));

             if(dfs(,len,)) puts("YES");

             else puts("NO");

         }else if(check()) puts("YES");

         else puts("NO");

     }

     return ;

 }