一个都知道的性质:一个数能被3整除,那么其数位和也能被3整除。
首先能想到的就是统计每个数 出现的次数
,然后从高位
枚举,
那么对于数,可以选的最大数量就是
cnt为目前还需要多少个数字,但是可能刚好选取 个
, 最后的答案不能被3整除,
所以我们枚举选的个数为,因为它们
都是
,肯定能找到答案(前提是有解)
最后直接dfs搜一遍所有情况,取一个最大的情况。还有就是前导0要判一下。
从 dfs一遍,每个位置最多
个可能,复杂度
code
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; const int man = 2e5+10; typedef long long ll; const ll mod = 1e9+7; char s[man]; int num[10],ans[10],tp[10],k; bool f; bool Max(){//判断之前的是否比目前的小 for(int i = 9;i >= 0;i--){ if(ans[i]>tp[i])return 0; else if(ans[i]<tp[i])return 1; } return 0; } void update(){//更新答案 for(int i = 0;i <= 9;i++){ ans[i] = tp[i]; } } void dfs(int pos,int cnt,int m){//pos表示当前的数字,cnt表示还需要多少个数,m表示选的数的和取余。 if(pos<0){ if(!cnt&&!m&&Max())update(),f = 1; return; } int tpnum = min(cnt,num[pos]);//目前最多能取的值 if(cnt==k&&pos==0)tpnum = min(tpnum,1);//判前导0 for(int i = tpnum;i >= max(0,tpnum-2);i--){//枚举选的个数 tp[pos] = i; dfs(pos-1,cnt-i,(m+i*pos)%3); } } int main() { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt","w",stdout); #endif int t; scanf("%d",&t); while(t--){ scanf("%s%d",s+1,&k); f = 0; for(int i =0 ;i <= 9;i++){ num[i] = ans[i] = tp[i] = 0; } for(int i = 1;s[i]!='\0';i++){ num[s[i]-'0']++; } dfs(9,k,0); if(f){ for(int i = 9;i >= 0;i--){ if(ans[i]){ for(int j = 1;j <= ans[i];j++){ printf("%d",i); } } }printf("\n"); }else cout << "-1\n"; } return 0; }