题意：

n个学生有两种买票方式，其一是每个人付费a，其二是最多润许三人的团体费用b

题解：

对比如下三种选择的花费即可：

1：为每个人采用方案一，总花费cost1 = a*n

2：为所有完整的三人小组购买方案二，剩余的人购买方案一，总花费cost2 = (n%3)*a + (n//3)*b

3：全部购买方案二，总花费cost3 = (n//3 + 1)*b

1
for _ in range(int(input())):
2
    n, a, b = map(int, input().split())
3
    cost1 = n * a
4
    cost2 = -(-n // 3) * b
5
    q = n // 3
6
    r = n % 3
7
    cost3 = q * b + min(r * a, b)
8
    print(min(cost1, cost2, cost3))

题意：

给定一个仅包含1~4的字符串s

求删掉的最小个数，使得按顺序从s中获取长度为2的子序列拼成的数字不能被4整除

题解：

显然的原字符串中4是必须删去的

此外，能被4整除的序列还有12和32

设计dp13和dp2

遍历字符c，如果字符为'2'，那么当前字符只能加到'2'后面，dp2 += 1;如果字符为'3'或者'1'，那么该字符可以加到'2'后面，也可以加到'1，3'后面，取二者的最大值：dp13 = max(dp2,dp3) + 1

那么剩下的最大的合法长度就是max(dp13,dp2)

1
for _ in range(int(input())):
2
    s = list(input().strip())
3
    ss = []
4
    ans = 0
5
    for ch in s:
6
        if ch == '4':
7
            ans += 1
8
        else:
9
            ss.append(ch)
10
    dp2 = dp3 = 0
11
    for x in ss:
12
        # 如果当前这个 '2' 想要加入到后面的 '1, 3' 阵营是不行的（会变成 12 或 32）
13
        # 所以只能更新纯 '2' 的长度
14
        if x == '2':
15
            dp2 += 1
16
        # '1' 或 '3' 可以接在当前的纯 '2' 后面，也可以接在已有的 '1, 3' 后面
17
        # 我们取两者的最大值，加 1
18
        else:
19
            dp3 = max(dp2,dp3) + 1
20
    # 剩下的最大的合法长度
21
    rem = max(dp2,dp3)
22
    ans += (len(ss) - rem)
23
    print(ans)

题意：

有n张牌，第n张牌有c个

选择需要从所有牌中至少取出3张将取出的牌排成圆圈满足：

任意连续的三张牌中，至少有两张牌的数字相同

求最大的取牌数

题解：

XXX1XX1XX1XXYY1YYY

对于每一个数量≥2的牌，为了包裹k个1，需要(k+1)对XX

则 x ≥ 2*(k+1)

所以其能够包裹的最大的单独为1的个数为：x//2 - 1

特殊情况：

若只有一种≥2的牌，则最大包裹个数为x//2

根据计算出的最大包裹的1个数，用总数减去该数即为答案

1
t = int(input())
2
for _ in range(t):
3
    n = int(input())
4
    c = list(map(int,input().split()))
5
    s = sum(c)
6
    one = st = 0
7
    for x in c:
8
        if x == 1:
9
            one += 1
10
        else:
11
            st += x//2 - 1
12
    if one == n - 1:
13
        st += 1
14
    wast = max(0,one - st)
15
    if s - wast < 3:
16
        print(0)
17
    else:
18
        print(s - wast)

题意：

给定两个城市在$n$天内各自播放的剧集序列$a$和$b$。两人需选择一个连续区间$[L, R]$，要求在此期间每一天两人必须满足：要么同时观看同一集，要么同时什么都不看。初始进度均为 0，且必须按顺序观看。求满足此条件的区间$[L, R]$** 的总数。** ​

题解：

这道题本质上是一个基于动态规划的区间计数问题，结合了贪心与逆向思维。其核心在于：如何在一个$O(N)$的时间内，快速计算出每一个左端点$i$ 所能延伸到的最远合法右端点。

以下是详细的题解思路：

1. 问题模型抽象

我们要统计所有满足条件的区间$[L, R]$。一个区间合法，当且仅当：

• 同步性：区间内每一天，两人要么看同一集，要么都不看。
• 进度一致：如果这一天他们看剧，那必须是他们当前看过的下一集。
• 不剧透：两人在区间内的任何时刻，进度都必须严格一致。如果某一天两地放的剧集不同，且其中一人看了剧，就会导致进度不同步或剧透。

2. 为什么选择逆向遍历？

如果我们从左向右扫描，很难判断当前区间是否会因为后面的某一天而失效。

如果我们从后向前（从$n-1$到$0$）遍历，对于每一个起始位置$i$：

• 我们维护pa[x]和pb[x]：分别记录剧集$x$在 Alice 和 Bob 的城市中，在当前索引$i$** 及其之后**第一次出现的位置。
• 我们可以实时知道：如果从$i$开始看剧，下一集$x+1$ 在两地分别会在哪里出现。

3. 核心动态规划状态：dp[i]

我们需要定义一个状态dp[i]：如果两人在索引$i$** 处刚好一起看完了同一集（且该集之后要看的是下一集），那么这个同步状态能向右无剧透延伸到的最远右边界。** ​

1
for _ in range(int(input())):
2
    n = int(input())
3
    a = [int(x) - 1 for x in input().split()]
4
    b = [int(x) - 1 for x in input().split()]
5
    # pa[x] 记录剧集 x 在 a 中的位置，pb[x] 同理
6
    # 初始化为 n，表示未出现
7
    pa = [n] * (n + 1)
8
    pb = [n] * (n + 1)
9
    dp = [n] * (n + 1)
10
    ans = 0
11
    # 从后往前遍历
12
    for i in range(n-1, -1, -1):
13
        pa[a[i]] = i
14
        pb[b[i]] = i
15
        # 如果这一天两人看同一集
16
        if a[i] == b[i]:
17
            x = a[i] + 1
18
            # 如果下一集在两人城市中出现位置相同，则继承该位置的 dp 状态
19
            if pa[x] == pb[x]:
20
                dp[i] = dp[pa[x]]
21
            else:
22
                # 否则，能走到的最远距离受限于两者中先出现的位置
23
                dp[i] = min(pa[x], pb[x])
24

25
        # 统计答案
26
        # 如果第 0 集（即原始编号 1）在两地的位置不同，说明区间 [i, min(pa[0], pb[0]) - 1] 是合法的
27
        if pa[0] != pb[0]:
28
            ans += min(pa[0], pb[0]) - i
29
        else:
30
            # 否则，利用 dp 数组跳转到下一次同步的终点
31
            ans += dp[pa[0]] - i
32
    print(ans)