fdu-oh

RedLycoris · 2024-06-16 19:41:22 · 科技·工程

T1

题目大意：

给你一个长度为 n\le3\times10^5 的字符串，支持修改和查询。每次询问给定区间 [l,r]，求出其中最长的全由一个个 fudan 组成的子序列的长度。

考虑使用线段树。每个节点存 [l,r] 内如果第一个有用的字符是 i，那么它对应的区间内最右边的有用的字符为 ri_i，个数为 cnt_i，暴力合并即可。

T2

一个朴素的想法是先二分答案（毕竟要求下取整），然后对所有 a_i 先减去这个答案，要求每段 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]: //sum是前缀和，即[f+1,i]这段的和>=0
                        dp[i][j]=min(dp[i][j],dp[f][j-1])
                    dp[i][j]=min(dp[i][j],dp[f][j-1])+1

这边加入一个线段树优化转移可以加速dp，但是复杂度仍然超标。

发现这种形式下每次转移 dp_{i,j} 最多只会+1，考虑从这里入手。

对于直接+1的情况，我们直接维护 i 递减，dp_{i,j} 递增的单调队列即可。

考虑不+1的情况。现在的 dp_{i,j} 要再更新最多只会在原来的基础上-1。维护一下对于每段区间是否存在即可。

T3

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

于是大胆猜测对于一行（或一列）有多个弹弓的情况，只需要考虑率他们两两的差的gcd的2倍即可。

T4

观察到一三象限只会和二四象限碰撞。直接暴力连边跑最小割。

对于判断两辆车是否相撞，可以先把他们通过绕原点旋转90度转到第1、2象限，然后枚举那辆车先通过。