Q1

捕获

小美在玩一项游戏。该游戏的目标是尽可能抓获敌人。

敌人的位置将被一个二维坐标 (x, y) 所描述。

小美有一个全屏技能，该技能能一次性将若干敌人一次性捕获。

捕获的敌人之间的横坐标的最大差值不能大于A，纵坐标的最大差值不能大于B。

现在给出所有敌人的坐标，你的任务是计算小美一次性最多能使用技能捕获多少敌人。

输入描述

第一行三个整数N,A,B，表示共有N个敌人，小美的全屏技能的参数A和参数B。

接下来N行，每行两个数字x,y，描述一个敌人所在的坐标。

1≤N≤500，1≤A,B≤1000，1≤x,y≤1000。

输出描述

一行，一个整数表示小美使用技能单次所可以捕获的最多数量。

样例输入

3 1 1

1 1

1 2

1 3

样例输出

2

这题枚举左上角的点即可 笔试的时候加了绝对值方法错了 以为a了就没管 不加绝对值应该是可以的

Q2

彩带

题目描述：

小美现在有一串彩带，假定每一厘米的彩带上都是一种色彩。

因为任务的需要，小美希望从彩带上截取一段，使得彩带中的颜色数量不超过K种。

显然，这样的截取方法可能非常多。于是小美决定尽量长地截取一段。

你的任务是帮助小美截取尽量长的一段，使得这段彩带上不同的色彩数量不超过K种。

输入描述

第一行两个整数N,K，以空格分开，分别表示彩带有N厘米长，你截取的一段连续的彩带不能超过K种颜色。

接下来一行N个整数，每个整数表示一种色彩，相同的整数表示相同的色彩。

1≤N,K≤5000，彩带上的颜色数字介于[1, 2000]之间。

输出描述

一行，一个整数，表示选取的彩带的最大长度。

样例输入

8 3

1 2 3 2 1 4 5 1

样例输出

5

lc常规滑动窗口

n, k = map(int, input().split())
*nums, = map(int, input().split())
cnt = 0 
from collections import defaultdict 
hm = defaultdict(int) 
l = r = 0 
res = 0
while r < len(nums):
    hm[nums[r]] += 1
    if hm[nums[r]] == 1:
        cnt += 1
    while cnt > k:
        hm[nums[l]] -= 1
        if hm[nums[l]] == 0:
            cnt -= 1
        l += 1
    res = max(res, r - l + 1)
    r += 1
print(res)

Q3

回文串

时间限制： 3000MS

内存限制： 589824KB

题目描述：

现在小美获得了一个字符串。小美想要使得这个字符串是回文串。

小美找到了你。你可以将字符串中至多两个位置改为任意小写英文字符’a’-‘z’

你的任务是帮助小美在当前制约下，获得字典序最小的回文字符串。

数据保证能在题目限制下形成回文字符串。

注：回文字符串：即一个字符串从前向后和从后向前是完全一致的字符串。

例如字符串abcba, aaaa, acca都是回文字符串。字符串abcd, acea都不是回文字符串。

输入描述

一行，一个字符串。字符串中仅由小写英文字符构成。

保证字符串不会是空字符串。

字符串长度介于 [1, 100000] 之间。

输出描述

一行，一个在题目条件限制下所可以获得的字典序最小的回文字符串。

样例输入

acca

样例输出

aaaa

分类讨论即可

s = input().split()[0]
s = list(s)
l = 0 
r = len(s) - 1
res = 2
tmp = []
while l < r:
    if s[l] != s[r]:
        tmp.append([l,r])
    l += 1
    r -= 1
if len(tmp) == 2:
    s[tmp[0][0]] = min(s[tmp[0][0]],s[tmp[0][1]])
    s[tmp[0][1]] = min(s[tmp[0][0]],s[tmp[0][1]])
    s[tmp[1][0]] = min(s[tmp[1][0]],s[tmp[1][1]])
    s[tmp[1][1]] = min(s[tmp[1][0]],s[tmp[1][1]])
elif len(tmp) == 1:
    c = min(s[tmp[0][0]],s[tmp[0][1]])
    if c != 'a':
        s[tmp[0][0]] = 'a'
        s[tmp[0][1]] = 'a'
    else:
        s[tmp[0][0]] = 'a'
        s[tmp[0][1]] = 'a'
        if len(s) % 2 == 1:
            s[len(s) // 2] = 'a'
else:
    l = 0
    r = len(s) - 1
    cnt = 2
    while cnt > 0 and l <= r:
        if s[l] != 'a':
            s[l] = 'a'
            s[r] = 'a'
            cnt -= 2
        l += 1
        r -= 1
print("".join(s))

Q4

商店

题目描述：

现在商店里有N个物品，每个物品有原价和折扣价。

小美想要购买商品。小美拥有X元，一共Y张折扣券。

小美需要最大化购买商品的数量，并在所购商品数量尽量多的前提下，尽量减少花费。

你的任务是帮助小美求出最优情况下的商品购买数量和花费的钱数。

输入描述

第一行三个整数，以空格分开，分别表示N,X,Y。

接下来N行，每行两个整数，以空格分开，表示一个的原价和折扣价。

1≤N≤100, 1≤X≤5000, 1≤Y≤50，每个商品原价和折扣价均介于[1,50]之间。

输出描述

一行，两个整数，以空格分开。第一个数字表示最多买几个商品，第二个数字表示在满足商品尽量多的前提下所花费的最少的钱数。

样例输入

3 5 1

4 3

3 1

6 5

样例输出

2 5

两个三维dp，python三维度会tle，压缩到二维即可

n, x, y = map(int, input().split())
nums = []
for _ in range(n):
    a, b = map(int, input().split())
    nums.append([a, b])

dp = [[0] * (y + 1) for _ in range(x + 1)]
for i in range(1, n + 1):
    for j in range(x, -1, -1):
        for k in range(y, -1, -1):
            if j >= nums[i - 1][0]:
                dp[j][k] = max(dp[j][k],dp[j - nums[i - 1][0]][k] + 1)
            if j >= nums[i - 1][1] and k != 0:
                dp[j][k] = max(dp[j][k],dp[j - nums[i - 1][1]][k - 1] + 1)
mx = dp[-1][-1]
dp = [[1 << 60] * (y + 1) for _ in range(mx + 1)]
for k in range(y + 1):
    dp[0][k] = 0 
for i in range(1, n + 1):
    for j in range(mx, - 1, - 1):
        for k in range(y, -1, -1):
            dp[j][k] = min(dp[j][k], dp[j - 1][k] + nums[i - 1][0])
            if k != 0:
                dp[j][k] = min(dp[j][k], dp[j - 1][k - 1] + nums[i - 1][1])
    
print(mx, dp[-1][-1])