很简单的一套题,写个题解。
A 题面
现有一个 3x3 规格的 Android 智能手机锁屏程序和两个正整数 m 和 n ,请计算出使用最少m 个键和最多 n个键可以解锁该屏幕的所有有效模式总数。 其中有效模式是指:
每个模式必须连接至少m个键和最多n个键;
所有的键都必须是不同的;
如果在模式中连接两个连续键的行通过任何其他键,则其他键必须在模式中选择,不允许跳过非选择键(如图);
顺序相关,单键有效(这里可能跟部分手机不同)。
输入:m,n 代表允许解锁的最少m个键和最多n个键 输出: 满足m和n个键数的所有有效模式的总数
题解 很显然,解锁方式最多有$\sum\limits_{i=1}^{9}{A_9^{i}}$种,每一种方式处理的时间复杂度是$O(9)$。
处理某一种方式的时候,只需要判断相邻的两个点的中间是否有点或者有点的情况下他是否已经经过了。
用C++的话使用dfs即可模拟出所有情况。
但是Python有一个很优秀的库itertools里面有permutations函数可以很快速地去枚举所有的方式,只可惜Python速度太慢了,直接计算会TLE,见下面的代码。
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 class Solution : def solution (self, m, n ): if m > n: return 0 m, n = max (m, 1 ), min (n, 9 ) dp = [[-1 for i in range (9 )] for j in range (9 )] dp[0 ][2 ] = 1 dp[0 ][6 ] = 3 dp[0 ][8 ] = 4 dp[1 ][7 ] = 4 dp[2 ][0 ] = 1 dp[2 ][6 ] = 4 dp[2 ][8 ] = 5 dp[3 ][5 ] = 4 dp[5 ][3 ] = 4 dp[6 ][0 ] = 3 dp[6 ][2 ] = 4 dp[6 ][8 ] = 7 dp[7 ][1 ] = 4 dp[8 ][0 ] = 4 dp[8 ][2 ] = 5 dp[8 ][6 ] = 7 from itertools import permutations ans = 0 for i in range (m, n + 1 ): for per in permutations(range (9 ), i): vis = [False for i in range (9 )] vis[per[0 ]] = True ok = True for k in range (1 , i): if dp[per[k]][per[k - 1 ]] != -1 : if not vis[dp[per[k]][per[k - 1 ]]]: ok = False break vis[per[k]] = True if ok: ans += 1 return ans
$dp[i][j]$表示的是第$i$个点和第$j$个点之间的点是什么,如果没有则是-1。(懒得想变量名,随便写了个叫dp)
TLE了怎么办,这么小的数据量当然是本地打表,然后弄个前缀和,显然这个题就变成了$O(1)$的时间复杂度,不可能过不了。
1 2 3 4 5 6 7 8 9 10 class Solution : def solution (self, m, n ): if m > n: return 0 m, n = max (m, 1 ), min (n, 9 ) a = [0 , 9 , 56 , 320 , 1624 , 7152 , 26016 , 72912 , 140704 , 140704 ] b = [0 for i in range (10 )] for i in range (1 , 10 ): b[i] = b[i - 1 ] + a[i] return b[n] - b[m - 1 ]
其实也可以不用前缀和 习惯这样做了
B 题面
现给定任意正整数 n,请寻找并输出最小的正整数 m(m>9),使得 m 的各位(个位、十位、百位 … …)之乘积等于n,若不存在则输出 -1。
题解 显然这个数$n$只能由若干个2到9的积组成才有解。如果不是则返回-1。
有解时,要保证$m$最小,则先要保证数位最少。
所以分解因子的时候应当从大到小分解。
那么假设$n=2^{q_1}\cdot 3^{q_2}\cdot 4^{q_3}\cdot … \cdot 9^{q_8}$
显然$m$为$q_1$个$2$、$q_2$个$3$等等依此类推连起来即可。
但这个样例估计很水,他不会爆int。
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 class Solution {public : int solution (int n) { vector <int > v (10 , 0 ) ; for (int i = 9 ; i >= 2 ; i--) { while (n % i == 0 ) { v[i]++; n /= i; } } if (n > 1 ) return -1 ; int ret = 0 ; for (int i = 2 ; i <= 9 ; i++) { for (int j = 0 ; j < v[i]; j++) { ret = ret * 10 + i; } } return ret; } };
C 题面
在vivo产线上,每位职工随着对手机加工流程认识的熟悉和经验的增加,日产量也会不断攀升。 假设第一天量产1台,接下来2天(即第二、三天)每天量产2件,接下来3天(即第四、五、六天)每天量产3件 … … 以此类推,请编程计算出第n天总共可以量产的手机数量。
题解 本以为这第三个题会更难一点,结果这题最简单。。
因为他传的参数是int范围,而且直接暴力的复杂度是$O(\sqrt{n})$。
时间完全够用,实际上还可以加速。但我的想法是能过就行。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 class Solution {public : int solution (int n) { int cnt = 1 , res = 0 ; while (n >= cnt) { res += cnt * cnt; n -= cnt; cnt++; } return res + n * cnt; } };
回到开头