3.24拼多多算法笔试（pdd）

Q1

这里有n个正整数，a1,....,an

Alice 会先去掉其中最多d 个数

Bob 接下来会将剩余的数中最多m个数乘以 -k

Alice 想要剩余数之和尽可能大，Bob 想要剩余数之和尽可能小。假设 Alice 和 Bob 都足够聪明，请问最后剩余数之和是多少。

输入描述

第一行一个正整数T，接下来有T组数据

每组数据2行

第一行4 个数

n, m, k, d (2 ≤ n ≤ 10^5) (0 ≤ m, d ≤ n) (1 ≤ k < 10^4)

第二行n个数，a1,a2,..., an (1 ≤ ai ≤ 10^9)

保证sigma n不超过10^5

输出描述

每组数据输出一行，每行一个数，表示剩余数之和

A1

排序，滑动窗口解决，为啥有滑动窗口这个结论是因为有一个单调性：Alice和Bob都倾向选大端的数！

import sys

t = int(input())
for i in range(t):
    n,m,k,d = map(int,input().split())
    nums = list(map(int,input().split()))
    nums.sort(key=lambda x:-x)
    tmp = -k*sum(nums[:m])+sum(nums[m:])
    res = tmp
    for i,num in enumerate(nums):
        if i>=d:
            break
        tmp+=k*nums[i]
        tmp-=(k+1)*nums[i+m] if i+m<n else 0
        res = max(res,tmp)
    print(res)

Q2

伊文有两个由0和1组成的字符串，A和B，长度分别为m和n（m>=n）。伊文希望取出A的连续子串与B构造若干长度为n的S串，满足：

• 
• 

伊文想知道总共能够构造出多少个不同的S串。

输入描述

输入有三行，第一行2个数m和n，为A和B的长度；

m,n （0 <n≤m≤5 x10^3）

第二行为长度为m的A串

第三行为长度为 的B串，A和B仅由'0'和'1'组成

输出描述

输出：一个数字，代表不同的S串个数

A2

签到题在第二题，这个数据量级直接暴力了

import sys

m,n = map(int,input().split())
a = input()
b = input()

def xor(s1,s2):
    res = ""
    cnt = 0
    for a,b in zip(s1,s2):
        if (a=='1' and b=='0') or (b=='1' and a=='0'):
            res+='1'
            cnt^=1
        else:
            res+='0'
            cnt^=0
    return cnt,res

s = set()
for i in range(m-n+1):
    cnt,res = xor(a[i:i+n],b)
    if cnt:
        continue
    if res not in s:
        s.add(res)
print(len(s))

Q3

多多快递站共有n个快递点，n个快递点之间通过m条单向车道连接。快递员从任何一个快递站点出发，都无法通过单向车道回到该站点。也就是说，n个快递点组成一张有向无环图。对于快递点u，如果对于所有的快递点v（u != w），快递员都可以从w走到v，或者从v走到u，那么则评定站点u为超级快递点。

请你帮忙算一算，一共有多少个超级快递点。

输入描述

第一行2个数字n（2≤n≤3*10^5）,m（1≤m ≤3*10^5），n为快递点个数，m为单向车道个数。

接下来的m行每行两个数字u,v (1<=u,v<=n,u!=v)，表示有一条站点么指向0的单向车道。

输出描述

请输出1个数字，表示超级快递点的个数。

A3

DFS暴力ac不了不献丑了

Q4

多多有一个长度为n的字符串，这个字符串由26个小写字母组成.

多多可以对这个字符串进行多次操作，每次操作可以把该字符串中一段连续的回文子串删除（单个字符也属于回文串），删除后剩下的串会拼在一起.

请问最少需要多少次操作可以将这个字符串删光.

输入描述

第一行，包含一个正整数T（1≤T≤20）代表测试数据的组数.

对于每组测试数据，仅有一行，代表这个字符串.（1≤n≤ 500）

保证\sigma n 不超过3000

输出描述

对于每组数据输出一行整数，代表多多在进行最少多少次操作后，可以将这个字符串删光.

A4

dp[i][j]代表最小操作数，从小到大枚举区间，并枚举区间分割点。

import sys

t = int(input())
for i in range(t):
    s = input()
    n = len(s)
    dp = [[n]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = 1
    for k in range(1, n):
      for j in range(0,n-k):
        if s[j] == s[j+k]:
          if k == 1:
            dp[j][j+k] = 1
          else:
            dp[j][j+k] = dp[j+1][j+k-1]
        for i in range(j, j+k):
          dp[j][j+k] = min(dp[j][j+k], dp[j][i] + dp[i+1][j+k])
    print(dp[0][n-1])