纸牌游戏

题目来源：牛客竞赛ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛牛客竞赛OJ (nowcoder.com)

下面给出这道题的题面

原题题面

题目描述

Cubercsl 和 Oneday 在玩一个纸牌游戏。两个人手中都有 n 张数字牌，每张牌面上都包含 0∼9其中一个阿拉伯数字。
游戏规则是需要将手中的牌选出恰好 k 张，组成一个能被 3 整除的非负整数（不能含有多余前导零），组成的数大的获胜。
Cubercsl 自然是想取得胜利，所以他需要找到符合条件的最大的数。

输入描述:

第一行包含一个整数 T (T≤1000)，表示测试数据的组数。
对于每组测试数据，包含一个数字构成的串 s (1≤∣s∣≤10^5) 和一个整数 k (1≤k≤∣s∣)，中间以空格分隔，分别表示 Cubercsl 手中的牌和要选出的牌的数量。
输入保证 ∑|s| < 10 ^ 6。

输出描述:

对于每组测试数据，在一行输出一个整数，表示最大的能被 3 整除的数。特别地，如果无解，输出 -1。

输入样例：

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

输出样例：

输入样例：

5
99999999999999999999 1
99999999999999999999 2
99999999999999999999 3
99999999999999999999 4
99999999999999999999 5

输出样例：

题目解释

这道题就是给定了我们好多的数字，要我们尽量地将数字组合成可以被3整除的最大的数

因此，我们该如何才能组成最大的数呢？

算法分析

我们可以想到，我们从最大的数9开始一次往下取，这样子可以每次都取到最大的，但是这样取不一定可以取到满足题目要求的答案，所以为了可以满足题目的要求，我们还需要进一步优化

假如我们现在有10个9，我们要组成大于10位的数，那么我们第一次就取10个9，然后取9个9，8个9…..依次往下取，这样子我们就可以找到所有的情况，然后当我们取完了需要的9以后，我们要记录我们当前的mod值(就是目前我们选择的所有的数对3取余剩下的数是多少，然后来选择我们下一次要的数字，比如我们选了9，那么我们下一步可以选6， 3， 0，最多就三种情况)

复杂度为3 ^ 10的

代码书写与分析

首先我们的全局变量，要记录我们的每种数字出现的个数，我们当前所取的每个数字的数量，我们所记录的满足要求的最大数字的数量，

分别是num, tp, ans数组

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
char s[N];
int num[N], ans[N], tp[N];
int k;
//判断是否可以找到最大的数
bool st;

main函数

开始，我们初始化所有的条件，然后我们依次枚举，最后我们看看能不能找到满足的，如果找到了满足的，那么它也一定满足最大的

int main()
{
    int T;
    cin >> T;
    while(T -- ) {
        //初始化
        cin >> (s + 1) >> k;
        st = 0;
        for(int i = 0;i <= 9;i++) num[i] = ans[i] = tp[i] = 0;
        int len = strlen(s + 1);
        //每种数字各有多少个
        for(int i = 1;i <= len;i++) num[s[i] - '0']++;
        //从最大的数字开始枚举，剩下k个数字没有枚举，目前%3为0
        dfs(9, k, 0);
        if(st) {
            for(int i = 9;i >= 0;i--) {
                //ans数组用来记录每种数字最终各取了多少个，然后从小到大输出
                if(ans[i]) {
                    for(int j = 1;j <= ans[i];j++) cout << i;
                }
            }
            cout << endl;
        }
        else cout << -1 << endl;
    }
    return 0;
}

dfs函数

//sum是现在枚举的数字是几，res是还剩下多少个位置没有枚举，mod是当前所有数总和%3的值
void dfs(int sum, int res, int mod) {
    if(sum < 0) {
        //如果剩下0个数字没有枚举的同时 所有数总和%3 == 0 同时需要把之前的记录下的数刷新
        //因为可能有很多种情况满足，只要有一个满足的，那么st = true
        //之后这个的if判断就是看是否有更大的数字满足这个情况了
        if(!res && !mod && Max()) update(), st = true;
        return;
    }
    //定义一个maxx，用来存储当前我还可以最多放多少个数字
    //如果我还有res个位置没有枚举，但是我现在这个数字的数量不够
    //或者我现在这个数字的数量比我的剩下没有枚举的位数要多，由于不清楚，所以要取最小的
    int minn = min(res, num[sum]);
    //如果所有数只有0的话，那么0最多出现一次，这里可以排除前导零的情况
    if(res == k && sum == 0) minn = min(1, minn);
    //最多只需要遍历3次即可，因为每个位置最多只有三种可能
    for(int i = minn;i >= max(0, minn - 2);i--) {
        tp[sum] = i;
        //枚举下一个数，下一种情况下还有res - i 个数字没有枚举，(之前的所有数%3的值+新添加的i个位置上的数的和)%3
        dfs(sum - 1, res - i, (mod + i * sum) % 3);
    }
}

Max函数

bool Max() {
    for(int i = 9;i >= 0;i--) {
        //从高位往低位枚举，如果有一种存在之前存的数是比目前这种情况存的数大的，那么false
        if(ans[i] > tp[i]) return 0;
        //在不满足平局的情况，返回true
        else if(ans[i] < tp[i]) return 1;
    }
    //平局，不需要更新，返回false
    return 0;
}

update函数

void update() {
    //将ans上的每一位数字的值全部刷新一遍
    for(int i = 0;i <= 9;i++) ans[i] = tp[i];
}

ac代码

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
char s[N];
int num[N], ans[N], tp[N];
int k;
bool st;

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 sum, int res, int mod) {
    if(sum < 0) {
        if(!res && !mod && Max()) update(), st = true;
        return;
    }
    int minn = min(res, num[sum]);
    if(res == k && sum == 0) minn = min(1, minn);
    for(int i = minn;i >= max(0, minn - 2);i--) {
        tp[sum] = i;
        dfs(sum - 1, res - i, (mod + i * sum) % 3);
    }
}

int main()
{
    int T;
    cin >> T;
    while(T -- ) {
        cin >> (s + 1) >> k;
        st = 0;
        for(int i = 0;i <= 9;i++) num[i] = ans[i] = tp[i] = 0;
        int len = strlen(s + 1);
        for(int i = 1;i <= len;i++) num[s[i] - '0']++;
        dfs(9, k, 0);
        if(st) {
            for(int i = 9;i >= 0;i--) {
                if(ans[i]) {
                    for(int j = 1;j <= ans[i];j++) cout << i;
                }
            }
            cout << endl;
        }
        else cout << -1 << endl;
    }
    return 0;
}