娱乐 每 日 算 法 挑 战 【第6期】

[随性而为]

22 小时前, Muriya Tensei 说道:

暴力点，第三行打表，然后遍历前两行就行了，但是表要打M/3讲道理有点长

(有没有测试案例啊)写了一串感觉很不靠谱

 

22 小时前, yhz012 说道:

数学一点的描述可以是

给定数组ABC，求系数abc，使得abc各分量都是01，且 sum a = sum b = sum c = 1，sum aA+bB+cC = M

所以这个是个01规划问题……，如果求精确解估计最好也只能伪多项式级别了

 

  

什么我以为连easy都会有问题的（x

因为真的太暴力了（

退一万步说sort一下之后也可以拉到O(n^2)的（

先把ABC 花O(nlogn)sort出来

for a in A:
  tempC = C[-1]
  for b in B:
    while a + b + tempC > M:
      tempC = tempC.prev
    if a + b + tempC == M:
      count = count + 1

这样BC实际上是一起跑的，所以事实上只有2个循环，能拉到O(n^2)

嗯这里我假定了ABC所有元素都不同，如果相同稍微改一下上面的代码问题应该也不大

或者舍得空间复杂度的话直接写哈希表

for a in A:
  dict = dict + {M - a: a}
for b in B:
  for c in C:
    if b + c in dict:
      count = count + 1

这个改相同元素很简单

for a in A:
  dict[M - a] = dict[M - a] + 1
for b in B:
  for c in C:
    if b + c in dict:
      count = count + dict[b + c]

避免误解，这里的dict始终都是hashmap，key存在的时候返回value，key不存在的时候返回0，所以前面打表A的时候我手懒判断M-a存不存在了（理解意思就好（x

浏览了下题目和大佬的初步分析，我感觉没必要用哈希表啊，如果想要o(n^2)的话，可以这样

for(i=0;i<=N;i++)

     for(j=0;j<=N;j++)

          if((M-i*A-j*B)%C==0&&(M-i*A-j*B)/C<=N)

                   count ++;

应该是可以跑hard难度的？extreme难度……，你这M怎么记录呢，unsigned long long好像也只能记到2^64-1

（理解错题目的意思了，尴尬）

（01规划已经看见大佬提了好多次了，看来是时候取学习一下了）

ps:昨天练了一天的车，真jb累，第一次跑还被教练冷嘲热讽的

四月 16, 2020，由随性而为修改

[随性而为]

1 分钟前, yhz012 说道:

我有点没看懂最里面的判断条件？

ABC是三种颜色石头的魔力组成的数列吗？

所以说我不是修改了那个回复了么……