莱芜网站建设排行百度客服在线咨询

链接：https://ac.nowcoder.com/acm/contest/5278/H
来源：牛客网

题目描述
Cubercsl 和 Oneday 在玩一个纸牌游戏。两个人手中都有 n 张数字牌，每张牌面上都包含 0 \sim 90∼9 其中一个阿拉伯数字。
游戏规则是需要将手中的牌选出恰好 k 张，组成一个能被 3 整除的非负整数（不能含有多余前导零），组成的数大的获胜。
Cubercsl 自然是想取得胜利，所以他需要找到符合条件的最大的数。
输入描述:
第一行包含一个整数 T (T \leq 1000T≤1000)，表示测试数据的组数。
对于每组测试数据，包含一个数字构成的串 s (1 \leq |s| \leq 10 ^ 51≤∣s∣≤105
) 和一个整数 k (1 \leq k \leq |s|1≤k≤∣s∣)，中间以空格分隔，分别表示 Cubercsl 手中的牌和要选出的牌的数量。
输入保证 \sum |s| < 10 ^ 6∑∣s∣<10 6 。
输出描述:
对于每组测试数据，在一行输出一个整数，表示最大的能被 3 整除的数。特别地，如果无解，输出 -1。
示例1
输入

9
998244353 1
998244353 2
998244353 3
998244353 4
998244353 5
998244353 6
998244353 7
998244353 8
998244353 9

输出

9
99
993
9984
99852
998544
9985443
99854433
-1

示例2
输入

5
99999999999999999999 1
99999999999999999999 2
99999999999999999999 3
99999999999999999999 4
99999999999999999999 5

输出

9
99
999
9999
99999

两个多月没写题，一题写了一下午。。。题意理解错了一直差一点对，写了正解试数据才发现的。
题目说组成的数不能含前导0，我一直以为组成的数可以是多个0，答案输出一个0就可以了，但是这样不行，只有k为1的时候输出一个0才对，语文是我的硬伤，哎。
总体来说难度适中，从大到小的搜索，每个数可以少0次，1次，2次，因为少三次就是3的倍数了，再少也没有意义，第一遍写没发现出来，写完超时了发现的规律。
开始写的比较臃肿，后来一直改不对就看着别人的再写了一遍，比较简洁。思路和我开始的差不多，函数的循环感觉比我的要好。

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define maxn 1000005
char a[maxn];
int b[100],b1[100];
int n,flag,len;
void dfs(int start,int sum,int cont){if(start==-1){if(sum==0&&cont==n){for(int i=9;i>=0;i--){for(int j=0;j<b1[i];j++)printf("%d",i);}printf("\n");flag=1;}}else {if(!start&&!cont&&n!=1) return;int avail=min(b[start],n-cont);for(int i=avail;i>=max(0,avail-2)&&!flag;i--){b1[start]=i;dfs(start-1,(sum+start*i)%3,cont+i);}}	
}
int main()
{int s=0,t,m,q,i,x,y;scanf("%d",&t);while(t--){scanf("%s %d",&a,&n);flag=0;memset(b,0,sizeof(b));memset(b1,0,sizeof(b1));for(i=0;a[i];i++){b[a[i]-'0']++;}dfs(9,0,0);if(!flag) printf("-1\n");}return 0;
}

我写的

#include<algorithm>
#include<cstdio>
#include<cstring>
#include<vector>
#include<map>
using namespace std;
#define maxn 1000005
char a[maxn];
int b[100],b1[100];
int n,flag,len,top=0;
void judge(int sum){if(flag) return;if(sum==0){if(n==1){printf("0\n");flag=1;}return;}if(sum%3==0){for(int i=9;i>=0;i--){for(int j=0;j<b1[i];j++)printf("%d",i);}printf("\n");flag=1;}  
}
void dfs(int start,int cont,int sum){if(!cont){judge(sum);return;}if(flag) return ;int Cont=cont,Sum=sum;for(int i=start;i>=0;i--){if(!b[i]) continue;cont=Cont;sum=Sum;if(b[i]<=cont){b1[i]=b[i];cont-=b[i];sum+=b[i]*i;}else{b1[i]=cont;sum+=i*cont;cont=0;judge(sum);if(flag) return;}int m=min(2,b1[i]);for(int j=0;j<=m;j++){if(j) b1[i]--;dfs(i-1,cont+j,sum-i*j);if(flag) return;}b1[i]=0;}
}
int main()
{int s=0,t,m,q,i,x,y;scanf("%d",&t);while(t--){scanf("%s %d",&a,&n);flag=0;memset(b,0,sizeof(b));memset(b1,0,sizeof(b1));for(i=0;a[i];i++){b[a[i]-'0']++;}dfs(9,n,0);if(!flag) printf("-1\n");}return 0;
}