[已解决]Python：每日一题 316

zltzlt

wanting-for 发表于 2020-1-28 20:57
一个数只能选择一次，还是可以重复选择呢？

重复选择

fan1993423

1. from itertools import combinations
   
2. def chengfa(y):
   
3.     r=1
   
4.     for i in y:
   
5.         r*=i
   
6.     return r
   
7. def fun316(a,k):
   
8.     a.sort()
   
9.     count=0
   
10.     while len(a)>4:
    
11.         b,c=a[:-3],a[-3:]
    
12.         for i in c:
    
13.             for j in combinations(b,3):
    
14.                 if chengfa(j)*i<=k:
    
15.                     count+=1
    
16.         for i in combinations(c,2):
    
17.             for j in combinations(b,2):
    
18.                 if chengfa(i)*chengfa(j)<=k:
    
19.                     count+=1
    
20.         for j in b:
    
21.             if chengfa(c)*j<=k:
    
22.                 count+=1
    
23.         a=b
    
24.     if len(a)==4:
    
25.         if chengfa(a)<=k:
    
26.             count+=1
    
27.     return count
    

复制代码

确实用了combinations，速度会变很多

wanting-for

1. def numofplan(a, k):
   
2.     n = len(a)
   
3.     sum = [0] * 1000010
   
4.     cnt = [0] * 1000010
   
5.     for i in range(n):
   
6.         if a[i] > k:
   
7.             continue
   
8.         cnt[a[i]] += 1#多少数字小于等于i
   
9.     for i in range(n):
   
10.         for j in range(i + 1, n):
    
11.             if a[i] * a[j] > k:
    
12.                 continue
    
13.             sum[a[i] * a[j]] += 1
    
14.     for i in range(1, k + 1):
    
15.         cnt[i] += cnt[i - 1]
    
16.         sum[i] += sum[i - 1]
    
17.     ans = 0
    
18.     for i in range(n):
    
19.         for j in range(i + 1, n):
    
20.             res = a[i] * a[j]
    
21.             if res > k:
    
22.                 continue
    
23.             res = k / res
    
24.             ans += sum[int(res)]
    
25.             if a[i] <= res:
    
26.                 ans -= cnt[int(res / a[i])]
    
27.                 if a[i] <= res / a[i]:
    
28.                     ans += 1
    
29.             if a[j] <= res:
    
30.                 ans -= cnt[int(res / a[j])]
    
31.                 if a[j] <= res / a[j]:
    
32.                     ans += 1
    
33.             if a[i] * a[j] <= res:
    
34.                 ans += 1
    
35.     return int(ans/6)
    
36. 
    
37. print(numofplan([1,1,1,2,2],3))
    

复制代码

这道题难倒我了，好长时间思考不出来，暴力方法指定超时，n^4,渐变方法适用于【1】*1000，这种，对于复杂的就难以处理，最后是百度了，看了一下别人的方法，
这才解决的，惭愧啊
现在的是n^2

fan1993423

wanting-for 发表于 2020-1-28 21:49
这道题难倒我了，好长时间思考不出来，暴力方法指定超时，n^4,渐变方法适用于【1】*1000，这种，对于复杂 ...

这个解法是百度其他人的解法？

wanting-for

fan1993423 发表于 2020-1-28 22:09
这个解法是百度其他人的解法？

对的，这道题的题目叫做四数乘积，直接搜可以搜到！

fan1993423

我感觉我的智商被完爆，脑细胞不够用啊

zltzlt

fan1993423 发表于 2020-1-28 22:31
我感觉我的智商被完爆，脑细胞不够用啊

嗯，316 和 317 的确有点难

Croper

花了10多页草稿纸。。。发现自己数列求和全还给高中老师了

1. def func316(l:list,k:int):
   
2.     N=len(l)
   
3.     if (N<4):
   
4.         return 0
   
5. 
   
6.     tmp={}
   
7.     for i in l:
   
8.         tmp[i]=tmp.get(i,0)+1
   
9.     l=list(sorted(tmp.items(),key=lambda x:x[0]))
   
10. 
    
11.     sum=0
    
12.     for i in range(len(l)):
    
13.         sum+=l[i][1]
    
14.         l[i]=(l[i][0],l[i][1],sum)
    
15. 
    
16.     ret=0
    
17.     for i in range(len(l)):
    
18.         for j in range(i,len(l)):
    
19.             p,q=j,len(l)-1
    
20.             while p<=q:
    
21.                 if l[i][0]*l[j][0]*l[p][0]*l[q][0]>k:
    
22.                     q-=1
    
23.                 else:
    
24.                     if p==j:
    
25.                         if i==j:
    
26.                             t,a=l[q][2]-l[p][2]+l[p][1]-3,l[p][1]-3
    
27.                             if a>=0:
    
28.                                 ret+=(-3*a**4+(4*t-18)*a**3+(24*t-33)*a**2+(44*t-18)*a+24*t)//24
    
29.                         else:
    
30.                             t,a=l[q][2]-l[p][2]+l[p][1]-2,l[p][1]-2
    
31.                             if a>=0:
    
32.                                 ret+=l[i][1]*(-2*a**3+(3*t-6)*a**2+(9*t-4)*a+6*t)//6
    
33.                     else:
    
34.                         if i==j:
    
35.                             base=l[i][1]*(l[i][1]-1)//2
    
36.                         else:
    
37.                             base=l[i][1]*l[j][1]
    
38.                         ret+=base*(2*l[q][2]-2*l[p][2]+l[p][1]-1)*l[p][1]//2
    
39.                     p+=1
    
40.     return ret

复制代码

fan1993423

1. count=0
   
2. def test(lst,k,num=4):
   
3.     global count
   
4.     if num==0 and k>1:
   
5.         count+=1
   
6.         return count
   
7.     lst.sort()
   
8.     for i in range(len(lst)):
   
9.         test(lst[i+1:],k/lst[i],num-1)
   
10.     return count

复制代码

麻烦楼主测一下，我22楼的答案对不对，这是我今天刚想到的方法，不知道对不对以及耗时多少？@zlzlt

fan1993423

麻烦测一下，版主

zltzlt

fan1993423 发表于 2020-2-1 21:56
麻烦测一下，版主

输入 a = [1, 1, 1, 2, 2]，k = 3 答案就有错呢

fan1993423

zltzlt 发表于 2020-2-2 09:40
输入 a = [1, 1, 1, 2, 2]，k = 3 答案就有错呢

我这边输出的是2啊

fan1993423

不管是22楼还是我29楼的答案

zltzlt

fan1993423 发表于 2020-2-2 12:09
我这边输出的是2啊

我再试了一下，现在正确了，可能刚才操作有误

fan1993423

zltzlt 发表于 2020-2-2 12:12
我再试了一下，现在正确了，可能刚才操作有误

嗯，22楼用了combinations可能有点慢，29楼是递归应该要快点，希望能超过其他鱼油的答案

fan1993423

zltzlt 发表于 2020-2-2 12:12
我再试了一下，现在正确了，可能刚才操作有误

版主，如果正确，能不能发一下我两个答案耗时分别是多少？

zltzlt

fan1993423 发表于 2020-1-31 21:34
麻烦楼主测一下，我22楼的答案对不对，这是我今天刚想到的方法，不知道对不对以及耗时多少？@zlzlt

耗时相当长输入 list(range(1, 101)) 就超时了

fan1993423

zltzlt 发表于 2020-2-3 15:50
耗时相当长输入 list(range(1, 101)) 就超时了

29楼的答案也是吗？

zltzlt

fan1993423 发表于 2020-2-3 15:54
29楼的答案也是吗？

是

fan1993423

zltzlt 发表于 2020-2-3 15:54
是

那就尴尬了