C++14(g++5.4) 解法, 执行用时: 48ms, 内存消耗: 1736K, 提交时间: 2020-04-20 13:26:04

#include<bits/stdc++.h>
using namespace std;
int _,n,m,a[15],b[15],ans[15];
string s;
bool check(){
	int i;
	for (i=9;i>=0;i--){
		if (b[i]>ans[i]) return 1;
		if (b[i]<ans[i]) return 0;
	}
	return 0;
}
void dfs(int x,int y,int z){
	int i,r;
	if (x<0){
		if (!y&&!z&&check()) memcpy(ans,b,sizeof(b));
		return;
	}
	r=min(z,a[x]);
	if (!x&&z==m) r=min(r,1);
	for (i=max(0,r-2);i<=r;i++){
		b[x]=i;
		dfs(x-1,(y+x*i)%3,z-i);
	}
}
int main(){
	int i,j;
	for (scanf("%d",&_);_;_--){
		cin>>s>>m;
		n=s.length();
		memset(a,0,sizeof(a));
		for (i=0;i<n;i++) a[s[i]-48]++;
		memset(ans,0,sizeof(ans));
		ans[0]=-1;
		dfs(9,0,m);
		if (ans[0]>=0){
			for (i=9;i>=0;i--)
			for (j=1;j<=ans[i];j++) putchar(i+48);
			putchar('\n');
		}
		else printf("-1\n");
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 54ms, 内存消耗: 1620K, 提交时间: 2020-07-04 02:03:32

#include<bits/stdc++.h>
using namespace std;

int i,flag,n,T,V[10],ans[10];
char R[100005];
void DFS(int L,int mod,int s)
{
	int i,j=min(V[L],n-s);
	if(flag)return;
	if(s==n)
	{
		if(!mod)
		{
			for(i=9;i>=0;i--)while(ans[i]--)printf("%d",i);
	        printf("\n");
	        flag=1;
		}
		return;
	}
	if((!L&&!s&&n!=1)||L==-1)return;
	for(i=j;i>=max(0,j-2);i--)ans[L]=i,DFS(L-1,(mod+L*i)%3,s+i),ans[L]=0;
}
int main()
{
	scanf("%d",&T);
	while(T--)
	{
		scanf("%s%d",R,&n);
		memset(V,0,sizeof(V)),memset(ans,0,sizeof(ans));
		for(i=0;R[i]!='\0';i++)V[R[i]-'0']++;
		flag=0,DFS(9,0,0);
		if(flag)continue;
		printf("-1\n");
	}
    return 0;
}