2020-2021 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)

D. Digits

题意

给定一个长度为n的数组a和一个k，求数组中最大的元素乘积的尾数为k
（每个元素只能用一次）,输出方案数

 1<= ai <= 1000
  1 <= n <= 1e5
  0 <= k <= 9

思路

很容易想到是01背包求方案数，但是乘积很大会爆long long，log x 也是满足递增情况，和乘积的递增表示类似，能够很好的把 * 转换为 +。

代码

#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<unordered_set>
#include<unordered_map>

using namespace std;
#define x first
#define y second
//#define int long long
typedef pair<int ,int > PII;
typedef long long ll;
const int N = 1e5 + 10;
const double eps = 1e-6;
int a[N];
double b[N];
double f[N][10];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;i++) scanf("%d",&a[i]);
	for(int i = 1;i <= n;i++) {
		b[i] = log(a[i]);
	}
	memset(f,-0x3f,sizeof f);
	f[0][1] = 0; 
	for(int i = 1;i <= n;i++){
		for(int j = 0;j <= 9;j++)
			f[i][j] = f[i - 1][j];
		for(int j = 0;j <= 9;j++){
			int t = a[i] * j % 10;
			if(f[i - 1][j] >= 0) f[i][t] = max(f[i][t],f[i - 1][j] + b[i]);
		}
	}
	if(f[n][m] < 0){
		cout << -1 << endl;
		return 0;
	}
	vector<int > ans;
	int u = n - 1,j = m;
	while(u >= 0){
		for(int i = 0;i <= 9;i++){
			int v = a[u + 1] * i % 10;
			if(v == j ){
				if(fabs(f[u][i] + b[u + 1] - f[u + 1][j]) < eps){
					ans.push_back(a[u + 1]);
					j = i;
					break;
				}
			}
		}
		u --;
	} 
	
	if(ans.size() == 0){
		puts("-1");
	}
	else{
		cout << ans.size() << endl;
		for(auto x:ans){
			printf("%d ",x);
		}
	}
	return 0;
}