abcdeffa's Blog

当局者迷，旁观者清。

0%

CF2B 【The least round way】

发表于 更新于

Description

一个 $n \times n$ 的矩阵，位置 $(i, j)$ 上有数 $a_{i, j}$。现在你在 $(1, 1)$，向右或向下，走到 $(n, m)$，将走到的数乘起来，问你所得的积末尾最少有几个 0，并给出这条路径。

$1 \leq n \leq 10^3, 0 \leq a_i \leq 10^9$

Solution

做的时候降智了。

考虑设 $f_{i, j}$ 表示到 $(i, j)$ 的情况下，经过的数的乘积中 2 的最小幂数。

再考虑设 $g_{i, j}$ 表示到 $(i, j)$ 的情况下，经过的数的乘积中 5 的最小幂数。

这样如果 $a_i \not= 0$ 的话答案就是 $\min(f_{n, m}, g_{n, m})$ 对吧。

然后你考虑一下 $a_i = 0$ 的情况。

如果经过 0，那么乘积为 0，那么答案不大于 1。

然后你看一下如果不经过 0，能不能使答案为 0，能的话就直接输出，不能的话就随便找一条经过 0 的路径输出就好了。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <cstdio>
#include <cstring>
#define maxN 1010
long long a[maxN][maxN];
long long f[maxN][maxN][2], g[maxN][maxN][2];
long long min (long long x, long long y)
{
	return x < y ? x : y;
}
void dfs (long long x, long long y, long long opt)
{
	if(x == 1 && y == 1)
	{
		return ;
	}
	if(!opt)
	{
		if(f[x][y][1])
		{
			dfs(x - 1, y, opt);
			printf("D");
		}
		else
		{
			dfs(x, y - 1, opt);
			printf("R");
		}
	}
	else
	{
		if(g[x][y][1])
		{
			dfs(x - 1, y, opt);
			printf("D");
		}
		else
		{
			dfs(x, y - 1, opt);
			printf("R");
		}
	}
}
int main ()
{
	long long n = 0;
	scanf("%lld", &n);
	for(long long i = 1;i <= n; i++)
	{
		for(long long j = 1;j <= n; j++)
		{
			scanf("%lld", &a[i][j]);
		}
	}
	memset(f, 127 / 3, sizeof(f));
	memset(g, 127 / 3, sizeof(g));
	f[1][0][0] = f[0][1][0] = g[1][0][0] = g[0][1][0] = 0;
	bool flag = false;
	for(long long i = 1;i <= n; i++)
	{
		for(long long j = 1;j <= n; j++)
		{
			long long now = a[i][j];
			long long x = 0, y = 0;
			while(now && !(now % 2))
			{
				x++, now /= 2;
			}
			while(now && !(now % 5))
			{
				y++, now /= 5;
			}
			f[i][j][1] = (f[i - 1][j][0] < f[i][j - 1][0]);
			f[i][j][0] = min(f[i - 1][j][0], f[i][j - 1][0]) + x;
			g[i][j][1] = (g[i - 1][j][0] < g[i][j - 1][0]);
			g[i][j][0] = min(g[i - 1][j][0], g[i][j - 1][0]) + y;
			if(!a[i][j])
			{
				flag = true;
			}
		}
	}
	if(flag)
	{ 
		memset(f, 127 / 3, sizeof(f));
		memset(g, 127 / 3, sizeof(g));
		f[1][0][0] = f[0][1][0] = g[1][0][0] = g[0][1][0] = 0;
		for(long long i = 1;i <= n; i++)
		{
			for(long long j = 1;j <= n; j++)
			{
				long long now = a[i][j];
				long long x = 0, y = 0;
				while(now && !(now % 2))
				{
					x++, now /= 2;
				}
				while(now && !(now % 5))
				{
					y++, now /= 5;
				}
				if(!a[i][j])
				{
					x = 999999999, y = 999999999;
				}
				f[i][j][1] = (f[i - 1][j][0] < f[i][j - 1][0]);
				f[i][j][0] = min(f[i - 1][j][0], f[i][j - 1][0]) + x;
				g[i][j][1] = (g[i - 1][j][0] < g[i][j - 1][0]);
				g[i][j][0] = min(g[i - 1][j][0], g[i][j - 1][0]) + y;
			}
		}
		if(min(f[n][n][0], g[n][n][0]) == 0)
		{
			if(f[n][n][0] <= g[n][n][0])
			{
				printf("%lld\n", f[n][n][0] < 0 ? 1 : f[n][n][0]);
				dfs(n, n, 0);
			}
			else
			{
				printf("%lld\n", g[n][n][0] < 0 ? 1 : g[n][n][0]);
				dfs(n, n, 1);
			}
			return 0;
		}
	}
	memset(f, 127 / 3, sizeof(f));
	memset(g, 127 / 3, sizeof(g));
	f[1][0][0] = f[0][1][0] = g[1][0][0] = g[0][1][0] = 0;
	for(long long i = 1;i <= n; i++)
	{
		for(long long j = 1;j <= n; j++)
		{
			long long now = a[i][j];
			long long x = 0, y = 0;
			while(now && !(now % 2))
			{
				x++, now /= 2;
			}
			while(now && !(now % 5))
			{
				y++, now /= 5;
			}
			f[i][j][1] = (f[i - 1][j][0] < f[i][j - 1][0]);
			f[i][j][0] = min(f[i - 1][j][0], f[i][j - 1][0]) + x;
			g[i][j][1] = (g[i - 1][j][0] < g[i][j - 1][0]);
			g[i][j][0] = min(g[i - 1][j][0], g[i][j - 1][0]) + y;
			if(!a[i][j])
			{
				f[i][j][0] = g[i][j][0] = -999999999;
			}
		}
	}
	if(f[n][n][0] <= g[n][n][0])
	{
		printf("%lld\n", f[n][n][0] < 0 ? 1 : f[n][n][0]);
		dfs(n, n, 0);
	}
	else
	{
		printf("%lld\n", g[n][n][0] < 0 ? 1 : g[n][n][0]);
		dfs(n, n, 1);
	}
	return 0;
}