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

发表于 分类于

原文：洛谷专栏

T1

给定一个长度为 的字符串，支持修改和查询。每次询问给定区间 ，求其中最长的、由若干个 fudan 组成的子序列长度。

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

T2

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

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

1
2
3
4
5
6
7
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)

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

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

T3

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

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

T4

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

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