牛客33-tokitsukaze and Number Game(數論)

題目描述

tokitsukaze又在玩3ds上的小游戲了，現在她遇到了難關。
tokitsukaze得到了一個整數x，并被要求使用x的每一位上的數字重新排列，組成一個能被8整除的數，并且這個數盡可能大。
聰明的你們請幫幫可愛的tokitsukaze，如果無法組成被8整除的數，請輸出-1。
保證輸入不含前導0，輸出也不能含前導0。

輸入描述:

第一行包括一個正整數T(T<=1000)，表示T組數據。
接下來T行，每一行包括一個整數x，(0≤x≤10^100)。

輸出描述:

請輸出用這些數字組成出能被8整除的最大的數，如果無法組成出能被8整除的數，請輸出-1。

?

示例1

輸入

2
666
1256

輸出

-1
6512

一個數能否被8整除,若大于999,呢么后三位能整除8,呢么這個數字就能整除8

快速判斷一個數能否被1、2、3、4、5、6、7、8、9、10、11、12、13、17、19、23等整除的規律總結:

https://blog.csdn.net/weixin_41183791/article/details/84887846

ac:

#include<bits/stdc++.h>
using namespace std;
int c[10]={0};
char str[1010]={0};struct node
{int num;int max2;int xc[10]={0};friend bool operator <(node a,node b){if(a.max2==b.max2)return a.num>b.num;else return a.max2<b.max2;}
}a[1000];int b[3]={0};int init()
{int n,m,x,j=1;a[0].num=0;   //別忘了000哦a[0].xc[0]=3;a[0].max2=0;for(int i=100;i<1000;i++){if(i%8==0){a[j].num=i;b[0]=i%10;b[1]=(i%100)/10;b[2]=i/100;a[j].xc[b[0]]++;a[j].xc[b[1]]++;a[j].xc[b[2]]++;sort(b,b+3,greater<int>());a[j].max2=b[0]*100+b[1]*10+b[2];j++;}}sort(a,a+j);return j;
}int gg[]={8,16,24,32,40,48,56,64,72,80,88,96};int main()
{int t;int j=init();scanf("%d",&t);while(t--){memset(str,0,sizeof(str));memset(c,0,sizeof(c));scanf("%s",&str);int len=strlen(str);if(len==1){if(str[0]-'0'==8)printf("8\n");else if(str[0]-'0'==0)printf("0\n");else printf("-1\n");}else if(len==2){int flag=0;int xx=(str[0]-'0')*10+str[1]-'0';int yy=str[0]-'0'+(str[1]-'0')*10;for(int i=11;i>=0;i--){if(xx==gg[i]||yy==gg[i]){flag=1;printf("%d\n",gg[i]);break;}}if(flag==0)printf("-1\n");}else{for(int i=0;i<len;i++)c[str[i]-'0']++;int sign=0;for(int i=0;i<j;i++){int flag=0;for(int k=0;k<10;k++){if(c[k]<a[i].xc[k]){flag=1;break;}}if(flag==0){for(int k=0;k<10;k++)c[k]-=a[i].xc[k];for(int k=10;k>=0;){if(c[k]>0){printf("%d",k);c[k]--;}else k--;}if(i==0)printf("000\n");else printf("%d\n",a[i].num);sign=1;break;}}if(sign==0)printf("-1\n");}}return 0;
}

?