版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - Codeforces Round #645 Div. 2 (A-D)" categories:
给定 $n\times m$ 矩形, 每一条长度为 1 的边均是一条街道(例如 $2\times2$ 的矩形有 12 条街道)
每条街道的中点均可放置一盏路灯, 路灯可照亮与之相邻的两个方格(若在边缘则为一个)
问至少需要几盏路灯可照亮全部方格
稍微想想就能发现, 答案即为 $\displaystyle\left\lceil\frac{mn}{2}\right\rceil$
Maria 要邀请一些人来开派对, 她一共可邀请 $n$ 个人, 第 $i$ 个人只有在当前在场人数(包括 Maria 和自己)严格大于$d_i$ 时才会赴约
Maria 可以一次性邀请多人, 此时在场人数按已赴约人数+当前邀请人数来计算
Maria 可以邀请无限次, 问派对最多可以有多少人
显然, 如果 $d_i>n$, 那对应的人肯定不会赴约
我们可以把 $d_i$ 从低到高排个序, 然后尽可能邀请要求低的
具体来说就是: 记录当前拟邀请人数, 如果已赴约人数+拟邀请人数严格大于拟邀请人员中要求最高的, 就把他们邀请过来
最后剩下的就是请不动的人了
我们可以开个大小为n的桶统计所有 $d_i$ 相同的人数
接下来从1到n遍历来统计拟邀请人数
把 $d_i$ 从低到高排个序, 然后从高到低遍历寻找第一个值 $\leqslant$ 下标的数
因为官方题解用的快排, 所以复杂度要高一些, 完全可以换成桶排
单次 $\Theta(n)$
给定如下形式的矩阵
规定
路径: 从 $(x_1,y_1)$ 经若干步转移到达 $(x_2,y_2)~(x_1\leqslant x_2,y_1\leqslant y_2)$, 以经过的所有格子上值的和为该路径的值
称两个路径不同, 当且仅当两个路径的值不同
问从 $(x_1,y_1)$ 到 $(x_2,y_2)~(x_1\leqslant x_2,y_1\leqslant y_2)$ 的不同路径数
我们可以发现, 任意一格的下侧格子值总比右侧格子值大 1
所以, 只要将路径中出现的"右 $\to$ 下"改成"下 $\to$ 右"就能使路径值+1
显然, 我们可以通过有限步上述操作将"右 $\to...\to$ 右 $\to$ 下 $\to...\to$ 下"变为"下 $\to...\to$ 下 $\to$ 右 $\to...\to$ 右", 同时该过程中路径的值严格单调增加
例如
显然上述前者为最短路径, 后者为最长路径
而显然任意位于两者之间的值都有路径与之对应
故答案即为最长路径-最短路径+1
实际上我们不需要求出最短路径和最长路径的值
观察上图, 我们将最短路径变为最长路径一共用了 $(x_2-x_1)(y_2-y_1)$ 步, 每一步都使路径值+1
也就是说 $(x_2-x_1)(y_2-y_1)$ 就是最长路径-最短路径
故结果为 $(x_2-x_1)(y_2-y_1)+1$
挺简单一道题咕了 4 天, 比赛时代码写得太乱就没写完, 我太菜了
给定数n,x和数组d[1..n], 由这组数可构造一个数组l[1..sum(d[],1,n)]满足
$$ l{\sum{i=1}^{j-1}d_i+k}=k,~j=1,2,...,n;k=1,2,...,d_j $$
即将每个 $d_i$ 均扩展成 ${1,2,...,d_i}$, 然后将所有的按顺序拼接在一起
求l[]首尾相接形成的环中, 长度为x的子区间和的最大值
举个例子, $n=5, x=6,d={4,2,3,1,3}$
那么 $l={1,2,3,4,1,2,1,2,3,1,1,2,3}$
答案为 $15$, 对应的子区间为 ${2,3,1,2,3,4}$
尺取法
显然构造出l[]之后再用l[]求会使时空双双爆炸
但是l[]的特殊性质使得我们可以通过d[]来解决问题, 这时候我们可以当作对l[]做了一个按给定方案进行的分块
我们可以很轻松的求出每一块的和 ($d(d+1)\over2$), 零碎部分也很好求
处理环上的区间问题, 我们往往会直接将其复制一份并接在末尾, 这样就断环为线了 (d[1..n] -> d[1..2n])
我们注意到, 如果某区间为最优解, 则区间的右端点一定为局部的峰值, 所以我们在枚举的时候可以直接把右端点定为 $d_i$, 这也就相当于倒序枚举 $d_i$
下一个问题就是解决怎么处理左端点了
官方题解用的二分, 我用的前缀和
首先记录d[1..2n]的前缀和sum_d[1..2n], 然后最开始让l = 2n, 当r从2n到n枚举的时候, 只需要保持sum_d[r] - sum_d[l-1] > x即可, 这样就找到了左端点
最后一个问题是处理区间和
就像我上面所说的, 整块直接求, 剩下零碎部分的另求 ($\frac{d(d+1)}{2}-\frac{d'(d'+1)}{2}$, 其中 $d'$ 是左端点所指的块中没被区间覆盖上的元素数)
这里可以用前缀和也可以不用, 用前缀和就非常简单了, 我没用前缀和是因为我最开始的思路有问题
我的处理方法就是在移动区间的时候减去右端点指向的块, 再补上左边部分
突然发现这不是莫队吗
最后的最后补充个细节, 如果按我的做法处理, 在枚举下一个右端点之前记得把零碎部分减掉
首先 $\Theta(n)$ 读入数据并求前缀和
然后再 $\Theta(n)$ 遍历右端点, 在总的遍历过程中, 每个sum[]和d[]中元素被访问次数为 1 或 2, 故遍历的总复杂度为 $\Theta(n)$
因此最终复杂度为 $\Theta(n)$