度小满笔试编程题讨论

都没AC，等待大神解答

1. 小游戏

• 问题：

• 分析：将b个不同的物品放入a个不同的盒子，允许盒子为空的前提下有a**b种方案。因为对题目中的描述的直观理解和样例答案不一致，我是输出负的一方。

• 代码：

T = input()


def solve(a,b,n):
    if a == 1 and n > 1:
        return 0
    x = (a+1) ** b
    y = a ** (b+1)
    if x >= n and y >= n:
        return -1
    elif x >= n or y >= n:
        tmp = solve(a,b+1,n) if x >= n else solve(a+1,b,n)
        return - tmp
    else:
        status1 = solve(a,b+1,n)
        status2 = solve(a+1,b,n)
        return 1 if status1 == -1 or status2 == -1 else -1
        
        
for _ in xrange(T):
    a,b,n = map(int,raw_input().split())
    tmp = solve(a,b,n)
    if tmp == 1:
        print 'B'
    elif tmp == -1:
        print 'A'
    else:
        print 'A&B'
        

2. 链式边权

• 问题：

• 分析：看了半天才明白题目的意思，可以用dp在O(n)时间复杂度下求解，转移方程如下，其中res[i]表示第i+1个边权，lw,rw分别表示分割点左右哈希计数器，l_count，r_count分别表示分割点左右元素个数；

  res[i] = res[i-1] + (r_count - rw[a[i]]) - (l_count - lw[a[i]])

  
  

• 代码：

import collections

n = input()
a = map(int,raw_input().split())

lw = collections.Counter()
l_count = 0
rw = collections.Counter(a)
r_count = n
res = [0] * (n-1)
for i in xrange(n-1):
    lw[a[i]] += 1
    l_count += 1
    rw[a[i]] -= 1
    r_count -= 1
    res[i] = res[i-1] + (r_count - rw[a[i]]) - (l_count - lw[a[i]])

print ' '.join(map(str,res))