“科大讯飞杯”第18届上海大学程序设计联赛春季赛暨高校网络友谊赛
0x01. A-F较简单，略
0x02. H. 纸牌游戏
看到余数看到位数，没多加思考直接敲了数位DP，但是一直没过，这时就发现设计的DP存在后效性，难受得想不出办法；结果比赛结束以后就想到搜索+剪枝，首先从余数角度考虑，根据数字%3后的余数mod，当mod==0时不管什么数字都可以直接选；当mod==1时，取 i 个与取 i+3 个取模后效果相同，对于mod==2 同样适用，那么最少只需要取可能最大值-2 ，因此每次枚举数量只会有最多3种可能，当前枚举数直接从9开始往小取即可，在输出的时候判断前导0的问题即可。
#include
using namespace std;
char s[100005];
int cnt[10],ans[10];
bool dfs(int x,int k,int mod){
//if(k==0)return mod==0;
if(x==-1)return k==0&&mod==0;
int r=min(k,cnt[x]),l=max(r-2,0);
for(int i=r;i>=l;i--)
if(dfs(x-1,k-i,(mod+i*x)%3)){
ans[x]=i;
return true;
}
return false;
}
int main(){
int T;
for(scanf("%d",&T);T;T--){
for(int i=0;i<10;i++)cnt[i]=0;
int k;
scanf("%s%d",s,&k);
int lena=strlen(s);
for(int i=0;i<lena;i++)cnt[s[i]-'0']++;
if(!dfs(9,k,0))cout<<-1<0;i--)
for(int j=ans[i];j;j--){
cout<<i;flag=true;
}
if(!flag) //处理前导0的情况
cout<<(k==1&&ans[0]?0:-1);
else
for(int i=ans[0];i;i--)
cout<<0;
cout<<endl;
}
}
return 0;
}
作者：cms061817
