首页 > 代码库 > SGU 160.Magic Multiplying Machine

SGU 160.Magic Multiplying Machine

2024-07-16 22:57:10   218人阅读

时间限制:0.5s

空间限制6M

题意：

       给出n个（1<=n<=10000）1~m（2<m<1000）范围内的数，选择其中任意个数，使它们的 乘积 模m 最大，输出最大的分数，和选择的数的编号。

 

 

 

 

 

 

 

Solution:

              DP,

              从第一个数开始,f[]记录当前有哪些数可以得到.如果k可以得到令f[k]=1;

              再记录路径,和更新ans。

              如果单纯使用二重循环将是N*M 的复杂度。有很大可能超过0.5s的时限。

              于是这里使用数组实现的记录了哪些数可以得到的链表，p是链表头。

code（31ms AC）

 

#include<cstdio>int n, m, x;int g[10009], pr[1009][2], f[1009][2];void write (int x) {	if (pr[x][0] != 0) write (pr[x][0]);	printf ("%d ", pr[x][1]);}int main() {	scanf ("%d %d", &n, &m);	for (int i = 1; i <= n; i++) scanf ("%d", &x), g[i] = x % m;	int p = 0, ans = 0;	for (int i = 1; i <= n; i++) {		for (int j = p; j != 0; j = f[j][1]) {			int tem = (g[i] * j) % m;			if (tem > 1 && !f[tem][0]) {				f[tem][0] = 1; f[tem][1] = p;				p = tem, pr[tem][0] = j, pr[tem][1] = i;				if (tem > ans) ans = tem;			}		}		if (!f[g[i]][0]) {			f[g[i]][0] = 1, f[g[i]][1] = p;			p = g[i], pr[g[i]][1] = i;			if (g[i] > ans) ans = g[i];		}	}	if (ans > 0) {		printf ("%d\n", ans);		write (ans);		return 0;	}	puts ("1");	return 0;}

　　

 

　　

 


联系
我们