包头全网营销网站建设,wordpress 极简 文字,中国城市建设网,做网站二级页面的链接#xff1a;https://ac.nowcoder.com/acm/contest/5278/H 来源#xff1a;牛客网
题目描述 Cubercsl 和 Oneday 在玩一个纸牌游戏。两个人手中都有 n 张数字牌#xff0c;每张牌面上都包含 0 \sim 90∼9 其中一个阿拉伯数字。 游戏规则是需要将手中的牌选出恰好 k 张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的倍数了再少也没有意义第一遍写没发现出来写完超时了发现的规律。 开始写的比较臃肿后来一直改不对就看着别人的再写了一遍比较简洁。思路和我开始的差不多函数的循环感觉比我的要好。
#includealgorithm
#includecstdio
#includecstring
#includevector
#includemap
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(sum0contn){for(int i9;i0;i--){for(int j0;jb1[i];j)printf(%d,i);}printf(\n);flag1;}}else {if(!start!contn!1) return;int availmin(b[start],n-cont);for(int iavail;imax(0,avail-2)!flag;i--){b1[start]i;dfs(start-1,(sumstart*i)%3,conti);}}
}
int main()
{int s0,t,m,q,i,x,y;scanf(%d,t);while(t--){scanf(%s %d,a,n);flag0;memset(b,0,sizeof(b));memset(b1,0,sizeof(b1));for(i0;a[i];i){b[a[i]-0];}dfs(9,0,0);if(!flag) printf(-1\n);}return 0;
}
我写的
#includealgorithm
#includecstdio
#includecstring
#includevector
#includemap
using namespace std;
#define maxn 1000005
char a[maxn];
int b[100],b1[100];
int n,flag,len,top0;
void judge(int sum){if(flag) return;if(sum0){if(n1){printf(0\n);flag1;}return;}if(sum%30){for(int i9;i0;i--){for(int j0;jb1[i];j)printf(%d,i);}printf(\n);flag1;}
}
void dfs(int start,int cont,int sum){if(!cont){judge(sum);return;}if(flag) return ;int Contcont,Sumsum;for(int istart;i0;i--){if(!b[i]) continue;contCont;sumSum;if(b[i]cont){b1[i]b[i];cont-b[i];sumb[i]*i;}else{b1[i]cont;sumi*cont;cont0;judge(sum);if(flag) return;}int mmin(2,b1[i]);for(int j0;jm;j){if(j) b1[i]--;dfs(i-1,contj,sum-i*j);if(flag) return;}b1[i]0;}
}
int main()
{int s0,t,m,q,i,x,y;scanf(%d,t);while(t--){scanf(%s %d,a,n);flag0;memset(b,0,sizeof(b));memset(b1,0,sizeof(b1));for(i0;a[i];i){b[a[i]-0];}dfs(9,n,0);if(!flag) printf(-1\n);}return 0;
}
