D.Digits（20202021ICPC,NERC,NorthernEurasiaOnsite题解）xiaodangao

题目链接：D. Digits
思路：$1e6 * 10$的$dp$每次更新以k为结尾的最大值就好了（最开始的想法是正确的），有一点是因为是乘法，所以必须进行取log操作，让乘法变成加法，才不会爆。然后需要注意的是进行存放方案的操作有些许的麻烦。
$Code:$

 #include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(auto i=a;i<=b;++i)
#define bep(i,a,b) for(auto i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;

template<typename T>void read(T&x){
static char c;static int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[65];int cnt=0;
if(x<0)pc('-'),x=-x;
q[++cnt]=x%10,x/=10;
while(x)
    q[++cnt]=x%10,x/=10;
while(cnt)pc(q[cnt--]+'0');
}

const int N = 1e5+10;
const double eps = 1e-9;
int n,d;
int a[N];double b[N],f[33],c[33];
vector<int>G[33],ans;
pair<int,int>tmp[33],cur[N][10];
int ma[33];
void solve(){
    int tot = 0;
    read(n);read(d);
    rep(i,1,n){read(a[i]);b[i] = log(1.0*a[i]); }
    //sort(a+1,a+1+n);
    rep(i,0,9)f[i] = -1;
    rep(i,1,n){
        tot = 0;
        rep(j,0,9)c[j] = f[j];
        rep(j,0,9){
        int s = a[i] % 10;
           if(j == s){
                if(b[i]>c[j]){
                    tmp[++tot] = {-1,j};c[j] = max(b[i],c[j]);
                }
           }
            int h = j*a[i]%10;
           double  p = f[j];
           if(f[j] < 0)continue;
           p += b[i];
           if(p>c[h] or c[h] == p){
            tmp[++tot] = {j,h};
            c[h] = max(c[h],p);
           }
        }
        rep(j,1,tot){
            int idx = tmp[j].first,idy = tmp[j].second;
            cur[i][idy] = {ma[idx],idx};
        }
        rep(j,1,tot)ma[tmp[j].second] = i;
        rep(j,0,9)f[j] = max(c[j],f[j]);//,printf("%lf ",f[j]);pc('\n');
    }
    if(f[d] == -1){
        puts("-1");return ;
    }
    //printf("%lf\n",f[d]);
    int idx = ma[d],idy = d;
    while(idx){ans.pb(a[idx]);int xx = idx,yy = idy;idx = cur[xx][yy].first,idy = cur[xx][yy].second; }
    sort(ans.begin(),ans.end());
    printf("%d\n",(int)ans.size());
    rep(i,0,(int)ans.size()-1)printf("%d ",ans[i]);
    //printf("%d\n",f[d]);
}
signed main(){solve();return 0;}

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章