H 纸牌游戏 题解

多组数据
每组给你一个字符串 和一个数字

要求你用 中的字符拼出一个长度为 的能被 整除的非负整数不能有前导

如果无解输出否则输出最大的答案

求最后的

首先如果答案中数字的个数知道了那么答案本身是什么 以及 答案 是否 就都知道了.

那么我们要求的就是答案中的出现次数

考虑从 枚举答案并

方法很多我赛场上是把的上界求出来然后枚举它们 的余数并的方法

复杂度

#include <bits/stdc++.h>
using namespace std;
int K;
struct Data{
    int c[12];
    inline bool check(){
        int tot = 0,i;
        for (i = 0; i <= 9; ++i){
            tot += c[i];
            if (c[i] < 0) return 0; 
        }
        if (tot != K) return 0;
        int tot1 = 0;
        for (i = 1; i <= 9; ++i) tot1 += c[i];
        if (!tot1 && tot > 1) return 0;
        return 1;
    }
    inline void print(){
        if (!check()){ cout <<"-1\n"; return; }
        for (int i = 9; i >= 0; --i) while (c[i]--) cout << (char)('0'+i); 
        cout << '\n';
    }
    inline void clear(){ memset(c,0,sizeof(c)),c[0] = 1; }
}ans,tmp;
bool operator < (Data A,Data B){
    if (!B.check()) return 0; if (!A.check()) return 1;
    for (int i = 9; i ; --i) if (A.c[i] != B.c[i]) return A.c[i] < B.c[i];
    return A.c[0] < B.c[0];
}
string SS;
int cnt[10],c[10];
inline bool check(int v){
    int ntot = 0,nsum = 0,i;
    for (i = 9; i > v; --i) ntot += c[i],nsum = (nsum + c[i] % 3 * i) % 3;
    if (ntot > K) return 0;
    if (ntot == K){ if (nsum == 0) return 1; return 0; } if (v < 0) return 0;
    int c0,c1,c2,need; need = K - ntot,c0 = c1 = c2 = 0;
    for (i = 0; i <= v; ++i)
        if (i%3==0) c0+=cnt[i]; else if (i%3==1) c1+=cnt[i]; else c2+=cnt[i];
    int j,k,num,kk;
    for (i = 0; i < 3; ++i) for (j = 0; j < 3; ++j) for (k = 0; k < 3; ++k){
        if (i > c0 || j > c1 || k > c2) continue; if ((j+k*2+nsum)%3) continue;
        num = i+j+k,kk = (c0-i)/3+(c1-j)/3+(c2-k)/3;
        if (need % 3 == num % 3 && need <= 3 * kk + num && need >= num) return 1;
    }
    return 0;
}
int now[10];
inline void solve(){
    int i;
    ans.clear(); cin >> SS >> K; memset(cnt,0,sizeof(cnt));
    for (i = 0; i < SS.size(); ++i) ++cnt[SS[i]-'0'];
    memset(c,0,sizeof(c));
    memset(now,0,sizeof(now));
    if (!check(9)){
        cout <<"-1\n"; return;
    }
    for (i = 9; i >= 0; --i){
        now[i] = c[i] = 0;
        for (int mid = cnt[i]; mid ; --mid){
            c[i] = mid;
            if (check(i-1)){ now[i] = mid; break; }
            else c[i] = 0;
        }
    }
    tmp.clear();
    for (i = 0; i <= 9; ++i) tmp.c[i] = now[i];
    ans = max(ans,tmp);
    ans.print();
}
int main(){
    ios::sync_with_stdio(0);
    int T; cin >> T; while (T--) solve();
    return 0;
}