• 这次比赛,本来能做四道,结果D题DP问题太不熟练,前面三题耽误了大量时间,反省

以下是这次比赛的总结:

作为DIV3的开题来说,实则是非常可口的一道开胃菜了 o( ̄▽ ̄)ブ 直接for循环嵌套一个if判断语句
实现。本题没有很高深的算法思想,just do it!

n = int(input())
a = [int(x) for x in input().split()]
a.append(-1)
b = []
c = 0
for i in range(0,n):
    if a[i+1] <= a[i]:
        c = c + 1
        b.append(a[i])
print(c)
for e in b:
    print(e,end=' ')

此题大概意思,即给两个string,可操作空间为remove掉最左边的字母,可以无限次,问最少几步操作能达
到两个string相等。 因只能从左边删除,最后保留的字符必须相等,所以应该从右往左循环最好,即逆输出
两个字符串 a = a[::-1] b = b[::-1],然后以最小长度的字符串 l = min(na,nb) 为range建立
for循环(多出来的 d = abs(na-nb) 为必定要remove的长度,最后循环完毕再加上即可)
以下是python语言实现:

a = str(input())
b = str(input())
a = a[::-1]
b = b[::-1]
na = len(a)
nb = len(b)
d = abs(na-nb)
l = min(na,nb)
k = 0
for i in range(0,l):
    if a[i] != b[i]:
        k =  (l - i)*2
        break
print(d+k)

题目大意:一个数组里对于任意一个元素,总能找到至少另外一个组里元素相加为2的幂,则此Sequence称之
go♂d 。给出一个数组,求需要最少操作量的remove能使其变为go♂d
思路: 鉴于 n <= 120000, a[i] <= 10^9 ,所以不能高于 Onlogn 的复杂度,鄙人认为最好的解
法应该先排序 a = sorted(a) (排序不影响go♂d),在n循环下实施 binary search ,对于任意
a里面的元素,其需要的互补元素(使之相加能达到2^k),即建立一个 2^k 数组:

for i in range(1,31):
    p2.append(2**i)

然后求出每一个互补元素 d = 2**k -a[i] 再通过 f = bisect.bisect(a,d) 判断 a[f-1] == d
的存在, 如果为真,则 c = c + 1break 跳出k循环。特别地,如果 bisect 得出的值是其本身 if i == f-1
则执行 if a[f-2] == d ,结果为真,则计数 c = c + 1。完整版代码如下:

import bisect
n = int(input())
a = [int(x) for x in input().split()]
a = sorted(a)
p2 = []
for i in range(1,31):
    p2.append(2**i)
c = 0
if n == 1:
    print(1)
else:
    for i in range(0,n):
        flag = 0
        for j in p2:
            if j > a[i]:
                d = j -a[i]
                f = bisect.bisect(a,d)
                if d != a[i]:
                    if a[f-1] == d:
                        flag = 100
                        break
                else:
                    if i != f-1:
                        if a[f-1] == d:
                            flag = 100
                            break
                    else:
                        if a[f-2] == d:
                            flag = 100
                            break

        if flag == 0:
            c = c + 1
    print(c)

Print the maximum number of numbers divisible by 3 that Polycarp can get by making vertical cuts in the given number s.

思路:最最最最简单的dp问题,不要怂,直接写就是了!

a = str(input())
a = 'x' + a
n = len(a)
f = [0 for i in range(0,10**6)]
k = 0
for i in range(1,n):
    if int(a[i])%3 == 0:
        f[i] = f[i-1] + 1
        #if i == 4:
            #print(a[i],f[i])
        k = i
    else:
        for j in range(i-1,k,-1):
            if int(a[j:i+1])%3 == 0:
                f[i] = f[k] + 1
                k = i
        else:
            f[i] = f[k]
maxf = 0
for i in range(0,n):
    maxf = max(maxf,f[i])
print(maxf)