2024复旦大学信息学强基题目

原文：洛谷专栏

T1

给定一个长度为 $n\le 3\times 10^5$ 的字符串，支持修改和查询。每次询问给定区间 $[l,r]$，求其中最长的、由若干个 fudan 组成的子序列长度。

考虑使用线段树。每个节点存：若区间内第一个有用字符是 $i$，那么对应区间内最右边的有用字符 $r_i$ 和字符个数 $cnt_i$。合并时枚举状态即可。

T2

一个朴素想法是先二分答案（因为要求下取整），然后让所有 $a_i$ 减去这个答案，要求每一段的和大于 $0$，再进行 DP。

令 $dp_{i,j}$ 表示考虑到第 $i$ 个人、此前已经分了 $j$ 段时，最少有多少段的和小于 $0$。转移大致为：

for i in [1,n]:
    for j in [1,k]:
        for f in [i-r,i-l]:
            if sum[i] >= sum[f]:
                dp[i][j] = min(dp[i][j], dp[f][j-1])
            else:
                dp[i][j] = min(dp[i][j], dp[f][j-1] + 1)

加入线段树可以优化转移，但复杂度仍然超标。

观察这种形式下每次转移的 $dp_{i,j}$ 最多只会加 $1$。对于直接加 $1$ 的情况，维护 $i$ 递减、$dp_{i,j}$ 递增的单调队列。对于不加 $1$ 的情况，新的 $dp_{i,j}$ 最多只会在原值基础上减 $1$，维护每段区间内相应状态是否存在即可。

T3

首先可以看出每次跳之后，行或者列的奇偶性不变。

于是大胆猜测：对于一行（或一列）有多个弹弓的情况，只需要考虑它们两两位置差的最大公约数的两倍。

T4

观察到一、三象限的车辆只会和二、四象限的车辆碰撞。直接暴力连边并运行最小割。

判断两辆车是否相撞时，可以先将它们绕原点旋转 $90^\circ$，转到第一、第二象限，然后枚举哪辆车先通过。