Nowcodercontest5278H 纸牌游戏

cnblogs页面

可以合理地想到从高到低依次枚举每一位的数，然后一下后面是否存在方案，问题在于如何快速Check

设还还剩下的的数个数分别为

设总共还需要个，需要凑出的方案

这时后我们假设枚举某一个，比如我们枚举选了个，设还剩下个要选，设剩下两个选了个，则有限制条件

把带掉，得到

我们可以根据各种限制条件解出的可行区间，然后判断区间内是否存在一个即可

同时我们可以发现，随的增大，的可行范围也会增大，所以可以直接枚举最大的3个就能完成check

#include<cstdio>
#include<cctype>
#include<queue>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<set>
#include<cmath>
using namespace std;

#define reg register
typedef long long ll;
#define rep(i,a,b) for(reg int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(reg int i=a,i##end=b;i>=i##end;--i)

#define pb push_back
template <class T> inline void cmin(T &a,T b){ ((a>b)&&(a=b)); }
template <class T> inline void cmax(T &a,T b){ ((a<b)&&(a=b)); }

char IO;
template<class T=int> T rd(){
    T s=0;
    int f=0;
    while(!isdigit(IO=getchar())) if(IO=='-') f=1;
    do s=(s<<1)+(s<<3)+(IO^'0');
    while(isdigit(IO=getchar()));
    return f?-s:s;
}

const int N=1e5+10;

int n,m;
char s[N],ans[N];
int cnt[10],c[3];

int Check(int n,int t){
    rep(i,0,2) c[i]=0;
    rep(i,0,9) c[i%3]+=cnt[i];
    // x+y=n-i
    // x<=c[2] ,y<=c[1]
    // 2x+y=t (mod 3)
    // x=n-i-y
    // 2n-2i-2y+y=t(mod 3)
    // 2n-y-2i=t(mod 3)
    // y=2n-2i-t (mod 3)
    int l0=max(0,n-c[1]-c[2]),r0=min(n,c[0]);
    drep(i,r0,max(l0,r0-4)) {
        int y=2*n-2*i-t;
        y=(y%3+3)%3;
        int l=max(0,n-i-c[2]),r=min(c[1],n-i); // y=的可行范围
        while(l%3!=y) l++;
        if(l<=r) return 1;
    }
    return 0;
}

int main(){
    rep(kase,1,rd()) {
        scanf("%s",s+1),n=strlen(s+1),m=rd();
        rep(i,0,9) cnt[i]=0;
        rep(i,1,n) cnt[s[i]-'0']++;
        int fl=1,c=0;
        rep(i,1,m) {
            ans[i]=0;
            drep(j,9,0) if(cnt[j]) {
                cnt[j]--;
                int t=3-c-j;
                t=(t%3+3)%3;
                int fl=Check(m-i,t);
                if(fl) {
                    ans[i]=j+'0';
                    c=(c+j)%3;
                    break;
                }
                cnt[j]++;
            }
            if(!ans[i] || (i==1 && m>1 && ans[i]=='0') ) {
                fl=0;
                break;
            }
        }
        ans[m+1]=0;
        puts(!fl?"-1":ans+1);
    }
}