Week1

CF1348E

题意

$n(n<=500)$棵树,每棵树上有$a_i(a_i<=10^9)$个红果实和$b_i(b_i<=10^9)$个蓝果实。有可以装$k(k<=500)$个果实的篮子,一个篮子只能放同种颜色或同一棵树上的果实。求最多可以放满多少个篮子

题解

若有$n(n>=2)$个篮子装了颜色不同的果实,则一定可以将其转化为只装红色或蓝色果实的篮子和至多$1$个装不同颜色的篮子。

设$dp_{i,j}$为第$i$棵树装完后余下$j$个红果实所能装的最多的篮子数,令$sum=\sum_{j=1}^i{(a_j+b_j)}$此时蓝果实的个数应为$B=sum-dp[i][j]*k-j$

接下来考虑转移。若在第$i$棵树选择装不同颜色的篮子,枚举这个篮子中红色果实的个数$s$,若有$s+b[i]>=k$,则

$dp[i+1][(j+a_i-s)\%k]=max\{dp[i+1][(j+a_i-s)\%k],dp[i][j]+1+(j+a_i-s)/k+(B+b_i-(k-s))/k\}$

若在第$i$棵树不选择装不同颜色的篮子,则$dp[i+1][(j+a_i)\%k]=max\{dp[i+1][(j+a_i)\%k],dp[i][j]+(j+a_i)/k+(B+b_i)/k\}$

最后取最大值即可

CF1348F

题意

长度为$n(n<=2*10^5)$的序列,每个位置$i$上有$L_i,R_i$表明第$i$位上的数$x$只能为$L_i<=x<=R_i$,问是否有唯一的一种方案可以将$1,2...n$放入到序列中,如果有多种方案输出其中两种。

题解

我们可以先将$L_i,R_i$按照$L_i$排序,对于每一个数$now$,将所有$L_i<=now$的区间的$R_i$放入$set$中,找到比$now$大且最小的一个$R_i$,$now$即可放在位置$i$处,同时将$set$中$R_i$删除,这样我们即可找到一组合法解。

如果有多种情况,必有一种情况为仅交换其中两个的顺序。考虑两个数$i,j(i<j)$,$pos_i$代表$i$所在的位置,因此我们有$L_{pos_i}<=i<=R_{pos_i},L_{pos_j}<=j<=R_{pos_j}$,若$i,j$可交换,则必有$L_{pos_j}<=i<j<=R_{pos_i}$,因此用线段树维护区间$[l,r]$中$R[x]$最大的点$x$即可